资源描述
1,第2章 命题逻辑,2,实例,某单位要从A,B,C三人中选派若干人出国考察, 需满足下述条件: (1) 若A去, 则C必须去; (2) 若B去, 则C不能去; (3) A和B必须去一人且只能去一人. 问有几种可能的选派方案?,3,请根据下面事实，找出凶手： 1. 清洁工或者秘书谋害了经理。 2. 如果清洁工谋害了经理，则谋害不会发生在午夜前。 3. 如果秘书的证词是正确的，则谋害发生在午夜前。 4. 如果秘书的证词不正确，则午夜时屋里灯光未灭。 5. 如果清洁工富裕，则他不会谋害经理。 6. 经理有钱且清洁工不富裕。 7. 午夜时屋里灯灭了。,实际推理题：,4,第2章 命题逻辑,2.1 命题逻辑基本概念 2.2 命题逻辑等值演算 2.3 范式 2.4 命题逻辑推理理论,5,2.1 命题逻辑基本概念,2.1.1 命题与联结词 命题与真值(简单命题, 复合命题) 联结词(, , , , ) 2.2.2 命题公式及其分类 命题公式及其赋值 真值表 命题公式的分类,6,命题及其真值,命题: 判断结果惟一的陈述句 命题的真值: 判断的结果,真或假 真命题: 真值为真的命题 假命题: 真值为假的命题 注意: 感叹句、祈使句、疑问句都不是命题 陈述句中的悖论以及判断结果不惟一确定的也不是 命题,7,例1 下列句子中那些是命题？ (1) 北京是中华人民共和国的首都. (2) 2 + 5 8. (3) x + 5 3. (4) 你会开车吗？ (5) 2050年元旦北京是晴天. (6) 这只兔子跑得真快呀！ (7) 请关上门！ (8) 我正在说谎话.,真命题,假命题,真值不确定,疑问句,感叹句,祈使句,悖论,(1),(2),(5)是命题, (3),(4),(6)(8)都不是命题,真值确定, 但未知,实例,8,简单命题与复合命题,简单命题(原子命题):简单陈述句构成的命题 简单命题的符号化:用p, q, r, ,pi,qi,ri (i1)表示 用“1”表示真，用“0”表示假 复合命题:由简单命题通过联结词联结而成的陈述句 例如 如果明天天气好, 我们就出去郊游 设p:明天天气好, q:我们出去郊游, 如果p, 则q 又如 张三一面喝茶一面看报 设p:张三喝茶, q:张三看报, p并且q,9,联结词与复合命题,定义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的合取式, 记作pq, 称作合取联结词, 并规定 pq为真当且仅当 p与q同时为真 例如 p:2是偶数, q: 2是素数, pq: 2是偶素数, p为真, q为真, pq为真,10,实例,例2 将下列命题符号化. (1) 王晓既用功又聪明. (2) 王晓不仅聪明，而且用功. (3) 王晓虽然聪明，但不用功. (4) 张辉与王丽都是三好生. (5) 张辉与王丽是同学. 解,记 p:王晓用功, q:王晓聪明,(1) pq,(2) pq,(3) pq,(4) 记 r:张辉是三好生, s:王丽是三好生, rs,(5) 简单命题, 记 t:张辉与王丽是同学,11,联结词与复合命题(续),定义2.3 设 p,q为命题, 复合命题“p或q”称作p与q的析取式, 记作pq, 称作析取联结词, 并规定pq为假当且仅当 p与q同时为假. 例如 张三和李四至少有一人会英语 设 p:张三会英语, q:李四会英语, 符号化为pq 相容或与排斥或 例如 这件事由张三和李四中的一人去做 设 p:张三做这件事, q:李四做这件事 应符号化为 (p q) (p q),12,实例,例3 将下列命题符号化 (1) 2或4是素数. (2) 2或3是素数. (3) 4或6是素数. (4) 元元只能拿一个苹果或一个梨. (5) 王晓红生于1975年或1976年. 解,记 p:2是素数, q:3是素数, r:4是素数, s:6是素数,(1) pr,(2) pq,(3) rs,(4) 记t:元元拿一个苹果,u:元元拿一个梨,真值:1,真值: 1,真值: 0,(tu)(tu),(5) 记v:王晓红生于1975年,w:王晓红生于1976年,(vw)(vw),又可形式化为 vw,13,联结词与复合命题(续),定义2.4 设 p,q为二命题, 复合命题 “如果p,则q” 称作p与q 的蕴涵式, 记作pq, 并称p是蕴涵式的前件, q为蕴涵式的 后件. 称作蕴涵联结词, 并规定, pq为假当且仅当 p为 真且q为假. 例如 如果明天天气好, 我们就出去郊游 设p:明天天气好, q:我们出去郊游, 形式化为 pq,14,蕴涵联结词(续),pq 的逻辑关系: q为p的必要条件, p为q的充分条件 “如果p,则q” 的多种表述方式： 若p,就q 只要p,就q 只有q 才p 除非q, 才p 除非q, 否则非p 当p为假时，pq为真(不管q为真, 还是为假),15,实例,例4 设p:天冷, q:小王穿羽绒服， 将下列命题符号化 (1) 只要天冷，小王就穿羽绒服. (2) 因为天冷，所以小王穿羽绒服. (3) 若小王不穿羽绒服，则天不冷. (4) 只有天冷，小王才穿羽绒服. (5) 除非天冷，小王才穿羽绒服. (6) 除非小王穿羽绒服，否则天不冷. (7) 如果天不冷，则小王不穿羽绒服.,注意： pq 与 qp 等值（真值相同）,pq,pq,qp 或 pq,pq,qp,qp,pq 或 qp,16,联结词与复合命题(续),定义2.5 设p, q为命题, 复合命题 “p当且仅当q”称作p与q的 等价式, 记作pq, 称作等价联结词. 并规定pq为真当 且仅当 p与q同时为真或同时为假. pq 的逻辑关系: p与q互为充分必要条件 例如 这件事张三能做好, 且只有张三能做好 设p:张三做这件事, q:这件事做好了 形式化为: pq,17,实例,例5 求下列复合命题的真值 (1) 2+24 当且仅当 3+36. (2) 2+24 当且仅当 3是偶数. (3) 2+24 当且仅当 太阳从东方升起. (4) 2+25 当且仅当 美国位于非洲. (5) f (x)在x0处可导的充要条件是它在 x0处连续.,1,0,1,1,0,18,联结词与复合命题(续),联结词优先级:( ), , , , 同级按从左到右的顺序进行,19,合式公式,命题常项: 简单命题 命题变项: 真值可以变化的陈述句 定义2.6 合式公式 (命题公式, 公式) 递归定义如下： (1) 单个命题常项或变项是合式公式,并称作原子合式公式 (2) 若A是合式公式, 则 (A)也是合式公式 (3) 若A, B是合式公式, 则(AB), (AB), (AB), (AB)也 是合式公式 (4) 只有有限次地应用(1)(3)形成的符号串才是合式公式 说明:(1) 元语言符号与对象语言符号 (2) 在不影响运算顺序时, 括号可以省去 例如 0, p, pq, (pq)(pr), pq r, (pq)r,20,合式公式的层次,定义2.7 (1) 单个命题变项或命题常项是0层公式 (2) 称A是n+1(n0)层公式是指下面情况之一： (a) A=B, B是n层公式 (b) A=BC, 其中B,C分别为i层和j层公式, 且 n=max(i, j) (c) A=BC, 其中B,C的层次及n同(b) (d) A=BC, 其中B,C的层次及n同(b) (e) A=BC, 其中B,C的层次及n同(b) 例如 p 0层 p 1层 pq 2层 (pq)r 3层 (pq) r)(rs) 4层,21,公式的赋值,定义2.8 设p1, p2, , pn是出现在公式A中全部的命题变项, 给 p1, p2, , pn指定一组真值, 称为对A的一个赋值或解释. 使公式为真的赋值称作成真赋值, 使公式为假的赋值称作 成假赋值 说明: (1) 赋值记作=12n, i=0或1, 诸i之间不加标 点符号 (2) 通常赋值与命题变项之间按下标或字母顺序对应, 即 当A的全部命题变项为p1, p2, , pn时, 给A赋值12n 是指p1=1,p2=2,pn=n; 当A的全部命题变项为p,q,r, 时, 给A赋值123是指p=1, q=2, r=3, ,22,实例,例6 公式A= p1 p2 01是成真赋值, 00是成假赋值 公式B=( p1 p2 p3 )(p1 p2) 000是成真赋值, 001是成假赋值 公式C= (pq)r 000是成假赋值, 001是成真赋值,23,真值表,例7 给出公式的真值表 (1) (qp) qp,真值表: 命题公式在所有可能的赋值下的取值的列表 含n个变项的公式有2n个赋值,24,实例(续),(2) (pq) q,25,实例(续),(3) (pq) r,26,命题公式的分类,重言式(永真式): 无成假赋值的命题公式 矛盾式(永假式): 无成真赋值的命题公式 可满足式: 非矛盾式的命题公式 注意: 重言式是可满足式，但反之不真. 例如 上例中 (1) (qp)qp为重言式 (2) (pq)q为矛盾式 (3) (pq)r为非重言式的可满足式,
展开阅读全文