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