2-2 命题逻辑的等值和推理演算.ppt

第2章命题逻辑的等值和推理演算,2.1等值定理2.2等值公式2.3命题公式与真值表的关系2.4联结词的完备集2.5对偶式2.6范式2.7推理形式2.8基本的推理公式2.9推理演算2.10归结推理法,讨论等值演算,讨论推理演算,2.4联结词的完备集,定义在一个联结词的集合中，如果一个联结词可由集合中的其他联结词定义，则称此联结词为冗余的联结词，否则称为独立的联结词。如：PQ=PQPQ=(PQ)(PQ)在，中、是冗余的。在，中，PQ=（PQ）所以是冗余的。在，中无冗余的联结词。同理，在，中无冗余的联结词。,联结词的完备集,定义设C是联结词的集合，若对任一命题公式都由C中的联结词表示出来的公式与之等值，就说C是完备的联结词集合。显然，全体联结词的无限集合是完备的。，等也是完备的。,2.5对偶式,定义在仅含联结词，的命题公式A中，将联结词，F，T分别换成，T，F所得的公式称为公式A的对偶式，记为A*如：PQ与PQ是对偶式(PQ)R与(PQ)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(QR)则：A*=P(QR)，A=P(QR)A=P(QR)所以：(A)*=P(QR)(A*)=P(QR)所以：(A)=P(QR)(A)=P(QR),与对偶式有关的定理,定理2.5.2：(A*)*=A,(A)=A定理2.5.3：A=A*如：A=P(QR)则：A=P(QR)A*=P(QR)所以：A*=P(QR)=A,此定理为摩根律：(AB)=AB(AB)=AB的另一种形式，,与对偶式有关的定理,定理2.5.4若A=B，必有A*=B*证：A=BAB永真AB永真A*B*永真A*B*永真A*=B*定理2.5.5若AB永真，必有B*A*永真（作业）定理2.5.6A与A同永真，同可满足A与A*同永真，同可满足对偶性是逻辑规律，给证明公式的等值和求否定带来方便,依定理2.5.3有，A=A*，B=B*,2.6范式,简单析取式它是仅由有限个命题变项或其否定构成的析取式。如:P，Q，P，Q，PQ，PQ，PQ它是重言式当且仅当它同时含一个命题变项及其否定；如：PQP是重言式简单合取式它是仅由有限个命题变项或其否定构成的合取式。如:P，Q，P，Q，PQ，PQ它是矛盾式当且仅当它同时含一个命题变项及其否定。如：PPQ是矛盾式,析取范式,析取范式由有限个简单合取式组成的析取式A1A2.An（n1，Ai都是简单合取式）如：(PQR)(PQ)Q一个析取范式是矛盾式，当且仅当其每个简单合取式都是矛盾式合取范式由有限个简单析取式组成的合取式A1A2.An（n1,Ai都是简单析取式）如：(PQR)(PQ)Q一个合取范式是重言式，当且仅当其每个简单析取式都是重言式范式析取范式与合取范式的总称,命题公式的范式,范式存在定理任何命题公式都存在着与之等值的析取范式与合取范式求公式A的范式的步骤：(1)消去A中的,（若存在）AB=ABAB=(AB)(AB)(求析取范式时)=(AB)(AB)(求合取范式时)(2)否定联结词的内移或消去（摩根定律）(3)使用分配律对分配（析取范式）对分配（合取范式）注意：公式的范式存在，但不惟一，这是它的局限性,求公式的范式举例,例:求下列公式的析取范式与合取范式(1)A=(PQ)R解(PQ)R=(PQ)R（消去）=PQR（结合律）这既是A的析取范式（由3个简单合取式组成的析取式）又是A的合取范式（由一个简单析取式组成的合取式）,求公式的范式举例,(2)B=(PQ)R解(PQ)R=(PQ)R（消去第一个）=(PQ)R（消去第二个）=(PQ)R（否定号内移摩根律）这已为析取范式（两个简单合取式构成）继续：(PQ)R=(PR)(QR)（对分配律）这一步得到合取范式（由两个简单析取式构成）,极小项,定义n个命题变项的简单合取式，其中每个命题变项与其否定不同时出现，而二者之一必出现且仅出现一次，这样的简单合取式称为极小项。如：两个命题变元P和Q，其极小项为：PQ，PQ，PQ，PQ说明n个命题变项产生2n个极小项，它们互不等值用mi表示第i个极小项，每个小项的n个变元排序相同。（按下标或字典顺序），分别记为其中i是该极小项成真赋值的十进制表示.,m11m10m01m00,极小项,由P,Q,R三个命题变项形成的极小项,主析取范式,主析取范式设命题公式A中含n个命题变项，如果A的析取范式中的简单合取式全是极小项，则称该析取范式为A的主析取范式如：n=3,命题变项为P,Q,R时，主析取范式：(PQR)(PQR)=m1m3定理任何命题公式都存在与之等值的主析取范式,并且是惟一的.求主析取范式的方法等值演算法和真值表法,用等价演算法求主析取范式的步骤,1.求A的析取范式A；2.若A的某简单合取式B中不含某命题变项或其否定，则将B展成如下形式：B=B1=B(PiPi)=(BPi)(BBi)3.将重复出现的命题变项、矛盾式及重复出现的极小项都“消去”。4.将极小项按由小到大的顺序排列，并用表示之，如m1m2m6用(1,2,6)表示。,求公式A=(PQ)R的主析取范式,解法1：(PQ)R=(PQ)R,=(PQ)R（析取范式）(PQ)=(PQ)(RR)=(PQR)(PQR)=m6m7R=(PP)(QQ)R=(PQR)(PQR)(PQR)(PQR)=m1m3m5m7,代入并合并相同式，得主析取范式：(PQ)R=m1m3m5m6m7=(1,3,5,6,7),解法2：(PQ)R=(PQ)R,=(PQ)R（析取范式）=m11xmxx1=(m110m111)(m001m011m101m111)=(1,3,5,6,7),求公式A=(PQ)R的主析取范式,主析取范式的用途,(1)求公式的成真赋值和成假赋值如前面例子中得到(PQ)R=m1m3m5m6m7其成真赋值为：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=0A为可满足式A的主析取范式中至少含一个极小项如A=(2,3),(PQ)Q=(PQ)Q=PQQ=F（矛盾式）,用主析取范式判断公式的类型,如前面例子中得到(PQ)R=m1m3m5m6m7=(1,3,5,6,7)(可满足式）,(PQ)P)Q=(PQ)P)Q=(PQ)PQ=m10m0 xmx1=m10m00m01m01m11=m0m1m2m3=(0,1,2,3)=T（重言式）,用主析取范式判断公式的类型,主析取范式的用途,(3)判断两个公式是否等值,如PQ=PQ=m0 xmx1=m00m01m01m11=m0m1m3=(0,1,3),P(PQ)=m0 xm11=m00m01m11=m0m1m3=(0,1,3),所以PQ=P(PQ),定理任何命题公式都存在与之等值的主析取范式,并且是惟一的.,主析取范式的应用(4)举例,例：甲、乙、丙、丁四人参加考试，有人问他们，谁的成绩最好，甲说：“不是我”乙说：“是丁”丙说：“是乙”丁说：“不是我”四人的回答只有一人符合实际，问是谁的成绩最好，若只有一人成绩最好，他是谁？,解此类问题的步骤为：将简单命题符号化写出各复合命题写出由中复合命题组成的合取式求中所得公式的主析取范式,主析取范式的应用举例,解设A：甲的成绩最好B：乙的成绩最好，C：丙的成绩最好D：丁的成绩最好，(1)(ADBD)(2)(ADBD)(3)(ADBD)(4)(ADBD),例：甲、乙、丙、丁四人参加考试，有人问他们，谁的成绩最好，甲说：“不是我”乙说：“是丁”丙说：“是乙”丁说：“不是我”四人的回答只有一人符合实际，问是谁的成绩最好，若只有一人成绩最好，他是谁？,主析取范式的应用举例,(1)(ADBD)(2)(ADBD)(3)(ADBD)(4)(ADBD)(1)(4)构成的析取式为(ADBD)(ADBD)(ADBD)(ADBD),主析取范式的应用举例,求中所得公式的主析取范式(ADBD)(ADBD)(ADBD)(ADBD)=(ADBD)(ADBD)=(ABD)(ABD)=m10 x1m10 x0=m1001m1011m1000m1010,所以，只有一人成绩最好的是甲。,甲、丁并列成绩最好,甲、丙、丁并列成绩最好,甲、丙并列成绩最好,极大项,定义n个命题变项的简单析取式，其中每个命题变项与其否定不同时出现，而二者之一必出现且仅出现一次，这样的简单析取式称为极大项。如：两个命题变元P和Q，其极大项为：PQ，PQ，PQ，PQ说明n个命题变项产生2n个极大项，它们互不等值用Mi表示第i个极大项，每个小项的n个变元排序相同。（按下标或字典顺序），分别记为其中i是该极大项成假赋值的十进制表示的补.（正变项：0，变元的否定：1）,M11M10M01M00,由P,Q,R三个命题变项形成的极小项与极大项,主合取范式,主合取范式由极大项构成的合取范式如n=3,命题变项为P,Q,R时，主合取范式:(PQR)(PQR)=M6M2定理任何命题公式都存在与之等值的主合取范式,并且是惟一的.求主合取范式的方法等值演算法和真值表法,1.求A的合取范式A；2.若A的某简单析取式B中不含某命题变项或其否定，则将B展成如下形式：B=B0=B(PiPi)=(BPi)(BPi)3.将重复出现的命题变项、重言式及重复出现的极大项都“消去”。4.将极大项按由小到大的顺序排列，并用表示之，如M1M2M6用(1,2,6)表示。,用等价演算法求主合取范式的步骤,求公式(PQ)R的主合取范式,解1:：(PQ)R=(PQ)R=(PQ)R=(PQ)(QR)PR=(PR)(QQ)=(PRQ)(PQR)=M111M101QR=(QR)(PP)=(PQR)(PQR)=M111M011,代入并排序，得主合取范式：=M3M5M7=(3,5,7),解2:(PQ)R=(PQ)R=(PQ)R=(PR)(QR)(合取范式)=M1x1Mx11=M101M111M011M111=M3M5M7=(3,5,7),求公式(PQ)R的主合取范式,=(PQ)R（析取范式）=m11xmxx1=(m110m111)(m001m011m101m11