离散数学与 课件 命题逻辑 .ppt

第2章 命题逻辑 实例 某单位要从A,B,C三人中选派若干人出国考察, 需满足下述条件: (1) 若A去, 则C必须去; (2) 若B去, 则C不能去; (3) A和B必须去一人且只能去一人. 问有几种可能的选派方案? 请根据下面事实，找出凶手： 1. 清洁工或者秘书谋害了经理。 2. 如果清洁工谋害了经理，则谋害不会发生在午夜前。 3. 如果秘书的证词是正确的，则谋害发生在午夜前。 4. 如果秘书的证词不正确，则午夜时屋里灯光未灭。 5. 如果清洁工富裕，则他不会谋害经理。 6. 经理有钱且清洁工不富裕。 7. 午夜时屋里灯灭了。 第2章 命题逻辑 2.1 命题逻辑基本概念 2.2 命题逻辑等值演算 2.3 范式 2.4 命题逻辑推理理论 2.1 命题逻辑基本概念 2.1.1 命题与联结词 命题与真值(简单命题, 复合命题) 联结词(?, ?, ?, ?, ?) 2.2.2 命题公式及其分类 命题公式及其赋值 真值表 命题公式的分类 命题及其真值 命题: 判断结果惟一的陈述句 命题的真值: 判断的结果,真或假 真命题: 真值为真的命题 假命题: 真值为假的命题 注意: 感叹句、祈使句、疑问句都不是命题 陈述句中的悖论以及判断结果不惟一确定的也不是 命题 例1 下列句子中那些是命题？ (1) 北京是中华人民共和国的首都. (2) 2 + 5 ＝8. (3) x + 5 ＞ 3. (4) 你会开车吗？ (5) 2050年元旦北京是晴天. (6) 这只兔子跑得真快呀！ (7) 请关上门！ (8) 我正在说谎话. 简单命题与复合命题 简单命题(原子命题):简单陈述句构成的命题 简单命题的符号化:用p, q, r, … ,pi,qi,ri (i≥1)表示 用“1”表示真，用“0”表示假 复合命题:由简单命题通过联结词联结而成的陈述句 例如 如果明天天气好, 我们就出去郊游 设p:明天天气好, q:我们出去郊游, 如果p, 则q 又如 张三一面喝茶一面看报 设p:张三喝茶, q:张三看报, p并且q 联结词与复合命题 定义2.1 设p为命题, 复合命题 “非p”(或 “p的否定”)称为 p的否定式, 记作?p, 符号?称作否定联结词, 并规定?p 为真当且仅当 p为假 例如 p:2是合数, ?p: 2不是合数, p为假, ?p为真 定义2.2 设p,q为二命题, 复合命题“p并且q”(或“p与q”)称 为p与q的合取式, 记作p∧q, ∧称作合取联结词, 并规定 p∧q为真当且仅当 p与q同时为真 例如 p:2是偶数, q: 2是素数, p∧q: 2是偶素数, p为真, q为真, p∧q为真 实例 例2 将下列命题符号化. (1) 王晓既用功又聪明. (2) 王晓不仅聪明，而且用功. (3) 王晓虽然聪明，但不用功. (4) 张辉与王丽都是三好生. (5) 张辉与王丽是同学. 解 联结词与复合命题(续) 定义2.3 设 p,q为命题, 复合命题“p或q”称作p与q的析取式, 记作p∨q, ∨称作析取联结词, 并规定p∨q为假当且仅当 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年. 解 联结词与复合命题(续) 定义2.4 设 p,q为二命题, 复合命题 “如果p,则q” 称作p与q 的蕴涵式, 记作p?q, 并称p是蕴涵式的前件, q为蕴涵式的 后件. ?称作蕴涵联结词, 并规定, p?q为假当且仅当 p为 真且q为假. 例如 如果明天天气好, 我们就出去郊游 设p:明天天气好, q:我们出去郊游, 形式化为 p?q 蕴涵联结词(续) p?q 的逻辑关系: q为p的必要条件, p为q的充分条件 “如果p,则q” 的多种表述方式： 若p,就q 只要p,就q 只有q 才p 除非q, 才p 除非q, 否则非p 当p为假时，p?q为真(不管q为真, 还是为假) 实例 例4 设p:天冷, q:小王穿羽绒服， 将下列命题符号化 (1) 只要天冷，小王就穿羽绒服. (2) 因为天冷，所以小王穿羽绒服