离散数学1-3-1-4

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