北京大学离散数学教材 2

2023年12月13日发(作者：初中数学试卷上的单位)

Discrete Mathematics©2002 Liu Aimin (刘爱民)命题逻辑等值演算学习目的2本章主要涉及命题演算中两个重要内容之一：等值演算。首先理解命题公式等值的含义，掌握构造真值表和不构造真值表两种方法证明等值式，熟练应用于命题公式的化简和范式表示基本内容z 命题公式等值关系及其证明z 联结词的全功能集z 命题公式的范式表示2-1Discrete Mathematics©2002 Liu Aimin (刘爱民)等值关系基本概念等值的两种定义：z 如果两个逻辑形式对其中的命题变项的任何取值，都具有相同的值，则称它们是相等的。z A、B等值是指等价式A↔B为重言式，记为A⇔B。可直接构造真值表证明两个命题形式的等值。等值演算根据已知的等值式，可以推演出另外许多的等值式，这种推演过程称为等值演算。这些已知等值式通常是经过证明了的常用等值式，其中许多是布尔代数或逻辑代数的主要组成部分，称为等值关系模式：(1) 双重否定律： A ⇔ ¬¬A(2) 等幂律：

(3) 交换律：

(2a) A ⇔ A∧A(2b) A ⇔ A∨A(3a) A∧B ⇔ B∧A2-2Discrete Mathematics©2002 Liu Aimin (刘爱民)

(4) 结合律：

(5) 分配律：

(7) 吸收律：

(8) 零律：

(9) 同一律：

(10)排中律：

(11)矛盾式：

