CS344 : Introduction to Artificial Intelligence
Pushpak Bhattacharyya
CSE Dept., IIT Bombay
Lecture 9,10,11- Logic; Deduction Theorem
23/1/09 to 30/1/09
Logic and inferencing
Vision NLP
Expert Systems
Planning Robotics
Search
Reasoning
Learning
Knowledge
Obtaining implication of given facts and rules -- Hallmark of intelligence
Propositions
− Stand for facts/assertions
− Declarative statements
− As opposed to interrogative statements (questions) or imperative statements (request, order)
Operators
=> and ¬ form a minimal set (can express other operations) - Prove it.
Tautologies are formulae whose truth value is always T, whatever the assignment is
) ( (~),
), ( ),
( OR NOT IMPLICATION AND
Model
In propositional calculus any formula with n propositions has 2n models (assignments)
- Tautologies evaluate to T in all models.
Examples:
1)
2)
-e Morgan with AND
P P
) (
)
( P Q P Q
Formal Systems
Rule governed
Strict description of structure and rule application
Constituents
Symbols
Well formed formulae
Inference rules
Assignment of semantics
Notion of proof
Notion of soundness, completeness, consistency, decidability etc.
Hilbert's formalization of propositional calculus 1. Elements are propositions : Capital letters
2. Operator is only one : (called implies) 3. Special symbol F (called 'false')
4. Two other symbols : '(' and ')'
5. Well formed formula is constructed according to the grammar WFF P|F|WFFWFF
6. Inference rule : only one Given AB and
A
write B
known as MODUS PONENS
7. Axioms : Starting structures A1:
A2:
A3
This formal system defines the propositional calculus ))
(
(A B A
))) (
) ((
)) (
((A B C A B A C
) )
)
(((A F F A
Notion of proof
1.
Sequence of well formed formulae 2. Start with a set of hypotheses3. The expression to be proved should be the last line in the sequence
4. Each intermediate expression is either one of the hypotheses or one of the axioms or the result of modus ponens
5. An expression which is proved only from the axioms and inference rules is called a THEOREM within the system
Example of proof
From P and and prove R H1: P
H2:
H3:
i) P H1
ii) H2
iii) Q MP, (i), (ii)
iv) H3
v) R MP, (iii), (iv)
Q P
Q P
Q P
R Q
R Q
R Q
Prove that is a THEOREM
i) A1 : P for A and B
ii) A1: P for A and for B
iii)
A2: with P for A, for B and P for C
iv) MP, (ii), (iii)
v) MP, (i), (iv)
) (P P
) )
((P P P
P
)
(P P
P
))]
( ))
( ((
)) )
((
[(P P P P P P P P P
) (P P ))
( )
(
(P P P P P )
(P P
) (P P
Formalization of propositional logic (review)
Axioms :
A1 A2 A3 Inference rule:
Given and A, write B A Proof is:
A sequence of i) Hypotheses ii) Axioms
iii) Results of MP A Theorem is an
Expression proved from axioms and inference rules
)) (
(A B A
))) (
) ((
)) (
((A B C A B A C
) )
)
(((A F F A
) (A B
Example: To prove
i) A1 : P for A and B
ii) A1: P for A and for B
iii)
A2: with P for A, for B and P for C
iv) MP, (ii), (iii)
v) MP, (i), (iv)
) (P P
) )
((P P P
P
)
(P P
P
))]
( ))
( ((
)) )
((
[(P P P P P P P P P
) (P P ))
( )
(
(P P P P P )
(P P
) (P P
Shorthand
1. is written as and called 'NOT P'
2. is written as and called
'P OR Q’
3. is written as and called
'P AND Q' Exercise: (Challenge)
- Prove that
¬P P F
) )
((P F Q (P Q)
) ))
(
((P Q F F (P Q)
)) (
( A
A
A very useful theorem (Actually a meta theorem, called deduction theorem)
Statement If
A1, A2, A3 ... An ├ B then
A1, A2, A3, ...An-1├
├ is read as 'derives' Given
A1 A2 A3 . .. . An
B Picture 1
A1 A2 A3 . . .. An-1
Picture 2 B
An
B An
Use of Deduction Theorem Prove
i.e.,
├ F (M.P)
A├ (D.T)
├ (D.T)
Very difficult to prove from first principles, i.e., using axioms and inference rules only
)) (
( A
A
) )
((A F F
A
F A
A,
F F
A ) (
) )
((A F F
A
Prove i.e.
├ F
├ (D.T)
├ Q (M.P with A3) P├
├
) (P Q P
) )
((P F Q
P
F Q
F P
P, ,
F P
P ,
(Q F) FQ F
P ) (
) )
((P F Q
P
Formalization of propositional logic (review)
Axioms :
A1 A2 A3 Inference rule:
Given and A, write B A Proof is:
A sequence of i) Hypotheses ii) Axioms
iii) Results of MP A Theorem is an
Expression proved from axioms and inference rules
)) (
(A B A
))) (
) ((
)) (
((A B C A B A C
) )
)
(((A F F A
) (A B
Example: To prove
i) A1 : P for A and B
ii) A1: P for A and for B
iii)
A2: with P for A, for B and P for C
iv) MP, (ii), (iii)
v) MP, (i), (iv)
) (P P
) )
((P P P
P
)
(P P
P
))]
( ))
( ((
)) )
((
[(P P P P P P P P P
) (P P ))
( )
(
(P P P P P )
(P P
) (P P
Shorthand
1. is written as and called 'NOT P'
2. is written as and called
'P OR Q’
3. is written as and called
'P AND Q' Exercise: (Challenge)
- Prove that
¬P P F
) )
((P F Q (P Q)
) ))
(
((P Q F F (P Q)
)) (
( A
A
A very useful theorem (Actually a meta theorem, called deduction theorem)
Statement If
A1, A2, A3 ... An ├ B then
A1, A2, A3, ...An-1├
├ is read as 'derives' Given
A1 A2 A3 . .. . An
B Picture 1
A1 A2 A3 . . .. An-1
Picture 2 B
An
B An
Use of Deduction Theorem Prove
i.e.,
├ F (M.P)
A├ (D.T)
├ (D.T)
Very difficult to prove from first principles, i.e., using axioms and inference rules only
)) (
( A
A
) )
((A F F
A
F A
A,
F F
A ) (
) )
((A F F
A
Prove i.e.
├ F
├ (D.T)
├ Q (M.P with A3) P├
├
) (P Q P
) )
((P F Q
P
F Q
F P
P, ,
F P
P ,
(Q F) FQ F
P ) (
) )
((P F Q
P
More proofs
) )
((
) (
. 3
) (
) (
. 2
) (
) (
. 1
Q P
Q Q
P
P Q
Q P
Q P
Q P
Proof Sketch of the Deduction Theorem
To show that If
A
1, A
2, A
3,… A
n|- B Then
A
1, A
2, A
3,… A
n-1|- A
n B
Case-1: B is an axiom
One is allowed to write A
1, A
2, A
3,… A
n-1|- B
|- B(A
nB)
|- (A
nB); mp-rule
Case-2: B is A n
A
nA
nis a theorem (already proved) One is allowed to write
A
1, A
2, A
3,… A
n-1|- (A
nA
n)
i.e. |- (A
nB)
Case-3: B is A i where (i <>n)
Since A
iis one of the hypotheses One is allowed to write
A
1, A
2, A
3,… A
n-1|- B
|- B(A
nB)
|- (A
nB); mp-rule
Case-4: B is result of MP
Suppose
B comes from applying MP on E
iand E
jWhere, E
iand E
jcome before B in
A
1, A
2, A
3,… A
n|- B
B is result of MP (contd)
If it can be shown that
A
1, A
2, A
3,… A
n-1|- A
n E
iand
A
1, A
2, A
3,… A
n-1|- (A
n( E
iB)) Then by applying MP twice
A
1, A
2, A
3,… A
n-1|- A
n B
B is result of MP (contd)
This involves showing that If
A
1, A
2, A
3,… A
n|- E
iThen
A
1, A
2, A
3,… A
n-1|- A
n E
i(similarly for AnEj)
B is result of MP (contd)
Adopting a case by case analysis as before,
We come to shorter and shorter length proof segments eating into the body of
A
1, A
2, A
3,… A
n|- B
Which is finite. This process has to
terminate. QED
Important to note
Deduction Theorem is a meta-theorem (statement about the system)
PP is a theorem (statement belonging to the system)
The distinction is crucial in AI
Self reference, diagonalization
Foundation of Halting Theorem, Godel
Theorem etc.
Example of ‘ of-about’
confusion
“This statement is false”
