离散 范式PPT课件

1、-1-第11讲 范式vPowerPoint Template_Sub 1命题与逻辑联结词2逻辑等价式和逻辑蕴涵式3范式4证明技术（补充）第1页/共31页范式离散数学第11讲Textbook Page 71 to 74文字、子句、互补文字对的概念析取范式与合取范式主范式联结词的扩充与规约 第2页/共31页-3-第11讲 范式要解决的问题 给定命题变元个数n，有无穷多个含有n个命题变元的命题公式，但只有有限多张这样的真值表 很多命题公式是互相逻辑等价的,是否它们有公共的标准形式 希望有一种规范的方法解决下面两个问题： 判定任意一个命题公式是否为永真式或永假式 判断任意两个命题公式是否等价第3页/共

2、31页-4-第11讲 范式有关术语 文字（letter）：是指命题常元、变元及它们的否定，如p，p。前者又称正文字，后者又称负文字。 析取子句（disjunctive clause）：指文字或文字的析取。例：p，p，pq等。 合取子句（conjunctive clause）：指文字或文字的合取。例：p，p，pp，pqr等。 互补文字对（complemental pair of letter）：指形如p、p的一对文字。第4页/共31页-5-第11讲 范式关于子句的真值 析取子句A1A2 Am为永真式，当且仅当子句中含有互补文字对Ai和 Ai 。 合取子句A1A2 Am为永假式，当且仅当子句中含有

3、互补文字对Ai和 Ai 。第5页/共31页-6-第11讲 范式析取范式 (disjunctive normal form) 定义4.6 ：命题公式A称为公式A的析取范式，如果 （1）A A （2）A为一合取子句或若干合取子句的析取(pq)r的析取范式： (pq)r (pq) p) q (p q) p) q (p p) ( q p) q p(qp) q析取范式的形式为： (. .) (. .) (. .) 第6页/共31页-7-第11讲 范式合取范式 (conjunctive normal form) 定义4.7 ：命题公式A称为公式A的合取范式，如果 （1）A A （2）A为一析取子句或若干析

4、取子句的合取pq pq，合取范式，也是析取范式 (pq)p)q (pq)p)q (pq)q)( pq) pq 合取范式(pq)r (p r)(qr)合取范式的形式为： (. .)(. .)(. .) 第7页/共31页-8-第11讲 范式求析取范式和合取范式p(pq) p(pq) 合取范式 (pp)(pq) 析取范式 pq 合取范式 析取范式例 4.21 p(pq) p(pq) p(pq) (pt)(pq) p (t q) p此为析取范式 (pp)(pq) p(pq) (pf)(pq) p(fq) p 这就是合取范式第一步，消去 和第二步，将向内深入，使之只作用于命题变元 或命题变元的否定，然后

5、把p化为p第三步，利用分配律进一步将公式化为所需要的范式第8页/共31页-9-第11讲 范式由析取范式判断永假式 在一命题公式的析取范式中，如果每一合取子句均为永假式，则这一命题公式也为永假式 而要看一个合取子句是否为永假式，只需看其中是否含有互补文字对 因此，只要求出公式的析取范式，就可以判断该公式是否为永假式析取范式为： (. .) (. .) (. .) 第9页/共31页-10-第11讲 范式由合取范式判断永真式 在一个命题公式的合取范式中，如果每一析取字句均为永真式，则这个命题公式也为永真式 而每一析取字句是否是永真式，只需看其中是否含有互补文字对 因此，只要求出公式的析取范式，就可以

6、判断该公式是否为永真式合取范式为： (. . . . .) (. . . . .) (. . . . .) 第10页/共31页-11-第11讲 范式不足 到目前为止，要判定一个命题公式是永真式、永假式还是可满足式的问题，可以说是解决了。将该命题公式的析取范式或合取范式求出来一看便可以知道了 但是，如何来判定两个命题公式是否等价的问题仍未解决。因为从前面的例子可以看到，对于同一个命题公式，它的范式并不是惟一的, 且可能合一。所以不能通过两个命题公式的范式来判定两个命题公式是否等价。为此，引入主范式的概念第11页/共31页-12-第11讲 范式主析取范式 定义4.8 设A为恰含有n个命题变元p1,

