CS621: Artificial Intelligence
Pushpak Bhattacharyya
CSE Dept., IIT Bombay
Lecture–10: Soundness of Propositional Calculus
12th August, 2010
Soundness, Completeness &
Consistency
Soundness Syntactic
World ---
Theorems, Proofs
Semantic World ---
Valuation, Tautology
Soundness
Completeness
* *
Soundness
Provability Truth
Provability Truth
Completeness
Truth Provability
Soundness:
Correctness of the SystemProved entities are indeed true/valid
Completeness:
Power of the SystemTrue things are indeed provable
TRUE Expression
s System
Outside Knowledge Validation
Consistency
The System should not be able to prove both P and ~P, i.e., should not be prove both P and ~P, i.e., should not be able to derive
F
Examine the relation between Soundness
Soundness
&
Consistency
Soundness Consistency
If a System is inconsistent, i.e., can derive F , it can prove any expression to be a
F , it can prove any expression to be a theorem. Because
F P is a theorem
Inconsistency Unsoundness
To show that
FP is a theorem Observe that
F, PF ⊢⊢ F By D.T.
F ⊢ (PF)F; A3
⊢ P
i.e. ⊢ FP
Thus, inconsistency implies unsoundness
Unsoundness Inconsistency
Suppose we make the Hilbert System of
propositional calculus unsound by introducing (A /\ B) as an axiom
Now AND can be written as
Now AND can be written as
(A(BF )) F
If we assign F to A, we have
(F (BF )) F
But (F (BF )) is an axiom (A1)
Hence F is derived
Inconsistency is a Serious issue.
Informal Statement of Godel Theorem:
Informal Statement of Godel Theorem:
If a sufficiently powerful system is complete it is inconsistent.
Sufficiently powerful: Can capture at least
Peano Arithmetic
Introduce Semantics in Propositional logic
Valuation Function V
Definition of V Syntactic ‘false
Definition of V V(F ) = F
Where F is called ‘false’ and is one of the two symbols (T, F)
Semantic ‘false’
V(F ) = F
V(AB) is defined through what is called the truth table
truth table
V(A) V(B) V(AB)
T F F
T T T
F F T
F T T
Tautology
An expression ‘E’ is a tautology if V(E) = T
V(E) = T
for all valuations of constituent propositions Each ‘valuation’ is called a ‘model’.
To see that
(FP) is a tautology two models
V(P) = T V(P) = F V(FP) = T for both
F P is a theorem
Soundness Completeness
F P is a tautology
If a system is Sound & Complete, it does not matter how you “Prove” or “show the validity”
matter how you “Prove” or “show the validity”
Take the Syntactic Path or the Semantic Path
Syntax vs. Semantics issue
Refers to
FORM VS. CONTENT FORM VS. CONTENT
Tea
(Content) Form
Form & Content
logician
painter
musician
Godel, Escher, Bach
By D. Hofstadter
logician
Problem
(P Q) (P Q)
Semantic Proof Semantic Proof
A B
P Q P Q P Q AB
T F F T T
T T T T T
F F F F T
F T F T T
To show syntactically
(P Q) (P Q)
i.e.
[(P (Q F )) F ]
[(P F ) Q]
If we can establish (P (Q F )) F ,
⊢ (P (Q F )) F ,
(P F ), Q F ⊢ F This is shown as
Q F hypothesis
(Q F ) (P (Q F)) A1
Q F; hypothesis
(Q F) (P (Q F)); A1 P (Q F); MP
P (Q F); MP F; MP
Thus we have a proof of the line we
started with
Soundness Proof
Hilbert Formalization of Propositional Calculus is sound.
“Whatever is provable is valid”
Statement Given
Given
A
1, A
2, … ,A
n|- B
V(B) is ‘T’ for all V
sfor which V(A
i) = T
Proof
Case 1 B is an axiom Case 1 B is an axiom
V(B) = T by actual observation
Statement is correct
Case 2 B is one of A
isif V(A ) = T, so is V(B)
if V(A
i) = T, so is V(B)
statement is correct
Case 3 B is the result of MP on Ei & Ej Ej is Ei B
.
. Ej is Ei B
Suppose V(B) = F
Then either V(Ei) = F or V(Ej) = F
. . Ei
. . . Ej
. . . B
i.e. Ei/Ej is result of MP of two expressions coming before them
Thus we progressively deal with shorter and shorter proof body.
shorter proof body.
Ultimately we hit an axiom/hypothesis.
Hence V(B) = T
Soundness proved
A puzzle
(Zohar Manna, Mathematical Theory of Computation, 1974)
From Propositional Calculus
Tourist in a country of truth- sayers and liers
Facts and Rules: In a certain country, people either always speak the truth or always
lie. A tourist T comes to a junction in the country and finds an inhabitant S of the
country standing there. One of the roads at country standing there. One of the roads at the junction leads to the capital of the
country and the other does not. S can be asked only yes/no questions.
Question: What single yes/no question can T ask of S, so that the direction of the capital is revealed?
Diagrammatic representation
Capital
S (either always says the truth Or always lies)
T (tourist)
Deciding the Propositions: a very difficult step- needs human intelligence
P: Left road leads to capital
Q: S always speaks the truth
Meta Question: What question should the tourist ask
The form of the question
Very difficult: needs human intelligence
The tourist should ask
The tourist should ask
Is R true?
The answer is “yes” if and only if the left road leads to the capital
The structure of R to be found as a function of P and Q
A more mechanical part: use of truth table
P Q S’s
Answer
R
T T Yes T
T T Yes T
T F Yes F
F T No F
F F No T
Get form of R: quite mechanical
From the truth table
R is of the form (P x-nor Q) or (P ≡ Q)
Get R in
English/Hindi/Hebrew…
Natural Language Generation: non-trivial
The question the tourist will ask is
Is it true that the left road leads to the Is it true that the left road leads to the capital if and only if you speak the truth?
Exercise: A more well known form of this
question asked by the tourist uses the X-OR operator instead of the X-Nor. What changes do you have to incorporate to the solution, to get that answer?
