离散数学第一章命题逻辑第三讲

1、1.5 对偶与范式对偶与范式(二二)一、复习一、复习1、公式的析取范式与合取范式的定义、公式的析取范式与合取范式的定义析取范式析取范式-有限个有限个简单合取式简单合取式的析取式的析取式合取范式合取范式-有限个有限个简单析取式简单析取式的合取式的合取式 2、公式的、公式的析取范式和合取范式的求法析取范式和合取范式的求法二、新课二、新课-主析取范式和主合取范式主析取范式和主合取范式 (一一)主主析取范式析取范式 定义定义1.20：在含：在含n个命题变项的个命题变项的简单合取式简单合取式中中,若若每个命题每个命题变项与其否定不同时存在变项与其否定不同时存在,而二者而二者之一必之一必出现且仅出现一次出

2、现且仅出现一次,且第且第i个命题变项或其否定出个命题变项或其否定出现现在从左起的第在从左起的第i位上位上(若命题变项无角标若命题变项无角标,则按字则按字典顺序排序典顺序排序),这样的简单合取式称为这样的简单合取式称为极小项极小项.极小项的性质极小项的性质 m3 m2 m1 m0 p q pq p q pq p q 00 0 0 0 0 0 1 01 0 1 0 0 1 0 10 1 0 0 1 0 0 11 1 1 1 0 0 0 a).若有若有n个变项，则有个变项，则有2n个极小项个极小项. b).每一个极小项有且只有一个成真赋值每一个极小项有且只有一个成真赋值.为了方便，可将各极小项分别记

3、作为了方便，可将各极小项分别记作m0,m1,m2,m2n-1上例中上例中, m0p q m1pq m2p q m3pq 3个命题变项，个命题变项，8个极小项对应情况如下：个极小项对应情况如下： p q r 000 0, 记作记作m0； p qr 001 1, 记作记作m1； p q r 010 2, 记作记作m2； p qr 011 3, 记作记作m3； p q r 100 4, 记作记作m4； p q r 101 5, 记作记作m5； p q r 110 6, 记作记作m6； p qr 111 7, 记作记作m7. 一般情况下一般情况下,n个命题变项共产生个命题变项共产生2n个极小项个极小项

4、,分别分别记为记为m0,m1,.m2n-1.2.2.主析取范式定义主析取范式定义 定义定义1.21 若公式若公式A的的析取范式中每个析取范式中每个简简单取式单取式都都是是极小项极小项，则该析取范式为，则该析取范式为A的的主析取范式主析取范式.定理定理 任何一个公式都有与之等值的主析取任何一个公式都有与之等值的主析取范式范式. . 3.3.主析取范式的求法：主析取范式的求法： 方法方法:等值演算法等值演算法 方法方法:真值表技术真值表技术 方法方法:等值演算法等值演算法求主析取范式求主析取范式的步骤的步骤:(1)求求A的析取范式的析取范式A；(2)若若A的某简单的某简单合取式合取式B中不含命题变

5、项中不含命题变项pi或其否定或其否定 pi,则将则将B展成如下形式：展成如下形式： B B1 B(pi pi) (Bpi)(B pi). (3)将重复出现的命题变项、将重复出现的命题变项、矛盾式矛盾式及重复出现的极及重复出现的极小项都小项都“消去消去”,如如pp用用p代代,p p用用0代代,mimi用用mi代代.(4)将极小项按将极小项按由小到大由小到大的顺序排列的顺序排列,并用并用表示之表示之.如如m1m2m5用用(1,2,5)表示表示.例例1.15 求求 (pq) r) p的主析的主析取范式取范式. 解：解：(pq) r) p p(q r) (例例1.14 已求出的析取范式已求出的析取范式

6、) p( qq) ( rr)( pp)(q r) (p q r)(p qr) (p q r)(p q r) ( pq r)(p q r) m4 m5 m6m7m2m6 m2m4m5m6m7 (2,4,5,6,7).练习练习 用等值演算法用等值演算法,求求(pq)r的主析取范式的主析取范式. 解解: (pq)r (pq)( rr)( pp)( qq)r) (pqr)(pq r) (pqr) (p qr)( pqr)( p qr) m7 m6 m7m5m3m1 m1m3m5m6m7 (1,3,5,6,7). 由极小项的定义可知由极小项的定义可知,上式中上式中,1,3,5,6,7的二进制表示的二进制

