离散数学I省名师优质课赛课获奖课件市赛课一等奖课件.ppt

,*,/73,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,离散数学 I,肖明军,Web:zhh1000,1/91,引言,课程介绍,离散数学是当代数学一个主要分支，是计算机科学中基础理论关键课程，它,研究对象是有限个或可数离散量,。充分描述了计算机科学离散性特征。,离散数学是传统逻辑学、集合论、数论基础、算法设计、组合分析、离散概率、关系理论、图论与树、抽象代数、布尔代数、计算模型等聚集起来一门综合学科。离散数学应用遍布当代科学技术很多领域。,离散数学是伴随计算机科学发展而逐步建立起来一门新兴工具性学科，形成于七十年代。,2/91,引言,课程意义,离散数学是计算机科学数学基础，其基本概念、理论、方法大量地应用在数字电路、编译原理、数据结构、操作系统、数据库系统、算法设计、人工智能、计算机网络等专业课程中，是这些课程基础课程。,离散数学学习十分有益于概括抽象能力、逻辑思维能力、归纳结构能力提升，能够培养提升学生数学思维能力和对实际问题求解能力。,教学内容,数理逻辑,、,集合论,、,代数结构,、图论,3/91,引言,教学内容,第一部分 数理逻辑,第一章 命题逻辑,第二章 谓词逻辑,第二部分 集合论,第三章 集合代数,第四章 二元关系,4/91,引言,教学内容,第二部分 集合论,第五章 函数,第六章 集合基数,第三部分 代数结构,第七章 代数系统,第八章 群论,5/91,引言,教学内容,第三部分 代数结构,第九章 环与域,第十章 格与布尔代数,6/91,第一部分 数理逻辑,逻辑学,是一门研究思维形式和规律科学。分为辩证逻辑和形式逻辑两种。思维形式结构包含了,概念,判断,和,推理,之间结构和联络，其中,概念,是思维基本单位，经过概念对事物是否含有某种属性进行必定或否定回答，就是,判断,。由一个或几个判断推出另一判断思维形式就是,推理,。,数理逻辑,用数学方法研究推理规律称为数理逻辑。所谓数学方法就是引用一套符号体系方法，所以数理逻辑又称作符号逻辑。,7/91,第一部分 数理逻辑,当代数理逻辑,逻辑演算、逻辑演绎、模型论、证实论、递归函数论、公理化集合论等。,我们要介绍是数理逻辑中最基本内容：命题逻辑和谓词逻辑。即普通所谓古典逻辑。,德国数学家莱布尼茨,Leibniz（当代逻辑首席创始人）；布尔Boole（奠基人，逻辑数学分析）；弗雷格（数论基础）,8/91,第一章 命题逻辑,命题逻辑也称命题演算或语句逻辑。它研究以“,命题,”为基本单位组成前提和结论之间可推导关系，研究什么是命题？怎样表示命题？怎样由一组前提推导一些结论。,概念,判断,推理,9/91,1.1 命题与命题联结词,1.1.1命题,定义1.1,：含有,确切真值陈说句,(或断言)称为命题(Proposition)。,命题取值称为真值。真值只有“真”和“假”两种，分别用“T”或“1”和“F”或“0”表示。,注意：命题真值非真即假，只有两种取值，这么系统为二值逻辑系统。,10/91,1.1 命题与命题联结词,例1-1：命题示例。,(a):今天下雪(b):3+3=6,(c):2是偶数而3是奇数,(d):陈胜起义那天，杭州下雨,(e):较大偶数都可表为两个质数之和,(f):x+y4(g):真好啊!(h):x=3,(i):你去哪里？(j):我正在说谎。,注意：,由定义知，一切没有判断内容句子如命令，感叹句，疑问句，祈使句，二义性陈说句等都不能作为命题。,11/91,1.1 命题与命题联结词,例1-2：以下句子哪些是命题，判断命题真假。,(1):2是素数(2):北京是中国首都,(3):这个语句是假,(4):x+y0(5):我喜欢踢足球,(6):地球外星球上也有些人,(7):明年国庆节是晴天,(8):把门关上,(9):你要出去吗？,(10):今天天气真好啊！,12/91,注意,命题一定是经过陈说句来表示；反之，并非一切陈说句都一定是命题。,命题真值有时可明确给出，有时还需要依靠环境条件，实际情况，时间才能确定其真值。但其真值一定是唯一确定。,1.1 命题与命题联结词,13/91,1.1 命题与命题联结词,命题可分为两种类型：,简单命题：,若一个命题已不能分解成更简单命题，则该命题叫原子命题或本原命题或简单命题（Simple Proposition）,复合命题,（Compound Proposition）：能够分解为简单命题命题，而且这些简单命题之间是经过关联词（如“或者”,“而且”,“不”，“假如 则”,“当且仅当”等）和标点符号复合而组成一个复合命题。,例，合肥是安徽省会当且仅当鸟会飞。,注意：,命题通惯用大写英文字母（可带下标）来表示。,14/91,1.1.2 命题联结词,命题通常能够经过一些联结词复合而组成新命题，这些联结词被称为逻辑联结词。用数学方法研究命题之间逻辑关系时（也就是在命题演算中），这些联结词能够看作是运算符，所以也叫作逻辑运算符。,惯用联结词有以下5个：,定义1.2：,设P是任一命题，复合命题“非P”（或“P否定”）称为P否定式（Negation），记作P，“”为否定联结词。P为真当且仅当P为假。,如：P：2是素数，则P：2不是素数。,1.1 命题与命题联结词,15/91,1.1 命题与命题联结词,定义1.3：,设P Q是任意两个命题，复合命题“P而且Q”（或“P和Q”）称为P与Q合取式（Conjunction），记作P Q，“”为合取联结词。P Q为真当且仅当P，Q同为真。,例，P：2是素数，Q：2是偶数。则P Q：2是素数而且是偶数。,16/91,1.1 命题与命题联结词,定义1.4：,设P Q是任意两个命题，复合命题“P或Q”称为P与Q析取式（Disjunction），记作P Q，“”为析取联结词。P Q为真当且仅当P，Q最少一个为真。,例，P：2是素数，Q：2是奇数。则P Q：2是素数或是奇数。,17/91,1.1 命题与命题联结词,定义1.5：,设P Q是任意两个命题，复合命题“假如P则Q”称为P与Q蕴含式（Implication），记作P,Q，“,”为 蕴含联结词，P称为蕴含式前提，假设或前件，而Q称为结论式后件。P,Q为假当且仅当P为真Q为假。,例，P：G是正方形，Q：G四边相等，则P,Q：假如G是正方形，则G四边相等。,蕴含式P,Q能够用各种方式陈说：,“若P，则Q”;“P是Q充分条件”;“Q是P必要条件”;“Q每当P”;“P仅当Q”等。,18/91,1.1 命题与命题联结词,给定命题PQ，我们把QP，PQ，QP分别叫作命题PQ逆命题，反命题和逆反命题。,定义1.6：,设P，Q是任意两个命题，复合命题“P当且仅当Q”称为P与Q等价式(Equivalence)，记作PQ，“”为等价联结词。PQ为真当且仅当P，Q同为真假。,比如，P：合肥是安徽省会，Q：鸟会飞，则PQ：合肥是安徽省会当且仅当鸟会飞。,假如PQ是真，则PQ和QP是真，反之亦然，所以PQ也读作“P是Q充要条件”或“P当且仅当Q”。,19/91,1.1 命题与命题联结词,五个联结词真值表,联结词,记号,表示式,读法,真值结果,否定,P,非P,P为真当且仅当P为假,合取,P Q,P且Q,P Q为真当且仅当P，Q同为真,析取,P Q,P或Q,P Q为真当且仅当P，Q最少一个为真,蕴含,PQ,若P则Q,PQ为假当且仅当P为真Q为假,等价,PQ,P当且仅当Q,PQ为真当且仅当P，Q同为真假,20/91,1.1 命题与命题联结词,普通约定：,a)：运算符(联结词)结协力强弱次序为：，；凡符合此次序，括号可省略。,b)：相同运算符，从左到右次序计算时，括号可省去。,c)：最外层括号可省。,如，(P Q)R)(R P)Q),(P QR)R PQ,21/91,例1.3：符号化以下命题。,a)：他现有理论知识又有实践经验,b)：i.假如明天不是雨夹雪则我去学校,ii.假如明天不下雨而且不下雪，则我去学校,iii.假如明天下雨或下雪则我不去学校,iv.明天我将风雨无阻一定去学校,v.当且仅当明天不下雪而且不下雨时我才去学校,1.1 命题与命题联结词,22/91,1.1 命题与命题联结词,c)：说小学生编不了程序，或说小学生用不了个人计算机，那是不正确。,d)：若不是他生病了或出差了，我是不会同意他不参加学习。,e)：假如我上街了，我就去书店看看，除非我很累。,23/91,1.1 命题与命题联结词,注意：,是自然语言中“非”“不”和“没有”等逻辑抽象,是自然语言中“而且”“既 又”“且”“和”等逻辑抽象,是自然语言中“或”和“或者”等逻辑抽象；但“或”有“可兼或”“不可兼或”“近似或”三种,P,Q是自然语言中“只要P，就Q”“因为P，所以Q”“P仅当Q”等逻辑抽象,24/91,(5)是自然语言中“充分必要条件”和“当且仅当”等逻辑抽象,(6)联结词连接是两个命题真值之间联结，而不是命题内容之间连接，所以复合命题 真值只取决于组成他们各原子命题真 值,(7)，含有对称性，而，没有,(8)，与计算机中与门，或门，非门电路是相对应,看P6-7 例1.4-1.5，P9 例1.7,1.1 命题与命题联结词,25/91,1.2.1：命题公式,就像在代数学里引入变量一样，为了更广泛应用命题演算，在数理逻辑中也引入了命题变量。使得在研究时，只需考虑命题真值，而不知晓命题详细含义。,定义1.7：,一个特定命题是一个常值命题(Constant Proposition)，它不是含有值“T”(“1”)，就是含有值“F”(“0”)。而一个任意没有赋予详细内容原子命题是一个变量命题，常称它为命题变量(或命题变元、命题变项)(Proposition Variable)。命题变量无详细真值，它值域是集合T，F(或1，0)。,1.2 公式解释与真值表,26/91,原子命题在不指派真值时称为命题变元，而复合命题由原子命题和联结词组成，能够看作是命题变元函数，且该函数值仍为“真”或“假”，能够称为真值函数（True Value Function）或命题公式。但不是说原子命题和联结词一个随便组合都能够为命题公式，我们用递归方法来定义命题公式。,1.2 公式解释与真值表,27/91,1.2 公式解释与真值表,定义1.8：命题公式,(1).命题变元本身是一个公式；,(2).假如P是公式，则P也是公式；,(3).假如P，Q是公式，则(,PQ)PQ P,Q PQ也是公式；,(4).命题公式(Prepositional Formula)是仅由有限步使用规则(1)(3)后产生结果。公式惯用符号G,H等表示。,例，(PQ)，(P(P Q)，(PQ)(R Q)(P R)是命题公式,(P Q)Q)，(P Q，(PQ(R，PQ 不是命题公式,28/91,注意：,假如G是含有n个命题变元 P,1,P,2,P,n,公式，通常记为G（P,1,P,n,）或简记为G。,原子命题变元是最简单（合式）公式，也叫原子（合式）公式。,合成公式没有真值，只有对其变元进行指派后才有真值。,合成公式无限多。,1.2 公式解释与真值表,29/91,1.2 公式解释与真值表,合式公式层次：,(1).若公式A是一单个命题变项，则称A为0层公式；,(2).称A是n+1(n0)层公式只需满足以下情况只一：,a).A=B，B是n层公式；,b).A=BC，其中B，C分别为i层和j层公式,且n=max(i,j)；,c).A=BC，其中B，C层次同b；,d).A=BC，其中B，C层次同b；,e).A=B,C，其中B，C层次同b；,从图论观点来看每个多层公式能够用一个“树”来表示。,30/91,1.2 公式解释与真值表,1.2.2：公式解释与真值表,公式本身没有真值，只有在对其全部命题变元指定真值后才变成一个含有真值命题。,定义1.9：,设命题变元P,1,P,2,P,n,是出现在公式G中全部命题变元，指定P,1,P,2,P,n,一组真值，则这组这组称为G一个解释(Explanation),并记作I。,普通来说，若有n个命题变元，则应有2,n,个不一样解释。,定义1.10：,公式G在其全部可能解释下所取真值表，称作G真值表(Truth)。,31/91,1.2 公式解释与真值表,例1.4：,5个联结词真值表(T：1，F：0),P,Q,P,P,Q,P Q,PQ,PQ,0,0,1,0,0,1,1,0,1,1,0,1,1,0,1,0,0,0,1,0,0,1,1,0,1,1,1,1,32/91,1.2 公式解释与真值表,例1.5：,设公式G=,(PQ)R)(PQ)，其中P，Q，R是G命题变元，则其真值表以下：,P,Q,R,PQ,(PQ)R,PQ,(PQ)R)(PQ),0,0,0,0,1,1,1,0,0,1,0,1,1,1,0,1,0,0,1,0,0,0,1,1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,0,1,0,0,1,1,0,1,0,1,0,1,1,1,1,1,0,0,33/91,1.2 公式解释与真值表,1.2.3：一些特殊公式,例1.6：,考虑：G1=,(PQ)P；,G2=(PQ)P；,G3=(P Q)(PQ),公式G1对全部可能解释都含有“真”值，G3对全部解释都含有“假”值，公式G2则含有“真”和“假”值。,34/91,1.2 公式解释与真值表,1.重言式：,定义1.11：,(1).公式G称为永真公式（重言式），假如在它全部解释下都为“真”；,(2).公式G称为可满足，假如它不是永假；,(3).公式G称为永假公式（矛盾式）,假如在它全部解释下都为“假”;有时也称永假公式为不可满足公式。,注意：,(1).重言式否定是矛盾式，矛盾式否定是重言式，所以研究其一就能够了；,35/91,1.2 公式解释与真值表,(2).重言式合取，析取，蕴含，等值等都是重言式；,(3).重言式中有许多非常有用恒等式叫永真蕴含式。,对任意公式，判定其是否为永真公式，永假公式，可满足公式问题称为给定公式,判定问题,。因为一个命题公式解释数目是有穷，所以命题逻辑判定问题是可解，即命题永真，永假性是可判定。其判定方法有,真值表法,和,公式推演法,。,36/91,1.2 公式解释与真值表,例1.7：,判定公式：,(1).(,PQ)(PQ);,(2).(PQ)P)Q；,(3).P(Q R)。,2.恒等式：,定义1.12：,公式G，H，假如在其任意解释下，其真值相同，则称G是H等价式(Equivalent)或称G恒等于H，记作G,H。,37/91,1.2 公式解释与真值表,定理1.1：,对于公式G和H，G,H充分必要条件是公式G H是重言式。,证实：,必要性：,假定G,H，则G和H在其任意解释I下，或同为真或同为假，由“”意义知，G H在任意解释I下，其真值为真，即G H为重言式；,充分性：,假设公式G H是重言式，I是它任意解释，在I下，G H为真，所以，G，H或同为真或同为假，因为I任意性，故有G,H。,38/91,1.2 公式解释与真值表,注意,与不一样：,(1).,：逻辑等价关系，G,H不是命题公式；,(2).：逻辑联结词，G H是命题公式；,(3).计算机不能判断G，H是否逻辑等价，而可计算G H是否为重言式。,39/91,1.2 公式解释与真值表,惯用逻辑恒等式（P，Q，R为任意命题，T为真命题，F为假命题）：,E1,PP,双否定,E2,PPP,幂等律,E3,PPP,幂等律,E4,PQQP,交换律,E5,PQQP,交换律,E6,(PQ)RP(QR),结合律,E7,(PQ)RP(QR),结合律,E8,P(QR)PQPR,在上分配律,E9,P(QR)(PQ)(PR),在上分配律,E10,(PQ)PQ,德摩根定律,E11,(PQ)PQ,40/91,1.2 公式解释与真值表,E12,P(PQ)P,吸收律,E13,P(PQ)P,E14,(PQ)PQ,蕴含等值式,E15,(PQ)(PQ)(QP),等价等值式,E16,PTT,零律,E17,PFF,E18,PFP,同一律,E19,PTP,E20,PPT,排中律,E21,PPF,矛盾律,E22,(PQR)(P(QR),输出律,E23,(PQ)(PQ)P,归谬律,E24,(PQ)QP,逆反律,41/91,1.2 公式解释与真值表,3.永真蕴含式：,定义1.13：若AB是一永真式，那么称为永真蕴含式，记为A,B，读作A永真蕴含B,惯用永真蕴含式,I1,P=PQ,I2,PQ=P,I3,P(PQ)=Q,I4,(PQ)Q=P,I5,P(PQ)=Q,I6,(PQ)(QR)=(PR),I7,(PQ)=(QR)(PR),I8,(PQ)(RS)=(PRQS),I9,(PQ)(RS)=(PR),42/91,1.2 公式解释与真值表,4.恒等式和永真蕴含式两个性质：,(1).若AB，BC，则AC；若A=B，B=C，则A=C.(即逻辑恒等和永真蕴含都是可传递),证实：AB，BC，即AB，BC为重言式，对任意解释I，A和B，B和C真值相同，则A和C真值相同。,A C为重言式，即AC；,A=B，B=C，即AB，BC为真；,(AB)(BC)为真，由公式I6：AC为重言式，即A=C。,43/91,1.2 公式解释与真值表,(2).若A=B，A=C，则A=BC.,证实：A为真时，B，C都为真，则BC也为真，即ABC为真；A为假时，则不论BC是真还是假时，ABC均为真，所以A=BC。,44/91,1.2 公式解释与真值表,1.2.4：代入规则和替换规则,当一个公式是永真式或永假式时，其公式真值完全跟随其命题变元真值改变而改变，所以，当用其它公式来取代公式中命题变元时，不会改变公式永真性和永假性,定理1.2(代入定理)：,设G(P,1,P,n,)是一个命题公式，其中P,1,P,n,是命题变元，G,1,(P,1,P,n,),G,n,(P,1,P,n,)为任意命题公式，此时若G是永真公式或永假公式，则用G,1,取代P,1,G,n,取代P,n,后，得到新命题公式G(G,1,G,n,)G(P,1,P,n,)也是一个永真公式或永假公式。,45/91,1.2 公式解释与真值表,例1.8：,设G(P,Q)=(PQ)P；用H(P,Q)=(P Q)；S(P,Q)=(P Q)代入G验证代入定理。,定理1.3(替换定理)：,设G1是G子公式，H1是任意命题公式，在G中凡出现G1处都以H1替换后得到新命题公式H，若G1H1，则GH。,例1.9：,简化开关电路：,S,S,R,Q,P,P,46/91,1.2 公式解释与真值表,例1.10：,将下面程序语言进行化简：,if A then if B then X else Y else if B then X else Y,例1.11：,简化逻辑电路：,R,Q,P,47/91,1.2 公式解释与真值表,例1.12：,求证：,(1).P(PQ)Q)是永真公式；,(2).P(QR)(PQ)R;,(3).(P(QR)(PQ R)P;,(4).(P(QR)(QR)(PR)R;,48/91,1.2 公式解释与真值表,1.2.5：对偶原理,定义1.14：,设公式A，其中仅有联结词，。在A中将，T，F分别换以，F，T得到公式A*，则A*称为A对偶公式。,对A*采取一样替换，又得到A，所以A也是A*对偶，即对偶是相互。,例，P(QR)和P(QR)互为对偶；PF和PT互为对偶。,定理1.4：,设A和A*是对偶式，P,1,P,2,P,n,是出现于A和A*中全部命题变元，于是,A(P,1,P,2,P,n,)A*(P,1,P,2,P,n,)公式(1),49/91,1.2 公式解释与真值表,定理1.5：,若AB，且A，B为命题变元P,1,P,2,P,n,及联结词，组成公式，则A*B*(对偶原理),例，若(PQ)(P(PQ)PQ，则由对偶原理，得 (PQ)(P(P Q)PQ,定理1.6：,假如A=B，且A，B为命题变元P,1,P,2,P,n,及联结词，组成公式，则B*=A*,50/91,1.3 联结词完备集,我们知道，命题公式经过等价公式转换，能够以不一样形式表示出来。我们前面介绍了5个联结词，是否够用呢？,1.3.1 联结词扩充,1.一元运算：,我们来看一个命题变元在一个一元运算作用下可能真值表。,P,f1,f2,f3,f4,0,0,0,1,1,1,0,1,0,1,51/91,1.3 联结词完备集,所以，最多只能定义4种运算，但除了否定之外，永假，永真，恒等作为运算意义不大，所以普通不再定义其它一元运算。,2.二元运算：,考虑两个变元在一个二元运算作用下可能真值表。,P,Q,f1,f2,f3,f4,f5,f6,f7,f8,f9,f10,f11,f12,f13,f14,f15,f16,0,0,0,1,0,0,0,1,1,1,0,0,0,1,1,0,1,1,0,1,0,0,1,0,0,1,0,0,1,1,0,1,1,1,0,1,1,0,0,0,0,1,0,0,1,0,1,0,1,1,0,1,1,1,1,1,0,0,0,0,0,0,0,1,0,1,1,0,1,1,1,1,永假,或非,蕴含否定,蕴含否定,合取,非P,非Q,等价,异或,恒等Q,恒等P,与非,蕴含,析取,蕴含,永真,52/91,1.3 联结词完备集,：已定义；：意义不大；：可再定义,f1=PP=F，f2=(PQ)，f3=(PQ)，,f4=(QP)，f5=PQ，f6=P，,f7=Q，f8=(PQ)，f9=(PQ),f10=Q，f11=P，f12=(PQ)，,f13=PQ，f14=PQ，f15=QP，,f16=PP=T，,其中：f2，f3(或f4)，f9，f12都是两个联结词组合，为了叙述方便，能够引进以下几个联结词：,53/91,1.3 联结词完备集,联结词,记号,复合命题,读法,记法,备注,f9,异或,P不可兼或Q,P异或Q,PQ,逻辑电路中异或门,f3，f4,蕴含否定,P和Q蕴含否定,P蕴含否定Q,P Q,f12,与非,P和Q与非,P与非Q,PQ,逻辑电路中与非门,f2,或非,P和Q或非,P或非Q,PQ,逻辑电路 中或非门,P Q(PQ)，P Q(PQ)，,PQ(PQ)，,PQ(PQ)，,这9个联结词组成命题演算中全部联结词。,54/91,1.3 联结词完备集,1.3.2 与非，或非，异或性质,1.与非性质：,PQ,QP，PP,P，,(PQ)(PQ),PQ，(PP)(QQ),PQ,2.或非性质：,PQ,QP，PP,P，,(PQ)(PQ),PQ，(PP)(QQ),PQ,3.异或性质：,P0，0 PP，1 PP,55/91,1.3 联结词完备集,1.3.3：全功效联结词,定义1.15：,设S是联结词集合，(1)用S中联结词表示公式，能够等价地表示任何命题公式，则称S是一个联结词完备集(或全功效集合)(Adequate Set of Connectives)，(2)S是一个联结词完备集，且S中无冗余联结词(即集合中不存在能够被其中其它联结词所定义联结词)，则称S为极小联结词完备集。,由1.3.1分析知，,是一个联结词完备集，而ABAB，AB(AB)(BA)，所以，是冗余，故,也是一个联结词完备集,而AB(AB)，所以也是冗余,也是一个联结词完备集，深入地,可知,是一个极小联结词完备集。,56/91,1.3 联结词完备集,证实,:联结词完备集,是一个极小。,注意：,同理，,，,，,也是极小完备集，另外由1.3.2中，性质可知，也是极小完备集；,及其子集不是完备集；,实际应用中经常采取联结词集合为,。,例1.13：,试将公式(P(QR)(PQ)用仅含，公式等价地表示出来。,57/91,1.4：范式,1.4.1：范式,对于给定公式判定问题，可用真值表方法加以解释，但当公式中命题变元数目较大时，计算量较大，每增加一个命题变元，真值表行数要翻倍，计算量加倍，另外，对于同一问题，能够从不一样角度去考虑，产生不一样但又等价命题公式，即同一个命题能够有不一样表示形式。这么给命题演算带来了一定困难，所以，有必要使命题公式规范化，为此，引入了范式概念。,58/91,1.4：范式,定义1.16：,(1)：命题变元或命题变元否定称为文字；,(2)：有限个文字析取式称为简单析取式(基本和)，有限个文字合取式称为简单合取式(基本积)；,(3)：由有限个简单合取式组成析取式称为析取范式(Disjunctive Normal From)，由有限个简单析取式组成合取式称为合取范式(Conjunctive Normal From)。,59/91,1.4：范式,比如，：P，P；：PQ R；,：PQR；：(PQ)(PQ)；,：(PQ)(PQ)；,性质：,(1)：一个文字既是一个析取范式又是一个合取范式；,(2)：一个析取范式为矛盾式，当且仅当它每个简单合取式是矛盾式；,(3)一个合取范式为重言式，当且仅当它每个简单析取式是重言式。,60/91,1.4：范式,定理1.7：,任一命题公式都存在着与之等值析取范式和合取范式。,例1.14：,求公式(PQ)(PR)析取范式和合取范式。,61/91,1.4：范式,1.4.2：主析取范式和主合取范式,范式即使为命题公式提供了一个统一表示形式，但这种表示形式却并不是唯一。如公式(PQ)(PR)与之等价公式有：P(QR)，(PP)(QR)，P(QQ)(QR)，P(PR)(QR),等，这种不唯一表示形式给研究问题带来了不便，所以有必要引进更为标准范式。,定义1.17：,(1)包含A中全部命题变元或其否定一次仅一次简单合取式，称为极小项；(2)包含A中全部命题变元或其否定一次仅一次简单析取式，称为极大项；(3)由有限个极小项组成析取范式称为主析取范式；(4)由有限个极大项组成合取范式称为主合取范式。,62/91,1.4：范式,1.极小项和极大项性质,对于两个命题变元P，Q来说，因为每个P，Q能够取命题变元本身和其否定，所以其对应极小项和极大项分别有四项：PQ，PQ，PQ，PQ；PQ，PQ,PQ，PQ。其真值表以下：,普通来说，对于n个命题变元，则应有 个不一样极小项和 个不一样极大项。,P,Q,PQ,PQ,PQ,PQ,PQ,PQ,PQ,PQ,0,0,1,0,0,0,1,1,1,0,0,1,0,1,0,0,1,1,0,1,1,0,0,0,1,0,1,0,1,1,1,1,0,0,0,1,0,1,1,1,63/91,1.4：范式,性质：,(1)：没有两个不一样极小项是等价，且每个极小项只有一组真值指派使该极小项真值为真，所以可给极小项编码，使极小项为“T”和那组真值指派为对应极小项编码；如极小项PQR只有在P，Q，R分别取真值0，0，0时才为真，所以有时又可用 ()来表示，又如PQR也可用 ()来表示。,(2)：没有两个不一样极大项是等价，且每个极大项只有一组真值指派，使该极大项真值为假。所以可给极大项编码，使极大项为“F”那组真值指派为对应极大项编码，如极大项PQR只有在P，Q，R分别取真值1，1，1时才为假，所以有时又可用 来表示。,64/91,1.4：范式,三个命题变元真值取值与极小项和极大项对应对位关系表：,P,Q,R,极小项,极大项,0,0,0,m0=PQR,M0=PQR,0,0,1,m1=PQR,M1=PQR,0,1,0,m2=PQR,M2=PQR,0,1,1,m3=PQR,M3=PQR,1,0,0,m4=PQR,M4=PQR,1,0,1,m5=PQR,M5=PQR,1,1,0,m6=PQR,M6=PQR,1,1,1,m7=PQR,M7=PQR,65/91,1.4：范式,(3)：任意两极小项合取必假，任意两个极大项析取必为真。极大项否定是极小项，极小项否定是极大项，即,(4)：全部极小项析取为永真公式，全部极大项合取是永假公式，即,66/91,1.4：范式,2.主析取范式和主合取范式存在性和唯一性,定理1.8：,任何命题公式主析取范式和主合取范式存在且唯一，即任何命题公式都有且仅有一个与之等价主合取范式和主析取范式。,真值表技术,例1.15：,求命题公式(PQ)R)(PQ)主析取范式。,例1.16：,求命题公式(PQ)R主合取范式。,67/91,1.4：范式,利用真值表技术求主析取范式和主合取范式方法：,：选出公式真值结果为真全部行，在这么行中，找到其每一个解释所对应极小项，将这些极小项析取即可得到对应主析取范式；,：选出公式真值结果为假全部行，在这么行中，找到其每一个解释所对应极大项，将这些极大项合取即可得到对应主合取范式。,68/91,1.4：范式,公式转换法,唯一性：,设任一命题公式A有两个主析取范式B和C，则因为AB，AC，所以BC，若B，C是A(在不计极小项次序情况下)不一样主析取范式，则必有在存在极小项mi，mi只存在于B，C之一中，不妨设mi在B中,而不在C中，所以i之二进制表示B一个真值解释，而对于C则为真值为假解释，这与BC矛盾，所以B和C相同，同理主合取范式也是唯一。,例1.17：,利用公式等价求G=(PQ)R主析取范式和主合取范式,69/91,1.4：范式,3：主合取范式和主析取范式之间转换,真值表技术和公式转换方式在求主析取范式和主合取范式各有其优点，在公式中命题变元较少时时，利用真值表技术更为简单。当命题变元较多时，普通采取公式转换法，而在公式转换中，有时求主析取范式更为方便，而有时求主合取范式更为方便。但二者之间必定有对应关系。下面介绍一个二者之间转换方法。,70/91,1.4：范式,(1)：已知公式G主析取范式求公式G主合取范式步骤以下：,a：求G主析取范式，即G主析取范式中没有出现过极小项析取,b：G(G)即是G主合取范式,即：若 为G主析取范式，则,为G主析取范式，其中,后剩下极小项。则,为G主合取范式。,71/91,1.4：范式,(2)：已知公式G主合取范式，求G主析取范式步骤以下：,a：求G主合取范式，即G主合取范式中没有出现过极大项合取,b：G(G)即是G主析取范式，,即，若 为G主合取范式，则,为G主合取范式。其中,后剩下极大项。,则,为G主析取范式,72/91,1.4：范式,例1.18：,设G=(P,Q)(PR)(QR),求其对应主析取范式和主合取范式,性质：,(1)：假如命题公式是永真公式它主析取范式包含全部极小项，此时主合取范式不含有任何极大项，为空，记1或T,(2)：假如命题公式是永假公式它主合取范式包含全部极大项，此时主析取范式不含有任何极小项，为空，记0或F,(3)：两个命题公式A，B，AB当且仅当A与B有相同真值表，又当且仅当A与B有相同主析取范式(主合取范式)。(真值表和主范式是描述命题公式标准形式两种不一样等价形式)。,73/91,1.5：命题逻辑推理理论,1.5.1：推理基本概念和推理形式,推理也称论证，它是指从前提出发推出结论思维过程，而前提是已知命题公式集合，结论是从前提出发应用推理规则推出命题形式。,定义1.18：,设G1，G2，Gn，H是命题公式，若对于G1，G2，Gn，H中出现命题变元任意一组赋值，或者G1G2Gn为假，或者当G1G2Gn为真，H也为真，则称H是G1，G2，Gn有效结论(Efficacious Conclusion)或逻辑结果(Logic Conclusion)。G1，G2，Gn仍为一组前提(Premise)。,74/91,1.5：命题逻辑推理理论,定理1.9：,命题公式G1，G2，Gn推出结论H推理正确或公式H是前提条件G1，G2，Gn逻辑结果，当且仅当(G1G2Gn)H为重言式。,=：逻辑蕴含关系，G=H不是命题公式，计算机判断G=H办不到；,：蕴含联结词，G H是命题公式，计算机可判断G H为永真公式。,所以我们能够用蕴含式来描述推理。,我们将由G1，G2，Gn推理H，用蕴含式表示为：(G1G2Gn)H,将由G1，G2，Gn正确推理出H，用蕴含式表示为：G1G2Gn=H,75/91,1.5：命题逻辑推理理论,推理形式结构为：G1G2Gn H，书写为：,前提：G1，G2，Gn,结论：H,推理有效性判断，即判断推理是否正确，也就是判断G1G2GnH是否为重言式。,1.5.2：判断结论有效方法,1.真值表法；2.等值演算法；3.主析取范式法,76/91,1.5：命题逻辑推理理论,1.真值表法,设P1，P2，Pn是出现在前提G1，G2，Gn和结论H中一切命题变元，假如将P1，P2，Pn中全部可能介绍及G1，G2，Gn，H对应真值结果都在一个表中，依据“”定义，则有以下判断方法：,(1)对全部G1，G2，Gn都含有真值T行(表示前提为真行)，假如在每个这么行中，H也含有真值T，则H是G1，G2，Gn逻辑结果；,(2)对全部H含有真值为F行(表示结论为假行)，假如在每一个这么行中，G1，G2，Gn中最少有一个公式真值为F(前提也为假)。则H是G1，G2，Gn逻辑结果。,77/91,1.5：命题逻辑推理理论,例1.18：,判断以下H是否为前提G1，G2逻辑结果。,(1).H：Q;G1：P，G2：PQ；,(2).H：P;G1：PQ，G2：Q；,(3).H：Q;G1：P，G2：PQ；,2.等值演算法,直接用等值演算来判断推理形式结构是否是重言式。,例1.19：,下午马芳或去看电影或去游泳。她没去看电影。所以，她去游泳了。,78/91,1.5：命题逻辑推理理论,3.主析取范式法,将推理形式结构转化为主析取范式，但仍判断其是否为重言式。,例1.20：,若下午气温超出30，则王小燕必去游泳。若她去游泳，她就不去看电影了。所以，若王小燕没去看电影，下午气温超出了30。,以上方法，当形式结构比较复杂，尤其是所含命题变元较多时，普通很不方便，下面介绍结构证实法。,79/91,1.5：命题逻辑推理理论,1.5.3：结构证实法,结构证实法是依据一些公认推理规则，从前提出发，推导结论，它能够看作公式序列，其中每个公式都是按照事先要求规则得到，且可将所用规则在公式后写明，该系列最终一个公式是所要证实结论。,(1)推理规则：,前提引入规则：在推理任何步骤上都能够引入前提；,结论引入规则：在推理任何步骤上所得到结论都能够做为后续证实前提；,置换规则：在推理任何步骤上，命题公式子公式都能够用与之等价公式置换，得到公式序列中又一个公式。,80/91,1.5：命题逻辑推理理论,(2)推理定理：(一些主要永真蕴含式),1.A=(AB)附加律,2.AB=A 化简律,3.(A,B)A=B 假言真理,4.(AB)B=A 拒取式,5.(A,B),B=A 析取三段论,6.(A,B)(BC)=AC 假言三段论,7.(AB)(BC)=AC 等价三段论,8.(AB)(CD)(AC)=(BD)结构性二难,(AB)(AB)(AA)=B结构性二难(特殊形式),9.(AB)(CD)(BD)=(AC)破坏性二难,81/91,1.5：命题逻辑推理理论,由着9个定律中8个能够得到8个推理规则：,附加规则：A|=(AB),化简规则：(AB)|=A,假言推理规则：(A,B)，A|=B,拒取式规则：(AB)，B|=A,假言三段论规则：(AB)，(BC)|=(AC),析取三段论规则：(AB)，B|=A,结构性二难规则：(AB)，(CD)，(AC)|=(BD),破坏性二难规则：(AB)，(CD)，(BD)|=(AC),合取引入规则：A，B|=(AB),82/91,1.5：命题逻辑推理理论,例1.21：,结构以下推理证实：,前提：p q，p r，s t，s r，t,结论：q,例1.22：,分析以下事实：“早饭我吃面包或蛋糕；假如我吃面包，那么我还要喝牛奶；假如我吃蛋糕，那么我还要喝咖啡；但我没有喝咖啡，所以早饭我吃是牛奶和面包。”写出前提和有效结论并证实之。,例1.23：,用结构法证实，找出以下推理有效结论。,假如我考试经过了，那么我很高兴；假如我高兴，那么阳光灿烂；现在是晚上11点，天很暗。,83/91,1.5：命题逻辑推理理论,(3)P1,P2Pn(P Q)形式命题证实。,附加前提证实法(CP规则),若P1，P2，Pn，P|=Q，则P1，P2，Pn|=P,Q,附加前提证实法意义在于：当推理结论是蕴含式时，能够将其前件作为附加前提引用，只要能推理出其后件，则原推理成立