离散数学证明题

一、填空题1设集合A,B，其中A＝｛1，2，3｝, B= {1，2}, 则A — B＝________｛3｝____________；ρ（A) - ρ(B)＝_____{｛3｝,｛1，3},{2，3}，｛1,2,3｝｝_______ 。

2. 2. 设有限集合A, ｜A｜= n，则｜ρ(A×A）｜= __3.设集合A = ｛a, b}, B = ｛1, 2}，则从A到B的所有映射是__α1= {(a,1）, (b,1）｝, α2= {（a,2)，（b，2）}，α3= {(a,1），(b,2)｝，α4= {(a,2）, （b，1)}；_，其中双射的是____α3，α4。

_4。

已知命题公式G＝⌝（P→Q)∧R，则G的主析取范式是______（P∧⌝Q∧R）__________________.5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为___12_______，分枝点数为_______3_________.6设A、B为两个集合, A= {1，2,4}， B = ｛3,4}，则从A⋂B＝_______｛4}__________________; A⋃B＝_____｛1, 2, 3, 4｝____________；A－B＝____{1, 2}_________________ .3.7。

设R是集合A上的等价关系，则R所具有的关系的三个特性是__自反性;对称性；传递性_______________________________.8. 设命题公式G＝⌝（P→（Q∧R）)，则使公式G为真的解释有____（1, 0, 0)________，___ _（1，0, 1)_________，____（1, 1，0）______________________。

9. 设集合A＝{1，2,3，4}, A上的关系R1 = ｛(1,4）,（2，3)，(3，2）｝，R1 = ｛（2，1)，（3,2）,（4,3)}，则R1•R2 = _｛(1，3）,（2，2）,（3,1)}__________，R2•R1=___{(2,4）,(3,3）,(4,2)}_____ __, R12 =_____｛（2,2)，(3,3）}__________________。

一、证明下列各题1、 （10分）证明蕴涵式：()P P Q Q ∧→⇒2、（10分）证明：,1111f g f g -⇒-I 为函数为函数。

5、 3、（10分）给定代数结构,N ⨯和{}0,1,⨯，其中N 是自然数集合，⨯是数的乘法。

设{}:0,1f N →，定义为：12,,()0k n n k N f n ⎧=∈=⎨⎩否则试证}01N ⨯≅⨯，，，。

4、（10分）给定代数结构,R *，其中R 是实数集合，对R 中任意元a 和b ，*定义如下：a b a b a b *=++⨯ 试证明：,R *是独异点。

二、求下列各题的解：1、试求下列公式的主析取范式和主合取范式（15分）：()()P Q P Q ⌝∨⌝→⌝€2、（15分）{}010*********R =设，，，，，，，，，，，，试求（1）、R R *，（2）、{}1R ↑，（3）、{}11R -↑，（4）、{}1R ⎡⎤⎣⎦，（5）、{}11R -⎡⎤⎣⎦3、（15分给定无向图,G V E =，如图，试求： F E DCA B（1） 从A 到D 的所有基本链； （2） 从A 到D 的所有简单链；（3） 长度分别是最小和最大的简单圈； （4） 长度分别是最小和最大的基本圈； （5） 从A 到D 的距离。

4、（15分）给定二部图12,,G E V =，如图 9v 8v 7v 6v 1V1v 2v 3v 4v 5v 2V 试求1V 到2V 的最大匹配一、证明下列各题1、 （10分）证明蕴涵式：()P Q P P Q →⇒→∧2、（10分）证明：()()()A B C A B A C ⨯-=⨯-⨯3、（10分）给定群,G ，则,G 为Abel 群⇔222()()(,())∀∀∈→=a b a b G a b a b4、（10分）给定代数结构,S *，其中S 中元为实数有序对，*定义为 ,,,2a b c d a c b d bd *=+++，试证,S *是可交换独异点。