7、表示001,011,101,110,111为原公式的为原公式的成真赋值成真赋值,而此公式的主析而此公式的主析取范式中取范式中没出现的极小项没出现的极小项m0,m2,m4的角码的角码0,2,4的二进制表的二进制表示示000,010,100为原公式的为原公式的成假赋值成假赋值.若知道了一个命题公式若知道了一个命题公式A的主析取范式的主析取范式,可立即写出可立即写出A的真值表的真值表. 反之反之,若知道了若知道了A的真值表的真值表,找出所有的找出所有的成真赋值成真赋值,及其对应的及其对应的十进制数作为角码的十进制数作为角码的极小项极小项即为即为A的主析取范式中所含的全的主析取范式中所含的全部极小项部

8、极小项,从而可立即写出从而可立即写出A的主析取范式的主析取范式.方法方法:真值表技术真值表技术求主析取范式的步骤：求主析取范式的步骤：列出给定公式的真值表列出给定公式的真值表.找出真值表中每个找出真值表中每个“1”对应的极小项对应的极小项.用用“”联结上述极小项，即可联结上述极小项，即可. 例例1.16 : 试由试由pqr的真值表求它的主析取范式的真值表求它的主析取范式.解解：列出其真值表如下：列出其真值表如下： 于是于是 pqr m1m3m5m6m7 (1,3,5,6,7).练习练习 求公式求公式G=(pq)G=(pq)r r的主析取范式的主析取范式. .解解：列出其真值表如下：列出其真值表

9、如下： 将极小项全部进行析取后，可得到相应将极小项全部进行析取后，可得到相应的主析取范式：的主析取范式： G=(pq)G=(pq)r r m1m3m4 m7 (1,3,4,7) (pqr)(pqr)(pqr)(pqr) (pqr)(pqr) (pqr)(pqr)4、主析取范式的用途、主析取范式的用途 1).判断命题公式的类型判断命题公式的类型设设A是含是含n个命题变项的命题公式个命题变项的命题公式, A为重言式为重言式,当且仅当当且仅当A的主析取范式中含全部的主析取范式中含全部2n个极小项；个极小项； A为矛盾式为矛盾式,当且仅当当且仅当A的主析取范式中不含任的主析取范式中不含任何极小项何极小

10、项,可设可设A的主析取范式为的主析取范式为0； 若若A的主析取范式中至少含一个极小项的主析取范式中至少含一个极小项,则则A是是可满足式可满足式. 2).判断两命题公式是否等值判断两命题公式是否等值.A B当且仅当当且仅当A与与B有相同的主析取范式有相同的主析取范式.例例1.17 判断下列命题公式的类型判断下列命题公式的类型. (1) (pq)p)q； (2) (pq)q. (1)(pq)p) q ( pq)p)q (消去消去) ( pq) pq ( 内移内移) (p q) pq (得到析取范式得到析取范式) (pq)p(qq)(pp)q (加项加项) ( p q)( pq)(p q)(pq)

11、m0m1m2m3 (0,1,2,3). 由以上推演可知由以上推演可知,(1) 为重言式为重言式. (2)(pq)q ( pq)q ( pq)q (p p) ( pq)(pq) m1m3. (1,3). 由以上推演可知由以上推演可知,(2)为可满足式为可满足式.主主合取范式合取范式1.极大项极大项定义定义1.22:在一个有在一个有n个命题变项的简单析取式个命题变项的简单析取式中，每个变项或其否定必出现且仅出现一次中，每个变项或其否定必出现且仅出现一次(按按字典顺序字典顺序)，称这个简单析取式是个，称这个简单析取式是个极大项极大项. 例如，有两个变项时，例如，有两个变项时， 极大项极大项 成假赋值

12、成假赋值 记号记号 pq 000，记作，记作M0 p q 011，记作，记作M1 pq 102，记作，记作M2 p q 113，记作，记作M3 例如，有三个变项时，例如，有三个变项时， pqr 0000，记作，记作M0 pq r 0011，记作，记作M1 p qr 0102，记作，记作M2 p q r 0113，记作，记作M3 pqr 1004，记作，记作M4 pq r 1015，记作，记作M5 p qr 1106，记作，记作M6 p q r 1117，记作，记作M7 极大项的性质极大项的性质 同极小项情况类似同极小项情况类似,n个命题变项个命题变项可产生可产生2n个极大项个极大项,每个极大项

13、对应一个二进制每个极大项对应一个二进制数和一个十进制数数和一个十进制数.二进制数为该极大项二进制数为该极大项的的成假赋值成假赋值,十进制数作为该极大项抽象十进制数作为该极大项抽象表示的角码表示的角码. 2.主合取范式定义主合取范式定义 合合取范式取范式 A1A2. An, , 其中每个其中每个Ai (i=1,2.n)都都是是极大项，称之为极大项，称之为主合取范主合取范式式. 3.主合取范式的写法主合取范式的写法 方法方法：列真值表：列真值表 列出给定公式的真值表列出给定公式的真值表. 找出真值表中每个找出真值表中每个“0”对应的极大项对应的极大项. 用用“”联结上述极大项，即可联结上述极大项，

