离散数学对偶与范式.ppt

第一章 命题逻辑 1-7 对偶与范式 尽管命题公式的最小联结词组可为??，∧?，??，∨?，?↑?，?↓?，但实际上一般出于方便的目的，命题公式常常包含??，∧， ∨ ?。 从第15页的表1-4.8的命题定律中可以看出，很多常用等价式是成对出现的，只要将其中的“∧”和“∨”分别换成“∨”和“∧”，就可以由一个得到另一个。 例如，将命题定律(P∨Q)∨R?P∨(Q∨R)中的“∨”换成“∧”就得到了命题定律(P∧Q)∧R?P∧(Q∧R)。这些成对出现的等价式反映了等价的对偶性。我们将这样的公式称作具有对偶规律。 本节将先介绍对偶式和对偶原理。 一、对偶式与对偶原理 定义1-7.1 在给定的命题公式A中，将联结词∨、∧分别换成∧、∨ ，若有特殊变元F和T亦相互对代，所得的公式称为公式A的对偶式，记为A*。 *设A*是A的对偶式，将A*中的∨，∧，F，T分别换成∧，∨，T，F，就会得到A。即A是A*的对偶式，(A*)*?A。所以说A*和A互为对偶式。 例题1 写出下列表达式的对偶式 1.（ P∨Q）∧R 2. （ P ∧ Q）∨T 3. ?（ P∨Q）∧（ P∨?（Q ∧ ?S）） 一、对偶式与对偶原理 例题2 求P↑Q和P↓Q的对偶式。 解： P↑Q??(P∧Q) ?(P∧Q)的对偶式是?(P∨Q)?P↓Q 故P↑Q的对偶式是P↓Q；同样的方法可以证明P↓Q的对偶式是P↑Q。 注意：根据例题2，对偶式概念可以推广为：在仅含有联结词?，∧，∨，↑，↓的命题公式中，将联结词∨，∧，↑，↓，F，T分别换成 ∧，∨，↓，↑，T，F，就得到了它的对偶式。 一、对偶式与对偶原理 *关于对偶式有以下两个结论。 定理1-7.1 设A*是A的对偶式，P1，P2，…，Pn是出现在A和A*中的原子变元，则 ?A(P1，P2，…，Pn)?A*(?P1，?P2，…，?Pn) A(?P1，?P2，…，?Pn)??A*(P1，P2，…，Pn) 证明见P30：由德摩根律层层置换，即可层层推出。 一、对偶式与对偶原理 例：设命题公式A(P,Q,R)?(P∨Q)∧R，试用此公式验证定理1.7.1的有效性。 证明： ⑴验证 ?A(P,Q,R)?A*(?P, ?Q, ?R) A(P,Q,R)?(P∨Q)∧R ?A(P,Q,R)??((P∨Q)∧R)?(?P∧?Q)∨?R A*(P,Q,R)?(P∧Q)∨R A*(?P, ?Q, ?R)?( ?P∧?Q)∨?R 所以，?A(P,Q,R) ?A*(?P,?Q,?R) ⑵验证 A(?P,?Q,?R)??A*(P,Q,R) A(?P,?Q,?R)?(?P∨?Q)∧?R ??((P∧Q)∨R)??A*(P,Q,R) 一、对偶式与对偶原理 定理1-7.2 设P1，P2，…，Pn是出现在公式A和B中的所有原子变元，如果A?B，则A*?B*。 证明： 因为 A?B, 所以 A(P1，P2，…，Pn)?B(P1，P2，…，Pn)是重言式 根据定理1-5.2(P19)，在上述重言式中用?Pi置换 Pi， i＝1, …,n，所得的公式仍为重言式，即 A(?P1，?P2，…，?Pn)?B(?P1，?P2，…，?Pn)是重言 式。 所以 A(?P1，?P2，…，?Pn)?B(?P1，?P2，…，?Pn) 由定理1-7.1?A*(P1，P2，…，Pn)??B*(P1，P2，…，Pn) 即 ?A*??B* 因此 A*?B* *定理1.7.2叫做对偶原理。对偶原理是数理逻辑中最基本的规律之一。 一、对偶式与对偶原理 例题4:如果A(P,Q,R)是P↑(Q∧?(R ↓P))，求它的对偶式A*(P,Q,R)。并求A及A*的等价，但仅包含联结词“∧”、“∨”及“?”的公式。 解： 因A(P,Q,R)是P↑(Q∧?(R ↓P)) 所以 A*是 P↓(Q∨?(R ↑ P)) 而 P↑(Q∧?(R ↓P)) ? ?(P∧(Q∧(R∨P)) 故 P↓(Q∨?(R ↑ P)) ? ?(P∨(Q∨(R∧P)) 使用真值表和对偶原理可以简化或推证一些命题公式。 一、对偶式与对偶原理 例：证明重言式的对偶式是矛盾式，矛盾式的对偶式是重言式。 证明：设A是重言式