Chapter1.4-Propositional_logic(Disjunctive Normal Form).ppt

(2)判断公式的类型： 设公式A中含有n个命题变元，则： （1） A为重言式? A的主析取范式含全部2n个小项。 （2）A为矛盾式? A的主析取范式不含任何小项， 记A的主析取范式为0。 （3） A为可满足式? A的主析取范式至少含一个小项。 （4） A为矛盾式? A的主合取范式含全部2n个大项。 （5） A为重言式? A的主合取范式不含任何大项， 记A的主合取范式为1 。 （6） A为可满足式? A的主合取范式中大项的个数 一定小于2n 。 例:判断下列命题公式的类型. (1) (P?Q)?R (2) ┐(P?Q)?Q (3) (P?Q)?Q?Q 解:(1) (P?Q)?R?m1∨m3∨m4∨m7为可满足式. (2) ┐(P?Q)?Q?0为矛盾式. (3) (P?Q)?Q?Q?1为重言式. (3)判断两个命题是否等价： 设公式A、B中共含有n个命题变元，按n个命题变 元求出A、B的主析(合)取范式 、 。若 = ， 则A ? B，否则A、B不等价. 例:试判断下列各组命题是否等价. (1) (P?Q)∧(P?R) 与 P?(Q∧R) (2) P?(Q∧R) 与 P∨(Q?R) 解:(1) (P?Q)∧(P?R) ? (┐P∨Q)∧(┐P∨R) ? (┐P∨Q∨(R∧┐R)∧(┐P∨R∨(Q∧┐Q) ?(┐P∨Q∨R)∧(┐P∨Q∨┐R)∧ (┐P∨R∨Q)∧ (┐P∨R∨┐Q) ? M4∧M5∧M6 P?(Q∧R)?┐P∨(Q∧R) ?(┐P∨Q)∧(┐P∨R) ? M4∧M5∧M6 所以 (P?Q)∧(P?R)? P?(Q∧R) 解(2) P?(Q∧R)?┐P∨(Q∧R) ?(┐P∨Q)∧(┐P∨R) ? M4∧M5∧M6 ? m0 ∨ m1 ∨ m2 ∨ m3∨m7 P∨(Q?R) ? P∨┐Q∨R ? M2 ?m0∨m1∨m3∨m4∨m5∨m6∨m7 所以 P?(Q∧R)与P∨(Q?R) 不等价. 5.解决实际问题： 某科研所有三名青年高级工程师A，B，C。所里 要选派他们中的1到2人出国进修，由于所里工作 的需要，选派时必须满足以下条件： ①若A去，则C也去 ②若B去，则C不能去 ③若C不去，则A或B去 问所里应如何选派他们？ 解: 设 P:派A去。Q :派B去。R :派C去。 根据所要满足的条件，得命题公式为： (P?R)∧(Q? ┐R)∧(┐R?( P∨Q) ) 求此公式的主析取范式: 原式 ?(┐P∧┐Q∧R)∨(┐P∧Q∧┐R)∨(P∧┐Q∧R) 因此有三种选派方案：Ｃ去，而Ａ、Ｂ都不去；Ｂ去，而Ａ、Ｃ都不去；Ａ、Ｃ都去，而Ｂ不去. 小结:本节主要介绍了析(合)取范式、(主)析(合)取范式。重点掌握(主)析(合)取范式的求法。 作业: 1. P30: 2, 5, 6(3), 8 2. 预习§1.8 END 2.命题公式的主合取范式 定义1.7.6：在含有n个命题变元的简单析取式中, 若每个命题变元和它的否定不同时出现，而二者 之一必出现且仅出现一次，称这样的简单析取式 为大项. 例如，有两个变元的大项及其真值表： M0 M1 M2 M3 P Q P∨Q P∨?Q ?P∨Q ?P∨?Q F F F T T T F T T F T T T F T T F T T T T T T F ⑵大项的性质 a).有n个变元，则有2n个大项。 b).每一组指派有且只有一个大项为F。 为了记忆方便，可将各组指派对应的为F的大项分别记作M0,M