当前位置：文档库 › 离散数学公式 (2)

离散数学公式 (2)

基本等值式

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 ? (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→C) 假言三段论

(7) (A?B) ∧(B?C) ? (A ? C) 等价三段论

(8) (A→B)∧(C→D)∧(A∨C) ?(B∨D) 构造性二难

(A→B)∧(┐A→B)∧(A∨┐A) ? B 构造性二难(特殊形式)

(9)(A→B)∧(C→D)∧(┐B∨┐D) ?(┐A∨┐C) 破坏性二难

设个体域为有限集D={a1,a2,…,an},则有

（1）?xA(x) ? A(a1)∧A(a2)∧…∧A(an)

（2）?xA(x) ? A(a1)∨A(a2)∨…∨A(an)

设A(x)是任意的含自由出现个体变项x的公式，则

（1）┐?xA(x) ??x┐A(x)

（2）┐?xA(x) ??x┐A(x)

设A(x)是任意的含自由出现个体变项x的公式，B中不含x的出现，则（1）?x(A(x)∨B) ??xA(x)∨B

?x(A(x)∧B) ??xA(x)∧B

?x(A(x)→B) ??xA(x)→B

?x(B→A(x)) ? B→?xA(x)

（2）?x(A(x)∨B) ??xA(x)∨B

?x(A(x)∧B) ??xA(x)∧B

?x(A(x)→B) ??xA(x)→B

?x(B→A(x)) ? B→?xA(x)

设A(x)，B(x)是任意的含自由出现个体变项x的公式，则

（1）?x(A(x)∧B(x)) ??xA(x)∧?xB(x)

（2）?x(A(x)∨B(x)) ??xA(x)∨?xB(x)

全称量词“?”对“∨”无分配律。

存在量词“?”对“∧”无分配律。

UI规则。

UG规则。EG规则。

A(c)

xA(x)

或

A(y)

xA(x)

∴

xA(x)

A(y)

∴

xA(x)

A(c)

∴

EI规则。

A∪B＝{x|x∈A∨x∈B } 、

A∩B＝{x|x∈A∧x∈B }

A－B＝{x|x∈A∧x?B }

幂集P(A)＝{x | x?A}

对称差集A⊕B＝(A－B)∪(B－A)

A⊕B＝(A∪B)－(A∩B)

绝对补集～A＝{x|x ? A }

广义并∪A＝{x | ?z(z∈A∧x∈z)} 广义交∩A＝{x | ?z(z∈A→x∈z)} 设A＝{{a,b,c},{a,c,d},{a,e,f}} B＝{{a}} C＝{a,{c,d}}

则∪A＝{a,b,c,d,e,f}

∪B＝{a}

∪C＝a∪{c,d}

∪?＝?

∩A＝{a}

∩B＝{a}

∩C＝a∩{c,d}

集合恒等式

幂等律A∪A＝A A∩A＝A

结合律(A∪B)∪C＝A∪(B∪C)(A∩B)∩C＝A∩(B∩C)

交换律A∪B＝B∪A A∩B＝B∩A

A(c)

xA(x)

∴

分配律A∪(B∩C)＝(A∪B)∩(A∪C) A∩(B∪C)＝(A∩B)∪(A∩C)

同一律A∪?＝A A∩E＝A

零律A∪E＝E A∩?＝?

排中律A∪～A＝E

矛盾律A∩～A＝?

吸收律A∪(A∩B)＝A A∩(A∪B)＝A

德摩根律A－(B∪C)＝(A－B)∩(A－C)A－(B∩C)＝(A－B)∪(A－C)～(B∪C)＝～B∩～C～(B∩C)＝～B∪～C

～?＝E～E＝?

双重否定律～(～A)＝A

集合运算性质的一些重要结果

A∩B?A，A∩B?B

A?A∪B，B?A∪B

A－B?A

A－B＝A∩～B

A∪B＝B ? A?B ? A∩B＝A ? A－B＝?

A⊕B＝B⊕A

(A⊕B)⊕C＝A⊕(B⊕C)

A?⊕＝A

A⊕A＝?

A⊕B＝A⊕C ? B＝C

对偶(dual)式：一个集合表达式，如果只含有∩、∪、～、?、E、＝、?、?，那么同时把∩与∪互换，把?与E互换，把?与?互换，得到式子称为原式的对偶式。

有序对具有以下性质：（1）当x≠y时，≠。

