Logic in Computer Science An Introductory Course for Master Students Wang j iwang@nudt.edu.cn Lecture 2 Propositional calculus Logic in Computer Science- p 1/39
Logic in Computer Science An Introductory Course for Master Students Wang Ji jiwang@nudt.edu.cn Lecture 2 Propositional Calculus Logic in Computer Science – p.1/39
Syntax Formation Rules for p The The Axiomatic Structure of p Theorems and derived rules Logic in Computer Science- p 2/39
Syntax • Formation Rules for P • The The Axiomatic Structure of P • Theorems and Derived Rules Logic in Computer Science – p.2/39
Primitive Symbols The primitive symbols of p are the following Improper symbols: ( Proper symbols: denumerably many propositional variable, p,g, r, p1, 91, r1, 2: The set of Primitive Symbols Logic in Computer Science - p 3/39
Primitive Symbols The primitive symbols of P are the following: • Improper symbols: (,), ∼,∨ • Proper symbols: denumerably many propositional variable, p, q, r, p1, q1, r1, · · · Σ :The set of Primitive Symbols Logic in Computer Science – p.3/39
Well-formed formulas The set of wffs is the intersection of all sets s of formulas such that 1. pE S for each propositional variable p 2. For each formula a,fA∈S,then(~A)∈S 3. For all formulas a and B,ifA∈ s and e∈S, then(A∨B)∈S a wff is a member of the set of wffs Logic in Computer Science- p 4/39
Well-Formed Formulas The set of wffs is the intersection of all sets S of formulas such that: 1. p ∈ S for each propositional variable p 2. For each formula A, if A ∈ S, then (∼ A) ∈ S 3. For all formulas A and B, if A ∈ S and B ∈ S, then (A ∨ B) ∈ S A wff is a member of the set of wffs. Logic in Computer Science – p.4/39
Principle of Induction on Wif Let be a property of formulas, and let r( A)mean that a has property Suppose r(a) for each propositional variable q 2. Whenever R(A), then e(o a 3. Whenever (A) and Se(B), then R ((AV B) Then every wff has property i Logic in Computer Science - p 5/39
Principle of Induction on Wff Let < be a property of formulas, and let <(A) mean that A has property <. Suppose 1. <(q) for each propositional variable q. 2. Whenever <(A), then <(∼ A). 3. Whenever <(A) and <(B), then <((A ∨ B)). Then every wff has property <. Logic in Computer Science – p.5/39