离散第1章 命题逻辑基本概念.ppt

数理逻辑主要内容 命题逻辑基本概念 命题逻辑等值演算 命题逻辑推理理论 一阶逻辑基本概念 一阶逻辑等值演算与推理;第一章 命题逻辑的基本概念;命题与真值 命题：判断结果惟一的陈述句 命题的真值：判断的结果 真值的取值：真与假 真命题与假命题 注意： 感叹句、祈使句、疑问句都不是命题 陈述句中的悖论，判断结果不惟一确定的不是命题;例1 下列句子中那些是命题？ (1) 是有理数. (2) 2 + 5 = 7. (3) x + 5 3. (4) 你去教室吗？ (5) 这个苹果真大呀！ (6) 请不要讲话！ (7) 2050年元旦下大雪. ;;否定、合取、析取联结词;例2 将下列命题符号化. (1) 吴颖既用功又聪明. (2) 吴颖不仅用功而且聪明. (3) 吴颖虽然聪明，但不用功. (4) 张辉与王丽都是三好生. (5) 张辉与王丽是同学.;解 令p:吴颖用功, q:吴颖聪明 (1) p?q (2) p?q (3) ?p?q (4) 设p:张辉是三好生, q:王丽是三好生 p?q (5) p:张辉与王丽是同学 (1)—(3) 说明描述合取式的灵活性与多样性 (4)—(5) 要求分清 “与” 所联结的成分;例3 将下列命题符号化 (1) 2 或 4 是素数. (2) 2 或 3 是素数. (3) 4 或 6 是素数. (4) 小元元只能拿一个苹果或一个梨. (5) 王小红生于 1975 年或 1976 年.;解 (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)则不能;定义1.4 设p, q为两个命题，复合命题“如果p, 则q”称作p与q的蕴涵式，记作p?q，并称p是蕴涵式的前件，q为蕴涵式的后件，?称作蕴涵联结词. 规定：p?q为假当且仅当p为真q为假.;例4 设 p：天冷，q：小王穿羽绒服，将下列命题符号化 (1) 只要天冷，小王就穿羽绒服. (2) 因为天冷，所以小王穿羽绒服. (3) 若小王不穿羽绒服，则天不冷. (4) 只有天冷，小王才穿羽绒服. (5) 除非天冷，小王才穿羽绒服. (6) 除非小王穿羽绒服，否则天不冷. (7) 如果天不冷，则小王不穿羽绒服. (8) 小王穿羽绒服仅当天冷的时候.;定义1.5 设 p, q为两个命题，复合命题“p当且仅当q”称作p与q的等价式，记作p?q，?称作等价联结词. 规定p?q为真当且仅当p与q同时为真或同时为假. p?q 的逻辑关系：p与q互为充分必要条件;本小节中p, q, r, … 均表示命题.;1.2 命题公式及其赋值;命题变项与合式公式;合式公式的层次;定义1.8 设p1, p2, … , pn是出现在公式A中的全部命题变项, 给p1, p2, … , pn各指定一个真值, 称为对A的一个赋值或解释. 若使A为1, 则称这组值为A的成真赋值; 若使A为0, 则称这组 值为A的成假赋值. 几点说明： A中仅出现 p1, p2, … , pn，给A赋值?=?1?2…?n是指 p1=?1, p2=?2, …, pn=?n, ?i=0或1, ?i之间不加标点符号 A中仅出现 p, q, r, …, 给A赋值?1?2?3…是指 p=?1, q=?2 , r=?3 … 含n个命题变项的公式有2n个赋值. 如 000, 010, 101, 110是?(p?q)?r的成真赋值 001, 011, 100, 111是成假赋值.;定义1.9 将命题公式A在所有赋值下取值的情况列成表, 称作 A的真值表. 构造真值表的步骤: (1) 找出公式中所含的全部命题变项p1, p2, … , pn(若无下角标 则按字母顺序排列), 列出2n个全部赋值, 从00?0开始, 按 二进制加法, 每次加1, 直至11?1为止. (2) 按从低到高的顺序写出公式的各个层次. (3) 对每个赋值依次计算各层次的真值, 直到最后计算出公式 的真值为止.;例6 写出下列公式的真值表, 并求它们的成真赋值和成假 赋值: (1) (p?q) ??r (2)