Logic in Computer Science An Introductory Course for Master Students Wang j iwang@nudt.edu.cn Lecture 10 Logic in Computer Science- p 1/21
Logic in Computer Science An Introductory Course for Master Students Wang Ji jiwang@nudt.edu.cn Lecture 10 Logic in Computer Science – p.1/21
COMPLETENSS Logic in Computer Science- p 2/21
Completenss Logic in Computer Science – p.2/21
Two forms of Completeness Theorem Let i be a set of wffs. The following parts are equivalent If r a then Th A Ifr is consistent thent is satisfiable Logic in Computer Science - p 3/21
Two forms of Completeness Theorem Let Γ be a set of wffs. The following parts are equivalent. • If Γ |= A then Γ ` A • If Γ is consistent, then Γ is satisfiable. Logic in Computer Science – p.3/21
Sequence of consistent sets of wifs Partially ordered Set a relation on a set s is called partial ordering or partial order if it is reflexive antisymmetric and transitive a set together with a partial ordering r is called a partially ordered set, or poset Totally Ordered Set If<s,r> is a poset and every two elements of s are comparable s is called a totally ordered set or linearly ordered set. a totally ordered set is also called a chain Lemma Let S 2C(). If <s, c> is a totally ordered set, and for any TE s, t is consistent hen U s is consistent Logic in Computer Science- p 4/21
Sequence of consistent sets of wffs Partially Ordered Set A relation on a set S is called partial ordering or partial order if it is reflexive, antisymmetric and transitive. A set S together with a partial ordering R is called a partially ordered set, or poset. Totally Ordered Set If < S, R > is a poset and every two elements of S are comparable, S is called a totally ordered set or linearly ordered set. A totally ordered set is also called a chain. Lemma Let S ⊆ 2L(F). If < S, ⊆> is a totally ordered set, and for any Γ ∈ S, Γ is consistent, then S S is consistent. Logic in Computer Science – p.4/21
Existence of consistent and maximal set Theorem LetiCl()be consistent. There existsT'EL()such that r∈I",and 2,T is consistent and maximal Zorn's Lemma Let s be a nonempty set such that for any chain Z cs, the set UZE S. Then there is a m e s which is maximal in the sense that it is not a subset of any other element of Logic in Computer Science - p 5/21
Existence of consistent and maximal set Theorem Let Γ ⊆ L(F) be consistent. There exists Γ0 ∈ L(F) such that 1. Γ ⊆ Γ0, and 2. Γ0 is consistent and maximal. Zorn’s Lemma Let S be a nonempty set such that for any chain Z ⊆ S, the set S Z ∈ S. Then there is a m ∈ S which is maximal in the sense that it is not a subset of any other element of S. Logic in Computer Science – p.5/21