第1页 / 共10页
第2页 / 共10页
第3页 / 共10页
第4页 / 共10页
第5页 / 共10页
第6页 / 共10页
第7页 / 共10页
第8页 / 共10页
离散数学.pdf
第一编 数理逻辑
第一章 命题逻辑
1.1 命题符号化
否定词┑，合取词∧，析取词∨，蕴含词→，等值词↔
若一个命题是一个简单陈述句，则称之为简单命题；由简单命题通过┑、∧、∨、→、↔这
些联结词组成的命题称为复合命题；P→Q 是条件命题；P↔Q 是双条件命题。
1.2 合式公式
命题常元 T，F
命题变元
P₁，P₂，...P
联结词 ┑∧∨→↔
辅助词 （）
这个字母表可记为∑（P₁，P₂，…）,如不引起混淆，也可简记为∑。∑（P₁，P₂，…）表示
字母表∑（P₁，P₂，…）上的所有字符串，包括空串ɛ；用∑⁺表示∑上的所有非空符号串的
集合。
● 合式公式：（1）命题常元或命题变元是合式公式；（2）若 A，B 是合式公式，则（┑A），
（A∧），（A∨B），（A→B），（A↔B）是合式公式；（3）只有通过有限次使用（1），（2）所
得到的符号串才是合式公式。
代入和替换：替换只要求对该子公式的某一出现或某几个出现进行替换，而不是对每一处出
现都进行替换。
1.3 永真公式
解释：设 是含有 这 n 个命题变元的合式公式，对 的
一组真值赋值，称为对 A 的一个解释，记作 I= ，其中 取 0 或 1，I( )= 。
合式公式可分为：永真式，永假式，可满足式。
逻辑恒等式：
永真蕴含式：
1.4 范式
文字：命题变元或命题变元的否定称为文字，并称命题变元为正文字，命题变元的否定为负
文字。
基本和的归纳定义是：①文字是基本和；②若 A，B 是基本和，则 A∨B 是基本和。
合取范式的归纳定义如下：①基本和是合取范式；②若 A，B 是合取范式，则（A∧B）是合
取范式。
主合取范式的归纳定义是：①极大项是主合取范式；②若 A，B 是主合取范式，则（A∧B）
是主合取范式。
基本积的归纳定义是：①文字是基本积；②若 A，B 是基本积，则 A∧B 是基本积。
析取范式的归纳定义如下：①基本积是析取范式；②若 A，B 是析取范式，则（A∨B）是析
取范式。
主析取范式的归纳定义是：①极小项是主析取范式；②若 A，B 是主析取范式，则（A∨B）
是主析取范式。
▲ 1.5 推理理论
推理规则：⑴附加规则
⑵化简规则
⑶MP 规则
⑷拒取式
⑸析取三段论
⑹假言三段论
⑺合取引入
⑻构造二性难
▲ 证明方法：
⑴前件假证明法
⑵后件真证明法
⑶直接证明法
⑷间接证明法
⑸分情况证明法
⑹附加前提证明法
⑺反证法
▲ 公理系统一般由下列几部分组成：
⑴初始符号：它们是不经定义而直接使用的符号；
⑵形成规则：确定定义在初始符号上的哪些符号串是合式公式；
⑶公理集：它们是不经证明而被认为是恒真的命题；
⑷推理规则：规定如何从公理和前面已经推导出的合式公式经过符号变形而推出其它公式。
命题逻辑的公理系统 L 的定义如下：
⑴初始符号：
⑵形成规则：①P 是合式公式；②若 A 是合式公式，则（┑A）是合式公式；③若 A 和 B 是
合式公式，则（A→B）是合式公式；④只有通过有限次使用①~③得到的符号串是合式公式。
⑶公理集：（L ）（A→（B→A））；（L ）（（A→（B→C））→（（A→B）→（A→C）））；（L ）（（（┑
A）→（┑B））→（B→A））。
⑷推理规则：从 A 和（A→B）可推出 B。
证明：L 中的证明是合式公式的一个有穷序列 A ，A ， …A ,其中 A 或者是公理，或者是
序列中其前的某两个合式公式经 MP 规则得到。并称该证明人是 A 是在 L 中的证明，称 A 是
L 的定理，记作 。
演绎：设 是合式公式集，L 中的从 推出 A 的一个演绎是合式公式的一个有穷序列 A ，
A ，…A ，其中 A 或者是公理，或者是 中的一个合式公式，或者是序列中其前的某两个合
式公式经 MP 规则得到。 中的合式公式称为假设。
L 的演绎定理：
推论：设 A，B，C 是 L 的任意合式公式，则{A→B，B→C} A→C。
1.6 联结词的全功能集
设 C 是联结词的集合，若任何公式均可由仅含 C 中联结词的公式等价的表示，则称 C 是联
结词的全功能集；若从 C 中任意去掉一个联结词，则 C 不是全功能集，则称 C 是联结词的极
小全功能集。
2.1 命题符号化
第二章 一阶逻辑
在一阶逻辑中，我们把所讨论的对象称为个体，用来表示个体的符号称为个体词。若一个个
体词表示一个特定个体，则称之为个体常元；若一个个体词泛指任何一个个体，则称之为个
体变元；个体变元的取值范围称为个体域或论域。
在简单命题中，表示个体的性质或个体之间联系的词称为谓词，表示数量的词称为量词，量
词一般有两种：全称量词∀和存在量词∃
2.2 合式公式
一阶谓词逻辑的字母表∑为
个体常元 a,b,c,…
个体变元 x,y,z,…
函数符号 f,g,h,…(n 元函数 f 可记为 f )
谓词符号 P，Q，R，…
联结词 ┑∧∨→↔
量词
∀ ∃
辅助符号 （）
项的归纳定义如下：⑴个体常元和个体变元是项；⑵若 t ,t ,t ,…是项，则 f (t ,t ,t,…)
是项；⑶只有通过有限次使用（1）和（2）所得到的符号串是项。
设 t ,t ,t ,…t 是项，则称 P (t ,t ,t ,…t )为原子公式。
合式公式的归纳定义如下：⑴原子公式是合式公式；⑵若 A，B 是合式公式，则（┑A），（A
∧），（A∨B），（A→B），（A↔B），∀xA, ∃xA 是合式公式；⑶只有通过有限次使用（1），（2）
所得到的符号串才是合式公式。
在合式公式 QxA 中，称 A 为 Q 的辖域，其中 Q 为∀或∃。变元 x 在 Qx 及 Q 的辖域中的出现称
为 x 的约束出现，并称 x 为约束变元；x 的非约束出现称为 x 的自由出现，并称 x 为自由
变元。
换名规则：若要将约束变元 x 改为 y，则⑴将 Qx 中的 x 及在 Q 的辖域中自由出现的 x 均改
为 y;⑵y 不在限制 x 的量词的辖域中出现。
2.2 永真公式
合式公式 G 的一个 I 是由一个非空集合 D （称为 I 的论域）和如下一组规则组成：
⑴对 G 中的每一个个体常元和自由个体变元指定 D 中的一个元素；
⑵对 G 中的每一个 n 元函数，指定 D 上的一个 n 元函数；
⑶对 G 中的每一个 n 元谓词符号，指定 D 上的一个 n 元谓词。
永真式：
2.4 范式
称下述形式的公式为前束范式：Q x Q x Q x Q …B,其中 Q 为∀或∃，B 是不含任何量词
的公式。并称 Q x Q x Q x Q 为前束词，称 B 为母式。
Skolem 范式
设前束范式为 Q x Q x …Q x …Q x B。若 Q x 为∃x (1≦t≦r),那么⑴当 Q x 左边无全
称量词时，用 B 中未出现的个体常元 a 支代替 B 中 x 的所有出现，并删支出 Q x ；⑵当 Q
x 左边的所有全称量词为 Q x Q x ,…,Q x (1≦ )时，取 B 中未出现的 s 元函数符
号 f ，用 f （x ,x ,…x ）代替 B 中 x 的所有出现，并删支 Q x 。这种消去量词的变换
称为 Skolem 变换。
▲2.5 推理理论
⑴全称指定规则（US 规则）：
⑵存在推广规则（EG 规则）：
⑶存在指定规则（ES 规则）：
⑷全称推广规则（UG 规则）：
第二编 集合论
第三章 集合
3.1 集合的基本概念及其表示法
集合，N，I，Q，R，C
●设 A 是任意集合，|A|表示 A 所含有的元素的个数。
⑴若|A|=0，则称 A 是空集，记作 。
⑵若|A|是自然数，则称 A 是有限集。
⑶若|A|无穷大，则称 A 是无限集。
▲集合的表示法:⑴列举法 按某一次序列出集合的全部或部分元素,并用一对花括号括起；
⑵描述法 用谓词描述出集合元素的公共特征，其形式为 S={x|P(x)}；
⑶归纳定义法 通常包括以下三步：
①基本步 S 非空且 S 中的任意元素均是 A 的元素；
②归纳步 给出一组规则，从 A 的元素出发，依据这些规则所得到的仍是 A 的元素；
③极小化 若 S 的任意元素均是 A 的元素，并且 S 满足①和②，则 S 与 A 有相同的元素。
元素可以多次出现的集合为多重集，无特别说明，集合均指一般集合，不是多重集。
3.2 集合的运算
并：
交：
差：
完全以集合为元素的集合称为集类，常用字母
广义交：
广义并：
补：
表示。
▲
环和：
幂：设 A 是集合，则称{x|x⊆A}为 A 的幂集，A 的幂集即是由 A 的所有子集组成的集合。
环积：
3.3 基本集合恒等式
3.4 容斥原理
3.5 集合的笛卡尔积
● 称={{x},{x,y}}为由 x 和 y 组成的有序二重组，也称为序偶。
● 设 n∈I ,x ,x ,…,x 是 n 个任意的元素。⑴若 n=1,则令=x ;⑵若 n=2,则令
={{x },{x ,x }};⑶若 n>2,则令=<,x >.称
是由 x ,x ,…,x 组成的有序 n 重组，称 x (1≤i≤n)是它的第 i 个分量。
● 设 n∈I ,集合 A ,A ,…,A 的笛卡尔积 A A … A 定义为 A A … A ={|a
∈A ,i=1,2,3…n}.称 n 为该笛卡尔积的维数。若 A =A =…A ,则记 A A A … A 为 A 。
笛卡尔积满足下列分配律：
第四章 二元关系
● 设 n∈I ，A ，A ，…，A 是 n 个集合，R⊆ A ，称 R 是集合 A ，A ，…,A 上的 n 元关
系。若 A =A =…=A =A,则称 R 是 A 上的 n 元关系。当 n=2 时，称 R 是 A 到 A 的二元关
系，A 称为 R 的前域，A 称为 R 的陪域，称 dom(R)={x|x∈A ∧∈R}为 R 的定义域，
称 ran(R)={y|y∈A ∧∈R}为 R 的值域。
若∈R,则说 a 与 b 有关系 R，常用中缀法记为 aRb; 若∈R,则说 a 与 b 没有关系
R，常用中缀法记为 aRb。
由于任意集合均有两个平凡子集，即空集和集合自身，因此称 A A …A 上的关系 为空关
系，称 A A … A 为全域关系。
A 上的关系{|x∈A}称为 A 上的恒等关系，记为 I 。
● 设 R ⊆ A ,R ⊆ A .若⑴n=m;⑵ ;⑶集合 R 和 R 相等，则称关系 R 与 R 相
等，记为 R =R 。
▲关系的表示
⑴集合表示法；⑵关系矩阵表示法；⑶关系图表示法。
4.2 关系的性质
● 设 A 是集合，R⊆A A。⑴若∀x(x∈A→xRx),则称 R 是自反的；⑵若∀x(x∈A→xRx),则
称 R 是反自反的；⑶若∀x∀y(x∈A∧y∈A∧xRy→yRx),则称 R 是对称的；⑷若∀x∀y(x
∈A∧y∈A∧xRy∧yRx→x=y),则称 R 是反对称的；⑸若∀x∀y∀z(x∈A∧y∈A∧z∈A∧
xRy∧yRz→xRz),则称 R 是传递的。
4.3 关系的运算
● 设 A，B 是集合，R⊆A B，且 S⊆A B，则交 R∩S，并 R∪S，差 R-S 和补 R 均是 A 和 B 上
的二元关系，且 x(R∩S)y⇔xRy∧xSy,x(R∪S)⇔xRy∨xSy,x(R-S)⇔xRy∧xSy,xRy⇔
xRy.
● 设 A 和 B 是集合，R⊆A B，令 R⊆B A 且 R={|xRy}，则称 R 是 R 的逆关系。
▲ 设 A 和 B 是集合，R ⊆A B（i=1,2），则⑴R =R ；⑵R∩R=R∩R；⑶R∪R=R∪R；⑷R-R=R-R；
⑸R=R；⑹若 R⊆R，则 R⊆R。
● 关系的合成：设 A，B 和 C 是集合，R⊆A B ，R⊆B C ，R 与 R 的合成关系是 R R⊆A C，
且 R R ={|x∈A∧z∈C∧∃y(y∈B∧xR y∧yR z)}.
合成运算不满足交换律，但是它满足结合律。
▲
● 关系的幂：设 A 是集合，R⊆A A，n∈N，则 R 的 n 次幂定义为 R =I ，R =R R。
▲
● 设 A 是集合，R⊆A A。若 R⊆A A，且满足：⑴R 是自反的（对称的、传递的）；⑵R⊆R；
⑶若 R⊆A A 且满足：①R 是自反的（对称的、传递的），②R⊆R,则⊆R；那么称 R 是 R
的自反（对称、传递）闭包，记为 r(R)(s(R),t(R))。
▲ 设 A 是集合，R⊆A A，则⑴R 是自反的当且仅当 r(R)=R；⑵R 是对称的当且仅当 s(R)=R；
⑶R 是传递的当且仅当 t(R)=R。
▲ 设 A 是集合，R ⊆A A，则⑴r(R)=R∪I ；⑵s(R)=R∪R;⑶t(R)= ∪R.
▲ 设 A 是集合，R ⊆A A(i=1,2)，若 R ⊆R ，则⑴r(R) ⊆r(R);⑵s(R) ⊆s(R);⑶t(R) ⊆
t(R);
▲ 设 A 是集合，R ⊆A A，⑴若 R 是自反的，则 s(R)和 t(R)j 自反的；⑵若 R 是对称的，则
r(R)和 t(R)是对称的；⑶若 R 是传递的，则 r(R)传递的。
▲ 设 A 是集合，R ⊆A A，则⑴rs(R)=sr(R);⑵rt(R)=tr(R);⑶st(R) ⊆ts(R).
4.4 等价关系和划分
● 设 A 是集合，R ⊆A A。若 R 是自反的、对称的和传递的，则称 R 是 A 上的等价关系，并
且若 aRb,则说 a 与 b 等价。
● 设 R 是集合 A 上的等价关系。对任何 a∈A,称[a] ={x|x∈A∧xRa}为 a 关于 R 的等价类
（有时简记为[a]），并且称 a 为[a] 的代表元；若等价类个数有限，则称 R 的不同类的
个数为 R 的秩，否则称 R 的秩是无限的，称{[a] |a∈A}为 A 关于 R 的商集，记为 A/R。
▲ 设 R 是 A 上的等价关系，A= ，a,b∈A,则⑴[a]= ;⑵aRb 当且仅当[a]=[b];⑶[a]=[b]
或者[a] ∩[b]= .
● 设集合 A= ，⊆ （A）。若 满足：⑴ ∈ ；⑵ 中任意两个不同元素不相交；⑶∪ =A；
则称 是 A 的一个划分，且称 中的元素为划分块；若 有限，则称 的不同划分块的个数
为 的秩，否则称 的秩是无限的。
▲ 设集合 A= ，R 是 A 上的等价关系，则 A/R 是 A 的一个划分。
▲ 设集合 A= ，R 和 R 是 A 上的等价关系，则 R =R 当且仅当 A/R =A/R 。
等价关系可以诱导一个划分，一个等价关系所诱导的划分是惟一的。
▲ 设 是非空集合 A 的划分，定义 A 上的二元关系 R 为： aRb 当且仅当 a 和 b 同属于 A 的
一个划分块。则 R 是 A 上的等价关系。
▲ 设集合 A= ，是 A 的一个划分，R 是 A 上的一个等价关系，则 诱导 R 当且仅当 R 诱导 。
一个等价关系可以惟一诱导出一个划分，一个划分也可惟一确定一个等价关系。
▲ 设集合 A= ， 和 是 A 的划分，且它们诱导的等价关系分别为 R 和 R，那么 细分 当且
仅当 R ⊆R。
● 设集合 A= ，和 是 A 划分。⑴若 是 A 的划分，且① 细分 和 ；②若 细分 和 ，则 细
分 ，则称 是 与 的积。记为 .⑵若 是 A 的划分，且① 和 细分 ；②若 和 细分 ，
则 细分 ，则称 是 与 的和。记为 。
▲ 设集合 A= ，和 是 A 的划分，且它们诱导的等价关系分别为 R 和 R ，那么⑴R∩R 诱
导的划分是 ；⑵t(R∪R)诱导的划分是 。
4.5 序关系
序关系是一类重要的二元关系，它提供了比较集合中元素的一种方法。
● 偏序关系：设 A 是集合，R ⊆A A。若 R 是自反的、反对称的和传递的，则称 R 是 A 上的
偏序关系，并称是偏序集。
偏序关系有时也称作半序或部分序关系，常用 表示偏序关系。
● 覆盖：设 R 是集合 A 上的偏序关系，a∈A.若 b∈A 满足⑴aRb 且 b=a;⑵若 x∈A 使得 aRx
且 xRb,则必有 x=a 或 x=b.那么称 b 是 a 关于 R 的覆盖。
●
● 拟序关系：设 A 是集合，R⊆A A。若 R 是反自反的和传递的，则称 R 是 A 上的拟序关系，
并称是拟序集。
▲ 拟序关系是反对称的。
▲ 设 A 是集合。R⊆A A。⑴若 R 是偏序关系，则 R-I 是拟序关系；⑵若 R 是拟序关系，则
R∪I 是偏序关系。
● 全序关系：设是偏序集，若∀x∀y(x∈A∧y∈A→x y∨y x),则称 是 A 上的全
序关系到，并称为全序集。全序关系也称作线序关系，全序集也称作线序集
或链。
● 良序关系：设是偏序集，若对任意的 S， =S⊆A,则 S 有最小元，那么称 是 A 上
的良序关系，并称为良序集。
4.6 相容关系
● 设 A 是集合，R⊆A A。若 R 是自反的和对称的，则称 R 是 A 上的相容关系；若 aRb,则称
x 与 y 相容，否则称 x 与 y 不相容。
● 设 R 是集合 A 上的相容关系。⑴若 =C⊆A，且∀a,b∈C,有 aRb,则称 C 是 R 的一个相容
类。⑵若 C 是 R 的相容类，∀b∈C,则必有 a∈C 使得 aRb,那么称 C 是 R 的一个极大相容
类。
▲ 求极大相容类的方法：⑴关系图法；
⑵关系矩阵法。
第五章 函数
5.1 函数的基本概念和性质
● 设 X 和 Y 是任意集合，f⊆X Y.若∀x(x∈X→∃!y(y∈Y∧∈f)),则称 f 是从 X 到 Y
的函数，记为 f:X→Y.
设 f: X→Y,X= .定义 R⊆X X 为∀x ,x ∈X,x Rx 当且仅当 f(x)=f(x),则易证 F 是 X
上的等价关系（称之为由 f 诱导的等价关系），并且由关系 R 确定的划分为{f ({y})|y
∈Y∧f ({y})= }.令 g:X→X/R,g(x)=[x] ,称 g 是由 f 诱导的规范映射。可见对给定的
一个函数均可得到一个规范映射。
● 设 X 和 Y 是任意集合，则从 X 到 Y 的所有函数构成的集合记为 Y ，即 Y ={f|f:X→Y}.
当一个函数是递归定义时，常需要验证函数是良定的(well-defined).
● 设 f:X→Y.⑴若 f(X)=Y,则称 f 是满射的。⑵若∀x∀x(x∈X∧f(x)=f(x)→x =x ),则称
f 是单射的。⑶若 f 既是单射的，又是满射的，则称 f 是双射的。
● 集合的的特征函数：设 U 是全集，A⊆U。定义 A 的特征函数 为 ：U→{0，1}， （x）=
▲
5.2 函数的合成
▲ 设 f:X→Y,g:Y→Z,则 f 与 g 的合成关系 f g 是从 X 到 Z 的函数，并且对一切 x∈X,f
g(x)=g(f(x)).
▲ 设 f:X→Y,g:Y→Z,则⑴若 f 和 g 是满射，则 g f 是满射；⑵若 f 和 g 是单射，则 g f 是
单射；⑶若 f 和 g 是双射，则 g f 是双射。
▲ 设 f:X→Y,g:Y→Z,则⑴若 g f 是满射，则 g 是满射；⑵若 g f 是单射，则 f 是满射；⑶
若 g f 是双射，则 g 是满射且 f 是单射。
5.3 逆函数
▲ 设 f:X→Y 是双射，则 f 的逆关系 f 是从 Y 到 X 的函数。
▲ 设 f 是从 X 到 Y 的双射，g 是从 Y 到 X 的函数，则 f =g 当且仅当 g f=1 且 f g=1 .
● 设 f:X→Y。若有 g:Y→X 使得 g f=1 和 f g=1 成立，则称 g 是 f 的逆函数，并称 f 是可
逆的。
● ⑴若有 g:X→Y,使得 g f=1 成立，则称 g 是 f 的左可逆函数，并称 f 是左可逆的。⑵若
有 g:X→Y,使得 f g=1 成立，则称 g 是 f 的右可逆函数，并称 f 是右可逆的。
▲ 设 f:X→Y,X= ,则⑴f 是左可逆的当且仅当 f 是单射；⑵f 是右可逆的当且仅当 f 是满射；
⑶f 是可逆的当且仅当 f 是双射，或当且仅当 f 既是左可逆的，又是右可逆的。
6.1 可数集和无限集
● 设 S 是任一集合，称 S =S∪{S}的后继集。
第六章 集合的基数
● 自然数 N 的归纳定义是：⑴ ∈N；⑵若 n∈N,则 n ∈N；⑶若 S∈N,且满足① ∈S；②
若 n∈S，则 n ∈S；则 S=N。
● 若 m,m∈N,n∈N 使 m∈n,则称 m 小于 m，记为 m
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
