第一部分-第二章-命题逻辑等值演算PPT参考课件

1、1,第二章 命题逻辑等值演算,2.1 等值式 2.2 析取范式与合取范式 2.3 联结词的完备集 2.4 可满足性问题与消解法,重点,难点,2,2.1 等值式,定义2.1 设A、B是任意两个命题公式，若等价式 A B为重言式，则称A与B是等值的， 记作：A B 自反性，即对任意命题公式A， AA 对称性，即对任意命题公式A和B， 若AB，则BA 传递性，即对任意命题公式A，B和C， 若AB，BC，则AC,3,两点注意,“”与“=” “A=B”表示两公式一样， “A B”表示两公式真值一样 与是两类完全不同的符号 是联结词、运算符，AB是一个公式。 不是联结词， 而是两个公式之间的关系符,4,真

2、值表判断等值,5,十六组重要的等值式（模式）,1.双重否定律 A A 2.幂等律 AA A，AA A 3.交换律 AB BA，AB BA 4.结合律 (AB)C A(BC) (AB)C A(BC),6,十六组重要的等值式,5.分配律 (提取公因式） A(BC) (AB)(AC) A(BC) ( AB)(AC) 6.德摩根律 (AB) AB (AB) AB,7,德摩根律的例子,“地大物博”的否定： 地不大或物不博 (AB) AB “用人民币或港币支付”的否定： 既不能用人民币支付，也不能用港币支付 (AB) AB,8,十六组重要的等值式,7.吸收律 A(AB)A，A(AB)A 8.零律 A11，

3、A00 9.同一律 A0A，A1A 10.排中律 AA 1 11.矛盾律 AA 0,9,十六组重要的等值式,12.蕴涵等值式 AB AB 13.等价等值式 AB (AB)(BA) 14.假言易位 AB BA 15.等价否定等值式 AB AB 16.归谬论 (AB)(AB) A,10,蕴涵等值式的例子,蕴涵等值式： AB AB 否定形式：并非（pq) (pq) p q 例： 并非招手即停 招手且不停车,11,归谬论的应用,归谬论 (AB)(AB) A 反证法 如果非p，则q 如果非p，则非q 所以，p,12,归谬论的例子,亚理士多德：物体的下落速度与物体的重量成正比。 伽利略的思想实验： A快B

4、慢，AB比A快； A快B慢，AB比A慢。,13,归谬论的例子,一个岛上有一个风俗，凡是外乡人都要作为祭品被杀掉。 但允许被杀的人在临死前说一句话。 如果这句话是真的，则死在真理之神面前。 如果这句话是假的，则死在错误之神面前。 一个哲学家说了一句话，而免于一死。,14,等值演算与置换规则,由已知的等值式推演出另外的等值式的过程称为等值演算。 置换规则 设（A）是一个含有公式A的命题公式， （B）是用公式B置换了（A）中的公式A后得到的公式， 如果A B，那么 （A） （B）。,15,等值演算的例子,【例2.1】 用等值演算验证等值式 p（qr）（pq）r,16,等值演算的例子,【例2.2】用等

5、值演算法判断下列公式的类型。 q (pq)p) (pp)(q q)r) (pq)p,17,等值演算的例子,解： q(pq)p) q(pp)(qp) (分配律) q(0(qp) (矛盾律) q(qp) (同一律) q(qp) (德摩根律) (qq)p (结合律) 1p (排中律) 1 (零律) 由此可知，为重言式。,18,等值演算的例子,解： (pp)(qq)r) 1(qq)r) (排中律) 1(0r) (矛盾律) 10 (零律) 0 (条件联结词的定义) 由此可知，为矛盾式。 (pq)p (pq)p (蕴涵等值式) p (吸收律) 由此可知，是可满足式。,19,练习,1.用等值演算验证等值式

6、（1） (pq)r (pr) (qr) （2） （(pq) （pq） （p q） 2.判断公式的类型 （1）（pq）p q （2） （pq）q）r,20,判断问题,【例2.6】判断王教授是哪里人： 甲说王教授不是苏州人，是上海人 乙说王教授不是上海人，是苏州人 丙说不是上海人，也不是杭州人 王教授说三个人中一个说的全对，一个说对了一半，另一个全不对。 解：p：王教授是苏州人 q：王教授是上海人 r：王教授是杭州人,21,解题思路,p q r 0 0 1 0 1 0 1 0 0 王教授的话是对的，写出公式 A（p,q,r)，找出它的成真赋值,根据实际情况， 只有3个赋值， 而不是8个,22,作业

