离散数学及其应用-屈婉玲 (6)

其内容较广，主要包括数理逻辑、 集合 论、图论、代数结构等四个基本部分。
7
什么是离散数学？
离散数学将日常的概念、判断、 推理用数学符号来表示，用数学方法 进行思维。其目标是掌握严密的思维 方法、严格证明的推理能力和演算能 力，掌握处理各种具有离散结构的事 物的描述工具与方法，适应学习其他 专业课程的各种需要，为学习其它计 算机课程提供必要的数学工具。
设P，Q是两命题，其条件命题是一个复合命题，记做P→Q， 读做“如果P，则Q”。
P 1
真值关系：
Q 1 0 1
PQ 1 0 1
“善意的推定”
1 0
0
0
1
28
1-2 联结词（续）
5、双条件
设P，Q是两命题，其双条件命题是一个复合命题， 记做P↔Q，读做“如果P，则Q”。
P 1 真值关系： 1 0 0


命题：能够判断真假的陈述语句。
例：‘中国是一个国家’， ‘9为素数’。
原子命题：不能分解成更简单的陈述语 句的命题。 复合命题：由连结词、标点符号和原子 命题复合构成的命题。

一般用字母“T”表示“真”，“F”表示 “假”。也经常用“1”表示“真”，“0” 表示“假”。
13
1-1 命题及其表示法（续）
T
F
F
T
F
T
F
T
F
F
T
T
F
命题的形式化描述：(P↔Q)。
35
1-3 命题公式及翻译（续）
例题3： （自学）
例题4： （自学）
例题5： （自学） 例题6： （自学）
36
习题：

* 各章节后习题中的双号大题中的双 号小题。

组合数学在计算机中的应用摘要：组合数学是计算机科学的核心基础理论课，为后续课程提供必须的理论基础。

本文分析了组合数学在计算机学科中与其他课程之间的关系，阐述了组合数学在计算机领域的实际应用。

关键词：组合数学；计算机；应用组合数学是计算机学科的专业基础课，不但为后续课程提供必须的理论基础，而且可以培养学生的抽象思维能力和解决问题的能力。

组合数学的教学内容与计算机硬件和软件都有着密切的关系，具有鲜明的基础特点，不仅是数据结构、数据库原理、数字逻辑、编译原理、人工智能、信息安全等课程的前续课程，同时以计算机导论和程序设计基础作为组合数学的先导课程[1]。

组合数学是计算机应用的必不可少的工具。

例如数理逻辑在数据模型、计算机语义、人工智能等方面的应用，集合论在数据库技术中的应用，代数系统在信息安全中的密码学方面的应用，图论在信息检索、网络布线、指令系统优化等方面的应用。

1组合数学与其他课程的关系1。

1组合数学与数据结构的关系组合数学与数据结构的关系非常紧密，数据结构课程描述的的对象有四种，分别是线形结构、集合、树形结构和图结构，这些对象都是组合数学研究的内容。

线形结构中的线形表、栈、队列等都是根据数据元素之间关系的不同而建立的对象，组合数学中的关系这一章就是研究有关元素之间的不同关系的内容；数据结构中的集合对象以及集合的各种运算都是组合数学中集合论研究的内容；组合数学中的树和图论的内容为数据结构中的树形结构对象和图结构对象的研究提供了很好的知识基础。

1。

2组合数学与数据库原理的关系目前数据库原理主要研究的数据库类型是关系数据库。

关系数据库中的关系演算和关系模型需要用到组合数学中的谓词逻辑的知识；关系数据库的逻辑结构是由行和列构成的二维表，表之间的连接操作需要用到组合数学中的笛卡儿积的知识，表数据的查询、插入、删除和修改等操作都需要用到组合数学中的关系代数理论和数理逻辑中的知识。

1。

3组合数学与数字逻辑的关系数字逻辑为计算机硬件中的电路设计提供了重要理论，而组合数学中的数理逻辑部分为数字逻辑提供了重要的数学基础。

P 0 0 1 1 Q 0 1 0 1 P∧Q 0 0 0 1
例4
设P：我们去看电影。Q：房间里有十张桌子。则
P ∧ Q表示“我们去看电影并且房间里有十张桌子。”
10
3. 析取“∨”（相容或）[讲解教材P3-5关于或]
4. 定义1.3
由命题P和Q利用“∨”组成的复合命题，称 为析取式复合命题，记作“P∨Q”（读作“P或Q”）。 当且仅当P和Q至少有一个取值为真时，P∨Q取值为真。
练习1-1
1. 判断下列语句哪些是命题，若是命题，则指出其真值。
（1） （2） 只有小孩才爱哭。 X+6=Y ( 是 假 ) ( 不是 ) (是 真) ( 不是 )
（3）
银是白的。
（4） 起来吧，我的朋友。 2． 将下列命题符号化
（1） 我看见的既不是小张也不是老李。 解 令P：我看见的是小张；Q：我看见的是老李。 则该命题可表示为¬ P∧¬ Q （2） 如果晚上做完了作业并且没有其它的事，他就会 看电视或听音乐。 解 令 P：他晚上做完了作业；Q：他晚上有其它的事； R：他看电视； S：他听音乐。 则该命题可表示为（P∧¬ Q）→（R∨S）
28
1.3 等值演算
• 定义1.10 设A和B是两个命题公式, 若等价式A↔B 是重言式，则称公式A 和B等值，记为A B,称 AB为等 值式。
• 注意： （1）符号“”与“↔”的区别与联系 “”不是联结词，AB不表示一个公式， 它表示两个公式间的一种关系，即等值关系。 “↔”是联结词，A↔B是一个公式。 AB 当且仅当 A↔B 是永真公式。
1 0 1 0 1 0 1 0
0 0 1 1 1 1 1 1
0 0 0 1 0 0 0 1
1 1 0 1 0 0 0 1

推理定律——重言蕴涵式
1. A (AB)
附加律
2. (AB) A
化简律
3. (AB)A B
假言推理
4. (AB)B A
拒取式
5. (AB)B A
析取三段论
6. (AB)(BC) (AC)
假言三段论
7. (AB)(BC) (AC)
等价三段论
8. (AB)(CD)(AC) (BD)
构造性二难
熟练掌握判断推理是否正确的不同方法（如真值表法、等 值演算法、主析取范式法等）
牢记 P 系统中各条推理规则 熟练掌握构造证明的直接证明法、附加前提证明法和归谬
法 会解决实际中的简单推理问题
练习1：判断推理是否正确
1. 判断下面推理是否正确: (1) 前提：pq, q 结论：p
解 推理的形式结构: (pq)qp 方法一：等值演算法
练习2解答
(3) 证明： ① p(qr) ②p ③ qr ④ sq ⑤s ⑥ q ⑦r ⑧ rt
前提引入 前提引入 ①②假言推理 前提引入 前提引入 ④⑤假言推理 ③⑥析取三段论 ⑦附加
谢谢大家！
定理3.1 由命题公式A1, A2, …, Ak 推B的推理正确当且仅当 A1A2…AkB为重言式
注意: 推理正确不能保证结论一定正确
推理的形式结构
由{A1, A2, …, Ak}推B的推理有以下的形式结构： 1. {A1, A2, …, Ak} B
若推理正确, 记为{A1,A2,,An} B 2. A1A2…AkB
练习2：构造证明
2. 在系统P中构造下面推理的证明： 如果今天是周六，我们就到颐和园或圆明园玩. 如果颐和 园游人太多，就不去颐和园. 今天是周六，并且颐和园游 人太多. 所以, 我们去圆明园或动物园玩.