（2）＝的充分必要条件是x＝u且y＝v。

笛卡儿积的符号化表示为A×B＝{|x∈A∧y∈B}

如果|A|=m,|B|=n,则|A×B|=mn。

笛卡儿积的运算性质

(1)对任意集合A，根据定义有

A×?＝?, ?×A＝?

(2)一般的说，笛卡儿积运算不满足交换律，即

A×B≠B×A (当A≠?∧B≠?∧A≠B 时)

(3)笛卡儿积运算不满足结合律，即

(A×B)×C≠A×(B×C) (当A≠?∧B≠?∧C≠?时)

(4)笛卡儿积运算对并和交运算满足分配律，即

A×(B∪C)=(A×B)∪(A×C) (B∪C)×A=(B×A)∪(C×A)

A×(B∩C)=(A×B)∩(A×C) (B∩C)×A=(B×A)∩(C×A)

(5)A?C ∧B?D ? A×B ? C×D

常用的关系

对任意集合A，定义

全域关系 EA={|x ∈A ∧y ∈A}=A ×A 恒等关系 IA={|x ∈A}

空关系 ?

小于或等于关系：LA={|x,y ∈A ∧x ≤y}，其中 A ?R 。

整除关系：DB={|x,y ∈B ∧x 整除y}，其中 A ?Z* ，Z*是非零整数集包含关系：R ?＝{|x,y ∈A ∧x ?y}，其中 A 是集合族。

关系矩阵和关系图

设 A={1,2,3,4}，R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>}，则R 的关系矩阵和关系图分别是

定义域 dom R ＝ {x | ?y(∈R )} 值域 ran R ＝{y | ? x(∈R)} 域 fld R ＝dom R ∪ ran R

例求R={<1,2>,<1,3>,<2,4>,<4,3>}的定义域、值域和域。解答 dom R ＝{1,2,4} ran R ＝{2,3,4} fld R ＝{1,2,3,4}

逆 R-1＝{|∈R}

右复合 F ?G ＝{ | ?t(∈F ∧∈G)}

限制 R ↑A={|xRy ∧x ∈A} 像 R[A]=ran(R ↑A)

例设R ＝{<1,2>，<1,3>，<2,2>，<2,4>，<3,2>}

R ↑{1}＝{<1,2>，<1,3>} R ↑? ＝? R ↑{2,3}＝{<2,2>，<2,4>}，<3,2>} R[{1}]＝{2,3} R[?] ＝? R[{3}]＝{2}

设F 是任意的关系，则 (1)(F-1)-1＝F

(2)dom F-1＝ran F ，ran F-1＝dom F 设F ，G ，H 是任意的关系，则 (1)(F ?G)?H ＝F ?(G ?H) (2)(F ?G)-1＝G-1 ? F-1

设R 为A 上的关系，则R ? IA ＝IA ? R ＝R 设F ，G ，H 是任意的关系，则 (1) F ?(G ∪H)＝F ?G ∪F ?H (2) (G ∪H)?F ＝G ?F ∪H ?F (3) F ?(G ∩H)?F ?G ∩F ?H (4) (G ∩H)?F ?G ?F ∩H ?F

?????

????

???=00

000011000011M R

设F为关系，A,B为集合，则

(1) F↑(A∪B)＝F↑A∪F↑B

(2) F[A∪B]＝F[A]∪F[B]

(3) F↑(A∩B)＝F↑A∩F↑B

(4) F[A∩B]?F[A]∩F[B]

关系的幂运算

设R为A上的关系，n为自然数，则R的n次幂定义为：

（1）R0＝{|x∈A}＝IA

（2）Rn+1＝Rn ? R

幂运算的性质

设A为n元集，R是A上的关系，则存在自然数s和t,使得Rs=Rt。

设R是A上的关系，m,n∈N，则

(1)Rm ? Rn＝Rm+n (2)(Rm)n＝Rmn

