Transcript PPT printable

Propositional Logic
Predicate Logic
Review of Propositional
Logic
Propositional variables
Propositional constants: T, F
Logical connectives
Let P: Today is Sunday
Q: We have guests
P  Q : Today is Sunday and We have guests
P  Q : Today is Sunday or We have guests
P
: Today is not Sunday.
P  Q : if today is Sunday then we have guests.
P  Q : Today is Sunday if and only if we have guests.
2
Semantics
Propositions and expressions have
truth values: can be true or false.
The truth value of an expression is
determined by truth tables, e.g.:
P
Q
PvQ
T
T
F
F
T
F
T
F
T
T
T
F
3
Propositional Proof Theory
Propositional proof theory: A set of axioms
(logical identities) and inference rules used to
manipulate expressions and to obtain true
expressions out of other true expressions.
Inference rules: give a mechanical procedure to
obtain true expressions out of other true
expressions.
Modus ponens: P, P  Q |= Q
4
Resolution
A  B, B  C
|= A  C
compare with: B, B  C |= C
(B C = B  C)
If B is true, then C must be true, if B is false
than A must be true.
This means that WHENEVER the conjunction
(A  B)  (B  C) is true, A  C is also true.
5
How resolution works
Eliminate opposite literals and rewrite two
expressions as one
P1 v P2 P2
P1
P3 v P4
P1 v P3 v P4
This is the conclusion
6
Proof by refutation
P4 v P6
P6
P4
Add the negation of the
statement to be proved
P4
contradiction
7
Predicate Logic
Represents properties and relations by
using predicates with arguments.
likes(mary,apples)  likes(mary,grapes)
Quantifiers: indicate the scope of the predicate
Universal quantifier:
 X likes ( mary , X) Mary likes everything
Existential quantifier
 X likes ( mary , X)
there is something which Mary likes.
8
Proof Theory for Predicate Logic
Based on the resolution procedure.
Unification: matching predicates with variables
to atomic sentences (matching variables to
constants.)
Example: Is Socrates mortal?
 X (human(X)  mortal(X))
human(socrates)
human(plato)
alien(spock)
9
Knowledge representation
using predicate logic
Some books are interesting.
 x (book(x) Λ interesting(x))
Anybody that has a friend is not lonely
(If someone has a friend, they are not lonely)
x ( y friend(x,y)  ~lonely(x))
10
Prolog example
Predicate logic representation is used only on paper.
Computational implementation: logic
programming languages
In Logic and in Prolog:
 X  Y (father(X,Y) v mother(X,Y)  parent(X,Y))
 X  Y( ( Z(parent(Z,X)  parent(Z,Y)) 
siblings(X,Y))
parent(X,Y):- father(X,Y).
parent(X,Y):- mother(X,Y).
siblings(X,Y):- parent(Z,X),parent(Z,Y).
11