离散数学第1章 1.ppt

题例2 甲、乙、丙、丁四人参加考试后，有人问他们，谁的成绩最好，甲说“不是我”，乙说“是丁”，丙说“是乙”，丁说“不是我”。四人的回答只有一人符合实际，问是谁的成绩最好？只有一人成绩最好的话，是谁？ 题例3 张三说李四在说谎，李四说王五在说谎，王五说张三、李四都在说谎。问张三、李四、王五三人，到底谁说真话，谁说假话？ * * * * * * * * (b)若A?0，或A可化为与其等价的、含2n个大项的主合取范式，则A为永假式。 (c)若A不与1或者0等价，且又不含2n个小项或者大项，则A为可满足的。 （2）证明等价式成立 由于任一公式的主范式是唯一的，所以将给定的公式求出其主范式，若主范式相同，则给定两公式是等价的。 主范式的用途(续) 例 某公司要从赵、钱、孙、李、周五名新毕 业的大学生中选派一些人出国学习. 选派必须 满足以下条件： (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.8 命题逻辑的推理理论 在逻辑学中，把从前题（又叫公理或假设）出发，依据公认的推理规则，推导出一个结论，这一过程称为有效推理或形式证明。所得结论叫做有效结论，这里最关心的不是结论的真实性而是推理的有效性。前提的实际真值不作为确定推理有效性的依据。但是，如果前提全是真，则有效结论也应该真而绝非假。 在数理逻辑中，集中注意的是研究和提供用来从前提导出结论的推理规则和论证原理，与这些规则有关的理论称为推理理论。 提请注意，必须把推理的有效性和结论的真实性区别开。有效的推理不一定产生真实的结论，产生真实结论的推理过程未必一定是有效的。再说，有效的推理中可能包含假的前提；而无效的推理却可能包含真的前提。 可见，推理的有效性是一回事，前提与结论的真实与否是另一回事。所谓推理有效，指它的结论是它的前提的合乎逻辑的结果，也即，如果它的前提都为真，那么所得结论也必然为真，而并不是要求前提或结论一定为真或为假。如果推理是有效的话，那么不可能它的前提都为真时而它的结论为假。 １.推理的基本概念和推理形式 推理也称论证，它是指由已知命题得到新的命题的思维过程，其中已知命题称为推理的前提或假设，推得的新命题称为推理的结论。 在数理逻辑中，前提H是一个或者n个命题公式H1,H2,···Hn；结论是一个命题公式C。由前提到结论的推理形式可表为H1,H2,···,Hn?C，其中符号?表示推出···。可见，推理形式是命题公式的一个有限序列，它