(3b) A∨B ⇔ B∨A(3c) A∨B ⇔ B∨A(3d) A↔B ⇔ B↔A(4a) (A∧B)∧C ⇔ A∧(B∧C)(4b) (A∨B)∨C ⇔ A∨(B∨C)(4c) (A∨B) ∨C ⇔ A∨ (B∨C)(4d) (A↔B) ↔C ⇔ A↔ (B↔C)(5a) A∨(B∧C) ⇔ (A∨B)∧(A∨C)(5b) A∧(B∨C) ⇔ (A∧B)∨(A∧C)(5c) A∧(B∨C) ⇔ (A∧B) ∨ (A∧C)(6b) ¬(A∨B)⇔ ¬B∧¬A(7a) A∨(A∧B)⇔A(7b) A∧(A∨B)⇔A(7c) A∨(¬A∧B)⇔A∨B(7d) A∧(¬A∨B)⇔A∧B(8a) A∨1 ⇔ 1(8b) A∧0 ⇔ 0(9a) A∨0 ⇔ A(9b) A∨0 ⇔ AA∨¬A ⇔ 1A∧¬A ⇔ 0(6) 德•摩根律：(6a) ¬(A∧B) ⇔ ¬B∨¬A (7e) (A∧B) ∨ (¬A∧C) ∨ (B∧C) ⇔ (A∧B) ∨ (¬A∧C)(12)蕴涵等值式：A→B ⇔ ¬A∨B2-3Discrete Mathematics©2002 Liu Aimin (刘爱民)(13)等价等值式：(13a) A↔B ⇔ (A→B) ∧ (B→A) (13b) A↔B ⇔ ¬ (A∨B)(14)假言易位： A→B ⇔ ¬B→¬A(15)等价否定等值式： A↔B ⇔ ¬A↔¬B(16)否定等价等值式：¬ (A↔B) ⇔ ¬A↔B ⇔ A↔¬B(17)归谬律： (A→B) ∧ (A→¬B) ⇔ ¬A(18)输出律：(A∧B) → C ⇔ A → (B → C)(19) A ∨¬A ⇔ 0(20) A ∨ B ⇔ (A ∧ ¬B) ∨ (¬A ∧ B)通常在等值演算的过程中，还可以用到一些规则或定理：z 置换规则设Φ是含有公式A的命题形式，Ψ是用公式B置换Φ中的公式A(不一定是每一处)而得到的命题形式，如果A ⇔ B，则Φ ⇔ Ψ。z 香农(Shannon)定理：命题形式A仅含有命题变项p1, p2,…, pn和命题常项0,1及联结词¬，∧，∨，表示成A(p1, p2,…, pn,0,1,∧,∨)，则A的非可以通过对所有命题变项取非，并将常量1换成0，0换成1，联结词∧换成∨，∨换成∧而得到：¬A(p1, p2,…, pn,0,1,∧,∨)⇔A(¬p1, ¬p2,…,¬pn,1,0,∨, ∧)2-4Discrete Mathematics©2002 Liu Aimin (刘爱民)z 对偶定理：对偶式：公式A仅含有联结词¬，∧，∨，则将A中的∧，∨，0，1分别换以∨，∧，1，0后得到的公式为A的对偶式A*。即：A*(p1, p2,…, pn,0,1,∧,∨) = A(p1, p2,…, pn,0,1, ∧,∨) 香农定理的对偶式表示：¬A(p1, p2,…, pn) ⇔ A*(¬p1, ¬p2,…, ¬pn)对偶定理：如果A ⇔ B，且A,B仅含有联结词¬，∧，∨，则A*⇔ B*。注意 两个定理的A、B、F仅含有联结词¬，∧，∨。z 展开定理设命题形式A含有命题变项p1, p2, …, pn，则A(p1,p2,…,pi,…,pn) ⇔(pi∧B(p1,p2,…,1,…,pn)) ∨(¬pi∧B(p1,p2,…,0,…,pn))；(1)A(p1,p2,…,pi,…,pn)⇔(pi∨B(p1,p2,…,0,…,pn)) ∧(¬pi∨B(p1,p2,…,1,…,pn))。(2)逻辑等值演算不仅仅停留在符号级，总要用来解决实际问题，如简化语句，确定一些命题的真值等等，可以首先符号化命题，然后由已知条件列出这些命2-5Discrete Mathematics©2002 Liu Aimin (刘爱民)题应该满足的方程组，从而达到要求。化简语句：“情况并非如此：如果他不来，那么我也不去” 设p:他来，q：我去；上述语句符号化为 ¬ (¬p → ¬q) 等值化简为¬ p ∧ q 化简后语句为：“我去了，而他每来”。小李或小张是先进工作者；如果小李是先进工作者，你是会知道的；如果小张是先进工作者，小赵也是；你不知道小李是先进工作者。问：谁是先进工作者？ 设p：小李是先进工作者；。 r：你知道小李是先进工作者； 则上述语句符号化为 (p∨q) ∧ (p→r) ∧ (q→s) ∧¬r ⇔ 1 等值化简为¬p ∧ q ∧ s ∧ ¬r ⇔ 1 显然p=0, q=1, s=1, r=0满足此等值式，即小张和小赵是先进工作者。q：小张是先进工作者；s：小赵是先进工作者。2-6Discrete Mathematics©2002 Liu Aimin (刘爱民)联结词的全功能集从等值式模式可以发现，常用的六种联结词不是相互独立的，其中有些联结词的逻辑功能可以用其它联结词代替，如:A→B ⇔ ¬A∨B，A↔B ⇔ (A→B) ∧ (B→A) ⇔ (¬A∨B) ∧ (¬B∨A)，A∨B ⇔ (A∧¬B) ∨ (¬A∧B)。将联结词组成一个集合，如果一个联结词可由集合中的其它联结词定义，则称此联结词为冗余联结词，否则称为独立连接词。一个联结词集合称作是全功能集是指任意真值函数都可以用仅含有此集合中联结词的命题形式表示。如果一个全功能联结词集合中不含有冗余联结词，则称其为极小全功能集。z {¬, ∧, ∨}是全功能集。z 如果一个全功能集S1中的所有联结词都可由一个联结词集合S2定义，则S2也是全功能集。要证明一个联结词集合是全功能集比较简单，只要写出各联结词的适当等值式即可。要证明一个联结词集合是极小全功能集，要证明它是全功能集，还要证明其中的每个联结词都不能由其它联结词定义。证明一个联结词集合是极小全功能集比证明其不是2-7Discrete Mathematics©2002 Liu Aimin (刘爱民)极小全功能集困难得多。可以证明 {¬, ∧}、{¬, →}是极小全功能集。“命题p与q的否定”称作p, q的与非式，记作p↑q，符号↑称为与非联结词。p↑q ⇔ ¬(p∧q)，从而p↑q为真当且仅当p, q不同时为真。“命题p或q的否定”称作p, q的或非式，记作p↓q，符号↓称作或非联结词。p↓q ⇔ ¬(p∨q)，从而p↓q为真当且仅当p, q同时为假。z {↑}, {↓}都是极小全功能集。{↑}, {↓}都是极小全功能集，这不仅在理论上而且在实践上都有着重要的意义。例如，在数字逻辑电路设计中，只要选择一个基本的单元电路——与非门或或非门就可以设计出满足任何要求的逻辑电路。逻辑电路中用得较多的就是与非门。2-8Discrete Mathematics©2002 Liu Aimin (刘爱民)范式我们知道，任何一个n元真值函数，其具体的逻辑命题形式是无穷多的，而这些命题形式实质上却是等值的。这里介绍一种方法，将公式都等值演算成某种标准形式，从而可以通过这些标准形式进行比较。简单合取式和简单析取式命题变项及其否定统称为文字(literal)。p, ¬p, q等都是文字，但¬¬p不是文字仅由有限个文字构成的合取式，称为简单合取式；仅由有限个文字构成的析取式，称为简单析取式。p∧q, p∧q∧¬p, p∧q∧r∧s等都是简单合取式，p∨q, p∨¬q∨r,p∨p∨r等都是简单析取式。单个文字既可看作是简单合取式，也可看作是简单合取式。z 一个简单合取式是矛盾式，当且仅当其含有一个文字及其否定。z 一个简单合取式是重言式，当且仅当其含有一个文字及其否定。2-9Discrete Mathematics©2002 Liu Aimin (刘爱民)析取范式和合取范式

