离散数学04196.ppt

两个命题变元P和Q的大项真值表如下表所示：由真值表可得大项具有如下的性质：(1)各大项的真值表都是不同的；(2)每个大项只有当赋值与其对应的二进制编码相同时，其真值为假，且其真值0位于主对角线上；(3)任两不同大项的析取式是永真式；(4)所有大项的合取式为永假式。2.主合取范式定义与存在定理定义1.25 由若干个不同的大项组成的合取式称为主合取范式；与A等价的主合取范式称为A的主合取范式。定理1.14 任意含n个命题变元的非永真命题公式A都存在与其等价的主合取范式，并且是惟一的。3.求主合取范式的方法1)真值表法定理1.15在真值表中，命题公式A的真值为F的赋值所对应的大项的合取即为此公式的主合取范式。例5 用真值表法求(P?Q)∧Q的主合取范式。解 (P?Q)∧Q的真值表如下表所示：从上表知，该公式仅在其真值表的00行、10行处取真值0，所以(P?Q)∧Q?(P∨Q)∧(?P∨Q)?M0∧M2。2)公式法求主合取范式的步骤如下：(1)求A的合取范式A?；(2)若A?的某简单析取式B中不含某个命题变元P或其否定?P，则将B展成形式B?B∨0?B∨(P∧?P)?(B∨P)∧(B∨?P)(3)将重复出现的命题变元、永真式及重复出现的大项都消去；(4)将大项按顺序排列。例6 用公式法求(P?Q)?(P∧?R)的主合取范式。解 (P?Q)?(P∧?R)(P∧?Q)∨(P∧?R)P∧(?Q∨?R)(P∨Q)∧(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)M0∧M1∧M2∧M3∧M7。4.主析取范式与主合取范式之间的关系定理1.16 小项mi与大项Mi满足?mi?Mi，?Mi?mi。证明 由小项和大项的定义及对偶性即得。定理1.17 设A是含有n个命题变元的命题公式，且A的主析取范式中含k个小项m1、m2、…、mk，则?A的主析取范式中必含有其余的2n－k个小项，记为，且A? 例7 求?(P∧Q)??(?P?R)的主析取范式和主合取范式。 证明 ?(P∧Q)??(?P?R)(?(P∧Q)??(?P?R))∧(?(?P?R)??(P∧Q))((P∧Q)∨?(?P?R))∧((?P?R)∨?(P∧Q))((P∧Q)∨(?P∧?R))∧((P∨R)∨(?P∨?Q))(P∨?R)∧(?P∨Q)∧(Q∨?R)(P∨Q∨?R)∧(P∨?Q∨?R)∧(?P∨Q∨R)∧(?P∨Q∨?R)∧(P∨Q∨?R)∧(?P∨Q∨?R)M1∧M3∧M4∧M5m0∨m2∨m6∨m7 1.7.3主范式的应用1.判定命题公式的类型定理1.18 设A是含n个命题变元的命题公式，则：(1)A为永真式当且仅当A的主析取范式含有全部2n个小项。(2)A为矛盾式当且仅当A的主合取范式含有全部2n个大项。(3)若A的主析取范式至少含有一个小项，则A是可满足式。例8 判断下列命题公式的类型：(1)(?P∨Q)∧(?Q∨R)∧(P∧?R)(2)((P?Q)∧P)?Q(3)(P?Q)∧Q解 (1)(?P∨Q)∧(?Q∨R)∧(P∧?R)(?P∨Q∨R)∧(?P∨Q∨?R)∧(P∨?Q∨R)∧(?P∨?Q∨R)∧(P∨Q)∧(P∨?Q)∧(P∨?R)∧(?P∨?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)∧(?P∨Q∨?R)∧(?P∨?Q∨?R)M0∧M1∧M2∧M3∧M4∧M5∧M6∧M7(2)((P?Q)∧P)?Q??((?P∨Q)∧P)∨Q(?P∨Q)∨?P∨Q?(P∧?Q)∨?P∨Q(P∧?Q)∨(?P∧(Q∨?Q))∨((P∨?P)∧Q)(P∧?Q)∨(?P∧Q)∨(?P∧?Q)∨(P∧Q)∨(?P∧Q)m0∨m1∨m2∨m3(3) (P?Q)∧Q?(?P∨Q)∧Q?(?P∧Q)∨Q(?P∧Q)∨((?P∨P)∧Q)(?P∧Q)∨(?P∧Q)∨(P∧Q)(?P∧Q)∨(P∧Q)?m1∨m3因此，(1)为永假式，(2)为永真式，(3)为可满足式。2.判断两个命题公式是否等价例9 判断(P?Q)∧(P?R)与P?(Q∧R)是否等价。证明 因为(P?Q)∧(P?R)?(?P∨Q)∧(?P∨R)(?P∨Q∨(R∧?R))∧(?P∨(Q∧?Q)∨R)(?P∨Q∨R)∧(?P∨Q∨?R)∧(?P∨Q∨R)∧(?P∨?Q∨R)M4∧M5∧M6P?(Q∧R)??P∨(Q∧R)(?P∨Q)∧(?P∨R)?M4∧M5∧M6所以，(P?Q)∧(P?R)?P?(Q∧R) 1.4对偶式与蕴涵式 1.4.1对偶式定义1.15 在给定的仅使