离散数学-全套PPT课件.pptx

1主要内容命题逻辑基本概念命题逻辑等值演算命题逻辑推理理论一阶逻辑基本概念一阶逻辑等值演算与推理第一部分 数理逻辑 2第一章 命题逻辑的基本概念主要内容命题与联结词 命题及其分类 联结词与复合命题命题公式及其赋值 3命题与真值 命题：判断结果惟一的陈述句 命题的真值：判断的结果 真值的取值：真与假 真命题与假命题注意：感叹句、祈使句、疑问句都不是命题陈述句中的悖论，判断结果不惟一确定的不是命题 1.1 命题与联结词 4例1 下列句子中那些是命题？ (1) 是有理数. (2) 2 + 5 = 7. (3) x + 5 3. (4) 你去教室吗？ (5) 这个苹果真大呀！ (6) 请不要讲话！ (7) 2050年元旦下大雪. 假命题命题概念 真命题不是命题 不是命题 不是命题不是命题命题，但真值现在不知道 5命题分类：简单命题（也称原子命题）与复合命题简单命题符号化用小写英文字母 p, q, r, …, pi, qi, ri (i?1)表示简单命题用“1”表示真，用“0”表示假 例如，令 p： 是有理数，则 p 的真值为0， q：2 + 5 = 7，则 q 的真值为1 命题分类 6否定、合取、析取联结词定义1.3 设p, q为两个命题，复合命题“p或q”称作p与q的析取式，记作p∨q，∨称作析取联结词. 规定p∨q为假当且仅当p与q同时为假.定义1.1 设 p为命题，复合命题“非p”(或“p的否定”)称为p的否定式，记作?p，符号?称作否定联结词. 规定?p 为真当且仅当p为假.定义1.2 设p,q为两个命题，复合命题“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 (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:小元元拿一个苹果, 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 只要p，就q p仅当q 只有q 才p 除非q, 才p 或 除非q，否则非p，…． (3) 当 p 为假时，p?q恒为真，称为空证明 (4) 常出现的错误：不分充分与必要条件 12例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 13定义1.5 设 p, q为两个命题，复合命题“p当且仅当q”称作p与q的等价式，记作p?q，?称作等价联结词. 规定p?q为真当且仅当p与q同时为真或同时为假.p?q 的逻辑关系：p与q互为充分