7、,习题二 3839页 题目： 3，4 17，18 19，20,23,2.2 析取范式与合取范式,定义2.2 将命题变元及其否定统称为文字（literal）。 简单析取式（基本和）： 仅由有限个文字构成的析取式，也称为子句（clause）。 简单合取式（基本积）：仅由有限个文字构成的合取式。,例如： p、q 既是一个文字的简单析取式， 又是一个文字的简单合取式。 pq，pr 均是有两个文字的简单析取式，即子句。 pqr，pqq 均是有三个文字的简单合取式。,24,定理 2.1,(1) 一个简单析取式是重言式， 当且仅当它同时含有一个命题变元及其否定。 (2) 一个简单合取式是矛盾式， 当且仅当它

8、同时含有一个命题变元及其否定。 例如， pqp 是重言式 pqq 是矛盾式,25,范式（normal form）的定义,定义2.3 析取范式 由有限个简单合取式构成的析取式，简称DNF（disjunctive normal form）。 合取范式 由有限个简单析取式构成的合取式，简称CNF（conjunctive normal form）。,析取范式的例子： A = A1 A2 An = (pqr) (pqq) p,合取范式的例子： A = B1 B2 Bm = (p q r) (p q q) p,子句,26,范式存在定理,定理2.3 任一命题公式都存在着与之等值的析取范式 任一命题公式都存在

9、着与之等值的合取范式,求范式的步骤如下： 消去联结词“”和“” 利用双重否定律消去否定联结词“”或利用德摩根律将否定联结词“”移到各命题变元前(内移)。 利用分配律，结合律将公式归约为合取范式和析取范式。,27,例题,【例2.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),合取范式,合取范式,析取范式,28,练习,求析取范式与合取范式： (pq) r,合取范式 （pr) (qr) (pqr) 析取范式 （pqr）（ pr ）（

10、 qr ）,29,极小项与极大项,定义2.4 极小项：在含有n个命题变元的简单合取式中，（1）若每个命题变元和它的否定式 不同时出现，而二者之一必 出现且仅出现一次 （2）且第i个命题变元（或它的否定式） 出现在从左算起的第i位上。,极大项：简单析取式中满足如上条件。,30,极小（大）项的核心性质,定理：n个命题变元共有2n个极小项（极大项）。,每个极小（大）项只有一个成真（假）赋值，且各极小项的成真赋值互不相同。 极小项和它的成真赋值构成了一一对应的关系。,31,极小项的记号与编码,可用成真赋值为极小项进行编码，并把编码作为m的下标来表示该极小项，叫做该极小项的名称。 极小项与其成真赋值的对

11、应关系为：变元对应1，而变元的否定对应0。,32,极小项的记号（n3）,33,极大项的记号（n2，3）,34,练习,写出极小项的公式： m4 m6 m7 （当变元的个数分别为3、4时） 写出极大项的公式： M4 M6 M7 （当变元的个数分别为3、4时）,35,定理：极小项与极大项,定理2.4 mi Mi mi Mi,36,主范式的定义,定义2.5 主析取范式：析取范式中所有的简单合取式都是极小项。 主合取范式：合取范式中所有的简单析取式都是极大项。,例： m0 m1 m7 （n3） M0 M2 M6 （n3）,问题： 对于n个命题变元， 有多少个主析（合）取范式？,37,主范式的存在性与唯一

12、性,定理2.5 任何命题公式都存在与之等值的主析取范式和主合取范式，并且是唯一的。,证明： （1）存在性：等值演算 （2）唯一性：反证法,38,例题与练习,【例2.8】求主析取范式与主合取范式： (pq) r,合取范式 （pr) (qr) (pqr) 析取范式 （pqr）（ pr ）（ qr ）,练习： 求 pq 的主范式,39,主范式与真值表,定理 若公式A中含 n 个命题变元， A的主析取范式含 s（0s2n）个极小项，则A有 s 个成真赋值， 它们是所含极小项编号的二进制表示 其余 2n s 个赋值都是成假赋值。 反之也成立。,对主合取范式有相同的结果 （对应成假赋值）,40,从真值表求

