离散数学-第一章逻辑与证明

主讲：檀晓红上课形式、点播、 ，多种方式混合学习多用

、答疑中心、邮件沟通交流、

提问锻炼和培养自主学习的能力，顺利完成网络教育的课业考核方式平时作业15%考勤15%期末考试（闭卷）70%2内容：

离散数学预备知识：

数学计算机34逻辑、证明、数学归纳法集合、函数、数列计数、鸽巢原理、排列组合高级计数问题：递推关系、容斥原理关系、等价关系图，哈米尔顿回路，欧拉回路，平面图树，树的遍历、最小生成树逻辑研究

推理关注

推理过程是否正确研究

命题之间的联系6逻辑（logic）是研究推理的，关注推理的正确性，重点研究命题之间的关系，而不是一个具体命题的内容。考虑下面的论断：所有的数学家都穿凉鞋。任何一个穿凉鞋的人都是代数学家。因此，所有的数学家都是代数学家。逻辑并不能帮助确定这些命题是否为真；然而，如果前两个命题为真，逻辑可以保证命题所有的数学家都是代数学家。也为真。逻辑在数学上一般用来证明定理，在计算机科学中一般用来证明程序实现了要求它完成的任务。本章将

采用逻辑方法来证明逻辑命题，这种逻辑命题可能是形式化的或非形式化的，但却是必不可少的。7命题是一个陈述句，或真或假，不可以既真又假。命题是逻辑的基本构成单元下列句子(a)

~(e)哪个为真，哪个为假（不能既真又假）能整除7

的正整数只有1

和7

本身。多伦多是

的首都。对于每个正整数n，存在一个大于n

的素数。地球是宇宙中惟一存在生命的星球。买两张星期五去“大剧院”音乐会的票。(a)真

(b)假

(c)真(d)不知真假，但一定是非真即假。因此是命题(e)不是命题89用变量来表示命题（如p、q

和r）。p:1+1=3定义p

是命题1+1=3。p

pTFFTp为一个命题，则p的否定表示为p，是命题not

p¬

p

写做“p

的说法是不正确的”。如：p：巴黎是英国的首都¬

p：巴黎是英国的首都的说法是不正确的简言之：¬

p：巴黎不是英国的首都11两个连接命题的连接词：“与”（and）“或”（or）定义2:

p,

q

的合取表示成

p∧q即“p

and

q”“p并且q”定义3：

p,

q的析取表示成

p∨q即“p or

q”,

“

p或q”12复合命题的真值可以由真值表来表达。用T

代表真，F

代表假。复合命题p∧q，p

∨q的真值由下列真值表pqp∧qTTTTFFFTFFFFpqp

∨

qTTTTFTFTTFFF13p∧q:p∨q:天正在下雨并且天很冷天正在下雨或者天很冷例如：命题“天正在下雨”与“天很冷”可以连接成单一命题形式“天正在下雨与天很冷”。“与”和“或”的形式化定义。p:天正在下雨 q:

天很冷p:

3<5q:巴黎是英国的首府则p,q皆为假，析取p∨q表示：3<5或巴黎是英国的首府假题（如p

∨q）在一般的语言中，组合起来通常

的是有关联的内容，但在逻辑中并不关心每个命题的内容是否相关，只关心命题真值之间的关系。1415定义4：异或p⊕q，当p和q中只有一个为真时，命题为真，否则为假pqp

⊕qTTFTFTFTTFFF某参与竞选的宣布：如果我当选了，那么我将会减税。——条件命题16定义4：如果p和q是命题，那么命题：

“若p则q”称为条件命题，并表为p

→

q命题p称为假设（或前提、前项）命题q称为结论（或推论）条件语句又称“蕴含”p：如果我当选了q：我将减税假设是“这位结论是“这位当选了”，会减税”。17如何确定命题的真值？先假设“这位若他减税，当选了”：题显然为真。（p

→q

为真）反之，他没有减税，则

题为假。（p

→q

为假。）再假设“这位

没有当选”：减了或没减，此时与题为

结论。这时能得出当这位没有当选时，无论无关，当然也不怎样，

的命题都为真。1819条件命题的真值表pqp

→

qTTTTFFFTTFFT：“如果今天天晴，那么去海滩”时，这个只有

