第一部分 第二章 命题逻辑等值演算

1、第二章第二章 命题逻辑命题逻辑等值演算等值演算 2.1 2.1 等值式等值式 2.2 2.2 析取范式与合取范式析取范式与合取范式 2.3 2.3 联结词的完备集联结词的完备集 2.4 2.4 可满足性问题与消解法可满足性问题与消解法重点重点难点难点2.1 2.1 等值式等值式定义定义2.12.1 设设A A、B B是任意两个命题公式，若等价式是任意两个命题公式，若等价式 A A B B为重言式，则称为重言式，则称A A与与B B是是等值的等值的， 记作：记作：A A B B 自反性自反性，即对任意命题公式，即对任意命题公式A A， A AA A 对称性对称性，即对任意命题公式，即对任意命题公

2、式A A和和B B， 若若A AB B，则，则B BA A 传递性传递性，即对任意命题公式，即对任意命题公式A A，B B和和C C， 若若A AB B，B BC C，则，则A AC C两点注意两点注意 “”与与“= =” “A=B”“A=B”表示表示两公式一样两公式一样， “ “A A B” B”表示两公式表示两公式真值一样真值一样 与与是两类完全不同的符号是两类完全不同的符号 是是联结词、运算符联结词、运算符，A AB B是一个公式。是一个公式。 不是联结词，不是联结词，而是两个公式之间的而是两个公式之间的关系符关系符真值表判断等值真值表判断等值p pq qr rp p(q(qr r）(p

3、(pq)q)r r(pq)(pq)r r0 00 00 01 10 01 10 00 01 11 11 11 10 01 10 01 10 01 10 01 11 11 11 11 11 10 00 01 11 11 11 10 01 11 11 11 11 11 10 00 00 00 01 11 11 11 11 11 1十六组重要的等值式（模式）十六组重要的等值式（模式） 1.1.双重否定律双重否定律 A A A A 2.2.幂等律幂等律 AA AA A A，AA AA A A 3.3.交换律交换律 AB AB BABA，AB AB BABA 4.4.结合律结合律 (AB)C (AB)C

4、 A(BC)A(BC) (AB)C (AB)C A(BC)A(BC)十六组重要的等值式十六组重要的等值式 5.5.分配律分配律 ( (提取公因式）提取公因式） A(BC) A(BC) ( (AAB)(B)(AAC)C) A(BC) A(BC) ( ( AAB)(B)(AAC)C) 6.6.德摩根律德摩根律 (AB) (AB) AAB B (AB) (AB) AAB B德摩根律德摩根律的例子的例子 “地大物博”的否定： 地不大地不大或或物不博物不博 (AB) (AB) AAB B “用人民币或港币支付”的否定： 既既不能用人民币支付，不能用人民币支付，也也不能用不能用港币支付港币支付 (AB)

5、(AB) AAB B 十六组重要的等值式十六组重要的等值式 7.7.吸收律吸收律 A(AB)A(AB)A A，A(AB)A(AB)A A 8.8.零律零律 A1A11 1，A0A00 0 9.9.同一律同一律 A0A0A A，A1A1A A 10.10.排中律排中律 AAA A 1 1 11.11.矛盾律矛盾律 AAA A 0 0十六组重要的等值式十六组重要的等值式 12.12.蕴涵等值式蕴涵等值式 AB AB ABAB 13.13.等价等值式等价等值式 A AB B (AB)(BA)(AB)(BA) 14.14.假言易位假言易位 AB AB BBA A 15.15.等价否定等值式等价否定等值

6、式 A AB B A AB B 16.16.归谬论归谬论 (AB)(A(AB)(AB) B) A A蕴涵等值式的例子蕴涵等值式的例子 蕴涵等值式：蕴涵等值式： AB AB ABAB 否定形式：并非（否定形式：并非（p pq q) ) (pq (pq) ) p p q q 例：例： 并非招手即停并非招手即停 招手且不停车招手且不停车归谬论的应用归谬论的应用 归谬论归谬论 (AB)(AB) (AB)(AB) AA 反证法反证法 如果非如果非p p，则，则q q 如果非如果非p p，则非，则非q q 所以，所以，p p归谬论的例子归谬论的例子 亚理士多德：物体的下落速度亚理士多德：物体的下落速度与物

7、体的重量成正比。与物体的重量成正比。 伽利略的思想实验：伽利略的思想实验： A A快快B B慢，慢，A AB B比比A A快；快； A A快快B B慢，慢，A AB B比比A A慢。慢。 归谬论的例子归谬论的例子 一个岛上有一个风俗，凡是外乡人都要作一个岛上有一个风俗，凡是外乡人都要作为祭品被杀掉。为祭品被杀掉。 但允许被杀的人在临死前说一句话。但允许被杀的人在临死前说一句话。 如果这句话是真的，则死在真理之神面前。如果这句话是真的，则死在真理之神面前。 如果这句话是假的，则死在错误之神面前。如果这句话是假的，则死在错误之神面前。 一个一个哲学家哲学家说了一句话，而免于一死。说了一句话，而免于

8、一死。等值演算与置换规则等值演算与置换规则 由已知的等值式推演出另外的等值由已知的等值式推演出另外的等值式的过程称为式的过程称为等值演算。等值演算。 置换规则置换规则 设设 （A A）是一个含有公式）是一个含有公式A A的命题公式，的命题公式， （B B）是用公式）是用公式B B置换了置换了 （A A）中的公式）中的公式A A后得到的公式，后得到的公式， 如果如果A A B B，那么，那么 （A A） （B B）。）。等值演算的例子等值演算的例子【例【例2.12.1】 用等值演算验证等值式用等值演算验证等值式 pp（qrqr）（pqpq）r r()()()()()()pqrpqrpqrpqrp

9、qrpqr 等值演算的例子等值演算的例子【例【例2.22.2】用等值演算法判断下列用等值演算法判断下列公式的类型。公式的类型。 qq ( (pq)ppq)p) ) (p (pp)(qp)(q q)rq)r) ) (pq) (pq)p p等值演算的例子等值演算的例子解：解： q(q(pq)p(pq)p) ) q(q(pp)(qp(pp)(qp) ) () (分配律分配律) ) q(0(qp) (q(0(qp) (矛盾律矛盾律) ) qq(qp(qp) ) ( (同一律同一律) ) qq(qp(qp) ) ( (德摩根律德摩根律) ) (qq)p(qq)p ( (结合律结合律) ) 1p (1p

10、(排中律排中律) ) 1 (1 (零律零律) ) 由此可知，由此可知，为为重言式重言式。等值演算的例子等值演算的例子解：解： (p(pp)(qp)(qq)rq)r) ) 1(q1(qq)r) (q)r) (排中律排中律) ) 1(0r) (1(0r) (矛盾律矛盾律) ) 10 (10 (零律零律) ) 0 (0 (条件联结词的定义条件联结词的定义) ) 由此可知，由此可知，为为矛盾式矛盾式。 (pq)(pq)p p ( (pq)pq)p p ( (蕴涵等值式蕴涵等值式) ) p (p (吸收律吸收律) ) 由此可知，由此可知，是是可满足式可满足式。练习练习1.1.用等值演算验证等值式用等值演

