[理学]ch01命题逻辑.ppt

计算机科学与技术系 离散数学 数学与计算机科学学院 王 一 蕾 yilei@fzu.edu.cn 第一部分 数理逻辑 从广义上讲，数理逻辑包括四论、两演算——即集合论、模型论、递归论、证明论和命题演算、谓词演算，但现在提到数理逻辑，一般是指命题演算和谓词演算。 本篇我们只从语义出发，对数理逻辑中的命题演算与谓词演算等作一简单的、直接的、非形式化的介绍，将不涉及任何公理系统。 第一章 命题逻辑基本概念 本章说明 第一章 命题逻辑基本概念 1.1 命题与联结词 基本概念 命题：能够判断真假的陈述句。 命题的真值：命题的判断结果。真值只取两个值： 真、假。 真命题：真值为真的命题。 假命题：真值为假的命题。 判断命题的两个步骤： 1、是否为陈述句； 2、是否有确定的、唯一的真值。 第一章 命题逻辑基本概念 例：判断下列句子是否为命题。 1、100是自然数。 2、太阳从西方升起。 3、How do you do ? 4、今年国庆节下小雨。 5、x+39 6、我正在说谎。 7、请不要说谎！ 8、如果周末不下雨，那么我们将去郊游。 9、这朵花真美丽啊！ 第一章 命题逻辑基本概念 命题及其真值的抽象化 在本书中，用小写英文字母p,q,r,…p1,p2,p3…等表示命题，用“1”、“0”分别表示真值的真、假。 如是： p：罗纳尔多是球星。 q：5是负数。 p3：明天天气晴。 皆为符号化的命题，其真值依次为1、0、1或0。 第一章 命题逻辑基本概念 命题的分类 简单/原子命题：由不能再分解为更简单的陈述句的陈述句构成。 如上例中的命题（除8外） 复合命题：由简单命题通过联结词联结而成的陈述句。 如上例中的命题8，参见课本例1.2 第一章 命题逻辑基本概念 常用联结词 定义1.1 设p为命题，复合命题“非p”（或“p的否定”）称为p的否定式，记作? p，符号?称为否定联结词。 运算规则：属于单目运算符 真值列举 第一章 命题逻辑基本概念 定义1.2 设p,q为二命题，复合命题“p并且q”（或“p与q”）称为p与q的合取式，记作p ∧ q，符号∧称为合取联结词。 运算规则：属于双目运算符 真值列举 第一章 命题逻辑基本概念 合取运算特点：只有参与运算的二命题全为真时，运算结果才为真，否则为假。 自然语言中的表示“并且”意思的联结词，如“既…又…”、“不但…而且…”、“虽然…但是…”、“一面…一面…”等都可以符号化为∧ 。 注意：不要见到“与”或“和”就使用联结词∧ ！ 例题参见例1.3 例1.3 将下列命题符号化 吴颖既用功又聪明。 吴颖不仅用功而且聪明。 吴颖虽然聪明，但不用功。 张辉与王丽都是三好学生。 张辉与王丽是同学。 合取举例 p：我们去看电影。q：房间里有十张桌子。 p∧q：我们去看电影并且房间里有十张桌子。 第一章 命题逻辑基本概念 定义1.3 设p,q为二命题，复合命题“p或q” 称为p与q的析取式，记作p ∨ q，符号∨称为析取联结词。 运算规则：属于双目运算符 真值列举 第一章 命题逻辑基本概念 析取运算特点：只有参与运算的二命题全为假时，运算结果才为假，否则为真。 这里的析取运算只能表示自然语言中的“相容或”的意思，不能表示自然语言里的“排斥或” 。例如： （1）小王爱打球或爱跑步。 设p：小王爱打球。 q：小王爱跑步。 则上述命题可符号化为：p ∨ q （2）火车8：00或9：00到站。 设p：火车8：00到站。 q：火车9：00到站。 则上述命题就不可简单符号化为：p ∨ q 而应描述为(p∧? q) ∨(? p∧q) 第一章 命题逻辑基本概念 定义1.4 设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”等。 与自然语言的不同：前件与后件可以没有任何内在联系！ 例题参见例1.5 例1.5 将下列命题符号化，并指出其真值 如果3+3＝6，则雪是白的。 如果3+3≠6，则雪是白的。 如果3+3＝6，则雪不是白的。 如果3+3≠6，则雪不是白的。 例1.5 将下列命题符号化，并指出其