离散数学课件：第2章

解法1 这只大红书柜摆满了那些古书。 解法2 x y 设 A(x)：x是书柜 设 F(x,y)：x摆满了y
解法1中R(x)表示x是大红书柜, 解法2中A(x) ∧B(x) ∧C(x)也 可表示大红书柜,但用A(x) ∧B(x) ∧C(x)将更方便于对 书柜的大小颜色进行讨论
B(x)：x是大的 D(y)：y是古老的 F(x,y)：x摆满了y
例题1 并非每个实数都是有理数。
设 R(x)：x是实数。 Q（x）：X是有理数。
每个实数都是有理数表示为： (x)( R( x) Q( x))
(x)( R( x) Q( x)) 并非每个实数都是有理数表示为：
例题2 没有不犯错误的人
解 本语句即为“不存在不犯错误的人”。 设 M(x)：x 是人。 F(x)：x犯错误。 “存在不犯错误的人”表示为： “不存在不犯错误的人”表示为：(x(M ( x) F ( x)) 等价于“任何人都要犯错误”或“所有人都要犯错误”。 所以此命题也可符号化为： (x)(M ( x) F ( x))
2.7谓词演算的推理理论
2
2.3谓词公式与翻译
一、谓词公式
• 定义1：n元谓词A(x1，x2...xn) 称为谓词演算的原子公式。 • 定义2：谓词演算的合式公式,可由下述各条组成: ① 原子公式是合式公式。 ② 若A 是合式公式，则(A)也是合式公式。 ③ 若A，B是合式公式，则(A ∧ B)，(A ∨ B)，(A B)， (A B)也是合式公式。 ④ 若A是合式公式，x是A中出现的任何变元 ,则(x)A , (x)A，也是合式公式。 ⑤ 只有有限次应用(1)~(4)得到的公式是合式公式.
练习1
（3）没有不能表示成分数的有理数。
解：令D(x): x是有理数。F(x):x能表示成分数。 则符号化为： (x)(D(x) F(x)) 或 (x)(D(x)∧ F(x)) 真值为１。

第一章 命题演算
设命题公式 A 中含有 n 个命题变元，且 A 的主析取范式中含有 k 个小项 mi1，mi2，…，mik，则 A 的主合取范式必含有 2n-k 个大项。如果命题公 式 A 的主析取范式为∑(i1,i2,…,ik)，则 A 的主合取范式为： ∏(0，1，2，…，i1-1，i1+1，…，ik-1，ik+1，…，2n-1)。 从 A 的主析取范式求其主合取范式步骤为：
本章的学习主要是在掌握命题逻辑的基础上，理解个体，谓词，量 词等概念，学会将命题进一步用谓词逻辑表示；在熟记谓词逻辑中的等 价式和蕴含式的基础上，将一个谓词演算公式化为与它等价的前束范式； 并能运用 US、UG、ES、EG 等规则，进行谓词演算的推理。
本章的重点是带量词的公式变换，即前束范式。难点是谓词演算的
具有确切真值的陈述句称作命题。 所谓真值就是命题为真或为假的性质。
判断一个语句是否为命题，首先要判断它是否是陈述句，然后判断 是否具有唯一的真假值。
在判断一个陈述句是否具有唯一的真假时，要注意：一个陈述句的 真假暂时不能唯一地确定，但总有一天可以唯一确定，与一个陈述句的 真假不能唯一确定是两件事。
第一章 命题演算
第一章 命题演算
等值公式表和蕴含公式表整理归纳如表 1.表 2
第一章 命题演算
（3） 构造论证法
常用的推理规则有：
（1）前提引入规则：在证明的任何步骤上，都可以引入前提，简称 P 规则。
（2）结论引入规则：在证明的任何步骤上，所证明的结论都可作为后续 证明的前提，称为 T 规则。
（3）置换规则：在证明的任何步骤上，命题公式中的任何子命题公式都 可以用与之等值的命题公式置换。亦记为 T 规则。
推理理论。

28.04.2020
引 言（续）
二、该课程的主要内容： 离散数学课程的主要内容可以分为四个部分： 数理逻辑，包括命题逻辑和谓词逻辑。(教材的第一、二章) 集合论，包括集合、关系和函数。（教材的第三、四章） 代数系统，包括代数系统的一般概念，几类典型的代数系
统和格。（教材的第五、六章） 图论，包括图的基本概念，几种特殊的图。 (教材的第七章)
数理逻辑：人工智能，数据库，形式语言及自动机， 高级程序设计语言。
集合论： 信息结构与检索，数据结构。 图论： 可计算性理论，计算机网络,数据结构。 代数结构：开关理论，逻辑设计和程序理论，语法
分析。 2. 通过学习离散数学，可以培养和提高自己的抽象思
维和逻辑推理能力，获得解决实际问题能力，为以 后的软、硬件学习和研究开发工作，打下坚实的数 学基础。
版） (美)Kenneth H.Rosen 著 机械工业出版社
28.04.2020
引 言（续）
七、考核方式： 期末考试成绩占70%, 平时成绩占30%.
28.04.2020
第一部分 数理逻辑（Mathematical Logic)
❖ 逻辑：是研究推理的科学。公元前四世纪由希腊的 哲学家亚里斯多德首创。作为一门独立科学，十七 世纪，德国的莱布尼兹(Leibniz)给逻辑学引进了符 号, 又称为数理逻辑(或符号逻辑)。
➢ 因此，离散数学是随着计算机科学的发 展而逐步建立的，它形成于七十年代初期， 是一门新兴的工具性学科。
28.04.2020
引 言（续）
➢ 离散数学是现代数学的一个重要分支， 是计算机科学与技术的理论基础，是计算机 科学与技术专业的核心、骨干课程。
➢ 它 以研究离散量的结构和相互间的关系 为主要目标，其研究对象一般是有限个或可 数个元素，因此它充分描述了计算机科学离 散性的特点。

