离散数学-命题逻辑-1-左孝凌.pdf

离散数学 一 大连理工大学电信学部计算机学院 内容 数理逻辑 命题逻辑 谓词逻辑 集合论 集合 关系 函数 代数系统 图论 说明 学时 32 教材 左孝凌 李为鑑 刘永才 离散数学 上海科学 技术文献出版社 作业 两周交一次作业 考试 100 范围 80 书上 60 课堂内容 成绩 平时成绩 考试成绩 加分 课堂表现活跃 作业完成认真 完整 以及 其它体现该课程学习努力的行为 加分上限8分 第一篇 数理逻辑 第1章 命题逻辑 命题及其表示法 联结词 命题公式与翻译 真值表和等价公式 重言式与蕴含式 全功能联结词集 对偶与范式 推理理论 1 1 命题及其表示法 在数理逻辑中把能判断真假的陈述句称为命题 一般 用大写英文字母或大写英文字母带下标表示 命题的概念包含了以下3个要素 只有陈述句才有可能成为命题 而其它的语句 如 感叹句 祈使句 疑问句等都不是命题 一个语句虽是陈述句 但不能判断真假不是命题 虽然要求命题能判断真假 但不要求现在就能确定 真假 将来可以确定真假也可以 命题的真值 一个命题表达的判断结果称为命题的真值 命题的真值有 真 和 假 两种 分别用 True T 1 真 和False F 0 假 来表示 真 值为真的命题称为真命题 真值为假的命题称为 假命题 任何命题的真值是惟一的 判断以下语句是否为命题 若是命题 确定其真值 解 命题 F 命题 待定 不是命题 祈使句 命题 T 命题 F 不是命 题 疑问句 命题 由上下文确定 不是 命题 悖论 上海是个小村庄 存在外星人 禁止吸烟 北京是中国的首都 4是素数或6是素数 今天你吃了吗 11 1 100 我正在说谎 命题常元 命题变元 原子命题 复合命题 表示命题的小写英文字母或带下标的小写英文字母常称为命 题标识符 如果命题标识符表示一个具体 确定的命题 称为命 题常元 命 题常元 如果命题标识符表示任意一个命题 称为命题变元命题变元 命 题变元无确定的真值 命题是能判断真假的陈述句 而命题变元代表任意的命题 其真值是不确定的 因而不是命题 如果一个命题不能再分解成更简单的命题 则称该命题为原 子命题 原 子命题 如果一个命题不是原子命题 称该命题为复合命题复合命题 如果命题变元表示原子命题时 该命题变元称为原子变元 1 2 命题联结词 在自然语言中 可以通过 如果 那么 不但 而且 这样的连词将简单的陈述句联结 成复合语句 同样在命题逻辑当中 也可以通过命题 联结词将原子变元联结起来表示复合命题 常用的逻辑联结词有五种 否定联结词 合取联 结词 析取联结词 条件联结词和双条件联结词 1 否定联结词 定义1 2 1 设P为命题 则P的否定是一个 复合命题 记作 P 读作 非P 或 P的否定 定义为 若P为T 则 P为F 若P为F 则 P的真值为T 表1 2 1 P P FT TF P和 P的关系如表1 2 1所示 叫做联结词 的真值表 联结词 也可以看作逻辑运算 它是一元运算 例 否定下列命题 P 王强是一名大学生 P 王强不是一名大学生 2 合取联结词 定义1 2 2 设P和Q均为命题 则P和Q的 合取是一个复合命题 记作P Q 读 作 P与Q 或 P合取Q 定义为 当 且仅当P和Q均为T时 P Q的才为T 联结词 的真值表如表1 2 2所示 联结词 也可以看成逻辑 运算 它是二元逻辑运算 表1 2 2 PQP Q FFF FTF TFF TTT 例1 P 今天下雨 Q 明天下雨 则P Q 今天下雨并且明天下 雨 或 P Q 今天与明天都下雨 例2 P 我们去看电影 Q 房间里有桌子 则P Q 我们去看电影且房间里有 桌子 3 析取联结词 定义1 2 3 设P和Q均为命题 则 P和Q的析取是一个复合命题 记作P Q 读作 P或Q 或者 P析取Q 定义为 当且仅 当P和Q均为F时 P Q才为F 表1 2 3 PQP Q FFF FTT TFT TTT 联结词 的真值表如表1 2 3所示 联结词 也可以看成逻辑运算 它是二元逻辑运算 析取联结词 与汉语中的 或 相似 但又不相 同 汉语中的或有可兼或与不可兼或 排斥或 的区分 例 在电视上看这场杂技或在剧场里看这场杂 技 不可兼 灯泡有故障或开关有故障 可兼 是可兼或 4 条件联结词 定义1 2 4 设P和Q均为命题 其条 件命题是个复合命题 记为 P Q 读作 如果P 那么Q 或 若P 则Q 定义为 当且仅 当P为T Q为F时 P Q才为F P 称为条件命题P Q的前件 Q称 为条件命题P Q的后件 联结词 真值表如表1 4所示 联结词 也可以 看成逻辑运算 它是二元逻辑运算 表1 2 4 PQP Q FFT FTT TFF TTT 条件联结词 例1 如果某动物为哺乳动物 则它必为胎生 例2 如果我得到这本小说 那么我今夜就读完它 例3 如果雪是黑的 那么太阳从西方出来 它们都可以表示为P Q的形式 5 双条件联结词 定义1 2 5 设P和Q均为命题 其 复合命题P Q称为双条件命 题 读作 P双条件Q 或者 P当且仅当Q 定义为 当 且仅当P和Q的真值相同时 P Q为T 表1 2 5 PQP Q FFT FTF TFF TTT 联结词 的真值表如表1 2 5所示 联结词 也可以理解成逻辑运算 它是二元逻辑运算 双条件联结词 双条件联结词表示的是一个充分必要关系 与前面所 述相同 也可以不必顾及其前因后果 而只根据联结 词的定义来确定其真值 例1 两个三角形全等 当且仅当它们的三组对应边相等 例2 燕子飞回南方 春天来了 例3 2 2 4当且仅当雪是白的 它们都可以表示为P Q 1 3 命题公式与翻译 把命题常量 命题变量按照一定的逻辑顺序用命题联结词连接起来 就构成了命题演算的合式公式 也叫命题公式 当使用联结词集 时 合式公式定义如下 定义1 3 1 按下列规则构成的符号串称为命题演算的合式公式 也称为 命题公式 简称公式 单个命题变元和常元是合式公式 如果A是合式公式 那么 A是合式公式 如果A和B是合式公式 那么 A B A B A B 和 A B 是合 式公式 当且仅当有限次地应用了 所得到的符号串是合式公式 说明 命题公式一般的用大写的英文字母A B C 表示 依照这个定义 下列符号串是合式公式 p q p q p p q p q q r s t 下列符号串不是合式公式 p q q p q p q q 定义1 3 1给出合式公式定义的方法称为归纳定义 它包括三部分 基础 归纳和界限 定义1 3 1中的 是基础 和 是归纳 是 界限 下文中还将多次出现这种形式的定义 一般地说 命题公式中包含命题变元 因而无法计算其真值 所以不 是命题 命题公式中的命题变元 也叫命题公式的分量 优先级 为方便起见 对命题公式约定如下 最外层括号可以省略 规定联结词的优先级由高到低依次为 按此优先级别 如果去掉括号 不改变原 公式运算次序 也可以省掉这些括号 符号化 翻译 例1 他或者骑自行车去学校 或者乘公共汽车去学 校 解 令P 他骑自行车去学校 Q 他乘公共汽车去学校 此命题中的或是不可兼或 所以不能符号化为 P Q 而要符号化为 P Q 或 P Q P Q 符号化 翻译 例2 符号化下列命题 只要天下雨 我就回家 只有天下雨 我才回家 除非天下雨 否则我不回家 仅当天下雨 我才回家 设P 天下雨 Q 我回家 则 符号化为P Q 均符号化为 Q P 或等价形式 P Q 符号化 翻译 练习 自然语言形式化举例 如果天不下雨并且不刮风 我就去书店 小王边走边唱 除非a能被2整除 否则a不能被4整除 此时 小纲要么在学习 要么在玩游戏 如果天不下雨 我们去打篮球 除非班上有 会 练习解答练习解答 设P 今天天下雨 Q 今天天刮风 R 我去书店 则原命 题符号化为 P Q R 设P 小王走路 Q 小王唱歌 则原命题符号化为 P Q 设P a能被2整除 Q a能被4整除 则原命题符号化 为 P Q 或者Q P 设P 小刚在学习 Q 小刚在玩游戏 则原命题符号化 为 P Q P Q 或 P Q P Q 设P 今天天下雨 Q 我们去打篮球 R 今天班上有 会 则原命题符号化为 R P Q