离散数学1-3,1-4.ppt

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