Logic in Computer Science An Introductory Course for Master Students Wang j iwang@nudt.edu.cn ecture Propositional Calculus( Cont'd) Logic in Computer Science- p 1/19
Logic in Computer Science An Introductory Course for Master Students Wang Ji jiwang@nudt.edu.cn Lecture 4 Propositional Calculus(Cont’d) Logic in Computer Science – p.1/19
PROPOSITIONAL CONNECTIVES Logic in Computer Science- p 2/19
Propositional Connectives Logic in Computer Science – p.2/19
Substitutivity of equivalence Let A, m and n be wffs and let an be the result replacing M by N at zero or more occurrences Henceforth called designate occurrences) of M in A 1. AN is a wff 2. IfFM=N then FA=An If H M=n then F A=An Logic in Computer Science -p 3/19
Substitutivity of Equivalence Let A,M and N be wffs and let AMN be the result of replacing M by N at zero or more occurrences (henceforth called designate occurrences) of M in A. 1. AMN is a wff. 2. If |= M ≡ N then |= A ≡ AMN . (≡ sub) If ` M ≡ N then ` A ≡ AMN Logic in Computer Science – p.3/19
Propositional connectives An n-ary truth function is a function from ples of truth values to truth values n-tuples A propositional connective is a symbol of a formalized language which in the intend interpretation, denotes a truth function How to lift a wff to be a truth function? Logic in Computer Science -p 4/19
Propositional Connectives • An n-ary truth function is a function from n-tuples of truth values to truth values. • A propositional connective is a symbol of a formalized language which, in the intend interpretation, denotes a truth function. • How to lift a wff to be a truth function? Logic in Computer Science – p.4/19
入 Abstraction If p1,... Pn are distinct propositional variables including all variables in A, let Ap1…入pn]A:{T,F}→{T,F} where 1 n)=0(A) and(p)=;forl0≤i≤m Obviously.Ap1…入pA=Ap1… n B iff A≡B Logic in Computer Science-p.5/19
λ Abstraction If p1, · · · , pn are distinct propositional variables including all variables in A, let [λp1 · · · λpn]A : {T, F}n → {T, F} where [λp1 · · · λpn]A(x1, · · · , xn) = φ(A) and φ(pi) = xi for all 0 ≤ i ≤ n. Obviously, [λp1 · · · λpn]A = [λp1 · · · λpn]B iff A ≡ B Logic in Computer Science – p.5/19