天天晴，而我们不去海滩命题为假，否则上述命题成立。：“如果今天是星期五，那么2+3=5”该命题总是成立，因为2+3=5总是为真“如果今天是星期五，那么2+3=6”该命题 天不是星期五 时，成立20一下命题：对于所有的实数x，若x>0，则x2

>0

为真。令p

：x

>0，令q

：x2>0。现在考虑当p

为

情况。若x

=-2，则p

为假，但q

为真。为了在这种情况下使命题为真，必须把p

→q在p

为假且q

为真时定义为真。若x=0，则p和q

都为假。为了在这种情况下使命题为真，必须把p→q

在p和q

都为假时定义为真。2122条件命题：p

→

q逆：

q→

p反（否）：

p

→

q倒置（逆否）：

q

→

p例：命题“每当下雨时，主队就能获胜”原命题p

→

q：如果下雨，那么主队就能获胜逆q

→

p

：如果主队获胜，那么下雨了倒置

q→

p：如果主队没有获胜，那么没有下雨反

p

→

q

：如果没有下雨，那么主队没有获胜23优先级:

(

)

假设：p真q假r真，给出下面每个命题的真值(p

q)

r(p

q)

rp

(q

r)p

(q

r)24构造真值表

(p

q)

(p

q)pq

qp

qp

q(p

q)

(p

q)TTFTTTTFTTFFFTFFFTFFTTFF新生，才可以从校园网访“只有你主修计算机科学问因特网”设：a:你可以从校园网c:你主修计算机科学因特网f:你是个新生问题：该语句的等价说法（

）：A“如果你主修计算机科学，或者你不是新生，那么你可以从校园网 因特网”B“如果你可以从校园网 因特网，那么你主修了计算机科学，或者你不是新生”所以，形式化表示为：

a

(c

f)25（a）如果Mary努力学习，她将成为一名好学生。仅当John是大二、大三或大四的学生时，他才学习微积分。你一唱歌，

耳朵就难受。Cubs获得世界职业棒球大赛冠军的必要条件是他们有一个右手的替补投手。Maria

法国的充分条件是Maria

到达了埃菲尔铁塔。2627仅当John

是大二、大三或大四的学生时，他才学习微积分(b)这个句子的意思是如果John

要学习微积分，则他必须是大二、大三或大四的学生。如果他是大一的学生，则不能学习微积分。所以，如果John学习微积分，那么他一定是大二、大三或大四的学生。这个句子等价于如果John学习微积分，则他是大二、大三或大四的学生。而不等价于如果John是大二、大三或大四的学生，则他学习微积分。如果John

是大二、大三或大四的学生，他可能学习微积分，也可能不学习微积分。（具有学习微积分的条件，但可能不打算学。）“如果p，则q”强调前提，“p

仅当q”强调结论，两者只有形式上的区别。28(d)Cubs获得世界职业棒球大赛冠军的必要条件是他们有一个右手的替补投手。注意：必要条件成立时并不确保结果成立；但是，若必要条件不成立，则结果一定不成立。上面的句子的含义为：如果Cubs获得世界职业棒球大赛的冠军，可以肯定他们有一个右手的替补投手，因为如果没有这个投手，则他们不可能获得世界职业棒球大赛的冠军。所以这个句子的等价形式为如果Cubs

获得世界职业棒球大赛的冠军，则他们有一个右手的替补投手。注意如果Cubs

他们有一个右手的替补投手，则他们获得世界职业棒球大赛的冠军。不是这个句子的等价形式。有一个右手的替补投手并不能保证他们获得世界职业棒球大赛的冠军。然而，如果没有一个右手的替补投手，则他们肯定不能获得世界职业棒球大赛的冠军。如果充分条件不成立，则结果可能成立也可能不成立；但如果条件成立，则可以保证结果成立。在

Maria

法国的充分条件是Maria到达了埃菲尔塔。中，如果Maria

到达了埃菲尔铁塔，则保证一定到了法国。（当然，通过其他方法也可以

法国，比如去里昂。）于是，上面的句子的等价形式为如果Maria

到达了埃菲尔铁塔，则Maria

了法国。注意如果Maria

法国，则Maria

到达了埃菲尔铁塔。不是上面的句子的等价形式。前面已经提到过，不去埃菲尔铁塔，到达其他地方也可以 法国。29例：当文件系统满时，自动应答不能够发出p:自动应答系统能够发出q:文件系统满了p:自动应答系统不能够发出规范说明表示为：q

