21-等值式

1第二章:命题逻辑等值演算主要内容：等值式与基本的等值式等值演算与置换规则析取范式与合取范式，主析取范式与主合取范式联结词完备集本章与其他各章的联系是第一章的抽象与延伸是后续各章的先行准备2第一节：等值式32.1等值式若等价式AB是重言式，则称A与B等值，记作AB，并称AB是等值式几点说明：定义中，A,B,均为元语言符号A或B中可能有哑元出现.例如，在(pq)((pq)(rr))中，r为左边公式的哑元.用真值表可验证两个公式是否等值42.1等值式p¬p¬¬p¬¬pp01011011例子判断¬¬pp52.1等值式pq¬ppq¬pq(pq)(¬pq)001111011111100001110111例子判断pq¬pq62.1等值式如果命题变项很多，怎么办？--利用已知的等值式通过代换得到新的等值式命题：设A是一个命题公式，含有命题变项p1，p2，…，pn，又设A1，A2，…，An是任意的命题公式.对每个i（i=1，2，…，n），把pi在A中的所有出现都替换成Ai，所得到的新命题公式记作B.那么，如果A是重言式，则B也是重言式.72.1等值式否定律双重否定律¬¬pp德摩根律•¬(pq)¬p¬q•¬(pq)¬p¬q幂等律ppp，ppp交换律pqqppqqppqqp82.1等值式结合律(pq)rp(qr)(pq)rp(qr)(pq)rp(qr)分配律p(qr)(pq)(pr)p(qr)(pq)(pr)92.1等值式常元律零律:p11，p00同一律:p0p，p1p排中律:p¬p1矛盾律:p¬p0吸收律p(pq)pp(pq)p102.1等值式蕴涵等值式pq¬pq等价等值式pq(pq)(qp)假言易位pq¬q¬p等价否定等值式pq¬p¬q归谬论(pq)(p¬q)¬p112.1等值式说明：(1)16组等值模式都可以给出无穷多个同类型的具体的等值式。(2)证明上述16组等值式的代入实例方法可用真值表法，把改为所得的命题公式为永真式，则成立。122.1等值式等值演算：由已知的等值式推演出另外一些等值式的过程置换规则：设φ(A)是含公式A的命题公式，φ(B)是用公式B置换了φ(A)中所有A后得到的命题公式，若ＡB，则φ(A)φ(B)说明：等值演算过程中遵循的重要规则一个命题公式A，经多次置换，所得到的新公式与原公式等价132.1等值式1.用等值演算验证等值式试证：p→(q→r)(pq)→r证明：a.p→(q→r)p→(¬q∨r)b.p→(¬q∨r)¬p∨¬q∨rc.¬p∨¬q∨r¬(pq)∨rd.¬(pq)∨r(pq)→r142.1等值式试证：¬(pq)→(¬p∨(¬p∨q))(¬p∨q)左边¬¬(pq)∨(¬p∨(¬p∨q))(pq)∨(¬p∨(¬p∨q))(pq)∨(¬p∨q)(p∨¬p∨q)(q∨¬p∨q)(¬p∨q)152.1等值式2.用等值演算判断公式的类型证明：((p∨q)¬(¬p(¬q∨¬r)))∨(¬p¬q)∨(¬p¬r)为一永真式证明：原式((p∨q)(p∨(qr)))∨¬(p∨q)∨¬(p∨r)((p∨q)(p∨q)(p∨r))∨¬((p∨q)(p∨r))((p∨q)(p∨r))∨¬((p∨q)(p∨r))1162.1等值式3．解判定问题在某次研讨会的中间休息时间，3名与会者根据王教授的口音对他是哪个省市的人判断如下：甲：王教授不是苏州人，是上海人乙：王教授不是上海人，是苏州人丙：王教授既不是上海人，也不是杭州人听完这3人的判断后，王教授笑着说，你们3人中有一人说得全对，有一人说对了一半，另一人说得全不对。试用逻辑演算分析王教授到底是哪里人。17第二节：析取范式与合取范式182.2析取范式和合取范式文字(literal):命题变项及其否定简单析取式:仅由有限个文字构成的析取式简单合取式:仅由有限个文字构成的合取式例：设p、q为二个命题变元p，q，p∨p，q∨q，¬p∨q，¬q∨¬p，p∨q，p∨¬q称为简单析取式p，q，p∧p，q∧q，¬p∧q，¬q∧¬p，p∧q，p∧¬q称为简单合取式。192.2析取范式和合取范式定理:1)一个简单析取式是永真式当且仅当它同时含某个命题变元及它的否定式2)一个简单合取式是永假式当且仅当它同时含某个命题变元及它的否定式202.2析取范式和合取范式析取范式:由有限个简单合取式构成的析取式A1…An,Ai为简单合取式(pq)(pr)合取范式:由有限个简单析取式构成的合取式A1…An,Ai为简单析取式(pq)(pr)析取范式与合取范式统称为范式212.2析取范式和合取范式定理：Ai简单合取式，A1…AnF当且仅当AiF，任意AiAi简单析取式，A1…AnT当且仅当AiT，任意Ai222.2析取范式和合取范式范式存在定理:任意命题公式都存在着与之等值的析取范式与合取范式方法：步骤一：消去“”、“”联结词步骤二：消去双重否定符，内移否定符步骤三：使用分配律232.2析取范式和合取范式范式存在定理:任意命题公式都存在着与之等值的析取范式与合取范式方法：步骤一：消去“”、“”联结词步骤二：消去双重否定符，内移否定符步骤三：使用分配律242.2析取范式和合取范式步骤一：利用等值公式：化去“→”、“”联结词pqpqp↔q(pq)(qp)252.2析取范式和合取范式范式存在定理:任意命题公式都存在着与之等值的析取范式与合取范式方法：步骤一：消去“”、“”联结词步骤二：消去双重否定符，内移否定符步骤三：使用分配律262.2析取范式和合取范式消去双重否定符，内移否定符德摩根律•¬(pq)¬p¬q•¬(pq)¬p¬q双重否定律¬¬pp272.2析取范式和合取范式范式存在定理:任意命题公式都存在着与之等值的析取范式与合取范式方法：步骤一：消去“”、“”联结词步骤二：消去双重否定符，内移否定符步骤三：使用分配律282.2析取范式和合取范式利用“”对“”的分配，将公式化成为析取范式p(qr)(pq)(pr)利用“”对“”的分配，将公式化成为合取范式p(qr)(pq)(pr)292.2析取范式和合取范式例：求(pq)(pq)的析取范式1.化去(pq)(pq)2.“”对“”分配，化为析取范式(ppq)(qpq)3.最简析取范式pq302.2析取范式和合取范式例：求((pq)r)p的析取范式和合取范式(一)求析取范式原式((pq)r)p((pq)r)p((pq)r)p((pq)r)p((pr)(qr))pp(pr)(qr)p(qr)312.2析取范式和合取范式(二)求合取范式原式((pq)r)p((pq)r)p((pq)r)p((pq)r)p(ppq)(pr)(pq)(pr)322.2析取范式和合取范式问题：一个命题公式的析取范式是不是唯一的？同一命题公式的析取范式是不是等值的？332.2析取范式和合取范式极小项(极大项):含有n个命题变项的简单合取式(简单析取式)，并满足每个命题变元和它的否定式不同时出现，而二者之一必出现且仅出现一次第i个命题变项或它的否定式出现在从左算起的第i位上(若无角标，则按字典顺序排列)若有ｎ个命题变项，则有2n个极小项（极大项）如果我们把不带否定符的命题变项取成1，带否定符的命题变项取成0，那么每一个极小项都对应一个二进制数，因而也对应一个十进制数342.2析取范式和合取范式极小项的编码:对应成真赋值三个变元p、q、r可构造8个极小项：¬p∧¬q∧¬rFFF0记作m0¬p∧¬q∧rFFT1记作m1¬p∧q∧¬rFTF2记作m2¬p∧q∧rFTT3记作m3p∧¬q∧¬rTFF4记作m4p∧¬q∧rTFT5记作m5p∧q∧¬rTTF6记作m6p∧q∧rTTT7记作m7352.2析取范式和合取范式极大项的编码:对应成假赋值如三个变元p、q、r，其记法如下：p∨q∨rFFF0记作M0p∨q∨¬rFFT1记作M1p∨¬q∨rFTF2记作M2p∨¬q∨¬rFTT3记作M3…………¬p∨¬q∨¬rTTT7记作M7362.2析取范式和合取范式定理:设mi和Mi是命题变元p1,p2…pn形成的极小项和极大项，则：(1)mimjF,(i≠j)(2)MiMjT,(i≠j)(3)miMi；Mimi372.2析取范式和合取范式主析取范式(主合取范式)：由n个命题变项构成的析取范式(合取范式)中所有的简单合取式(简单析取式)都是极小项(极大项)定理:任何命题公式都存在着与其等值的主析取范式和主合取范式，并且是唯一的。382.2析取范式和合取范式证法一在真值表中，使命题公式的真值为T的指派所对应的极小项的析取，即为此公式的主析取范式证：给定一个命题公式A，使其为T的真值指派所对应的极小项为m’1,m’2,…,m’k,这些极小项的析取记为B，为此要证AB，即要证A与B在相同的指派下具有相同的真值。392.2析取范式和合取范式首先对于使A为T的指派显然使B为T对于使A为F的指派，它对应的极小项(设为m’j)不包含在m’1,m’2,…,m’k中。所以m’j为使B为F的指派所以AB得证402.2析取范式和合取范式一个公式的主析取范式即为令此公式的真值为T的指派所对应的极小项的析取。一个命题公式的真值表是唯一的，因此一个命题公式的主析取范式也是唯一的412.2析取范式和合取范式pqrm1m3m5m6m7pqrp∧q∨rFFFFFFTTFTFFFTTTTFFFTFTTTTFTTTTTpqr的真值表422.2析取范式和合取范式证法二：构造法用等值演算方法求命题公式主析取范式的方法①将命题公式化归为与其等值的析取范式②添变元:③消去重复项Ai(pjpj)(Aipj)(Aipj)432.2析取范式和合取范式例：求(p∧(p→q))∨q的主析取范式解：原式(p∧¬p)∨(p∧q)∨q----(1)化为析取范式(p∧q)∨q----(2)化简(p∧q)∨(q∧(p∨¬p))(p∧q)∨(p∧q)∨(¬p∧q)----(3)添项(p∧q)∨(¬p∧q)m1m3----(4)合并相同最小项442.2析取范式和合取范式主合取范式任何一个命题公式都可求得它的主合取范式一个命题公式的主合取范式是唯一的在真值表中，令命题公式的真值为“F”的指派就对应其主合取范式的一个极大项构造法452.2析取范式和合取范式例:求p∧(p→q)∨q的主合取范式解：原式p∧(p∨q)∨q(p∧p)∨(p∧q)∨q(p∧q)∨q(p∨q)∧q(p∨q)∧(q∨(p∧p))(p∨q)∧(p∨q)M0∧M2pq上式FFFFTTTFFTTT462.2析取范式和合取范式主析（合）取范式的用途讨论：①求公式的成真与成假赋值②判断公式类型③判断两个命题公式是否等值④应用主析（合）取范式分析和解决实际问题472.2析取范式和合取范式1.求公式的成真与成假赋值例：(pq)rm1m3m5m6m7成真赋值为001,011,101,110,111成假赋值为000,010,100482.2析取范式和合取范式2.判断公式的类型设A含n个命题变项A为重言式A的主析取范式含2n