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

1、2.1 等值式与基本的等值式2.2 析取范式与合取范式2.3 联结词完备集2.4 可满足性问题与消解法第二章第二章 命题逻辑等值演算命题逻辑等值演算 定义定义7.2.4 7.2.4 给定命题公式 A、B,设 是出现于A和B中的所有的命题变元.若对 的每一组赋值，A和B的真值相同，则称A和B是等值的等值的，记作：12,.,np pp12,.,np ppAB（1）双重否定律()pp （2） 德.摩根律()pqpq （3） 德.摩根律()pqpq 例例1 用真值表法证明下列等值式。等值式可以用真值表来判断。证明（1）p 011001故原来的结论成立p()p (1)()pp ()pq证明（2）pq 0

2、011010111001010011110001000pqpqpq 故原来的结论成立(2)()pqpq 证明（3）pq 0011010111001010000111101110故原来的结论成立(3)()pqpq ()pqpqpqpq 下面列出一些基本的命题定律下面列出一些基本的命题定律 p17p17双重否定律 AA幂等律 AAA AAA 交换律 ABBA ABBA结合律 (AB)CA(BC) (AB)CA(BC)分配律 A(BC)(AB)(AC), A(BC)(AB)(AC)德摩根律 (AB)AB (AB)AB吸收律 A(AB)A, A(AB)A零(一)律 A11, A00同一律 A0A. A

3、1A排中律 AA1矛盾律 AA0蕴涵等值式 ABAB等价等值式 AB(AB)(BA)假言易位 ABBA等价否定等值式 ABAB归谬论 (AB)(AB) A例例2 2 证明 不成立。()pqpq pq0011010111001010000111101000故结论不成立证明：()pqpqpqpq 例例3 3 证明蕴含恒等式：pqpq pq 001101011100 1 1 0 1 1 1 0 1ppq pq故结论成立证明 ：例例4 4 证明假言易位：pqqp pq 001101011100101011011101pqpq故结论成立证明：pq例例5 5 证明 ()()pqpqqp证明：pq00110

4、10111011011 1 0 0 1 1 0 0 1pqqp()()pqqppq故结论成立.等值演算 由已知的等值式推演出另外一些等值式的过程称为等值演算法。 设 (A) 是含公式 A 的命题公式，(B) 是用公式 B 置换(A) 中所有的 A 后得到的命题公式，那么有如下的置换规则： 若 AB，则 (A)(B) 例如ApqBpq例例6 6 利用等值演算法证明 qppq 证明：证毕 ！qp ()qp qp pq pq例例7 7 利用等值演算法证明 ()pqpq证明：()()pqpq 证毕！ pq pq例例8 8 利用等值演算法证明 ()()pqrpqr证明：()()pqrpqr ()pqr

5、()pqr ()pqr例例9 9 利用等值演算法证明下面公式是矛盾式。 ()()ppqqr 证明：()()()ppqqrTqqr()TFrTF F作业P3842.2 析取范式与合取范式析取范式与合取范式 本节将介绍两种范式析取范式与合取范式。任何一个公式都可以用这两种范式来等值。定义2.2 文字命题变项及其否定的总称例如：p, q,r, p, q,r例如： p, q, pq, pqr, 例如： p, q, pq, pqr, 简单合取式有限个文字构成的合取式简单析取式有限个文字构成的析取式说明：单个文字既是简单析取式，又是简单合取式；一、范式一、范式证明：必要性根据排中律AA1很容易得到；定理2

6、.1 (1) 一个简单析取式是重言式当且仅当 它同时含有某个命题变项和它的否定式.充分性：设简单析取式A为重言式，假设A没有同时含有某个命题变项及它的否定式，则将A中不带否定符的命题都取假，同时可以将带有否定符的命题也都取假，此时A的真值就是0,与A是重言式相矛盾。(2) 一个简单合取式是矛盾式当且仅当它同时含有某个命题变项和它的否定式.同理，根据排中律pp0易得:定义2.3 析取范式由有限个简单合取式组成的析取式例如：p, pq, pq, (pq)(pqr)(qr)合取范式由有限个简单析取式组成的合取式例如： p, pq, pq, (pq)p(pqr)范式析取范式与合取范式的总称说明：简单析

