文档库

最新最全的文档下载
当前位置:文档库 > 离散数学复习提纲

离散数学复习提纲

离散数学复习题

1、求一个公式的主析取或主合取范式的方法,有______________法和

______________法。

2、给定谓词合式公式A,其中一部分公式形式为(x?)B(x)或(?x)B(x),则量词

?,?后面所跟的x称为______________,而称B为相应量词的______________。

3、设X,U,V,Y都是实数集,f1:X→U,且fl(x)→ex; f2:U→V,且f2(u)

=u (1+u);f3:V→Y,且f3(v)=cosv。那么f3 f2 f1的定义域是______________,而复合函数(f3 f2 f1)(x)= ______________。

4、集合X={a,b,c,d}上二元关系R={

d>,},则R的自反闭包r(R)= ______________,对称闭包s(R)=

______________。

5、已知G=<{l,-1,i,-i},·>(其中i=1-,是数的乘法)是群,则-l的阶

是______________;i的阶是______________。

6、对代数系统,其中*是S上的二元运算,若a,b∈S,且对任意的x

∈S,都有a*x=x*a=x,b*x=x*b=b,则称a为运算“*”的______________,称b为运算“*”的______________。

计算题1、若集合A={a,{b,c}}的幂集为P(A),集合B={ O/,{ O/}}的幂集为P(B),

求P(A)∩P(B)。2、构造命题公式(p→(q∧r))→┐p的真值表。

证明题1、设M是偶数集,+和·是数的加、乘运算,证明是一个环。

2、设R是集合X上的二元关系,证明R是X上传递关系当且仅当R R?R。

应用题有6个村庄V i,i=l,2,…,6欲修建道路使村村可通。现已有修建方案如下带权无向图所示,其中边表示道路,边上的数字表示修建该道路所需费用,问应选择修建哪些道路可使得任二个村庄之间是可通的且总的修建费用最低?要求写出求解过程,画出符合要求的最低费用的道路网络图并计算其费用。

1、设集合A,B,其中A={1,2,3}, B= {1,2}, 则A - B=____________________;

ρ(A) - ρ(B)= __________________________ .

2. 设有限集合A, |A| = n, 则 |ρ(A×A)| = __________________________.

3. 设集合 A = {a, b}, B = {1, 2}, 则从A到B的所有映射是

__________________________ _____________, 其中双射的是__________________________.

4. 已知命题公式G=?(P→Q)∧R,则G的主析取范式是

_______________________________

5.设G是完全二叉树,G有7个点,其中4个叶点,则G的总度数为__________,

分枝点数为________________.

6 设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B=

_________________________; A?B=_________________________;A-B = _____________________ .

7. 设R是集合A上的等价关系,则R所具有的关系的三个特性是

______________________, ________________________, _______________________________.

三、计算题题(每小题10分,共20分)

1、设集合A={1, 2, 3, 4, 6, 8, 9, 12},R为整除关系。

(1)画出半序集(A,R)的哈斯图;

(2)写出A的子集B = {3,6,9,12}的上界,下界,最小上界,最大下界;

(3)写出A的最大元,最小元,极大元,极小元。

2.设集合A={1, 2, 3, 4},A上的关系R={(x,y) | x, y∈A 且x ≥ y}, 求

(1)画出R的关系图;

(2)写出R的关系矩阵.

证明题1、利用形式演绎法证明:{P→Q, R→S, P∨R}蕴涵Q∨S。

2、设A,B为任意集合,证明:(A-B)-C = A-(B∪C).

应用题有6个村庄V i,i=l,2,…,6欲修建道路使村村可通。现已有修建方案如下带权无向图所示,其中边表示道路,边上的数字表示修建该道路所需费用,问应选择修建哪些道路可使得任二个村庄之间是可通的且总的修建费用最低?要求写出求解过程,画出符合要求的最低费用的道路网络图并计算其费用。

1、设命题公式G=?(P→(Q∧R)),则使公式G为真的解释有

__________________________,_____________________________,

__________________________.

