第二章:命题逻辑等值演算 主要内容： 本章与其他各章的联系 等值式与基本的等值式 等值演算与置换规则 析取范式与合取范式，主析取范式与主合取范式 联结词完备集 本章与其他各章的联系 是第一章的抽象与延伸 是后续各章的先行准备

第一节：等值式

2.1 等值式 若等价式AB是重言式，则称A与B等值，记作AB，并称AB是等值式 几点说明： 定义中，A, B, 均为元语言符号 (pq)  ((pq) (rr)) 中，r为左边公式的哑元. 用真值表可验证两个公式是否等值

2.1 等值式 例子 判断¬¬pp p ¬p ¬¬p ¬¬p  p 1

2.1 等值式 例子 判断 pq  ¬pq p q ¬p pq ¬pq (pq)  (¬pq) 1

2.1 等值式 如果命题变项很多，怎么办？ -- 利用已知的等值式通过代换得到新的等值式 命题：设A是一个命题公式，含有命题变项p1，p2，…，pn，又设A1，A2，…，An是任意的命题公式. 对每个i（i=1，2，…，n），把pi在A中的所有出现都替换成Ai，所得到的新命题公式记作B. 那么，如果A是重言式，则B也是重言式.

2.1 等值式 否定律 幂等律 p  p  p， p  p  p 交换律 双重否定律 ¬¬pp 德摩根律 ¬ (p  q)  ¬ p  ¬q ¬ (p  q)  ¬p  ¬q 幂等律 p  p  p， p  p  p 交换律 p  q  q  p p  q  q  p p  q  q  p

2.1 等值式 结合律 分配律 (p  q)  r  p  (q  r) (p  q)  r  p  (q  r) p  (q  r)  (p  q)  (p  r) p  (q  r)  (p  q)  (p  r)

2.1 等值式 常元律 吸收律 零律: p  1  1， p  0  0 同一律: p  0  p， p  1  p p  (p  q)  p p (p  q)  p

2.1 等值式 蕴涵等值式 p  q  ¬ p  q 等价等值式 p  q (p  q)  (q  p)

2.1 等值式 说明： (1)16组等值模式都可以给出无穷多个同类型的具体的等值式。 (2)证明上述16组等值式的代入实例方法可用真值表法，把改为所得的命题公式为永真式，则成立。

2.1 等值式 等值演算：由已知的等值式推演出另外一些等值式的过程 置换规则：设φ(A)是含公式A的命题公式， φ(B)是用公式B置换了φ(A)中所有A后得到的命题公式，若ＡB ，则φ(A)  φ(B) 说明： 等值演算过程中遵循的重要规则 一个命题公式A，经多次置换，所得到的新公式与原公式等价

2.1 等值式 1.用等值演算验证等值式 试证：p→(q→r) (p  q)→r 证明： p→(q→r)p→(¬q∨r)

2.1 等值式 试证： ¬(p  q)→(¬p∨(¬p∨ q))(¬p∨q) 左边  ¬¬(p  q) ∨ (¬p∨(¬p∨ q)) (p∨ ¬p∨ q)  (q∨ ¬p∨ q)  (¬p∨ q)

2.1 等值式 2. 用等值演算判断公式的类型 证明： ((p∨q)  ¬(¬p (¬q∨¬r)))∨(¬p¬q)∨(¬p  ¬r)为一永真式 证明：原式 ((p∨q) (p∨(q  r)))∨¬(p∨q)∨¬(p∨r)　  ((p∨q) (p∨q) (p∨r))∨¬((p∨q) (p∨r)) ((p∨q) (p∨r))∨¬((p∨q) (p∨r)) 1

2.1 等值式 3．解判定问题 在某次研讨会的中间休息时间，3名与会者根据王教授的口音对他是哪个省市的人判断如下： 甲：王教授不是苏州人，是上海人 乙：王教授不是上海人，是苏州人 丙：王教授既不是上海人，也不是杭州人 听完这3人的判断后，王教授笑着说，你们3人中有一人说得全对，有一人说对了一半，另一人说得全不对。试用逻辑演算分析王教授到底是哪里人。

第二节：析取范式与合取范式

2.2 析取范式和合取范式 文字(literal): 命题变项及其否定 简单析取式:仅由有限个文字构成的析取式 简单合取式:仅由有限个文字构成的合取式 例：设p、q为二个命题变元 p，q，p∨p，q∨q，¬p∨q， ¬q∨ ¬p，p∨q，p∨ ¬q 称为简单析取式 p，q，p∧p，q∧q， ¬p∧q， ¬q∧ ¬p，p∧q，p∧ ¬q 称为简单合取式。

2.2 析取范式和合取范式 定理: 1)一个简单析取式是永真式当且仅当它同时含某个命题变元及它的否定式 2)一个简单合取式是永假式当且仅当它同时含某个命题变元及它的否定式