《离散数学》试题及答案 2《离散数学》试题及答案2一、填空题1设子集a,b，其中a＝{1,2,3},b={1,2},则a-b＝____________________;?(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所具备的关系的三个特性就是______________________,________________________,______________________________ _.8.设命题公式g＝?(p?(q?r))，则使公式g为真的解释有__________________________，_____________________________,__________________________.9.设子集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=________________________.(a)-10.设有限集a,b，|a|=m,|b|=n,则||?(a?b)|=_____________________________.11设a,b,r是三个集合，其中r是实数集，a={x|-1≤x≤1,x?r},b={x|0≤x<2,x?r},则a-b=__________________________,b-a=__________________________,a∩b=__________________________,.13.设子集a＝{2,3,4,5,6}，r就是a上的相乘，则r以子集形式(列出法)记作__________________________________________________________________.14.设一阶逻辑公式g=?xp(x)??xq(x)，则g的前束范式是_______________________________.15.设g就是具备8个顶点的树，则g中减少_________条边就可以把g变为全然图。

离散数学试题及答案一、选择题1. 设A、B、C为三个集合，下列哪个式子是成立的？A) \(A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\)B) \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\)C) \(A \cup (B \cup C) = (A \cup B) \cup (A \cup C)\)答案：B2. 对于一个有n个元素的集合S，S的幂集中包含多少个元素？A) \(n\)B) \(2^n\)C) \(2 \times n\)答案：B二、判断题1. 对于两个关系R和S，若S是自反的，则R ∩ S也是自反的。

答案：错误2. 若一个关系R是反对称的，则R一定是反自反的。

答案：正确三、填空题1. 有一个集合A，其中包含元素1、2、3、4和5，求集合A的幂集的大小。

答案：322. 设a和b是实数，若a \(\neq\) b，则a和b之间的关系是\(\__\_\)关系。

答案：不等四、解答题1. 证明：如果关系R是自反且传递的，则R一定是反自反的。

解答：假设关系R是自反的且传递的，即对于集合A中的任意元素x，都有(x, x) ∈ R，并且当(x, y) ∈ R和(y, z) ∈ R时，(x, z) ∈ R。

反证法：假设R不是反自反的，即存在一个元素a∈A，使得(a, a) ∉ R。

由于R是自反的，所以(a, a) ∈ R，与假设矛盾。

因此，R一定是反自反的。

答案完整证明了该结论。

2. 已知集合A={1, 2, 3}，集合B={2, 3, 4}，求集合A和B的笛卡尔积。

解答：集合A和B的笛卡尔积定义为{(a, b) | a∈A，b∈B}。

所以，集合A和B的笛卡尔积为{(1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)}。

离散数学证明题离散数学证明题:链为分配格证明设a,b均是链A的元素，因为链中任意两个元素均可比较，即有a≤b或a≤b，如果a ≤b，则a,b的最大下界是a,最小上界是b，如果b≤a，则a,b的最大下界是b,最小上界是a，故链一定是格,下面证明分配律成立即可,对A中任意元素a,b,c分下面两种情况讨论:⑴b≤a或c≤a⑵a≤b且a≤c如果是第⑴种情况,则a∪(b∩c)=a=(a∪b)∩(a∪c)如果是第⑵种情况,则a∪(b∩c)=b∩c=(a∪b)∩(a∪c)无论那种情况分配律均成立,故A是分配格.一.线性插值(一次插值)已知函数f(x)在区间[xk ,xk+1 ]的端点上的函数值yk =f(xk ), yk+1 = f(xk+1 ),求一个一次函数y=P1 (x)使得yk =f(xk ),yk+1 =f(xk+1 ), 其几何意义是已知平面上两点(xk ,yk ),(xk+1 ,yk+1 ),求一条直线过该已知两点。

1. 插值函数和插值基函数由直线的点斜式公式可知：把此式按照 yk 和yk+1 写成两项:记并称它们为一次插值基函数。

该基函数的特点如下表：从而P1 (x) = yk lk (x) + yk+1 lk+1 (x)此形式称之为拉格朗日型插值多项式。