11、算验证等值式（1 1） (pq)r(pq)r (pr) (qr (pr) (qr) )（2 2） （(pq(pq) ) （pqpq） （p p q q） 2.2.判断公式的类型判断公式的类型 （1 1）（）（pqpq）p qp q （2 2） （pqpq）qq）r r判断问题判断问题【例【例2.62.6】判断王教授是哪里人：判断王教授是哪里人： 甲说王教授不是苏州人，是上海人甲说王教授不是苏州人，是上海人 乙说王教授不是上海人，是苏州人乙说王教授不是上海人，是苏州人 丙说不是上海人，也不是杭州人丙说不是上海人，也不是杭州人 王教授说三个人中一个说的全对，一个说对王教授说三个人中一个说的全对，一

12、个说对了一半，另一个全不对。了一半，另一个全不对。解：解：p p：王教授是苏州人：王教授是苏州人 q q：王教授是上海人：王教授是上海人 r r：王教授是杭州人：王教授是杭州人解题思路解题思路 p q rp q r 0 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 0 王教授的话是对的，写出公式王教授的话是对的，写出公式 A A（p,q,rp,q,r) )，找出它的成真赋值，找出它的成真赋值 根据实际情况，根据实际情况，只有只有3个赋值，个赋值，而不是而不是8个个作业作业 习题二习题二 38383939页页 题目：题目： 3 3，4 4 17 17，1818 19 19，20

