数理逻辑 Mathematical Logic.doc

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) 土星表面温度不是华氏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 qp2.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 formulas2.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,一个赋值对应于命题变元的一种真假取值。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(真)的公式。对任意赋值，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就是等价公式。用真值表可以判定一个公式是否恒真式，恒假式，可满足公式，可以判断两个公式是否等价。例。 证明下列公式都是恒真式：(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 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) pq 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*互为对偶公式.(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个基本合取项对应的赋值:p1p2p3， 000 m0p1p2p3， 001 m1p1p2p3， 010 m2p1p2p3， 011 m3p1p2p3， 100 m4p1p2p3， 101 m5p1p2p3， 110 m6p1p2p3，111 m7若干基本合取项的析取叫析取范式normal disjunction formulas定理 每个可满足的命题公式都等价于唯一一个析取范式。 先给出命题公式的真值表，找出取值为1的所有赋值，这些赋值对应的基本合取项的析取就是所求的析取范式。也可以通过等价变换得到析取范式：p(qr) pqr p(qq) (rr)(pp) q (rr)(pp) (qq)rpqrpq rpqrpqrp q rpqrpqrpqrpqrpqrpqrpqrpqrpqrpqrp q rpqrpqrpqrpqr2.4.2合取范式命题变元p1,p2,pn的基本析取项basic disjunction terms Q1Q2Qn其中每个 Qi =pi 或 pi 1in.p1p2pn有2n个基本合取项。p1p2p3的8个基本合取项为p1p2p3，p1p2p3，p1p2p3，p1p2p3，p1p2p3，p1pp3，p1p2p3，p1p2p3。命题变元p1,p2,pn的赋值(p1,p2,pn)对应的基本析取项： Q1Q2Qn其中每个 Qi =pi if pi=0 Qi=pi if pi=1.设Q1Q2Qn是命题变元p1,p2,pn的一个基本析取项，是p1,p2,pn的一个赋值， (Q1Q2Qn) =0 当且仅当 Q1Q2Qn是对应的基本析取项。若干基本析取项的合取叫合取范式Normal conjunction formulas 定理 每个不恒真的命题公式都等价于唯一一个合取范式。 先给出命题公式A的真值表，找出取值为0的所有赋值，这些赋值对应的基本析取项的合取就是A的合取范式。也可以先给出A的析取范式，再用De Morgan律算出A的合取范式。2.1.6联结词的全功能集full function sets of logical connectives 真值函数truth functions f:2n2 2=0,1, 2n=0,10,10,1。 每个命题公式A(p1,p2,pn)都是一个真值函数，每个真值函数都可以表示为命题公式。互不等价的真值函数共有个.只用某几个命题联结词就可以给出所有真值函数，这几个联结词组成的集合称为全功能集。， 是一个全功能集。每个命题公式都能表示为析取范式，可以只用，做联结词。由pq (pq) pq (pq), , 也是全功能集。由pq pq知，也是全功能集。令 pq ( pq) 与非 pq (pq) 或非pq pq Pq00 1 101 1 010 1 011 0 0 p pp pp pq (pq) (pq)(pq) pq ( pq) ( pq)( pq) , 也是全功能集。 包含全功能集的集合是全功能集。 ， 都不是全功能集。Exercises1. 只用联结词或表示命题公式pq.2 证明，都不是全功能集。2.1.7命题逻辑的推理 deduction on proposition logic 单前提推理：设A, B都是命题公式，如果AB是恒真式，就称由A推出B是一个正确的推理，记作AB。AB 当且仅当对任意赋值，A=1 B=1Theorem 4 基本推理（推理规则）Rule of deduction(a) pp(b) pp(c) pqp(d) pqq(e) ppq(f) qpq(g) ppq(h) (pq) p(i) p (pq)q(j) p(pq)q(k) q(pq)p(l) (pq) (qr) pr(m) (pq) (pq)(qp)(n) (pq) (pr)(qs) rs(o) (pq) (pr) (qr) r多前提推理：设A1,A2,An, B都是命题公式，如果A1A2AnB是恒真式，就称由A1, A2,An推出B是一个正确的推理，记作A1,A2,AnB。A1,A2,An B当且仅当对任意赋值，A1=1,A2=1,An=1 B=1由于A1A2AnBA1A2AnB若A1A2AnB是恒真式，则A1,A2,AnB。Theorem 5 多前提基本推理(a) p, pq q(b) q, pq p(c) q, pq p(d) pq, qr pr(e) pq, pr , qs rs(f) pq, pr , qr rqpq ppqprqs rs pq p q pq qr prqpq p称命题公式序列B1,B2,Bm=B为从A1,A2,An到B的一个证明(论证Deduction), 如果每个Bi, 1im, 或是某个Aj, 或是由其前面若干公式推出. 如果存在A1,A2,An到B的一个论证则A1,A2,AnB。对任意赋值，若A1=1, A2=1,An=1 则对每个i, 1in, 都有Bi=1, 因此B=1。于是有A1,A2,AnB。例. 构造下列推理的论证deduction(1) pq, pr, st, sr, tq st hypothesis t hypothesiss Thm5(b)sr hypothesis r Thm5(a)pr hypothesisp Thm5(b)pq hypothesisq Thm5(c) Theorem (Deduction Theorem) A1,A2, An ABif and only if A1,A2, An , ABHomework 1. Prove the following equivalent formulas (1) (pq) (pq)(pq) (2) (pr)(qr) (pq) r2. Give the normal disjunction formumlas of the following statements (1) (pq) r) p (2) ( pq)qr3. Give the deductions of the following consequence (1) pq, rq, rs, sqp (2) (pq), qr, rp (3) p (qr), q, pssr2.2一阶逻辑First Order Logic2.2.1谓词和量词Predicate and Quantifiers 1 谓词Predicate关系Relation集合x|P(x)中P(x) 变元x满足某种性质称P(x)为一元谓词,或一元关系Q(x,y) 二元谓词二元关系R(x,y,z) 三元谓词三元关系论域A中元素a,b,cA,满足关系P,Q,R，记作P(a),Q(a,b),R(a,b,c).不满足关系记作P(a),Q(a,b),R(a,b,c).函数Function论域A上的函数是一种特殊的关系，也是谓词F:AA，一元函数，也是二元关系对任意xA, F(x) A, F(x)唯一确定。G:AAA,二元函数，任意x,yA,G(x,y) A唯一确定。对a,b,cA, 如果F(a)=b, 就说F(a)=b真。G(a,b)=c就说G(a,b)=c真。2量词Quantifier全称量词Universal Quantifier xP(x), yQ(x,y)存在量词Existencial Quantifier xP(x), xyQ(x,y)2.2.2一阶逻辑的符号集-语言Language1逻辑符号 个体变元v1,v2,v3, 命题联结符号， 量词符号， 等号= 技术符号），（ 2非逻辑符号关系符号P,Q,R, 每个关系符号都指定是几元关系函数符号F,G,H, 每个函数符号都指定是几元函数常量符号a,b,c,2 一阶语言 L =P,Q,R,;F,G,H,;a,b,c非逻辑符号属于每一个一阶语言。2.2.2一阶逻辑的公式formulas of first order logic 1项term 1） 单个命题变元vi是项， 2）单个常量是项， 3） 如果t1,t2,tn是项，F是n元函数符号，则F(t1,t2,tn)是项。 例L=+，0,1 v1+v2 +1是L的项。 2原子公式 atomic formulas 1）若t1,t2是项，则t1=t2是原子公式， 2）若t1,t2,tn是项，P是n元关系符号，则P(t1,t2,tn)是原子公式。 v1 +1=0v1+v2 +10 都是原子公式。 3公式 1）原子公式是公式, 2) 设， 是公式，则（），（），（），（），（），3) 设， 是公式，x是个体变元则（x）， (x)都是公式。 v1 (v1 +1=0)v2 (v1+ v2 +10)v1 (v1 +1=0 v2 (v1+ v2 +10) )2.2.3量词的辖域约束变元和自由变元v1 (v1 +1=0) 量词的辖域是全公式。v1是约束变元v2 (v1+ v2 +10) 量词的辖域是全公式。v2是约束变元, v1是自由变元v1 (v1 + v2+1=0 v2 (v1+ v2 +10)v2 的辖域是(v1+ v2 +10)v1的辖域是全公式，v1是约束变元，第二个v2是约束变元，第一个v2是自由变元.公式常记作(x1,x2,xn), 中自由变元都在x1,x2,xn中。没有自由变元的公式叫做闭公式，也叫句子。一阶语言L的一个句子集叫做一个理论。2.2.4一阶语言的模型Model数学结构Mathematical Structure一阶语言L= P,Q,R,;F,G,H,;a,b,c 一阶语言的模型M=A, PM,QM,;FM,GM,HM,;aM,bM,cMA是论域Universe，PM,QM,RM,是A的关系FM,GM,HM,是A上函数aM,bM,cM 是A的元素例 N,+,0,N,+,0, Z,+,0,1, Zn,+,0,1 都是模型。2.2.5一阶公式的赋值一阶公式在模型M上的赋值。1项的解释1）先为个体变元指派模型论域中的一些元素做解释，a1, a2,A,(v1,v2)=( a1,a2,)x=vi , aA,(a/x)=( a1,a2,a,)2）项t1,t2,tn如果有解释t1,t2,tn，F是n元函数符号，则F(t1,t2,tn)=FM(t1,t2,tn)2原子公式 的取值 1）原子公式t1=t2的取值，对赋值，若t1=t2则在模型M中t1=t2取值为真，记作Mt1=t2. 2）原子公式P(t1,t2,tn) 的取值,对赋值，若PM(t1,t2,tn)成立，则在模型M中P(t1,t2,tn),取值为真，记作MP(t1,t2,tn). 3公式的取值 对赋值，公式在模型M中取值真，记作M. 1) M 当且仅当 M. 2) M 当且仅当 M或M3) M当且仅当 M且M4) M 当且仅当 M或M5) M 当且仅当M且M 或M且M6) Mx当且仅当对任意a A, M(a/x)7) Mx当且仅当存在a A, M(a/x)模型M=Z,+,0,1,=(0,0,)公式v1 (v1 +1=0)，v2 ( v1 v2+10)，v1 (v1 0 v2 (v1+ v2 +10) )在M上的取值：Mv1 (v1 +1=0)Mv2 (v1v2 +10)Mv1 (v10 v2 (v1 v2 +10) ) 一个公式的取值只与公式中自由变元的解释有关，与约束变元的取值无关。M(x1,x2,xn)当且仅当M(x1,x2,xn)如果x1=a1, x2=a2, ,xn =an,则M(x1,x2,xn)也写成M(a1,a2,an).闭公式在模型中的取值与指派无关，如果存在一个指派，M，则对任意指派M。2.2.6一阶公式的分类恒真式如果公式 (x1,x2,xn), 在模型M的任何指派下取值都是真，就称为在M中恒真，记作M。如果公式(x1,x2,xn), 在任何模型，任何指派下取值都是真，就称为恒真式, 记作。 恒假式如果公式(x1,x2,xn), 在任何模型，任何指派下取值都是假，就称为恒假式。可满足公式如果公式 (x1,x2,xn), 存在模型，存在指派取值为真，就称为可满足公式。，。命题逻辑的所有恒真形式都是恒真式。HomeworkProve the following 1) (x)x(x)， 2) x()xx3) x() xx。4) x() xx 5) x () xxProve each of the following is not a tautology 1) (x) x(x),2)xy(x,y)yx(x,y).2.2.7一阶公式的等价变换1 等价公式 如果一阶公式(x1,x2,xn), (x1,x2,xn)在任何模型，任何指派下都有相同取值，就称(x1,x2,xn), (x1,x2,xn)是等价公式 ，记作(x1,x2,xn) (x1,x2,xn)。(x1,x2,xn)(x1,x2,xn)是等价公式当且仅当(x1,x2,xn)(x1,x2,xn)是恒真式。 2基本等价公式命题逻辑的等价形式也是一阶逻辑的等价形式 1) xx 2) xx 3) xx 4) xx 4) x() xx5) x() xx 如果x不在中自由出现6) x() x7) x() x如果x不在中自由出现8）x () x9）x () x如果x不在中自由出现10）x()x11）x()x利用基本公式可以做公式的等价变换，可以将公式化简，可以将公式化成某种标准形式。x() x () x () x () x() xx xx 3约束变元换名x(x, x1,x2,xn) y(y, x1,x2,xn)x(x, x1,x2,xn) y(y, x1,x2,xn)其中yx1,x2,xn例. v2 (v1v2 +10) v3 (v1v3 +10, k-10。于是有 k-1, k-1. 由b)有kA，得到矛盾。因此=, A=N。 第一归纳法 Mathematical Induction关于自然数的一个性质P(x),如果有a) P(0)成立，b) P(k)P(k+1), k0则nN P(n) 成立。证明 令A=nN | P(n), AN.则满足a) 0A,b) kAk+1A.由归纳原理A=N,即nN P(n) 成立。第一归纳法的应用例1证明12+22+32+n2=证明. a) n=1, 12=123/6. b) 设12+22+32+k2=则12+22+32+k2+(k+1)2=+(k+1)2=例2证明容斥原理=证明 n=1，2显然。=+|An+1|-=+|An+1|-=+|An+1|-= 例3 Function SQ(A) 1. C0 2. D0 3.while(DA) a. CC+A b. DD+1 4. Return(C) End of Function SQ解. 先猜测结果 第一轮 C1=A , D1=1 第二轮 C2=A+A=2A, D2=2 第三轮 C3=2A+A=3A, D3=3 猜Cn=DnA 证明 设 Ck=DkA, 则Ck+1=Ck+A=DkA+A =( Dk+ 1)A= Dk+1A 所以Cn=DnA 程序终止时C=Cn, D=Dn =A. C=A*A=A2.例4证明以下程序得到X,Y的最大公约数Function GCD(X,Y)While (XY)If(XY)Then1. XX-Y b) Else 1. YY-X2. Return(X)End of Function GCD证明 令X0=X, Y0=Y Xk+1=Xk-Yk0 Yk+1=Yk-Xk0 返回值为Xn=Yn我们有 1) GCD(X0,Y0)=GCD(X,Y) 2) GCD(Xk+1,Yk+1) = GCD(Xk,Yk)由归纳法对任意n , GCD(Xn,Yn)= GCD(X,Y)当Xn=Yn时，GCD(Xn,Yn)=Xn。所以返回值即GCD(X,Y)。第一归纳法的推广关于整数的一个性质P(x),如果有a) P(n0)成立，n0Zb) P(k)P(k+1), kn0.则nn0P(n)成立。例4. 证明存在n0Z,使n n0 (2nn3)2 第二归纳原理如果AN, A是自然数集合N的具有以下性质的子集：a) 0Ab) s0。并且sk(s，于是有sk(sA)。 由b)有kA，得到矛盾。因此=, A=N。 第二归纳法strong form of mathematical induction,Strong Induction关于自然数的一个性质P(x),如果有a) P(0)成立，b) s0。于是有 skP(s)成立. 由b)有P(k)成立，得到矛盾。因此nP(n) 成立。第二归纳法的推广：关于整数的一个性质P(x),如果有n0Z使c) P(n0)成立，d) sZ (n0skP(s)P(k), 则n n0P(n)成立。例6 每个大于1的正整数n都能唯一地表示为素因子的乘积：n= p1a1p2a2psas,其中 p1p2ps 都是素数。a）n=2时命题成立，因为2是素数。 b) 设n=2,3,k-1时命题真。 我们证明n=k时也真。 i 如果k是素数，命题成立。 ii 如果k不是素数，k=lm, 2lk-1, 2mk-1. 对l,m命题成立:l= q1b1q2b2qubu,m= t1g1t2g2