离散数学总复习.pptVIP

1

2主要内容命题逻辑根本概念命题逻辑等值演算命题逻辑推理理论一阶逻辑根本概念第一局部数理逻辑

3第一章命题逻辑的根本概念主要内容命题与联结词命题及其分类联结词与复合命题命题公式及其赋值

4命题与真值命题：判断结果惟一的陈述句命题的真值：判断的结果真值的取值：真与假真命题与假命题注意：感慨句、祈使句、疑问句都不是命题陈述句中的悖论，判断结果不惟一确定的不是命题〔我正在说假话〕1.1命题与联结词

5否认、合取联结词定义1.1设p为命题，复合命题“非p”(或“p的否认”)称为p的否认式，记作?p，符号?称作否认联结词.规定?p为真当且仅当p为假.是有理数是不对的p:是有理数符号化为?p

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

7定义1.3设p,q为两个命题，复合命题“p或q”称作p与q的析取式，记作p∨q，∨称作析取联结词.规定p∨q为假当且仅当p与q同时为假.析取联结词例3将以下命题符号化(1)2或4是素数.(2)2或3是素数.(3)4或6是素数.(4)小元元只能拿一个苹果或一个梨.(5)王小红生于1975年或1976年.

8定义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只要p，就qp仅当q只有q才p除非q,才p或除非q，否那么非p，…．(3)当p为假时，p?q恒为真，称为空证明(4)常出现的错误：不分充分与必要条件

9例4设p：天冷，q：小王穿羽绒服，将以下命题符号化(1)只要天冷，小王就穿羽绒服.(2)因为天冷，所以小王穿羽绒服.(3)假设小王不穿羽绒服，那么天不冷.(4)只有天冷，小王才穿羽绒服.(5)除非天冷，小王才穿羽绒服.(6)除非小王穿羽绒服，否那么天不冷.(7)如果天不冷，那么小王不穿羽绒服.(8)小王穿羽绒服仅当天冷的时候.蕴涵联结词的实例p?q注意：p?q与?q??p等值〔真值相同〕p?qp?qq?pq?pp?qq?pq?p

10定义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.(2)2+2＝4当且仅当3是偶数.(3)2+2＝4当且仅当太阳从东方升起.(4)2+24当且仅当美国位于非洲.(5)函数f(x)在x0可导的充要条件是它在x0连续.10011

11联结词集为{?,?,?,?,?}，?p,p?q,p?q,p?q,p?q为根本复合命题.其中要特别注意理解p?q的涵义.反复使用{?,?,?,?,?}中的联结词组成更为复杂的复合命题. 小结联结词的优先顺序：?,?,?,?,?,同级按先出现者先运算.

121.2命题公式及其赋值命题变项与合式公式命题变项合式公式合式公式的层次公式的赋值公式赋值公式类型真值表

13命题变项与合式公式命题常项：真值确定的简单命题命题变项〔命题变元〕：取值1或0的变元，表示真值可以变化的陈述句常项与变项均用p,q,r,…,pi,qi,ri,…,等表示.定义1.6合式公式〔简称公式〕的递归定义：(1)单个命题变项和命题常项是合式公式,称作原子命题公式(2)假设A是合式公式，那么(?A)也是(3)假设A,B是合式公式，那么(A?B),(A?B),(A?B),(A?B)也是(4)只有有限次地应用(1)—(3)形成的符号串才是合式公式几点说明：归纳或递归定义,元语言与对象语言,外层括号可以省去

14定义1.8设p1