设R是A上的关系，若存在自然数s,t(s

(1) 对任何k∈N有Rs+k=Rt+k

(2) 对任何k,i∈N有Rs+kp+i=Rs+i，其中p=t-s

(3) 令S={R0，R1，…，Rt-1}，则对于任意的q∈N有Rq∈S

自反?x(x∈A→∈R)，

反自反?x(x∈A→?R)，

对称?x?y(x,y∈A∧∈R→∈R)

反对称?x?y(x,y∈A∧∈R∧∈R→x=y)，

传递?x?y?z(x,y,z∈A∧∈R∧∈R→∈R)

关系性质的等价描述

设R为A上的关系，则

（1）R在A上自反当且仅当IA ? R

（2）R在A上反自反当且仅当R∩IA＝?

（3）R在A上对称当且仅当R＝R-1

（4）R在A上反对称当且仅当R∩R-1 ? IA

（5）R在A上传递当且仅当R?R?R

(1)若R1，R2是自反的和对称的，则R1∪R2也是自反的和对称的。

(2)若R1和R2是传递的，则R1∩R2也是传递的。

关系性质的特点

自反性反自反性对称性反对称性传递性集合表达式IA ? R R∩IA＝?R＝R-1 R∩R-1 ? IA R?R?R

关系矩阵主对角线元

素全是1 主对角线元素

全是0

矩阵是对称矩

阵

若rij＝1，且i

≠j，则rji＝0

对M2中1所

在位置，M中

相应的位置都

是1

关系图每个顶点都

有环每个顶点都没

有环

如果两个顶点

之间有边，一

定是一对方向

相反的边(无

单边)

如果两点之间

有边，一定是

一条有向边(无

双向边)

如果顶点xi到

xj有边，xj到

xk有边，则从

xi到xk也有边

关系的性质和运算之间的关系

自反性反自反性对称性反对称性传递性R1-1 √√√√√

R1∩R2 √√√√√

R1∪R2 √√√××

R1－R2 ×√√√×

R1 ? R2 √××××

闭包的构造方法

设R为A上的关系，则有

（1）自反闭包r(R)＝R∪R0

（2）对称闭包s(R)＝R∪R-1

（3）t(R)＝R∪R2∪R3∪…

关系性质与闭包运算之间的联系

设R是非空集合A上的关系，

（1）若R是自反的，则s(R)与t(R)也是自反的。

（2）若R是对称的，则r(R)与t(R)也是对称的。

（3）若R是传递的，则r(R)是传递的。

等价类的性质

设R是非空集合A上的等价关系，则

（1）?x∈A，[x]是A的非空子集。

（2）?x,y∈A，如果xRy，则[x]＝[y]。

（3）?x,y∈A，如果?R，则[x]与[y]不交。

（4）∪{[x]|x∈A}＝A。

偏序集中的特殊元素

设为偏序集，B?A，y∈B。

（1）若?x(x∈B→y≤x)成立，则称y为B的最小元。

（2）若?x(x ∈B →x ≤y)成立，则称y 为B 的最大元。

（3）若?x(x ∈B ∧x ≤y →x ＝y)成立，则称y 为B 的极小元。（4）若?x(x ∈B ∧y ≤x →x ＝y)成立，则称y 为B 的极大元

上界

下界上确界下确界 {2,3,6,12,24,36} 无无

无无 {6,12} 12,24,36 2,3,6 12 6 {2,3,6} 6,12,24,36 无 6 无 {6}

6,12,24,36, 2,3,6,

函数相等

由定义可知，两个函数F 和G 相等, 一定满足下面两个条件：（1）dom F ＝dom G

（2）?x ∈dom F ＝dom G ，都有 F(x )＝G(x )

所有从A 到B 的函数的集合记作BA ，读作“B 上A ”，符号化表示为 BA ＝{f | f ：A →B} 。例：设A ＝{1,2,3}，B ＝{a,b}，求BA 。

BA ＝{ f 0, f 1, f 2, f 3, f 4, f 5, f 6, f 7} 。其中

f 0＝{<1,a>,<2,a>,<3,a>} f 1＝{<1,a>,<2,a>,<3,b>} f 2＝{<1,a>,<2,b>,<3,a>} f 3＝{<1,a>,<2,b>,<3,b>} f 4＝{<1,b>,<2,a>,<3,a>} f 5＝{<1,b>,<2,a>,<3,b>} f 6＝{<1,b>,<2,b>,<3,a>} f 7＝{<1,b>,<2,b>,<3,b>}

设f :A →B ，（1）若ran f ＝B ，则称f :A →B 是满射(surjection )的。

（2）若?y ∈ran f 都存在唯一的x ∈A 使得f (x )＝y ，则称 f :A →B 是单射(injection )的。（3）若f 既是满射又是单射的，则称f :A →B 是双射(bijection )

单射双射函数满射例：判断下面函数是否为单射、满射、双射的，为什么?

最大元最小元极大元极小元

{2,3,6,12,24,36} 无无 24，36 2,3 {6,12} 12 6 12 6 {2,3,6} 6 无 6 2,3 {6}

a b c

1 2 3

12 6

a b c

1 2 3 4

a b c

1 2 3

4 d

a b c

1 2 3

4 d

(1) f：R→R，f(x)= -x2+2x-1 (2) f：Z+→R，f(x)=ln x，Z+为正整数集

(3) f：R→Z，f(x)=?x?(4) f：R→R，f(x)=2x+1。

解（1）f 在x=1取得极大值0。既不是单射也不是满射的。

（2）f 是单调上升的，是单射的，但不满射。ran f={ln1, ln2, …}。

（3）f 是满射的，但不是单射的，例如f(1.5)=f(1.2)=1。

（4）f 是满射、单射、双射的，因为它是单调函数并且ran f=R。

例：(1) 给定无向图G＝，其中V＝{v1,v2,v3,v4,v5}，

E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)}.