2.2 析取范式和合取范式 析取范式:由有限个简单合取式构成的析取式 合取范式:由有限个简单析取式构成的合取式 析取范式与合取范式统称为范式 A1 … An, Ai 为简单合取式 (p  q)  (p  r) 合取范式:由有限个简单析取式构成的合取式 A1 … An, Ai 为简单析取式 (p  q)  (p  r) 析取范式与合取范式统称为范式

2.2 析取范式和合取范式 定理： Ai 简单合取式， A1 … An  F 当且仅当 Ai  F，任意Ai Ai 简单析取式， A1 … An  T 当且仅当 Ai  T，任意Ai

2.2 析取范式和合取范式 范式存在定理: 任意命题公式都存在着与之等值的析取范式与合取范式 方法： 步骤一：消去“”、“”联结词 步骤二：消去双重否定符，内移否定符 步骤三：使用分配律

2.2 析取范式和合取范式 范式存在定理: 任意命题公式都存在着与之等值的析取范式与合取范式 方法： 步骤一：消去“”、“”联结词 步骤二：消去双重否定符，内移否定符 步骤三：使用分配律

2.2 析取范式和合取范式 步骤一：利用等值公式：化去“→”、“”联结词 p  q  p  q p ↔ q  (p  q)  (q  p)

2.2 析取范式和合取范式 范式存在定理: 任意命题公式都存在着与之等值的析取范式与合取范式 方法： 步骤一：消去“”、“”联结词 步骤二：消去双重否定符，内移否定符 步骤三：使用分配律

2.2 析取范式和合取范式 消去双重否定符，内移否定符 德摩根律 双重否定律 ¬¬p  p ¬ (p  q)  ¬ p  ¬q

2.2 析取范式和合取范式 范式存在定理: 任意命题公式都存在着与之等值的析取范式与合取范式 方法： 步骤一：消去“”、“”联结词 步骤二：消去双重否定符，内移否定符 步骤三：使用分配律

2.2 析取范式和合取范式 利用“”对“”的分配，将公式化成为析取范式 利用“”对“”的分配，将公式化成为合取范式 p  (q  r)  (p  q)  (p  r) 利用“”对“”的分配，将公式化成为合取范式 p  (q  r)  (p  q)  (p  r)

2.2 析取范式和合取范式 例：求(p  q)  (p  q)的析取范式 化去  ( p  q)  (p  q) “”对“”分配，化为析取范式  ( p  p  q)  (q  p  q) 最简析取范式  p  q 　

2.2 析取范式和合取范式 例：求((p  q)  r)  p的析取范式和合取范式 (一) 求析取范式  ((p   r)  (q   r))  p  p  (p   r)  (q   r)  p  (q   r)

2.2 析取范式和合取范式 (二)求合取范式 原式 ((p  q)  r)  p  ((p  q)  r)  p  (p  p  q)  (p   r)  (p  q)  (p   r)

2.2 析取范式和合取范式 问题： 一个命题公式的析取范式是不是唯一的？ 同一命题公式的析取范式是不是等值的？

2.2 析取范式和合取范式 极小项(极大项):含有n个命题变项的简单合取式 (简单析取式)，并满足 每个命题变元和它的否定式不同时出现，而二者之一必出现且仅出现一次 第i个命题变项或它的否定式出现在从左算起的第i位上(若无角标，则按字典顺序排列) 若有ｎ个命题变项，则有2n个极小项（极大项） 如果我们把不带否定符的命题变项取成1，带否定符的命题变项取成0，那么每一个极小项都对应一个二进制数，因而也对应一个十进制数

2.2 析取范式和合取范式 极小项的编码:对应成真赋值 三个变元p、q、r可构造8个极小项： ¬p∧¬q∧¬r FFF 0 记作 m0 ¬p∧¬q∧r FFT 1 记作 m1 ¬p∧q∧¬r FTF 2 记作 m2 ¬p∧q∧r FTT 3 记作 m3 p∧¬q∧¬r TFF 4 记作 m4 p∧¬q∧r TFT 5 记作 m5 p∧q∧¬r TTF 6 记作 m6 p∧q∧r TTT 7 记作 m7

2.2 析取范式和合取范式 极大项的编码:对应成假赋值 如三个变元 p、q、r，其记法如下： p∨q∨r F F F 0 记作 M0 p∨ q∨ ¬r F F T 1 记作 M1 p∨ ¬q∨r F T F 2 记作 M2 p∨ ¬q∨ ¬r F T T 3 记作 M3 ………… ¬p∨ ¬q∨ ¬r T T T 7 记作 M7

