2第二章 命题逻辑等值演算

ห้องสมุดไป่ตู้
方法3，等值演算法
(p q) r
( p ∨ q) r
(蕴涵等值式)
( p ∨ q) ∨ r
(蕴涵等值式)
(p ∧ q) ∨ r
(德摩根律)
p (q r)
p ∨(q ∨ r)
(蕴涵等值式)
p ∨q ∨ r
(结合律)
18
【例2.5】 用等值演算法判断下列公式的类型 (1) (p q) ∧p q (2) (p (p ∨ q)) ∧r (3) p∧ (((p ∨ q) ∧p) q)
( p∨q) (p∧ q ) ( p∨q)∨ (p∧ q )
❖若对多个变元进行代入, 则代入必须同时进行。 11
【定义】由已知的等值式推演出另外一些等值式的 过程为等值演算。
等值演算是布尔代数或逻辑代数的重要组成部分， 但是在等值演算过程中，要不断的用到一条重要的 规则，即置换规则。
【定理 】(置换规则) (replacement) 设Φ(A)是含公 式A的命题公式，Φ(B)是用公式B置换了Φ(A) 中 某些的A后得到的命题公式，若AB，则Φ(A) Φ(B) 。
(p ∨q) ∨ r
(分配律)
(p ∧ q )∨ r
(德摩根律)
(p∨q) r
(蕴涵等值式)
16
例 证明 A∨(A∧B) A∨B 证明 A∨(A∧B)
(A∨A)∧(A∨B) 1∧(A∨B) A∨B
例 证明 (A∧B)∨(A∧C)∨(B∧C)
(A∧B)∨(A∧C)
证明 (A∧B)∨(A∧C)∨(B∧C)
解： p q r p(qr) (p∧q)r (pq)r
000 1
1
0
001 1
1
1
010 1
1
0
011 1
1
1
100 1
1
1
101 1
1
1
110 0
0
0
111 1
1
1
5
区别: 1. 符号“”不是命题联结词而是公式间的关 系符号。A B不表示公式, 即不代表命题, 而表示 公式A和公式B有逻辑等值关系。
第二章 命题逻辑等值演算
1
本章内容 2.1 等值式 2.2 析取范式与合取范式 2.3 联结词的完备集 2.4 可满足性问题与消解法 本章小结
2
§2.1 等值式
【定义 2.1】设A和B是两个命题公式, 若AB为重 言式, 则称公式A和B是等值的公式, 记为AB .
❖ 显然, 当且仅当A和B真值表完全相同时, A和B是等 值的公式。 【例2.1】 证明(pq) (qP) ; p∨p p 。
证 用列真值表法证明:
p q pq qp pq qp
0 01
1
1
1
0 11
0
0
1
1 00
1
1
0
1 11
1
1
1
从真值表可知, 正命题pq和逆否命题q p的对
应项真值完全相同, 所以它们等值。
同理, 逆命题qp和否命题p q等值。
4
【例2.2】判断下列各组公式是否等值： (1) p (q r) 与 (p∧q) r (2) (p q) r 与 (p∧q) r
❖ 注意代入规则和替换规则的区别, 祥见表 2.1。
13
使用对象 代换对象 代换物
表2.1 代入规则 等值式 命题变元 命题公式
代换方式 代换同一命题 的所有出现
代换结果 等值式
置换规则 命题公式 子公式 与代换对象等值 的命题公式 代换子公式 某些出现 与原公式等值
❖ 引入代入规则和置换规则, 我们可将公式变形,
27
【定义 2.3】 (1)由有限个简单合取式构成的析取式称 为析取 (disjunctive)范式。具有形式A1∨A2∨… ∨An (n≥1), 其中Ai (1≤i≤n)都是简单合取式。
23
❖ 根据标准化, 同一真值函数对应的所有命题公式具有 相同的标准形式。
❖ 这样, 根据命题的形式结构就能判断两命题公式是否 等值以及判断公式的类型。
❖ 主范式的思想和平面上的二次曲线标准方程的思想 是类似的。一般形式的二次方程难以知道方程所代 表的曲线形状, 如果将它化为标准方程, 便可知道二 次方程所代表的是圆、椭圆、双曲线或是抛物线。
类似可得 B1∧C3∧D2 p ∧q ∧ r B2∧C1∧D3 0
B2∧C3∧D1 0 B3∧C1∧D2 p ∧q ∧ r (假命题)
B3∧C2∧D1 0
E(p∧q∧r)
22
§2.2 析取范式和合取范式
❖ 命题真假的判定问题总是可解的, 我们已有两种判 定方法: 真值表技术和等值演算法。
(E6) 德摩根律 (A∨B) A∧B
(A∧B) A∨B
(E7) 吸收律 A∨(A∧B) A
A∧(A∨B) A
(E8) 零律 A∨1 1A∧0 0
(E9) 同一律 A∨0 A
A∧1 A
(E10) 排中律 A∨A 1
(E11) 矛盾律 A∧A 0
(E12) 蕴涵等值式 AB A∨B
9
(E13) 等价等值式 AB (AB)∧(BA) (E14) 假言易位 AB BA (E15) 等价否定等值式 AB A B (E16) 归谬论 (AB)∧(A B) A
【例 2.2】证明等值式 AB A∨B
AB (AB)∧(BA)
(AB)∧(A B) A
证明 分别列出它们的真值表，真值表所列值完全
等值 Equivalent 表2.1
(E1) 双重否定律 A A
(E2) 幂等律 A∨A A
A∧A A
(E3) 交换律 A∨B B∨A A∧B B∧A
(E4) 结合律 A∨(B∨C) (A∨B)∨C
A∧(B∧C) (A∧B)∧C
8
(E5) 分配律 A∧(B∨C) (A∧B)∨(A∧C) A∨(B∧C) (A∨B)∧(A∨C)
相同就证明它们等值。
10
【定义】以上的等值式，由于A,B,C可以代表任意 的公式，因而以上各等式都是用元语言符号书写 的，称以上的等值式为等值式模式。
每个等值式模式都给出了无穷多同类型的具体的等 值式，这些具体的等值式称为原来的等值式模式的 代入实例。（代入规则）
例如：蕴涵等值式AB A∨B中 取 A=p，B＝q 可得等值式pq p∨q 取 A= p∨q，B= p∧ q ，则
则 甲的判断全对： B1= A1= p ∧q 甲的判断对一半：B2=( p ∧q)∨(p ∧q) 甲的判断全错： B3=p ∧ q
乙的判断全对： C1= A2= p ∧ q 乙的判断对一半：C2= (p ∧q)∨( p ∧q) 乙的判断全错： C3= p∧ q
丙的判断全对： D1= A3= q ∧ r
❖ 此外, 正是表达式的不唯一, 才使得命题演算在简化 电子线路和程序设计中成为必不可少的武器。
15
等值演算的用途：
验证等值式、判断公式的类型、解决工作和生活中 的判定问题。
【例2.3 】 证明等值式
(p∨q) r (p r)∧(q r)
证明： (p r)∧(q r)
(p ∨ r)∧( q ∨r) (蕴涵等值式)
(2)一个简单合取式为矛盾式当且仅当它同时包 含某个命题变项及其否定式。
证明 我们只证明(1), (2)的证明方法同(1), 留给读 者自证。
充分性: 命题变元p, p∨p是重言式。因此, 若有p∨p在简单析取式中出现, 则这个简单析取 式必为重言式。
26
必要性: 假设一个简单析取式为重言式, 但式中 不同时包含任一命题变元及其否定, 那么, 我们对该析取式中出现在后面的命题变元指派 值1, 而对不出现在后面的命题变元指派值0, 则整个析取式取值必为0, 这与假设矛盾。
解: (2) (p (p ∨ q)) ∧r ( p ∨ p ∨ q) ∧ r (p ∧ p ∧ q) ∧ r 0∧r 0
(1) (p q) ∧p q 1 (3) p∧ (((p ∨ q) ∧p) q) p
19
【例2.6】在某次研讨会的中间休息时间，3名与会者 根据王教授的口音对他是哪个省市的人进行了判断: 甲说王教授不是苏州人，是上海人。 乙说王教授不是上海人，是苏州人。 丙说王教授既不是上海人，也不是杭州人。
❖ 命题逻辑所研究的思维规律, 很多是以等值式给出。
❖ 我们知道可以用真值表判断任何两个公式是否等值, 但是这样做很麻烦。因此人们验证了一组基本的又
是重要的等值式。
7
下面给出的等值式, 它们的正确性均可由真值表验证。 这些等值式也就是通常所说的布尔代数或逻辑代数 的主要组成部分。
以它们为基础进行公式之间的演算，判断公式之间 是否等值。
❖ 范式在线路设计方面、自动机器理论和人工智能方 面也有极其重要的作用。
24
【定义2.2 】命题变项及其否定统称为文字(literal). 仅由有限个文字构成的析取式称为简单析取式。 仅由有限个文字构成的合取式称为简单合取式。
例： p、p ∧ q、 p ∧q ∧ p等都是简单合取式。 p、p∨q、p∨q∨p、 q∨q等都是简单析取式 单个的文字既是简单合取式，又是简单析取式。
(A∧B)∨(A∧C)∨((A∨A)∧(B∧C))
(A∧B)∨(A∧C)∨(A∧B∧C)∨(A∧C∧B)
(A∧B)∨(A∧B∧C)∨(A∧C)∨(A∧C∧B)
(A∧B)∨(A∧C)
E7(吸收律) 17
【例2.4】 证明等值式 (p q) r p (q r)
证明： 方法1，真值表法
方法2，观察法，对公式给予赋值
❖ 由所学知识可知, 含有n个命题变元的公式有2n组不 同的真值指派, 对于每个指派有真、假两种可能,即 共有22 n个不同的真值函数。
❖ 每种真值函数都可以用无穷多种命题公式表示。很 多从形式上看不尽相同的命题公式, 实质上是等值 的。为了解决上述问题, 我们引入范式的概念, 把命 题公式规范(标准)化。