(北大)数理逻辑.ppt

离散数学 数理逻辑部分 命题逻辑 第1章 命题逻辑 1.1 命题符号化及联结词 1.2 命题公式及分类 1.3 等值演算 1.4 对偶与范式 1.5 推理理论 1.1 命题符号化及联结词 命题与真值 原子命题 复合命题 命题常项 命题变项 联结词 命题与真值 命题: 能判断真假的陈述句 命题的真值: 判断的结果 真值的取值: 真与假 真命题: 真值为真的命题 假命题: 真值为假的命题 注意: 1.感叹句、祈使句、疑问句都不是命题； 2.陈述句中的悖论不是命题； 3.判断结果不惟一确定的不是命题 例：下列句子中哪些是命题？ (1) 是无理数. (2) 2 + 5 ＝8. (3) x + 5 ＞ 3. (4) 你有铅笔吗？ (5) 这只兔子跑得真快呀！ (6) 请不要讲话！ (7) 我正在说谎话. 命题的分类 1.简单命题(原子命题) 简单构成的命题 (不能分解成更简单的陈述句) 简单命题的真值是确定的，又称为命题常项或命题常元 2.复合命题 由简单命题与联结词按一定规则复合而成的命题 3.命题变项（命题变元） 真值不确定的陈述句，如:x+35 注意：命题变元不是命题！ 简单命题符号化 联结词与复合命题 1.否定式与否定联结词“?” 定义 设p为命题，复合命题 “非p”（或 “p的否定”）称 为p的否定式，记作?p，符号?称作否定联结词 ?p 为真当且仅当p为假 2.合取式与合取联结词“∧” 定义 设p,q为二命题,复合命题“p并且q”(或“p与q”)称 为p与q的合取式，记作p∧q，∧称作合取联结词，并规 定 p∧q为真当且仅当p与q同时为真 注意：描述合取式的灵活性与多样性 分清简单命题与复合命题 例 将下列命题符号化. (1) 王晓既用功又聪明. (2) 王晓不仅聪明，而且用功. (3) 王晓虽然聪明，但不用功. (4) 张辉与王丽都是三好生. (5) 张辉与王丽是同学. 解: 令 p：王晓用功，q：王晓聪明，则 (1) p∧q (2) p∧q (3) q ∧? p. 例 (续) 令 r : 张辉是三好学生，s :王丽是三好学生 (4) r∧s. (5) 令 t : 张辉与王丽是同学，t 是简单命题 . 联结词与复合命题(续) 定义 设 p,q为二命题，复合命题“p或q”称作p与q 的析取式，记作p∨q，∨称作析取联结词，并规 定p∨q为假当且仅当p与q同时为假. 例 （6）选小王或小李中的一人当班长. 解 令 t :小王当班长，u:小李当班长 则 (6) 符号化为 (t∧?u) ∨(?t∧u). 例 （7）小王现在在宿舍或图书馆里. 令v :小王在宿舍,w:小王在图书馆 则 (7) 符号化为 v∨w 联结词与复合命题(续) 定义 设 p,q为二命题，复合命题 “如果p,则q” 称作p与q的蕴涵式，记作p?q，并称p是蕴涵式的前件，q为蕴涵式的后件. ?称作蕴涵联结词，并规定，p?q为假当且仅当 p 为真 q 为假. 注意：1. p与q不一定有内在联系 2. 前件p为假时， p?q为真 联结词与复合命题(续) p?q 的逻辑关系： p为 q 的充分条件，q 为 p 的必要条件 “如果 p，则 q ” 的不同表述法很多： 若 p，就 q 只要 p，就 q p 仅当 q 只有 q 才 p 除非 q, 才 p 或 除非 q, 否则非 p， 常出现的错误：不分充分与必要条件 例 设 p:天冷，q:小王穿羽绒服， 将下列命题符号化 (1) 只要天冷，小王就穿羽绒服. (2) 因为天冷，所以小王穿羽绒服. (3) 若小王不穿羽绒服，则天不冷. (4) 只有天冷，小王才穿羽绒服. (5) 除非天冷，小王才穿羽绒服. (6) 除非小王穿羽绒服，否则天不冷. (7) 如果天不冷，则小王不穿羽绒服. (8) 小王穿羽绒服仅当天冷的时候. 联结词与复合命题(续) 定义 设p，q为二命题，复合命题 “p当且仅当q”称作p与q的等价式，记作p?q，?称作等价联结词.并p?q规为真当且仅当p与q同时