7、取式、简单合取式都既是析取范式，又是合取范式.例如： pq, pq， p q r s定理2.2 (1) 一个析取范式是矛盾式当且仅当它每个简单合取式都是矛盾式.证明：必要性根据000 0很容易得到；充分性：设析取范式A=A1A2An为矛盾式，则用反正法易证Ai只能均为矛盾式。(2) 一个合取范式是重言式当且仅当它的每个简单析取式都是重言式.证明：必要性根据111 1很容易得到；充分性：设析取范式A=A1A2An为重言式，则用反正法易证Ai必须均为重言式。定理2.3（范式存在定理） 任何命题公式都存在与之等值的析取范式与合取范式求公式A的范式的步骤：ABAB(2)否定联结词的内移或消去AB(AB

8、 ) (BA ) (AB)(AB) A A(AB)AB(AB)AB (1) 消去A中的, （若存在） (3) 使用分配律A(BC)(AB)(AC) 求合取范式 A(BC) (AB)(AC) 求析取范式例5 求下列公式的析取范式与合取范式 (1) (pq)r (2) (pq)r解 (1) (pq)r最后结果既是析取范式(由3个简单合取式组成的析取式)，又是合取范式(由一个简单析取式组成的合取式) (pq)r （消去） pqr (2) (pq)r (pq)r (pr)(qr) (pq)r (pq)r析取范式 合取范式定义2.4 在含有n个命题变项的简单合取式（简单析取式）中，若每个命题变项和它的否

9、定式恰好出现且仅出现一次，而且命题变项和它的否定式按下标从小到大或按字典顺序排列，称这样的简单合取式（简单析取式）为极小项(极大项). 命题公式的范式是不惟一的，为了使命题公式的范式惟一，我们先将简单合取式（简单析取式）进行规范化：二、主范式二、主范式例如，由两个命题变项 p, q 形成的极小项与极大项极小项极大项公式成真赋值名称公式成假赋值名称pqpqpqpq 0 0 0 1 1 0 1 1 m0m1m2m3 pq pq pq pq 0 0 0 1 1 0 1 1M0M1M2M3几点说明： n个命题变项有2n个极小项和2n个极大项2n个极小项（极大项）均互不等值。 用mi表示第i个极小项，其

10、中i是该极小项成真赋值的十进制表示. 用Mi表示第i个极大项，其中i是该极大项成假赋值的十进制表示. mi（Mi）称为极小项（极大项）的名称. 每个极小项只有一个成真赋值，每个极大项只有一个成假赋值。极小项极大项公式成真赋值名称公式成假赋值名称pqrp q rp q rp q rp q rp q rp q rp q r0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 m0m1m2m3m4m5m6m7 p q r p q r p q r p q r p q r p q r p q r p qr0 0 00 0 10 1 00 1 11 0 01 0 11 1 01

11、 1 1 M0M1M2M3M4M5M6M7由三个命题变项由三个命题变项 p, q, r 形成的极小项与极大项形成的极小项与极大项. 定理2.4 设mi与Mi是命题变项含mi MiMi mip1,p2,pn的极小项与极大项，则定义2.5 主析取范式由极小项构成的析取范式例如，n=3, 命题变项为 p, q, r 时，主合取范式由极大项构成的合取范式 (pqr)(pqr) m1m3 主析取范式 (pqr)(pqr) M1M7主合取范式定理2.5 (主范式的存在惟一定理) 任何命题公式都存在与之等值的主析取范式和主合取范式,并且是惟一的。(2) 若某个Bj既不含pi, 又不含pi, 则将Bj展开成

