离散数学PPT课件-18范式.ppt

1-6.范式 范式就是命题公式形式的规范形式。分为析取范式与合取范式一一.定义:1.析取范式析取范式 公式A如果写成如下形式：A1A2.An (n1)其中每个Ai(i=1,2.n)是合取式，称之为A的析取范式 2.合取范式合取范式 公式A如果写成如下形式：A1A2.An (n1)其中每个Ai(i=1,2.n)是析取式，称之为A的合取范式可以看出:在析取范式与合取范式中只含有联结词,并且在命题变元之前 例如，PQ 的析取范式与合取范式：PQ(PQ)(PQ)-析取范式 PQ(PQ)(PQ)-合取范式注:PPP PPP P是合(析)取式.4.析取范式与合取范式的写法析取范式与合取范式的写法 先用相应的公式去掉先用相应的公式去掉和和。公式公式E16 PQPQ 公式公式E21 PQ(PQ)(P Q)公式公式E20 PQ(PQ)(QP)再用再用E16 PQ(PQ)(P Q)用公式的否定公式或摩根定律将用公式的否定公式或摩根定律将 后移到命题后移到命题变元之前。变元之前。A(P1,P2,Pn)A*(P1,P2,Pn)德德-摩根定律摩根定律 (PQ)P Q (PQ)P Q 用分配律、幂等律等公式进行整理，使之成用分配律、幂等律等公式进行整理，使之成为所要求的形式。为所要求的形式。例如求(PQ)R的析取范式与合取范式(PQ)R (PQ)(PQ)R(PQ)(PQ)R -析取范式(PQ)R(PQ)(PQ)R(PQ)(PQ)R(PQR)(PQR)-合取范式 请同学阅读一下17页的例1.14二.主析取范式与主合取范式 一个公式的析取范式与合取范式的形式是不唯一的。下面定义形式唯一的主析取范式与主合取范式。主析取范式主析取范式 1.小项 定义：是n个命题变元的合取式，其中每个变元必出现且仅出现一次，称这个合取式为小项。例如，有两个变元的小项：PQ、PQ、PQ、PQ小项可编码:用1表变元本身,0表变元的 否定形式,则m00 P Q m01 PQ m10P Q m11PQ(2)小项的性质小项的性质 m11 m10 m01 m00 P Q PQ P Q PQ P Q 00 F F F F F T 01 F T F F T F 10 T F F T F F 11 T T T F F F a).有有n个变元，则有个变元，则有2n个小项。个小项。b).每个小项当且仅当其真值指派与编码相同时每个小项当且仅当其真值指派与编码相同时,其真值为其真值为T;其余其余2n-1组真值指派均使该小项的组真值指派均使该小项的 真值为真值为F。c).c).全体小项的析取式为永真式全体小项的析取式为永真式,记为记为:mmi i=m=m0 0 mm1 1 m m2n-1 T2.主析取范式定义 若一个命题公式的析取范式为A1A2.An,其中每个Ai(i=1,2.n)都是小项，则称之为该命题公式的主析取范式。3.主析取范式的写法 方法：列真值表 列出给定公式的真值表。找出真值表中该公式的每个为“T”行的真值指派所对应的小项。用“”联结上述小项，即可。i=02n-1例如求 PQ和PQ的主析取范式 P Q PQ PQ F F T T F T T F T F F F T T T T PQ m00m01m1111 (PQ)(PQ)(PQ)PQm00m11 (PQ)(PQ)思考题:永真式的主析取范式是什么样？方法：用公式的等价变换先写出给定公式的析取范式 A1A2.An。为使每个Ai都变成小项，对缺少变元的Ai补全变元，比如缺变元R，就用联结永真式(RR)形式补R。用分配律等公式加以整理。PQPQ(P(QQ)(P P)Q)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)主主合取范式合取范式1.大项大项定义:是n个命题变元的析取式，其中每个变元必出现且仅出现一次,称之为大项 例如，有两个变元的大项及其真值表：M0 0 M01 M10 M11 P Q PQ PQ PQ PQ00 F F F T T T 01 F T T F T T10 T F T T F T11 T T T T T F可看出大项的编码正好与小项相反:用0表变元本身,1表变元的否定形式M0 0PQ M01 PQ M10 PQ M11 PQ大项的性质 a).有n个变元，则有2n个大项。b).每个大项当且仅当其真值指派与编码相每个大项当且仅当其真值指派与编码相同时同时,其真值为其真值为F;其余其余2n-1组真值指派均组真值指派均使该大项的使该大项的 真值为真值为T。c).全体大项的合取式必为永假式 Mi =M0 M1M2n-1 Fi=02n-12.主合取范式定义 若一个命题公式的合取范式 为A1A2.An,其中每个Ai(i=1,2.n)都是大项，则称之为该命题公式的主合取范式。3.主合取范式的写法 方法：列真值表 列出给定公式的真值表。找出真值表中该公式的每个为“F”行的真值指派所对应的大项。用“”联结上述大项，即可。例如求 PQ和PQ的主合取范式 P Q PQ PQ F F T T F T T F T F F F T T T T PQ M10 PQ PQ M01M10 (PQ)(PQ)课堂练习课堂练习：1.已知已知A(P,Q,R)的真值表如图：的真值表如图：求它的主析取和主合取范式。求它的主析取和主合取范式。2.已知已知A(P,Q,R)的主析取范式中含有下面小项的主析取范式中含有下面小项m1,m3,m5,m7求它的主合取范式求它的主合取范式.P Q R A(P,Q,R)F F F TF F T FF T F FF T T TT F F TT F T FT T F TT T T T练习答案：练习答案：1.A(P,Q,R)的主析取范式的主析取范式:A(P,Q,R)m000m011m100m110m111 (P Q R)(PQR)(P Q R)(PQ R)(PQ R)A(P,Q,R)的的主合取范式：主合取范式：A(P,Q,R)M001M010M101(PQ R)(P QR)(PQ R)2.A(P,Q,R)M0M2M4 M6 M000M010M100 M 110(PQR)(P QR)(PQR)(P QR)方法：用公式的等价变换先写出给定公式的合取范式 A1A2.An。为使每个Ai变成大项，对缺少变元的析取式Ai补全变元，比如缺变元R，就用联结永假式(RR)形式补R。用分配律等公式加以整理。例如，求(PQ)R的主合取范式(PQ)R(PQ)R(PQ)R(PR)(QR)(P(QQ)R)(PP)QR)(PQR)(PQR)(PQR)(PQR)例1.安排课表，教语言课的教师希望将课程安排在第一或第三节；教数学课的教师希望将课程安排在第二或第三节；教原理课的教师希望将课程安排在第一或第二节。如何安排课表，使得三位教师都满意。令L1、L2、L3分别表示语言课排在第一、第二、第三节。M1、M2、M3分别表示数学课排在第一、第二、第三节。P1、P2、P3分别表示原理课排在第一、第二、第三节。三位教师都满意的条件是：(L1L3)(M2M3)(P1P2)为真。将上式写成析取范式(用分配律)得：(L1M2)(L1M3)(L3M2)(L3M3)(P1P2)(L1M2P1)(L1M3P1)(L3M2P1)(L3M3P1)(L1M2P2)(L1M3P2)(L3M2P2)(L3M3P2)可以取(L3 M2P1)、(L1M3P2)为T，得到两种排法。本节要掌握：析取范式、合取范式、主析取范式、主合取范式的写法，范式的应用。作业 第34页：1.12 1.13 1.19 1.20