离散数学ch01

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

1、1第一部分数理逻辑主要内容命题逻辑基本概念命题逻辑等值演算命题逻辑推理理论一阶逻辑基本概念一阶逻辑等值演算与推理2第一章命题逻辑的基本概念主要内容命题与联结词命题及其分类联结词与复合命题命题公式及其赋值31.1命题与联结词命题与真值命题：判断结果惟一的陈述句命题的真值：判断的结果真值的取值：真与假真命题与假命题注意：感叹句、祈使句、疑问句都不是命题陈述句中的悖论，判断结果不惟一确定的不是命题4命题概念例1下列句子中那些是命题？(1)2是有理数.假命题(2)2+5=7.真命题(3)x+5>3.不是命题(4)

2、你去教室吗？不是命题(5)这个苹果真大呀！不是命题(6)请不要讲话！不是命题(7)2050年元旦下大雪.命题，但真值现在不知道5命题分类命题分类：简单命题（也称原子命题）与复合命题简单命题符号化用小写英文字母p,q,r,…,p,q,r(i1)表示简单命题iii用“1”表示真，用“0”表示假例如，令p：2是有理数，则p的真值为0，q：2+5=7，则q的真值为16否定、合取、析取联结词定义1.1设p为命题，复合命题“非p”(或“p的否定”)称为p的否定式，记作p，符号称作否定联结词.规定p为真当且仅当p为假.定

3、义1.2设p,q为两个命题，复合命题“p并且q”(或“p与q”)称为p与q的合取式，记作p∧q，∧称作合取联结词.规定p∧q为真当且仅当p与q同时为真.定义1.3设p,q为两个命题，复合命题“p或q”称作p与q的析取式，记作p∨q，∨称作析取联结词.规定p∨q为假当且仅当p与q同时为假.7合取联结词的实例例2将下列命题符号化.(1)吴颖既用功又聪明.(2)吴颖不仅用功而且聪明.(3)吴颖虽然聪明，但不用功.(4)张辉与王丽都是三好生.(5)张辉与王丽是同学.8合取联结词的实例解令p:吴颖用功,q:吴颖聪明(1)pq(

4、2)pq(3)pq(4)设p:张辉是三好生,q:王丽是三好生pq(5)p:张辉与王丽是同学(1)—(3)说明描述合取式的灵活性与多样性(4)—(5)要求分清“与”所联结的成分9析取联结词的实例例3将下列命题符号化(1)2或4是素数.(2)2或3是素数.(3)4或6是素数.(4)小元元只能拿一个苹果或一个梨.(5)王小红生于1975年或1976年.10析取联结词的实例解(1)令p:2是素数,q:4是素数,pq(2)令p:2是素数,q:3是素数,pq(3)令p:4是素数,q:6是素数,pq(4)令p:小元元拿

5、一个苹果,q:小元元拿一个梨(pq)(pq)(5)p:王小红生于1975年,q:王小红生于1976年,(pq)(pq)或pq(1)—(3)为相容或(4)—(5)为排斥或,符号化时(5)可有两种形式，而(4)则不能11蕴涵联结词定义1.4设p,q为两个命题，复合命题“如果p,则q”称作p与q的蕴涵式，记作pq，并称p是蕴涵式的前件，q为蕴涵式的后件，称作蕴涵联结词.规定：pq为假当且仅当p为真q为假.(1)pq的逻辑关系：q为p的必要条件(2)“如果p,则q”有很多不同的表述方法：若p，就q

6、只要p，就qp仅当q只有q才p除非q,才p或除非q，否则非p，…．(3)当p为假时，pq恒为真，称为空证明(4)常出现的错误：不分充分与必要条件12蕴涵联结词的实例例4设p：天冷，q：小王穿羽绒服，将下列命题符号化(1)只要天冷，小王就穿羽绒服.pqpq(2)因为天冷，所以小王穿羽绒服.pq(3)若小王不穿羽绒服，则天不冷.qp(4)只有天冷，小王才穿羽绒服.qp(5)除非天冷，小王才穿羽绒服.(6)除非小王穿羽绒服，否则天不冷.pq(7)如果天不冷，则小王不穿羽绒服.qp(8)小王穿羽绒服仅当天冷的时

7、候.qp注意：pq与qp等值（真值相同）13等价联结词定义1.5设p,q为两个命题，复合命题“p当且仅当q”称作p与q的等价式，记作pq，称作等价联结词.规定pq为真当且仅当p与q同时为真或同时为假.pq的逻辑关系：p与q互为充分必要条件例5求下列复合命题的真值(1)2+2＝4当且仅当3+3＝6.1(2)2+2＝4当且仅当3是偶数.0(3)2+2＝4当且仅当太阳从东方升起.1(4)2+2＝4当且仅当美国位于非洲.0(5)函数f(x)在x可导的充要条件是它在x连续.00014小结本小节中p,q,r,…

8、均表示命题.联结词集为{,,,,}，p,pq,pq,pq,pq为基本复合命题.其中要特别注意理解pq的涵义.反复使用{,,,,}中的联结词组成更为复杂的复合命题.设p:2是无理数，q:3是奇数，r:苹果是方的，s:太阳绕地球转则复合命题(pq)((rs)p)是假命题.联结词的运算顺序