国防科学技术大学：《数理逻辑》（英文版）Lecture 3 Propositional Calculus(Cont’d)

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