离散数学、.ppt

* 计算机学院 * 利用公式的等价求G＝(P→Q)∧R的主合取范式和主析取范式。 解：G＝(P→Q)∧R＝(～P∨Q)∧R（蕴涵） ＝(～P∨Q∨(R∧～R))∧ ((～P∧P)∨(～Q∧Q)∨R)（添加R、P、Q） ＝(～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)（结合律） －－－－－主合取范式 例1-5.4 * 计算机学院 * G＝(P→Q)∧R＝(～P∨Q)∧R （蕴涵） ＝(～P∧R)∨(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) ——主析取范式 例1-5.4（续） * 计算机学院 * §1．6 命题公式的蕴涵 定义1.18 设A和B是两个合适公式，如果在任何解释下，A取值1时B也取值1，则称公式A蕴涵公式B，并记A ?B。 定理1.11 A?B iff A→B为永真式。 注意：蕴涵和条件联结词→是完全不同的。 →是命题联结词，A→B是一个命题公式； ?是公式间关系符，A?B不是一个命题公式，仅表示A，B间的蕴涵关系。 * 计算机学院 * 基本蕴涵（关系）式（蕴涵定律） I1：P∧Q ?P ， P∧Q?Q I2: ～（P→Q）?P ，～（P→Q）?～Q I3：P?P∨Q ， Q?P∨Q I4：～P?P→Q ， Q?P→Q √I5：P∧（P→Q）? Q 假言推论 √I6：～Q∧（P→Q）? ～P 拒取式（否定式假言推论） √I7：～P∧（P∨Q）? Q 析取三段论 √I8：（P→Q）∧（Q→R）? P→R 假言三段论 扩充法则 简化法则 * 计算机学院 * 基本蕴涵（关系）式（续） √I9：（P∨Q）∧（P→R）∧（Q→R）? R 二难推论 I10： （P→Q）∧（R→S）?（P∧R）→（Q∧S） √I11：（P?Q）∧（Q?R）? P?R 等价三段论 √I12：（P∨Q）∧（～P∨R）? Q∨R 归结原理 [解释：（～P→Q）∧（P→R） ? Q∨R ] * 计算机学院 * 蕴涵关系的性质 ① 自反性 A ? A ② 反对称性: 如果A ? B，B ? A， iff A ? B ③ A ? B 且A为永真式，则B必为永真式 * 计算机学院 * ④传递性，如果A ? B，B ? C，则A ? C 【证明】 由已知条件A ? B，且 B ? C， 根据定理1.11 (A→B）∧（B→C） 是永真式； 再由假言三段论，应有 （A→B）∧（B→C）? A→C ； 再根据性质3， A→C也必是永真式， 即A ? C 。■ * 计算机学院 * ⑤ 如A ? B，A ? C， iff A ? B∧C 【证明】“?” 由 A?B 且 A?C 得到A?B和A?C都是永真式，于是 （A?B）∧（A?C）也是永真式；但是， （A?B）∧（A?C） ?（～A∨B）∧(～A∨C) ?～A∨(B∧C)?A→(B∧C)， 所以A?(B∧C)是永真式，即A?B∧C。 * 计算机学院 * “?”从证明过程看，性质5反过来也对，即由 A?B∧C可以得到A?B 且 A?C 。 ⑥ 如A ? B，C ? B，则A∨C ? B ⑦ A∧B ?C iff A ? B→C 该性质是推理演绎中CP规则的基础 ⑧ A ? B iff A∧～B是矛盾式 该性质是反证法的基础 * 计算机学院 * 定理1.12 A?B iff ～B?～A 该定理提供了逆向思维的基础 * 计算机学院 * 例1-6.1 考虑以下语句，并将其前提和结论符号化。 1)、前提： 　1. 如果明天天晴，我们准备外出旅游。P→Q 　2．明天的确天晴。　　　　　　　　 P 　　结论：我们外出旅游。　　　　 Q 　上述例子可描述为：P→Q，P?Q　(假言推论) 2)、前提： 　1.　如果一个人是单身汉，则他不幸福。P→Q 　2.　如果一个人不幸福，