离散数学命题与联结词

关于离散数学命题与联结词第1页，共25页，2023年，2月20日，星期五2第一章命题逻辑逻辑：研究推理，关注推理的正确性数学上，证明定理；计算机科学中，证明程序实现了要求它完成的任务。逻辑重点研究命题之间的关系，而不是一个具体命题内容在自然语言中的意义.第2页，共25页，2023年，2月20日，星期五3例如，软工专业的学生都喜欢看宫廷剧《延禧攻略》.任何一个喜欢看《延禧攻略》的学生都是软工1701班的.软工专业的学生都是软工1701班的.真真真从逻辑的角度从语义的角度假第3页，共25页，2023年，2月20日，星期五41.1命题与联结词1.2命题公式与赋值1.3等值演算1.4析取范式与合取范式1.5命题逻辑的推理理论本章内容第4页，共25页，2023年，2月20日，星期五51.1命题与联结词命题与真值原子命题复合命题命题常项命题变项联结词第5页，共25页，2023年，2月20日，星期五6命题与真值命题:判断结果惟一的陈述句.命题的真值:判断的结果.真值的取值:真与假.真命题:真值为真的命题.假命题:真值为假的命题.

感叹句、祈使句、疑问句都不是命题！陈述句中的悖论以及判断结果不惟一确定的也不是命题！注意:

理发师悖论第6页，共25页，2023年，2月20日，星期五7理发师悖论：在某个城市中有一位理发师，他的广告词是这样写的：“本人的理发技艺十分高超，誉满全城。我将为本城所有不给自己刮脸的人刮脸，我也只给这些人刮脸。我对各位表示热诚欢迎！”来找他刮脸的人络绎不绝，自然都是那些不给自己刮脸的人。可是，有一天，这位理发师从镜子里看见自己的胡子长了，他本能地抓起了剃刀，你们看他能不能给他自己刮脸呢？如果他不给自己刮脸，他就属于“不给自己刮脸的人”，他就要给自己刮脸，而如果他给自己刮脸呢？他又属于“给自己刮脸的人”，他就不该给自己刮脸。

第7页，共25页，2023年，2月20日，星期五8

例1.1下列句子中哪些是命题？

(1)是无理数.(2)2+5＝8.(3)x+5＞3.(4)你有铅笔吗？

(5)这只兔子跑得真快呀！

(6)请不要讲话！

(7)我正在说谎话.真命题假命题真值不确定疑问句感叹句祈使句悖论(3)—(7)都不是命题第8页，共25页，2023年，2月20日，星期五9命题的分类简单命题(原子命题)：简单陈述句构成的命题.

复合命题：由简单命题与联结词按一定规则复合而成的命题.第9页，共25页，2023年，2月20日，星期五10例如p

：是有理数，则p

的真值为

