2007 年 6 月 楚雄师范学院计科系 离 散 数 学 第三章 逻辑代数 ( 上 ) 命题演算

2007 年 6 月 楚雄师范学院计科系 §3.1 逻辑学的概念 §3.2 命题和逻辑联结词 §3.3 命题符号化 §3.4 命题公式 §3.6 对偶与范式 §3.5 逻辑等价式和逻辑蕴涵式 章节介绍： 教学时数： 12 节 § 3.7 推理理论

2007 年 6 月 楚雄师范学院计科系 §3.1 逻辑学的概念 逻辑学是一门研究思维形式及思维规律的科学 例 : 如果今天是周一, 则要进行离散数学 或 C 语言程序设计两门课中的一门的考试。 如果 C 语言设计老师有会，则不考 C 语言 程序设计。 今天是周一。 C 语言程序设计老师又有会。 结论：今天要进行离散数学考试。

2007 年 6 月 楚雄师范学院计科系 由于研究对象和方法的侧重点不同而分为 形式逻辑、 辨证逻辑。 数理逻辑是用数学方法研究推理，是研究推 理中前提和结论之间的形式的科学，所谓推理就 是由一个或多个判断推出一个新 判断 的思维形式， 所谓数学方法就是要建立通用的符号语言和通用 的代数思想，在通用符号中实现语句的符号化， 推理过程表现为符号序列的变形，只要对符号体 系能作出明确的规定，就可以按照这些规定机械 地推理。

2007 年 6 月 楚雄师范学院计科系 §3. ２ 命题和逻辑联结词 定义 1 命题是指具有真假态的陈述句，具真 或具假二者必居其一，具真用 1 或 表示，具假 用 0 或 表示。 例 1 (1) 今天是五一国际劳动节。 (2) 飞碟是从外星来的。 (3) 太阳从西边升起。 (4) １＋ 101=110 。 (5) 全体立正！ (6) 他去北京吗 ? §3. ２.1 命题

2007 年 6 月 楚雄师范学院计科系 注１ : 命题的真值是客观存在且唯一的, 与我们的 感觉或是否知道是真是假无关。

2007 年 6 月 楚雄师范学院计科系 注２：命题的真值通常与 命题 论及的范围、 时间和空间有关。 注 3 ：（ 9 ）、（ 1 ２）是矛盾句，不 是命题。 注 4 ：一个陈述句不具有真假态，就不是命题。 如例 1 （ 12 ）、 （９） 定义 2 除其本身外，它的任何局部不是命题， 这样的命题称为原子命题。 例 2 ：雪是白的。 定义 3 把原子命题和逻辑联结词共同组成的命 题称为复合命题。

2007 年 6 月 楚雄师范学院计科系 原子命题通常用 等大写字母 表示 ． 原子命题符号化步骤是：用大写字母 可表示具体原子命题，此时它们称为命题常量。 大写字母 还可表示一个待定的命题， 此时称它们为命题变量 。

2007 年 6 月 楚雄师范学院计科系 §3.2.2 逻辑联结词 真值表

2007 年 6 月 楚雄师范学院计科系 真值表

2007 年 6 月 楚雄师范学院计科系 注１：逻辑学的形式语言与论述的具体内容和我们的 自身感受无关，上例完全符合逻辑学上的语法规则。 注２： “ 与 ” 、 “ 和 ” 有时不是我们定义的合取联结词。 ：小张与小王是同学。 不是合取联结词 ：小张与小王都是三好生。 是合取联结词 小张是三好生且小王是三好生。

2007 年 6 月 楚雄师范学院计科系 真值表

2007 年 6 月 楚雄师范学院计科系 注 1 ：命题逻辑中联结词 “ 或 ” 与自然语言中的 “ 或 ” 有 较大区别，命题联结词中的 “ 或 ” 是 “ 可兼或 ” 。 例：今天食堂供应米饭或馒头。 注 2 ：自然语言中的 “ 或 ” 还有 “ 不可兼或 ” 的意义。 真值表

2007 年 6 月 楚雄师范学院计科系 注 3: 自然语言中有些 “ 或 ” 并不是联结词。 例：电影院里大约有 400 或 500 名观众。 真值表

2007 年 6 月 楚雄师范学院计科系 注 1: 自然语言中, 往往有因果关系，但在数理 逻辑中 不一定有因果关系。 是前件， 为后件。 注 2 ：一定要分析句子中那部分是前件，那部分是后件。

2007 年 6 月 楚雄师范学院计科系 例 1 ：你将一事无成，除非你努力。 如果你不努力，那么你将一事无成。 令 ：你努力； ：你将一事无成。 则命题符号化为： 。 例 2 ：只有天不下雨，我才骑自行车上班。 如果我骑自行车上班，那么天不下雨。 令 ：天下雨； ：我骑自行车上班。 则命题符号化为： 。

2007 年 6 月 楚雄师范学院计科系 真值表

2007 年 6 月 楚雄师范学院计科系 §3.3 命题符号化 1. 原子命题符号化 一般用大写字母符号化。如 。习惯将这些符号放在命题前面。 2. 复合命题符号化，要正确的表示出原子命题和选择 恰当逻辑联结词。 例：对下列命题符号化： （ 1 ）我和他既是兄弟又是同学。 （ 2 ）我和你之间至少有个要去海南岛。 （ 3 ）狗急跳墙。 （ 4 ）除非他来，否则我不同他谈判。 如果我与他谈判，那么他来。 （ 5 ）如果他没来见你，那么他或者生病了， 或者他不在本地。

2007 年 6 月 楚雄师范学院计科系 §3.4 命题公式... 等可表示一个具体命题，此 时... 为命题常元。.. 等也可表示某一待定的命题，此时 为命题变元，命题变元不是命题。 可用 表示两个特殊的命题：永假命题 和永真命题。 联结词、命题常元、命题变元及圆括号经过适 当连接，得到字符串称为命题公式或合式公式， 命题公式用..... 等表示。

2007 年 6 月 楚雄师范学院计科系

2007 年 6 月 楚雄师范学院计科系 定义 2 公式 称为公式 的子式，如果 是公式 中 字母相互毗连的一部分，且 自身为一公式。

2007 年 6 月 楚雄师范学院计科系 定义 4 真值表

2007 年 6 月 楚雄师范学院计科系 §3.5 逻辑等价式和逻辑蕴涵式 定义 5 公式 称为重言式（又称永真式） 公式 称为矛盾式（永假式） 公式 称为可满足式

2007 年 6 月 楚雄师范学院计科系

2007 年 6 月 楚雄师范学院计科系

2007 年 6 月 楚雄师范学院计科系

2007 年 6 月 楚雄师范学院计科系

2007 年 6 月 楚雄师范学院计科系

2007 年 6 月 楚雄师范学院计科系

2007 年 6 月 楚雄师范学院计科系

2007 年 6 月 楚雄师范学院计科系 Th3( 代入原理 ) 为永真式, 为 中变元, 将 中 的出现处全部用公式 代换后的命题公式 ( 称为 的一 个代入实例 ) 仍为一永真式。 注：可用于证明一个公式是永真式，证明等价蕴涵中很有用

2007 年 6 月 楚雄师范学院计科系

2007 年 6 月 楚雄师范学院计科系

2007 年 6 月 楚雄师范学院计科系 §3.6 对偶与范式 §3.5.1 对偶 例： 写出下列公式对偶式

2007 年 6 月 楚雄师范学院计科系

2007 年 6 月 楚雄师范学院计科系 §3.5.2 主范式

2007 年 6 月 楚雄师范学院计科系 §3.5.2 主范式

2007 年 6 月 楚雄师范学院计科系

2007 年 6 月 楚雄师范学院计科系 §3.5.2 主范式

2007 年 6 月 楚雄师范学院计科系 Th1 任何公式都有与之等价的析取范式和合取范式。 但析取范式和合取范式不唯一。 求一个命题的合取范式和析取范式步骤如下：

2007 年 6 月 楚雄师范学院计科系