12、Bj Bj(pipi) (Bjpi)(Bjpi) 重复这个过程, 直到所有简单合取式都是长度为n的极小项为止(3) 消去重复出现的极小项, 即用mi代替mimi(4) 将极小项按下标从小到大排列(1) 求A的析取范式A=B1 B2 Bs , 其中Bj是简单合取式 j=1,2, ,s求公式主析取析取范式的步骤:设公式A含命题变项p1，p2，pn例6 (1) 求公式 A=(pq)r的主析取范式解 A=(pq)r (pq) (pq)r (pq)r （析取范式） (pq) r (pq)(rr) (pqr)(pqr) m6m7 r (pp)(qq)r (pqr)(pqr)(pqr)(pqr) m1m3m

13、5m7 , 代入并排序，得 (pq)r m1m3m5 m6m7 （主析取范式）求公式的主合取主合取范式的步骤:设公式A含命题变项p1,p2,pn(1) 求A的合取范式A=B1B2 Bs , 其中Bj是简单析取式 j=1,2, ,s (2) 若某个Bj既不含pi, 又不含pi, 则将Bj展开成 Bj Bj(pipi) (Bjpi)(Bjpi) 重复这个过程, 直到所有简单析取式都是长度为n的极大项为止(3) 消去重复出现的极大项, 即用Mi代替MiMi(4) 将极大项按下标从小到大排列例6 （2）求公式 A=(pq)r的主合取范式 A= (pq)rpr (pr)(qr) （合取范式） (pq)r

14、 （析取范式） (pqr)(pqr) p(qq)r M0M2 qr (pp)qr M0M4 (pqr)(pqr) , 代入 并排序，得 (pq)r M0M2M4 （主合取范式）三、主范式的应用三、主范式的应用1.求公式的成真成假赋值 设公式A含n个命题变项, A的主析取主析取范式有s个极小项, 则A 有s个成真赋值, 它们是极小项下标的二进制表示, 其余2n-s个赋值都是成假赋值. 例如 (pq)r m1m3m5 m6m7成真赋值为 001, 011, 101, 110, 111，成假赋值为 000, 010, 100. 类似地，由主合取范式也立即求出成假赋值和成真赋值. 作业P385、6例7