13、20 2.2 2.2 析取范式与合取范式析取范式与合取范式定义定义2.22.2 将 命 题 变 元 及 其 否 定 统 称 为将 命 题 变 元 及 其 否 定 统 称 为 文 字文 字（literalliteral）。 简单析取式简单析取式（基本和）：（基本和）： 仅由有限个文字仅由有限个文字构成的析取式，也称为构成的析取式，也称为子句（子句（clauseclause）。 简单合取式简单合取式（基本积）：（基本积）：仅由有限个文字仅由有限个文字构成的合取式。构成的合取式。 例如：例如： p p、q q 既是一个文字的简单析取式，既是一个文字的简单析取式， 又是一个又是一个文字的简单合取式。文

14、字的简单合取式。 pqpq，ppr r 均是有两个文字的简单析取式，均是有两个文字的简单析取式，即即子句子句。 pqrpqr，pqpqq q 均是有三个文字的简单合均是有三个文字的简单合取式。取式。定理定理 2.12.1(1) (1) 一个简单析取式是重言式，一个简单析取式是重言式， 当且仅当当且仅当它它同时含有一个命题变元及其否定同时含有一个命题变元及其否定。(2) (2) 一个简单合取式是矛盾式，一个简单合取式是矛盾式， 当且仅当当且仅当它它同时含有一个命题变元及其否定同时含有一个命题变元及其否定。 例如，例如， pqp 是是重言式重言式 pqq 是是矛盾式矛盾式范式（范式（normal

15、form）的定义）的定义定义定义2.32.3 析取范式析取范式 由有限个简单合取式构成的析由有限个简单合取式构成的析取式，简称取式，简称DNFDNF（disjunctive normal disjunctive normal formform）。）。 合取范式合取范式 由有限个简单析取式构成的合由有限个简单析取式构成的合取式，简称取式，简称CNFCNF（conjunctive normal conjunctive normal formform）。）。析取范式的例子：析取范式的例子： A = AA = A1 1 A A2 2 A An n = = (pqr) (pqq) p合取范式的例子：合取

16、范式的例子： A = BA = B1 1 B B2 2 B Bm m = = (p q r) (p q q) p子句子句范式存在定理范式存在定理定理定理2.32.3 任一命题公式都任一命题公式都存在存在着与之等值的着与之等值的析取范式析取范式 任一命题公式都任一命题公式都存在存在着与之等值的着与之等值的合取范式合取范式求范式的步骤如下：求范式的步骤如下： 消去联结词消去联结词“”和和“” 利用双重否定律消去否定联结词利用双重否定律消去否定联结词“”或或利用德摩根律将否定联结词利用德摩根律将否定联结词“”移到各命题移到各命题变元前变元前( (内移内移) )。 利用分配律利用分配律，结合律将公式归

17、约为合取，结合律将公式归约为合取范式和析取范式。范式和析取范式。例题例题【例【例2.72.7】 求求 (pq)p 的合取范式和析取范式的合取范式和析取范式。 (pq)p (pq)p) (p(pq) (pq)p) (p(pq) (pq)p) (p(pq) (pp)(qp)(ppq) ) 1(qp)(1q) 1(qp)1 (qp)合取范式合取范式合取范式合取范式析取范式析取范式练习练习 求析取范式与合取范式：求析取范式与合取范式： (pq(pq) ) r r 合取范式合取范式 （pr) (qr) (pqr) 析取范式析取范式 （pqr）（ pr ）（ qr ）极小项与极大项极小项与极大项定义定义2

