中国科学院计算机技术研究所1998年硕士生入学试题离散数学

计算机离散数学习题答案计算机离散数学习题答案计算机离散数学是计算机科学中的一门重要学科，它研究的是离散的数学结构和离散的数学对象。

在学习计算机离散数学的过程中，我们经常会遇到各种各样的习题，而这些习题的答案往往是我们学习的关键。

下面，我将为大家提供一些计算机离散数学习题的答案，希望对大家的学习有所帮助。

一、命题逻辑命题逻辑是计算机离散数学中的基础内容，它研究的是命题之间的逻辑关系。

在命题逻辑中，我们经常会遇到一些关于命题的合取、析取、条件、双条件等运算。

下面是一些常见的命题逻辑习题及其答案：1. 给定命题p: "我喜欢数学"，q: "我喜欢计算机"，r: "我喜欢编程"，判断以下命题的真假：a) p ∧ qb) p ∨ qc) p → rd) p ↔ q答案：a) 真b) 真c) 真d) 假2. 给定命题p: "我喜欢音乐"，q: "我喜欢运动"，r: "我喜欢读书"，判断以下命题的真假：a) p ∧ (q ∨ r)b) (p ∧ q) ∨ rc) p → (q ∧ r)d) (p → q) ∧ (p → r)答案：a) 假b) 真c) 假d) 真二、集合论集合论是计算机离散数学中另一个重要的内容，它研究的是集合之间的关系和运算。

在集合论中，我们经常会遇到一些关于集合的并、交、差、补等运算。

下面是一些常见的集合论习题及其答案：1. 设A = {1, 2, 3, 4}，B = {3, 4, 5, 6}，C = {2, 4, 6, 8}，求以下集合的并、交、差和补：a) A ∪ Bb) A ∩ Cc) B \ Cd) C'答案：a) A ∪ B = {1, 2, 3, 4, 5, 6}b) A ∩ C = {2, 4}c) B \ C = {3, 5}d) C' = {1, 3, 5, 7, 9, ...}2. 设A = {a, b, c, d}，B = {c, d, e, f}，C = {a, d, f, g}，求以下集合的并、交、差和补：a) A ∪ Bb) A ∩ Cc) B \ Cd) C'答案：a) A ∪ B = {a, b, c, d, e, f}b) A ∩ C = {a, d}c) B \ C = {c, e}d) C' = {b, c, e, ...}三、关系与函数关系与函数是计算机离散数学中的另一个重要内容，它研究的是元素之间的关系和映射。

