Download presentation
Presentation is loading. Please wait.
1
等值式与基本的等值式 等值演算与置换规则 析取范式与合取范式，主析取范式与主合取范式 联结词完备集 可满足性问题与消解法
第2章 命题逻辑等值演算 等值式与基本的等值式 等值演算与置换规则 析取范式与合取范式，主析取范式与主合取范式 联结词完备集 可满足性问题与消解法
2
2.1 等值式 等值式：公式A，B的等价式A↔B为永真式 符号：ＡＢ，也称A逻辑恒等于B
3
2.1 等值式 例子 判断¬¬pp p ¬p ¬¬p ¬¬p p F T
4
2.1 等值式 例子 判断 pq ¬pq p q ¬p pq ¬pq pq ¬pq F T
5
2.1 等值式 否定律 幂等律 p p p， p p p 交换律 双重否定律 ¬¬pp 德摩根律
¬ (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
6
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)
7
2.1 等值式 吸收律 常元律 p (p q) p p (p q) p
零律: p T T， p F F 同一律: p F p， p T p 排中律: p ¬ p T 矛盾律: p ¬ p F
8
2.1 等值式 蕴含等值式 p q ¬ p q 等价等值式 p q (p q) (q p)
9
2.1 等值式 说明： (1)16组等值模式都可以给出无穷多个同类型的具体的等值式。
(2)证明上述16组等值式的代入实例方法可用真值表法，把改为所得的命题公式为永真式，则成立。
10
2.1 等值式 置换规则：设φ(A)是含公式A的命题公式， φ(B)是用公式B置换了φ(A)中所有A后得到的命题公式，若ＡB ，则φ(A) φ(B) 。 说明： 等值演算过程中遵循的重要规则。 一个命题公式A，经多次置换，所得到的新公式与原公式等价。 称由已知的等值式推演出另外一些等值式的过程为等值演算。
11
2.1 等值式 1.试证：p→(q→r) (p q)→r 证明： p→(q→r)p→(¬q∨r) p→(¬q∨r)¬p∨¬q∨r
12
2.1 等值式 2 试证： ¬(p q)→(¬p∨(¬p∨ q))(¬p∨q) 左边
(p∨ ¬p∨ q) (q∨ ¬p∨ q) (¬p∨ q)
13
2.1 等值式 3. 证明： ((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)) Ｔ P19 例2.3 从左面演算
14
2.2 析取范式和合取范式 文字(literal): 命题变元及其否定 简单析取式:仅由有限个文字构成的析取式
简单合取式:仅由有限个文字构成的合取式 例：设p、q为二个命题变元 p，q，p∨p，q∨q，¬p∨q， ¬q∨ ¬p，p∨q，p∨ ¬q 称为简单析取式 q，p∧p，q∧q， ¬p∧q， ¬q∧ ¬p，p∧q，p∧ ¬q 称为简单合取式。
15
2.2 析取范式和合取范式 定理: 1)一个简单析取式是永真式当且仅当它同时含某个命题变元及它的否定式 证明？
2)一个简单合取式是永假式当且仅当它同时含某个命题变元及它的否定式
16
2.2 析取范式和合取范式 析取范式:由有限个简单合取式构成的析取式 合取范式:由有限个简单析取式构成的合取式 析取范式与合取范式统称为范式
A1 … An, Ai 为合取式 (p q) (p r) 合取范式:由有限个简单析取式构成的合取式 A1 … An, Ai 为合取式 (p q) (p r) 析取范式与合取范式统称为范式
18
2.2 析取范式和合取范式 定理： 设Ai 为简单合取式，析取范式A1 … An F 当且仅当 Ai F，任意Ai
设Ai 为简单析取式， 合取范式A1 … An T 当且仅当 Ai T，任意Ai
19
2.2 析取范式和合取范式 范式存在定理: 任意命题公式都存在着与之等值的析取范式与合取范式 方法： 步骤一：消去“”、“”联结词
步骤二：消去双重否定符，内移否定符 步骤三：使用分配律
20
2.2 析取范式和合取范式 范式存在定理: 任意命题公式都存在着与之等值的析取范式与合取范式 方法： 步骤一：消去“”、“”联结词
步骤二：消去双重否定符，内移否定符 步骤三：使用分配律
21
2.2 析取范式和合取范式 步骤一：利用等值公式：化去“→”、“”联结词 p q p q
p ↔ q (p q) (q p)
22
2.2 析取范式和合取范式 范式存在定理: 任意命题公式都存在着与之等值的析取范式与合取范式 方法： 步骤一：消去“”、“”联结词
步骤二：消去双重否定符，内移否定符 步骤三：使用分配律
23
2.2 析取范式和合取范式 消去双重否定符，内移否定符 德摩根律 双重否定律 ¬¬p p ¬ (p q) ¬ p ¬q
24
2.2 析取范式和合取范式 范式存在定理: 任意命题公式都存在着与之等值的析取范式与合取范式 方法： 步骤一：消去“”、“”联结词
步骤二：消去双重否定符，内移否定符 步骤三：使用分配律
25
2.2 析取范式和合取范式 利用“”对“”的分配，将公式化成为析取范式 p (q r) (p q) (p r)
26
2.2 析取范式和合取范式 例：求(p q) (p q)的析取范式 化去 ( p q) (p q)
“”对“”分配，化为析取范式 ( p p q) (q p q) 最简析取范式 p q 那么如何获得合取范式呢？
27
2.2 析取范式和合取范式 例：求((p q) r) p的合取范式和析取范式 (一) 求析取范式
((p r) (q r)) p p (p r) (q r) p (q r)
28
2.2 析取范式和合取范式 (二)求合取范式 原式 ((p q) r) p ((p q) r) p
(p p q) (p r) (p q) (p r)
29
2.2 析取范式和合取范式 讨论： 一个命题公式的析取范式不是唯一的，但同一命题公式的析取范式一定是等值的 练习 P38 5(2) 6(2)
30
2.2 析取范式和合取范式 极小项(极大项):含有n个命题变元的简单合取式 (简单析取式)并满足
每个命题变元和它的否定式不同时出现，而二者之一必出现且仅出现一次 第i个命题变元或它的否定式出现在从左算起的第i位上(若无角标则按字典顺序排列) 若有ｎ个命题变元，则有2n个极小项（极大项）
31
2.2 析取范式和合取范式 极小项的编码:对应成真赋值 三个变元p、q、r可构造8个极小项： ¬p∧¬q∧¬r FFF 0 记作 m0
¬p∧¬q∧r FFT 记作 m1 ¬p∧q∧¬r FTF 记作 m2 ¬p∧q∧r FTT 记作 m3 p∧¬q∧¬r TFF 记作 m4 p∧¬q∧r TFT 记作 m5 p∧q∧¬r TTF 记作 m6 p∧q∧r TTT 记作 m7
32
2.2 析取范式和合取范式 极大项的编码:对应成假赋值 如三个变元 p、q、r，其记法如下： p∨q∨r F F F 0 记作 M0
p∨ q∨ ¬r F F T 记作 M1 p∨ ¬q∨r F T F 记作 M2 p∨ ¬q∨ ¬r F T T 记作 M3 ………… ¬p∨ ¬q∨ ¬r T T T 记作 M7
33
2.2 析取范式和合取范式 定理:设mi和Mi是命题变元p1, p2… pn形成的极小项和极大项，则：
(1) mi mj F, (i≠j) (2) Mi Mj T, (i≠j) (3) mi T, (i =0,1,…,2n-1) (4) Mi F, (i =0,1,…,2n-1) (5) mi Mi； Mi mi
34
2.2 析取范式和合取范式 定理: 任何命题公式都存在着与其等值的主析取范式和主合取范式，并且是唯一的。
主析取范式(主合取范式)：由n个命题变元构成的析取范式(合取范式)中所有的简单合取式(简单析取式)都是极小项(极大项) 定理: 任何命题公式都存在着与其等值的主析取范式和主合取范式，并且是唯一的。
35
2.2 析取范式和合取范式 证法一 在真值表中，使命题公式的真值为T的指派所对应的极小项的析取，即为此公式的主析取范式 证：给定一个命题公式A，使其为T的真值指派所对应的极小项为m’1, m’2,…, m’k,这些极小项的析取记为B，为此要证AB，即要证A与B在相同的指派下具有相同的真值。
36
2.2 析取范式和合取范式 首先对于使A为T的指派显然使B为T
对于使A为F的指派，它对应的极小项(设为m’j )不包含在m’1, m’2,…, m’k 中。所以 m’j为使B为F的指派 所以A B 得证
37
2.2 析取范式和合取范式 一个公式的主析取范式即为令此公式的真值为T的指派所对应的极小项的析取。
一个命题公式的真值表是唯一的，因此一个命题公式的主析取范式也是唯一的
38
2.2 析取范式和合取范式 pqr的真值表 F T p q r m1 m3 m5 m6 m7 p q r
39
2.2 析取范式和合取范式 证法二：构造法 将命题公式化归为与其等值的析取范式 添变元: 消去重复项
用等值演算方法求命题公式主析取范式的方法 将命题公式化归为与其等值的析取范式 添变元: 消去重复项 Ai (pj pj) (Ai pj) (Ai pj)
40
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) ----(4)合并相同最小项
41
2.2 析取范式和合取范式 主析取范式的用途讨论： 求公式的成真与成假赋值 判断公式类型 判断两个命题公式是否等值
应用主析取范式分析和解决实际问题
42
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))
43
2.2 析取范式和合取范式 经演算可得： (p→r) ∧(q→¬r)∧(¬r →(p∨q)) m1∨m2∨m5 可知选派方案有三种：
C去，A，B都不去。 B去，A，C不去。 A，C去，B不去。
44
2.2 析取范式和合取范式 主合取范式 任何一个命题公式都可求得它的主合取范式 一个命题公式的主合取范式是唯一的
在真值表中，令命题公式的真值为“F”的指派就对应其主合取范式的一个极大项
45
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
46
2.2 析取范式和合取范式 主合取范式与主析取范式转换 公式: A = mi1 mi2 … mis
A = mj1 mj2 … mjt ，t=2n-s A A (mj1 mj2 … mjt ) mj1 mj2 … mjt Mj1 Mj2 … Mjt
47
2.2 析取范式和合取范式 讨论：具有n个变元的命题公式有多少个不同的主析取范式？
对于含有ｎ个变元的命题公式，必定可写出22n个主析取范式(包括F)。 同理，含有ｎ个变元的命题公式，也可写出22n个主合取范式(包括T)。 练习8 (3), 11(3)
49
2.3 联结词的完备集 排斥或(异或) 符号：“⊕”( ) p q p⊕q F T 性质： p⊕q (¬pΛq)∨(¬qΛp)
(p⊕q)⊕rp⊕(q⊕r)(可结合的)
50
2.3 联结词的完备集 “与非”联结词： 符号“↑” (p↑q)读作：“p与q的否定” (p↑q)¬(p∧q) p q p↑q F T
51
2.3联结词的完备集 “或非”联结词： (a)符号：“↓” (b)(p↓q) ¬(p∨q) p q p↓q F T
52
2.3 联结词的完备集 真值函数F: {0,1}n {0,1} 联结词完备集S: 定理: S ={，，}是联接词完备集
证明：任何一个n（n1）元真值函数都与唯一的一个主析取范式等值，而主析取范式仅含，，
53
2.3 联结词的完备集 推论: S ={，}是联接词完备集 证明：p q (p q) ( p q)
54
2.3 联结词的完备集 定理: {↑}， {↓}是联接词完备集 证明： 首先， p (p p) p↑p
其次，p q (p q) (p↑q) (p↑q) ↑ (p↑q) (p↑q) (pq)
55
2.4 消解法 引入消解法！ 可满足性问题： 解决方法 用于证明A是否永真 用于验证逻辑蕴涵 真值表 主析取范式 主合取范式 缺点：计算量大
A1…Ak B 永真 当且仅当 A1…Ak B 永假 解决方法 真值表 主析取范式 主合取范式 缺点：计算量大 引入消解法！
56
2.4 消解法 文字l的补： 消解式： C1 , C2是简单析取式，C1= C′1 l, C2= C′2 lc
lc=p，如果l =p lc=p，如果l = p 消解式： C1 , C2是简单析取式，C1= C′1 l, C2= C′2 lc Res(C1,C2)= C′1 C′2 定理：C1 C2 ⊨ Res(C1,C2) 消解式是原公式的逻辑推论 讨论！是简单析取式
57
2.4 消解法 定理： C1 C2和Res(C1,C2)可满足性相同 证明：C1= C′1 l, C2= C′2 lc
如果C1 C2可满足，则存在v，v(Ci)=T 假设v(l)=T，则v(C′2)=T。 如果Res(C1,C2)可满足，则存在v 存在l’在C′1使得v(l’)=T, v可以扩展为 v(p)=F 如果p=l v(p)=T 如果p=lc v对C1 C2赋值为T v(C′1 C′2)=T
58
2.4 消解法 C1 C2和Res(C1,C2)不等值 例：C1=pqr, C2=pr Res(C1,C2) = pq
v=FTT满足Res(C1,C2) 但不满足C1 C2
59
2.4 消解法 消解推导：S=C1 … Cn和C 符号：{C1,…,Cn} ⊢ C
存在公式序列A1, A2,…,Ak，对每个i(i=1,…,k), Ai是某个Cj或者 Ai是有序列中前面的公式应用消解得到 Ak=C 称A1,…,Ak是由S到C的推导 如果C 为空子句□，则称此序列是S的一个否证
60
2.4 消解法 消解可靠性：如果合取范式S有否证，则S是不可满足 证明：每次使用消解，都保持可满足性。如果消解结果不可满足，则S必不可满足。
61
2.4 消解法 消解算法（分层饱和法） 输入：合式公式A 输出：yes (A可满足)，no (A不可满足) 求A的合取范式S.
令i=1, S(0)=S. 若S(i)包含空子句，则S不可满足，算法终止. i=i+1. 构造S(i)={Res(C1,C2) | C1(S(0) ⋃… ⋃ S(i-1))且C2 S(i-1)}. 若S(i) S(0) ⋃ … ⋃ S(i-1)则S是可满足的，算法终止. 转3
62
2.4 消解法 书P37页例题2.14 A=(pq) (pq) (q) 循环1 开始， S(0) =Φ
S(1) = {pq, pq, q} S(2) =Φ 通过对S(0) 、S(1) ， S(1) 进行消解得到 S(2) = {q, p, p} 循环2开始， S(0) = {pq, pq, q} S(1)={q, p, p} 得到λ，算法终止
63
2.4 消解法 例2：S={pq, pq, pq, pq} p q p q q p q q p p
□
65
2.4 消解法 引理1：如果合取范式S含有文字l，S’为
再删除剩下的简单析取式中lc 则S和S’可满足性相同 证明： 如果v为满足S的赋值，S含有文字l，v(l)=T，对任意S’中C’，必有v(S’)=T。 如果v为满足S’的赋值，则可以扩展为满足S的赋值（验证）！
66
2.4 消解法 消解完全性：如果合取范式S是不可满足，则S有否证 证明：对S中所含命题个数k归纳证明 第一步骤 k=1: S中有p, p
第二步骤 假设k<n时定理成立，证明k=n时定理成立 1. 对S p应用引理1，得到等满足性的S’ 2. 对S p应用引理1，得到等满足性的S’’ 由假设，存在S’的否证C1,…,Ci，S’’的否证 D1,…,Dj
67
2.4 消解法 证明（继续）： 1. 对S p应用引理1，得到等满足性的S’ 2. 对S p应用引理1，得到等满足性的S’’
由假设，存在S’的否证C1,…,Ci，S’’的否证 D1,…,Dj 情况1：Ct (it1)或Ds (jt1)都是由不含p的简单析取式消解得到， C1,…,Ci或D1,…,Dj为S的否证 情况2： Ct (或Ds)不满足情况1条件，则扩展Ct (或Ds)得到C′t= Ct p (或D′s = Ds p ) ，则C′t (或D′s )属于S ，且 C′i= p， D′j=p，消解得到空子句□
68
第二章 习题课 主要内容 等值式与等值演算 基本等值式（16组，24个公式） 主析取范式与主合取范式 联结词完备集 消解法
69
基本要求 深刻理解等值式的概念 牢记基本等值式的名称及它们的内容 熟练地应用基本等值式及置换规则进行等值演算
理解文字、简单析取式、简单合取式、析取范式、合取范式的概念 深刻理解极小项、极大项的概念、名称及下角标与成真、成假赋值的关系，并理解简单析取式与极小项的关系 熟练掌握求主范式的方法（等值演算、真值表等） 会用主范式求公式的成真赋值、成假赋值、判断公式的类型、判断两个公式是否等值 会将公式等值地化成指定联结词完备集中的公式 会用命题逻辑的概念及运算解决简单的应用问题 掌握消解规则及其性质 会用消解算法判断公式的可满足性
70
练习1:概念 1. 设A与B为含n个命题变项的公式，判断下列命题是否为真？ (1) AB当且仅当A与B有相同的主析取范式
(2) 若A为重言式，则A的主合取范式为0 (3) 若A为矛盾式，则A的主析取范式为1 (4) 任何公式都能等值地化成{, }中的公式 (5) 任何公式都能等值地化成{, , }中的公式 真 假 假 假 真 说明: (2) 重言式的主合取范式不含任何极大项，为1. (3) 矛盾式的主析取范式不含任何极小项, 为0. (4) {, }不是完备集，如矛盾式不能写成{, }中的公式. (5) {, }是完备集.
71
练习2: 判断公式类型 2. 判断下列公式的类型: (1) (pq)(qp) 解 用等值演算法求主范式 (pq)(qp)
解 用等值演算法求主范式 (pq)(qp) (pq)(qp) (pq)(qp) (pq)(pq)(pq)(pq) m2 m1 m3 m0 m0 m1 m2 m 主析取范式 主合取范式 重言式
72
练习题2(续) (2) (pq)q 解 用等值演算法求公式的主范式 (pq)q (pq)q pqq
解 用等值演算法求公式的主范式 (pq)q (pq)q pqq 主析取范式 M0 M1 M2 M 主合取范式 矛盾式
73
练习2(续) (3) (pq)p 解 用等值演算法求公式的主范式 (pq)p (pq)p p
解 用等值演算法求公式的主范式 (pq)p (pq)p p (pq)(pq) m0 m 主析取范式 M2 M 主合取范式 非重言式的可满足式
74
练习3：求公式的主范式 3．已知命题公式A中含3个命题变项p, q, r，并知道它的成真
赋值为001, 010, 111, 求A的主析取范式和主合取范式，及A对应的真值函数. 解 A的主析取范式为m1 m2 m7 A的主合取范式为M0 M3 M4 M5 M6 p q r F p q r F
75
练习4：联结词完备集 4．将A = (pq)r改写成下述各联结词集中的公式: (1) {, , } (2) {, }
(3) {, } (4) {, } (5) {} (6) {} 解 (1) (pq)r (pq)r (2) (pq)r (pq)r (3) (pq)r (pq)r ((pq)r)
76
练习4 解答 (4) (pq)r ((pq)r) ((pq)r)
((pp)(qq)(rr) 说明：答案不惟一
77
练习5：应用题 5. 某公司要从赵、钱、孙、李、周五名新毕业的大学生中选 派一些人出国学习. 选派必须满足以下条件：
(1) 若赵去，钱也去. (2) 李、周两人中至少有一人去 (3) 钱、孙两人中去且仅去一人. (4) 孙、李两人同去或同不去. (5) 若周去，则赵、钱也去. 用等值演算法分析该公司如何选派他们出国？
78
练习5解答 解此类问题的步骤： 1.设简单命题并符号化 2. 用复合命题描述各条件 3. 写出由复合命题组成的合取式
4. 将合取式成析取式（最好是主析取范式） 5. 求成真赋值, 并做出解释和结论
79
练习5解答 解 1. 设简单命题并符号化 设 p: 派赵去，q: 派钱去，r: 派孙去，s: 派李去，u: 派周去 2. 写出复合命题
(3) 钱、孙两人中去且仅去一人 (qr)(qr) (4) 孙、李两人同去或同不去 (rs)(rs) (5) 若周去，则赵、钱也去 u(pq)
80
3. 设(1)—(5)构成的合取式为A A = (pq)(su)((qr)(qr)) ((rs)(rs))(u(pq)) 4. 化成析取式 A (pqrsu)(pqrsu) 结论：由上述析取式可知，A的成真赋值为00110与11001， 派孙、李去（赵、钱、周不去） 派赵、钱、周去（孙、李不去）
81
练习5解答 A (pq)((qr)(qr)) (su)(u(pq)) ((rs)(rs))
B1=(pq)((qr)(qr)) ((pqr)(pqr)(qr)) （分配律） B2=(su)(u(pq)) ((su)(pqs)(pqu)) （分配律） B1B2 (pqrsu)(pqrsu) (qrsu)(pqrs)(pqru) 再令 ((rs)(rs))=B3，则 B1B2B3 (pqrsu)(pqrsu)
82
练习6:消解法 6. 构造公式A=(pq)( qr) (pq)r的否证, 从而证明它是矛盾式. 解 消解序列:
解 消解序列: ① pq A的简单析取式 ② pq A的简单析取式 ③ q ①,②消解 ④ qr A的简单析取式 ⑤ r A的简单析取式 ⑥ q ④,⑤消解 ⑦ ③,⑥消解 这是A的一个否证, 从而证明A是矛盾式.
83
练习7:消解法 7. 用消解法判断下述公式是否是可满足的: (pq)(qr)(qr)
7. 用消解法判断下述公式是否是可满足的: (pq)(qr)(qr) 解 S=(pq)(qr)(qr) 第1次循环 S0=,S1={pq, qr, qr}, S2= pq, qr 消解得到pr qr, qr消解得到r S2={pr,r} 第2次循环 S0={pq, qr, qr},S1={pr,r}, S2= S2= 输出“Yes”,计算结束.
Similar presentations