p系统规范说明应该一致，无 的需求30确定下列系统规范说明是否一致消息 在缓冲区中或者被重传消息没有缓存在缓冲区中消息被重传如果

消息

在缓冲区中，那么它被重传解：p:

消息 在缓冲区中q:p

qpp

q一致的。pq

pp

qp

qTTFTTTFFTFFTTTTFFTFT大多数网上搜索引擎支持布尔检索技术，以找到有关特定 的网页例：用布尔检索找出关于新墨西哥州(NewMexico)各大学的网页New

and

Mexico

and

University找出与新墨西哥州或亚利桑那州的大学有关网页(New

and

Mexico

Or

Arizona)

and

University找出有关墨西哥的大学的网页(Mexico

and

University)

Not

New32一个岛上居住着两类人——骑士和 。骑士说的都是真话，而 总是说谎。现在碰到了岛上的两个人A和B，如果A说“B是骑士”，B说“我们两人不是一类人”。请判断A、B的

。解：每个人要么是骑士，要么是

。假设A是骑士，那么他说的是真话，即B也是骑士，那么B应当说真话，但B所说并非如此，所以A不是骑士假设A是 ，那么他说的是谎话，则B也是 ，那么B也应当说谎话，与题目所给的条件一致。所以A和B都是

。331.

条件命题？条件命题如何表示？2.给出条件命题的真值表。3.在条件命题中，4.在条件命题中，前提？结论？.必要条件？充分条件？p

→q

的逆命题？双条件命题？9.P

和Q

逻辑等价的含义是什么？10.

p

→q

的逆否命题？34Joey将通过离散数学考试,如果他学习努力。Rosa可以毕业,如果她获得160学分。Fernando

一台计算机的必要条件是他得到2000美圆。Katrina选修算法课的充分条件是她学过离散数学。当可以制造出更好的汽车时，Buick会制造它们。当

讲

，听众会睡觉。仅当程序具有良好的结构，才是可读的。1.

如果Joey学习努力，则他将通过离散数学考试。4.

如果Katrina通过离散数学考试，则她将修算法课。7.

如果程序是可读的，则它具有良好的结构。8.

（对于练

）如果Joey通过离散数学考试，则他学习努力。351.

如果Joey学习努力，则他将通过离散数学考试。２.如Rosa

获得160学分，她可以毕业。３、如果Fernando

了一台计算机，那么他一定得到了2000美圆4.

如果Katrina通过离散数学考试，则她将修算法课。５、如果可以制造出更好的汽车，Buick会去制造的６、如果 讲课，听众会睡觉7.

如果程序是可读的，则它具有良好的结构。8.

（对于练

）如果Joey通过离散数学考试，则他学习努力。36定义1复合命题的永真式（重言式）：无论其中题的真值是什么，该复合命题的真值总是真。：真值

是

复合命题。可能式：既不永真又不

题例：p

pp

pp

∧pTFTFFTTF3738pq

（p∨q）p∧qTTFFTFFFFTFFFFTT任何情况下都有相同真值的两个复合命题称为逻辑等价定义：如果p↔q是永真式，那么命题p，q是逻辑等价，记为p

≡q判断方法之一：真值表德摩根定律（p∨q）≡

p∧

q（p∧q）≡

p

∨

qpqp

q(p

q

)(q

p)p

pTTTTTTTFFFTFFTFTFFFFTTTT3940证明命题:

p∨(q

∧

r)与

(p∨q)

∧(p∨r)

等价pqrq

∧

rp∨(q

∧

r)p∨qp∨r(p∨q)

∧(p∨r)TTTTTTTTTTFFTTTTTFTFTTTTTFFFTTTTFTTTTTTTFTFFFTFFFFTFFFTTFFFFFFFF41证明:¬

(p

→q)≡p∧¬

q解：¬

(p

→q)≡¬

(¬

p∨q)≡

¬

(¬

p)

∧

¬

q≡p∧

¬

q证明:(p

∧q)→(p

∨q)永真证明：¬

(p

∨

(¬

p

∧

q)

)≡

¬

p∧

¬

q证明:¬

(p

→q)≡p

∧¬

q证：通过写出P

