离散数学,命题逻辑等值演算.ppt

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

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

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

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

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

6、类型 （1）（pq）p q （2） （pq）q）r,判断问题,【例2.6】判断王教授是哪里人： 甲说王教授不是苏州人，是上海人 乙说王教授不是上海人，是苏州人 丙说不是上海人，也不是杭州人 王教授说三个人中一个说的全对，一个说对了一半，另一个全不对。 解：p：王教授是苏州人 q：王教授是上海人 r：王教授是杭州人,解题思路,p q r 0 0 1 0 1 0 1 0 0 王教授的话是对的，写出公式 A（p,q,r)，找出它的成真赋值,根据实际情况， 只有3个赋值， 而不是8个,作业,习题二 3839页 题目： 3，4 17，18 19，20,2.2 析取范式与合取范式,定义2.2 将命题变元及

7、其否定统称为文字（literal）。 简单析取式（基本和）： 仅由有限个文字构成的析取式，也称为子句（clause）。 简单合取式（基本积）：仅由有限个文字构成的合取式。,例如： p、q既是一个文字的简单析取式， 又是一个文字的简单合取式。 pq，p r均是有两个文字的简单析取式，即子句。 pqr，pq q均是有三个文字的简单合取式。,定理 2.1,(1) 一个简单析取式是重言式， 当且仅当它同时含有一个命题变元及其否定。 (2) 一个简单合取式是矛盾式， 当且仅当它同时含有一个命题变元及其否定。 例如， pq p 是重言式 p q q是矛盾式,范式（normal form）的定义,定义2.3

8、 析取范式 由有限个简单合取式构成的析取式，简称DNF（disjunctive normal form）。 合取范式 由有限个简单析取式构成的合取式，简称CNF（conjunctive normal form）。,析取范式的例子： A = A1 A2 An = (pqr) (pq q) p,范式存在定理,定理2.3 任一命题公式都存在着与之等值的析取范式 任一命题公式都存在着与之等值的合取范式,求范式的步骤如下： 消去联结词“”和“” 利用双重否定律消去否定联结词“”或利用德摩根律将否定联结词“”移到各命题变元前(内移)。 利用分配律，结合律将公式归约为合取范式和析取范式。,例题,【例2.7】

9、 求(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)r,合取范式 （pr) (qr) (pqr) 析取范式 （pqr）（ pr ）（ qr ）,极小项与极大项,定义2.4 极小项：在含有n个命题变元的简单合取式中，若每个命题变元和它的否定式不同时出现，而二者之一必出现且仅出现一次，且第i个命题变元（或它的否定式）出现在从左算起的第i位上。 极大项：简单析取式中满足如上条件。,极小（大）项的核心性质,定理：n

10、个命题变元共有2n个极小项（极大项）。 每个极小（大）项只有一个成真（假）赋值，且各极小项的成真赋值互不相同。 极小项和它的成真赋值构成了一一对应的关系。,极小项的性质,可用成真赋值为极小项进行编码，并把编码作为m的下标来表示该极小项，叫做该极小项的名称。 极小项与其成真赋值的对应关系为：变元对应1，而变元的否定对应0。,极小项的性质,极大项,练习,写出极小项的公式： m4 m6 m7 当变元的个数分别为3、4时。 写出极大项的公式： M4 M6 M7 当变元的个数分别为3、4时。,定理：极小项与极大项,定理2.4 miMi mi Mi,定义：主范式,定义2.5 主析取范式：析取范式中所有的简

11、单合取式都是极小项。 主合取范式：合取范式中所有的简单析取式都是极大项。 问题： 对于n个命题变元， 有多少个主析（合）取范式？,例： m0m1m7 （n3） M0M2M6 （n3）,主范式的存在性与唯一性,定理2.5 任何命题公式都存在与之等值的主析取范式和主合取范式，并且是唯一的。 证明： （1）存在性：等值演算 （2）唯一性：反证法,例题与练习,【例2.8】求主析取范式与主合取范式： (pq)r 练习： pq,合取范式 （pr) (qr) (pqr) 析取范式 （pqr）（ pr ）（ qr ）,主范式与真值表,定理： 若公式A中含n个命题变元，A的主析取范式含s（0s2n）个极小项，则

12、A有s个成真赋值，它们是所含极小项编号的二进制表示，其余2n s个赋值都是成假赋值。 反之也成立。 对主合取范式有相同的结果（对应成假赋值）,从真值表求主范式,【例】用真值表法，求(pq)r的主范式。 m001m011m100m101m111 m1m3m4m5m7,“排斥或”的公式,排斥或： ( pq) (p q) m1 m2,通过主范式判别公式类型,定理 A为重言式当且仅当A的主析取范式含全部2n个极小项（主合取范式0个极大项） A为矛盾式当且仅当A的主析取范式不含任何极小项（主合取范式含所有的极大项） A为可满足式当且仅当A的主析取范式至少含一个极小项。,主析取范式与主合取范式的关系,定理

