Propositional Logic

Sentance

logical formula

Model

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

n symbols -> 2^n models

When is m a model of sentance s?

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

Knowledge base

set of sentances

When is m a model of a knowledge base (KB)?

m is model of knowledge base

<= >

m is a model for all sentances s in m

When is a knowledge base satisfiable?

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

Logical entailment

a |= b

sentance b follows logically from sentance a:

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

KB |= b

sentance b follows logically from knowledge base KB:

every model of KB is also a model of b

Logical equivalence

a ≡ b

a and b are logical equivalent:

a |= b AND b |= a

“a and b have the same models”

Inference rules

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

Inference

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

apply inference rules successively to increase KB

Knowledge based agent

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

Problem of propositional logic

limited expressive power

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

except for writing a sentance for each square

First order logic

Logical search problem

given:

KB over p_n variables

Inference rules I

sentance a

task:

proving that KB |= a

Logical search:

Search definition

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?

State space

lower bound: 2^n

upper bound: inf

Last changeda year ago