其中, 插值基函数与yk 、yk+1 无关，而由插值结点xk 、xk+1 所决定。

一次插值多项式是插值基函数的线性组合, 相应的组合系数是该点的函数值yk 、yk+1 .例1: 已知lg10=1,lg20=1.3010, 利用插值一次多项式求lg12的近似值。

解: f(x)=lgx,f(10)=1,f(20)=1.3010, 设x0 =10 ,x1 =20 ,y0 =1 ,y1 =1.3010则插值基函数为：于是, 拉格朗日型一次插值多项式为:故 :即lg12 由lg10 和lg20 两个值的线性插值得到,且具有两位有效数字(精确值lg12=1.0792).二.二次插值多项式已知函数y=f(x)在点xk-1 ,xk ,xk+1 上的函数值yk-1 =f(xk-1 ),yk =f(xk ), yk+1 =f(xk+1 ), 求一个次数不超过二次的多项式P2 (x), 使其满足,P2 (xk-1 )=yk-1 , P2 (xk )=yk , P2 (xk+1 )=yk+1 .其几何意义为:已知平面上的三个点(xk-1 ,yk-1 ),(xk ,yk ),(xk+1 ,yk+1 ),求一个二次抛物线, 使得该抛物线经过这三点。

离散数学考试题(后附详细答案)一、命题符号化（共6小题，每小题3分，共计18分）1.用命题逻辑把下列命题符号化a)假如上午不下雨，我去看电影，否则就在家里读书或看报。

b)我今天进城，除非下雨。

c)仅当你走，我将留下。

2.用谓词逻辑把下列命题符号化a)有些实数不是有理数b)对于所有非零实数x，总存在y使得xy=1。

c) f 是从A到B的函数当且仅当对于每个a∈A存在唯一的b∈B，使得f(a)=b.二、简答题（共6道题，共32分）1.求命题公式(P→(Q→R)) (R→(Q→P))的主析取范式、主合取范式，并写出所有成真赋值。

（5分）2.设个体域为{1,2,3}，求下列命题的真值（4分）a)x y(x+y=4)b)y x (x+y=4)3.求x(F(x)→G(x))→(xF(x)→xG(x))的前束范式。

（4分）4.判断下面命题的真假，并说明原因。

（每小题2分，共4分）a)（A B）－C=(A-B) (A-C)b)若f是从集合A到集合B的入射函数，则|A|≤|B|5.设A是有穷集，|A|=5，问（每小题2分，共4分）a)A上有多少种不同的等价关系？b)从A到A的不同双射函数有多少个？6.设有偏序集<A,≤>，其哈斯图如图1，求子集B={b,d,e}的最小元，最大元、极大元、极小元、上界集合、下界集合、上确界、下确界，(5分)f g图17.已知有限集S={a1,a2,…,a n},N为自然数集合，R为实数集合，求下列集合的基数S;P(S);N,N n;P(N);R,R×R,{o,1}N（写出即可）(6分)三、证明题（共3小题，共计40分）1.使用构造性证明，证明下面推理的有效性。

（每小题5分，共10分）a)A→(B∧C),(E→ F)→ C, B→(A∧ S) B→Eb)x(P(x)→ Q(x)), x(Q(x)∨R(x))，x R(x) x P(x)2.设R1是A上的等价关系，R2是B上的等价关系，A≠ 且B≠ ，关系R满足：<<x1,y1>,<x2,y2>>∈R，当且仅当< x1, x2>∈R1且<y1,y2>∈R2。

(2)（高概）证明若S为集合X上的二元关系：a)S是传递的，当且仅当(S∘S)⊆S证明：证明：必要性使得任取序偶<a,b>∈S∘S,则存在c∈X,使得<a,c>∈S∧<c,b>∈S,因为S传递，故传递，故<a,b>∈S,即S∘S⊆S.充分性对任意序偶<a,b>∈S∧<b,c>∈S,有<a,c>∈S∘S,<a,c>∈S,S S传递. 因为S∘S⊆S,故有<a,c>∈S,(3)（中难）（中难） 设S为X上的关系，证明若S是自反的和传递的，则S∘S=S。

