离散数学第1章第4节.ppt

第一章 命题逻辑第5讲 第一章 命题逻辑第4讲§1—7 对偶与范式 定义1-7.1 在给定的命题公式中，将联结词∨换成∧，将∧换成 ∨，若有特殊变元F和T亦相互取代，所得公式A*称作A的对偶式。 一、对偶式 1. 复习命题定律。见15页表1-4.8 我们从表1-4.8可以看到命题定律除对合律外都是成对出现的，其不同的只是∨和∧互换。我们把这样的公式称作具有对偶规律。 定义1-7.1 在给定的命题公式中，将联结词∨换成∧，将∧换成 ∨，若有特殊变元F和T亦相互取代，所得公式A*称作A的对偶式。 显然A也是A*的对偶式。 例题1 写出下列表达式的对偶式。 例题1 写出下列表达式的对偶式。 二、范式的概念 1、举例 将命题公式(┐P ∧ Q) → R化成仅包含联结词“∧”、“∨”、及“┐”的公式。 2、合取范式的定义 定义1-7.2 一个命题公式称为合取范式，当且仅当它具有形式： A1 ∧ A2 ∧ … ∧ An， （n≥1） 其中A1，A2，…An都是由命题变元或其否定所组成的析取式。 例如(P∨┐ Q ∨R) ∧(┐P∨Q) ∧┐Q 只有1个命题变元或命题变元的否定的命题公式可以看做析取式，也可以看做合取式，如P 和┐P 。 3、析取范式的定义 定义1-7.3 一个命题公式称为析取范式，当且仅当它具有形式： A1 ∨ A2 ∨ … ∨ An， （n≥1） 其中A1，A2，…An都是由命题变元或其否定所组成的合取式。 例如┐P ∨(P∧ Q )∨(P ∧┐Q ∧R)是析取范式。 4、求一个命题公式的合取或析取范式的三个步骤： 例题5 求(P ∧( Q → R)) →S的合取范式。 ? (┐P∧┐Q∧P∧Q)) ∨ (P ∧┐P )∨(Q ∧┐P ) ∨ (P ∧┐Q )∨(Q ∧┐Q ) 四、主范式 一个命题公式的合取范式或析取范式并不是唯一的。例如 P∨(Q ∧R)是一个析取范式，但它亦可以写成 P∨(Q ∧R) ?( P∨Q) ∧(P∨R) ? (P ∧P) ∨(P∧R) ∨ (Q∧P) ∨(Q∧R) 1、小项 为了使任意一个命题公式，化成唯一的等价命题的标准形式，下面给出主范式的有关概念。 定义1-7.4 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个小项。 两个命题变元P和Q及其小项的真值表： 三个命题变元P、Q、R及其小项的真值表（真值T和F分别记为1和0）： 按照三个命题变元P、Q、R及其小项的真值表可以作出一种编码： m000= ┐P∧┐Q ∧┐R ，m100= P∧┐Q ∧┐R m001= ┐P∧┐Q ∧R， m101=P∧┐Q ∧R m010= ┐ P∧Q ∧┐R ， m110=P∧Q ∧┐R m011= ┐P∧Q ∧R， m111=P∧Q∧R 3、小项的性质 定义1-7.5 对于给定的命题公式，如果有一个等价公式，它仅由小项的析取所组成，则该等价式称作原式的主析取范式。 如┐(P∧Q )∧(P∨Q)的主析取范式为 (P∧┐Q ) ∨(┐P∧Q) （1） 真值表法 定理1-7.3 在真值表中,一个公式的真值为T的指派所对应的小项的析取,即为此公式的主析取范式。 证明 设给定公式