离散数学1-3-1-4优秀PPT.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,离散数学,离 散 数 学,Discrete Mathematics,陈明,Email:mingchen_gang,信息科学与工程学院,二零一三年九,月,1,课程回顾,命题：命题的定义、真值、分类及其表示。,命题联结词：,否定、合取、析取、条件、双条件。,P,Q,P,PQ,PQ,PQ,P Q,T,T,F,T,T,T,T,T,F,F,F,T,F,F,F,T,T,F,T,T,F,F,F,T,F,F,T,T,2,例：我将去镇上（,P,），仅当我有时间（,Q,）。,Q P(,是否正确？,),PQ,（正确）,3,AB,，,(BC,）,可以逻辑推出,A,或写成,(AB)(BC),A,4,1-3,命题公式与翻译,1-4,真值表与等价公式,5,一、合式公式,前面已经提到，不包含任何联结词的命题叫做,原子命题,，至少包含一个联结词的命题称作,复合命题,。,设,P,和,Q,是任意两个命题，则,PQ,，,(PQ,）,(FQ,），,P (Q P),等都是复合命题。,若,P,和,Q,是命题变元,，则上述各式均称作,命题公式,。,P,和,Q,称作命题公式的分量。,说明：,命题公式没有真值,，仅当其中命题变元用确定的命题代入时，才得到一个命题。这个命题的真值，依赖于代换变元的那些命题的真值。,并不是由命题变元、联结词和一些括号组成的字符串都能成为命题公式,。,1-3,命题公式与翻译,6,定义,1-3.1,命题演算的,合式公式,(wff),，规定为：,(1),单个命题变元（常元）本身是一个合式公式。,(2),如果,A,是合式公式，那么,A,是合式公式。,(3),如果,A,和,B,是合式公式，那么,(AB),，,(AB),，,(AB,）和,(A B),都是合式公式。,(4),当且仅当能够,有限次,地应用,(1),、,(2),、,(3),所得到的包含命题变元、联结词和括号的符号串是合式公式。,这个合式公式的定义，是以递归形式给出的，其中,(1),称为基础，,(2)(3),称为归纳，,(4),称为界限。,7,按照定义，下列公式都是合式公式：,(PQ,），,(PQ),，,(P(PQ),，,(PQ,）,(QR),（,S T),而,(PQ,）,(Q),，,(PQ,，,(PQ,）,Q,）,等都不是合式公式。,8,联结词的优先级,目的：减少使用括号的数量；,约定：命题公式外层的括号可以省略；,联结词的优先级：,、,。,利用加括号的方法可以提高优先级,。,范例：,PQR,等价于,wff,：,（,（,PQ,）,R,）,等价于,w,ff,：（,PQ,）,R,不等价于,w,ff,：,P,（,QR,）,9,有了联结词的合式公式概念，我们可以把自然语言中的有些语句，翻译成数理逻辑中的符号形式。,把一个用文字叙述的命题相应地写成由,命题标识符、联结词和圆括号,表示的合式公式，称为,命题的符号化,。,符号化应该注意下列事项：,确定给定句子是否为命题；,句子中联结词是否为命题联结词；,要正确地表示原子命题和适当选择命题联结词。,二、翻译（符号化）,10,命题符号化步骤：,(1),分成原子命题,；,(2),用大写字母代替命题；,(3),按题意用联结词。,11,自然语言的语句用,wff,形式化,的,例题,解 找出各原子命题，并用命题符号表示：,A,：我们,要,做到身体好。,B,：我们,要,做到学习好。,C,：我们,要,做到工作好。,P,：我们,要,为祖国四化建设而奋斗。,例题,1,试以符号形式写出命题：我们,要,(,删掉,),做到身体好、学习好、工作好，为祖国四化建设而奋斗。,故命题可形式化为：,（,A B C,）,P,12,说明：定义用双条件表示，,P12,（,6,）,13,自然语言的语句用,wff,形式化,要准确确定原子命题，并将其形式化；,要选用恰当的联结词，尤其要善于识别自然语言中的联结词（有时它们被省略），否定词的位置要放准确；,必要,时可以进行改述，即改变原来的叙述方式，,但要保证表达意思一致,；,需要的括号不能省略，而可以省略的括号，在需要提高公式可读性时亦可不省略；,要注意语句的形式化未必是唯一的。,主要是以下几个方面：,14,从表中可看出原命题不能用前述五个联结词单独写出。,解,P,：上海到北京的,14,次列车是下午五点半开。,Q,：上海到北京的,14,次列车是下午六点开。,在本例中，汉语的“或”是不可兼或，而逻辑联结词是“可兼或”，因此不能直接对两命题析取。,真值可构造如表,1-3.1,所示。,P,Q,原命题,T,T,F,T,F,T,F,T,T,F,F,F,表,1-3.1,例题,2,上海到北京的,14,次列车是下午五点半或六点开。,15,可以用命题和联结词组合，可以把本命题表达为：,(P Q,）。,P,Q,原命题,P Q,(P Q),T,T,F,T,F,T,F,T,F,T,F,T,T,F,T,F,F,F,T,F,表,1-3.1,续,例题,2,上海到北京的,14,次列车是下午五点半或六点开。,或是,或是,(P Q)(P Q),，,16,解 若设,P,：他聪明。,Q,：他用功。,在自然语言中这个“既,又,”,显然与“且”的意义一样，,故本例可记为：,PQ,。,例题,3,他既聪明又用功。,17,解 这里“虽,但,”,这个词不能用前述联结词表达。,但其实际意义是：他聪明且不用功。,若设,P,：他聪明。,Q,：他用功。,本例可表示为：,PQ,例题,4,他虽聪明但不用功。,18,解 这个命题的意义，亦可理解为：如果你,不努力则你将失败。,若设,P,：你努力。,Q,：你失败。,本例可表示为：,PQ,例题,5,除非你努力，否则你将失败。,19,解 这个命题的意义是：张三可以做这件事，并且李四也可以做这件事。,若设,P,：张三可以做这事。,Q,：李四可以做这事。,本例可表示为：,PQ,例题,6,张三,或,李四,都,可以做这件事。,20,注意：,从上面的例子中可以看到，自然语言中的一些联结词，如：“与”“且”“或”“除非,则,”,等等都各有其具体含义，因此需分别不同情况翻译成适当的逻辑联结词。为了便于正确表达命题间的相互关系，有时也常常采用,列出“真值表”的方法,，进一步分析各原命题，以此寻找逻辑联结词，使原来的命题能够正确地用形式符号予以表达。,21,练习 把下列自然语言命题符号化：,(1),小张既聪明，又勤奋，所以他学习好。,(2),或者你没有给我写信，或者它在途中丢失了。,解,(1),设,P,：小张聪明。,Q,：小张勤奋。,R,小张学习好。则命题符号化为：,PQR,(2),设,P,：你没有给我写信。,Q,：信在途中丢失了。,命题符号化为：（,P,Q),命题符号化是很重要的，一定要掌握好，在命题推理中常常最先遇到的就是符号化一个问题，解决不好，等于说推理的首要前提没有了。,22,1.,真值表,定义,1-4.1,在命题公式中，,对于分量指派真值的各种可能组合，,就确定了这个命题公式的各种真值情况，把它汇列成表，就是命题公式的,真值表,。,P,Q,P,PQ,T,T,F,T,T,F,F,F,F,T,T,T,F,F,T,T,现举例说明如下：,例题,1,构造,PQ,的真值表。,解（见表,1-4.1,）,表,1-4.1,1-4,真值表与等价公式,23,例题,2,给出,(PQ,）,P,的真值表。,解,P,Q,PQ,P,(PQ,）,P,T,T,T,F,F,T,F,F,F,F,F,T,F,T,F,F,F,F,T,F,表,1-4.2,24,例题,3,给出,(PQ,）（,PQ,）的真值表。,解,P,Q,P,Q,PQ,PQ,（,PQ,）（,PQ,）,T,T,F,F,T,F,T,T,F,F,T,F,F,F,F,T,T,F,F,F,F,F,F,T,T,F,T,T,表,1-4.3,25,例题,4,给出,(PQ,）（,PQ,）的真值表。,解,P,Q,PQ,(PQ),P,Q,PQ,(PQ,）（,PQ,）,T,T,T,F,F,F,F,T,T,F,F,T,F,T,T,T,F,T,F,T,T,F,T,T,F,F,F,T,T,T,T,T,表,1-4.4,26,由表,1-4.4(,表,1-4.2),可以看出，有一类公式不论命题变元作何种指派，其,真值永为真,(,假,),，我们把这类公式记为,T(F),。,在真值表中，命题公式真值的取值数目，决定于分量的个数。例如，由,2,个命题变元组成的命题公式共有四种可能的真值，由,3,个命题变元组成的命题公式共有八种真值。,一般说来，,n,个命题变元组成的命题公式共有,2,n,种真值情况。,27,从真值表中可以看到，有些命题公式在分量的不同指派下，其,对应的真值与另一命题公式完全相同,，如,PQ,与,PQ,的对应真值相同，如表,1-4.5,所示。,P,Q,PQ,PQ,T,T,T,T,T,F,F,F,F,T,T,T,F,F,T,T,表,1-4.5,我们说,PQ,和,PQ,是等价的，这在以后的推理中特别有用。,28,同理,(PQ)(PQ),与,P Q,对应的真值相同，如表,1-4.6,所示。,P,Q,P Q,(PQ)(PQ),T,T,T,T,T,F,F,F,F,T,F,F,F,F,T,T,表,1-4.6,29,二、等价公式,1.,定义,定义,1-4.2,给定两个命题公式,A,和,B,，设,P,1,，,P,2,，,，,P,n,为所有出现于,A,和,B,中的原子变元，若给,P,1,，,P,2,，,，,P,n,任一组真值指派，,A,和,B,的真值都相同，则称,A,和,B,是等价的或逻辑相等。,记作,A,B,。,30,在这里，请注意,和,的区别与联系,：,区别：,是逻辑联结词，属于目标语言中的符号，它出现在命题公式中；,不是逻辑联结词，,属于元语言中的符号，,表示两个命题公式的一种关系，不属于这两个公式的任何一个公式中的符号。,2,、证明方法：,真值表法,31,由表,1-4.7,可知,P Q,与,(PQ)(QP,）真值相同，命题得证。,例题,5,证明,P Q,(PQ)(QP),证明 列出其值表,表,1-4.7,P,Q,P Q,QP,P Q,(PQ)(QP,）,T,T,T,T,T,T,T,F,F,T,F,F,F,T,T,F,F,F,F,F,T,T,T,T,32,推导的证明方法,命题定律（表,1-4.8,列出的命题定律都可以用真值表予以验证），见下表,1-4.8,33,对合律,P,P,1,幂等律,PP,P,，,PP,P,2,结合律,(PQ,）,R,P,（,QR,）,(PQ,）,R,P,（,QR,）,3,交换律,PQ,QP,PQ,QP,4,分配律,P,（,QR,）,（,PQ,）（,PR,）,P,（,QR,）,（,PQ,）（,PR,）,5,吸收律,P,（,PQ,）,P,P,（,PQ,）,P,6,德摩根律,(PQ),PQ,(PQ),PQ,7,同一律,P,F,P,，,P,T,P,8,零律,P,T,T,，,P,F,F,9,否定律,PP,T,，,PP,F,10,PQ,PQ,表,1-4.8,34,例题,6,验证吸收律,P,（,PQ,）,P,P,（,PQ,）,P,证明 列出真值表,P,Q,PQ,P,（,PQ,）,PQ,P,（,PQ,）,T,T,T,T,T,T,T,F,F,T,T,T,F,T,F,F,T,F,F,F,F,F,F,F,由表,1-4.9,可知吸收律成立。,表,1-4.9,35,等价置换,在一个命题公式中，如果用公式置换命题的某个部分，一般地将会产生某种新的公式。,例如,Q(P(PQ),中以,(PQ),取代,(PQ),，则,Q(P(PQ),就与原式不同。,为了保证取代后的公式与原始公式是等价的，故需对置换作出一些规定。,36,定义,1-4.3,如果,X,是合式公式,A,的一部分，且,X,本身也是一个合式公式，则称,X,为公式,A,的,子公式,。,证明 因为在相应变元的任一种指派情况下，,X,与,Y,的真值相同，故以,Y,取代,X,后，公式,B,与公式,A,在相应的指派情况下，其真值亦必相同，故,A,B,。口,满足定理,1-4.1,条件的置换称为,等价置换,(,等价代换,),。,定理,1-4.1,设,X,是合式公式,A,的子公式，若,X,Y,，如果将,A,中的,X,用,Y,来置换，所得到公式,B,与公式,A,等价，即,A,B,。,37,例题,7,证明,Q(P(PQ),QP,证明 设,A,：,Q(P(PQ),，,B,：,QP,因为,P(PQ),P,故,A,B,吸收律,对,A,B,亦可用表,1-4.10,（真值表）予以验证：,38,P,Q,PQ,P,（,PQ,）,QP,（,PQ,）,QP,T,T,T,T,T,T,T,F,F,T,T,T,F,T,F,F,F,F,F,F,F,F,T,T,有了最基本的的命题公式的等价关系，再利用定理,1-4.1,，就可以推证一些更为复杂的命题等价公式。,表,1-4.10,39,例题,8,证明,(PQ)(PQ),P,P,P T,证明,(PQ)(PQ),P(QQ),合取对析取的分配律,否定律,同一律,40,例题,9,证明,P(QR),Q(PR),R(Q,P),P(QR),P(Q R),R(Q P),R(QP),证明,P(QR),P(Q R),Q(P R),Q(PR),PQ,PQ,41,例题,10,证明,(PQ)(P(QR)(PQ)(PR),T,T,(P Q)(P R)(PQ)(PR),(PQ),(P Q),(P R)(PQ)(PR),原式左边,(PQ)(P(QR)(PQ)(PR),证明,42,化简如下语句：,“情况并非如此：若他不来，则我不去”。,43,解：首先符号化上述语句。,设,P,：他来。,Q,：我去,则原句：（,PQ,）,然后化简上述命题公式,（,PQ,）,（,P,Q,）,P,Q,即：我去了，但他未来。,44,P,：上午下雨，,Q,：我去看电影，,R,：我在家看书；,S,：我在家看报,。,（,P,Q,）（,P,（,R S,）,P12,：（,7,）,a,）,45,作业：,P12,：,(7)b,P17,：（,1,）,d,P19,：（,7,）,f,46,学习本节要深刻理解命题公式的定义，能够把用自然语言中的有些语句，翻译成数理逻辑中的符号形式。,合式公式,：命题演算的合式公式,(wff),规定为：,(1),单个命题变元本身是一个合式公式。,(2),如果,A,是合式公式，那么,A,是合式公式。,(3),如果,A,和,B,是合式公式，那么,(AB),，,(AB),，,(AB,）和,(A B),都是合式公式。,(4),当且仅当能够有限次地应用,(1),、,(2),、,(3),所得到的包含命题变元，联结词和括号的符号串是合式公式。,翻译,把自然语言中的有些语句，翻译成数理逻辑中的符号形式。,优先次序,规定联结词运算的优先次序为：、,小结,47,真值表,在命题公式中，对于分量指派真值的各种可能组合，就确定了这个命题公式的各种真值情况，把它汇列成表，就是命题公式的真值表。,逻辑相等,给定两个命题公式,A,和,B,，设,P,1,，,P,2,，,，,P,n,为所有出现于,A,和,B,中的原子变元，若给,P,1,，,P,2,，,，,P,n,任一组真值指派，,A,和,B,的真值都相同，则称,A,和,B,是等价的或逻辑相等。记作,A,B,。,子公式,如果,X,是合式公式,A,的一部分，且,X,本身也是一个合式公式，则称,X,为公式,A,的子公式。,定理,1-4.1,设,X,是合式公式,A,的子公式，若,X,Y,，如果将,A,中的,X,用,Y,来置换，所得到公式,B,与公式,A,等价，即,A,B,。,10,个命题定律。,48,重点：合式公式的定义，两个合式公式等价的定义，,10,个命题定律。,难点：推证等价公式。,49,作业：,P12,：,(7)b,，,c;,P17,：（,1,）,d,P19,：（,7,）,a,，,f,（,8,）,b,课下讨论,P18,（,5,）、（,6,）,(,不用写到作业本,),50,化简如下语句：,“情况并非如此：若他不来，则我不去”。,51,解：首先符号化上述语句。,设,P,：他来。,Q,：我去,则原句：（,PQ,）,然后化简上述命题公式,（,PQ,）,（,P,Q,）,P,Q,即：我去了，但他未来。,52,课程回顾,第,1,次课：,命题；,5,个联结词,第,2,次课：,命题的翻译,命题公式等价的两种证明方法,真值表,利用命题定律推导,53,合式公式,：命题演算的合式公式,(wff),规定为：,(1),单个命题变元本身是一个合式公式。,(2),如果,A,是合式公式，那么,A,是合式公式。,(3),如果,A,和,B,是合式公式，那么,(AB),，,(AB),，,(AB,）和,(A B),都是合式公式。,(4),当且仅当能够有限次地应用,(1),、,(2),、,(3),所得到的包含命题变元，联结词和括号的符号串是合式公式。,翻译,把自然语言中的有些语句，翻译成数理逻辑中的符号形式。,优先次序,规定联结词运算的优先次序为：、,54,真值表,在命题公式中，对于分量指派真值的各种可能组合，就确定了这个命题公式的各种真值情况，把它汇列成表，就是命题公式的真值表。,逻辑相等,给定两个命题公式,A,和,B,，设,P,1,，,P,2,，,，,P,n,为所有出现于,A,和,B,中的原子变元，若给,P,1,，,P,2,，,，,P,n,任一组真值指派，,A,和,B,的真值都相同，则称,A,和,B,是等价的或逻辑相等。记作,A,B,。,子公式,如果,X,是合式公式,A,的一部分，且,X,本身也是一个合式公式，则称,X,为公式,A,的子公式。,定理,1-4.1,设,X,是合式公式,A,的子公式，若,X,Y,，如果将,A,中的,X,用,Y,来置换，所得到公式,B,与公式,A,等价，即,A,B,。,10,个命题定律。,55,对合律,P,P,1,幂等律,PP,P,，,PP,P,2,结合律,(PQ,）,R,P,（,QR,）,(PQ,）,R,P,（,QR,）,3,交换律,PQ,QP,PQ,QP,4,分配律,P,（,QR,）,（,PQ,）（,PR,）,P,（,QR,）,（,PQ,）（,PR,）,5,吸收律,P,（,PQ,）,P,P,（,PQ,）,P,6,德摩根律,(PQ),PQ,(PQ),PQ,7,同一律,P,F,P,，,P,T,P,8,零律,P,T,T,，,P,F,F,9,否定律,PP,T,，,PP,F,10,PQ,PQ,表,1-4.8,56,