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
Zuletzt geändertvor 2 Jahren