15、、用主范式求下列公式的赋值.(1)、求公式(p(qr)(pqr)的成真赋值.解(p(qr)(pqr)(p(qr)(pqr) (p (qr)(pqr) (p( qr)(pqr) (p q) (p r)(pqr) (p q) (p r)pqr因为 p q pq （r r） (pq r)(pq r） m1m0p r p（q q）r (pq r)(p q r） m2m0p p (q q) (r r） (p q r) (p q r ) (p q r) (p q r） m7m6 m5 m4同理q (p q r) (p q r ) ( p q r) (p q r） m7m6 m3 m2r (p q r) (

16、p q r ) ( p q r) (p q r） m7m5 m3 m1因此，(p(qr)(pqr) m0 m1m2 m3 m4 m5 m6 m7从而原公式的成真赋值是000，001，010，011，100，101，110，111.（2）求公式 (p q) ( p r)的成假赋值.解(p q) ( p r)(p q) p r(p p r ) (q p r)1 (q p r)q p r p q r M4从而 (p q) ( p r)的成假赋值只有100.2. 判断公式的类型设A含n个命题变项. A为重言式 A的主析取范式含全部2n个极小项 A的主合取范式不含任何极大项, 记为1.A为矛盾式 A的主

17、合析取范式含全部2n个极大项 A的主析取范式不含任何极小项, 记为0. A为可满足式 A的主析取范式中至少含一个极小项 A的主合取范式不是全部的极大项.例8 用主析取范式判断公式的类型:(1) A (pq)q (2) B p(pq) (3) C (pq)r解 (1) A ( pq)q(2) B p(pq) ( pq)q 0 矛盾式 ( p(qq) 1 ( pp)q m0m1m2m3 重言式 (pq)r (pq)r (pqr)(pqr)因此C m0m1m3 m5m7是非重言式的可满足式(3) C (pq)rr(pqr)(pqr)(pqr)(pqr)而 pq m1m0 m1m3m5 m7例9、求公

18、式 (q p) p的成假赋值.解 (q p)p(q p) p (q p)p q pp 0 M0 M1M2 M3从而原公式的成假赋值是00，01，10，11.(2)、求公式(p(pq)r的成假赋值.解(p(pq)r(p(pq)rppqr1从而原公式没有成假赋值。3. 判断两个公式是否等值例10 用主析取范式判以下每一组公式是否等值 p(qr) 与 (pq)r p(qr) 与 (pq)r解 p(qr) = m0m1m2m3 m4m5 m7 (pq)r = m0m1m2m3 m4m5 m7 (pq)r = m1m3 m4m5 m7显见，中的两公式等值，而的不等值.4. 解实际问题例11 某单位要从A

19、,B,C三人中选派若干人出国考察, 需满足下述条件: (1) 若A去, 则C必须去; (2) 若B去, 则C不能去; (3) A和B必须去一人且只能去一人. 问有几种可能的选派方案?解 记 p:派A去, q:派B去, r:派C去(1) pr, (2) qr, (3) (pq)(pq)求该公式的主析取范式 (pr)(qr)(pq)(pq) (pr)(qr)(pq)(pq) (pq)(pr)(rq)(rr) (pq)(pq) (pq)(pq)(pr)(pq) (rq)(pq)(pq)(pq) (pr)(pq)(rq)(pq)该问题转化为求下式的成真赋值 (pr)(qr)(pq)(pq) (pqr)

20、(pqr)成真赋值:101,010结论: 方案1 派A与C去, 方案2 派B去四、主范式的其他求法四、主范式的其他求法1、根据真值表求主范式由A的成真赋值可以得到主析取范式；由A的成假赋值可以得到主合取范式。解pqr00001111001100110101010110001pq011112()pqr例求的主范式.110()pqr1111()pqr成真赋值有000，001，011，101，111246MMM成假赋值有010，100，11001357mmmmm2、主析取范式与主合取范式互相转化原理：因此A的主析取范式是设A含n个命题变项，A的主析取范式为12siiiAmmm将A的主析取范式不含有的

21、极小项记为122,nsjjjmmm122nsjjjAmmmA A122()nsjjjmmm 122nsjjjmmm 122nsjjjMMM这样，A的主合取范式含有的极大项恰好是将A的主析取范式中没有的极小项改成极大项。同理，可A的主合取范式化成主析取范式。例13 设A有3个命题变项, 且已知A= m1m3m7, 求A的主合取范式.解因此，A M0M2M4M5M6A中没出现的极小项为m0，m2， m4， m5 ， m6 思考： n个命题变项的主析取范式（主合 取范式）共有多少个呢？ n个命题变项共可产生2n个极小项（极大项），因而共可产生012222nnnnCCC 个不同的主析取范式（主合取范式

22、）。11 1nnnnnabaC abb（）012nnnnnCCC 二项式定理22n例如2个命题变项的主析取范式共有 16个：0，m0，m1， m2， m3 m0m1， m0m2 ， m0m3， m1m2 ， m1m3 ， m2m3 m0m1m2 ， m0m1m3 m0m2m3 ， m1m2m3 m0m1m2 m3作业P387(1)、8(1)、9（1）、10(1)2.3 联结词的完备集定义2.6 称F:0,1n 0,1 为n元真值函数.n22n21元真值函数 p 0 0 0 1 1 1 0 1 0 1 )1(3)1(2)1(1)1(0FFFF定义域0,1n=000, 001, , 111，包含

23、个长为n的0,1符号串. n 个命题变项共可构成 个不同的真值函数. p q0 00 11 01 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1p q0 00 11 01 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1)2(7)2(6)2(5)2(4)2(3)2(2)2(1)2(0FFFFFFFF)2(15)2(14)2(13)2(12)2(11)2(10)2(9)2(8FFFFFFFF2元真值函数元真值函数(2)7F 每个真值函数与唯一的一个主析