离散数学(对偶和范式).ppt

* 主范式的用途(续) 例 某公司要从赵、钱、孙、李、周五名新毕 业的大学生中选派一些人出国学习. 选派必须 满足以下条件： (1)若赵去，钱也去； (2)李、周两人中至少有一人去； (3)钱、孙两人中有一人去且仅去一人； (4)孙、李两人同去或同不去； (5)若周去，则赵、钱也去. 试用主析取范式法分析该公司如何选派他们出 国？ * 例 (续) 解此类问题的步骤为： ① 将简单命题符号化 ② 写出各复合命题 ③ 写出由②中复合命题组成的合取式 ④ 求③中所得公式的主析取范式 * 例 (续) 解 ① 设p：派赵去，q：派钱去，r：派孙去， s：派李去，u：派周去. ② (1) (p?q) (2) (s?u) (3) ((q??r)?(?q?r)) (4) ((r?s)?(?r??s)) (5) (u?(p?q)) ③ (1) ~ (5)构成的合取式为 A=(p?q)?(s?u)?((q??r)?(?q?r))? ((r?s)?(?r??s))?(u?(p?q)) * 例 (续) ④ A ? (?p??q?r?s??u)?(p?q??r??s?u) 结论：由④可知，A的成真赋值为00110与11001， 因而派孙、李去（赵、钱、周不去）或派赵、钱、 周去（孙、李不去）. A的演算过程如下: A ? (?p?q)?((q??r)?(?q?r))?(s?u)?(?u?(p?q))? ((r?s)?(?r??s)) （交换律) B1= (?p?q)?((q??r)?(?q?r)) ? ((?p?q??r)?(?p??q?r)?(q??r)) （分配律） * 例 (续) B2= (s?u)?(?u?(p?q)) ? ((s??u)?(p?q?s)?(p?q?u)) （分配律） B1?B2 ? (?p?q??r?s??u)?(?p??q?r?s??u) ?(q??r?s??u)?(p?q??r?s)?(p?q??r?u) 再令 B3 = ((r?s)?(?r??s)) 得 A ? B1?B2?B3 ? (?p??q?r?s??u)?(p?q??r??s?u) 注意：在以上演算中多次用矛盾律 要求：自己演算一遍 * 1.5 对偶与范式 对偶式与对偶原理 析取范式与合取范式 主析取范式与主合取范式 * 对偶式和对偶原理 定义 在仅含有联结词?, ∧,∨的命题公式A中，将∨换成∧, ∧换成∨，若A中含有0或1，就将0换成1，1换成0，所得命题公式称为A的对偶式，记为A*. 从定义不难看出，(A*)* 还原成A 显然，A也是A*的对偶式。可见A与A*互为对偶式。 * 对偶式和对偶原理 定理 设A和A*互为对偶式，p1,p2,…,pn是出现在A和 A*中的全部命题变项，将A和A*写成n元函数形式， 则 (1) ? A(p1,p2,…,pn) ? A* (? p1, ? p2,…, ? pn) (2) A(? p1, ? p2,…, ? pn) ? ? A* (p1,p2,…,pn) (1)表明，公式A的否定等价于其命题变元否定的对偶式； (2)表明，命题变元否定的公式等价于对偶式之否定。 * 对偶式和对偶原理 定理（对偶原理）设A，B为两个命题公式， 若A ? B，则A* ? B*. 有了等值式、代入规则、替换规则和对偶定理，便可以得到更多的永真式，证明更多的等值式，使化简命题公式更为方便。 * 判定问题 真值表 等值演算 范式 * 析取范式与合取范式 文字:命题变项及其否定的总称 如 p, ?q 简单析取式:有限个文字构成的析取式 如 p, ?q, p??q, p?q?r, … 简单合取式:有限个文字构成的合取式 如 p, ?q, p??q, p?q?r, … 注意：一个命题变元或其否定既可以是简单合取式，也可是简单析取式，如p，?q等。 * 析取范式与合取范式 定理： 简单合取式为永假式的充要条件是：它同时含有某个命题变元及其否定。 定理： 简单析取式为永真式的充要条件是：它同时含有某个命题变元及其否定。 * 析取范式与合取范式 简单析取式:有限个文字构成的析取式 如 p, ?q, p??q, p?q?r, … 简单合取式:有限个文字构成的合取式 如 p, ?q, p??q, p?q?r, … 析取范式:由有限个简单合取式组成的析取式 A1?A2???Ar, 其中A1,A2,?,Ar