13、主范式,【例】用真值表法，求(pq)r的主范式。,m001m011m100m101m111 m1m3m4m5m7,41,“排斥或”的公式,排斥或： ( pq) (p q) m1 m2,42,通过主范式判别公式类型,定理 A为重言式当且仅当A的主析取范式含全部2n个极小项（主合取范式0个极大项） A为矛盾式当且仅当A的主析取范式不含任何极小项（主合取范式含所有的极大项） A为可满足式当且仅当A的主析取范式至少含一个极小项。,43,主析取范式与主合取范式的关系,定理 同一公式的主析取范式中极小项m的下标和主合取范式中极大项M的下标是互补的。 换言之，对于任一公式， 在它的2n个赋值中， 非0即1，

14、 因此其主析取范式中的极小项和其主合取范式中的极大项的个数之和恰为2n， 且其下标不会相同。,44,练习,由主析取范式，求主合取范式 （1）Am1m2 （两个变元） （2）Bm1m2m3 （三个变元）,45,作业,习题二 3840页 题目： 5，6，9 10， 12 13， 14 25， 26,46,练习,12. 已知公式A含3个命题变项 p,q,r, 且它的成真赋值为 000，011，110， 求A的主范式。 13. 已知公式A含3个命题变项 p,q,r, 且它的成假赋值为 010，011，110，111 求A的主范式。 14. 已知公式A含n个命题变项，且无成假赋值， 求A的主合取范式。,

15、47,2.3 联结词的完备集,定义2.6 n元真值函数F：0,1n 0,1 定理 每个真值函数，都一一对应一个真值表。每个真值函数，都存在许多与之等值的命题公式。反之，每个命题公式对应唯一的与之等值的真值函数。 定义2.7 设S是联结词集合，如果任何n元真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词完备集。,48,联结词的完备集,定理2.6 S，联结词完备集。 推论 以下集合都是完备集 ， ， ， ， ，,49,联结词的完备集,定义2.8 与非联结词：pq (pq) 或非联结词：pq (pq) 定理2.7 ，是联结词完备集。,50,2.4 可满足性问题 与消解法,命题公式的“可

16、满足性问题” （SAT问题，SATisfiability Problem）是“算法理论”的核心问题之一。 真值表、主范式的计算量大。 从“算法复杂度”上讲，SAT是第一个被证明为“NP难”的问题。,51,八皇后问题,52,SAT问题,很多问题可以转化为SAT问题 如：著名的八皇后问题 鸽笼问题 图着色问题等,本节内容 将一般的SAT问题转化为“合取范式的SAT问题” 理论准备：从“消解规则”到“可满足的否证” 可编程实现的“消解算法”,在掌握理论与算法的同时，理解其背后的“思想”更重要！,53,合取范式的可满足性（SAT）问题,合取范式： SC1 C2 C3 Cn S 表示合取范式，C 表示简

17、单析取式（子句）， L 表示文字,S是可满足的当且仅当每个Ci都是可满足的 或者，只要一个子句不可满足，则S不可满足 进一步，只要一部分不满足，则整体不可满足,对整个合取范式的不可满足问题，采用： “分而治之”的思想 多个子句合取转化为 “比较少”的子句合取的相应问题 以致于最终转化为“一个子句” 或“两个子句合取”的（不）可满足问题,54,一个子句（简单析取式）,Ci L1 L2 L3 Lk 一个简单析取式中同时出现： 文字 L（如 p）及它的补 Lc（如 p）， 则它为永真式。,永真式可以从合取范式中除去，是多余的。 因此，假设简单析取式中不同时出现某个命题变项和它的否定。（与“极大项”类

18、似）,简单的消解规则,55,简单的消解规则,合取范式： SC1 1 C3 Cn 消解后的范式 SC1 C3 Cn 根源： 一个子句中同时出现文字 L 及它的补 Lc,那么在不同的子句中，同时出现文字 L 及它的补Lc，是不是也能对合取范式进行化简呢？,少了一个子句,56,子句间的“冲突”造成合取范式“不可满足”,合取范式： SC1 C2 C3 Cn,SC1 C2 p p ,子句间的“冲突”的根源在于： “不同的子句中，同时出现文字 L 及它的补 Lc”,S （pq）（pq） q,S（pq）（ qr） （ pq ） r,引入消解法： 将（p p）削去，归结为“空子句” 并规定“空子句”不可满足！