18、.4 2.4 极小项极小项：在含有：在含有n n个命题变元的个命题变元的简单合取式简单合取式中中，（1 1）若每个命题变元和它的否定式）若每个命题变元和它的否定式 不同时出现，而不同时出现，而二者之一二者之一必必 出现且仅出现一次出现且仅出现一次 （2 2）且第）且第i i个命题变元（或它的否定式）个命题变元（或它的否定式） 出现在从左算起的第出现在从左算起的第i i位上位上。 极大项：极大项：简单析取式中满足如上条件。简单析取式中满足如上条件。 极小（大）项的极小（大）项的核心性质核心性质 定理：定理：n n个命题变元共有个命题变元共有2 2n n个极小项（极大项）。个极小项（极大项）。 p

19、qpqpqpqpq000001010010100100111000 每个极小（大）项只有每个极小（大）项只有一个成真（假）赋值一个成真（假）赋值，且各极小项的成真赋值且各极小项的成真赋值互不相同互不相同。 极小项和它的成真赋值构成了极小项和它的成真赋值构成了一一对应一一对应的关的关系系。极小项的记号与编码极小项的记号与编码极小项成真赋值成真赋值名称pq00m0pq01m1pq10m2pq11m3 可用成真赋值可用成真赋值为极小项进行编码为极小项进行编码，并把编码作为，并把编码作为m m的下标来表示该极小项，叫做该极小项的名称。的下标来表示该极小项，叫做该极小项的名称。 极小项与其成真赋值的对应

20、关系为：极小项与其成真赋值的对应关系为：变元对应变元对应1 1，而变元的否定对应而变元的否定对应0 0。极小项的记号（极小项的记号（n3）极小项极小项成真赋值成真赋值名称名称pqr000m0pqr001m1pqr010m2pqr011m3pqr100m4pqr101m5pqr110m6pqr111m7极大项极大项成假赋值成假赋值名称名称pq00M0pq01M1pq10M2pq11M3极大项极大项成假赋值成假赋值名称名称pqr000M0pqr001M1pqr010M2pqr011M3pqr100M4 pqr101M5pqr110M6pqr111M7极大项的记号极大项的记号（n2，3）练习练习 写

21、出极小项的公式：写出极小项的公式： m m4 4 m m6 6 m m7 7 （当变元的个数分别为（当变元的个数分别为3 3、4 4时）时） 写出极大项的公式：写出极大项的公式： M M4 4 M M6 6 M M7 7 （当变元的个数分别为（当变元的个数分别为3 3、4 4时）时）定理：极小项与极大项定理：极小项与极大项定理定理2.4 2.4 m mi i M Mi i m mi i M Mi i极大项极大项成假赋值成假赋值名称名称pq00M0pq01M1pq10M2pq11M3极小项成真赋值成真赋值名称pq00m0pq01m1pq10m2pq11m3主范式的定义主范式的定义定义定义2.52

22、.5 主析取范式主析取范式：析取范式中所有的简单合取式都：析取范式中所有的简单合取式都是极小项。是极小项。 主合取范式主合取范式：合取范式中所有的简单析取式都：合取范式中所有的简单析取式都是极大项。是极大项。 例：例： m m0 0 m m1 1 m m7 7 （n n3 3） M M0 0 M M2 2 M M6 6 （n n3 3）22n 问题：问题： 对于对于n n个命题变元，个命题变元， 有多少个主析（合）取范式？有多少个主析（合）取范式？主范式的存在性与唯一性主范式的存在性与唯一性定理定理2.52.5 任何命题公式都任何命题公式都存在存在与之等值的主与之等值的主析取范式和主合取范式，

23、并且是析取范式和主合取范式，并且是唯唯一一的。的。证明：证明： （1 1）存在性：等值演算）存在性：等值演算 （2 2）唯一性唯一性：反证法：反证法 例题与练习例题与练习【例【例2.82.8】求主析取范式与主合取范式：求主析取范式与主合取范式： (pq) r 合取范式合取范式 （pr) (qr) (pqr) 析取范式析取范式 （pqr）（ pr ）（ qr ）练习：练习： 求求 pqpq 的主范式的主范式主范式与真值表主范式与真值表定理定理 若公式若公式A A中含中含 n n 个命题变元，个命题变元， A A的的主析取范式主析取范式含含 s s（0s20s2n n）个）个极极小项小项，则，则A