用小写英文字母p,q,r,…,pi,qi,ri(i≥1）表示简单命题，简单命题符号化用“1”表示真，用“0”表示假.1q

：2+5=7，则q

的真值为0第10页，共25页，2023年，2月20日，星期五11联结词与复合命题

1.否定式与否定联结词“”定义设p为命题，复合命题“非p”（或“p的否定”）称为p的否定式，记作p，符号称作否定联结词，并规定p

为真当且仅当p为假.例如：p：10是素数，则p：10不是素数.第11页，共25页，2023年，2月20日，星期五122.合取式与合取联结词“∧”

定义设p,q为二命题,复合命题“p并且q

”(或“p与q

”)称为p与q

的合取式，记作p∧q，∧称作合取联结词，并规定

p∧q为真当且仅当p与

q

同时为真.描述合取式的灵活性与多样性，分清简单命题与复合命题.注意:第12页，共25页，2023年，2月20日，星期五13

例1.3将下列命题符号化.(1)丁楠既聪明又用功.(2)丁楠不仅聪明，而且用功.(3)丁楠虽然聪明，但不用功.(4)丁楠不是不聪明，而是不用功.(5)凌道恒与鞠奕明都是三好学生.(6)凌道恒与鞠奕明是同学.解：令p

：丁楠聪明，q

：丁楠用功，则

(1)p∧q(2)

p∧q

(3)

p∧q

(4)

()p∧(q).第13页，共25页，2023年，2月20日，星期五14

例1.3(续)

令r

:凌道恒是三好学生，s

:鞠奕明是三好学生(5)r∧s.(6)令t

:凌道恒与鞠奕明是同学，t

是简单命题.(1)—(5)说明描述合取式的灵活性与多样性.(6)中“与”联结的是句子的主语成分，因而(6)中句子是简单命题.说明第14页，共25页，2023年，2月20日，星期五15定义设p,q为二命题，复合命题“p或q”称作p与q

的析取式，记作p∨q，∨称作析取联结词，并规定p∨q为假当且仅当p与q同时为假.例1.4将下列命题符号化:(1)2或4是素数；(2)2或3是素数；(3)4或6是素数；(4)小元元只能拿一个苹果或一个梨；(5)王晓红生于1989年或1990年.3.析取式与析取联结词“∨”第15页，共25页，2023年，2月20日，星期五16解：令p

:2是素数,q

:3是素数,

r:4是素数,

s

:6是素数,则(1),(2),(3)均为相容或.分别符号化为:p∨r,p∨q,r∨s,它们的真值分别为1,1,0.而(4),(5)为排斥或.令t

:小元元拿一个苹果，u

:小元元拿一个梨，则(4)符号化为(t∧u)∨(t∧u).令v:王晓红生于1989年,w:王晓红生于1990年,则(5)既可符号化为(v∧w)∨(v∧w),又可符号化为v∨w,Why?第16页，共25页，2023年，2月20日，星期五17定义设p,q为二命题，复合命题“如果p,则q”称作p与q的蕴涵式，记作pq，并称p是蕴涵式的前件，q为蕴涵式的后件.称作蕴涵联结词，并规定，pq为假当且仅当p为真q为假.4.蕴涵式与蕴涵联结词“”第17页，共25页，2023年，2月20日，星期五18pq

的逻辑关系：q

为p

的必要条件“如果

p，则

q”的不同表述法很多：

若p，就

q

只要

p，就

q

p

仅当

q

只有

q

才p

除非

q,才

p

或除非

q,否则非

p，当p为假时，pq为真常出现的错误：分不清充分条件与必要条件！第18页，共25页，2023年，2月20日，星期五19例1.5设p

:天冷，q

:小王穿羽绒服，将下列命题符号化(1)只要天冷，小王就穿羽绒服.(2)因为天冷，所以小王穿羽绒服.(3)若小王不穿羽绒服，则天不冷.(4)只有天冷，小王才穿羽绒服.(5)除非天冷，小王才穿羽绒服.(6)除非小王穿羽绒服，否则天不冷.(7)如果天不冷，则小王不穿羽绒服.(8)小王穿羽绒服仅当天冷的时候.

注意：pq

与qp

等值（真值相同）pqpqqppqqp

qppqqp第19页，共25页，2023年，2月20日，星期五20定义设p，q为二命题，复合命题“p当且仅当q”称作p与q的等价式，记作pq，称作等价联结词.并规定pq为真当且仅当p与q同时为真或同时为假.5.等价式与等价联结词“”说明:(1)pq

的逻辑关系:p与q互为充分必要条件,(2)pq为真当且仅当p与q同真或同假.第20页，共25页，2023年，2月20日，星期五21例1.6求下列复合命题的真值(1)2+2＝4当且仅当3+3＝6.(2)2+2＝4当且仅当3是偶数.(3)2+2＝4当且仅当太阳从东方升起.(4)2+2＝4当且仅当美国位于非洲.(5)函数f(x)在x0可导的充要条件是它在x0连续.10100第21页，共25页，2023年，2月20日，星期五22以上给出了5个联结词：,,,,，组成一个联结词集合{,,,,}，联结词的优先顺序为：,,,,;

如果出现的联结词同级，又无括号时，则按从左到右的顺序运算;若遇有括号时，应该先进行括号中的运算.本书中使用的括号全为圆括号.注意:①②③第22页，共25页，2023年，2月20日，星期五23逻辑联结词真值表小结第23页，共25页，2023年，2月20日，星期五24例1.7将下列命题符号化并求其真值.(1)如果3是合数，则4是素数，并且如果4是素数，则它不能被2整除；(2)如果当且仅当5是合数，则和都是有理数.解:(1)设p