离散数学-公式合集
命题联结词
等价公式
定义设A和B是两个命题公式，如果A和B在任意赋值情况下都具有相同的真值，则称A和B是等价公式。记为A?B。
性质定理
设A、B、C是公式，则
（1）A?A
（2）若A?B则B?A
（3）若A?B且B?C则A?C
定理设A、B、C是公式，则下述等价公式成立：
（1）双重否定律??A?A
（2）等幂律 A∧A?A ； A∨A?A
（3）交换律 A∧B?B∧A ； A∨B?B∨A
（4）结合律（A∧B）∧C?A∧（B∧C）
（A∨B）∨C?A∨（B∨C）
（5）分配律（A∧B）∨C?（A∨C）∧（B∨C）
（A∨B）∧C?（A∧C）∨（B∧C）
（6）德·摩根律?（A∨B）??A∧?B
?（A∧B）??A∨?B
（7）吸收律 A∨（A∧B）?A；A∧（A∨B）?A
（8）零一律 A∨1?1 ； A∧0?0
（9）同一律 A∨0?A ； A∧1?A
（10）排中律 A∨?A?1
（11）矛盾律 A∧?A?0
（12）蕴涵等值式 A→B??A∨B
（13）假言易位 A→B??B→?A
（14）等价等值式 A?B?（A→B）∧（B→A）
（15）等价否定等值式 A?B??A??B??B??A
（16）归缪式（A→B）∧（A→?B）??A
主合取范式取极大值，P=0
主析取范式取极小值，P=1
公式的蕴涵
1.6.1 蕴涵的概念定义
设G、H是两个公式，若G→H是永真式，则称G蕴涵H，记作G?H。
推理规则
1．前提引入规则：可以在证明的任何时候引入前提；
2．结论引入规则：在证明的任何时候，已证明的结论都可以作为后续证明的前提；3．置换规则：在证明的任何时候，命题公式中的任何子命题公式都可以用与之等价的命题公式置换。
4．附加：A?（A∨B）；
5．化简：（A∧B）?A；
6．假言推理：(A→B) ∧A?B
7．拒取式：（A→B）∧?B ??A；
8．假言三段论：（A→B）∧（B→C）?(A→C)；
9．析取三段论：(A∨B) ∧?B ?A;
10.等价三段论：（A?B）∧（B?C）?（A?C）
11.构造性二难规则：（A→B）∧（C→D）∧(A∨C)?（B∨D）；
12.合取引入规则：A,B?A∧B
推理常用方法
1.直接证法
直接证法就是根据一组前提，利用前面提供的一些推理规则，根据已知的等价公式和蕴涵式，推演得到有效的结论的方法，即有前提直接推导出结论。
例构造下列推理的证明。
前提：P∨Q，P→R，Q→S 结论：S∨R
证明（1）P∨Q 前提引入规则
（2）P→R 前提引入规则
（3）Q→S 前提引入规则
（4）S∨R （1）（2）（3）构造性二难规则
2．间接证法
间接证法主要有如下两种情况。
（1）附加前提证明法有时要证明的结论以蕴涵式的形式出现，即推理的形式结构为：（G1∧G2∧…∧G n）?（R→C）设（G1∧G2∧…∧G n）为S，则上述推理
可表示为证明S?（R→C），即证明S→（R→C）为永真式。
用附加前提证明法证明下面推理。
前提：P→（Q→R），?S∨P，Q 结论：S→R
证明：（1）?S∨P 前提引入规则
（2）S 附加前提引入规则
（3）P （1）（2）析取三段论规则
（4）P→（Q→R）前提引入规则
（5）Q→R （3）（4）假言推理规则
（6）Q 前提引入规则
（7）R （5）（6）假言推理规则
2）归缪法定义设G1，G2，…，G n是n个命题公式，如果G1∧G2∧…∧G n 是可满足式，则称G1，G2，…，G n是相容的。否则（即G1∧G2∧…∧G n是矛盾式）称G1，G2，…，G n是不相容的。
例用归缪法证明。
前提：P∨Q，P→R，Q→S 结论：S∨R
证明（1）?（S∨R）附加前提引入规则
（2）?S∧?R （1）置换规则
（3）?S （2）化简规则
（4）?R （2）化简规则
（5）Q→S 前提引入规则
（6）?Q∨S （5）置换规则
（7）?Q （3）（6）析取三段论
（8）P∨Q 前提引入规则
（9）P （7）（8）析取三段论规则
（10）P→R 前提引入规则
（11）?P∨R （10）置换规则
（12）R （9）（11）析取三段论规则
（13）?R∧R （4）（12）合取引入规则
谓词表示
例2.1 将下列命题在谓词逻辑中符号化，并讨论它们的真值：
（1）只有4是素数，8才是素数。
（2）如果2小于3，则8小于7。
解（1）设谓词G（x）：x是素数，a：4，b：8；
（1）中的题符号化为谓词的蕴涵式：G（a）→G（b）
由于此蕴涵式的前件为假，所以（1）中的命题为真。
（2）设谓词H（x，y）：x小于y，a：2，b：3，c：8，d：7
（2）中的命题符号化为谓词的蕴涵式：H（a，b）→H（c，d）
由于此蕴涵式的前件为真，后件为假，所以（2）中的命题为假。
例 2.2 在个体域分别限制为（a）和（b）条件时，将下面的命题符号化：（1）所有人都是要死的。
（2）有的人天生就近视。
其中：（a）个体域D1为人类集合。
（b）个体域D2为全总个体域。
解（a）令F（x）：x要死的；G（x）：x天生就近视。
（1）在个体域D1中除人外，没有其他的事物，因而（1）可符号化为：
?x F（x）
（2）在个体域D1中有些人是天生就近视，因而（2）可符号化为谓词的蕴涵式：
? x G（x）
（b）在个体域D2中除人外，还有其他的事物，因而在将（1）、（2）符号化时，必须考虑先将人分离出来，令M（x）：x是人。在D2中，（1）、（2）可分别描
述如下：对于宇宙间的一切事物，如果事物是人，则他是要死的。
（2）在宇宙间存在着天生就近视的人。将（1）、（2）分别符号化为：（1）?x（M（x）→F（x））
（2）?x（M（x）→G（x））
在个体域D1、D2中命题（1）、（2）都是真命题。
例2.3 在个体域分别限制为（a）和（b）条件时，将下面的命题符号化：（1）对任意的x，都有x2-5x+6=（x-2）（x-3）
（2）存在x，使得x+1=0。
其中：（a）个体域D1为自然数集合。
（b）个体域D2为实数集合。
解（a）令F（x）：x2-5x+6=（x-2）（x-3）；G（x）：x+1=0。
（1）可符号化为：
?x F(x)
（2）可符号化为：
?x G（x）
在个体域D1中命题（1）为真命题，命题（2）为假命题。
（b）在个体域D2中（1）、（2）符号化分别为
（1）?x F（x）
（2）?x G（x）
在个体域D2中命题（1）、（2）都是真命题。
例2.4 将下列命题符号化，并指出真值情况。
（1）没有人登上过月球。
（2）所有人的头发未必都是黑色的。
解个体域为全总个体域，令M（x）：x是人。
（1）令F（x）：x登上过月球。命题（1）符号化为：
??x（M（x）∧F（x））
设a是1969年登上月球完成阿波罗计划的一名美国人，则M（a）∧F（a）为真，故命题（1）为假。
（2）令H（x）：x的头发是黑色的。命题（2）可符号化为：
??x（M（x）→H（x））
我们知道有的人头发是褐色的，所以?x（M（x）→H（x））为假，故命题（2）为真。
例2.5 将下列命题符号化。
（1）猫比老鼠跑得快。
（2）有的猫比所有老鼠跑得快。
（3）并不是所有的猫比老鼠跑得快。
（4）不存在跑得同样快的两只猫。
解设个体域为全总个体域。令C（x）：x是猫；M（y）：y是老鼠；Q（x，y）：x比y跑得快；L（x，y）：x和y跑得同样快。这4个命题分别符号化为：
（1）?x?y（C（x）∧M（y）→Q（x，y））；
（2）?x（C（x）∧?y（M（y）→Q（x，y）））；
（3）??x ?y（C（x）∧M（y）→Q（x，y））；
（4）??x? y（C（x）∧C（y）∧L（x，y））
2.3 谓词逻辑约束公式的等价与蕴涵
2.3.1 谓词逻辑的等价公式
定义2.7 设A、B是命题逻辑中的任意两个公式，设它们有共同的个体域E，若对任意的解释I都有T I（A）= T I（B），则称公式A、B在E上是等价的，记作
A?B。
定理1设A（x）是谓词公式，有关量词否定的两个等价公式：
（1）﹁?x A（x）??x﹁A（x）
（2）﹁?x A（x）??x﹁A（x）
证明（1）设个体域是有限的为：D={ a1，a2，…，a n}，则有
﹁?x A（x）?﹁（A（a1）∧A（a2）∧…∧A（a n））
?﹁A（a1）∨﹁A（a2）∨…∨﹁A（a n））
??x﹁A（x）
（2）设个体域是有限的为：D={ a1，a2，…，a n}，则有﹁?x A（x）?﹁（A（a1）∨ A（a2）∨…∨A（a n））
?﹁A（a1）∧﹁A（a2）∧…∧﹁A（a n）
??x﹁A（x）
定理2 设A（x）是任意的含自由出现个体变项x的公式，B是不含x出现的公式，则有
（1）?x（A（x）∨B）??x A（x）∨B
（2）?x（A（x）∧B）??x A（x）∧B
（3）?x（A（x）→ B）??x A（x）→ B
（4）?x（B→A（x））?B→?x A（x）
（5）?x（A（x）∨B）??x A（x）∨B
（6）?x（A（x）∧B）??x A（x）∧B
（7）?x（A（x）→ B）??x A（x）→ B
（8）?x（B→A（x））?B→?x A（x）
4.量词分配等值式：
?x（A（x）∧B（x））??x A（x）∧?x B（x）
?x（A（x）∨B（x））??xA（x）∨?x B（x）
集合论
定义3.5 设A 是有限集，由A 的所有子集作为元素而构成的集合称为A 的幂集，记作ρ(A)，即ρ(A)＝｛X|X ?A ｝。在A 的所有子集中，A 和φ这两个子集又叫平凡子集。
例如：A ＝｛1，2，3｝，则 ρ(A)＝｛φ，｛1｝，｛2｝，｛3｝，｛1，2｝，｛1，3｝，｛2，3｝，｛1，2，3｝｝
定理3.2 设A 是有限集，|A|=n ，则A 的幂集ρ(A)的基为2n 。
证明：由排列组合知： n n n n n n c c c c A ++++=-110)( ρ
又由二项式定理知：
n n n n n
n n c c c c 2110=++++- 所以可得： n A 2)(=ρ
集合的运算
3.3.1 集合的并运算
定义3.6 任意两个集合A 、B 的并，记作A ∪B ，它也是一个集合，由所有属于A 或者属于B 的元素合并在一起而构成的，即
A ∪
B ＝｛x | x ∈A 或x ∈B ｝
例如，A ＝｛a ，b ，c ｝，B ＝｛a ，b ，c ，d ，e ｝，则A ∪B ＝｛a ，b ，c ，d ，e ｝
又如，A ＝｛1，2，3，4，5｝，B ＝｛1，3，5，7，9｝，则A ∪B ＝｛1，2，3，4，5，7，9｝
用文氏图表示集合之间的并运算：
用平面上的矩形表示全集U 。用矩形内的圆表示U 中的任一集合。图中表示了集合A 和集合B 的并集。阴影部分就是A ∪B 。
由集合并运算的定义可知，并运算具有以下性质：
（1）幂等律：A ∪A ＝A （2）同一律：A ∪φ＝A
（3）零律：A∪U＝U （4）结合律：(A∪B)∪C＝A∪(B∪C)
（5）交换律：A∪B＝B∪A
3.3.2 集合的交运算
定义3.7 任意两个集合A、B的交记作A∩B，它也是一个集合，由所有既属于A又属于B的元素构成，即
A∩B ＝｛x | x∈A且x∈B｝
例如，A＝｛a，b，c｝，B＝｛b，c，d，e｝，则A∩B＝｛b，c｝
又如，A＝｛1，2，3，4，5｝，B＝｛1，3，5，7，9｝，则A∩B＝｛1，3，5｝集合的交运算的文氏图表示，见图，其中阴影部分就是A∩B。
由集合交运算的定义可知，交运算有以下性质：
（1）幂等律：A∩A＝A
（2）同一律：A∩U＝A
（3）零律：A∩φ＝φ
（4）结合律：(A∩B)∩C＝A∩(B∩C)
（5）交换律：A∩B＝B∩A
定理3.3设A，B，C是三个集合，则下列分配律成立：
A∩（B∪C）＝（A∩B）∪（A∩C）
A∪（B∩C）＝（A∪B）∩（A∪C）
定理3.4设A，B为两个集合，则下列关系式成立：
A∪（A∩B）＝A A∩（A∪B）＝A
这个定理称为吸收律，可以用文氏图验证
3.3.3 集合的补
定义3.8设A、B是两个集合，A-B也是一个集合。它是由属于集合A但不属于集合B的所有元素组成的。A-B称为集合B关于A的补集(或相对补)。即
Ａ-B＝｛x|x∈Ａ且x?B｝
A-B也称为集合A和B的差集。
例如，Ａ＝｛a，b，c｝，B＝｛a，b｝，则Ａ-B＝｛c｝
又如，Ａ＝｛a，b，c，d｝，B＝｛a，b，e，f｝，则Ａ-B＝｛c，d｝定义3.9 设U是全集，A是U的一个子集，称U-A为A关于全集的补集，也叫做A的绝对补集，简称为补集。记作~A。即
U-Ａ＝｛x|x∈Ｕ且x?Ａ｝
例如，U＝｛x | x是江西理工大学的学生｝，
A＝｛x | x是江西理工大学的女学生｝，
则~A＝｛x | x是江西理工大学的男学生｝
集合的补运算有以下性质
（1）双重否定律：~（~A）＝A
（2）摩根律：~φ＝U
（3）摩根律：~U＝φ
（4）矛盾律：A∩（~A）＝φ
（5）排中律：A∪（~A）＝U
为了简单，约定A∩（~B）表示为A∩~B，A∪（~B）表示为A∪~B。
定理3.5设A、B是两个集合，则下列关系式成立：
~（A∪B）＝~A∩~B
~（A∩B）＝~A∪~B
这个定理称为德摩根定律。可以用文氏图验证
定理3.6 设A、B、C是任意三个集合，则下列关系式成立：
A-B＝A∩~B
A-B＝A-（A∩B）
定理可由差运算的定义直接得到。
3.3.4 集合的对称差
定义3.10设A、B是两个集合，集合A和B的对称差记作A⊕B，它是一个集合，其元素或属于A，或属于B，但不能既属于A又属于B。即
A⊕B＝(A∪B)-(A∩B)
例如，A＝｛a，b，c，d｝，B＝｛a，c，e，f，g｝
那么
A⊕B＝｛b，e，d，f，g｝
集合的对称差的文氏图表示
由对称差的定义易得下列性质：
（1）A⊕A＝φ
（2）A⊕φ＝A
（3）A⊕Ｕ＝~Ａ
（4）A⊕B＝B⊕A
（5）（A⊕B）⊕C＝A⊕（B⊕C）
（6）A⊕B＝(A-B)∪(B-A)
二元关系
序偶与笛卡儿积
4.1.1 有序n元组
定义4.1由两个固定次序的个体x，y组成的序列称为序偶，记为
定义4.2两序偶
4.1.2 笛卡儿积的概念
定义4.3给定两个集合A和B，如果序偶的第一个分量是A中的一个元素，第二个分量是B中的一个元素，则所有这种序偶的集合称为集合A和B的笛卡儿积，简称为卡氏积，记为A×B，即
例4.1（1）A={a，b}，B={c，d}，求A×B。
（2）A={a，b}，B={c，d}，求B×A。
（3）A={a，b}，B={1，2}，C={c}，求（A×B）×C和A×（B×C）。解（1）A×B={a，b}×{c，d}={
（2）B×A={c，d}×{a，b}={
（3）（A×B）={a，b}×{1，2}={
（A×B）×C={<
B×C={1，2}×{c}={<1，c>，<2，c>}。
A×（B×C）={
4.1.3 笛卡儿积的性质
定理4.1设A，B，C为任意3个集合，则有
（1）A×（B∪C）=（A×B）∪（A×C）
（2）A×（B∩C）=（A×B）∩（A×C）
（3）（A∪B）×C=（A×C）∪（B×C）
（4）（A∩B）×C=（A×C）∩（B×C）
定理4.2 设A，B，C为任意3个集合，且C≠φ，则有
A?B ?（A×C ?B×C）?（C×A ?C×B）
定理4.3设A，B，C，D为四个非空集合，则A×B?C×D的充分必要条件是：A?C且B?D。
反之，如果A?C且B?D，设任意x∈C和y∈B，有
?x∈C∧y∈D?
所以，A×B?C×D。
二元关系及其表示
4.2.1 二元关系的概念
定义4.4设A，B是两个集合，R是笛卡儿积A×B的任一子集，则称R为从A到B的一个二元关系，简称关系。特别当A=B时，则称R为A上的二元关系（或A上的关系）。
定义4.5设R是二元关系，由
R（R）={yx??（x∈A∧
例4.2 设A={a，b，c，d，e}，B={1，2，3}，R={
解 D（R）={a，b，c} ， R（R）={2，3}。
例4.3 设A={1，3，5，7}，R是A上的二元关系，当a，b∈A且a
解 R={<1，3>，<1，5>，<1，7>，<3，5>，<3，7>，<5，7>}
D（R）={1，3，5}，R（R）={3，5，7}。
定义4.6设I A为集合A上的二元关系，且满足I A={
为集合A上的恒等关系。
4.2.2 二元关系的表示
1．关系矩阵表示法
设给定集合A={a1，a2，…，a n}，集合B={b1，b2，…，b m}，R为从A到B
的一个二元关系，构造一个n×m矩阵。用集合A的元素标注矩阵的行，用集合B 的元素标注矩阵的列，对于a∈A和b∈B，若
2. 关系图表示法
有限集的二元关系可以用有向图来表示，设集合A={a1，a2，…，a n}，集合B={b1，b2，…，b m}，R为从A到B的一个二元关系，首先在平面上作出n个结点分别记作a1，a2，…，a n，然后另外作出m个结点分别记作b1，b2，…，b m，
如果a∈A、b∈B且
例4.8 A={1，2，3，4}，B={5，6，7}，R={<1，7>，<2，5>，<3，6>，<4，7>}，作出R的关系图。
解R的关系图，如图所示：
例4.9 设A={1，2，3，4}，R={<1，2>，<2，2>，<3，3>，<4，1>}。画出A 上的关系图。
解A上的关系图如图所示
4.3 关系的运算
4.3.1 关系的交、并、差、补运算
例4.10 设X={1，2，3，4，5}，若A={
解 A={<1，1>，<1，3>，<1，5>，<2，2>，<2，4>，<3，1>，<3，3>，<3，5>，<4，2>，<4，4>，<5，1>，<5，3>，<5，5>}
B={<4，1>，<5，2>}
A∪B={<1，1>，<1，3>，<1，5>，<2，2>，<2，4>，<3，1>，<3，3>，<3，5>，<4，1>，<4，2>，<4，4>，<5，1>，<5，2>，<5，3>，<5，5>}
A∩B=φ
A-B={<1，1>，<1，3>，<1，5>，<2，2>，<2，4>，<3，1>，<3，3>，<3，5>，<4，2>，<4，4>，<5，1>，<5，3>，<5，5>}
。
。
。
。
1
2
3
4
B-A={<4，1>，<5，2>}
~A={1，2，3，4，5}×{1，2，3，4，5}-{<1，1>，<1，3>，<1，5>，<2，2>，<2，4>，<3，1>，<3，3>，<3，5>，<4，2>，<4，4>，<5，1>，<5，3>，<5，5>}={<1，2>，<1，4>，<2，1>，<2，3>，<2，5>，<3，2>，<3，4>，<4，1>，<4，3>，<4，5>，<5，2>，<5，4>}
4.3.2 关系的复合运算
定义4.7设R是从集合A到集合B上的二元关系，S是从集合B到集合C 上的二元关系，则R?S称为R和S的复合关系，表示为
R?S={
例4.10 （1）A={1，2，3，4}，B={3，5，7}，C={1，2，3}，
R={<2，7>，<3，5>，<4，3>}，S={<3，3>，<7，2>}，
R?S={<2，2>，<4，3>}。如图所示：
（2）设R，S都是A上的关系，A={1，2，3，4}。
R={<1，2>，<1，3>，<3，4>}，S={<1，1>，<2，2>，<3，3>，<4，4>}，即S 为A上的恒等关系，则R?S=S?R=R。如图所示：
（3）设R是A上的关系，S为A上的空关系，即S=φ，则R?S=S?R=φ。
定理4.4设R是从A到B的关系，S是从B到C的关系，其中A={a1，a2，…，a m}，B={b1，b2，…，b n}，C={c1，c2，…，c t}。而M R，M S和M R ? S分别为关系R，S和R?S的关系矩阵，则有M R?S=M R·M S。
定理4.5设R是从集合A到集合B上的二元关系，S是从集合B到集合C 上的二元关系，T是从集合C到集合D上的二元关系，则有：
（1）R?（S∪T）=R?S∪R?T
（2）R?（S∩T）?R?S∩R?T
（3）（R∪S）?T= R?T∪S?T
。
。
。
。
1
2
4
3
（4）（R ∩S ）?T ?R ?T ∩S ?T
定理4.6 设R 是从A 到B 的关系，S 是从B 到C 的关系，T 是从C 到D 的关系，则有 R ?（S ?T ）=（R ?S ）?T 。
定义4.8 设R 是从A 上的关系，n 为整数，关系R 的n 次幂定义如下：
（1）R 0={
从关系R 的n 次幂定义，可得出下面的结论：
（1）R m n +=R n ?R m ； （2）nm m n R R =)(
4.3.3 关系的逆运算
定义4.9 设R 是从集合A 到集合B 的二元关系，如果将R 中每序偶的第一元素和第二元素的顺序互换，所得到的集合称为R 的逆关系，记为1-R ，即
1-R ={
定理4.7 设R ，S 和T 都是从A 到B 的二元关系，则下列各式成立：
（1）（（R ）1-）1-=R
（2）（R ∪S ）1-=R 1-∪S 1-
（3）（R ∩S ）1-=R 1-∩S 1-
（4）（A ×B ）1- =B ×A
（5）（~R ）1-= ~（R 1-）（这里~R=A ×B -R ）
（6）（R -S ）1-=R 1--S 1-
定理4.8 设R 是从A 到B 的二元关系，S 是从B 到C 的二元关系，则下面的式子成立： （R ?S ）1-=S 1-?R 1-
证明
? ?y （y ∈B ∧
? ?y （y ∈B ∧
?
所以， （R ?S ）1-=S 1-?R 1-。
4.4 关系的性质
4.4.1 自反性和反自反性
定义4.10设R是集合A上的二元关系，如果对于每个x∈A，都有
R在A上是自反的??x（x∈A→
定义4.11设R是集合A上的二元关系，如果对于每个x∈A，都有
R在A上是反自反的??x（x∈A→< x，x >?R）
4.4.2 对称性和反对称性
定义4.12设R是集合A上的二元关系，如果对于每个x，y∈A，当
R在A上是对称的??x?y（x∈A∧y∈A∧
定义4.13设R是集合A上的二元关系，如果对于每个x，y∈A，当
4.4.3 传递性
定义4.14设R是集合A上的二元关系，如果对于任意x，y，z∈A，当
R在A上是传递的??x?y?z（x∈A∧y∈A∧z∈A∧
例4.13 设A={a，b，c}，R，S，T是A上的二元关系，其中
R={
S={
T={
说明R，S，T是否为A上的传递关系。
解根据传递性的定义知，R和T是A上的传递关系，S不是A上的传递关系，因为
4.4.4 关系性质的判定
1．自反性的判定方法
定理4.9设R是A上的二元关系，则R在A上是自反的当且仅当I A?R。
证明 先证必要性。任取
从而证明了I A ?R 。
再证充分性。任取x ∈A ，有
x ∈A ?
因此，R 在A 上是自反的。
1．自反性的判定方法
R 的关系矩阵为： R 的关系图为
2．反自反性的判定方法
定理4.10 设R 是A 上的二元关系，则R 在A 上是反自反的当且仅当
I A ∩R=φ。
例4.15 设集合A={a ，b ，c ，d }，A 上的二元关系R={，，，，
解 由于，，
R 的关系矩阵为： R 的关系图为：
3．对称性的判定方法
定理4.11 设R 是A 上的二元关系，则R 在A 上是对称的当且仅当R=R 1-。 例4.16 设集合A={a ，b ，c ，d}，A 上的二元关系R={，，，，
解 因为?R ，所以R 不是自反的。
????????????=1000110101100011R M 。。。。a b
d c ?????
???????=0100100101010110R M
由于
R 1-={，，，，
R 的关系矩阵为 R 的关系图为:
4．反对称性的判定方法
定理4.12 设R 是A 上的二元关系，则R 在A 上是反对称的当且仅当
R ∩R 1-?I A 。
例4.17 设集合A={a ，b ，c ，d}，A 上的二元关系R={，，，
解 因为?R ，所以R 不是自反的。由于
R 的关系矩阵为： R 的关系图为：
5．传递性的判定方法
定理4.3 设A ，B ，C ，D 为四个非空集合，则A ×B ?C ×D 的充分必要条件是：
A ?C 且
B ?D 。
定理4.13 设R 是A 上的二元关系，则R 在A 上是传递的当且仅当R ?R ?R ?????
???????=1100101101010110R M ????????????=1001100001010100R M 。。。。a b
d c
定理4.14设集合A={a1，a2，…，a n}，R是A上的二元关系，R的关系矩阵为M R，令M=M R?M R，则R在A上是传递的当且仅当矩阵M的第i行，第j列元素为1时，M R的第i行，第j列元素必为1。
4.5 关系的闭包
定义4.15设是集合A上的二元关系，如果有另一个关系满足：
（1）是自反的（对称的、传递的）；
（2）?；
（3）对于任何自反的（对称的、传递的）关系，如果有?，就有?。
则称关系为R的自反（对称、传递）闭包。
定理4.15设R是集合A上的二元关系，则自反闭包r（R）=R∪I A.
定理4.16设R是集合A上的二元关系，则对称闭包 s（R）=R∪R1-.
定理4.17设R是集合A上的二元关系，则传递闭包t（R）==R∪R2∪R3∪…
定理4.18设A={a1，a2，…，a n}，R是集合A上的二元关系，则存在一个正整数k≤n，使得
t（R）= R∪R2∪R3∪…∪R k
定理4.19设R是非空集合A上的关系，则
（1）R是自反的，当且仅当r（R）=R；
（2）R是对称的，当且仅当s（R）=R；
（3）R是传递的，当且仅当t（R）=R。
定理4.20设R，S是非空集合A上的关系，且R?S，则
（1）r（R）?r（S）；
（2）s（R）?s（S）；
（3）t（R）?t（S）。
定理4.21设R是非空集合A上的关系，则
（1）rs（R）= sr（R）；
（2）rt（R）= tr（R）；
（3）ts（R）?st（R）。
4.6 等价关系与集合的划分
4.6.1 等价关系
定义4.16 设R 是非空集合A 上的二元关系，如果有R 是自反的、对称的和传递的，则称R 是集合A 上的等价关系
例：设集合A={a ，b ，c ，d ，}，R={，， b>，， 证明 写出R 的关系矩阵从关系矩阵主对角线元素都是1，可知R 是自反的。关系 矩阵是对称的，故R 是对称的。从R 的序偶表达式中，可以看出R 是传递的，逐个检查序偶，如，∈R ，有∈R 。， 4.6.2 等价类 定义4.17 设R 是非空集合A 上的等价关系，对于任何a ∈A ，集合 [a]R ={x ∣x ∈A 且∈R} 称为元素a 形成的R 等价类。 定理4.22 设R 是非空集合A 上的等价关系，对于a ，b ∈R ，有∈R 当且仅当[a]R =[b]R 。 定义4.18 设R 是集合A 上的等价关系，等价类集合{[a]R ∣a ∈A}称作A 关于R 的商集，记作A/R 。 定理4.22 设R 是非空集合A 上的等价关系，对于a ，b ∈R ，有∈R 当且仅当[a]R =[b]R 。 定义4.19 设A 是一个集合，A 1，A 2，…，A m 是它的子集，如果它满足下列条件： （1）所有A i 间均是分离的，亦即对所有i ，j （i=1，2，…，m ，j=1，2，…，m ），如果i ≠j ，则A i ∩A j =φ。 （2）A 1∪A 2∪…∪A m =A 则称A={A 1，A 2，…，A m }为集合A 的一个划分，而A 1，A 2，…，A m 称为这个划分的块。 ????? ???????1001011001101001 定理4.23设R是非空集合A上的等价关系，确定了A的一个划分，该划分就是商集A/R。 定理4.24集合A的一个划分确定A上的一个等价关系。 定理4.25 设R1和R2是非空集合A上的等价关系，则R1=R2当且仅当 A/R1=A/R2。 例4.28 设集合A={1，2，3，4，5}上的关系R为 R={<1，1>，<1，2>，<2，1>，<1，3>，<3，1>，<2，2>，<2，3>，<3，2>，<3，3>，<4，4>，<4，5>，<5，4>，<5，5>}。 解它的关系图如图4.9所示：由此图可以看出关系R是等价关系，并且它的 等价类分别为[1]R=[2]R=[3]R[4]R=[5]R 由等价关系所构成的等价类在图中即是等价关系图中的完全图，所谓完全图是指图形中每个结点与其它结点有边联结的图形。 4.7 相容关系 4.7.1 相容关系 定义4.20设R是集合A上的一个二元关系，如果R是自反的、对称的，则称R是相容关系。 定义4.21设R是集合A上的一个相容关系，C是A的子集，如果对于C 中任意两个元素x，y，有 定义4.22设R是集合A上的一个相容关系，不能真包含在任何其它相容类 中的相容类，称作最大相容类，记作C R。 定理4.26设R是有限集A上的相容关系，C是一个相容类，那么一定存在 一个最大相容类C R，使得C?C R。。 4.7.2 覆盖 定理4.27给定集合A的覆盖{A1，A2，…，A n}，由它确定的关系R=A1×A1∪A2×A2∪…∪A n×A n是A上的相容关系。 定理4.28集合A上相容关系R与完全覆盖存在一一对应. 例4.27 设A={a，b，c，d，e，f}，R为A上的相容关系，其图形表示如图所示。求R的完全覆盖。 c b 。。 。 。 。。 d f e a 离散数学必备知识点总 结 Document number：NOCG-YUNOO-BUYTT-UU986-1986UT 总结离散数学知识点 第二章命题逻辑 1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P,Q,R的顺序依次写； 6.真值表中值为1的项为极小项，值为0的项为极大项； 7.n个变元共有n2个极小项或极大项，这n2为(0~n2-1)刚好为化简完后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P规则，T规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 第三章谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含→，存在量词用合取^; 3.既有存在又有全称量词时，先消存在量词，再消全称量词； 第四章集合 1.N，表示自然数集，1,2,3……，不包括0； 2.基：集合A中不同元素的个数，|A|； 3.幂集：给定集合A，以集合A的所有子集为元素组成的集合，P(A)； 4.若集合A有n个元素，幂集P(A)有n2个元素，|P(A)|=||2A=n2； 5.集合的分划：(等价关系) ①每一个分划都是由集合A的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 第五章关系 1.若集合A有m个元素，集合B有n个元素，则笛卡尔A×B的基 2种不同的关系； 数为mn，A到B上可以定义mn 2.若集合A有n个元素，则|A×A|=2n，A上有22n个不同的关系； 、基本等值式 ⑴双重否定律 A A ⑵籍等律 A A A A A V A A ⑶交换律 A A B BA A A V B BV A ⑷结合律 A V (B V C) (A V B) V C A A (B A C) (A A B) A C ⑸分配律 A V (B A C) (A V B) A (A V C) A A (B V C) (A A B) V (A A C) (6)德摩根律(A V B) AA B (A A B) AV B ⑺吸收律 A (8)零律A ⑼同一律 A (10) 排中律 A (11) 矛盾律 A (12) 蕴含等值式A (13) 等价等值式A V (A A B) V1 1 A1 A V A 1 A A 0 B AV B (A A A A A B B) A (B A) A (A V B) A 0 0 V 0 A A A B (AV B) A (A V B) A B (A A B) V ( AA B ) (14) 假言易位ABBA (15) 等价否定等值式ABA B (16)归谬论(A B) A (A B) A 一、推理定律里口编涵式 1.A ( A B) 附加律 2.( A B) A 化简律 3.( A B) A B 假言推理 4.( A B) B A 拒取式 5.( A B) B A 析取三段论 6.( A B) (B C) (A 假言三段论 7.( A B) (B Q (A C) 等价三段论 8.( A B) (C D) (A C) (B D) 构造性二难 (A B) ( A B) B 构造性二难(特殊形式) 9.( A B) (C D) ( B D) ( A Q 破坏性二难 三、量词辖域收缩与扩张 x(A(x) V B) xA(x) VB x(A(x) A B) xA(x) AB x(A(x) —B) xA(x) F x(B t A(x)) B T xA(x) x(A(x) V B) xA(x) VB x(A(x) A B) xA(x) A B x(A(x) —B) xA(x) F x(B t A(x)) B T xA(x) 四、量词分配 x(A(x) A B(x)) xA(x) A xB(x) x(A(x) V B(x)) xA(x) V xB(x) x(A(x) V B(x)) xA(x) V xB(x) 第二章谓词逻辑 2—1基本概念 例题1. 所有的自然数都是整数。 设N(x):x是自然数。I(x):x是整数。此命题可以写成?x(N(x)→I(x)) 例题2. 有些自然数是偶数。 设E(x):x是偶数。此命题可以写成?x(N(x)∧E(x)) 例题3. 每个人都有一个生母。 设P(x):x是个人。M(x,y):y是x的生母。此命题可以写 成:?x(P(x)→?y(P(y)∧M(x,y))) 2-2 谓词公式及命题符号化 例题1. 如果x是奇数,则2x是偶数。 其中客体x与客体2x之间就有函数关系,可以设客体函数g(x)=2x, 谓词O(x):x是奇数,E(x):x是偶数, 则此命题可以表示为:?x(O(x)→E(g(x))) 例题2 小王的父亲是个医生。 设函数f(x)=x的父亲,谓词D(x):x是个医生,a:小王,此命题可以表示为D(f(a))。 例题3 如果x和y都是奇数,则x+y是偶数。 设h(x,y)=x+y ,此命题可以表示为:?x?y((O(x)∧O(y))→E(h(x,y)) 命题的符号表达式与论域有关系 两个公式:一般地,设论域为{a1,a2,....,an},则有 (1). ?xA(x)?A(a1)∧A(a2)∧......∧A(an) (2). ?xB(x)?B(a1)∨B(a2)∨......∨B(an) 1.每个自然数都是整数。该命题的真值是真的。 表达式?x(N(x)→I(x))在全总个体域的真值是真的, 因?x(N(x)→I(x))?(N(a1)→I(a1))∧(N(a2)→I(a2))∧…∧(N(an)→I(an)) 式中的x不论用自然数客体代入,还是用非自然数客体代入均为真。例如(N(0.1)→I(0.1))也为真。 而?x(N(x)∧I(x))在全总个体域却不是永真式。 离散数学基础试题（二） 一、判断题（每题2分，共12分） 1.在命运题逻辑中，任何命题公式的主合取范式都是存在的，并且是唯一的。（） 2.与是不等值的（） 3.设是非连通平面图G的对偶图，设分别为的顶点数，边数和面数，则它们之间满足欧拉公式：。（） 4.设无向图G具有割点，则G中一定不存在哈密尔顿通路。（） 5.设，A上的恒等关系既是A上的等价关系也是A上的偏序关系。（） 6.设A,B,C,D均为非空的集合，已知A*B且C*D，则一定有。（） 二、填空题（每小题3分，共30分） 1.设p:小王走路,q:小王听音乐,在命题逻辑中，命题“小王边走路边听音乐”的符号化形式为___________________。 2.设F(x):x是人，H(x,y):x与y一样高，在一阶逻辑中，命题“人都不一样高”的符号化形式为_________________。 3.的成真赋值为________________________。 4.设G是n阶无向带权边通图，各变的权均为a(a>0),设T是G的一棵最小生成树，则T的权W(T)=_______________________。 5.设G1,G2,G3,G4都是4阶3条边的无向简单图，则它们之间至少有 ___________________个是同构的。 6．设G是n（n2）阶二部图，又是平面图，则命题“G的对偶图是欧拉图”的真值为_______________________。 7.设为整数集，，则f的值域ranf=___________。 8.设则A上共有____________个不同的等价关系。 9.设，恒等关系IA的传递闭包t(IA)=_________________。 数理逻辑部分 第2章一阶逻辑 2.1 一阶逻辑基本概念 个体词（个体）: 所研究对象中可以独立存在的具体或抽象的客体个体常项：具体的事物，用a, b, c表示 个体变项：抽象的事物，用x, y, z表示 个体域: 个体变项的取值范围 有限个体域，如{a, b, c}, {1, 2} 无限个体域，如N, Z, R, … 全总个体域: 宇宙间一切事物组成 谓词: 表示个体词性质或相互之间关系的词 谓词常项：F(a)：a是人 谓词变项：F(x)：x具有性质F 一元谓词: 表示事物的性质 多元谓词(n元谓词, n≥2): 表示事物之间的关系 如L(x,y)：x与y有关系L，L(x,y)：x≥y，… 0元谓词: 不含个体变项的谓词, 即命题常项或命题变项 量词: 表示数量的词 全称量词?: 表示任意的, 所有的, 一切的等 如?x 表示对个体域中所有的x 存在量词?: 表示存在, 有的, 至少有一个等 如?x表示在个体域中存在x 一阶逻辑中命题符号化 例1 用0元谓词将命题符号化 要求：先将它们在命题逻辑中符号化，再在一阶逻辑中符号化(1) 墨西哥位于南美洲 在命题逻辑中, 设p:墨西哥位于南美洲 符号化为p, 这是真命题 在一阶逻辑中, 设a：墨西哥，F(x)：x位于南美洲 符号化为F(a) 例2 在一阶逻辑中将下面命题符号化 (1)人都爱美; (2) 有人用左手写字 分别取(a) D为人类集合, (b) D为全总个体域 . 解：(a) (1) 设G(x)：x爱美, 符号化为?x G(x) (2) 设G(x)：x用左手写字, 符号化为?x G(x) (b) 设F(x)：x为人，G(x)：同(a)中 离散数学自学笔记命题公式及其真值表 我们把表示具体命题及表示常命题的p，q，r，s等与f，t统称为命题常元（proposition constant）。深入的讨论还需要引入命题变元（proposition variable）的概念，它们是以“真、假”或“1，0”为取值范围的变元，为简单计，命题变元仍用p，q，r，s等表示。相同符号的不同意义，容易从上下文来区别，在未指出符号所表示的具体命题时，它们常被看作变元。 命题常元、变元及联结词是形式描述命题及其推理的基本语言成分，用它们可以形式地描述更为复杂的命题。下面我们引入高一级的语言成分——命题公式。 定义1.1 以下三条款规定了命题公式（proposition formula）的意义： （1）命题常元和命题变元是命题公式，也称为原子公式或原子。 （2）如果A，B是命题公式，那么（┐A），（A∧B），（A∨B），（A→B），（A？B）也是命题公式。 （3）只有有限步引用条款（1），（2）所组成的符号串是命题公式。 命题公式简称公式，常用大写拉丁字母A，B，C等表示。公式的上述定义方式称为归纳定义，第四章将对此定义方式进行讨论。 例1.8 （┐（p→（q∧r）））是命题公式，但（qp），p→r，p1∨p2∨…均非公式。 为使公式的表示更为简练，我们作如下约定： （1）公式最外层括号一律可省略。 （2）联结词的结合能力强弱依次为┐，（∧，∨），→，？，（∧，∨）表示∧与∨平等。 （3）结合能力平等的联结词在没有括号表示其结合状况时，采用左结合约定。湖南省自考网：https://www.wendangku.net/doc/4b12538584.html,/整理 例如，┐p→q∨（r∧q∨s）所表示的公式是（（┐p）→（q∨（（r∧q）∨s））） 设A是命题公式，A1是A 的一部分，且A1也是公式，则A1称为公式A的子公式。 离散数学部分概念和公式总结 命题：称能判断真假的陈述句为命题。 命题公式：若在复合命题中，p、q、r等不仅可以代表命题常项，还可以代表命题变项，这样的复合命题形式称为命题公式。 命题的赋值：设A为一命题公式，p ,p ,…,p 为出现在A中的所有命题变项。给p ,p ,…,p 指定一组真值，称为对A的一个赋值或解释。若指定的一组值使A的值为真，则称成真赋值。真值表：含n（n≥1）个命题变项的命题公式，共有2^n组赋值。将命题公式A在所有赋值下的取值情况列成表，称为A的真值表。 命题公式的类型：（1）若A在它的各种赋值下均取值为真，则称A为重言式或永真式。 （2）若A在它的赋值下取值均为假，则称A为矛盾式或永假式。 （3）若A至少存在一组赋值是成真赋值，则A是可满足式。 主析取范式：设命题公式A中含n个命题变项，如果A得析取范式中的简单合取式全是极小项，则称该析取范式为A的主析取范式。 主合取范式：设命题公式A中含n个命题变项，如果A得析取范式中的简单合析式全是极大项，则称该析取范式为A的主析取范式。 命题的等值式：设A、B为两命题公式，若等价式A?B是重言式，则称A与B是等值的，记作A<=>B。 约束变元和自由变元：在合式公式?x A和?x A中，称x为指导变项，称A为相应量词的辖域，x称为约束变元，x的出现称为约束出现，A中其他出现称为自由出现（自由变元）。一阶逻辑等值式：设A，B是一阶逻辑中任意的两公式，若A?B为逻辑有效式，则称A与B是等值的，记作A<=>B，称A<=>B为等值式。 前束范式：设A为一谓词公式，若A具有如下形式Q1x1Q2x2Q k…x k B，称A为前束范式。集合的基本运算：并、交、差、相对补和对称差运算。 笛卡尔积：设A和B为集合，用A中元素为第一元素，用B中元素为第二元素构成有序对组成的集合称为A和B的笛卡尔积，记为A×B。 二元关系：如果一个集合R为空集或者它的元素都是有序对，则称集合R是一个二元关系。特殊关系：（1）、空关系：Φ（2）全域关系：EA={ 离散数学公式 ————————————————————————————————作者: ————————————————————————————————日期： ? 基本等值式 1．双重否定律A?┐┐A ２．幂等律 A ? A∨A,?A ?A∧A 3．交换律?Ａ∨Ｂ?B∨A，?A∧B ?B∧A 4.结合律??（Ａ∨Ｂ)∨Ｃ? A∨（B∨Ｃ) ?(A∧B)∧C ? A∧(Ｂ∧Ｃ) ５.分配律Ａ∨(B∧C）?（Ａ∨B)∧(Ａ∨C）(∨对∧的分配律）??A∧(B∨Ｃ）?(A∧B）∨（A∧Ｃ) (∧对∨的分配律) 6.德·摩根律?┐(A∨B) ?┐A∧┐B ┐（A∧Ｂ）?┐A∨┐B 7.吸收律?Ａ∨(Ａ∧Ｂ) ?A,A∧(A∨B) ?Ａ 8．零律?A∨１?1,A∧0 ?０ ９.同一律?A∨0 ?A，A∧1?Ａ 10．排中律A∨┐A ?１ 11．矛盾律?A∧┐Ａ? 0 12.蕴涵等值式Ａ→B?┐A∨B １3．等价等值式??Ａ?Ｂ?(A→B）∧(Ｂ→Ａ) １4.假言易位A→Ｂ?┐Ｂ→┐A 15.等价否定等值式 A?B ?┐Ａ?┐Ｂ 16.归谬论(A→Ｂ)∧（A→┐B)?┐A 求给定公式范式的步骤 (1)消去联结词→、?(若存在)。 (2）否定号的消去(利用双重否定律)或内移(利用德摩根律)。 (３）利用分配律：利用∧对∨的分配律求析取范式,∨对∧的分配律求合取范式。 推理定律-－重言蕴含式 (１）A ?(A∨B) 附加律 (2) （A∧B）? A ?化简律 （3） (Ａ→B)∧Ａ? B ??假言推理 (４) (Ａ→B)∧┐Ｂ?┐A 拒取式 （5）(A∨B）∧┐B? A ?析取三段论 (6) (A→B) ∧（Ｂ→C)?（A→C) ?假言三段论 (7) (Ａ?B) ∧（B?C) ? (Ａ? C)?等价三段论 （8) (A→B)∧（Ｃ→Ｄ）∧(A∨Ｃ) ?(B∨Ｄ) 构造性二难 (A→B)∧(┐Ａ→B)∧(Ａ∨┐A) ?Ｂ构造性二难（特殊形式) （9)(A→B)∧(Ｃ→Ｄ)∧(┐B∨┐D) ?(┐Ａ∨┐C) 破坏性二难 离散数学的基础知识点总结 第一章命题逻辑 1.前键为真，后键为假才为假；＜—＞，相同为真，不同为假；2?主析取范式：极小项（m）之和；主合取范式：极大项（M）之积； 3.求极小项时，命题变元的肯定为1，否定为0,求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P,Q,R的顺序依次写; 6.真值表中值为1的项为极小项，值为0的项为极大项； 7.n个变元共有2n个极小项或极大项，这2n为（0~2n-1）刚好为化简完后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法（=＞）:真值表法；分析法（假定前键为真推出后键为真，假定前键为假推出后键也为假） 10.命题逻辑的推理演算方法：P规则，T规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 第二章谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含T,存在量词用合取“； 3.既有存在又有全称量词时，先消存在量词，再消全称量词； 第四章集合 1.N，表示自然数集，1,2,3……，不包括0; 2.基：集合A中不同元素的个数，|A|; 3.幕集：给定集合A，以集合A的所有子集为元素组成的集合，P(A)； 4.若集合A有n个元素，幕集P(A)有2°个元素，|P(A)|= 2|A|= 2； 5.集合的分划：(等价关系) ①每一个分划都是由集合A的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 第五章关系 1.若集合A有m个元素，集合B有n个元素，则笛卡尔AXB的基数为mn , A到B上可以定义2mn种不同的关系； 2.若集合A有n个元素，则|A X\|= n2, A上有2n个不同的关系； 3.全关系的性质：自反性，对称性，传递性； 空关系的性质：反自反性，反对称性，传递性； 全圭寸闭环的性质：自反性，对称性，反对称性，传递性； 4.前域（domR）:所有元素x组成的集合； 基本等值式 1.双重否定律 A ?┐┐A 2.幂等律 A ? A∨A, A ? A∧A 3.交换律A∨B ? B∨A， A∧B ? B∧A 4.结合律(A∨B)∨C ? A∨(B∨C) (A∧B)∧C ? A∧(B∧C) 5.分配律A∨(B∧C) ? (A∨B)∧(A∨C) （∨对∧的分配律） A∧(B∨C) ? (A∧B)∨(A∧C) （∧对∨的分配律） 6.德·摩根律┐(A∨B) ?┐A∧┐B ┐(A∧B) ?┐A∨┐B 7.吸收律 A∨(A∧B) ? A，A∧(A∨B) ? A 8.零律A∨1 ? 1,A∧0 ? 0 9.同一律A∨0 ? A，A∧1 ? A 10.排中律A∨┐A ? 1 11.矛盾律A∧┐A ? 0 12.蕴涵等值式A→B ?┐A∨B 13.等价等值式A?B ? (A→B)∧(B→A) 14.假言易位A→B ?┐B→┐A 15.等价否定等值式 A?B ?┐A?┐B 16.归谬论(A→B)∧(A→┐B) ?┐A 求给定公式范式的步骤 (1)消去联结词→、?(若存在)。 (2)否定号的消去(利用双重否定律)或内移(利用德摩根律)。 (3)利用分配律：利用∧对∨的分配律求析取范式，∨对∧的分配律求合取范式。 推理定律--重言蕴含式 (1) A T (A∨B) 附加律 (2) (A∧B) T A 化简律 (3) (A→B)∧A T B 假言推理 (4) (A→B)∧┐B T┐A 拒取式 (5) (A∨B)∧┐B T A 析取三段论 (6) (A→B) ∧(B→C) T (A→C) 假言三段论 (7) (A?B) ∧(B?C) T (A ? C) 等价三段论 (8) (A→B)∧(C→D)∧(A∨C) T(B∨D) 构造性二难 (A→B)∧(┐A→B)∧(A∨┐A) T B 构造性二难(特殊形式) (9)(A→B)∧(C→D)∧(┐B∨┐D) T(┐A∨┐C)破坏性二难 理学院 《离散数学基础》实验教学大纲 课程名称：离散数学基础实验 课程编号：080J21A 课程总学时：51 实验学时数：17 课程总学分：2.5 实验学分：0.5 开设实验项目数：5 一、实验教学目的 面向离散数学在计算机中的应用，通过实验操作，使学生掌握研究计算机科学的基础理论，进一步提高学生的抽象思维与逻辑推理能力，增强实际应用能力。 二、实验项目内容、基本要求与学时分配 注：1、实验类型：演示、验证、操作、综合、设计、研究。2、实验要求：指必做、选做。 三、实验考核方式与标准 实验考核以学生的实验态度、掌握的实验理论、实际操作技能和实验报告等为主，各单项考核内容所占分数比例为：实验态度占10%、实验理论占15%；操作技能占50%；实验报告占25%。 四、实验教材与参考书 推荐教材：《离散数学》（修订版），耿素云屈婉玲编著，高等教育出版社，2004年。 主要参考书：《离散数学导论》第二版，徐洁磬编著，高等教育出版社，1997年。 《离散数学》， [美]S.利普舒尔茨， M.利普森，周兴和、孙志人、张学斌译, 科学出版社和麦格劳-希尔教育出版集团, 2001年。 《计算方法》实验教学大纲 课程名称：计算方法实验 课程编号：080J22B 课程总学时：85 实验学时数：34 课程总学分：4 实验学分：1 开设实验项目数：5 一、实验教学目的 本课程以MATLAB或C为编程语言，将《计算方法》课程中的常用算法用MATLAB语言描述并上机进行数值实验。通过实验，使学生进一了解各个算法的特点及适用范围，提高学生用计算机解决实际问题的能力。 二、实验项目内容、基本要求与学时分配 三、实验考核方式与标准 实验考核以学生的实验态度、掌握的实验理论、实际操作技能和实验报告等为主，各单项考核内容所占分数比例为：实验态度占10%、实验理论占15%；操作技能占50%；实验报告占25%。 四、实验教材与参考书 1、《计算机数值方法》（第二版），施吉林等，高教出版社出版，2005年 2、《计算方法引论》（第二版），徐翠薇、孙绳武，高等教育出版社，2002 总结离散数学知识点 第二章命题逻辑 1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P,Q,R的顺序依次写； 6.真值表中值为1的项为极小项，值为0的项为极大项； 7.n个变元共有n2个极小项或极大项，这n2为(0~n2-1)刚好为化简完后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P规则，T规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 第三章谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含→，存在量词用合取^; 3.既有存在又有全称量词时，先消存在量词，再消全称量词； 第四章集合 1.N，表示自然数集，1,2,3……，不包括0； 2.基：集合A中不同元素的个数，|A|； 3.幂集：给定集合A，以集合A的所有子集为元素组成的集合，P(A)； 4.若集合A有n个元素，幂集P(A)有n2个元素，|P(A)|=||2A=n2； 5.集合的分划：(等价关系) ①每一个分划都是由集合A的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 第五章关系 1.若集合A有m个元素，集合B有n个元素，则笛卡尔A×B的基 2种不同的关系； 数为mn，A到B上可以定义mn 2.若集合A有n个元素，则|A×A|=2n，A上有22n个不同的关系； 离散数学基本知识 体积和表面积三角形的面积,底×高?2。公式S= a×h?2 正方形的面积,边长×边长公式 S= a2 长方形的面积,长×宽公式S= a×b 平行四边形的面积,底×高公式S= a×h 梯形的面积,(上底+下底)×高?2 公式 S=(a+b)h?2 内角和:三角形的内角 和,180度。 长方体的表面积,(长×宽，长×高，宽×高) ×2 公 式:S=(a×b+a×c+b×c)×2 正方体的表面积,棱长×棱长×6 公式: S=6a2 长方体的体积,长×宽×高公式:V = abh 长方体(或正方体)的体积,底面积×高公式:V = abh 正方体的体积,棱长×棱长×棱长公式:V = a3 圆的周长,直径×π公式:L,πd,2πr 1 圆的面积,半径×半径×π公式:S,πr2 圆柱的表(侧)面积:圆柱的表(侧)面积等于底面的周长乘高。公 式:S=ch=πdh,2πrh 圆柱的表面积:圆柱的表面积等于底面的周长乘高再加上两头的圆的面积。公式:S=ch+2s=ch+2πr2 圆柱的体积:圆柱的体积等于底面积乘高。公式:V=Sh 圆锥的体积,1/3底面×积高。公式:V=1/3Sh 算术 1、加法交换律:两数相加交换加数的位置，和不变。 2、加法结合律:a + b = b + a 3、乘法交换律:a × b = b × a 4、乘法结合律:a × b × c = a ×(b × c) 5、乘法分配律:a × b + a × c = a × b + c 6、除法的性质:a ? b ? c = a ?(b × c) 7、7、除法的性质:在除法里，被除数和除数同时扩大(或缩小)相同的倍数，商不变。 O除以任何不是O的数都得O。简便乘法:被乘数、乘数末尾有O的乘法，可以先把O前面的相乘，零不参加运算，有几个零都落下，添在积的末尾。 8、 8、有余数的除法: 被除数,商×除数+余数方程、代数与等式 2 9、等式:等号左边的数值与等号右边的数值相等的式子叫做等式。等式的基本性质:等式两边同时乘以(或除以)一个相同的数，等式仍然成立。 10、方程式:含有未知数的等式叫方程式。一元一次方程式:含有一个未知数，并且未知数的次数是一次的等式叫做一元一次方程式。学会一元一次方程式的例法及计算。即例出代有χ的算式并计算。 11、代数: 代数就是用字母代替数。代数式:用字母表示的式子叫做代数式。如:3x =ab+c 分数:把单位“1”平均分成若干份，表示这样的一份或几分的数,叫做分数。 分数大小的比较:同分母的分数相比较，分子大的大，分子小的小。异分母的分数相比较，先通分然后再比较;若分子相同，分母大的反而小。 分数的加减法则:同分母的分数相加减，只把分子相加减，分母不变。异分母的分数相加减， 先通分，然后再加减。 分数乘整数，用分数的分子和整数相乘的积作分子，分母不变。 分数乘分数，用分子相乘的积作分子，分母相乘的积作为分母。 3 离散数学总结 班级：学号：姓名： 临近期末各科课程已经结束，随之而来就是总结各科学习总结和对这门学科的建议。《离散数学》这门课程当然也不会例外了。经过一个学期的学习我发现《离散数学》是一门理论性非常强的课程，而且知识点非常多，定义和定理以及定律是数之不尽。 《离散数学》顾名思义就是一门数学，它是数学众多领域中的一个小分支，即使是一个小小的分支，但是它的内容也非常之多，同时也非常抽象。自认我的数学成绩还是不错的，但是面对《离散数学》我就头痛，书本里面很多知识点我都是似懂非懂地。但鉴于《离散数学》在计算科学中的重要性，这是一门必须牢牢掌握的课程。因此我也很无奈，只好硬着头皮去学好它了。 离散数学是理论性较强的学科，学习离散数学的关键是对离散数学(集合论、数理逻辑和图论)有关基本概念的准确掌握，对基本原理及基本运算的运用，并要多做练习。 《离散数学》的特点是： 1、知识点集中，概念和定理多。《离散数学》是建立在大量概念之上的逻辑推理学科，概念的理解是我们学习这门学科的核心。不管哪本离散数学教材，都会在每一章节列出若干定义和定理，接着就是这些定义定理的直接应用。掌握、理解和运用这些概念和定理是学好这门课的关键。要特别注意概念之间的联系，而描述这些联系的则是定理和性质。 2、方法性强：离散数学的特点是抽象思维能力的要求较高。通过对它的学习，能大大提高我们本身的逻辑推理能力、抽象思维能力和形式化思维能力，从而今后在学习任何一门计算机科学的专业主干课程时，都不会遇上任何思维理解上的困难。《离散数学》的证明题多，不同的题型会需要不同的证明方法（如直接证明法、反证法、归纳法等），同一个题也可能有几种方法。但是《离散数学》证明题的方法性是很强的，如果知道一道题用什么方法讲明，则很容易可以证出来，否则就会事倍功半。因此在平时的学习中，要勤于思考，对于同一个问题，尽可能多探讨几种证明方法，从而学会熟练运用这些证明方法，再者要善于总结。 在学习《离散数学》的过程中，我明白了理解概念是至关重要的。只有概念明确，才有可能将离散数学学好。但是初学者往往不能够将概念与现实世界中的事物联系起来，这是学好离散数学的基础，因此也是初学者面临的一个困难。只有克服它，你才能有可能学好《离散数学》。 学完这门课后，我总结到了，如果你想学得更好——你可以在进行完一章的学习后，用专门的时间对该章包括的定义与定理实施强记。只有这样才可能本课程的抽象能够适应，并为后续学习打下良好的基础。而且必须及时复习和总结。 《离散数学》是一门数学科，大家都知道学数学就是要大量做数学，因此《离散数学》也不会例外。学习数学不仅限于学习数学知识，更重要的还在于学习数学的思维方法。这一点非常重要。 课程虽然是上完了，但是老师你的教学方法独特而新颖，思想开化而先进，是个容易沟通的老师。有你带着我们学习《离散数学》就是我们不想学好，我想也是很难吧！就我来说每次上课时在我快要与“周公”会面之际，你突然一个笑话和雷人的语录，我和“周公”迫不得已就分开了。当我再次看到周公时，耳边 离散数学笔记 第一章命题逻辑 合取 析取 定义 1. 1.3否定：当某个命题为真时，其否定为假，当某个命题为假时，其否定为真定义 1. 1.4条件联结词，表示“如果……那么……”形式的语句 定义 1. 1.5双条件联结词，表示“当且仅当”形式的语句 定义 1.2.1合式公式 (1)单个命题变元、命题常元为合式公式，称为原子公式。 (2)若某个字符串A 是合式公式，则?A、(A)也是合式公式。 (3)若A、B 是合式公式，则A ∧B、A∨B、A→B、A?B 是合式公式。 (4)有限次使用(2)~(3)形成的字符串均为合式公式。 1.3等值式 1.4析取范式与合取范式 将一个普通公式转换为范式的基本步骤 1.6推理 定义 1.6.1 设 A 与 C 是两个命题公式， 若 A → C 为永真式、 重言式，则称 C 是 A 的有 效结论，或称 A 可以逻辑推出 C ，记为 A => C 。（用等值演算或真值表） 第二章 谓词逻辑 2.1、基本概念 ?：全称量词 ?：存在量词 一般情况下， 如果个体变元的取值范围不做任何限制即为全总个体域时， 带 “全称量词”的谓词公式形如"?x(H(x)→B(x))，即量词的后面为条件式，带“存在量词”的谓词公式形如?x(H(x)∨WL(x))，即量词的后面为合取式 例题 R(x)表示对象 x 是兔子，T(x)表示对象 x 是乌龟， H(x,y)表示 x 比 y 跑得快，L(x,y)表示x 与 y 一样快，则兔子比乌龟跑得快表示为： ?x ?y(R(x)∧T(y)→H(x,y)) 有的兔子比所有的乌龟跑得快表示为：?x ?y(R(x)∧T(y)→H(x,y)) 2.2、谓词公式及其解释 定义 2.2.1、 非逻辑符号： 个体常元(如 a,b,c)、 函数常元(如表示22 y x 的 f(x,y))、 谓词常元(如表示人 类的 H(x))。 定义 2.2.2、逻辑符号：个体变元、量词(??)、联结词(﹁∨∧→?)、逗号、括号。 定义 2.2.3、项的定义：个体常元、变元及其函数式的表达式称为项(item)。 定义 2.2.4、原子公式：设 R(n x x ... 1)是 n 元谓词，n t t ...1是项，则 R(t)是原子公式。原子公式中的个体变元，可以换成个体变元的表达式(项)，但不能出现任何联结词与量词，只能为单个的谓词公式。 定义 2.2.5 合式公式：(1)原子公式是合式公式；(2)若 A 是合式公式，则(﹁A)也是合式公式；(3)若 A,B 合式，则 A ∨B, A ∧B, A →B , A ?B 合式(4)若 A 合式，则?xA 、?xA 合式(5)有限次使用(2)~(4)得到的式子是合式。 定义 2.2.6 量词辖域：?xA 和?xA 中的量词?x/?x 的作用范围，A 就是作用范围。 定义 2.2.7 约束变元：在?x 和?x 的辖域 A 中出现的个体变元 x ，称为约束变元，这是与量词相关的变元，约束变元的所有出现都称为约束出现。 定义 2.2.8 自由变元：谓词公式中与任何量词都无关的量词，称为自由变元，它的每次出现称为自由出现。一个公式的个体变元不是约束变元，就是自由变元。 注意：为了避免约束变元和自由变元同名出现，一般要对“约束变元”改名，而不对自由变元改名。 定义 2.2.9 闭公式是指不含自由变元的谓词公式 怎样学好离散数学 最常和理论计算机科学放在一起的一个词是什么？答：离散数学。这两者的关系是如此密切，以至于它们在不少场合下成为同义词。（这一点在前面的那本书中也有体现）传统上，数学是以分析为中心的。数学系的同学要学习三四个学期的数学分析，然后是复变函数，实变函数，泛函数等等。实变和泛函被很多人认为是现代数学的入门。在物理，化学，工程上应用的，也以分析为主。 随着计算机科学的出现，一些以前不太受到重视的数学分支突然重要起来。人们发现，这些分支处理的数学对象与传统的分析有明显的区别：分析研究的问题解决方案是连续的，因而微分，积分成为基本的运算；而这些分支研究的对象是离散的，因而很少有机会进行此类的计算。人们从而称这些分支为“离散数学”。“离散数学”的名字越来越响亮，最后导致以分析为中心的传统数学分支被相对称为“连续数学”。 《离散数学》作为一个单独的分枝，在世界上出现的时间并不久，不过几十年，但它的各部分内容中有相当一部分却早已出现在数学中。为什么将各个数学分支中的一些内容集中起来加以研究，并且冠上一个新的名称——离散数学呢？这主要是因为计算机科学的产生和发展。正如恩格斯所说：“……科学的状况还更多的从属于技术的状况和需要。倘若社会上有了一种技术上的需要，那就比十个大学还更能推动科学前进。”①计算机的出现，在很大程度上影响到了人们的思想和生活，对社会生产起了重大作用。为了研究计算机科学的理论基础，离散数学也就应运而生。因此，如果我们不从纯数学的角度，而从应用数学的角度来考虑，也许给离散数学换一个名称一一计算机科学的数学基础——更能说明问题。 正是因为这个原因，在计算机科学系。信息管理系都将离散数学作为必须学习的基础课程。而实践证明这种做法是正确的。 离散数学(Discrete mathematics)是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。 随着信息时代的到来，工业革命时代以微积分为代表的连续数学占主流的地位已经发生了变化，离散数学的重要性逐渐被人们认识。离散数学课程所传授的思想和方法，广泛地体现在计算机科学技术及相关专业的诸领域，从科学计算到信息处理，从理论计算机科学到计算机应用技术，从计算机软件到计算机硬件，从人工智能到认知系统，无不与离散数学密切相关。 由于数字电子计算机是一个离散结构，它只能处理离散的或离散化了的数量关系，因此，无论计算机科学本身，还是与计算机科学及其应用密切相关的现 方法、知识点总结（知识重点和考题重点） 前三章重点内容（知识重点）： 1、蕴含（条件）“→”的真值 P→Q的真值为假，当且仅当P为真，Q为假。 2、重言(永真)蕴涵式证明方法 <1>假设前件为真，推出后件也为真。 <2>假设后件为假，推出前件也为假。 易错 3、等价公式和证明中运用 4、重要公式 重言蕴涵式：P∧Q => P or Q P or Q => p∨Q A->B =>(A∧or∨C)->(B∧or∨C) 其他是在此基础上演变 等价公式：幂等律 P∧P=P P∨P=P 吸收律 P∧(P∨Q)=P P∨(P∧Q)=P 同一律 P∨F=P P∧T=P P∨T=T P∧F=F P <-> Q = (P->Q)∧(Q->P) = (P∧Q)∨(﹁P∧﹁Q) 5、范式的写法（最方便就是真值表法） 6、派遣人员、课表安排类算法： 第一步：列出所有条件，写成符号公式 第二步：用合取∧连接 第三步：求上一步中的析取范式即可 7、逻辑推理的写法 直接推理论证：其中I公式是指重言蕴涵式那部分 其中E公式是指等价公式部分 条件论证: 形如 ~ , ~, ~ => R->S R P(附加条件) ... ... S T R->S CP 8、谓词基本内容 注意：任意用—> 连接 存在用∧连接 量词的否定公式 量词的辖域扩充公式 量词分配公式 其他公式 9、带量词的公式在论域内的展开 10、量词辖域的扩充公式 11、前束范式的写法 给定一个带有量词的谓词公式， 1)消去公式中的联接词→和←→(为了便于量词辖域的扩充)； 2)如果量词前有“﹁?”，则用量词否定公式﹁?”后移。再用摩根定律或求公式的否定公式，将“﹁?”后移到原子谓词公式之前； 3)用约束变元的改名规则或自由变元的代入规则对变元换名(为量词辖域扩充作准备)； 《离散数学》期末复习大纲（完整版）（含例题和考试说明） 一、命题逻辑 [复习知识点] 1、命题与联结词（否定￢、析取∨、合取∧、蕴涵→、等价?），复合命题 2、命题公式与赋值（成真、成假），真值表，公式类型（重言、矛盾、可满足），公式的基本等值式 3、范式：析取范式、合取范式，极大（小）项，主析取范式、主合取范式 4、公式类型的判别方法（真值表法、等值演算法、主析取/合取范式法） 5、命题逻辑的推理理论 本章重点内容：命题与联结词、公式与解释、（主）析取范式与（主）合取范式、公式类型的判定、命题逻辑的推理 [复习要求] 1、理解命题的概念；了解命题联结词的概念；理解用联结词产生复合命题的方法。 2、理解公式与赋值的概念；掌握求给定公式真值表的方法，用基本等值式化简其它公式，公式在解释下的真值。 3、了解析取（合取）范式的概念；理解极大（小）项的概念和主析取（合取）范式的概念；掌握用基本等值式或真值表将公式化为主析取（合取）范式的方法。 4、掌握利用真值表、等值演算法和主析取/合取范式的唯一性判别公式类型和公式等价方法。 5、掌握命题逻辑的推理理论。 [疑难解析] 1、公式类型的判定 判定公式的类型，包括判定公式是重言的、矛盾的或是可满足的。具体方法有两种，一是真值表法，二是等值演算法。 2、范式 求范式，包括求析取范式、合取范式、主析取范式和主合取范式。关键有两点：一是准确理解掌握定义；另一是巧妙使用基本等值式中的分配律、同一律和互补律（排中律、矛盾律），结果的前一步适当使用幂等律，使相同的短语（或子句）只保留一个。 3、逻辑推理 掌握逻辑推理时，要理解并掌握12个（除第10，11）推理规则和3种证明法（直接证明法、附加前提证明法和归谬法）。 例1.试求下列公式的主析取范式： 图论部分 第七章、图的基本概念 7.1 无向图及有向图 无向图与有向图 多重集合: 元素可以重复出现的集合 无序积: A&B={(x,y) | x∈A∧y∈B} 定义无向图G= 通常用G表示无向图, D表示有向图, 也常用G泛指 无向图和有向图, 用e k表示无向边或有向边. V(G), E(G), V(D), E(D): G和D的顶点集, 边集. n 阶图: n个顶点的图 有限图: V, E都是有穷集合的图 零图: E=? 平凡图: 1 阶零图 空图: V=? 顶点和边的关联与相邻：定义设e k=(v i,v j)是无向图G=离散数学必备知识点总结
离散数学基本公式
离散数学谓词逻辑课后总结
离散数学基础试题(二)
离散数学第二章一阶逻辑知识点总结
离散数学自学笔记命题公式及其真值表
离散数学部分概念和公式总结
离散数学公式
离散数学的基础知识点总结
离散数学公式
离散数学基础实验教学大纲Word版
离散数学知识点总结
离散数学基本知识
离散数学总结
完整word版,离散数学知识汇总,推荐文档
怎样又快又好地学好离散数学
东北大学离散数学复习总结
离散数学复习提纲(完整版)
离散数学第七章图的基本概念知识点总结docx