14、即可.例如例如 求求 pq和和p pq的的主合取范式主合取范式 p q pq p pq 0 0 1 1 0 1 1 0 1 0 0 0 1 1 1 1 pq pq M2 p pq (p q )( pq) M1M2 mi Mi, Mi mi. 设命题公式设命题公式A中含中含n个命题变项个命题变项,且设且设A的的主析取 范式中含k个极小项mil,mi2,mik则则 A的主析取的主析取 范式中必含范式中必含2n-k个极小项个极小项,设为设为mjl,mj2, , , 即即 A mjl mj2 A A (mjl mj2 ) mjl mj2 Mjl Mj2 22nknkjjMm22nknkjjMm22nk

15、nkjjMm22nknkjjMm极小项与极大项之间的关系极小项与极大项之间的关系方法方法:由由A的主析取范式求主合取范式的主析取范式求主合取范式 步骤步骤: (1)求出求出A的主析取范式中的主析取范式中没包含没包含的极小项的极小项mj1,mj2, . (2)求出与求出与(1)中极小项角码相同的极大项中极小项角码相同的极大项Mj1,Mj2, . (3)由以上极大项构成的合取式为由以上极大项构成的合取式为A的主合取范式的主合取范式.22nknkjjMm22nknkjjMm例如例如, A中含中含3个命题变项个命题变项,主析取范式为主析取范式为 A m0m1m5m7 (0,1,5,7)则主合取范式为则

16、主合取范式为 A M2M3M4M6 (2,3,4,6).练习练习 求求(pq)r的主合取范式和的主合取范式和主析取范式主析取范式.(pq)r ( pq)r(p q)r(pr)( qr) (p(q q)r)(p p) qr) (pqr) (p qr) (p qr)( p qr) (pqr) (p qr) ( p qr)M0M2 M6 (主合取范式主合取范式)m1m3m4m5 m7 (1,3,4,5,7) (主析取范式主析取范式)判定问题及判定方法判定问题及判定方法 方法方法1: 真值表法真值表法; 方法方法2: 等值演算法等值演算法. 方法方法3: 当命题变项的数目较多时当命题变项的数目较多时,

17、 可把可把命题公式化成标准型命题公式化成标准型(主析取范式和主合主析取范式和主合取范式取范式).使同一真值函数所对应的所有命使同一真值函数所对应的所有命题公式具有相同的标准型题公式具有相同的标准型.(三三). 范式的应用范式的应用 范式在逻辑设计方面有广泛的应用范式在逻辑设计方面有广泛的应用.例例1. 安排课表，教语言课的教师希望将课程安排安排课表，教语言课的教师希望将课程安排在第一或第三节；教数学课的教师希望将课程安在第一或第三节；教数学课的教师希望将课程安排在第二或第三节；教原理课的教师希望将课程排在第二或第三节；教原理课的教师希望将课程安排在第一或第二节安排在第一或第二节.如何安排课表，

18、使得三位如何安排课表，使得三位教师都满意教师都满意. 解：令解：令l1、l2、l3分别表示语言课排在第一、第二、分别表示语言课排在第一、第二、第三节第三节. m1、m2、m3分别表示数学课排在第一、第二、分别表示数学课排在第一、第二、第三节第三节. p1、p2、p3分别表示原理课排在第一、第二、分别表示原理课排在第一、第二、第三节第三节.三位教师都满意的条件是：三位教师都满意的条件是：(l1l3)(m2m3)(p1p2 ) 为真为真.将上式写成析取范式将上式写成析取范式(用分配律用分配律)得：得：(l1m2)(l1m3)(l3m2)(l3m3)(p1p2)(l1m2p1)(l1m3p1) (l

19、3m2p1)(l3m3p1) (l1m2p2)(l1m3p2) (l3m2p2)(l3m3p2) (l3m2p1) (l1m3p2 )可以取可以取(l3 m2p1)、(l1m3p2)为为1，得到两种排法得到两种排法.1.6 1.6 推理理论推理理论 推理推理就是根据一个或几个已知的判断得出一个就是根据一个或几个已知的判断得出一个新的判断的思维过程新的判断的思维过程. .称这些已知的判断为称这些已知的判断为前前提提. .得到的新的判断为前提的得到的新的判断为前提的有效结论有效结论. . 一、一、推理推理理论理论1. 定义定义 如果公式如果公式AB是是重言式，则称重言式，则称A A重言蕴重言蕴涵涵