(2) 给定有向图D=，其中V＝{a,b,c,d}，

E＝{,,,,,,}。

画出G与D的图形。

邻域：NG(v1) ＝{v2，v5} 后继元集：Г+D(d ) ＝{c}

闭邻域：NG(v1) ＝{v1，v2，v5} 先驱元集：Г-D(d ) ＝{a，c}

关联集：IG(v1) ＝{e1，e2，e3} 邻域：ND(d ) ＝{a，c}

闭邻域：ND(d )＝{a，c，d}

d(v1)＝4(注意，环提供2度)，出度：d+(a)＝4，入度：d-(a)＝1

△＝4，δ＝1，(环e1提供出度1，提供入度1)，

v4是悬挂顶点，e7是悬挂边。d(a)＝4+1＝5。△＝5，δ＝3，

△+＝4 (在a点达到)

度数列为4,4,2,1,3。δ+＝0(在b点达到)

△-＝3(在b点达到)

δ-＝1(在a和c点达到)

按字母顺序，度数列：5,3,3,3

出度列：4,0,2,1 入度列：1,3,1,2

设G＝是n阶m条边的无向图，则下面各命题是等价的：

（1）G是树。（2）G中任意两个顶点之间存在唯一的路径。

（3）G中无回路且m＝n-1。（4）G是连通的且m＝n-1。

（5）G是连通的且G中任何边均为桥。

（6）G中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到唯一的一个含新边的圈。

例题已知无向树T中，有1个3度顶点，2个2度顶点，其余顶点全是树叶，试求树叶数，并画出满足要求的非同构的无向树。

解答设有x片树叶，于是结点总数

n＝1+2+x＝3+x

由握手定理和树的性质m＝n-1可知，

2m＝2(n-1)＝2×(2+x)

＝1×3+2×2+x

解出x＝3，故T有3片树叶。

故T的度数应为1、1、1、2、2、3。

求最小生成树的算法（避圈法(Kruskal)）

(1)设n阶无向连通带权图G＝有m条边。不妨设G中没有环（否则，可以将所有的环先删去），将m条边按权从小到大排序：e1,e2,…,em。

(2)取e1在T中。

(3)依次检查e2,…,em，若ej(j≥2)与已在T中的边不构成回路，取ej也在T中，否则弃去ej。

(4)算法停止时得到的T为G的最小生成树为止。

例：求下图所示两个图中的最小生成树。

W(T1)＝6 W(T2)＝12

T是n(n≥2)阶有向树，

(1) T为根树—T中有一个顶点入度为0，其余顶点的入度均为1

(2) 树根——入度为0的顶点

(3) 树叶——入度为1，出度为0的顶点

(4) 内点——入度为1，出度不为0的顶点

(5) 分支点——树根与内点的总称

(6) 顶点v的层数——从树根到v的通路长度

(7) 树高——T中层数最大顶点的层数

根树的画法：树根放上方，省去所有有向边上的箭头。

树叶——8片内点—— 6个分支点—— 7个高度—— 5

求带权为1、1、2、3、4、5的最优树。

W(T)=38

中序行遍法：b a (f d g) c e前序行遍法：a b (c (d f g) e)

后序行遍法：b ((f g d) e c) a

高等数学等价替换公式泰勒公式资料讲解

