Logic in Computer Science An Introductory Course for Master Students Wang iwang@nudt.edu.cn Lecture 3 Propositional Calculus( Cont'd) Logic in Computer Science- p1/17
Logic in Computer Science An Introductory Course for Master Students Wang Ji jiwang@nudt.edu.cn Lecture 3 Propositional Calculus(Cont’d) Logic in Computer Science – p.1/17
COMPLETENESS THEOREM Logic in Computer Science- p 2/17
Completeness Theorem Logic in Computer Science – p.2/17
Completeness of r r is complete iff for any wff A A∈Tor~A∈ ience-p. 3/17
Completeness of Γ Γ is complete iff for any wff A A ∈ Γ or ∼ A ∈ Γ Logic in Computer Science – p.3/17
Let t be a consistent set of wffs define a sequence as follows ∫△nU{An}△n +1 △nU{~An} otherwise =0 Logic in Computer Science- p4/17
∆Γ Let Γ be a consistent set of wffs. Define a sequence as follows. ∆0 = Γ ∆n+1 = ∆n ∪ {An} if ∆n ` An ∆n ∪ {∼ An} otherwise ∆Γ = S∞n=0 ∆n Logic in Computer Science – p.4/17
Some Properties 1.△ Is consistent. 2.T∈△nC△ n+1 r is complete 4.f△ r HA then there exists n∈ N such that △n}A 5.A∈△rif△r}A 6.△ r Is consistent Logic in Computer Science- p 5/17
Some Properties 1. ∆n is consistent. 2. Γ ⊆ ∆n ⊆ ∆n+1 ⊆ ∆Γ 3. ∆Γ is complete. 4. If ∆Γ ` A then there exists n ∈ N such that ∆n ` A. 5. A ∈ ∆Γ iff ∆Γ ` A 6. ∆Γ is consistent. Logic in Computer Science – p.5/17
or is an assignment TifA∈△r F otherwise Or is an assignment Logic in Computer Science- p6/17
φΓ is an assignment φΓ(A) = T if A ∈ ∆Γ F otherwise φΓ is an assignment. Logic in Computer Science – p.6/17
Completeness Theorem If a then Th A Godel 1930 H A iff a TH iffT ience-p.7/17
Completeness Theorem If Γ |= A then Γ ` A (G¨odel 1930) • ` A iff |= A • Γ ` A iff Γ |= A Logic in Computer Science – p.7/17
For any wff A, let a if O(A)=T N A if (A)=F Lemma Let all variables in a be among pi, . . pn. Then p,…,p2+A° Logic in Computer Science-p8/17
Aφ For any wff A, let Aφ = A if φ(A) = T ∼ A if φ(A) = F Lemma: Let all variables in A be among p1, · · · , pn. Then pφ1 , · · · , pφn ` Aφ Logic in Computer Science – p.8/17
Another Proof of Completeness Theorem? Every tautology is a theorem of p Proof Sketch: By using the above lemma. Let a be a wff and let nm be the number of variables which occurred in a Prove that for any assignment pi,,,P, F A by induction on m-j(0≤j≤m) Logic in Computer Science - p 9/17
Another Proof of Completeness Theorem? Every tautology is a theorem of P. Proof Sketch: By using the above lemma. Let A be a wff and let n be the number of variables which occurred in A. Prove that for any assignment φ, pφ1 , · · · , pφj ` A by induction on n − j(0 ≤ j ≤ n). Logic in Computer Science – p.9/17
Compactness Satisfiability and consistency are coextensive Let i be any set of wffs, I is satisfiable iff r is consistent Compactness Theorem T is satisfiable iff every finite subset of r is satisfiable Logic in Computer Science- p10/17
Compactness Satisfiability and consistency are coextensive. • Let Γ be any set of wffs, Γ is satisfiable iff Γ is consistent. • Compactness Theorem Γ is satisfiable iff every finite subset of Γ is satisfiable. Logic in Computer Science – p.10/17