20、B B，记作，记作AB. 例如例如 由由(p(pq)q是是重言式，重言式，可以得到可以得到 (p(pq)q 注：注：“”不是联结词，它是表示公式间的不是联结词，它是表示公式间的“永真蕴涵永真蕴涵”关系，也可以看成是关系，也可以看成是“推导推导”关关系系. .即即AB可以理解成由可以理解成由A A可推出可推出B B，即，即由由A为为真，可以推出真，可以推出B也为真也为真. 实际上，推理的过程就是证明是永真蕴实际上，推理的过程就是证明是永真蕴含式的过程，即令含式的过程，即令H H1 1，H H2 2，H Hn n是已知是已知的命题公式的命题公式( (前提前提) )，若有，若有 H H1 1HH2

21、2.H.Hn n C C 则称则称C C是是H H1 1，H H2 2，HHn n的的有效结论有效结论，简称，简称结论结论. .例1.19 (1) 如果天气凉快,小王就不去游泳.天气凉快.所以小王没去游泳. (2)如果我上街,我就去书店看看.我没上街.所以我没去书店.2.重言重言( (永真永真) )蕴涵式证明方法蕴涵式证明方法方法方法1 1. .利用定义，证明利用定义，证明AB是是重言式重言式. . A B AA B A B0 0 10 1 11 0 01 1 1先看一看先看一看A AB B的真的真值表，如果值表，如果A AB B为为真式，则真值表的真式，则真值表的第三组解释不会出第三组解释不

22、会出现现. .方法方法2.假设前件为真，推出后件也为真假设前件为真，推出后件也为真.例如例如 求证：求证： (p(p q) q 证明：证明： 设设p=1，p q=1，易得，易得 q=1 故推理正确。故推理正确。3.重要的重言蕴涵式重要的重言蕴涵式(教材第教材第23页页)1)A1)AA AB B 附加附加2)2) A ABBA A 化简化简3)3)( (A AB)B)A A B B 假言推理假言推理 4)4)( (A AB)B) B B A A 拒取式拒取式5)5)( (A AB)B) A A B B 析取三段论析取三段论6)(6)(A AB )(BB )(BC)C) ( (A AC ) C )

23、 假言三段论假言三段论7)7) ( (A A B )(B B )(B C)C)( (A A C )C ) 等价三段论等价三段论8)(8)(A AB )(CB )(CD)D)( A AC)C) B BD D 构造性二难规则构造性二难规则上述公式的证明都比较简单，可以用假设前件为上述公式的证明都比较简单，可以用假设前件为1，推出后件也为，推出后件也为1的方法证明的方法证明. 4 4 推理规则推理规则1)1)前提引入规则：可以在证明的任何时候引入前提引入规则：可以在证明的任何时候引入前提；前提；2)2)结论引入规则：在证明的任何时候，已证明结论引入规则：在证明的任何时候，已证明的结论都可以作为后续证

24、明的前提；的结论都可以作为后续证明的前提；3)3)置换规则：置换规则：在证明的任何时候，命题公式中的任在证明的任何时候，命题公式中的任何子命题公式都可以用与之等值的命题公式置换何子命题公式都可以用与之等值的命题公式置换. .4)4)假言推理规则：假言推理规则：P P，P PQ QQ Q5)5)附加规则：附加规则：P PP PQ Q；6)6)化简规则：化简规则：P P，Q QP P；7)7)拒取式规则：拒取式规则： Q Q，P PQ QP P；8)8)假言三段论规则：假言三段论规则：P PQ Q，Q QR RP PR R；9)9)析取三段论规则：析取三段论规则： P P，P PQ QQ Q；10

25、)10)构造性二难规则：构造性二难规则：P PQ Q，P PR R，Q QR RR R；11)11)合取引入规则：合取引入规则：P P，Q QP PQ Q二、二、 证明方法证明方法 1 1、直接证法直接证法( (构造证明法构造证明法) ) ( (就是从前提直接推出结论就是从前提直接推出结论) )例例1.201.20 构造下列推理的证明构造下列推理的证明. .前提：前提：p pq q，p pr r，q qs s结论：结论：s sr r证明：证明：( (1 1) )p pq q前提引入规则前提引入规则( (2 2) )p pr r前提引入规则前提引入规则( (3 3) )q qs s前提引入规则前

