离散数学与组合数学汇总

定义2.1 若等价式A↔B是重言式，则称A与B等值，记作AB，并称AB是等值式

几点说明：

例1 判断下列各组公式是否等值: (1) p→(q→r) 与 (p∧q) →r 结论: p→(q→r) (p∧q) →r (2) p→(q→r) 与 (p→q) →r 结论：p→(q→r) 与 (p→q) →r 不等值

特别提示：必须牢记这16组等值式，这是继续学习的基础

证明两个公式等值

证 p→(q→r) ¬p∨（¬q∨r) （蕴涵等值式，置换规则） (¬p∨¬q)∨r （结合律，置换规则） ¬(p∧q)∨r （德摩根律，置换规则） (p∧q)→r （蕴涵等值式，置换规则） 今后在注明中省去置换规则 注意：用等值演算不能直接证明两个公式不等值

证明两个公式不等值

证 方法一 真值表法, 见例1(2) 方法二 观察法. 观察到000, 010是左边的成真赋值，是右边的成假赋值 方法三 先用等值演算化简公式，然后再观察 p→(q→r) ¬p∨¬q∨r (p→q)→r ¬(¬p∨q)∨r(p∧¬q)∨r 更容易看出前面的两个赋值分别是左边的成真赋 值和右边的成假赋值 判断公式类型: A为矛盾式当且仅当A 0 A为重言式当且仅当A 1

解 (1) q∧¬(p→q) q∧¬(¬p∨q) （蕴涵等值式） q∧(p∧¬q) （德摩根律） p∧(q∧¬q) （交换律，结合律） p∧0 （矛盾律） 0 （零律） 矛盾式 (2) (p→q) ↔(¬q→¬p) (¬p∨q)↔(q∨¬p) （蕴涵等值式） (¬p∨q)↔(¬p∨q) （交换律） 1 重言式 (3) ((p∧q)∨(p∧¬q))∧r) (p∧(q∨¬q))∧r （分配律） p∧1∧r （排中律） p∧r （同一律） 可满足式，101和111是成真赋值，000和010等是成假赋值.

基本概念 (1) 文字——命题变项及其否定的总称 (2) 简单析取式——有限个文字构成的析取式 p, ¬q, p∨¬q, p∨q∨r, … (3) 简单合取式——有限个文字构成的合取式 p, ¬q, p∧¬q, p∧q∧r, … (4) 析取范式——由有限个简单合取式组成的析取式 p, ¬p∧q, p∨¬q, (p∧¬q)∨(¬p∧q∧¬r)∨(q∧r) (5) 合取范式——由有限个简单析取式组成的合取式 p, p∨¬q, ¬p∧q, (p∨q∧¬p)∧(p∨¬q∨¬r) (6) 范式——析取范式与合取范式的总称 说明：

定理2.1 (1) 一个简单析取式是重言式当且仅当它同时含有某个命题变项和它的否定式. (2) 一个简单合取式是矛盾式当且仅当它同时含有某个命题变项和它的否定式.

定理2.2 (1) 一个析取范式是矛盾式当且仅当它每个简单合取式都是矛盾式. (2) 一个合取范式是重言式当且仅当它的每个简单析取式都是重言式.

定理2.3（范式存在定理） 任何命题公式都存在与之等值的析取范式与合取范式 公式A的析取(合取)范式-与A等值的析取(合取)范式

求公式A的范式的步骤

(1) 消去A中的→, ↔（若存在） A→B¬A∨B A↔B(¬A∨B)∧(A∨¬B) (2) 否定联结词¬的内移或消去 ¬ ¬A A ¬(A∨B) ¬A∧¬B ¬(A∧B) ¬A∨¬B (3) 使用分配律 A∨(B∧C) (A∨B)∧(A∨C) 求合取范式 A∧(B∨C) (A∧B)∨(A∧C) 求析取范式

公式范式的不足——不惟一

例5 求下列公式的析取范式与合取范式 (1) (p→¬q)∨¬r (2) (p→¬q)→r 解 (1) (p→¬q)∨¬r (¬p∨¬q)∨¬r （消去→） ¬p∨¬q∨¬r （结合律） 最后结果既是析取范式(由3个简单合取式组成的析取式)，又 是合取范式(由一个简单析取式组成的合取式) (2) (p→¬q)→r (¬p∨¬q)→r （消去第一个→） ¬(¬p∨¬q)∨r （消去第二个→） (p∧q)∨r （否定号内移——德摩根律) 析取范式 (p∨r)∧(q∨r) （∨对∧分配律） 合取范式

定义2.4 在含有n个命题变项的简单合取式（简单析取式） 中，若每个命题变项均以文字的形式在其中出现且仅出现 一次，而且第i个文字出现在左起第i位上（1