7、pn的公式。公式A称为A的主析取范式，如果A是A的析取范式，并且其每个合取子句中p1,pn均恰出现一次。p(pq) p(pq) p(pq) 析取范式 (p (q q)(pq) (p q) (p q)(pq) (p q) (p q) 主析取范式第12页/共31页-13-第11讲 范式主合取范式 定义4.8 设A为恰含有n个命题变元p1,pn的公式。公式A称为A的主合取范式，如果A是A的合取范式，并且其每个析取子句中p1,pn均恰出现一次。p(pq) p(pq) p(pq) (p p ) (p q) p(pq) 合取范式 (p (qq)(pq) (pq)(pq)(pq) (pq)(pq) 主合取范

8、式第13页/共31页-14-第11讲 范式例4.23 求公式(pq)r的主析取范式及主合取范式。 (pq)r (pq(rr)(pp)(qq)r) (pqr)(pqr)(pqr)(pq r)(pqr)(pqr) (pqr)(pqr)(pqr)(p qr)(pqr) 第14页/共31页-15-第11讲 范式(pq)r (pr)(qr) (p(qq)r)(pp)qr) (pqr)(pqr)(pqr)(pqr) (pqr)(pqr)(pqr)第15页/共31页-16-第11讲 范式思考 每一合取子句中，让负文字中的命题变元取真值0，正文字中的命题变元取真值1，那么这一组指派使合取子句取真值1 只要有一

9、个合取子句是真的，整个命题公式就取真的真值 主析取范式中的每个合取子句对应着一个弄真命题公式指派 p(pq) (p q) (p q) 主析取范式 可通过公式的真值表求其主析取范式 一个命题公式的真值表是唯一的，其主析取范式也是唯一的。(1,1)(1,0)第16页/共31页-17-第11讲 范式由主析取范式获得弄真指派(pq)r pqrp q(p q) r 0000000101010000110110000101011101111111(0,0,1)(0,1,1)(1,0,1)(1,1,0)(1,1,1)pqrpqrpqrpqrpqr(pqr)(pqr)(pqr)(pqr) (pqr)(0,0,

10、1)(0,1,1)(1,0,1)(1,1,0)(1,1,1)让负文字中的命题变元取真值0，正文字中的命题变元取真值1，那么这一组指派使合取子句取真值1只要有一个合取子句是真的，整个命题公式就取真的真值主析取范式中的每个合取子句对应着一个弄真命题公式指派第17页/共31页-18-第11讲 范式思考 每一析取子句中，让负文字中的命题变元取真值1，正文字中的命题变元取真值0，那么这一指派使析取子句取真值0 只要有一个析取子句是假的，整个命题公式就取假的真值 主合取范式中的每个析取子句对应着一个弄假命题公式的指派 p(pq) (pq)(pq) 主合取范式 可通过公式的真值表求它的主合取范式 一个命题公

11、式的真值表是唯一的，其主合取范式也是唯一的(0,0)(0,1)第18页/共31页-19-第11讲 范式由主合取范式获得弄假指派(pq)r pqrp q(p q) r 0000000101010000110110000101011101111111(0,0,0)(0,1,0)(1,0,0)p qrpqrpqr(p qr) (pqr) (pqr)(0,0,0)(0,1,0)(1,0,0)让负文字中的命题变元取真值1，正文字中的命题变元取真值0，那么这一指派使析取子句取真值0只要有一个析取子句是假的，整个命题公式就取假的真值主合取范式中的每个析取子句对应着一个弄假命题公式的指派第19页/共31页-2

12、0-第11讲 范式由真值表得到主析取、主合取范式pqrS00000011010101101001101011011110使公式S为真的指派有：(0,0,1)、(0,1,0)、(1,0,0)、(1,1,0)S的主析取范式为(pqr)(pqr)(pqr) (pqr)使公式S为假的指派有：(0,0,0)、(0,1,1)、(1,0,1)、(1,1,1)S的主合取范式为(pqr) (pqr) (pqr) (pqr)第20页/共31页-21-第11讲 范式由真值表得到主合取、主析取范式pqrS00010010010101101000101111011110使公式S为真的指派有：(0,0,0)、(0,1,0

13、)、(1,0,1)、(1,1,0)使公式S为假的指派有：(0,0,1)、(0,1,1)、(1,0,0)、(1,1,1)S的主合取范式为(pqr) (pqr) (pqr) (pqr)S的主析取范式为(pqr)(pqr)(pqr) (pqr)第21页/共31页-22-第11讲 范式永假式和永真式 由于永假式没有成真指派，所以永假式没有主析取范式。为方便起见，将其记为f。 由于永真式没有成假指派，所以永真式没有主合取范式。为方便起见，将其记为t。 第22页/共31页-23-第11讲 范式等价命题公式类 由n个命题变元可以组成无限个命题公式 每一命题公式均与一个主析取范式（或主合取范式）等价，与同一个

14、主析取范式（或主合取范式）等价的所有公式就组成一个等价类。 共有22n个等价类 第23页/共31页-24-第11讲 范式联结词的扩充 n个变元的真值表共有22n张，因此可以定义22n个n元联结词 p1(p)2(p)3(p)4(p)0001110101第24页/共31页-25-第11讲 范式16个二元联结词p qp*1qp*2qp*3qp*4qp*5qp*6qp*7qp*8q0 0000000000 1000011111 0001100111 101010101p qp*9qp*10qp*11qp*12qp*13qp*14qp*15qp*16q0 0111111110 1000011111 00

15、01100111 101010101合取析取双向蕴涵蕴涵第25页/共31页-26-第11讲 范式联结词的规约 定义4.9 ：称n元联结词h是用m个联结词g1, g2, , gm可表示的，如果能找到一个仅含联结词g1, g2, , gm的命题公式A，使得： h(p1，p2，pn) A第26页/共31页-27-第11讲 范式联结词的规约 一元联结词都是，可表示的。p1(p)2(p)3(p)4(p)00011101011(p) f, 2(p) p, 3(p) p, 4(p) t同样可知道，二元联结词都是，可表示的 第27页/共31页-28-第11讲 范式完备联结词组 定义4.10 ：当联结词组g1，g2，gm可表示所有一元、二元联结词时，称为完备联结词组，或联结词的全功能集（complete group of connectives）根据以上讨论可知，是完备联结词组 ，也是完备联结词组 由于，可利用来相互表示 ，、及、都构成完备联结词组 此外，及1，分别构成完备联结词组 ，及，都不是完备的 第28页/共31页-29-第11讲 范式完备联结词组 证明一个联结词组完备的方法为：选取一个已知的完备联结词组，证明该组中每一