离散数学中科院计算机技术研究所1999年硕⼠研究⽣⼊学考试试题离散数学⼀.(8分)求与公式(x2 or not x1)->x3 逻辑等值的主合取范式和主析取范式.⼆.(8分)判断下列各公式是: 1.永真式 2.永假式 3.其它(1) (p->(q->r))->(q->(p->r))(2) (not p or q)<->(p and(p and q))(3) (not p or q)and not(q or not r)and not(r or not p or not q)(4) (q and p)->(p or q)三.(9分)问any x exist y P(x,y)->exist y any x P(x,y)是否谓词演算的有效式?证明你的结论.四.(9分)将下列推理符号化并给出形式证明:鸟会飞,猴⼦不会飞;所以,猴⼦不是鸟.五.(12分)令X={x1,x2,...,xm},Y={y1,y2,...,yn},问:(1) 有多少不同的由X到Y的关系?(2) 有多少不同的由X到Y的影射?(3) 有多少不同的由X到Y的单射，双射?六.(8分)设e是奇数阶交换群G的单元位,试证:G的所有元素之积为e.七.(15分) ①是个群,H,K 是其⼦群,在G上定义⼆元关系R:any a,b in G,aRb <=>存在 h,k in k,使得 b=h*a*k,证明:R是G上的等价关系.②在①中,若|H|=m,|K|=n,|G|=mn,m与n互素,且R的某个等价类在G的乘法运算下构成G的⼀个⼦群,则R=G*G.⼋.(8分)把平⾯分成β个区域,每两个区域都相邻,问β最⼤为⼏?九.(11分)设G为⾮平凡有向图,V(G)为G的结点集合,若对V(G)的任意⾮空⼦集S,G中起始结点在S中,终⽌结点在V(G) S中的有向边都⾄少有k条,则称G是k边连通的.证明:⾮平凡有向图G是强连通的充要条件是他是1边连通的.⼗.(12分)设G是⼀⽆向加权图且各边的权不相等,V,E分别是G的结点集合和边的集合, (V1,V2)是V 的划分,即V1 or V2 = V, V1 and V2=null,且 V1!=null,V2!=null,则V1与V2间的最短边⼀定在G的最⼩⽣成树上.中科院计算机技术研究所1999年硕⼠研究⽣⼊学考试试题离散数学参考答案⼀.主合取范式: (not x1 or not x2 or x3)and(x1 or not x2 or x3) and (x1 or x2 or x3)主析取范式: (x1 and not x2 and not x3)or(x1 and x2 and x3)or(x1 and not x2 andx3) or (not x1 and x2 and x3)or (not x1 and not x2 and x3)⼆.(1) 1(2) 3(3) 2(4) 1三.不是.取⼀特定解释域 I 如下.[P(x,y)] I ="x<=y",论域D=N(⾃然数集)则显然有[any x exist y P(x,y)] I =t[exist y any x P(x,y)] I =f故给定公式在 I 中为假,因此它不是谓词公式的有效式.四.(1) any x(bird(x)->fly((x)) //前提1(2) any x(monkey(x)->not fly(x)) //前提2(3) bird(a)->fly(a) //(1)脱帽(4) monkey(a)->not fly(a) //(2)脱帽(5) not fly(a)->not bird(a) //逆否律(3)(6) monkey(a)->not bird(a) //传递律(4)(5)(7) any x(monkey(x)->not bird(x)) //(6)戴帽五.解:(1) ⼀个x到y的关系对应于x*y的⼀个⼦集.因此,不同的x到y的关系数=|φ(x*y)|=2^(mn)(2)不同的由x到y的映射个数=|{f|f: x->y}|=|{(f(x1),f(x2),...,f(xm) )|,f(xi) in y, 1==Π(i=1 to m) |{f(xk)|f(xk) in y }|=n^m.(3) 若m!=n,则双射的个数为0若m=n,则双射的个数为m!若m>n,则单射个数0若mm!种不同的双射,共有单射Cn(m)*m!种.六.证明:由于G为奇数阶交换群,由拉格朗⽇定理,其中不可能有2阶元,因此any a in G(a!=e),a!=a^(-1),即a与a^(-1)是两个不同元素(a!=e),因此G的所有元素之积=e*a1*a1^(-1)*a2*a2^(-1)*...*am*am^(-1)=ea1 in G-{e},a2 in G-{a1,a^(-1),e},...,am in G-{e,a1,a1^(-1),a2,a2^(-1),...,a(m-1),a(m-1)^(-1)|G|=2m+1七.(1)1. ⾃反性:any a in G 有:a=e*a*e.(e 为单位元) ,⽽H,k为 G的⼦群,从⽽ e in H ,e in k so: aRa.2. 对称性:若aRb,=>存在 h in H ,k in K 使 b=h*a*k=>a=h^(-1)*k^(-1),由于 H,K为G的⼦群=>h^(-1) in H ,k^(-1) in K,所以 bRa.3.传递性:若aRb,bRc=>存在 h1,h2 in H ,k1,k2 in K ,使b=h1*a*k1,c=h2*b*k2,由于H,K为G的⼦群,得h2*h1 in H,k1* k2 in K,使c=(h2*h1)*a*(k1*k2),所以aRc,因此 R 是等价关系.(2)设是的⼦群的那个的等价关系为[a]R={x|x in G and aRx}={x|x in G 且存在h in H,k in K ,使 x=h*a*k}={h*a*k| h in H,k inK} 由于该等价类为的⼦群,故对任意的h1,h2 in H 有(h1*a*k1)*(h2*a*k2)^(-1) in [a]R取k1=k 2则得any R1,R2 in H有h1*a^2*h2^(-1) in [a]R从⽽可以从中推出h1*a^(2r)*h2^(-1) in [a]R由于G 为有限群,必存在某个 r 使a^(2r)=e 此时 ,有any h1,h2 in H,h1*h2^(-1) in [a]R即H 为[a]R的⼦群.同理, 为 K 的⼦群,所以 m| |[a]R| , n| |[a]R|⽽m 与 n 互素=>mn| |[[a]R|即|G| | |[a]R|⼜[a]R 为G 的⼦群,因此|[a]R| | |G|,从⽽|G|=|[a]R| , 从⽽[a]R=G,即 any g in G有aRg,⽽R 为等价关系.any g1,g2 in G, 由对称性 aRg1=>g1Ra由传递性,aRg1,aRg2=>g1Ra,aRg2 =>g1Rg2So:R=G*G⼋.在每个区域放⼀个结点,当两区域相临时就在响应的两个结点间连⼀条线,如此构造了⼀个平⾯图且是完全图kβ.⽽最⼤的平⾯完全图为k4,所以,β最⼤为四.九.必要性:设G是强连通的,此时若从s到v-s没有有向边,则s中的任⼀顶u到v-s中的任⼀顶v均没有有向道路,从⽽与G是强连通的⽭盾.所以,从s到v-s⾄少有⼀条有向边.充分性:设G是⼀边连通的,any u,v in V(G)则{u}到V(G)-{u}⾄少有⼀条有向边,设为uu1.⽽{u,u1} 到V(G)-{u ,u1}⾄少有⼀条有向边uu2或u1u2.⽆论那种情况都有从u到u2的有向道路.因G中结点数有限,通过如上递归地求解,⼀定有u到v的有向道路.所以G是强连通的.⼗.设e是v1与v2间的最短边,G的最⼩⽣成树为T.若e不在T中,则T+e有唯⼀的圈c,因T是G的最⼩⽣成树,所以,c上除e之外⼀定有另⼀条v1与v2间的边e1,⽽ω(e1)>ω(e). T+e-e1是连通图且与T的边数相同,所以,T+e-e1也是G的⽣成树,⽽ω(T+e-e1)=ω(T)+ω(e)-ω(e1)<ω(T).所以T不是最⼩⽣成树.⽭盾.2000年2001年。

离散数学考试题(后附详细答案)一、命题符号化（共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。

计算机离散数学习题答案《计算机离散数学习题答案》计算机离散数学是计算机科学中的重要基础课程，它涉及到许多重要的数学概念和理论。

学习离散数学需要掌握一定的数学知识和逻辑推理能力，而做习题是提高这些能力的有效途径之一。

以下是一些计算机离散数学习题的答案，希望能对大家的学习有所帮助：1. 证明：对任意整数n，n^2-n为偶数。

答案：当n为偶数时，n=2k，所以n^2-n=4k^2-2k=2(2k^2-k)，为偶数；当n为奇数时，n=2k+1，所以n^2-n=(2k+1)^2-(2k+1)=4k^2+4k+1-2k-1=2(2k^2+2k)，为偶数。

2. 证明：任意正整数n，n^3-n为3的倍数。

答案：当n为3的倍数时，n=3k，所以n^3-n=27k^3-3k=3(9k^3-k)，为3的倍数；当n为3的倍数+1时，n=3k+1，所以n^3-n=(3k+1)^3-(3k+1)=27k^3+27k^2+9k+1-3k-1=3(9k^3+9k^2+3k)，为3的倍数；当n为3的倍数+2时，n=3k+2，所以n^3-n=(3k+2)^3-(3k+2)=27k^3+54k^2+36k+8-3k-2=3(9k^3+18k^2+12k+2)，为3的倍数。

3. 证明：若A、B、C为任意三个集合，则(A∪B)∩C=A∪(B∩C)。

答案：对任意元素x，若x∈(A∪B)∩C，则x∈A∪B且x∈C，即x∈A或x∈B且x∈C，所以x∈A∪(B∩C)；若x∈A∪(B∩C)，则x∈A或x∈B且x∈C，即x∈A∪B且x∈C，所以x∈(A∪B)∩C。

以上是一些计算机离散数学习题的答案，希望对大家的学习有所帮助。

在学习过程中，不断做习题并查看答案，可以帮助加深对知识点的理解和掌握，提高解题能力和逻辑推理能力。

希望大家在学习离散数学的过程中能够坚持不懈，取得更好的成绩。