24、 A有有 s s 个个成真赋值成真赋值， 它们是所含极小项编号的二进制表示它们是所含极小项编号的二进制表示 其余其余 2 2n n s s 个赋值都是个赋值都是成假赋值成假赋值。 反之也成立。反之也成立。 对主合取范式有相同的结果对主合取范式有相同的结果（对应成假赋值）（对应成假赋值）从真值表求主范式从真值表求主范式【例【例】用真值表法，求用真值表法，求(pq)r(pq)r的主范式的主范式。pqrpq(pq)r0001000111010100111110001101011101011111 m m001001mm011011mm100100mm101101mm111111 m m1 1mm3

25、3mm4 4mm5 5mm7 7“排斥或排斥或”的公式的公式排斥或排斥或pq排斥或排斥或000011101110排斥或：排斥或： ( ( pq pq) ) (p (p q) q) m1 m2通过主范式判别公式类型通过主范式判别公式类型定理定理 A A为为重言式重言式当且仅当当且仅当A A的主析取范式含全的主析取范式含全部部2 2n n个极小项（个极小项（主合取范式主合取范式0 0个极大项个极大项） A A为为矛盾式矛盾式当且仅当当且仅当A A的主析取范式不含的主析取范式不含任何极小项（任何极小项（主合取范式含所有的极大主合取范式含所有的极大项项） A A为为可满足式可满足式当且仅当当且仅当A

26、A的主析取范式至的主析取范式至少含一个极小项。少含一个极小项。主析取范式与主合取范式的关系主析取范式与主合取范式的关系定理定理 同一公式的主析取范式中极小项同一公式的主析取范式中极小项m m的下标和主的下标和主合取范式中极大项合取范式中极大项M M的的下标是互补的下标是互补的。 换言之，对于任一公式，换言之，对于任一公式， 在它的在它的2 2n n个赋值中，个赋值中， 非非0 0即即1 1， 因此其因此其主析取范式中的极小项和其主析取范式中的极小项和其主合取范式中的极大项的个数之和恰为主合取范式中的极大项的个数之和恰为2 2n n， 且其下标不会相同且其下标不会相同。练习练习 由主析取范式，求

27、主合取范式由主析取范式，求主合取范式 （1 1）A Am1m2 （两个变元）（两个变元） （2 2）B Bm1m2m3 （三个变元个变元）作业作业 习题二习题二 38384040页页 题目：题目： 5 5，6 6，9 9 10 10， 12 12 13 13， 1414 25 25， 2626 练习练习12. 12. 已知公式已知公式A A含含3 3个命题变项个命题变项 p,q,rp,q,r, , 且它的成真赋值为且它的成真赋值为 000000，011011，110110， 求求A A的主范式。的主范式。13. 13. 已知公式已知公式A A含含3 3个命题变项个命题变项 p,q,rp,q,r

28、, , 且它的成假赋值为且它的成假赋值为 010010，011011，110110，111111 求求A A的主范式。的主范式。14. 14. 已知公式已知公式A A含含n n个命题变项，且无成假赋值，个命题变项，且无成假赋值， 求求A A的主合取范式。的主合取范式。 2.3 2.3 联结词的完备集联结词的完备集定义定义2.62.6 n n元真值函数元真值函数F F：0,10,1n n 0,1 0,1定理定理 每个真值函数，都一一对应一个真值表。每个每个真值函数，都一一对应一个真值表。每个真值函数，都存在许多与之等值的命题公式。真值函数，都存在许多与之等值的命题公式。反之，每个命题公式对应唯一

