离散数学1-3.4

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,离散数学,Discrete,thematics,课程回顾,命题：命题的定义、真值、分类及其表示。,命题联结词：,否定、合取、析取、条件、双条件。,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,讲,13,命题公式与翻译,14,真值表与等价公式,要求：理解合式公式及两个合式公式等价的定义，熟悉命题定律，会证明等价公式。,重点：合式公式的定义，两个合式公式等价的定义，,10,个命题定律。,难点：推证等价公式。,13,命题公式与翻译,p9,一、合式公式,前面已经提到，不包含任何联结词的命题叫做原子命题，至少包含一个联结词的命题称作复合命题。,设,P,和,Q,是任意两个命题，则,P,，,PQ,，,(PQ,）,(FQ,），,P (Q P),等都是复合命题。,若,P,和,Q,是命题变元，则上述各式均称作命题公式。,P,和,Q,称作命题公式的分量。,说明：,命题公式没有真值，仅当其中命题变元用确定的命题代入时，才得到一个命题。这个命题的真值，依赖于代换变元的那些命题的真值。,并不是由命题变元，联结词和一些括号组成的字符串都能成为命题公式。,定义,1-3.1,命题演算的合式公式,(,wff,),，,规定为：,(1),单个命题变元（常元）本身是一个合式公式。,(2),如果,A,是合式公式，那么,A,是合式公式。,(3),如果,A,和,B,是合式公式，那么,(AB),，,(AB),，,(AB,）和,(A B),都是合式公式。,(4),当且仅当能够有限次地应用,(1),、,(2),、,(3),所得到的包含命题变元，联结词和括号的符号串是合式公式。,这个合式公式的定义，是以递归形式给出的，其中,(1),称为基础，,(2)(3),称为归纳，,(4),称为界限。,按照定义，下列公式都是合式公式：,(PQ,），,(PQ),，,(P(PQ),，,(PQ,）,(QR),（,S T),而,(PQ,）,(Q),，,(PQ,，,(PQ,）,Q,）,等都不是合式公式。,练习,11,页（,1,）,联结词的优先级,命题公式外层的括号可以省略；,*联结词的优先级：,、,。,利用加括号的方法可以提高优先级,。,范例：如下的,Wff,：,PQR,等价于,Wff,：,（,（,PQ,）,R,）,等价于,Wff,：（,PQ,）,R,不等价于,Wff,：,P,（,QR,）,练习,11,页（,2,）,二、翻译（符号化）,有了联结词的合式公式概念，我们可以把自然语言中的有些语句，翻译成数理逻辑中的符号形式。,把一个用文字叙述的命题相应地写成由命题标识符、联结词和圆括号表示的合式公式，称为命题的符号化。符号化应该注意下列事项：,确定给定句子是否为命题。,句子中联结词是否为命题联结词。,要正确地表示原子命题和适当选择命题联结词。,命题符号化步骤：,(1),分成原子命题,(2),用大写字母代替命题,(3),按题意用联结词,自然语言的语句用,Wff,形式化,主要是以下几个方面：,要准确确定原子命题，并将其形式化。,要选用恰当的联结词，尤其要善于识别自然语言中的联结词（有时它们被省略），否定词的位置要放准确。,必要,时可以进行改述，即改变原来的叙述方式，,但要保证表达意思一致,。,需要的括号不能省略，而可以省略的括号，,在需要提高公式可读性时亦可不省略。,要注意语句的形式化未必是唯一的。,自然语言的语句用,Wff,形式化,的,例子。,例题,解 找出各原子命题，并用命题符号表示：,A,：,我们要做到身体好。,B,：,我们要做到学习好。,C,：,我们要做到工作好。,P,：,我们要为祖国四化建设而奋斗。,例题,1,(p10),试以符号形式写出命题：我们要做到身体好、学习好、工作好，为祖国四化建设而奋斗。,故命题可形式化为：,（A,B,C）P,从表中可看出原命题不能用前述五个联结词单独写出，但是如用命题和联结词组合，可以把本命题表达为：,(P Q,）。,解,P,：,上海到北京的,14,次列车是下午五点半开。,Q,：,上海到北京的,14,次列车是下午六点开。,在本例中，汉语的“或”是不可兼或，而逻辑联结词,是“可兼或”，因此不能直接对两命题析取。构造表如表如表,1-3.1,所示。,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,：,他用功。,在自然语言中这个“既,又,”,显然与“且”的意义一样，故本例可记为：,PQ,。,例题,3,他既聪明又用功。,解 这里“虽,但,”,这个词不能用前述联结词表达，但其实际意义是：他聪明且不用功。若设,P,：,他聪明。,Q,：,他用功。,本例可表示为：,PQ,例题,4,他虽聪明但不用功。,解 这个命题的意义，亦可理解为：如果你,不努力则你将失败。,若设,P,：,你努力。,Q,：,你失败。,本例可表示为：,PQ,例题,5,除非你努力，否则你将失败。,解 这个命题的意义是：,张三可以做这件事，并且李四也可以做这件事。,若设,P,：,张三可以做这事。,Q,：,李四可以做这事。,本例可表示为：,PQ,例题,6,张三或李四都可以做这件事。,从上面的例子中可以看到，自然语言中的一些联结词，如：“与”“且”“或”“除非,则,”,等等都各有其具体含义，因此需分别不同情况翻译成适当的逻辑联结词。为了便于正确表达命题间的相互关系，有时也常常,采用列出“真值表”的方法,，进一步分析各原命题，以此寻找逻辑联结词，使原来的命题能够正确地用形式符号予以表达。,练习 把下列自然语言命题符号化：,(1),小张既聪明，又勤奋，所以他学习好。,(2),小李不在图书馆，他要么找老师去了，要么就是因为身体不适，回宿舍去了。,命题符号化是很重要的，一定要掌握好，在命题推理中常常最先遇到的就是符号化一个问题，解决不好，等于说推理的首要前提没有了。,解,(1),设,P,：,小张聪明。,Q,：,小张勤奋。,R,小张学习好。则命题符号化为：,(,PQ)R,(2),设,P,：,小李在图书馆。,Q,：,小李找老师。,R,：,小李身体不适。,S,：,小李回宿舍。,则命题符号化为：,P(Q(RS),小结 学习本节要深刻理解命题公式的定义，能够把用自然语言中的有些语句，翻译成数理逻辑中的符号形式。,合式公式：命题演算的合式公式,(,wff,),规定为：,(1),单个命题变元本身是一个合式公式。,(2),如果,A,是合式公式，那么,A,是合式公式。,(3),如果,A,和,B,是合式公式，那么,(AB),，,(AB),，,(AB,）和,(A B),都是合式公式。,(,4),当且仅当能够有限次地应用,(1),、,(2),、,(3),所得到的包含命题变元，联结词和括号的符号串是合式公式。,翻译 把自然语言中的有些语句，翻译成数理逻辑中的符号形式。,优先次序 规定联结词运算的优先次序为：,、,、,练习,12,页（,5,）（,6,）（,7,）,14,真值表与等价公式,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,p13,构造,PQ,的真值表。,解（见表,1-4.1,）称为可满足式,表,1-4.1,例题,2,给出,(PQ,）,P,的真值表。,解 （见表,1-4.2,）,称为矛盾式,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,例题,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,例题,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,p14,称为重言式,由表,1-4.4(,表,1-4.2),可以看出，有一类公式不论命题变元作何种指派，其真值永为真,(,假,),，我们把这类公式记为,T(F),。,在真值表中，命题公式真值的取值数目，决定于分量的个数。例如，由,2,个命题变元组成的命题公式共有四种可能的真值，由,3,个命题变元组成的命题公式共有八种真值。一般说来，,n,个命题变元组成的命题公式共有,2,n,种真值情况。,练习,17,页（,1,）,18,页*（,6,）,从真值表中可以看到，有些命题公式在分量的不同指派下，其对应的真值与另一命题公式完全相同，如,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,是等价的，这在以后的推理中特别有用。,同理,(PQ)(PQ),与,P Q,对应的真值相同，如表,1-4.6,所示。,表,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,练习,17,页（,2,）,二、等价公式,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,。,在这里，请注意,和,的区别与联系：,区别：,是逻辑联结词，属于目标语言中的符号，它出现在命题公式中；,不是逻辑联结词，属于元语言中的符号，表示两个命题公式的一种关系，不属于这两个公式的任何一个公式中的符号。,2,、证明方法：,真值表法,由表,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,推导的证明方法,命题定律（表,1-4.8,列出的命题定律都可以用真值表予以验证）,表,1-4.8,对合律,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,例题,6,验证吸收律,P,（,PQ,）,P,P,（,PQ,）,P,证明 列出真值表,表,1-4.9,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,可知吸收律成立。,练习,18,页（,4,）,等价置换,在一个命题公式中，如果用公式置换命题的某个部分，一般地将会产生某种新的公式，例如,Q(P,Q),中以,(PQ),取代,(PQ),。为了保证取代后的公式与原始公式是等价的，故需对置换作出一些规定。,P,Q,Q(P,Q),PQ,Q,(,PQ),T,T,T,T,T,T,F,T,T,T,F,T,T,T,T,F