06 Logical Reasoning

• logical formula

• assignment of a truth value for all propositional symbols in a sentance

• n symbols -> 2^n models

• m is a model of sentance s < = > s evaluates to true given m

• set of sentances

m is model of knowledge base

<= >

m is a model for all sentances s in m

knowledge base is satisfiable

< = >

it has at least one model

knowledge base is unsatisfiable

< = >

there is no model for KB

knowledge base is tautology

< = >

all models are valid for KB

sentance b follows logically from sentance a:

a |= b

< = >

in every model in which a is true, b is also true

sentance b follows logically from knowledge base KB:

KB |= b

< = >

every model of KB is also a model of b

a and b are logical equivalent:

a ≡ b

< = >

a |= b AND b |= a

“a and b have the same models”

• using inference rules, we can increase the knowledge base

• given that both sentances on the left are in the KB, and the inference rule holds:

  we can add right sentance to the KB

given KB (knowledge base) and I (inference rules):

• apply inference rules successively to increase KB

Idea:

• apply inference on KB to derive new information and make decisions

Structure:

• agent maintains KB

  • initial knowledge

  • learns from perceptions

• agent function queries KB for next action

• limited expressive power

  • e.g. can not say: “pits cause breezes in adjacent squares”

  • except for writing a sentance for each square

given:

• KB over p_n variables

• Inference rules I

• sentance a

task:

• proving that KB |= a

search problem:

• states: each state is a KB

• initial state: given KB

• actions: actions represent applying a inference rule to a KB

• successor states: KB + inferred proposition

• goal test: a in KB?

• lower bound: 2^n

• upper bound: inf