29、的与之等值的真反之，每个命题公式对应唯一的与之等值的真值函数。值函数。定义定义2.72.7 设设S S是联结词集合，如果任何是联结词集合，如果任何n n元真值函数元真值函数都可以由仅含都可以由仅含S S中的联结词构成的公式表中的联结词构成的公式表示，则称示，则称S S是是联结词完备集联结词完备集。联结词的完备集联结词的完备集定理定理2.6 2.6 S S，联结词完备集。联结词完备集。推论推论 以下集合都是完备集以下集合都是完备集 ， ， ， ， ，联结词的完备集联结词的完备集定义定义2.82.8 与非联结词：与非联结词：pqpq (pq(pq) ) 或非联结词：或非联结词：pqpq (pq(p

30、q) )定理定理2.72.7 ， 是联结词完备集。是联结词完备集。 2.4 2.4 可满足性问题可满足性问题 与消解法与消解法 命题公式的命题公式的“可满足性问题可满足性问题”（SATSAT问题问题，SATSATisfiabilityisfiability Problem Problem）是是“算法理论算法理论”的的核心问题核心问题之一。之一。 真值表、主范式的计算量大。真值表、主范式的计算量大。 从从“算法复杂度算法复杂度”上讲，上讲，SATSAT是第一个是第一个被证明为被证明为“NPNP难难”的问题。的问题。八皇后问题八皇后问题SATSAT问题问题 很多问题可以转化为很多问题可以转化为SA

31、TSAT问题问题 如：著名的八皇后问题如：著名的八皇后问题 鸽笼问题鸽笼问题 图着色问题等图着色问题等本节内容本节内容 将一般的将一般的SAT问题转化为问题转化为“合取范式的合取范式的SAT问题问题” 理论准备：从理论准备：从“消解规则消解规则”到到“可满足的否证可满足的否证” 可编程实现的可编程实现的“消解算法消解算法” 在掌握理论与算法在掌握理论与算法的同时，理解其背后的同时，理解其背后的的“思想思想”更重要！更重要！合取范式的合取范式的可满足性（可满足性（SAT）问题）问题 合取范式：合取范式： S SC C1 1 C C2 2 C C3 3 C Cn n S S 表示合取范式，表示合取

32、范式，C C 表示简单析取式（子句），表示简单析取式（子句）， L L 表示文字表示文字 S S是可满足的是可满足的当且仅当当且仅当每个每个C Ci i都是可满足的都是可满足的 或者，只要一个子句不可满足，则或者，只要一个子句不可满足，则S S不可满足不可满足 进一步，进一步，只要一部分不满足，则整体不可满足只要一部分不满足，则整体不可满足对整个合取范式的对整个合取范式的不可满足问题不可满足问题，采用：，采用： “ “分而治之分而治之”的思想的思想 多个子句合取转化为多个子句合取转化为 “ “比较少比较少”的子句合取的相应问题的子句合取的相应问题 以致于最终转化为以致于最终转化为“一个子句一个

33、子句” 或或“两个子句合取两个子句合取”的（不）可满足问题的（不）可满足问题一个子句（简单析取式）一个子句（简单析取式） C Ci i L L1 1 L L2 2 L L3 3 L Lk k 一个简单析取式中同时出现：一个简单析取式中同时出现： 文字文字 L L（如如 p p）及它的补）及它的补 LcLc（如（如 p p），）， 则它为永真式。则它为永真式。 永真式可以从合取范式中永真式可以从合取范式中除去除去，是多余的。，是多余的。 因此，假设简单析取式中不同时出现某个命因此，假设简单析取式中不同时出现某个命题变项和它的否定。（与题变项和它的否定。（与“极大项极大项”类似）类似）简单的消解规

34、则简单的消解规则简单的消解规则简单的消解规则 合取范式：合取范式： S SC C1 1 1 1 C C3 3 C Cn n 消解后的范式消解后的范式 S SC C1 1 C C3 3 C Cn n 根源：根源： 一个子句中同时出现文字一个子句中同时出现文字 L L 及它的补及它的补 LcLc 那么在不同的子句中，同时出现文字那么在不同的子句中，同时出现文字 L L 及它的补及它的补LcLc，是不是也能对合取范式进行化简呢？，是不是也能对合取范式进行化简呢？少了一个子句少了一个子句子句间的子句间的“冲突冲突”造成合取范式造成合取范式“不可满足不可满足” 合取范式：合取范式： S SC C1 1