=¬

(p

→q)和Q=p∧¬

q的真值表来验证对于任意给定的p

和q的真值，或者P

和Q都为真，或者P

和Q都为假。42用德摩根律表达“麦克有一部 和一台电脑”的否定解：p麦克有一部

，q麦克有一台电脑那么原命题表示为：p

∧q则其否定（p∧q）等价于

p

∨

q即：“麦克没有一部

或没有一台电脑”用德摩根律表达“John或者Jessi将去看 ”的否定解：p:John去看

，q：Jessi去看那么原命题表示为：p∨q则其否定（p

∨q）等价于

p

∧

q即：“John和Jessi都不去看

”4344句子p:n是一个奇数p

不是一个命题句子p

不是命题，因为p

的真假取决于n

的值。例如，当n

=103

时p

为真，当n

=8

时p

为假。因为数学和计算机科学中的多数句子使用变元，所以必须扩展逻辑系统使之包括这样的句子。——谓词逻辑含变量的语句：x

>3，即“x

大于3”主语

谓词令P(x)表示x

>3，其中P表示谓词“大于3”,x是变量命题函数P

(x)，表示P在x的值。如：令p(x)表示x

>3，则p(4),p(2)的真值分别为T和F如：Q(x,y)表示语句“x=y+3”,则Q(1,2)和Q(3,0)的真值是什么？4546P(n)

：n

是一个奇数D

正整数集合P

是一个命题函数例如，如果n

=1，得到命题P(1):１是一个奇数（命题为真）。如果n

=2，得到命题P(2):2

是一个奇数（命题为假）。47命题函数P本身既不为真也不为假。然而，对于命题论域中的每一个x，P(x)是一个命题，所以它或者为真或者为假。可以把命题函数当成一个命题类，论域中的每个元素对应一个命题。例如，如果P是一个命题函数，其论域是正整数集合，便得到命题类P(1),

P(2),...每个P(1),P(2),...或者为真，或者为假。下面所述的都是命题函数。n2+2n是奇数（

域是正整数集合）A(c,n)：计算机c被连接到网络nA(x):

计算机x正被一个

者命题函数，本身既不为真，也不为假，而对于每个

x,

p(x)是一个命题4849量化：谓词在一定范围内的取值谓词演算：处理谓词和量词的逻辑领域全称量词：P(x)的全称量化表示语句“P(x)对x在其论域中的所有值都为真”存在量词：P(x)的存在量化表示语句“论域中至少有一个值满足P(x)为真”量词命题何时为真何时为假全称量词∀∀xP(x)对每一个x，P(x)都为真有一个x，使得P(x)为假存在量词∃∃xP(x)有一个x，使得P(x)为真对每一个x，P(x)为假对于全称量词语句

x

(x2

≥

0)论域是实数集合。这个句子为真。对于全称量词语句

x

(x2

-

1

>0)论域是实数集合。这个句子为假，因为当x

=1

时，命题12

-

1>

0为假。所以1

是语句

x(x2

-

1

>

0)

的一个反例。虽然x取某些值时命题函数为真，但一个反例就可以使全称量词语句为假。51例：P(x)表示语句“x2＞0”，论域为不超过4的真整数，∃xP(x)的真值是什么？解：论域为{1，2，3，4}，P(1),P(2),P(3)为真。52唯一量词∃！：存在唯一的x使∃x

P(x)为真53x<0

(x2>0)y≠0

(y3

≠

0)x(x<0

→x2>0)y(y≠0

→y3

≠

0)全称量词的约束等价于一个条件语句的全称量化∃z>0

(z2=2)