⊆S; ; 证明: S传递ÛS∘S⊆S以下只需证明S⊆S∘S. "<x,y>ÎS, 因为S自反，有<x,x>ÎS, 由关系合成运算的定义，有<x,y>ÎS∘S，即S⊆S∘S。

本命题的逆不真，举反例如下：仅传递而不自反。

空关系j满足j∘j=j, 但j仅传递而不自反。

(6)（中概低难）设R为集合X上的二元关系，R在X上反传递⇔∀x∀y∀z(x∈X∧y∈X∧z∈X∧xRy∧yRz→x Rz) 当且仅当(R∘R)∩R=φ。

证明：证明：必要性必要性使得任取序偶<a,b>∈R∘R,则存在c∈X,使得<a,c>∈R∧<c,b>∈R,因为R反传递，故反传递，故<a,b>∉R,即R∘R中任何序偶都不属于R，因此(R∘R)∩R=φ. 充分性充分性对R 中任意序偶aRc∧cRb,有<a,b>∈R∘R, 因为(R (R∘R)∩R=φ,∘R)∩R=φ,故<a,b>∉R ， 因此，R 反传递. (8)(中概中上难度)设R,S,T 为集合X 上的关系，证明上的关系，证明R∘(S∪T)=R∘S∪R∘T证明：a)任取序偶<a,b>∈R∘(S∪T), 则存在c∈X,使得使得<a,c>∈R 且<c,b>∈S∪T, 若<c,b>∈S,则<a,b>∈R∘S, 若<c,b>∈T,则<a,b>∈R∘T,故<a,b>∈R∘S∪R∘T,即R∘(S∪T)⊆R∘S∪R∘T. b)任取序偶<a,b>∈R∘S∪R∘T,则有<a,b>∈R∘S 或<a,b>∈R∘T, 若<a,b>∈R∘S,则存在c∈X,使得使得 <a,c>∈R 且<c,b>∈S,若<a,b>∈R∘T,则存在d∈X,使得使得 <a,d>∈R 且<d,b>∈T,总之，总之，存在y∈X,使得<y,b>∈S∪T 且<a,y>∈R, 故<a,b>∈R∘(S∪T),即R∘(S∪T)⊇R∘S∪R∘T R∘(S∪T)⊇R∘S∪R∘T. . 综合a)和b)，有R∘(S∪T)=R∘S∪R∘T. 3-8 （2）算闭包。

《离散数学》试题含答案⼀、填空题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所具有的关系的三个特性是______________________,________________________, _______________________________.8. 设命题公式G＝?(P→(Q∧R))，则使公式G为真的解释有__________________________，_____________________________, __________________________.9. 设集合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=________________________.10. 设有限集A, B，|A| = m, |B| = n, 则| |ρ(A?B)| = _____________________________.11设A,B,R是三个集合，其中R是实数集，A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B =__________________________ , B-A = __________________________ ,A∩B = __________________________ , .13.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除，则R以集合形式(列举法)记为__________________________________________________________________.14. 设⼀阶逻辑公式G = ?xP(x)→?xQ(x)，则G的前束范式是__________________________ _____.15.设G是具有8个顶点的树，则G中增加_________条边才能把G变成完全图。

离散数学一、填空题(本大题共48分，共16小题，每小题3分)1.--公式为之充分必要条件是其合取范式之每一合取项中均必同时包含一命题变元及其否定2.无向图G具有是生成树，当且仅当的，若G为(n,m)连通图，要确定G的一棵生成树必删掉G的条边。

3.一个无向图的欧拉回路要求经过图中一次且仅一次，汉密顿图要求经过图中一次且仅一次。

