数理逻辑 Mathematical Logic

2.数理逻辑MathematicalLogic2.1命题逻辑propositionallogical2.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复合命题compoundstatement:用逻辑连接词可以将若干命题联接成复合命题。(1)地球是圆的并且2+3=5.p∧q(2)土星表面温度不是华氏800度。~r(3)因为地球是圆的，所以明天会出太阳。p→s(4)明天不会出太阳，除非2+3=5。即，明天不会出太阳或2+3=5。~s∨q（5）明天出太阳，只要2+3=5。q→s(6)明天出太阳，仅当2+3=5。s→q2.1.1.3条件命题conditionalstatementsp→qimplicationp前提antecedent,hypothesis.q结论consequent,conclusion.逆命题converseoftheimplicationq→p逆否命题contrapositiveoftheimplication~q→~pp→q~q→~p2.1.1.4命题变元propositionalvariable可以代表任意以一个命题的变元符号p,q,r,s，…p1,p2,p3，…2.1.1.5逻辑连接词logicalconnectives否定negation~~p合取conjunction∧p∧q析取disjunction∨p∨q蕴含implication→p→q等价equivalence,biconditionalpq联结词的真值表truthtablepq~pp∧qp∨qp→qpq00100110110110100010011011112.1.2命题公式propositionalformulas2.1.2.1命题公式的递归定义（1）单个命题变元是命题公式。（2）如果A,B是命题公式，则(~A),(A∧B),(A∨B),(A→B),(AB)都是命题公式。例A=((p∧(~q))→(((~p)∨q)∧q))是命题公式.可以省略最外层的括号:A=(p∧(~q))→(((~p)∨q)∧q).规定命题连接词的优先级：~，∧，∨，→，，左边高于右边。命题A可以化简为：A=p∧~q→(~p∨q)∧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=p∧~q→(~p∨q)∧q,B=p→(q→r)的赋值Aσ=((p∧~q→(~p∨q)∧q))σ=0∧~1→(~0∨1)∧0)=1Bσ=pσ→(qσ→rσ)=0→(1→0)=12.1.2.3命题公式的真值表truthtableofpropositionsA的真值表2.1.2.4命题公式的分类2.1.2.4.1恒真式重言式tautology无论命题变元取什么值，命题公式取值都是1(真)的公式。pQ~p~qp∧~q~p∨q(~p∨q)∧qp∧~q→(~p∨q)∧q00110101011001111001100011000101对任意赋值σ，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（逻辑）等价公式ABAB是恒真式。命题公式A,B具有相同的真值表。无论公式A,B中的命题变元如何取值,A,B都有相同的真假值。对任意赋值σ，Aσ=Bσ,A,B就是等价公式。用真值表可以判定一个公式是否恒真式，恒假式，可满足公式，可以判断两个公式是否等价。例。证明下列公式都是恒真式：(1)p→p(2)~~p→p(3)p→(q→p)(4)(p→((q→r))→((p→q)→(p→r))(5)(~q→~p)→p→qProofof(3).证法1：真值表法pqQ→pp→(q→p)0011010110111111证法2：反证法设对某个赋值σ，(p→(q→p))σ=0，则pσ=1且(q→p)σ=0，因此qσ=1且pσ=0。但pσ不可能同时取值1和0，矛盾。于是p→(q→p)不可能取值0，只能取值1。p→(q→p)是恒真式。Theorem1.基本等价公式，逻辑定律交换律commutativeproperties1.p∧qq∧p2.p∨qq∨p结合律associativeproperties3.(p∧q)∧rp∧(q∧r).4.(p∨q)∨rp∨(q∨r).分配律distributiveproperties5.p∧(q∨r)p∧q∨p∧r.6.p∨(q∧r)(p∨q)∧(p∨r).幂等律idempotentproperties7.p∨pp.8.p∧pp.双重否定propertyofnegation9．~~ppDeMorgan’slaw10.~(p∨q)~p∧~q11.~(p∧q)~p∨~q吸收律absorbproperties12.p∨(p∧q)p13.p∧(p∨q)p零一律14．p∨~p1.15．p∧~p0.16．p∨11.17．p∧1p.18．p∨0p.19．p∧00.Theorem2.(a)p→q~p∨q(b)p→q~q→~p(c)pq(p→q)∧(q→p)(d)~(p→q)p∧~q(e)~(pq)(p∧~q)∨(q∧~p)2.1.3命题公式的等价变换利用基本等价公式可以作公式的等价变换，（等值运算）把一个公式化为与之等价的另一个公式；可以将一个公式化简，或化为某种特定形式。例。化简命题公式A=p∧~q→(~p∨q)∧q.解A~(p∧~q)∨(~p∨q)∧q(~p∨q)∨((~p∨q)∧q)~p∨q2.1.4对偶公式dualpropositionsformula不含联结词→，的命题公式A中，将∨换成∧，将∧换成∨，如果有0，1，就将0换成1，1换成0，所的命题公式称为A的对偶公式,记作A*.(A*)*=A,即A,A*互为对偶公式.(p∧q)*=p∨q(~(p∨q))*=~(p∧q)(~p∨(q∧r))*=~p∧(q∨r)Proposition设A,B是两个命题公式，AB则A*B*。A是恒真式1，则A*是恒假式0。A=p∨~p=1A*=p∧~p=02.1.5范式normalformulapropositions2.4.1析取范式命题变元p1,p2,……,pn的基本合取项basicconjunctiontermsQ1∧Q2∧……∧Qn其中每个Qi=pi或~pi1≤i≤n.p1p2…pn有2n个基本合取项。p1p2p3的8个基本合取项为p1∧p2∧p3，p1∧p2∧~p3，p1∧~p2∧p3，~p1∧p2∧p3，p1∧~p2∧~p3，~p1∧~p2∧p3，~p1∧p2∧~p3，~p1∧~p2∧~p3。命题变元p1,p2,…,pn的赋值σ(p1,p2,…,pn)对应的基本合取项：Q1∧Q2∧……∧Qn其中每个Qi=piifpiσ=1Qi=~piifpiσ=0.设Q1∧Q2∧……∧Qn是命题变元p1,p2,…,pn的一个基本合取项，σ是p1,p2,…,pn的一个赋值，则(Q1∧Q2∧……∧Qn)σ=1当且仅当Q1∧Q2∧……∧Qn是σ对应的基本合取项。p1p2p3的8个基本合取项对应的赋值:p1∧p2∧p3，000m0p1∧p2∧~p3，001m1p1∧~p2∧p3，010m2p1∧~p2∧~p3，011m3~p1∧p2∧p3，100m4~p1∧p2∧~p3，101m5~p1∧~p2∧p3，110m6~p1∧~p2∧~p3，111m7若干基本合取项的析取叫析取范式normaldisjunctionformulas定理每个可满足的命题公式都等价于唯一一个析取范式。先给出命题公式的真值表，找出取值为1的所有赋值，这些赋值对应的基本合取项的析取就是所求的析取范式。也可以通过等价变换得到析取范式：p→(q→r)~p∨~q∨r~p∧(q∨~q)∧(r∨~r)∨(p∨~p)∧~q∧(r∨~r)∨(p∨~p)∧(q∨~q)∧r~p∧q∧r∨~p∧~q∧r∨~p∧q∧~r∨~p∧~q∧~r∨p∧~q∧r∨p∧~q∧~r∨~p∧~q∧r∨~p∧~q∧~r∨p∧q∧r∨p∧~q∧r∨~p∧q∧r∨~p∧~q∧r~p∧q∧r∨~p∧q∧~r∨~p∧~q∧~r∨p∧~q∧r∨p∧~q∧~r∨~p∧~q∧r∨~p∧~q∧~r∨p∧q∧r2.4.2合取范式命题变元p1,p2,……,pn的基本析取项basicdisjunctiontermsQ1∨Q2∨……∨Qn其中每个Qi=pi或~pi1≤i≤n.p1p2…pn有2n个基本合取项。p1p2p3的8个基本合取项为p1∨p2∨p3，p1∨p2∨~p3，p1∨~p2∨p3，~p1∨p2∨p3，p1∨~p2∨~p3，~p1∨~p∨p3，~p1∨p2∨~p3，~p1∨~p2∨~p3。命题变元p1,p2,…,pn的赋值σ(p1,p2,…,pn)对应的基本析取项：Q1∨Q2∨……∨Qn其中每个Qi=piifpiσ=0Qi=~piifpiσ=1.设Q1∨Q2∨……∨Qn是命题变元p1,p2,…,pn的一个基本析取项，σ是p1,p2,…,pn的一个赋值，(Q1∨Q2∨……∨Qn)σ=0当且仅当Q1∨Q2∨……∨Qn是σ对应的基本析取项。若干基本析取项的合取叫合取范式Normalconjunctionformulas定理每个不恒真的命题公式都等价于唯一一个合取范式。先给出命题公式A的真值表，找出取值为0的所有赋值，这些赋值对应的基本析取项的合取就是A的合取范式。也可以先给出~A的析取范式，再用DeMorgan律算出A的合取范式。2.1.6联结词的全功能集fullfunctionsetsoflogicalconnectives真值函数truthfunctionsf:2n→22={0,1},2n={0,1}×{0,1}×……×{0,1}。每个命题公式A(p1,p2,…,pn)都是一个真值函数，每个真值函数都可以表示为命题公式。互不等价的真值函数共有n22个.只用某几个命题联结词就可以给出所有真值函数，这几个联结词组成的集合称为全功能集。{~，∨，∧}是一个全功能集。每个命题公式都能表示为析取范式，可以只用~，∨，∧做联结词。由p∨q~(~p∧~q)p∧q~(~p∨~q){~,∧},{~,∨}也是全功能集。由p∨q~p→q知{~，→}也是全功能集。令p↑q~(p∧q)↑与非p↓q~(p∨q)↓或非~pp↑pp↓pp∧q~(p↑q)(p↑q)↑(p↑q)p∨q~(p↓q)(p↓q)↓(p↓q)pqp↑qP↓q0011011010101100{↑},{↓}也是全功能集。包含全功能集的集合是全功能集。{∨}，{∧}，{→}，{~，}都不是全功能集。Exercises1.只用联结词↑或↓表示命题公式p→q.2．证明{∨}，{∧}，{→}，{~，}都不是全功能集。2.1.7命题逻辑的推理deductiononpropositionlogic单前提推理：设A,B都是命题公式，如果A→B是恒真式，就称由A推出B是一个正确的推理，记作A⇒B。A⇒B当且仅当对任意赋值σ，Aσ=1⇒Bσ=1Theorem4基本推理（推理规则）Ruleofdeduction(a)p⇒p