应用高等数学等价替换公式 1、无穷小量：设0）x （g lim ）x （f lim 0 x x x x ==→→ *1）若0） x （g ） x （f lim x x =→，f （x ）是g （x ）的高阶无穷小 *2）若∞=→） x （g ） x （f lim x x ，f （x ）是g （x ）的低阶无穷小 *3）若c ） x （g ） x （f lim x x =→，f （x ）是g （x ）的同阶无穷小 *4）若1） x （g ） x （f lim x x =→，f （x ）是g （x ）的等价无穷小 *5）若0） x （g ） x （f lim k x x 0 =→，f （x ）是g （x ）的 k 阶无穷小 2、等价替换：若x →x 0，f （x ）~ f 1（x ），g （x ）~ g 1（x ）则=→）x （g ） x （f lim x x ） x （g ）x （f lim 11x x 0→ 6、常用等价形式：当f （x ）→0时 *1）sinf （x ）~ f （x ） *2）arc sinf （x ）~ f （x ） *3）tanf （x ）~ f （x ）

*4）arc tanf （x ）~ f （x ） *5）In （1+f （x ））~ f （x ） *6）e f （x ）-1~ f （x ） *7）1-cosf （x ）~ 2 ） x （f 2 *8）（1+f （x ））α -1~ αf （x ）二、函数的连续： 1、间断点： *1）第一类间断点：f -（x 0）、f +（x 0）均存在的间断点 ⑴跳跃间断点： f -（x 0）≠f +（x 0） ⑵可去间断点： f -（x 0）=f +（x 0） *2）第二类间断点：f -（x 0）、f +（x 0）至少有一个不存在的间断点 ⑴无穷间断点： f -（x 0）、f +（x 0）中至少有一个为 ∞ ⑵振荡间断点： f -（x 0）、f +（x 0）中至少有一个振荡不存在三、导数： 1、定义：）x （f '= x △） x （f -）x △x （f lim 000 x △+→ 2、导数的常见形式： *1） 0 0x x 0x -x ） x （f -）x （f lim ）x （f 0 →=' *2） h ） x （f -）h x （f lim ）x （f 000 h +='→

离散数学(集合论)课后总结

