离散数学PowerPoint 演示文稿12.ppt

《离散数学PowerPoint 演示文稿12.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、克拉玛依职业技术学院制作人:卢自娟2007年9月10日离散数学基础第一部分数理逻辑引言数理逻辑主要包括两部分的内容,命题逻辑和一阶逻辑.命题逻辑是研究由命题为基本单位构成的前提和结论之间的可推导关系.一阶逻辑又称谓词逻辑.案例:一个公安人员审查一件盗窃案,已知下列事实:(1)甲或乙盗窃了DVD(2)若甲盗窃了DVD,则作案时间不能发生在午夜前;(3)若乙的证词正确,则午夜时灯光未灭;(4)若乙的证词不正确,则作案时间发生在午夜前;(5)午夜时屋里灯灭了.试问:盗窃DVD的是甲还是乙主要内容１.1命题与联结词１.2命题公式与赋值１.3等值演算１.4析取范式与合取

2、范式１.5命题逻辑的推理理论1.1命题与联结词１.命题的概念所谓命题，是指具有非真必假的陈述句。而疑问句、祈使句和感叹句等因都不能判断其真假，故都不是命题。命题仅有两种可能的真值—真和假，且二者只能居其一真用1或T表示，假用0或F表示。由于命题只有两种真值，所以称这种逻辑为二值逻辑。命题的真值是具有客观性质的，而不是由人的主观决定的。例1.1判断下列句子中哪些是命题.(1)2是素数.(2)x+y>9.(3)太阳从西方升起.(4)乌鸦是黑色的.(5)这个男孩多勇敢啊!(6)明年中秋节的晚上是晴天.(7)您贵姓?(8)请把门开开!(9)地球外的星球上也有生物如果

3、一陈述句再也不能分解成更为简单的语句，由它构成的命题称为原子命题.原子命题是命题逻辑的基本单位。命题分为两类，第一类是原子命题，原子命题用大写英文字母P，Q，R…及其带下标的Pi，Qi，Ri，…表示。例:p:2是素数;q:乌鸦是黑色的.第二类是复合命题，它由原子命题、命题联结词和圆括号组成。２.命题联结词定义1.1设P表示一个命题，由命题联结词l和命题P连接成lP，称lP为P的否定式复合命题，lP读“非P”。称l为否定联结词(否定联结词“l”的定义可由表1.1.1表示之).例:P:10是素数真值为Flp:10不是素数真值为TQ:5是素数真值为TlQ5不是素数

4、真值为F由于“否定”修改了命题，它是对单个命题进行操作，称它为一元联结词.定义1.2设P和Q为两个命题,由命题联结词∧将P和Q连接成P∧Q,称P∧Q为命题P和Q的合取式复合命题，P∧Q读做“P与Q”,或“P且Q”。称∧为合取联结词.自然语言中,既…又…,不但…而且…虽然…但是…等都可以符号化为∧例1.3将下列命题符号化.(1)张路即聪明又用功.(2)张路不仅聪明,而且用功.(3)张路虽然不太聪明,但他很用功.(4)张路不是不聪明,而是不用功,解设P:张路聪明,Q:张路用功.则(1)到(4)分别符号化P∧Q，P∧QlP∧Q，l（lP）∧lQ定义.1.3设P和Q为两

5、个命题，由命题联结词∨把P和Q连接成P∨Q，称P∨Q为命题P和Q的析取式复合命题，P∨Q读做“P或Q”。称∨为析取联结词。自然语言中的“或”有二义性，有时具有相容性，有时具有排斥性，注意区分．例1.3将下列命题符号化(1)谢丹生于1972年或1973年.(2)吕小洲学过德语或法语．(3)派老王或老李中的一人到上海开会.分析:上述例题(1)(3)的或为排斥或,而(2)中的或为可兼或.解设Ｒ：谢丹生于1972年S:谢丹生于1973年Q:吕小洲学过德语　　Ｍ：吕小洲学过法语　Ｎ：派老王到上海开会　Ｈ：派老李到上海开会则:(1)可符号化为R∨S;(2)可符号化为

6、Q∨M;(3)可符号化为(N∧lH)∨(lN∧H)定义1.1.4设P和Q为两个命题，由命题联结词→把P和Q连接成P→Q，称P→Q为命题P和Q的条件式复合命题,简称条件命题P→Q读做“P条件Q”或者“若P则Q”。称→为条件联结词或蕴涵联结词．自然语言中,“只要Ｐ就Ｑ”，“Ｐ仅当Ｑ”，“只有Ｐ才Ｑ”等都可以符号化为P→Q的形式．自然语言中,“如果Ｐ则Ｑ”中的Ｐ与Ｑ往往有某种内在的联系，而在数理逻辑中，Ｐ与Ｑ不一定有联系．在数学和其他自然科学中，“如果Ｐ则Ｑ”表示的前件Ｐ为真，后件Ｑ为真的推理关系，但数理逻辑中不同例1.４将下列命题符号化(1)若3+3=6，则地球是运

7、动的.(2)只要a是4的倍数,a就是2的倍数.(3)a是4的倍数,仅当a是2的倍数．(4)只有a是2的倍数,a才是4的倍数解　设Ｐ：3+3=6Ｑ：地球是运动的Ｒ：a是4的倍数　Ｓ：a是2的倍数则(1)可符号化为P→Q(2)__(4)可符号化为R→S定义１.1.5令P与Q是两个命题，由命题联结词把P和Q连接成PQ，称PQ为命题P和Q的双条件式复合命题，　简称双条件命题，PQ读做“P当且仅当Q”，称为双条件联结词。例1.５将下列命题符号化(1)2+3=5当且仅当８是有理数；解　设Ｐ：2+3=5Ｑ：８是有理数则(1)可符号化为PQ(2)A,B两角相等当且

8、仅当他们是