《数理逻辑MathematicalLogic》由会员分享，可在线阅读，更多相关《数理逻辑MathematicalLogic（26页珍藏版）》请在金锄头文库上搜索。
1、2.数理逻辑 Mathematical Logic2.1命题逻辑propositional logical2.1.1命题和命题联结词2.1.1.1命题statement： 可以判断真假的陈述.(1) 地球是圆的。p(2) 2+3=5. q(3) 你说英语吗？(4) 3-X=5.(5) 吃两片阿斯匹林！(6) 土星表面温度是华氏800度。r(7) 明天会出太阳。s可以用符号表示命题: p,q,r,s,t 分别表示命题（1）（2）（6）（7）。2.1.1.2复合命题 compound statement: 用逻辑连接词可以将若干命题联接成复合命题。(1) 地球是圆的并且2+3=5. pq(2) 土
2、星表面温度不是华氏800度。r(3) 因为地球是圆的，所以明天会出太阳。ps(4) 明天不会出太阳，除非2+3=5。即，明天不会出太阳或2+3=5。sq （5）明天出太阳，只要2+3=5。 qs (6) 明天出太阳，仅当2+3=5。 sq2.1.1.3条件命题conditional statements pq implicationp 前提antecedent, hypothesis.q 结论consequent, conclusion. 逆命题converse of the implicationqp 逆否命题contrapositive of the implication qp pq q
3、p2.1.1.4命题变元propositional variable可以代表任意以一个命题的变元符号p,q,r,s，p1,p2,p3，2.1.1.5逻辑连接词logical connectives否定negation p合取 conjunction pq析取 disjunction pq蕴含 implication pq等价equivalence, biconditional pq联结词的真值表truth tablepqppqpq pq pq00 1 0 0 1 101 1 0 1 1 010 0 0 1 0 011 0 1 1 1 12.1.2命题公式 propositional formu
4、las2.1.2.1命题公式的递归定义（1）单个命题变元是命题公式。（2）如果A, B是命题公式，则(A), (AB), (AB), (AB), (AB)都是命题公式。 例 A=(p(q) (p)q) q) 是命题公式.可以省略最外层的括号: A=(p(q) (p)q) q).规定命题连接词的优先级：，左边高于右边。命题A可以化简为：A= pq (pq) q.A可以记作A(p,q)，p, q是A中变元.2.1.2.2命题变元p1,p2,pn的赋值(p1,p2,pn)(p1,p2,pn)=(0,1,1,0,1)也记作p1=0, p2=1, p3=1, p3=0, pn=1,一个赋值对应于命题变元
5、的一种真假取值。n个变元共有2n种不同的赋值。例. 令赋值(p1,p2,p3)=(0,1,0),计算命题公式A= pq (pq) q, B= p(qr) 的赋值A= (pq (pq) q) = 01 (01) 0)=1 B=p(qr)=0(10)= 12.1.2.3命题公式的真值表truth table of propositionsA的真值表pQpqpqpq(pq) qpq (pq) q001101010110 01111001 10001100 01012.1.2.4命题公式的分类2.1.2.4.1恒真式 重言式tautology无论命题变元取什么值，命题公式取值都是1(真)的公式。对任意
6、赋值，A =1, A就是恒真式。2.1.2.4.2恒假式 矛盾式contradiction, absurdity无论命题变元取什么值，命题公式取值都是0(假)的公式。对任意赋值，A=0, A就是恒假式。2.1.2.4.3可满足的命题公式contingency 不恒假的命题公式。存在赋值，A=1, A就是可满足的。2.1.2.5（逻辑）等价公式AB AB是恒真式。 命题公式A, B具有相同的真值表。 无论公式A, B中的命题变元如何取值, A, B都有相同的真假值。对任意赋值，A =B, A, B就是等价公式。用真值表可以判定一个公式是否恒真式，恒假式，可满足公式，可以判断两个公式是否等价。例。
7、 证明下列公式都是恒真式：(1) pp(2) pp(3) p(qp)(4) (p(qr)(pq) (pr)(5) (qp) pqProof of (3). 证法1：真值表法 p q Qp p(qp) 0 0 1 1 0 1 0 1 1 0 1 1 1 1 1 1证法2： 反证法设对某个赋值，(p(qp)=0，则p=1且(qp) =0，因此q=1且p=0。但p不可能同时取值1和0，矛盾。于是p(qp)不可能取值0，只能取值1。p(qp)是恒真式。Theorem 1. 基本等价公式，逻辑定律交换律commutativeproperties1. pqq p2. pqqp结合律associative
8、properties3. (pq) rp(qr).4. (pq)rp(qr).分配律distributive properties5. p (qr) pqpr.6. p(qr) (pq) (pr).幂等律idempotent properties7. ppp.8. ppp.双重否定property of negation9ppDe Morgans law10. ( pq) pq11. (pq) pq吸收律absorb properties 12. p(pq) p13. p (pq) p零一律14pp1.15pp0.16p11.17p1p.18p0p.19p00.Theorem 2. (a) p
9、q pq(b) pq qp(c) pq (pq) (qp)(d) (pq) pq(e) (pq) (pq)(qp)2.1.3命题公式的等价变换利用基本等价公式可以作公式的等价变换，（等值运算）把一个公式化为与之等价的另一个公式；可以将一个公式化简，或化为某种特定形式。例。 化简命题公式A= pq (pq) q. 解 A (pq) (pq) q (pq)(pq) q) pq2.1.4对偶公式dual propositions formula不含联结词 ，的命题公式A中，将换成 ，将 换成，如果有0，1，就将0换成1，1换成0，所的命题公式称为A的对偶公式,记作A*.(A*)*=A, 即A, A*
10、互为对偶公式.(p q )*= pq(pq)*=( pq ) (p (q r)*=p (qr)Proposition 设A, B是两个命题公式， A B 则A* B*。 A是恒真式1， 则A*是恒假式0。 A=pp=1 A*=pp=02.1.5范式normal formula propositions2.4.1析取范式命题变元p1,p2,pn的基本合取项basic conjunction terms Q1Q2Qn其中每个 Qi =pi 或 pi 1in.p1p2pn有2n个基本合取项。p1p2p3的8个基本合取项为p1p2p3， p1p2p3，p1p2p3， p1p2p3，p1p2p3， p1p2p3，p1p2p3， p1p2p3。命题变元p1,p2,pn的赋值(p1,p2,pn)对应的基本合取项： Q1Q2Qn其中每个 Qi =pi if pi=1 Qi=pi if pi=0.设Q1Q2Qn是命题变元p1,p2,pn的一个基本合取项，是p1,p2,pn的一个赋值，则 (Q1Q2Qn) =1 当且仅当 Q1Q2Qn是对应的基本合取项。p1p2p3的8个基本合取项对应的赋值:p1