第三章集合论基础 1、设A={a,{a},{a,b},{{a,b},c}}判断下面命题的真值。 ⑴{a}∈A T ⑵?({a}? A) F ⑶c∈A F ⑷{a}?{{a,b},c} F ⑸{{a}}?A T ⑹{a,b}∈{{a,b},c} T ⑺{{a,b}}?A T ⑻{a,b}?{{a,b},c} F ⑼{c}?{{a,b},c} T ⑽({c}?A)→(a∈Φ) T 2、证明空集是唯一的。（性质1：对于任何集合A，都有Φ?A。）证明：假设有两个空集Φ1 、Φ2 ，则因为Φ1是空集，则由性质1得Φ1 ?Φ2 。因为Φ2是空集，则由性质1得Φ2 ?Φ1 。所以Φ1=Φ2 。 3、设A={Φ},B=P(P(A)).问：(这道题要求知道幂集合的概念) a)是否Φ∈B?是否Φ?B? b)是否{Φ}∈B? 是否{Φ}?B? c)是否{{Φ}}∈B? 是否{{Φ}}?B? 解：设A={Φ}，B=P(P(A)) P(A)= {Φ,{Φ}} 在求P(P(A))时，一些同学对集合{Φ,{Φ}}难理解，实际上你就将{Φ,{Φ}}中的元素分别看成Φ=a ,{Φ}=b, 于是{Φ,{Φ}}={a,b} B=P(P(A))=P({a,b}) ={B0, B1 , B2 , B3 }={B00, B01,B10 ,B11}={Φ, {b}, {a}, {a,b}} 然后再将a,b代回即可B=P(P(A))=P({Φ,{Φ}})={Φ,{Φ} ,{{Φ}}, {Φ,{Φ}}} 以后熟悉后就可以直接写出。 a) Φ∈B Φ?B b) {Φ}∈B {Φ} ? B c) {{Φ}}∈B {{Φ}}?B a)、b)、c)中命题均为真。 4、证明A?B ? A∩B=A成立。证明：A∩B=A ??x(x∈A∩B ?x∈A) ??x((x∈A∩B → x∈A)∧(x∈A→ x∈A∩B)) ??x((x?A∩B∨x∈A)∧(x?A∨x∈A∩B)) ??x((?(x∈A∧x∈B)∨x∈A)∧(x?A∨(x∈A∧x∈B)) ??x(((x?A∨x?B)∨x∈A)∧(x?A∨(x∈A∧x∈B))) ??x(T∧(T∧( x?A∨x∈B))) ??x( x?A∨x∈B)??x(x∈A→x∈B)? A?B 5、(A-B)-C=(A-C)-(B-C) 证明：任取x∈(A-C)-(B-C) ?x∈(A-C)∧x?(B-C) ?(x∈A∧x?C)∧?(x∈B∧x?C) ?(x∈A∧x?C)∧(x?B∨x∈C) ?(x∈A∧x?C∧x?B)∨(x∈A∧x?C∧x∈C) ?x∈A∧x?C∧x?B?x∈A∧x?B∧x?C ?(x∈A∧x?B)∧x?C ?x∈A-B∧x?C?x∈(A-B)-C 所以(A-B)-C=(A-C)-(B-C)

离散数学集合论部分常考××题

离散数学常考题型梳理第2章关系与函数一、题型分析本章主要介绍关系的概念及运算、关系的性质与闭包运算、等价关系、相容关系和偏序关系三个重要关系、函数以及函数相关知识等内容。常涉及到的题型主要包括： 2-1关系的概念理解以及关系的并、交、补、差以及复合和逆关系等运算2-2关系自反和反自反、对称和反对称等性质的概念理解与判定；自反、对称和传递闭包运算。 2-3等价关系 2-4偏序关系和哈斯图 2-5 函数的概念和性质因此，在本章学习过程中希望大家要清楚地知道： 1．有序对和笛卡尔积（1）有序对：所谓有序对就是指一个有顺序的数组，如< x , y >，x , y的位置是确定的，且< a , b >< b , a >。（2）笛卡尔积：把集合A，B合成集合A×B，规定： {,|} ?=<>∈∈ 且 A B x y x A y B 由于有序对< x , y >中x，y 的位置是确定的，因此A×B 的记法也是确定的，不能写成B×A 。笛卡儿积的运算一般不满足交换律。 2．二元关系的概念和表示、几种特殊的关系和关系的运算（1）二元关系的概念：二元关系是一个有序对集合，设集合A，B ，从集合A 到B的二元关系 R∈ x ∈ < y =且 > } , x {B | y A 记作xRy。二元关系的定义域：A Ram? R ) (。 ) R Dom? (；二元关系的值域：B 二元关系R 是一个有序对组成的集合．因此，一个二元关系是一个集合，可以用集合形式表示；反过来说，一个集合未必是一个二元关系，仅当集合是由有序对元素组成的，才能当做二元关系。常用关系的表示法包括了集合表示法、列举法、描述法、关系矩阵法和关系图法。关系矩阵和关系图是有限集合上的二元关系的表示方法。

离散数学基本公式

、基本等值式 ⑴双重否定律 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)

(完整word)高等数学等价替换公式

