离散数学课件-2-命题逻辑等值演算

1第二章命题逻辑等值演算§1等值式定义设A,B是两个命题公式，若复合公式A↔B是重言式，则称A与B等值，记为A⇔B。注①“⇔”不是联结词，是元语言。②“⇔”与“=”不同。例¬(p∨q)⇔¬p∧¬qpq¬p¬qp∨q¬(p∨q)¬p∧¬q¬(p∨q)↔¬p∧¬q001101110110100110011001110010012常用等值式：1．双重否定律：A⇔¬(¬A)2．幂等律：A⇔A∨A，A⇔A∧A3．交换律：A∨B⇔B∨A，A∧B⇔B∧A4．结合律：(A∨B)∨C⇔A∨(B∨C)(A∧B)∧C⇔A∧(B∧C)5．分配律：A∨(B∧C)⇔(A∨B)∧(A∨C)A∧(B∨C)⇔(A∧B)∨(A∧C)6．德摩根律：¬(A∨B)⇔¬A∧¬B¬(A∧B)⇔¬A∨¬B7．吸收律：A∨(A∧B)⇔A，A∧(A∨B)⇔A8．零律：A∨1⇔1，A∧0⇔09．同一律：A∨0⇔A，A∧1⇔A10．排中律：A∨¬A⇔111．矛盾律：A∧¬A⇔0312．蕴涵等值式：A→B⇔¬A∨B13．等价等值式：(A↔B)⇔(A→B)∧(B→A)14．假言易位：A→B⇔¬B→¬A15．等价否定等值式：A↔B⇔¬A↔¬B16．旧谬论：(A→B)∧(A→¬B)⇔¬A这里，A、B、C为任意命题公式。置换规则：设φ(A)是含公式A的命题公式，φ(B)是用公式B置换φ(A)中的所有A后得到的命题公式。若A⇔B，则φ(A)⇔φ(B)。例证明：(p∨q)→r⇔(p→r)∧(q→r)证(p→r)∧(q→r)⇔(¬p∨r)∧(¬q∨r)⇔(¬p∧¬q)∨r⇔¬(p∨q)∨r⇔(p∨q)→r4例证明：(p→q)→rkp→(q→r)证(p→q)→r⇔(p∧¬q)∨rp→(q→r)⇔¬p∨¬q∨r因为000是(p→q)→r的成假赋值，是p→(q→r)的成真赋值，所以(p→q)→rkp→(q→r)。例判断公式的类型（1）(p→q)∧p→q（2）¬(p→(p∨q))∧r（3）p∧(((p∨q)∧¬p)→q)解(1)(p→q)∧p→q⇔¬((p→q)∧p)∨q⇔¬(p→q)∨¬p∨q⇔¬(¬p∨q)∨¬p∨q⇔(p∧¬q)∨¬p∨q⇔(p∨¬p)∧(¬q∨¬p)∨q⇔1∧(¬q∨¬p)∨q5⇔(¬q∨¬p)∨q⇔(¬q∨q)∨¬p⇔1∨¬p⇔1重言式(2)¬(p→(p∨q))∧r⇔¬(¬p∨(p∨q))∧r⇔¬((¬p∨p)∨q)∧r⇔¬(1∨q)∧r⇔¬1∧r⇔0∧r⇔0矛盾式(3)p∧(((p∨q)∧¬p)→q)⇔p∧(¬((p∨q)∧¬p)∨q)⇔p∧(¬(p∨q)∨p∨q)⇔p∧((¬(p∨q)∨q)∨p)⇔p非永真的可满足式6例甲、乙、丙三名勘探队员判断一块矿样的种类乙的判断：不是铁，是锡。甲的判断：不是锡，是铁。丙的判断：既不是铁，也不是铜。经鉴定，其中一人判断全对，一人判断对一半，一人判断全错，试确定矿样的种类。解p：矿样是锡q：矿样是铁r：矿要是铜甲：A1=¬p∧q乙：A2=p∧¬q丙：A3=¬q∧¬r甲全对B1甲对一半B2甲全错B3乙全对C1乙对一半C2乙全错C3丙全对D1丙对一半D2丙全错D3则实际情况可表示为E=(B1∧C2∧D3)∨(B1∧C3∧D2)∨(B2∧C1∧D3)∨(B2∧C2∧D1)∨7(B3∧C1∧D2)∨(B3∧C2∧D1)⇔1可证B1∧C2∧D3⇔0，B1∧C3∧D2⇔¬p∧q∧¬rB2∧C1∧D3⇔0，B2∧C2∧D1⇔0B3∧C1∧D2⇔p∧¬q∧r，B3∧C2∧D1⇔0由此得：E⇔(¬p∧q∧¬r)∨(p∧¬q∧r)因矿样不能既是锡，又是铜，故p、r之一必为假。于是，E⇔¬p∧q∧¬r由E为真命题立得p、r为假，q为真，即矿样是铁。此时，甲全对，丙对一半，乙全错。§2析取范式与合取范式命题公式的标准形，用于判断类型，等值。定义命题变项及否定称为文字，有限个文字的析取式称为简单析取式，有限个文字的合取式称为简单合取式。8有限个简单析取式的合取式称为合取范式，有限个简单合取式的析取式称为析取范式，合取范式与析取范式统称为范式。显然，简单析（合）取式是重言（矛盾）式当且仅当它同时含有某个命题变项及其否定。显然，析（合）取范式是矛盾（重言）式当且仅当它的每个简单合（析）取式都是矛盾（重言）式。例求命题公式(p→q)↔r的范式。解（1）求合取范式(p→q)↔r⇔((p→q)→r)∧(r→(p→q))⇔((p∧¬q)∨r)∧(¬r∨¬p∨q)⇔(p∨r)∧(¬q∨r)∧(¬p∨q∨¬r)（2）求析取范式(p→q)↔r⇔((p∧¬q)∨r)∧(¬r∨¬p∨q)⇔((p∧¬q)∧(¬p∨q∨¬r))∨(r∧(¬p∨q∨¬r))9⇔(p∧¬q∧¬p)∨(p∧¬q∧q)∨(p∧¬q∧¬r)∨(r∧¬p)∨(r∧q)∨(r∧¬r)定理任一命题公式都存在与之等值的析取范式与合取范式。求范式的步骤：①消去联结词→，↔②否定联结词消去或内移③∧对∨分配求析取范式，∨对∧分配求合取范式。定义在含n个命题变项的简单合取（析取）式中，若每个命题变项或其否定恰出现一次但不同时出现，并且文字按字母顺序或下标递增顺序排列，则称这样的简单合取（析取）式为极小项（极大项）。注（1）含n个命题变项的极小项有2n个；（2）每个极小项恰有一个成真赋值，且不同极小项的成真赋值也不同。10因此，每个n位二进制数恰对应一个极小项，用mi表示极小项，i为对应成真赋值的十进制表示。例如，m0=m00=¬p∧¬qm1=m01=¬p∧qm2=m10=p∧¬qm3=m11=p∧q同理，极大项也有2n个，每个恰有一个成假赋值，故每个n位二进制数恰对应一个极大项，用Mi表示极大项，i为对应成假赋值的十进制表示。例如，M0=M00：p∨qM1=M01：p∨¬qM2=M10：¬p∨qM3=M11：¬p∨¬q显然，¬mi⇔Mi，¬Mi⇔mi定义由极小项构成的析取范式称为主析取范式，由极大项构成的合取范式称为主合取范式，主析取范式与主合取范式统称为主范式。11注在主范式中，一个极小(大)项只写一次。求主范式的步骤：①同求范式的步骤②若析取范式中某简单合取式A不含pi及¬pi，则：A⇔A∧1⇔A∧(pi∨¬pi)⇔(A∧pi)∨(A∧¬pi)反复上述过程，直到A变为极小项；若合取范式中某简单析取式B不含pi及¬pi，则B⇔B∨0⇔B∨(pi∧¬pi)⇔(B∨pi)∧(B∨¬pi)反复上述过程，直到B变为极大项。例求命题公式(p→q)↔r的主范式。解（1）求主析取范式：(p→q)↔r⇔(p∧¬q∧¬p)∨(p∧¬q∧q)∨(p∧¬q∧¬r)∨(r∧¬p)∨(r∧q)∨(r∧¬r)⇔(p∧¬q∧¬r)∨(¬p∧r)∨(q∧r)⇔(p∧¬q∧¬r)∨(¬p∧1∧r)∨(1∧q∧r)12⇔(p∧¬q∧¬r)∨(¬p∧(q∨¬q)∧r)∨((p∨¬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)=m1∨m3∨m4∨m7（2）求主合取范式：(p→q)↔r⇔(p∨r)∧(¬q∨r)∧(¬p∨q∨¬r)⇔(p∨0∨r)∧(0∨¬q∨r)∧(¬p∨q∨¬r)⇔(p∨(q∧¬q)∨r)∧((p∧¬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)=M0∧M2∧M5∧M6注①在主析取（合取）范式中，使一个极小13（大）项成真（假）的赋值也使整个主析取（合取）范式成真（假）。②在两个主范式中，出现的极小项和极大项对应的赋值包含全部可能的赋值，但二者不重合。③主析取范式中出现的极小项对应命题公式的成真赋值，而主合取范式中出现的极大项对应命题公式的成假赋值。④重言式的主合取范式记为1，矛盾式的主析取范式记为0。例讨论命题公式p→q的主范式与各种赋值。解（方法一）p→q⇔¬p∨q=M2主合取范式⇔(¬p∧1)∨(1∧q)⇔(¬p∧(q∨¬q))∨((p∨¬p)∧q)⇔(¬p∧q)∨(¬p∧¬q)∨(p∧q)∨(¬p∧q)⇔(¬p∧q)∨(¬p∧¬q)∨(p∧q)=m0∨m1∨m3主析取范式14（方法二）由真值表得p→q的成假赋值为10，所以命题公式对应极大项为M2=¬p∨q，故主合取范式为M2。又因为p→q的成真赋值为00,01,11，它们分别对应极小项m0=¬p∧¬q，m1=¬p∧q，m3=p∧q，所以主析取范式为m0∨m1∨m3。（方法三）p→q⇔¬p∨q=M2主合取范式⇒成假赋值10⇒成真赋值00,01,11⇒极小项m0=¬p∧¬q，m1=¬p∧q，m3=p∧q⇒p→q⇔m0∨m1∨m3主析取范式pqp→q00101110011115例从甲、乙、丙三人中挑选一至两名出国进修，要求（1）若甲去，则丙同去；（2）若乙去，则丙不能去；（3）若丙不去，则甲或乙可以去。求全部派出方案。解p：派甲去；q：派乙去；r：派丙去。三个条件可表示为：(p→r)∧(q→¬r)∧(¬r→(p∨q))可得上式的主析取范式为(¬p∧¬q∧r)∨(¬p∧q∧¬r)∨(p∧¬q∧r)由此得有3种派出方案：（Ⅰ）丙去，甲、乙都不去。（Ⅱ）乙去，甲、丙都不去。（Ⅲ）甲、丙去，乙不去。n个命题变项可产生2n个极小项，由此可构造：01222222nnnnnCCC+++=个不同的主析取范式。因此，含n个命题变项的不等值命题公式共有22n类。16§3联结词的完备集定义设12(,,,)nFFxxx=是n元函数，自变量和函数值都取值于{0,1}，则称F是n元真值函数。每个命题公式类都对应一个与类中每个公式都等值的真值函数F，而一个真值函数F对应一个主析取范式。定义设S是联结词集合，若任何n(≥1)元真值函数都可由S中的联结词构成的命题公式表示，则称S是联结词完备集。定理S={¬,∨,∧}是联结词完备集。推论S1={¬,∧}，S2={¬,∨}，S3={¬,→}都是联结词完备集。不同联结词完备集可构造出不同的形式系统。例如，S构造的形式系统是主析取范式和主合取范式。17定义设p,q是两个命题，（1）复合命题“p与q的否定式”称为p与q的与非式，记为p↑q，命题p↑q真当且仅当p与q不同时为真。（2）复合命题“p或q的否定式”称为p与q的或非式，记为p↓q，命题p↓q真当且仅当p与q同时为假。定理{↓}，{↑}都是联结词完备集。¬p⇔p↑pp∧q⇔(p↑q)↑(p↑q)p∨q⇔(p↑p)↑(q↑q)¬p⇔p↓pp∧q⇔(p↓p)↓(q↓q)p∨q⇔(p↓q)↓(p↓q)