仅由有限个简单析取式的合取构成的命题形式，称为合取范式；仅由有限个简单合取式的析取构成的命题形式，称为析取范式。z 一个析取范式是矛盾式，当且仅当它的每个简单合取式都是矛盾式。z 一个合取范式是重言式，当且仅当它的每个简单析取式都是重言式。任何一个命题形式都可以等值演算成合取范式和析取范式，具体步骤如下：z 任何命题形式化为由¬, ∧, ∨定义的形式。z 简化双重否定号，并利用香农定理将所有¬写到文字里；z 利用分配律，将A最终变成合取范式和析取范式。通过等值演算将 ((p∨q)→r)→p化成合取范式和析取范式。 ((p∨q)→r) → p ⇔ ¬(¬(p∨q)∨r) ∨ p ⇔ (p∧¬r) ∨ (q∧¬r ) ∨ p ⇔ p ∨ (q∧¬r) ⇔ (p∨q) ∧ (p∨¬r)。(析取范式)(析取范式)(合取范式)一个命题形式的析取范式不是唯一的，同样，合取2-10Discrete Mathematics©2002 Liu Aimin (刘爱民)范式也不是唯一的。不能将析取范式和合取范式作为标准形式。主析取范式和主合取范式在含有n个命题变项的简单合取式中，每个命题变项作为文字出现且仅出现一次，则称此简单合取式为n个命题变项的极小项(minterm)。在极小项中，不允许一个文字及其否定式同时出现，也不允许一个文字出现多次。n个命题变项共可构成2n个不同的极小项。极小项的主要性质：z 每个极小项的成真赋值有且仅有一个；z 两个不同的极小项的合取构成的命题形式为矛盾式；z 所有极小项的析取构成的命题形式为重言式。为了书写方便，通常用mi表示第i个极小项，其中下标i的规定如下：将极小项的命题变项按照一定次序排列，下标i化为二进制后恰好等于该极小项的成真赋值。这样，每个mi与其成真赋值之间就建立了一一对应的关系。2-11Discrete Mathematics©2002 Liu Aimin (刘爱民)极小项可以用卡诺图表示：A01A0B0110B0A0012A0CB01D9141001C11208卡诺图的构成遵循以下规律：(1) 含有n个命题变项，若n是偶数，则斜线左右命题变项数目相同；若n是奇数，斜线左边命题变项的数目多一个；按照排列顺序，依次从外到里，从斜线左边到右边；(2) 命题变项的赋值，位于最外层的总是从上往下、从左到右依次为0, 1；位于里层的，则按照其相邻外层的相邻两个赋值0, 1，从上往下、从左到右依次扩展为0, 1, 1, 0。一个n元真值函数，仅由其n个命题变项的极小项构成的析取范式，称为主析取范式。2-12Discrete Mathematics©2002 Liu Aimin (刘爱民)主析取范式有如下主要性质：z 若mi是主析取范式A的一个极小项，则mi的成真赋值一定是A的成真赋值；z A, B是由n个相同命题变项构成的主析取范式，则A∨B包含A和B的所有极小项；A∧B将包含A和B的所有公共极小项；z ¬A包含主析取范式A的所有极小项之外的其余极小项。z 命题逻辑中任一命题形式都存在着与之等值的主析取范式。z 任一命题形式的主析取范式是唯一的。求((p∨q)→r)→p主析取范式并进行化简。 (p∨q→r) → p ⇔ (p∧¬r) ∨ (q∧¬r ) ∨ p。右式中的析取范式共有三项，将每项文字共同拥有的网格标记如下(如果已经标记，则不必重记)：将p∧¬r, q∧¬r, p，最终获得的极小项图中标“1”的部分(卡诺图方法)，即原式 ⇔ m2 ∨ m4 ∨ m5 ∨ m6 ∨ m7q∧¬rp0qr0101pqrq∧¬rpqrp11pqr1p11101p∧¬r2-13Discrete Mathematics©2002 Liu Aimin (刘爱民)在含有n个命题变项的简单析取式中，每个命题变项作为文字出现且仅出现一次，则称此简单合取式为n个命题变项的极大项。n个命题变项共可构成2n个不同的极大项，并且有类似于极小项的三个主要性质：z 每个极大项的成假赋值有且仅有一个；z 两个不同的极大项的析取构成的命题形式为重言式；z 所有极大项的合取构成的命题形式为矛盾式。用Mi表示第i个极大项，下标i的规定如下：极大项的命题变项按照一定次序排列，下标i化为二进制后恰好等于该极大项的成假赋值。这样，每个Mi与其成假赋值之间就建立了一一对应的关系。n个命题变项构成的极小项mi和极大项Mi之间存在以下关系： Mi