26、提引入规则( (4) )sr(1)(2)(3)(1)(2)(3)构造性二难构造性二难2 2间接证法间接证法 主要有如下两种情况主要有如下两种情况. .( (1 1) )附加前提证明法附加前提证明法有时要证明的结论以蕴涵式的形式出现，有时要证明的结论以蕴涵式的形式出现，即推理的形式结构为：即推理的形式结构为：( (A A1 1A A2 2A Ak k) )( (A AB B) )设设( (A A1 1A A2 2A Ak k) )为为S S, ,则上述推理可表示则上述推理可表示为证明为证明S S( (A AB B),),即证明即证明S S(A AB B) )为永为永真式真式. . 而而S S(A

27、 AB B) ) (S SA)A)B B，则可把，则可把R R作作为附加前提条件进行证明为附加前提条件进行证明. . 例例 用附加前提证明法证明下面推理用附加前提证明法证明下面推理. .前提：前提：p p(q qr r) )， s sp p，q q结论：结论：s sr r证明一：证明一：( (1 1) ) s sp p前提引入规则前提引入规则( (2 2) )s s 附加前提引入规则附加前提引入规则( (3 3) )p p( (1 1)()(2 2) )析取三段论规则析取三段论规则( (4 4) )p p(q qr r) )前提引入规则前提引入规则( (5 5) )q qr r( (3 3)(

28、)(4 4) )假言推理规则假言推理规则( (6 6) )q q前提引入规则前提引入规则( (7 7) )r r( (5 5)()(6 6) )假言推理规则假言推理规则练习练习 17(3)17(3) 1.17(2)1.17(2)求证求证p(qs),pp(qs),p r,q r,q rs rs 证明二证明二: : (1) p(qs) (1) p(qs) 前提引入规则前提引入规则 (2) q(ps) (1)(2) q(ps) (1)置换置换 (3) q (3) q 前提引入规则前提引入规则 (4) ps(4) ps (5) p (5) p r r 前提引入规则前提引入规则 (6) rp (5)(6

29、) rp (5)置换置换 (7) rs (4)(6)(7) rs (4)(6)假言三段论假言三段论 练习练习 已知：已知：pqpq，(q(q r)s r)s 求证：求证：( ( rr s)s) p p 证明：证明：(1) (1) rr s s 附加前提引入附加前提引入(2) (2) r (1) r (1) 化简化简 (3) (3) s (1) s (1) 化简化简 (4) (q(4) (q r)s r)s 前提引入前提引入(5) (5) (q(q r) (2)(4)r) (2)(4)拒取式拒取式(6) (6) qr (5)qr (5)置换置换(7) (7) q (2)(6)q (2)(6)析取

30、三段论析取三段论(8) pq (8) pq 前提引入前提引入(9) (9) p (7)(8)p (7)(8)拒取式拒取式( (2 2) )归缪法（略）归缪法（略）定义定义 设设G G1 1，G G2 2，G Gn n是是n n个命题公式，个命题公式，如果如果G G1 1G G2 2G Gn n是可满足式，则称是可满足式，则称G G1 1，G G2 2，G Gn n是相容的；是相容的； 如果如果G G1 1G G2 2G Gn n是矛盾式是矛盾式, ,称称G G1 1，G G2 2，G Gn n是不相容的是不相容的. . 例例1.231.23 p( p( ( (rs)s) q),p,q),p,

31、s s q 证明一证明一: : (1) (1) q q 否定结论否定结论引入规则引入规则 (2) q (1)(2) q (1)置换置换 (3) p(3) p( ( (rs)s) q) q) 前提引入规则前提引入规则 (4) p (4) p 前提引入规则前提引入规则 (5) (5) ( (rs)s) q (3)(4)q (3)(4)假言推理假言推理 (6) (6) rs (4)(5) s (4)(5) 拒取规则拒取规则 (7) s (6)(7) s (6)化简化简 (8) (8) s s 前提引入规则前提引入规则 (9) s(9) s s (7)(8) s (7)(8) 合取合取 例例1.231

32、.23 p(p( ( (rs)s) q),p,q),p, s s q 证明二证明二: : (1) p(1) p( ( (rs)s) q) q) 前提引入规则前提引入规则 (2) p (2) p 前提引入规则前提引入规则 (3) (3) ( (rs)s) q (1)(2)q (1)(2)假言推理假言推理 (4) (4) s s 前提引入规则前提引入规则 (5) (5) r r s (4)s (4)附加附加 (6) (6) ( (rs) s) （5 5）置换）置换 (7) (7) q (3)(6)(3)(6)假言推理假言推理 例例 pq,(pq,( qr)qr) r, r, ( ( ps)ps)s s 证明证