19、,57,“空子句”不可满足,Ci L1 L2 L3 Lk 文字越多，越容易满足 文字越少，越难满足，越易冲突,如子句 p ，在 p1 时被满足 而子句 pq，在 p0 时也能满足（q0）,定理：空子句，记为，不可满足,定理：含有空子句的合取范式是不可满足的,SC1 C2 C3 不可满足！,58,通过“消解规则”，寻找“冲突”,SC1 C2 p p SC1 C2 不可满足！,一般情况，如： S （pq）（ qr） （ pq ） r,少了一个子句,消解规则,59,一般的“消解规则”,定义2.9 C1 与 C2 是两个子句（简单析取式） C1 C1 L （如： pq r ） C2 C2 Lc （如:

20、 p r s t） 消解式（消解规则） Res（C1,C2） C1 C2,消解式： Res（C1,C2） q r r s t p q p s t Res( p , p ) = ,60,消解规则的理论基础,定理2.8 C1 C2 Res（C1，C2） 即: C1 C2 可满足 当且仅当 消解式Res（C1，C2）可满足,例：若 C1 p q r C2 p r 则 C1 C2 （ p q r ） （p r ） Res（C1,C2） p q,61,例题：求消解结果,1. C1 p q r C2 p r s 2 C1 p q r C2 p qr,Res（C1,C2） q r s Res（C1,C2）

21、p p r q q r,62,例题,通过消解规则，寻找子句间的“冲突”,S （pq） （ qr） （ pq ） r,q, q,p与 p为消解文字,不可满足,不可满足,63,消解序列与否证,定义2.10 设 S 是一个合取范式，C1，C2， ，Cn 是一个如下生成的子句序列： 对每一个i（1in），Ci是S中的一个子句（简单析取式）； 或者 Ci 是它之前的某两个子句（简单析取式）Cj，Ck（1jki）的消解结果。 则称此序列是由 S 导出的消解序列。 当 Cn （空子句）时， 称此序列是 S 的一个否证。,64,例题,构造公式的否证，从而证明它是矛盾式,S （pq） （ qr） （ pq ）

22、r,q, q,否证：pq， qr，pq， r，q， q， ,65,练习,构造公式的否证，从而证明它是矛盾式,q,否证：pq，pq， q， q，,S （pq） （pq） q,66,练习,构造公式的否证，从而证明它是矛盾式,q r,q,（ pq）（ pr）（ q r）（ p r） r, q,否证：pq，qr， pr， r，qr，q， q， ,67,理论基础：消解的完全性,推论 如果合取范式 S 有否证，则S是不可满足的。 定理2.10（消解的完全性） 如果合取范式 S 是不可满足的，则 S 有否证。 推论 合取范式 S 是不可满足的当且仅当 S 有否证。,68,如何判别可满足的公式？,p(pq)(

23、pq)(qr)(qr),p,p r,p r,q,p,p,pq,pq,当遍历所有的消解结果后，都不出现， 则公式可满足！,69,面向实用：消解算法,输入：合式公式 A 输出：当 A 是可满足的，回答“yes”； 否则回答“no”。 步骤如下： 求 A 的合取范式 S S1 为 S 的所有子句的集合， S0 与 S2 为空集,典型的判定问题,当前的子句集合,历史子句集合,消解出的子句集合,70,算法的核心步骤： 对 S0 与 S1 运用消解规则,3.对 S0 中的每一个子句 C1 与 S1 中的每一个子句 C2 如果 C1、C2 可以消解， 则计算 CRes（C1，C2） 如果 C 则输出“no”

24、，计算结束 否则， 如果 S0 与 S1 都不包含 C 则将 C 加入 S2,71,算法的核心步骤： 对 S1 运用消解规则,4.对 S1 中的每一对子句 C1 与 C2 如果 C1、C2 可以消解， 则计算 CRes（C1，C2） 如果 C 则输出“no”，计算结束 否则， 如果 S0 与 S1 都不包含 C 则将 C 加入 S2,72,算法循环或结束,5.如果 S2 中没有任何元素则 输出 “yes”，计算结束 否则 把 S1 加入 S0， 令 S1 等于 S2， 清空 S2， 返回3,73,例题,【例2.14】 通过消解法判断公式是否是可满足的。,（1）（ pq ） （ pq ） q,（2） p （ pq ） （ pq ） （ qr ） （qr）,74,（1）（ pq ） （ pq ） q,第一次循环 2. 已相互消解结束的: S0 存放消解结果： S2 当前需要处理的： S1 p q