⇔ ¬mi，mi

⇔ ¬Mi。一个n元真值函数，仅由其n个命题变项的极大项构成的析取范式，称为主合取范式。主合取范式也有类似于主析取范式的三个性质、存在定理以及唯一性定理等等，这里不再一一给出。主析取范式和主合取范式是相通的。例主析取范式m2 ∨ m4 ∨ m5 ∨ m6 ∨ m7的主合取范式2-14Discrete Mathematics©2002 Liu Aimin (刘爱民) m2 ∨ m4 ∨ m5 ∨ m6 ∨ m7 ⇔ ¬¬(m2

∨ m4 ∨ m5 ∨ m6 ∨ m7)⇔ ¬(m0

∨ m1

∨ m3)⇔ ¬m0 ∧ ¬m1 ∧ ¬m3⇔ M0 ∧ M1 ∧ M3。一个命题形式的主析取范式所不包含的极小项的标号正是其主合取范式所包含的极大项的标号。(应用主析取范式的性质)2-15Discrete Mathematics©2002 Liu Aimin (刘爱民)习题二一 设A, B, C为任意的命题形式，已知下面条件，能否得到A ⇔ B ?1) A ∨ C ⇔ B ∨ C 2) A ∧ C ⇔ B ∧ C 3) ¬A ⇔ ¬B二 用等值演算法：证明下列等值式：(1) p→(q→r) ⇔ q → (p → r)(2) ¬(p ↔ q) ⇔ ((p∨q)∧¬(p∧q))判定命题形式类型：(3) (p↔q)→¬((p∧¬p)∨(¬p∧q))

(4) ¬(q∨¬((¬p∨q)∧p))(5) ((p→q)∧(¬q→p)) ↔p三 找出下式的等值的尽可能简单的由{¬,∨}和{¬,∧}生成的公式:(1) p∨(¬q ∧ (r→p)) (2) p → (q → p)四 分别通过求主析取范式和主合取范式判断下列各组命题是否等值：(1) (a) (p∧q)∨(¬p∧q∧r) (b) (p∨(q∧r))∧(q∨(¬p∧r)(2) (a) p→(q→r) (b) q→(p→r)五 先等值演算,再用对偶定理得到新的等值式。(1) ¬ (¬p∨¬q)∨ ¬ (¬p∨q) ⇔p (2) q ∨ ¬((¬p∨q) ∧p) ⇔12-16