离散数学第5次课.ppt

1.6 公式标准型——范式 １.简单合取式与简单析取式 定义1.6.1 在一公式中，仅由命题变元及其否定构成的合取式， 称该公式为简单合取式， 其中每个命题变元或其否定，称为合取项。 定义1.6.2 在一公式中，仅由命题变元及其否定构成的析取式， 称该公式为简单析取式， 其中每个命题变元或其否定，称为析取项。 例如，公式P，?Q，P?Q和?P?Q?P等都是简单合取式， 而P，Q和?P为相应的简单合取式的合取项； 公式P，?Q，P?Q，?P?Q?P等都是简单析取式， 而P，Q和?P为相应简单析取式的析取项。 注意，一个命题变元或其否定既可以是简单合取式， 也可是简单析取式， 如例中P，?Q等。 定理1.6.1 简单合取式为永假式的充要条件是 它同时含有某个命题变元及其否定。 定理1.6.2 简单析取式为永真式的充要条件是 它同时含有某个命题变元及其否定。 ２.析取范式与合取范式 定义1.6.3 一个命题公式A称为析取范式，当且仅当A可表为简单合取式的析取， 即A?∨Ai；其中Ai为简单合取式，i=1，2，…，n。 定义1.6.4 一个命题公式A称为合取范式，当且仅当A可表为简单析取式的合取， 即A?∧Ai；其中Ai为简单析取式，1≤i≤n。 定理1.6.3 对于任何一命题公式，都存在与其等价的析取范式和合取范式。 求范式算法： ① 使用命题定律，消去公式中除?、?和?以外公式中出现的所有联结词； ② 使用?(?P)?P和德·摩根律，将公式中出现的联结词?都移到命题变元之前； ③ 利用结合律、分配律等将公式化成析取范式或合取范式。 ３.范式的应用 利用析取范式和合取范式可对公式进行判定。 定理1.6.4 公式A为永假式的充要条件是A 的析取范式中每个简单合取式至少包含一个命题变元及其否定。 定理1.6.5 公式A为永真式的充要条件是A 的合取范式中每个简单析取式至少包含一个命题变元及其否定。 ４.范式不唯一性 1.7 公式的主范式 范式基本解决了公式的判定问题。 但由于范式不唯一性，对识别公式间是否等价带来一定困难，而公式的主范式解决了这个问题。 下面将分别讨论主范式中的 主析取范式和主合取范式。 １.主析取范式 (1) 小项的概念和性质 定义1.7.1 在含有n个命题变元的简单合取式中， 若每个命题变元与其否定不同时存在， 而二者之一出现一次且仅出现一次， 则称该简单合取式为小项，或布尔积。 例如，两个命题变元P和Q，其构成的小项有 P?Q，P??Q，?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，?P??Q??R。 可以证明，n个命题变元共形成2n个小项。 如果将命题变元按字典序排列， 并且把命题变元与1对应，命题变元的否定与0对应， 则可对2n个小项依二进制数编码，记为mi， 其下标i是由二进制数转化的十进制数。 用这种编码所求得2n个小项的真值表， 可明显地反映出小项的性质。 表1.7.1和表1.7.2分别给出了2个命题变元P和Q 3个命题变元P、Q和R的小项真值表。 从表1.7.1，表1.7.2可看出，小项有如下性质： (a)没有两个小项是等价的，即是说各小项的真值表都是不同的； (b)任意两个不同的小项的合取式是永假的：mi∧mj?Ｆ，i≠j。 (c)所有小项之析取为永真： ∨mi?Ｔ。 (d)每个小项只有一个解释为真，且其真值1位于主对角线上。 (2) 主析取范式定义与存在定理 定义1.7.2 在给定公式的析取范式中， 若其简单合取式都是小项， 则称该范式为主析取范式。 定理1.7.1 任意含n个命题变元的非永假命题公式A 都存在与其等价的主析取范式。 (3) 主析取范式的求法 主析取范式求法有两种：真值表法和公式化归法。 定理1.7.1的证明已给出了用真值表求主析取范式的方法， 而公式化归法给出如下： (a)把给定公式化成析取范式； (b)删除析取范式中所有为永假的简单合取式； (c