35、C C2 2 C C3 3 C Cn n S SC C1 1 C C2 2 p p 子句间的子句间的“冲突冲突”的根源在于：的根源在于： “不同的子句中，同时出现文字不同的子句中，同时出现文字 L L 及它的补及它的补 LcLc” S S （pqpq）（pqpq） q qS S（pqpq）（ qrqr） （ pqpq ） r r 引入引入消解法：消解法： 将（将（p p p p）削去，归结为削去，归结为“空子句空子句” 并规定并规定“空子句空子句”不可满足！不可满足！“空子句空子句”不可满足不可满足 C Ci i L L1 1 L L2 2 L L3 3 L Lk k 文字越多，越容易满足文字

36、越多，越容易满足 文字越少，越难满足，越易冲突文字越少，越难满足，越易冲突 如子句如子句 p p ，在，在 p p1 1 时被满足时被满足 而子句而子句 pq q，在，在 p p0 0 时也能满足（时也能满足（q q0 0）定理：空子句，记为定理：空子句，记为，不可满足，不可满足 定理：含有空子句的合取范式是不可满足的定理：含有空子句的合取范式是不可满足的 S SC C1 1 C C2 2 C C3 3 不可满足！不可满足！通过通过“消解规则消解规则”，寻找，寻找“冲冲突突” S SC C1 1 C C2 2 p p p p S SC C1 1 C C2 2 不可满足！不可满足！一般情况，如：

37、一般情况，如： S （pq）（ qr） （ pq ） r少了一个子句少了一个子句消解规则消解规则一般的一般的“消解规则消解规则”定义定义2.92.9 C C1 1 与与 C C2 2 是是两个子句两个子句（简单析取式）（简单析取式） C C1 1 C C1 1 L L （如：（如： p pqq r r ） C C2 2 C C2 2 LcLc （如（如: : p p r r s t s t） 消解式（消解规则）消解式（消解规则） ResRes（C C1 1,C,C2 2） C C1 1 C C2 2 消解式：消解式： ResRes（C C1 1,C,C2 2） q q r r r r s t

38、s t p q p p q p s t s t Res Res( ( p p , , p p ) = ) = 消解规则的理论基础消解规则的理论基础定理定理2.8 2.8 C C1 1 C C2 2 Res Res（C C1 1，C C2 2） 即即: : C C1 1 C C2 2 可满足可满足 当且仅当当且仅当 消解式消解式ResRes（C C1 1，C C2 2）可满足）可满足例：若例：若 C C1 1 p q p q r r C C2 2 p p r r 则则 C C1 1 C C2 2 （ p q r p q r ） （p p r r ） ResRes（C C1 1,C,C2 2） p

39、 qp q 例题：求消解结果例题：求消解结果 1. C1 p q r C2 p r s 2 C1 p q r C2 p qr1.1. Res Res（C C1 1,C,C2 2） q q r r ss2.2. Res Res（C C1 1,C,C2 2） p p p r p r q q q r q r 例题例题 通过消解规则，寻找子句间的通过消解规则，寻找子句间的“冲突冲突”S （pq） （ qr） （ pq ） rq qp p与与 p p为消解文字为消解文字不可满足不可满足不可满足不可满足消解序列与否证消解序列与否证定义定义2.10 设设 S S 是一个合取范式，是一个合取范式，C C1 1

40、，C C2 2， ，C Cn n 是是一个如下生成的子句序列：一个如下生成的子句序列： 对每一个对每一个i i（1in1in），），C Ci i是是S S中的一个子句中的一个子句（简单析取式）；（简单析取式）； 或者或者 C Ci i 是它之前的某两个子句（简单析取式）是它之前的某两个子句（简单析取式）C Cj j，C Ck k（1j1jk ki i）的消解结果。）的消解结果。 则称此序列是由则称此序列是由 S S 导出的导出的消解序列消解序列。 当当 C Cn n （空子句）时，（空子句）时， 称此序列是称此序列是 S S 的一个的一个否证否证。例题例题 构造公式的否证，从而证明它是矛盾式构