∃z(z>0

∧(z2=2)存在量词的约束等价于一个合取的存在量化54量词比所有命题演算的逻辑运算符的优先级高如语句xP(x)

∨

Q(x)等价于（

A

）？A.

(xP(x))

∨

Q(x)B.

(xP(x)

∨

Q(x))绑定&当量词作用于变量x时，x是绑定的没有被量词绑定的变量是

的例：∃x(x+y=1)其中x

是绑定变量，y是 变量5556考虑语句的否定：“班里每个学生都学过微积分”即xP(x)其中P(x)：x学过离散数学其否定：“并非班里每个学生都学过微积分”也就是：“班里有学生没有学过微积分”，即∃

xP(x)等价关系：xP(x)

≡∃

xP(x)57再考虑“班里有个学生学过离散数学”即∃xP(x)其中P(x)：x学过离散数学否定：“并非班里有学生学过微积分”也就是：“班里没有学生学过微积分”即“班里每个学生都没有学过微积分”P(x)：x学过离散数学x

P(x)等价关系：

∃

xP(x)

≡

x

P(x)量词否定的规则：量词的德摩根定律否定等价语句何时为真何时为假

∃

xP(x)∀xP(x)对每个x，P(x)都为假有x，使得P(x)为真∀xP(x)∃xP(x)有x，使得P(x)为假对每一个x，P(x)为真例：“有的

诚实”的否定是：解：H(x):x是诚实的，∃xH(x)，则

∃xH(x)≡∀xH(x)表示：每个都不诚实。例：“所有 人都吃干酪汉堡包”的否定：解：设C(x):

x吃干酪汉堡包，

∀xC(x)∀xC(x)

≡

∃

xC(x),

即：有些

人不吃。。。5859用谓词和量词表达：“这个班上某个学生去过墨西哥”引入量词x,表示某个学生x，论域是这个班级引入谓词M(x)，表示x

去过墨西哥（1）

x

M(x)引入变量x，表示某个人x,论域是所有人引入谓词S(x)，表示x是这个班上的一个学生则：x(S(x)∧M(x))表示某个人，他是这个班级的学生，并且他去过墨西哥，或者去过用谓词和量词表示“这个班上每个学生或者去过墨西哥”C(x)表示x去过

，M(x)表示x去过墨西哥（1）如果x的论域是这个班级的学生，则表示为：x

(C(x)∨M(x))（2）如果x的论域是所有人则表示为：x

(S(x)

(C(x)∨M(x))表示语句“对于每一个人，如果他是这个班级的学生，那么他去过

或去过墨西哥”6061用谓词与量词表达系统说明：每封大于1MB的邮件将被压缩令S(m,y)表示“邮件m大于yMB”C(m)表示“邮件m被压缩”其中m的论域是所有邮件，y的论域是正实数则：：x(S(m,1)

C(m))62如果用户处于活动状态，那么至少有一个网络连接有效令A(u)表示“用户u处于活动状态”，u的论域是所有用户S(n,x)表示“网络连接n处于x状态其中n的论域时所有的网络连接，x的论域是（available,

unavailable）u

A(u)

n

S(n,

available)63论证：前几句是前提，最后一句是结论。例：“所有狮子都是凶猛的”“有些狮子不喝咖啡”“有些凶猛的动物不喝咖啡”引入量词x,表示所有动物引入谓词P(x)——“x是狮子”Q(x)——“x是凶猛的”R(x)——“x喝咖啡”则这些语句可以表示为右表的形式：x(

P(x)

Q(x))x

(

P(x)

∧

R(x))x

(Q(x)

∧

R(x))64例：“所有蜂鸟都是五彩斑斓的”“没有大鸟以蜜为生”“不以蜜为生的鸟都色彩单调”“蜂鸟是小鸟”引入量词x,表示所有鸟的集合引入谓词：P(x)：x是只蜂鸟Q(x)：x是大的

R(x)：x以蜜为生

S(x):x是五彩斑斓的则这些语句可以表示为：x(

P(x)

S(x))

x(Q(x)

∧

R(x))x(

R(x)

S(x))x(

P(x)

Q(x)).5.命题函数？论域？全称量词语句？反例？存在量词语句？叙述一般化的De

Morgan

逻辑定律。解释如何证明全称量词语句为真。解释如何证明存在量词语句为真。解释如何证明全称量词语句为假。解释如何证明存在量词语句为假。6566考虑用符号表示句子任意两个正实数的和为正。如果要表示这个句子，首先需要为这两个正实数分别选择一个变量，记做x

和y。这个句子可以写做：如果x

>0

与y

>0，则x

+y

>0。句子中提到任意的两个正实数的和都是正数，所以需要两个全称量词。xy((x

>

0)∧(y

>

0)→(x

+

y>

0))67例：P(x,y):“x+y=y+x”,量化语句：xyP(x,y)

与yxP(x,y)的真值都为真例：Q(x,y)：“x+y=0”

yx

P(x,y)表示“有个实数y，对任意实数x，