无穷小极限的简单计算【教学目的】 1、理解无穷小与无穷大的概念； 2、掌握无穷小的性质与比较会用等价无穷小求极限； 3、不同类型的未定式的不同解法。【教学内容】 1、无穷小与无穷大； 2、无穷小的比较； 3、几个常用的等价无穷小等价无穷小替换； 4、求极限的方法。【重点难点】重点是掌握无穷小的性质与比较用等价无穷小求极限。难点是未定式的极限的求法。【教学设计】首先介绍无穷小和无穷大的概念和性质（30分钟），在理解无穷小与无穷大的概念和性质的基础上,让学生重点掌握用等价无穷小求极限的方法（20分钟）。最后归纳总结求极限的常用方法和技巧（25分钟），课堂练习（15分钟）。【授课内容】一、无穷小与无穷大 1.定义前面我们研究了∞→n 数列n x 的极限、∞→x （+∞→x 、+∞→x ）函数() x f 的极限、0x x →（+→0x x 、- →0x x ）函数()f x 的极限这七种趋近方式。下面我们用 →x ＊表示上述七种的某一种趋近方式，即＊{ } - + →→→-∞→+∞→∞→∞→∈00 x x x x x x x x x n 定义：当在给定的→x ＊下，()f x 以零为极限，则称()f x 是→x ＊下的无穷小，即()0lim =→x f x ＊。例如, ,0sin lim 0 =→x x Θ .0sin 时的无穷小是当函数→∴x x ,01lim =∞→x x Θ .1 时的无穷小是当函数∞→∴x x ,0)1(lim =-∞→n n n Θ .})1({时的无穷小是当数列∞→-∴n n n 【注意】不能把无穷小与很小的数混淆；零是可以作为无穷小的唯一的数，任何非零常量都不是无穷小。

离散数学之集合论

第二篇集合与关系集合论是现代各科数学的基础，它是德国数学家康托（Geog Cantor, 1845～1918）于1874年创立的，1876～1883年康托一系列有关集合论的文章，对任意元的集合进行了深入的探讨，提出了关于基数、序数和良序集等理论，奠定了集合论深厚的基础，19世纪90年代后逐渐为数学家们采用，成为分析数学、代数和几何的有力工具。随着集合论的发展，以及它与数学哲学密切联系所作的讨论，在1900年前后出现了各种悖论，使集合的发展一度陷入僵滞的局面。1904～1908年，策墨罗（Zermelo）列出了第一个集合论的公理系统，它的公理，使数学哲学中产生的一些矛盾基本上得到了统一，在此基础上以后就逐渐形成了公理化集合论和抽象集合论，使该学科成为在数学中发展最为迅速的一个分支。现在，集合论已经成为内容充实、实用广泛的一门学科，在近代数学中占据重要地位，它的观点已渗透到古典分析、泛函、概率、函数论、信息论、排队论等现代数学各个分支，正在影响着整个数学科学。集合论在计算机科学中也具有十分广泛的应用，计算机科学领域中的大多数基本概念和理论几乎均采用集合论的有关术语来描述和论证，成为计算机科学工作者必不可少的基础知识。集合论可作为数学学科的通用语言，一切必要的数据结构都可以利用集合这个原始数据结构而构造出来，计算机科学家或许也可以利用这种方法。本篇介绍集合论的基础知识，主要内容包括集合及其运算、性质、序偶、关系、映射、函数、基数等。第2-1章集合及其运算 §2-1-1 集合的概念及其表示一、集合的概念 “集合”是集合论中的一个原始的概念，因此它不能被精确地定义出来。一般地说，把具有某种共同性质的许多事物，汇集成一个整体，就形成一个集合。构成这个集合的每一个事物称为这个集合的一个成员（或一个元素），构成集合的这些成员可以是具体东西，也可以是抽象东西。例如：教室内的桌椅；图书馆的藏书；全国的高等学校；自然数的全体；程序设计语言C的基本字符的全体等均分别构成一个集合。通常用大写的英文字母表示集合的名称；用小写的英文字母表示元素。若元素a属于集合A记作

离散数学集合论部分测试题

离散数学集合论部分综合练习本课程综合练习共分3次，分别是集合论部分、图论部分、数理逻辑部分的综合练习，这3次综合练习基本上是按照考试的题型安排练习题目，目的是通过综合练习，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次是集合论部分的综合练习。一、单项选择题 1．若集合A={a，b}，B={ a，b，{ a，b }}，则（）． A．A?B，且A∈B B．A∈B，但A?B C．A?B，但A?B D．A?B，且A?B 2．若集合A＝{2，a，{ a }，4}，则下列表述正确的是( )． A．{a，{ a }}∈A B．{ a }?A C．{2}∈A D．?∈A 3．若集合A＝{ a，{a}，{1，2}}，则下列表述正确的是( )． A．{a，{a}}∈A B．{2}?A C．{a}?A D．?∈A 4．若集合A={a，b，{1，2 }}，B={1，2}，则（）． A．B? A，且B∈A B．B∈ A，但B?A C．B ? A，但B?A D．B? A，且B?A 5．设集合A = {1, a }，则P(A) = ( )． A．{{1}, {a}} B．{?,{1}, {a}} C．{?,{1}, {a}, {1, a }} D．{{1}, {a}, {1, a }} 6．若集合A的元素个数为10，则其幂集的元素个数为（）． A．1024 B．10 C．100 D．1 7．集合A={1, 2, 3, 4, 5, 6, 7, 8}上的关系R={|x+y=10且x, y∈A}，则R 的性质为（）． A．自反的B．对称的 C．传递且对称的D．反自反且传递的 8．设集合A = {1，2，3，4，5，6 }上的二元关系R ={?a , b∈A , 且a +b = 8}，则R具有的性质为（）． A．自反的B．对称的 C．对称和传递的D．反自反和传递的 9．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有（）个． A．0 B．2 C．1 D．3 10．设集合A={1 , 2 , 3 , 4}上的二元关系 R = {<1 , 1>，<2 , 2>，<2 , 3>，<4 , 4>}，