13、： 同一公式的主析取范式中极小项m的下标和主合取范式中极大项M的下标是互补的。 换言之，对于任一公式， 在它的2n个赋值中， 非0即1， 因此其主析取范式中的极小项和其主合取范式中的极大项的个数之和恰为2n， 且其下标不会相同。,练习,由主析取范式，求主合取范式 （1）Am1m2 （两个变元） （2）Bm1m2m3 （三个变元）,作业,习题二 3840页 题目：5，6 7，8 9，10 11，12 13，14 25，26,2.3 联结词的完备集,定义2.6 n元真值函数F：0,1n 0,1 定理 每个真值函数，都一一对应一个真值表。每个真值函数，都存在许多与之等值的命题公式。反之，每个命题公式

14、对应唯一的与之等值的真值函数。 定义2.7 设S是联结词集合，如果任何n元真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词完备集。,联结词的完备集,定理2.6 S，联结词完备集。 推论 以下集合都是完备集 ， ， ， ， ，,联结词的完备集,定义2.8 与非联结词：pq (pq) 或非联结词：pq (pq) 定理2.7 ，是联结词完备集。,2.4 可满足性问题与消解法,命题公式的可满足性问题 （SAT问题，satisfiability problem）是算法理论的核心问题之一。 真值表、主范式的计算量大。 从算法复杂度上讲，SAT是第一个被证明为NP难的问题。,SAT问题,很多问

15、题可以转化为SAT问题 著名的八皇后问题 鸽笼问题 图着色问题等,合取范式的可满足性问题,S表示合取范式，C表示简单析取式（子句），L表示文字 合取范式： SC1 C2 C3 Cn S是可满足的当且仅当每个Ci都是可满足的。 或者，只要一个子句不可满足，则S不可满足 进一步，只要一部分不满足，则整体不满足,简单析取式（子句）,Ci L1 L2 L3 Lk 一个简单析取式中同时出现文字L（如p）及它的补Lc（如p），则它为永真式。 永真式可以从合取范式中除去，是多余的。 因此，假设简单析取式中不同时出现某个命题变项和它的否定。,空子句不可满足,Ci L1 L2 L3 Lk 文字越多，越容易满足

16、文字越少，越难满足 空子句，记为，不可满足。（没有极小项，无成真赋值）。 因此，含有空子句的合取范式是不可满足的。,如子句 p，在p1时被满足， 而子句pq，在p0时也能满足 （q0）。,通过“消解规则”产生“空子句”,定义2.9 C1与C2是两个简单析取式 C1C1 L （ pq r ） C2C2 Lc （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)= ,通过消解规则化简合取式,定理2.8 C1 C2 Res（C1，C2） 即，C1 C2可满足当且仅当 消解式Res（C1，C

17、2）可满足,若 C1 p q r C2 p r 则 C1 C2 （ p q r ） （p r ） Res（C1,C2） p q,消解序列与否证,定义2.10 设S是一个合取范式，C1，C2， ，Cn是一个如下生成的子句序列： 对每一个i（1in），Ci是S中的一个简单析取式； 或者Ci是它之前的某两个简单析取式Cj，Ck（1jki）的消解结果， 则称此序列是由S导出的消解序列。 当Cn时，称此序列是S的一个否证。,消解的完全性,推论 如果合取范式S有否证，则S是不可满足的。 定理2.10（消解的完全性） 如果合取范式S是不可满足的，则S有否证。 推论 合取范式S是不可满足的当且仅当S有否证。,

18、消解算法,输入：合式公式A 输出：当A是可满足的，回答“yes”； 否则回答“no”。 步骤如下： 求A的合取范式S S1为S的所有子句的集合，S0与S2为空集,运用消解规则,3.对S0 中的每一个子句C1与S1中的每一个子句C2 如果C1、C2可以消解，则计算CRes（C1，C2） 如果C 则输出“no”，计算结束 否则，如果S0与S1都不包含C 则将C加入S2,运用消解规则,4.对S1 中的每一对子句C1与C2 如果C1、C2可以消解，则计算CRes（C1，C2） 如果C 则输出“no”，计算结束 否则，如果S0与S1都不包含C 则将C加入S2,5 .如果S2中没有任何元素则 输出“yes”，计算结