2.2 析取范式和合取范式 定理:设mi和Mi是命题变元p1, p2… pn形成的极小项和极大项，则： (1) mi  mj  F, (i≠j) (2) Mi  Mj  T, (i≠j) (3)  mi  Mi；  Mi  mi

2.2 析取范式和合取范式 定理: 任何命题公式都存在着与其等值的主析取范式和主合取范式，并且是唯一的。 主析取范式(主合取范式)：由n个命题变项构成的析取范式(合取范式)中所有的简单合取式(简单析取式)都是极小项(极大项) 定理: 任何命题公式都存在着与其等值的主析取范式和主合取范式，并且是唯一的。

2.2 析取范式和合取范式 证法一 在真值表中，使命题公式的真值为T的指派所对应的极小项的析取，即为此公式的主析取范式 证：给定一个命题公式A，使其为T的真值指派所对应的极小项为m’1, m’2,…, m’k,这些极小项的析取记为B，为此要证AB，即要证A与B在相同的指派下具有相同的真值。

2.2 析取范式和合取范式 首先对于使A为T的指派显然使B为T 对于使A为F的指派，它对应的极小项(设为m’j )不包含在m’1, m’2,…, m’k 中。所以 m’j为使B为F的指派 所以A  B 得证

2.2 析取范式和合取范式 一个公式的主析取范式即为令此公式的真值为T的指派所对应的极小项的析取。 一个命题公式的真值表是唯一的，因此一个命题公式的主析取范式也是唯一的

2.2 析取范式和合取范式 pqr的真值表 F T p  q  r  m1  m3  m5  m6  m7 p q r

2.2 析取范式和合取范式 证法二：构造法 将命题公式化归为与其等值的析取范式 添变元: 消去重复项 用等值演算方法求命题公式主析取范式的方法 将命题公式化归为与其等值的析取范式 添变元: 消去重复项 Ai  (pj  pj)  (Ai  pj)  (Ai   pj)

2.2 析取范式和合取范式 例：求(p∧(p→q))∨q的主析取范式 解：原式 (p∧¬p)∨(p∧q)∨q ----(1)化为析取范式 ----(2)化简 (p∧q)∨(q∧(p∨¬p)) (p∧q)∨(p∧q)∨(¬p∧q) ----(3)添项 (p∧q)∨(¬p∧q)  m1  m3 ----(4)合并相同最小项

2.2 析取范式和合取范式 主合取范式 任何一个命题公式都可求得它的主合取范式 一个命题公式的主合取范式是唯一的 在真值表中，令命题公式的真值为“F”的指派就对应其主合取范式的一个极大项 构造法

2.2 析取范式和合取范式 例:求p∧(p→q)∨q的主合取范式 解：原式 p∧(p∨q)∨q (p∧p)∨(p∧q)∨q  (p∨q)∧(p∨q)  M0 ∧ M2 p q 上式 F T

2.2 析取范式和合取范式 主析（合）取范式的用途讨论： 求公式的成真与成假赋值 判断公式类型 判断两个命题公式是否等值 应用主析（合）取范式分析和解决实际问题

2.2 析取范式和合取范式 1. 求公式的成真与成假赋值 例：(pq)r  m1m3m5 m6m7 成真赋值为001, 011, 101, 110, 111 成假赋值为000, 010, 100

2.2 析取范式和合取范式 2. 判断公式的类型 设A含n个命题变项 A为重言式  A的主析取范式含2n个极小项  A的主合取范式为1

2.2 析取范式和合取范式 2. 判断公式的类型 例： 用公式的主析取范式判断下述公式的类型： （1）( p q)  q 例： 用公式的主析取范式判断下述公式的类型： （1）( p q)  q （2）p( p q) （3）( p q) r

2.2 析取范式和合取范式 3. 判断两个命题公式是否等值 例： 用主析取范式判两个公式是否等值 ⑴ p(qr) 与 (pq)r 解： p(qr)  m0m1m2m3 m4m5 m7 (pq)r  m0m1m2m3 m4m5 m7 (pq)r  m1m3 m4m5 m7 显见，⑴中的两公式等值，而⑵的不等值.

2.2 析取范式和合取范式 例：某研究所要从3名科研骨干A，B，C中挑选1～2名出国进修，由于工作需要，选派时要满足以下条件： 若A去，则C同去。 若B去，则C不能去。 若C不去，则A或B可以去。 解:设p：派A去；q：派B去；r：派C去。 则(p→r) ∧(q→¬r)∧(¬r →(p∨q))

2.2 析取范式和合取范式 经演算可得： (p→r) ∧(q→¬r)∧(¬r →(p∨q)) m1∨m2∨m5 可知选派方案有三种： C去，A，B都不去。 B去，A，C不去。 A，C去，B不去。

