离散数学(讲)命题逻辑.pptVIP

等价式的判定 例3.4 证明P∨┐((P∨┐Q)∧Q) 是永真公式。 证：P∨┐((P∨┐Q)∧Q) ?P∨┐(P∨┐Q)∨┐Q (De Morgan定律) ?(P∨┐Q)∨┐(P∨┐Q) (交换律) (结合律) ?T ■（矛盾律） * * 等价式的判定 例3.5 证明P→(Q→R) ?(P∧Q)→R 证：P→(Q→R) ? ┐P∨(Q→R)（蕴涵） ? ┐P∨(┐Q∨R) （蕴涵） ?(┐P∨┐Q)∨R (结合律) ? ┐(P∧Q)∨R （蕴涵） ?(P∧Q)→R ■（蕴涵） * * 等价式的判定 例3.6 试证明(P∧(Q∨R))∨(P∧┐Q∧┐R) ?P 证明： (P∧(Q∨R))∨(P∧┐Q∧┐R) ?P∧((Q∨R)∨(┐Q∧┐R))（分配律） ? P∧((Q∨R)∨┐(Q∨R)) (De Morgan定律) ? P∧T（矛盾律） ?P■(同一律) * * 等价式的判定 例3.7 试证明(┐P∧(┐Q∧R))∨((Q∧R)∨(P∧R))?R 证明：(┐P∧(┐Q∧R))∨((Q∧R)∨(P∧R)) ?((┐P∧┐Q)∧R）∨((Q∨P)∧R)（结合律、分配律） ?(┐(P∨Q)∧R)∨((Q∨P)∧R) (De Morgan定律) ?(┐(P∨Q)∨(Q∨P)）∧R（分配律） ?T∧R(交换律、矛盾律） ?R ■（同一律） * * 等价式的判定 将下列语句化简：情况并非如此：如果他不来，那么我也不去。 解：设P：他来，Q：我去 此语句为： ～（～ P→～Q） 化简～（ ～P→～Q） ? ～（ ～ ～ P ∨ ～ Q ） ? ～（P ∨ ～ Q ） ? ～ P ∧ Q 我去了但他没来。 * * 等价式的判定 世界冰球赛在激烈地进行，看台上三位观众正在热烈地议论着这场比赛的名次。 甲：中国第一，匈牙利第三； 乙：奥地利第一，中国第三； 丙：匈牙利第一，中国第二。 比赛结束后，发现三位观众每人恰好都猜对了一个。问：中国、奥地利、匈牙利各队的名次各是第几（无并列名次）？ * * 等价式的判定 解：设命题如下：P1：中国第一，P2：中国第二， P3：中国第三,Q1:奥地利第一,R1:匈牙利第一,R3:匈牙利第三 由于甲、乙、丙各猜对了一个，故有等值式 （P1∧～R3）∨（～P1∧R3） ? 1……① （Q1∧～P3）∨（～Q1∧P3） ? 1……② （R1∧～P2）∨（～R1∧P2） ? 1……③ 由于重言式的合取仍为重言式，先对①，②两式左端求合取有： * * 等价式的判定 （（P1∧～R3）∨（～P1∧R3）)∧ （（Q1∧～P3）∨（～Q1∧P3）) ? 1……④ 对④式左端进行等值演算。得： （P1∧～R3∧Q1∧～P3)∨（～P1∧R3∧Q1∧～ P3）∨（P1∧～ R3∧ ～ Q1∧P3）∨（ ～ P1∧R3 ∧ ～Q1∧P3） ? 1……⑤ 在⑤式中，第一个合取式P1和Q1同时存在，即‘中国第一和奥地利第一’同时成立。在逻辑上是矛盾的，因此，把它消去。 同理，第三、四个合取式消去得 * * 等价式的判定 ～ P1∧R3∧Q1∧ ～ P3 ? 1 ……⑥ 再将⑥和③作同样处理得 ～ P1∧R3∧Q1∧ ～P3 ∧ ～R1∧P2 ? 1 各命题间不再有任何矛盾。因而它们的合取为1，这意味着各命题的取值均为1。由此得结论： 奥地利第一，中国第二，匈牙利第三。 * * 对偶式 E3～E18，E23～E24都是成对出现的，它是逻辑系统对偶性的反映，即对偶式，利用对偶式可以扩大等价式的个数，也可减少证明的次数。 定义：在给定的仅使用联结词～ 、∨、∧的命题公式A中，若把∧和∨，F和T互换而得的公式A*，则称A*为A的对偶（公）式。 将公式中的命题变为其否定，所得公式为A的相反式。 如公式（P∨Q）∧R的对偶式为（P∧Q）∨R ～P∨（Q∧R）的对偶式为～P∧（Q∨R） * * 对偶式 问题：如果两个公式等价，那么它们的对偶式是否也是等价的？ 引理：设P1,P2,…Pn是公式A和A*中的所有命题变元，则 ～A（P1,P2,…Pn）?A*（～P1,～P2,…,～Pn） A(～P1,～P2,…,～Pn)? ～A*(P1,P2,…Pn) 证：∵由 De Morgan定律可知 ～（P∨Q）? ～P∧～Q， ～（P∧Q）? ～P∨～ Q ～T ? F， ～F ? T ∴对公式的否定可以直接作用到原子本身，并且把公式中的∧变成∨，把∨变成∧，即得 ～A（P1,P2,…Pn）?A*（～P1,～P2,…,～Pn） * * 对偶式 对偶原理 设A和B是两个命题公式，若A