4.设P：我生病，Q：我去学校(1)命题“我虽然生病但我仍去学校”符号化为o (2)命题“只有生病的时候，我才不去学校”符号化为o (3)命题"如果我生病，那么我不去学校”符号化为o5.设有33盏灯，拟公用一个电源，则至少需要5个插头的接线板数6.若HlAH2A-AHn是 ,则称Hl, H2, -Hn是相容的，若HlAH2A-AHn是 ,则称H1.H2, -Hn是不相容的7.设f,g,h 是N 到N上的函数(N 为自然数集合),f(n)=n+l;g(n)=2n;h(n)=0；贝lj(fdg)oh=8.K5的点连通度为 ,边连通度为o9.A={1, 2, 3, 4, 5, 6, 8, 10, 24, 36}, R 是A 上的整除关系。

子B={1, 2, 3, 4},那么B的上界是； B的下界是；：6的上确界是; B的下确界为10.命题公式P-*QAR的对偶式为11.设入={1, {2}, <t>},则A的幕集有元素个。

12.设A={0, 1,2, 3}, B={4,6, 7}, C={8, 9, 12, 14}, R1 是由A 到B 的关系,R2 是由B到C原关系，分别定义为Rl={<2, 6>, <3, 4>, <0, 7>} ;R2={<4, 8>, <4, 12>, <6, 12>,〈7, 14〉},则复合关系RloR2 为：13.设A= {<i)}, B={<t>, (<!>}},贝i]P(A) nP(B)= 。

离散数学证明题离散数学证明题离散数学证明题离散数学证明题:链为分配格证明设a,b均是链A的元素，因为链中任意两个元素均可比较，即有a≤b或a≤b，如果a≤b，则a,b的最大下界是a,最小上界是b，如果b≤a，则a,b的最大下界是b,最小上界是a，故链一定是格,下面证明分配律成立即可,对A中任意元素a,b,分下面两种情况讨论:⑴b≤a或≤a⑵a≤b且a≤如果是第⑴种情况,则a∪(b∩)=a=(a∪b)∩(a∪)如果是第⑵种情况,则a∪(b∩)=b∩=(a∪b)∩(a∪)无论那种情况分配律均成立,故A是分配格.一.线性插值(一插值)已知函数f(x)在区间xk ,xk+1 ]的端点上的函数值yk =f(xk ), yk+1 = f(xk+1 ),求一个一函数y=P1 (x)使得yk =f(xk ),yk+1 =f(xk+1 ), 其几何意义是已知平面上两点(xk ,yk ),(xk+1 ,yk+1 ),求一条直线过该已知两点。

1. 插值函数和插值基函数由直线的点斜式公式可知：把此式按照 yk 和yk+1 写成两项:记并称它们为一插值基函数。

该基函数的特点如下表：从而P1 (x) = yk lk (x) + yk+1 lk+1 (x)此形式称之为拉格朗日型插值多项式。

其中, 插值基函数与yk 、yk+1 无关，而由插值结点xk 、xk+1 所决定。

一插值多项式是插值基函数的线性组合, 相应的组合系数是该点的函数值yk 、yk+1 .例1: 已知lg10=1,lg=1.3010, 利用插值一多项式求lg12的近似值。

解: f(x)=lgx,f(10)=1,f()=1.3010, 设x0 =10 ,x1 = ,y0 =1 ,y1 =1.3010则插值基函数为：于是, 拉格朗日型一插值多项式为:故 :即lg12 由lg10 和lg 两个值的线性插值得到,且具有两位有效数字(精确值lg12=1.0792).二.二插值多项式已知函数y=f(x)在点xk-1 ,xk ,xk+1 上的函数值yk-1 =f(xk-1 ),yk =f(xk ), yk+1 =f(xk+1 ), 求一个数不超过二的多项式P2 (x), 使其满足,P2 (xk-1 )=yk-1 , P2 (xk )=yk , P2 (xk+1 )=yk+1 .其几何意义为:已知平面上的三个点(xk-1 ,yk-1 ),(xk ,yk ),(xk+1 ,yk+1 ),求一个二抛物线, 使得该抛物线经过这三点。