离散数学1-3,1-4

1、离散数学离散数学Discrete Mathematics陈明陈明Email:mingchen_信息科学与工程学院信息科学与工程学院二零一三年九二零一三年九月月离散数学离散数学课程回顾课程回顾 命题：命题的定义、真值、分类及其表示。命题：命题的定义、真值、分类及其表示。命题联结词：命题联结词： 否定、合取、析取、条件、双条件。否定、合取、析取、条件、双条件。PQPPQPQPQP QTT FTT TTTF FFT FFFT TFT TFFF TFF TT离散数学离散数学例：我将去镇上（例：我将去镇上（P） ，仅当我有时间（，仅当我有时间（Q）。）。 Q P(是否正确？是否正确？) PQ（正确）（正

2、确）离散数学离散数学AB，(BC）可以逻辑推出可以逻辑推出A或写成或写成(AB) (BC)A离散数学离散数学 1-3 命题公式与翻译命题公式与翻译 1-4 真值表与等价公式真值表与等价公式 离散数学离散数学一、合式公式一、合式公式 前面已经提到，不包含任何联结词的命题叫做前面已经提到，不包含任何联结词的命题叫做原子命原子命题题，至少包含一个联结词的命题称作，至少包含一个联结词的命题称作复合命题复合命题。 设设P和和Q是任意两个命题，则是任意两个命题，则 PQ，(PQ）(FQ），），P (Q P)等都是复合命题。等都是复合命题。 若若P和和Q是命题变元是命题变元，则上述各式均称作，则上述各式均称

3、作命题公式命题公式。P和和Q称作命题公式的分量。称作命题公式的分量。说明：说明：命题公式没有真值命题公式没有真值，仅当其中命题变元用确定的命题代入，仅当其中命题变元用确定的命题代入时，才得到一个命题。这个命题的真值，依赖于代换变元的时，才得到一个命题。这个命题的真值，依赖于代换变元的那些命题的真值。那些命题的真值。并不是由命题变元、联结词和一些括号组成的字符串都能并不是由命题变元、联结词和一些括号组成的字符串都能成为命题公式成为命题公式。 1-3 命题公式与翻译命题公式与翻译离散数学离散数学定义定义1-3.1 命题演算的命题演算的合式公式合式公式(wff)，规定为：，规定为： (1)单个命题变

4、元（常元）本身是一个合式公式。单个命题变元（常元）本身是一个合式公式。 (2)如果如果A是合式公式，那么是合式公式，那么A是合式公式。是合式公式。 (3)如果如果A和和B是合式公式，那么是合式公式，那么(AB)，(AB)，(AB）和）和(A B)都是合式公式。都是合式公式。 (4)当且仅当能够当且仅当能够有限次有限次地应用地应用(1)、(2)、(3)所得到所得到的包含命题变元、联结词和括号的符号串是合式的包含命题变元、联结词和括号的符号串是合式公式。公式。 这个合式公式的定义，是以递归形式给出的，其这个合式公式的定义，是以递归形式给出的，其中中(1)称为基础，称为基础，(2)(3)称为归纳，称

5、为归纳，(4)称为界限。称为界限。离散数学离散数学按照定义，下列公式都是合式公式：按照定义，下列公式都是合式公式： (PQ），），(PQ)，(P(PQ)， (PQ）(QR) （S T)而而 (PQ）(Q)，(PQ，(PQ）Q）等都不是合式公式。等都不是合式公式。离散数学离散数学v目的：减少使用括号的数量；目的：减少使用括号的数量；v约定：命题公式外层的括号可以省略；约定：命题公式外层的括号可以省略；、。v范例：范例： PQRv等价于等价于 ： （PQ）R ）v等价于等价于w ： （PQ）Rv不等价于不等价于w ： P（QR）离散数学离散数学v有了联结词的合式公式概念，我们可以把自然有了联结词的

6、合式公式概念，我们可以把自然语言中的有些语句，翻译成数理逻辑中的符号语言中的有些语句，翻译成数理逻辑中的符号形式。形式。v把一个用文字叙述的命题相应地写成由把一个用文字叙述的命题相应地写成由命题标命题标识符、联结词和圆括号识符、联结词和圆括号表示的合式公式，称为表示的合式公式，称为命题的符号化命题的符号化。v符号化应该注意下列事项：符号化应该注意下列事项： 确定给定句子是否为命题；确定给定句子是否为命题； 句子中联结词是否为命题联结词；句子中联结词是否为命题联结词； 要正确地表示原子命题和适当选择命题联结词。要正确地表示原子命题和适当选择命题联结词。二、翻译（符号化）二、翻译（符号化）离散数学

7、离散数学(1)分成原子命题；分成原子命题；(2)用大写字母代替命题；用大写字母代替命题；(3)按题意用联结词。按题意用联结词。离散数学离散数学自然语言的语句用自然语言的语句用 形式化形式化例题例题解解 找出各原子命题，并用命题符号表示：找出各原子命题，并用命题符号表示： A：我们：我们要要做到身体好。做到身体好。 B：我们：我们要要做到学习好。做到学习好。 C：我们：我们要要做到工作好。做到工作好。 P：我们：我们要要为祖国四化建设而奋斗。为祖国四化建设而奋斗。 例题例题1 试以符号形式写出命题：我们试以符号形式写出命题：我们要要(删掉删掉)做到身体做到身体好、学习好、工作好，为祖国四化建设而

8、奋斗。好、学习好、工作好，为祖国四化建设而奋斗。故命题可形式化为：故命题可形式化为：（A B C） P离散数学离散数学说明：定义用双条件表示，说明：定义用双条件表示，P12（6）离散数学离散数学自然语言的语句用自然语言的语句用 形式化形式化 要准确确定原子命题，并将其形式化；要准确确定原子命题，并将其形式化； 要选用恰当的联结词，尤其要善于识别自然语要选用恰当的联结词，尤其要善于识别自然语言中的联结词（有时它们被省略），否定词的位置要言中的联结词（有时它们被省略），否定词的位置要放准确；放准确； 必要必要时可以进行改述，即改变原来的叙述方式，时可以进行改述，即改变原来的叙述方式，但要保证表达意

9、思一致但要保证表达意思一致； 需要的括号不能省略，而可以省略的括号，在需要的括号不能省略，而可以省略的括号，在需要提高公式可读性时亦可不省略；需要提高公式可读性时亦可不省略； 要注意语句的形式化未必是唯一的。要注意语句的形式化未必是唯一的。 主要是以下几个方面：主要是以下几个方面：离散数学离散数学从表中可看出原命题从表中可看出原命题不能用前述五个联结不能用前述五个联结词单独写出。词单独写出。 解解 P：上海到北京的：上海到北京的14次列车是下午五点半开。次列车是下午五点半开。 Q：上海到北京的：上海到北京的14次列车是下午六点开。次列车是下午六点开。 在本例中，汉语的在本例中，汉语的“或或”是

10、不可兼或，而逻辑联结词是不可兼或，而逻辑联结词是是“可兼或可兼或”，因此不能直接对两命题析取。，因此不能直接对两命题析取。 真值可构造如表真值可构造如表1-3.1所示。所示。PQ原命题原命题TT FTF TFT TFF F表表1-3.1例题例题2 上海到北京的上海到北京的14次列车是下午五点半或六点开。次列车是下午五点半或六点开。离散数学离散数学可以用命题和联结词组可以用命题和联结词组合，可以把本命题表达合，可以把本命题表达为：为：(P Q）。）。PQ原命题原命题P Q(P Q)TT F T FTF T F TFT T F TFF F T F表表1-3.1续续例题例题2 上海到北京的上海到北京

11、的14次列车是下午五点半或六点开。次列车是下午五点半或六点开。或是或是QP 或是或是(P Q) (P Q) ，离散数学离散数学解解 若设若设 P：他聪明。：他聪明。 Q：他用功。：他用功。 在自然语言中这个在自然语言中这个“既既又又”显然与显然与“且且”的意义一样，的意义一样， 故本例可记为：故本例可记为： PQ 。例题例题3 他既聪明又用功。他既聪明又用功。离散数学离散数学解解 这里这里“虽虽但但”这个词不能用前述联这个词不能用前述联结词表达。结词表达。 但其实际意义是：他聪明且不用功。但其实际意义是：他聪明且不用功。 若设若设 P：他聪明。：他聪明。 Q：他用功。：他用功。 本例可表示为：

12、本例可表示为： PQ例题例题4 他虽聪明但不用功。他虽聪明但不用功。离散数学离散数学 解解 这个命题的意义，亦可理解为：如果你这个命题的意义，亦可理解为：如果你 不努力则你将失败。不努力则你将失败。 若设若设 P：你努力。：你努力。 Q：你失败。：你失败。 本例可表示为：本例可表示为： PQ例题例题5 除非你努力，否则你将失败。除非你努力，否则你将失败。离散数学离散数学 解解 这个命题的意义是：张三可以做这件事，这个命题的意义是：张三可以做这件事，并且李四也可以做这件事。并且李四也可以做这件事。 若设若设 P：张三可以做这事。：张三可以做这事。Q：李四可以做：李四可以做这事。这事。 本例可表示

13、为：本例可表示为： PQ例题例题6 张三张三或或李四李四都都可以做这件事。可以做这件事。离散数学离散数学 注意：注意： 从上面的例子中可以看到，自然语言中的一从上面的例子中可以看到，自然语言中的一些联结词，如：些联结词，如：“与与”“”“且且”“”“或或”“”“除非除非则则”等等都各有其具体含义，因此需分别不同情况翻译等等都各有其具体含义，因此需分别不同情况翻译成适当的逻辑联结词。为了便于正确表达命题间的成适当的逻辑联结词。为了便于正确表达命题间的相互关系，有时也常常采用相互关系，有时也常常采用列出列出“真值表真值表”的方法的方法，进一步分析各原命题，以此寻找逻辑联结词，使原进一步分析各原命题

14、，以此寻找逻辑联结词，使原来的命题能够正确地用形式符号予以表达。来的命题能够正确地用形式符号予以表达。 离散数学离散数学练习练习 把下列自然语言命题符号化：把下列自然语言命题符号化：(1)小张既聪明，又勤奋，所以他学习好。小张既聪明，又勤奋，所以他学习好。(2)或者你没有给我写信，或者它在途中丢失了。或者你没有给我写信，或者它在途中丢失了。解解 (1)设设 P：小张聪明。：小张聪明。 Q：小张勤奋。：小张勤奋。 R小张学习好。则命题小张学习好。则命题符号化为：符号化为：PQR(2)设设 P：你没有给我写信。：你没有给我写信。Q：信在途中丢失了。：信在途中丢失了。命题符号化为：命题符号化为： （

15、PQ) 命题符号化是很重要的，一定要掌握好，在命题推理中常常最先遇到的就是符号化一个问题，解决不好，等于说推理的首要前提没有了。 离散数学离散数学 1.真值表真值表 定义定义1-4.1 在命题公式中，在命题公式中，对于分量指派真值的各对于分量指派真值的各种可能组合，种可能组合，就确定了这个命题公式的各种真值情就确定了这个命题公式的各种真值情况，把它汇列成表，就是命题公式的况，把它汇列成表，就是命题公式的真值表真值表。P QP PQT TFTT FFF F TTTFFTT现举例说明如下：现举例说明如下：例题例题1 构造构造PQ的真值表。的真值表。解（见表解（见表 1-4.1 ）表表 1-4.11

16、-4 真值表与等价公式真值表与等价公式离散数学离散数学例题例题2 给出给出(PQ）P的真值表。的真值表。解解P QPQP(PQ）PTTTFFTFFFFFTFTFFFFTF表表1-4.2离散数学离散数学例题例题3 给出给出(PQ）（PQ）的真值表。）的真值表。解解 PQPQPQPQ（PQ） （PQ）TT F F T F TTF F T F F FFT T F F F FFF T T F T T表表1-4.3离散数学离散数学例题例题4 给出给出(PQ） （PQ）的真值表。）的真值表。解解PQPQ(PQ)PQPQ(PQ） （PQ）TT T F F F F TTF F T F T T TFT F T

17、T F T TFF F T T T T T表 1-4.4离散数学离散数学v 由表由表1-4.4 (表表1-4.2)可以看出，有一类公式不论命题可以看出，有一类公式不论命题变元作何种指派，其变元作何种指派，其真值永为真真值永为真(假假)，我们把这类，我们把这类公式记为公式记为T(F)。v 在真值表中，命题公式真值的取值数目，决定于分在真值表中，命题公式真值的取值数目，决定于分量的个数。例如，由量的个数。例如，由2个命题变元组成的命题公式个命题变元组成的命题公式共有四种可能的真值，由共有四种可能的真值，由3个命题变元组成的命题个命题变元组成的命题公式共有八种真值。公式共有八种真值。一般说来，一般说

18、来，n个命题变元组成个命题变元组成的命题公式共有的命题公式共有2n种真值情况。种真值情况。离散数学离散数学 从真值表中可以看到，有些命题公式在分量的不从真值表中可以看到，有些命题公式在分量的不同指派下，其同指派下，其对应的真值与另一命题公式完全相同对应的真值与另一命题公式完全相同，如如PQ与与PQ的对应真值相同，如表的对应真值相同，如表1-4.5所示。所示。 PQPQPQTT T TTF F FFT T TFF T T表1-4.5我们说我们说PQ和和PQ是等价的，是等价的，这在以后的推理中这在以后的推理中特别有用。特别有用。离散数学离散数学 同理同理(PQ)(PQ)与与P Q对应的真值相对应的

19、真值相同，如表同，如表1-4.6所示。所示。PQ P Q (PQ)(PQ)TT T TTF F FFT F FFF T T表表1-4.6离散数学离散数学二、等价公式二、等价公式 1.定义定义 定义定义1-4.2 给定两个命题公式给定两个命题公式A和和B，设，设P1，P2，Pn为所有出现于为所有出现于A和和B中的原中的原子变元，若给子变元，若给P1，P2，Pn任一组真任一组真值指派，值指派，A和和B的真值都相同，则称的真值都相同，则称A和和B是等价的或逻辑相等。是等价的或逻辑相等。记作记作A B。离散数学离散数学v在这里，请注意在这里，请注意和和的区别与联系的区别与联系：v区别：区别：是逻辑联结

20、词，属于目标语言中的是逻辑联结词，属于目标语言中的符号，它出现在命题公式中；符号，它出现在命题公式中；不是逻辑联不是逻辑联结词，结词，属于元语言中的符号，属于元语言中的符号，表示两个命题表示两个命题公式的一种关系，不属于这两个公式的任何公式的一种关系，不属于这两个公式的任何一个公式中的符号。一个公式中的符号。2、证明方法：、证明方法： 真值表法真值表法离散数学离散数学 由表1-4.7可知P Q与(PQ) (QP）真值相同，命题得证。例题例题5 证明证明 P Q (PQ) (QP)证明证明 列出其值表列出其值表 表表 1-4.7PQP QQPP Q (PQ) (QP）TT T T T TTF F

21、 T F FFT T F F FFF T T T T离散数学离散数学推导的证明方法推导的证明方法命题定律（表命题定律（表1-4.8列出的命题定律都可以用列出的命题定律都可以用真值表予以验证），见下表真值表予以验证），见下表1-4.8离散数学离散数学对合律P P1幂等律PP P，PP P2结合律(PQ）R P（QR）(PQ）R P（QR）3交换律PQ QPPQ QP4分配律P（QR） （PQ）（PR）P（QR） （PQ）（PR）5吸收律P（PQ） PP（PQ） P6德摩根律(PQ) PQ(PQ) PQ7同一律PF P，PT P8零律PT T，PF F9否定律PP T，PP F10PQ PQ表表1

22、-4.8离散数学离散数学例题例题6 验证吸收律验证吸收律 P（PQ） P P（PQ） P证明证明 列出真值表列出真值表 PQPQ P（PQ）PQP（PQ）TT T T T TTF F T T TFT F F T FFF F F F F 由表由表1-4.9可知吸收律成立。可知吸收律成立。表表1-4.9离散数学离散数学等价置换等价置换 在一个命题公式中，如果用公式置换命题的某在一个命题公式中，如果用公式置换命题的某个部分，一般地将会产生某种新的公式。个部分，一般地将会产生某种新的公式。 例如例如 Q(P(PQ)中以中以(PQ)取代取代(PQ)，则，则 Q(P(PQ) )就与原式不同。就与原式不同。

23、 为了保证取代后的公式与原始公式是等价的，为了保证取代后的公式与原始公式是等价的，故需对置换作出一些规定。故需对置换作出一些规定。 离散数学离散数学 定义定义1-4.3 如果如果X是合式公式是合式公式A的一部分，且的一部分，且X本本身也是一个合式公式，则称身也是一个合式公式，则称X为公式为公式A的的子公式子公式。 证明证明 因为在相应变元的任一种指派情况下，因为在相应变元的任一种指派情况下，X与与Y的的真值相同，故以真值相同，故以Y取代取代X后，公式后，公式B与公式与公式A在相应的在相应的指派情况下，其真值亦必相同，故指派情况下，其真值亦必相同，故A B。 口口 满足定理满足定理1-4.1条件

24、的置换称为条件的置换称为等价置换等价置换(等价代等价代换换)。 定理定理1-4.1 设设X是合式公式是合式公式A的子公式，若的子公式，若X Y，如果将，如果将A中的中的X用用Y来置换，所得到公式来置换，所得到公式B与公与公式式A等价，即等价，即A B。离散数学离散数学 例题例题7 证明证明Q(P(PQ) QP 证明证明 设设A：Q(P(PQ)， B：QP 因为因为 P(PQ) P 故故 A B 吸收律吸收律对对A B亦可用表亦可用表1-4.10（真值表）予以验证：（真值表）予以验证：离散数学离散数学PQPQP（PQ）QP（PQ）QPTT T T T TTF F T T TFT F F F FF

25、F F F T T有了最基本的的命题公式的等价关系，再利用定理有了最基本的的命题公式的等价关系，再利用定理1-4.1，就可，就可以推证一些更为复杂的命题等价公式。以推证一些更为复杂的命题等价公式。 表表 1-4.10离散数学离散数学 例题例题8 证明证明(PQ) (PQ) P P P T证明 (PQ) (PQ) P (QQ)合取对析取的分配律否定律同一律离散数学离散数学例题例题9 证明证明P (QR) Q(PR) R(QP) P (QR) P(Q R) R (Q P) R(QP)证明 P (QR) P(Q R) Q (P R) Q(PR)PQ PQ离散数学离散数学 例题例题10 证明证明(PQ

26、) (P (QR) (PQ) (PR) T T (P Q)(P R) (PQ) (PR) (PQ) (P Q)(P R) (PQ) (PR)原式左边(PQ) (P (QR) (PQ) (PR)证明离散数学离散数学化简如下语句：化简如下语句：“情况并非如此：若他不来，则我不去情况并非如此：若他不来，则我不去”。 离散数学离散数学解：首先符号化上述语句。解：首先符号化上述语句。 设设P：他来。：他来。Q：我去：我去 则原句：则原句：（PQ） 然后化简上述命题公式然后化简上述命题公式 （PQ） （ P Q ） P Q即：我去了，但他未来。即：我去了，但他未来。 离散数学离散数学v P：上午下雨，：上

27、午下雨，Q：我去看电影，：我去看电影，R：我在家看书；：我在家看书；S：我在家看报：我在家看报。（P Q） （P （R S ）P12：（：（7）a）离散数学离散数学作业：作业：P12： (7) bP17： （1）dP19： （7）f 离散数学离散数学 学习本节要深刻理解命题公式的定义，能够把用自然语言学习本节要深刻理解命题公式的定义，能够把用自然语言中的有些语句，翻译成数理逻辑中的符号形式。中的有些语句，翻译成数理逻辑中的符号形式。 合式公式合式公式：命题演算的合式公式：命题演算的合式公式(wff) 规定为：规定为： (1)单个命题变元本身是一个合式公式。单个命题变元本身是一个合式公式。 (2

28、)如果如果A是合式公式，那么是合式公式，那么A是合式公式。是合式公式。 (3)如果如果A和和B是合式公式，那么是合式公式，那么(AB)，(AB)，(AB）和和(A B)都是合式公式。都是合式公式。 (4)当且仅当能够有限次地应用当且仅当能够有限次地应用(1)、(2)、(3)所得到的包含命所得到的包含命题变元，联结词和括号的符号串是合式公式。题变元，联结词和括号的符号串是合式公式。 翻译翻译 把自然语言中的有些语句，翻译成数理逻辑中的把自然语言中的有些语句，翻译成数理逻辑中的符号形式。符号形式。 优先次序优先次序 规定联结词运算的优先次序为：规定联结词运算的优先次序为：、小结小结离散数学离散数学

29、 真值表真值表 在命题公式中，对于分量指派真值的各种可能组合，就确定在命题公式中，对于分量指派真值的各种可能组合，就确定了这个命题公式的各种真值情况，把它汇列成表，就是命题公式的真值了这个命题公式的各种真值情况，把它汇列成表，就是命题公式的真值表。表。 逻辑相等逻辑相等 给定两个命题公式给定两个命题公式A和和B，设，设P1，P2，Pn为所有出现为所有出现于于A和和B中的原子变元，若给中的原子变元，若给P1，P2，Pn任一组真值指派，任一组真值指派，A和和B的的真值都相同，则称真值都相同，则称A和和B是等价的或逻辑相等。记作是等价的或逻辑相等。记作A B。 子公式子公式如果如果X是合式公式是合式

30、公式A的一部分，且的一部分，且X本身也是一个合式公式，则本身也是一个合式公式，则称称X为公式为公式A的子公式。的子公式。 定理定理1-4.1 设设X是合式公式是合式公式A的子公式，若的子公式，若X Y，如果将，如果将A中的中的X用用Y来置换，所得到公式来置换，所得到公式B与公式与公式A等价，即等价，即A B。 10个命题定律。个命题定律。离散数学离散数学重点：合式公式的定义，两个合式公式等价重点：合式公式的定义，两个合式公式等价的定义，的定义，10个命题定律。个命题定律。难点：推证等价公式。难点：推证等价公式。离散数学离散数学作业：作业：P12： (7)b，c;P17： （1）dP19： （7

31、）a，f （8）b课下课下讨论讨论P18（5）、（）、（6）(不用写到作业本不用写到作业本)离散数学离散数学化简如下语句：化简如下语句：“情况并非如此：若他不来，则我不去情况并非如此：若他不来，则我不去”。 离散数学离散数学解：首先符号化上述语句。解：首先符号化上述语句。 设设P：他来。：他来。Q：我去：我去 则原句：则原句：（PQ） 然后化简上述命题公式然后化简上述命题公式 （PQ） （ P Q ） P Q即：我去了，但他未来。即：我去了，但他未来。 离散数学离散数学课程回顾v第第1次课：次课：命题；命题；5个联结词个联结词v第第2次课：次课：命题的翻译命题的翻译命题公式等价的两种证明方法命题公式等价的两种证明方法v真值表真值表v利用命题定律推导利用命题定律推导离散数学离散数学合式公式合式