交大数理逻辑课件2-2 命题逻辑的等值和推理演算

第2章命题逻辑的等值和推理演算2.1等值定理2.2等值公式2.3命题公式与真值表的关系2.4联结词的完备集2.5对偶式2.6范式2.7推理形式2.8基本的推理公式2.9推理演算2.10归结推理法讨论等值演算讨论推理演算2.4联结词的完备集定义在一个联结词的集合中，如果一个联结词可由集合中的其他联结词定义，则称此联结词为冗余的联结词，否则称为独立的联结词。如：PQ=PQPQ=(PQ)(PQ)在{，，，，}中、是冗余的。在{，，}中，PQ=（PQ）所以是冗余的。在{，}中无冗余的联结词。同理，在{，}中无冗余的联结词。联结词的完备集定义设C是联结词的集合，若对任一命题公式都由C中的联结词表示出来的公式与之等值，就说C是完备的联结词集合。显然，全体联结词的无限集合是完备的。{，，，，}{，，，，}{，，}{，}，{，}，{}，{}等也是完备的。是完备的2.5对偶式定义在仅含联结词¬，∧，∨的命题公式A中，将联结词∨，∧，F，T分别换成∧，∨，T，F所得的公式称为公式A的对偶式，记为A*如：PQ与PQ是对偶式(PQ)R与(PQ)R是对偶式推广在仅含有联结词¬，∧，∨，↑，↓的命题公式中，将联结词∨，∧，↑，↓，F，T分别换成∧，∨，↓，↑，T，F，就得到了它的对偶式。与对偶式有关的定理设A和A*互为对偶式，P1,P2,…,Pn是出现在A和A*中的全部命题变项，令A=A(P1,P2,…,Pn),A—=A(P1,P2,…,Pn)定理2.5.1：(A*)=(A)*,(A—)=(A)—如：A=P(QR)则：A*=P(QR)，A—=P(QR)A=P(QR)所以：(A)*=P(QR)(A*)=P(QR)所以：(A)—=P(QR)(A—)=P(QR)(A*)=(A)*(A—)=(A)—与对偶式有关的定理定理2.5.2：(A*)*=A,(A—)—=A定理2.5.3：A=A*—如：A=P(QR)则：A=P(QR)A*=P(QR)所以：A*—=P(QR)=A此定理为摩根律：(AB)=AB(AB)=AB的另一种形式，与对偶式有关的定理定理2.5.4若A=B，必有A*=B*证：A=BAB永真AB永真A*—B*—永真A*B*永真A*=B*定理2.5.5若AB永真，必有B*A*永真（作业）定理2.5.6A与A—同永真，同可满足A—与A*同永真，同可满足对偶性是逻辑规律，给证明公式的等值和求否定带来方便依定理2.5.3有，A=A*—，B=B*—2.6范式简单析取式它是仅由有限个命题变项或其否定构成的析取式。如:P，Q，P，Q，PQ，PQ，PQ它是重言式当且仅当它同时含一个命题变项及其否定；如：PQP是重言式简单合取式它是仅由有限个命题变项或其否定构成的合取式。如:P，Q，P，Q，PQ，PQ它是矛盾式当且仅当它同时含一个命题变项及其否定。如：PPQ是矛盾式析取范式析取范式由有限个简单合取式组成的析取式A1A2….An（n1，Ai都是简单合取式）如：(PQR)(PQ)Q一个析取范式是矛盾式，当且仅当其每个简单合取式都是矛盾式合取范式由有限个简单析取式组成的合取式A1A2….An（n1,Ai都是简单析取式）如：(PQR)(PQ)Q一个合取范式是重言式，当且仅当其每个简单析取式都是重言式范式——析取范式与合取范式的总称命题公式的范式范式存在定理任何命题公式都存在着与之等值的析取范式与合取范式求公式A的范式的步骤：(1)消去A中的,（若存在）AB=ABAB=(A∧B)∨(A∧B)(求析取范式时)=(A∨B)∧(A∨B)(求合取范式时)(2)否定联结词的内移或消去（摩根定律）(3)使用分配律对分配（析取范式）对分配（合取范式）注意：公式的范式存在，但不惟一，这是它的局限性求公式的范式举例例:求下列公式的析取范式与合取范式(1)A=(PQ)R解(PQ)R=(PQ)R（消去）=PQR（结合律）这既是A的析取范式（由3个简单合取式组成的析取式）又是A的合取范式（由一个简单析取式组成的合取式）求公式的范式举例(2)B=(PQ)R解(PQ)R=(PQ)R（消去第一个）=(PQ)R（消去第二个）=(PQ)R（否定号内移——摩根律）这已为析取范式（两个简单合取式构成）继续：(PQ)R=(PR)(QR)（对分配律）这一步得到合取范式（由两个简单析取式构成）极小项定义n个命题变项的简单合取式，其中每个命题变项与其否定不同时出现，而二者之一必出现且仅出现一次，这样的简单合取式称为极小项。如：两个命题变元P和Q，其极小项为：PQ，PQ，PQ，PQ说明n个命题变项产生2n个极小项，它们互不等值用mi表示第i个极小项，每个小项的n个变元排序相同。（按下标或字典顺序），分别记为其中i是该极小项成真赋值的十进制表示.m11m10m01m001210,,nmmm极小项由P,Q,R三个命题变项形成的极小项极小项成真赋值名称¬P∧¬Q∧¬R000m0¬P∧¬Q∧R001m1¬P∧Q∧¬R010m2¬P∧Q∧R011m3P∧¬Q∧¬R100m4P∧¬Q∧R101m5P∧Q∧¬R110m6P∧Q∧R111m7主析取范式主析取范式设命题公式A中含n个命题变项，如果A的析取范式中的简单合取式全是极小项，则称该析取范式为A的主析取范式如：n=3,命题变项为P,Q,R时，主析取范式：(PQR)(PQR)=m1m3定理任何命题公式都存在与之等值的主析取范式,并且是惟一的.求主析取范式的方法等值演算法和真值表法用等价演算法求主析取范式的步骤1.求A的析取范式A´；2.若A´的某简单合取式B中不含某命题变项或其否定，则将B展成如下形式：B=B1=B(PiPi)=(BPi)(BBi)3.将重复出现的命题变项、矛盾式及重复出现的极小项都“消去”。4.将极小项按由小到大的顺序排列，并用表示之，如m1m2m6用(1,2,6)表示。求公式A=(PQ)R的主析取范式解法1：(PQ)R=(PQ)R,=(PQ)R（析取范式）①(PQ)=(PQ)(RR)=(PQR)(PQR)=m6m7②R=(PP)(QQ)R=(PQR)(PQR)(PQR)(PQR)=m1m3m5m7③②,③代入①并合并相同式，得主析取范式：(PQ)R=m1m3m5m6m7=(1,3,5,6,7)解法2：(PQ)R=(PQ)R,=(PQ)R（析取范式）=m11xmxx1=(m110m111)(m001m011m101m111)=(1,3,5,6,7)求公式A=(PQ)R的主析取范式主析取范式的用途(1)求公式的成真赋值和成假赋值如前面例子中得到(PQ)R=m1m3m5m6m7其成真赋值为：001,011,101,110,111则其余的赋值为成假赋值000,010,100主析取范式的用途(2)判断公式的类型设A含n个命题变项，则A为重言式A的主析取范式含2n个极小项如命题变项为P,Q时，A=(0,1,2,3)A为矛盾式A的主析取范式为0如A=0A为可满足式A的主析取范式中至少含一个极小项如A=(2,3)(PQ)Q=(PQ)Q=PQQ=F（矛盾式）用主析取范式判断公式的类型如前面例子中得到(PQ)R=m1m3m5m6m7=(1,3,5,6,7)(可满足式）((PQ)P)Q=((PQ)P)Q=(PQ)PQ=m10m0xmx1=m10m00m01m01m11=m0m1m2m3=(0,1,2,3)=T（重言式）用主析取范式判断公式的类型主析取范式的用途(3)判断两个公式是否等值如PQ=PQ=m0xmx1=m00m01m01m11=m0m1m3=(0,1,3)P(PQ)=m0xm11=m00m01m11=m0m1m3=(0,1,3)所以PQ=P(PQ)定理——任何命题公式都存在与之等值的主析取范式,并且是惟一的.主析取范式的应用(4)举例例：甲、乙、丙、丁四人参加考试，有人问他们，谁的成绩最好，甲说：“不是我”乙说：“是丁”丙说：“是乙”丁说：“不是我”四人的回答只有一人符合实际，问是谁的成绩最好，若只有一人成绩最好，他是谁？解此类问题的步骤为：①将简单命题符号化②写出各复合命题③写出由②中复合命题组成的合取式④求③中所得公式的主析取范式主析取范式的应用举例解①设A：甲的成绩最好B：乙的成绩最好，C：丙的成绩最好D：丁的成绩最好，②(1)(ADBD)(2)(ADBD)(3)(ADBD)(4)(ADBD)例：甲、乙、丙、丁四人参加考试，有人问他们，谁的成绩最好，甲说：“不是我”乙说：“是丁”丙说：“是乙”丁说：“不是我”四人的回答只有一人符合实际，问是谁的成绩最好，若只有一人成绩最好，他是谁？主析取范式的应用举例②(1)(ADBD)(2)(ADBD)(3)(ADBD)(4)(ADBD)③(1)~(4)构成的析取式为(ADBD)(ADBD)(ADBD)(ADBD)主析取范式的应用举例④求③中所得公式的主析取范式(ADBD)(ADBD)(ADBD)(ADBD)=(ADBD)(ADBD)=(ABD)(ABD)=m10x1m10x0=m1001m1011m1000m1010所以，只有一人成绩最好的是甲。甲、丁并列成绩最好甲、丙、丁并列成绩最好甲、丙并列成绩最好极大项定义n个命题变项的简单析取式，其中每个命题变项与其否定不同时出现，而二者之一必出现且仅出现一次，这样的简单析取式称为极大项。如：两个命题变元P和Q，其极大项为：PQ，PQ，PQ，PQ说明n个命题变项产生2n个极大项，它们互不等值用Mi表示第i个极大项，每个小项的n个变元排序相同。（按下标或字典顺序），分别记为其中i是该极大项成假赋值的十进制表示的补.（正变项：0，变元的否定：1）M11M10M01M001210,,nMMM由P,Q,R三个命题变项形成的极小项与极大项极小项极大项公式成真赋值名称公式成假赋值名称PQRPQRPQRPQRPQRPQRPQRPQR000001010011100101110111m0m1m2m3m4m5m6m7PQRPQRPQRPQRPQRPQRPQRPQR111110101100001010001000M0M1M2M3M4M5M6M7主合取范式主合取范式由极大项构成的合取范式如n=3,命题变项为P,Q,R时，主合取范式:(PQR)(PQR)=M6M2定理任何命题公式都存在与之等值的主合取范式,并且是惟一的.求主合取范式的方法等值演算法和真值表法1.求A的合取范式A´；2.若A´的某简单析取式