2、设集合A={1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 则 R1?R2 = ________________________,R2?R1

=____________________________, R12 =________________________.

3、设有限集A, B,|A| = m, |B| = n, 则| |ρ(A?B)| =

_____________________________.

4、设A,B,R是三个集合,其中R是实数集,A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = __________________________ , B-A =

__________________________ ,

A∩B = __________________________ , .

5、设集合A={2, 3, 4, 5, 6},R是A上的整除,则R以集合形式(列举法)记为

___________ _______________________________________________________. 6、设一阶逻辑公式G = ?xP(x)→?xQ(x),则G的前束范式是

__________________________ _____.

7、设G是具有8个顶点的树,则G中增加_________条边才能把G变成完全图。

8、设谓词的定义域为{a, b},将表达式?xR(x)→?xS(x)中量词消除,写成与之对应的命题公式是

_____________________________________________________________________ ____.

计算题1、设R 是实数集合,σ,τ,?是R 上的三个映射,σ(x) = x+3, τ(x) = 2x, ?(x)

= x/4,试求复合映射σ?τ,σ?σ, σ??, ??τ,σ???τ.

2、设集合A ={1, 2, 4, 6, 8, 12},R 为A 上整除关系。

(3) 画出半序集(A,R)的哈斯图;

(4) 写出A 的最大元,最小元,极大元,极小元;

(5) 写出A 的子集B = {4, 6, 8, 12}的上界,下界,最小上界,最大下界. 证明题1、利用形式演绎法证明:{?A ∨B, ?C →?B, C →D}蕴涵A →D 。

2、A, B 为两个任意集合,求证:A -(A ∩B) = (A ∪B)-B .

应用题 设有n 个村庄要修路,(1)若要使所有村庄之间都有通路,问需在两村之间至少修几条路?(2)若要使任意两村庄之间有一条直接的路,则至少修几个路?(3)若修一条连接所有村庄的环路,问有多少种修路方案?

1. 真值表 等值演算

2. 指导变元或作用变元 作用域

3. X c o s ((1)x x e e +

4.

{a a b b c cd d d e e }R ?<><><><><>,,,,,,,,{{b a c a d a c b d b d e }}R ?<><><><><><>,,,,,,,,,,,

5. 2 4

6. 幺元 零元

计算题 1.解 :因为(){,{},P A a b c a b c =?,(){,{},{{}}{,{}}}P B =?????

所以()(){}P A P B ?=?

2解:

离散数学复习提纲

四、证明题

1、12{2},2,2M n n Z n n M =∈?∈设

1212222()n n n n M

+=+∈ , 1212222(2)n n n n M *=*∈

加法交换律成立

020M M =*∈为的幺元

2-2n n M ∈的逆元为

乘法结合律成立

乘法对加法的左右分配律成立

所以是一个环。

2、必要性:若R 是X 上传递关系,则对任意的

,,,,,,,,x y y x R R t x t t y R x y R <><>∈??<><>∈?<>∈ 所以 R R R ? 充分性:若R R R ? ,则

,,x y z X ?∈,,,,x y R y z R x z R R x z R <>∈∧<>∈?<>∈?<>∈ 所以R 是X 上传递关系。

1. {3}; {{3},{1,3},{2,3},{1,2,3}}.

2.22n .

3. α1= {(a ,1), (b ,1)}, α2= {(a ,2), (b ,2)},α3= {(a ,1), (b ,2)}, α4= {(a ,2), (b ,1)}; α3, α

4. 4.(P ∧?Q ∧R).

5. 12,

3. 6. {4}, {1, 2, 3, 4}, {1, 2}. 7.自反性;对称性;传递性.

1.

(1)

无上界,也无最小上界。下界1, 3; 最大下(2) B

界是 3.

(3) A 无最大元,最小元是1,极大元8, 12, 90+; 极小元是1.

2.R = {(1,1),(2,1),(2,2),(3,1),(3,2),(3,3),(4,1),(4,2),(4,3),(4,4)}.

(1)

(2)100011001

1101111R M ??????=??????

四、证明题

1. 证明:{P →Q , R →S , P ∨R }蕴涵Q ∨S

(1) P ∨R P

(2) ?R →P

Q(1) (3) P →Q P

124836129 1 2 3 4

(4) ?R→Q Q(2)(3)

(5) ?Q→R Q(4)

(6) R→S P

(7) ?Q→S Q(5)(6)

(8) Q∨S Q(7)

2. 证明:(A-B)-C = (A∩~B)∩~C = A∩(~B∩~C)= A∩~(B∪C)= A-(B∪C)

二、. 1. (1, 0, 0), (1, 0, 1), (1, 1, 0). 2.{(1,3),(2,2),(3,1)}; {(2,4),(3,3),(4,2)};

{(2,2),(3,3)}. 3.2m?n. 4. {x | -1≤x < 0, x∈R}; {x | 1 < x < 2, x∈R};

{x | 0≤x≤1, x∈R}.

5. {(2, 2),(2, 4),(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(6, 6)}.

6. ?x(?P(x)∨Q(x)).

7.

21.

8(R(a)∧R(b))→(S(a)∨S(b)).

三、1. (1)σ?τ=σ(τ(x))=τ(x)+3=2x+3=2x+3.

(2)σ?σ=σ(σ(x))=σ(x)+3=(x+3)+3=x+6,

(3)σ??=σ(?(x))=?(x)+3=x/4+3,

(4)??τ=?(τ(x))=τ(x)/4=2x/4 = x/2,

(5)σ???τ=σ?(??τ)=??τ+3=2x/4+3=x/2+3.

2. (1)

2

4

16

812

(2) 无最大元,最小元1,极大元8, 12; 极小元是1.

(3) B无上界,无最小上界。下界1, 2; 最大下界2.

四、证明题

1. 证明:{?A∨B, ?C→?B, C→D}蕴涵A→D

(1) A D(附加)

(2) ?A∨B P

(3) B Q(1)(2)

(4) ?C→?B P

(5) B→C Q(4)

(6) C Q(3)(5)

(7) C→D P

(8) D Q(6)(7)

(9) A→D D(1)(8)

所以{?A∨B, ?C→?B, C→D}蕴涵A→D.

2.证明:A-(A∩B) = A∩~(A∩B)=A∩(~A∪~B)

=(A∩~A)∪(A∩~B)=?∪(A∩~B)=(A∩~B)=A-B 而(A∪B)-B= (A∪B)∩~B= (A∩~B)∪(B∩~B)= (A∩~B)∪?= A-B 所以:A-(A∩B) = (A∪B)-B.