离散数学命题与联结词.ppt

《离散数学命题与联结词.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1数理逻辑部分第一章命题逻辑第二章一阶逻辑2第一章命题逻辑逻辑：研究推理，关注推理的正确性数学上，证明定理；计算机科学中，证明程序实现了要求它完成的任务。逻辑重点研究命题之间的关系，而不是一个具体命题内容在自然语言中的意义.3例如，软工专业的学生都喜欢看宫廷剧《延禧攻略》.任何一个喜欢看《延禧攻略》的学生都是软工1701班的.软工专业的学生都是软工1701班的.真真真从逻辑的角度从语义的角度假41.1命题与联结词1.2命题公式与赋值1.3等值演算1.4析取范式与合取范式1.5命题逻辑的推理理论本章

2、内容51.1命题与联结词命题与真值原子命题复合命题命题常项命题变项联结词6命题与真值命题:判断结果惟一的陈述句.命题的真值:判断的结果.真值的取值:真与假.真命题:真值为真的命题.假命题:真值为假的命题.感叹句、祈使句、疑问句都不是命题！陈述句中的悖论以及判断结果不惟一确定的也不是命题！注意:理发师悖论7理发师悖论：在某个城市中有一位理发师，他的广告词是这样写的：“本人的理发技艺十分高超，誉满全城。我将为本城所有不给自己刮脸的人刮脸，我也只给这些人刮脸。我对各位表示热诚欢迎！”来找他刮脸的人络绎不

3、绝，自然都是那些不给自己刮脸的人。可是，有一天，这位理发师从镜子里看见自己的胡子长了，他本能地抓起了剃刀，你们看他能不能给他自己刮脸呢？如果他不给自己刮脸，他就属于“不给自己刮脸的人”，他就要给自己刮脸，而如果他给自己刮脸呢？他又属于“给自己刮脸的人”，他就不该给自己刮脸。8例1.1下列句子中哪些是命题？(1)是无理数.(2)2+5＝8.(3)x+5＞3.(4)你有铅笔吗？(5)这只兔子跑得真快呀！(6)请不要讲话！(7)我正在说谎话.真命题假命题真值不确定疑问句感叹句祈使句悖论(3)—(7)都不

4、是命题9命题的分类简单命题(原子命题)：简单陈述句构成的命题.复合命题：由简单命题与联结词按一定规则复合而成的命题.10例如p：是有理数，则p的真值为用小写英文字母p,q,r,…,pi,qi,ri(i≥1）表示简单命题，简单命题符号化用“1”表示真，用“0”表示假.1q：2+5=7，则q的真值为011联结词与复合命题1.否定式与否定联结词“”定义设p为命题，复合命题“非p”（或“p的否定”）称为p的否定式，记作p，符号称作否定联结词，并规定p为真当且仅当p为假.例如：p：10是素数，则p

5、：10不是素数.122.合取式与合取联结词“∧”定义设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q的合取式，记作p∧q，∧称作合取联结词，并规定p∧q为真当且仅当p与q同时为真.描述合取式的灵活性与多样性，分清简单命题与复合命题.注意:13例1.3将下列命题符号化.(1)丁楠既聪明又用功.(2)丁楠不仅聪明，而且用功.(3)丁楠虽然聪明，但不用功.(4)丁楠不是不聪明，而是不用功.(5)凌道恒与鞠奕明都是三好学生.(6)凌道恒与鞠奕明是同学.解：令p：丁楠聪明，q：丁楠用功，则(

6、1)p∧q(2)p∧q(3)p∧q(4)()p∧(q).14例1.3(续)令r:凌道恒是三好学生，s:鞠奕明是三好学生(5)r∧s.(6)令t:凌道恒与鞠奕明是同学，t是简单命题.(1)—(5)说明描述合取式的灵活性与多样性.(6)中“与”联结的是句子的主语成分，因而(6)中句子是简单命题.说明15定义设p,q为二命题，复合命题“p或q”称作p与q的析取式，记作p∨q，∨称作析取联结词，并规定p∨q为假当且仅当p与q同时为假.例1.4将下列命题符号化:(1)2或4是素数；(2)2或3是素数

7、；(3)4或6是素数；(4)小元元只能拿一个苹果或一个梨；(5)王晓红生于1989年或1990年.3.析取式与析取联结词“∨”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

8、∧w),又可符号化为v∨w,Why?17定义设p,q为二命题，复合命题“如果p,则q”称作p与q的蕴涵式，记作pq，并称p是蕴涵式的前件，q为蕴涵式的后件.称作蕴涵联结词，并规定，pq为假当且仅当p为真q为假.4.蕴涵式与蕴涵联结词“”18pq的逻辑关系：q为p的必要条件“如果p，则q”的不同表述法很多：若p，就q只要p，就qp仅当q只有q才p除非q,才p或除非q,否则非p，当p为假时，pq为真常出现的错误：分不清充分条件与必要条件！19例1.5设p:天冷，q:小王穿羽