A＝B C或A＝B C或A＝B C，则公式A是n＋1层公式， n max( i, j)。
例（1）p q r (2)r q p q p
第23页/共292页
1.2 命题公式及其赋值
( p q) r
p：2是素数，q：3是偶数，r：2是有理数 p：2是素数，q：3是偶数，r：2是无理数
例2.等值等价式p q p q q p
等值演算的应用： 1.验证等值式 ( p q) ( p r) p (q r) 2.判定公式的类型 ( p q) p q,( p ( p q)) r, p ((( p q) p) q) 3.解决工作生活中的判断问题
甲、已、丙3人根据口音对王教授是哪人进行了判断： 甲说：王教授不是苏州人，是上海人 已说：王教授不是上海人，是苏州人 丙说：王教授既不是上海人，也不是杭州人
例：1.如果3＋3＝6，那么雪是白的。 2.除非我能工作完成了，我才去看电影。 3.只要天下雨，我就回家。 4.我回家仅当天下雨。 p→q的逻辑关系为q是p的必要条件或p是q的充分条件。
第15页/共292页
1.1 命题和命题联结词
5).等价词 由命题p、q和 组成的复合命题记作p q,读作“p当且仅当q”。 是自然语言中的“充要条件”，“当且仅当”的逻辑抽象。
1.3 命题公式的等值式
定义1.设A和B是两个命题公式，若A B为重言式， 则称公式A, B是等值的公式，记作A B。
例1.证明（p q) (q p); p p p.
注意： 和 的区别 是公式间的关系符号，如：p q 是命题联结词.p q
第28页/共292页
1.3 命题公式的等值式
1.1 命题和命题联结词
例：1）海洋的面积比陆地的面积大。 例 q2:）： 22p6:6海 9洋 9。 。的面积比陆地的面积大。 r3:）火火星星上上有有生生命命。。 s4:）三三角角形形的的内内角角和和等等于 于118800。 。 55））你你喜 喜欢 欢数学吗吗？？ 66））我我们 们要 要努 努力力学学习习。。 77））啊啊， ，我 我的 的天天哪哪！！ 88））我我正 正在 在说 说谎 谎。。