2.2 析取范式和合取范式 主合取范式与主析取范式转换 公式: A = mi1  mi2  …  mis A = mj1  mj2  …  mjt ，t=2n-s A   A  (mj1  mj2  …  mjt )  mj1  mj2  …  mjt  Mj1  Mj2  …  Mjt

2.2 析取范式和合取范式 讨论：具有n个变项的命题公式有多少个不同的主析取范式？

第三节：联结词的完备集

2.3 联结词的完备集 “与非”联结词： 符号“↑” (p↑q)读作：“p与q的否定” (p↑q)¬(p∧q) p q p↑q F T

2.3联结词的完备集 “或非”联结词： 符号：“↓”　 (p↓q)读作：“p或q的否定”　 (p↓q) ¬(p∨q) p q p↓q F T

2.3 联结词的完备集 真值函数F: {0,1}n {0,1} 联结词完备集S: 定理: S ={，，}是联结词完备集 证明：任何一个n（n1）元真值函数都与唯一的一个主析取范式等值，而主析取范式仅含，，

2.3 联结词的完备集 推论: S ={，}是联结词完备集 证明：p  q   (p  q)   ( p   q)

2.3 联结词的完备集 定理: {↑}， {↓}是联结词完备集 证明： 首先，  p   (p  p)  p↑p 其次，p  q   (p  q)   (p↑q)  (p↑q) ↑ (p↑q) p  q  (p↑p) ↑ (q↑q) (p↑q)   (pq)

第二章 习题课 主要内容 等值式与等值演算 基本等值式（16组，24个公式） 主析取范式与主合取范式 联结词完备集

基本要求 深刻理解等值式的概念 牢记基本等值式的名称及它们的内容 熟练地应用基本等值式及置换规则进行等值演算 理解文字、简单析取式、简单合取式、析取范式、合取范式的概念 深刻理解极小项、极大项的概念、名称及下角标与成真、成假赋值的关系 熟练掌握求主范式的方法（等值演算、真值表等） 会用主范式求公式的成真赋值、成假赋值、判断公式的类型、判断两个公式是否等值 会将公式等值地化成指定联结词完备集中的公式 会用命题逻辑的概念及运算解决简单的应用问题

练习1:概念 1. 设A与B为含n个命题变项的公式，判断下列命题是否为真？ (1) AB当且仅当A与B有相同的主析取范式 (2) 若A为重言式，则A的主合取范式为0 (3) 若A为矛盾式，则A的主析取范式为1 (4) 任何公式都能等值地化成{, }中的公式 (5) 任何公式都能等值地化成{, , }中的公式 真 假 假 假 真 说明: (2) 重言式的主合取范式不含任何极大项，为1. (3) 矛盾式的主析取范式不含任何极小项, 为0. (4) {, }不是完备集，如矛盾式不能写成{, }中的公式. (5) {, }是完备集.

练习2：联结词完备集 2．将A = (pq)r改写成下述各联结词集中的公式: (1) {, , } (2) {, } (3) {, } (4) {, } (5) {} (6) {} 解 (1) (pq)r  (pq)r (2) (pq)r  (pq)r (3) (pq)r  (pq)r  ((pq)r)

练习2 解答 (4) (pq)r  ((pq)r)  ((pq)r)  (pp)(qq)(rr) 说明：答案不惟一

练习3：应用题 3. 某公司要从赵、钱、孙、李、周五名新毕业的大学生中选派一些人出国学习. 选派必须满足以下条件： (1) 若赵去，钱也去 (1) 若赵去，钱也去 (2) 李、周两人中至少有一人去 (3) 钱、孙两人中去且仅去一人 (4) 孙、李两人同去或同不去 (5) 若周去，则赵、钱也去 用等值演算法分析该公司如何选派他们出国？

练习3解答 解此类问题的步骤： 1.设简单命题并符号化 2. 用复合命题描述各条件 3. 写出由复合命题组成的合取式 4. 将合取式化成主范式 5. 求成真赋值, 并做出解释和结论

练习3解答 解 1. 设简单命题并符号化 设 p: 派赵去，q: 派钱去，r: 派孙去，s: 派李去，u: 派周去 2. 写出复合命题 (3) 钱、孙两人中去且仅去一人 (qr)(qr) (4) 孙、李两人同去或同不去 (rs)(rs) (5) 若周去，则赵、钱也去 u(pq)

练习3解答 3. 设(1)—(5)构成的合取式为A A = (pq)(su)((qr)(qr)) ((rs)(rs))(u(pq)) 4. 化成析取式 A  (pqrsu)(pqrsu) 结论：由上述析取式可知，A的成真赋值为00110与11001， 派孙、李去（赵、钱、周不去） 派赵、钱、周去（孙、李不去）

作业 5（2） 6（2） 15 27 29