41、造公式的否证，从而证明它是矛盾式S （pq） （ qr） （ pq ） rq q否证：否证：pqpq， qrqr，pqpq， r r，q q， q q， 练习练习 构造公式的否证，从而证明它是矛盾式构造公式的否证，从而证明它是矛盾式q否证：否证：pqpq，pqpq， q q， q q， S （pq） （pq） q练习练习 构造公式的否证，从而证明它是矛盾式构造公式的否证，从而证明它是矛盾式q rq（ pq）（ pr）（ q r）（ p r） r q 否证：否证：pqpq，qqr r， ppr r， r r，qqr r，q q， q q， 理论基础理论基础：消解的完全性消解的完全性 推论推论 如

42、果合取范式如果合取范式 S S 有否证，则有否证，则S S是不可满足的。是不可满足的。 定理定理2.10（消解的完全性）（消解的完全性） 如果合取范式如果合取范式 S S 是不可满足的，则是不可满足的，则 S S 有否证。有否证。 推论推论 合取范式合取范式 S S 是不可满足的是不可满足的当且仅当当且仅当 S S 有否证有否证。如何判别可满足的公式？如何判别可满足的公式？ p(pq)(p p(pq)(pq)(qq)(qr)(qrr)(qr) ) pp rp rqpppqpq 当当遍历遍历所有的消解结果后，所有的消解结果后，都不出现都不出现， 则公式可满足！则公式可满足！面向实用面向实用：消解

43、算法消解算法输入输入：合式公式：合式公式 A A输出输出：当：当 A A 是可满足的，回答是可满足的，回答“yesyes”； 否则回答否则回答“nono”。步骤如下：步骤如下：1.1. 求求 A A 的合取范式的合取范式 S S2.2. S S1 1 为为 S S 的所有子句的集合，的所有子句的集合， S S0 0 与与 S S2 2 为空集为空集典型的判定问题典型的判定问题当前的子句集合当前的子句集合历史子句集合历史子句集合消解出的子句集合消解出的子句集合 算法的核心步骤：算法的核心步骤： 对对 S S0 0 与与 S S1 1 运用消解规则运用消解规则 3.3.对对 S S0 0 中的每一

44、个子句中的每一个子句 C C1 1 与与 S S1 1 中的每一个子句中的每一个子句 C C2 2 如果如果 C C1 1、C C2 2 可以消解，可以消解， 则计算则计算 C CResRes（C C1 1，C C2 2） 如果如果 C C 则输出则输出“nono”，计算结束计算结束 否则，否则， 如果如果 S S0 0 与与 S S1 1 都不包含都不包含 C C 则将则将 C C 加入加入 S S2 2 算法的核心步骤：算法的核心步骤： 对对 S S1 1 运用消解规则运用消解规则 4.4.对对 S S1 1 中的每一对子句中的每一对子句 C C1 1 与与 C C2 2 如果如果 C C

45、1 1、C C2 2 可以消解，可以消解， 则计算则计算 C CResRes（C C1 1，C C2 2） 如果如果 C C 则输出则输出“nono”，计算结束计算结束 否则，否则， 如果如果 S S0 0 与与 S S1 1 都不包含都不包含 C C 则将则将 C C 加入加入 S S2 2算法循环或结束算法循环或结束 5.5.如果如果 S S2 2 中没有任何元素则中没有任何元素则 输出输出 “ “yesyes”，计算结束计算结束 否则否则 把把 S S1 1 加入加入 S S0 0， 令令 S S1 1 等于等于 S S2 2， 清空清空 S S2 2， 返回返回3 3 例题例题【例【例2.142.14】 通过消解法判断公式是否是可满足的。通过消解法判断公式是否是可满足的。 （1 1）（）（ pqpq ） （ pqpq ） q q（2 2） p p （ pqpq ） （ ppq q ） （ qqr r ） （qrqr） （1 1）（）（ pqpq ） （ pqpq ） q q第一次循环第一次循环2. 2. 已相互消解结束的已相互消解结束的: