于是，当时多个国家几乎同时出现了关 于继电器接点线路结构的符号方法及数理逻 辑的命题演算在其中的应用。
1943年，数理逻辑又应用于所有开关线 路的理论中。以后，又在计算机科学和控制 论方面获得应用，成为基础理论之一。
12
数理逻辑在计算机科学技术中的应用
数理逻辑是计算理论的基础，而计算理 论又是计算机科学的核心基础，在编译原理、 复杂性分析中有广泛的应用；
10
1879年，《概念语言》，建立 第一个比较严格的逻辑演算系统。
《数学原理》，当时数理逻辑 的成果总结，使得数理逻辑形成了 专门的学科。
11
1930年以前，数理逻辑的发展主要是针 对纯数学的。从20世纪40年代起，自动化和 计算技术的发展要求建立包含数百个甚至数 千个继电器的复杂系统，人们难以进行分析 和综合。
序号
句子
是否为命题 原因
(8) 明年10月1日是晴天.
√
真值唯一
(9) 地球外的星球上有人.
√
真值唯一
(10) 11＋1＝100.
×
真值不确定
（8）、（9）的真值虽然现在还不知道，但它的真 值是唯一的，因而是命题。 （10）在二进制中为真，在十进制中为假，需根据 上下文才能确定其真值，因而不是命题。
5
《离散数学》是现代数学的一个重要分支， 是构筑于数学和计算机学科之间的桥梁，是计 算机科学的理论基础。
作为核心基础课程，该课程在计算机及相 关专业课程体系中扮演着重要的角色，是构筑 于数学和计算机学科之间的桥梁，。
它以研究离散量的结构及相互关系为主要 目标，充分描述了计算机科学离散性的特点。
6
与后续课程的关系
例 判断下列句子是否为命题：
序号
句子
是否为命题 原因
(1)
2 是无理数.
√
真命题
(2)
2 + 5 ＝8.
√
假命题
(3)
x + 5 ＞ 3.
×
真值不确定
பைடு நூலகம்(4)
你有铅笔吗？
×
疑问句
(5) 这只兔子跑得真快呀！ ×
感叹句
(6)
请不要讲话！
×
祈使句
(7)
我正在说谎话.
×
悖论
（7）这种由真能推出假、又由假能推出真，从而既 不能为真、也不能为假的陈述句称为悖论。悖论不 是命题。
“计算思维” 图1 自动计算、形式化与“计算思维”的关系
4
中学数学
数学分析
离散数学
形式语言与 自动机理论
具体、静止
变量、运动
离散、抽象
形式、模型
（基本运算系统） （计算系统）
运算范围
实数
抽象集合
特征
孤立、单一的计算 （实例计算）
一般、形式化的计算 （类计算、模型计算）
图2 “计算思维”梯度训练系统
另外，数理逻辑也是形式语言、程序设 计方法、机器证明、人工智能等学科的基础。
下面将介绍一些数理逻辑的典型应用， 供参考。
13
命题逻辑的知识在日常生活和工程技术 中都有着广泛的应用。电子计算机是数理逻 辑和电子学相结合的产物。实际上，无论是 作为计算机雏形的图灵机，还是作为程序设 计的语言等，无不涉及它的知识和理论。
离散数学
计算机1501-04 赵曦
教材
《离散数学》 屈婉玲、耿素云、张立昂， 高等教育出版社， 2015年3月第二版
2
学科地位
计算机相关专业，需具备的专业能力： • 计算思维能力； • 算法设计与分析能力； • 程序设计与实现能力； • 计算机系统的认知、分析、开发和应用能
力，简称系统能力。
3
被有效地自动计算 形式化
• 数理逻辑——在人工智能、程序理论和数据 库理论等的研究中有重要的应用。
• 集合论、图论——为数据结构和算法分析奠 定了数学基础，也为许多问题从算法角度如 何加以解决提供了继续抽象和描述的一些重 要方法。
• 代数结构——代数结构中的代数方法被广泛 应用，如可计算性与计算复杂性、形式语言 与自动机、密码学、网络与通信理论、程序 理论和形式语义学等计算机分支学科。
7
第一部分 数理逻辑
数理逻辑 用数学方法研究推理的一门科学。
命题逻辑
第一章 命题逻辑的基本概念 第二章 命题逻辑等值演算 第三章 命题逻辑的推理理论
一阶逻辑
第四章 一阶逻辑基本概念 第五章 一阶逻辑等值演算与推理
要想把这种推理规则应用到各个学科领 域中去，就必须使用一种概括性较强，并且 又是独立于任何特定的论证或者所涉及的学 科的语言。
14
命题逻辑的知识逻辑结构
3.2 3.1
2.2
2.1
1.2 1.1
15
第一章 命题逻辑的基本概念
§1.1 命题与联结词 §1.2 命题公式及其赋值
16
§1.1 命题与联结词
一、命题与真值 二、命题的分类 三、命题与真值的符号化 四、常用联结词及其符号 五、基本复合命题 六、复合命题
返回
17
一、命题与真值
1. 命题
判断结果惟一的陈述句。
2. 命题的真值 判断的结果。
3. 真命题
真值为真的命题。
4. 假命题
真值为假的命题。
18
命题的注意事项
• 非假即真的陈述句。 • 一切没有判断内容，不分真假的句子，都不是命题。 • 陈述句能否分辨真假，和是否知道它的真假，是两回事。 • 命题不能是疑问句或是祈使句等其他类型的句子。 •一个命题的真值只能是真或是假，不能兼而有之。
这种语言是一种符号化的形式语言，它 没有二义性。
第一至五章将介绍这套符号化形式体系 的制定，以及它在数理逻辑中的应用。
数理逻辑的发展
在17世纪，曾经设想创造一种 “通用的科学语言”，能够像数学 一样利用公式对推理过程进行计算， 但没有实现。是数理逻辑的先驱。
1847年，《逻辑的数学分析》， 建立了“布尔代数”，并创造了一 套符号系统，初步奠定了数理逻辑 的基础。
q：2 + 5 = 7，则 q 的真值为 1。
注意：书P4 例1.2
返回
23
四、常用联结词及其符号
1. 否定（定义1.1） 规定 p为真当且仅当p为假.
2. 合取∧（定义1.2） 规定 p∧q为真当且仅当p与q
同时为真.
3.
析取∨（定义1.3）
规定p∨q为假当且仅当p与q同时 为假.
4. 蕴涵→（定义1.4）规定pq为假当且仅当 p 为真 q 为假.
返回
21
二、命题的分类
1. 简单命题（原子命题） 不能被分解成更简单命题。
简单命题是最小的基本单位。 2. 复合命题
由简单命题通过联接词联接而成。
返回
22
三、命题与真值的符号化
1. 命题的符号化
用p、q、r等表示命题。
2. 真值的符号化
用数字1代表真，0代表假。
例如，令
p：2是有理数，则 p 的真值为 0。