离散数学基础
2017-11-17
本单元内容比较多，视频分割成三个部分：范式的概念、主范式及其应用和主范式的编码
PART 1 范式的概念
•范式的一些基本定义
−文字：原子命题及其否定式统称为文字（形）。
»例：对变量表 {p, q}，p, ¬p, q, ¬q 都是文字。
»例：把 F 称为空文字，记作 NIL。
−基本积：由有限个文字的合取构成。(简单合取式)
»例：对变量表 {p, q, r}，基本积有 p, ¬p, q∧¬p, ¬q∧¬p∧r 等等。
−基本和：由有限个文字的析取构成。 (简单析取式)
»例：对变量表 {p, q, r}，基本和有 p, ¬p, q∨¬p, ¬q∨¬p∨r 等等。
•定理6
−一个基本和是永真的当且仅当其中含有某个原子的互补对；
»由排中律和零律：α∨p∨¬p ⇔ α∨1 ⇔ 1
−一个基本积是矛盾的当且仅当其中含有某个原子的互补对。
»由矛盾律和零律： α∧p∧¬p ⇔ α∧0 ⇔ 0
•定义：析取范式
−一个命题公式称为是一个析取范式当且仅当其具有形式 A1∨A2∨ …∨A n
(1≤n<∞)，其中 A i 是基本积 (1≤i≤n)。
−例1：¬p ∨ (q∧¬r) ∨ s，(n=3)
−例2：¬p，(n=1)
−例3：¬p ∧ q ∧ ¬r，(n=1)
−例4：¬p ∨ q ∨ ¬r，(n=3)
•定义：合取范式
−一个命题公式称为是一个合取范式当且仅当其具有形式 A1∧A2∧…∧A n
(1≤n<∞)，其中 A i 是基本和 (1≤i≤n)。
−例1：(¬p∨q∨s)∧(¬p∨¬r∨s)， (n=2)
−例2：¬p， (n=1)
−例3：¬p ∧ q ∧ ¬r， (n=3)
−例4：¬p ∨ q ∨ ¬r， (n=1)
•定理7
(1) 一个合取范式是永真的当且仅当其中含有的基本和都是永真的；
(2) 一个析取范式是矛盾的当且仅当其中含有的基本积都是矛盾的。
−证明：留作思考。
•定理8（范式存在基本定理）
−任一命题公式都有与之等值的析取范式和合取范式。
−构造性证明
−以求合取范式为例，重复施行如下的等值变形：
①联结词化归：应用联结词消去等值式，消去→ 和 ↔ ；
②否定词深入：应用德‐摩根律，使否定词直接作用于原子命题变量；
③重复利用 ∧ 和 ∨ 之间的分配律求得析取范式或合取范式。
−例： (p∧(q→r))→s
⇔ ¬(p∧(¬q∨r))∨s 联结词化归
⇔ ¬p∨¬(¬q∨r)∨s 德‐摩根律
⇔ ¬p∨(q∧¬r)∨s 德‐摩根律
⇔ (¬p∨q∨s)∧(¬p∨¬r∨s) 分配律
⇔ (¬p∨q∨s)∧(¬p∨¬r∨s)∧(¬p∨¬r∨s) 幂等律
•讨论：一个命题公式的合取（析取）范式不是唯一的。
PART 2 主范式及其应用
•定义：极小项
−设命题公式 A(p1, p2, …, p n)，又设 A k∈{p k, ¬p k}, k =1..n, 则称 A1∧A2∧…∧A n 为公式 A 的一个极小项。
−极小项也称布尔积。
(1) 关于 A(p1, p2, …, p n) 或原子变量集合 {p1, p2, …, p n} 的极小项有 2n 个。
»例：对 {p, q}，可以构造 22 =4 个极小项 ¬p∧¬q，¬p∧q，p∧¬q，p∧q 。
(2) 对变量表的任一解释有且仅有一个极小项的值为1，其余的值为0，称该极
小项为该解释所对应的极小项。
»例：对 {p, q} 的一个解释 t(p)=1, t(q)=0，有且仅有 p∧¬q=1, 对其他的三个
极小项，每个极小项中至少有一个文字的值是0，所以这三个极小项的值都
是0 。
(3) 任何一对不同极小项的合取为0。所有极小项的析取为1。
»由(2), 对变量表的任一解释，任何一对极小项中最多有一个极小项取值为
1，另外的取值为0，所以合取为0；所有极小项中恰有一个极小项取值为1，
所以析取为1。
•定义：极大项
−设命题公式 A(p1, p2, …, p n)，又设 A k∈{p k, ¬p k}, k =1..n, 则称 A1∨A2∨…∨A n 为公式 A 的一个极大项。
−极大项也称布尔和。
(1) 关于 A(p1, p2, …, p n) 或原子变量集合 {p1, p2, …, p n} 的极大项有 2n 个。
»例：对 {p, q}，可以构造极大项 ¬p∨¬q，¬p∨q，p∨¬q，p∨q 。
(2) 对任一解释有且仅有一个极大项的值为0，其余的值为1，称该极大项为该解
释所对应的极大项。
(3) 任何一对不同极大项的析取为1。所有极大项的合取为0。
•定义：主析取范式
−一个命题公式 B(p1, p2, …, p n) 称为是一个主析取范式(形的)，当且仅当其具有形式
B1∨B2∨…∨B m (1≤m≤ 2n)，
其中 B i (1≤i≤m) 为公式 B 的一个极小项，且 B i≠B j (对i≠j)。
•定义：主合取范式
−一个命题公式 B(p1, p2, …, p n) 称为是一个主合取范式(形的)，当且仅当其具有形式
B1∧B2 ∧ …∧B m (1≤m≤ 2n)，
其中 B i (1≤i≤m) 为公式 B 的一个极大项，且 B i≠B j (对i≠j)。
•定理9（主范式存在和唯一性定理）
−任一命题公式都有与之等值的主析取范式和主合取范式。考虑到在交换律下等值的公式形态的同一性，主范式的形态是唯一的。
−证明：留作思考。
•例：利用真值表求公式 A 的主析取范式。
p q A
000
011
101
111
−在命题公式 A 的真值表中，令 A 的取值为1的所有解释所对应的极小项的析
