电子科技大学离散期末试题13年
电子科技大学2012 -2013学年第 2学期期 末 考试 A 卷
课程名称： 离散数学 考试形式： 闭卷 考试日期： 2013 年 月 日 考试时长：120分钟 课程成绩构成：平时 10 %， 期中 20 %， 实验 0 %， 期末 70 % 本试卷试题由____ _部分构成，共_____页。
I.
Multiple Choice (15%, 10 questions, 1.5 points each)
（ ） 1.
Which of these propositions is not logically equivalent to the other three? a) (p → q) ∧ (r → q) b) (p ∨ r) → q c) (p ∧ r) → q d) ?q → (?p ∧?r) （ ） 2. Suppose A = {x ,y } and B = {x ,{x }}, then we don ’t have
a) x ∈ B b)? ∈ P (B ). c) {x } ? A - B . d)| P (A ) | = 4.
（ ） 3.
Suppose the variable x represents students, F (x ) means “x
is a freshman”, and M (x ) means “x is a math major”. Match the statement “??x (M (x ) ∧ ?F (x ))” with one of the English statements below:
A. Some freshmen are math majors.
B. Every math major is a freshman.
C. No math major is a freshman.
D. Some freshmen are not math majors. （ ） 4.
The two's complement of -13 is
A. 1 0011.
B. 0 1101 a)
C. 1 0010
D. 0 1100
（ ） 5.
The chromatic number of a graph is the least number of colors needed for a coloring of this graph. The chromatic number of the graph G is
a) 2 b)3
c)4 d) 5
（ ） 6. The function f(x)=x 2log(x 3
+100) is big-O of which of the following functions? a) x 2 b)x 2logx c) x(logx)3 d) xlogx
（ ） 7.
Which of the following complete graphs is planar?
a) K 5 b) K 3,3 c) K 6 d) K 4
（ ） 8.
Which of the following set is uncountable ?
a) The set of real numbers between 172 and 173. b) The set of integers
c) The set of integers not divisible by 3. d) The union of two countable sets. （ ） 9.
How many numbers must be selected from the set {2,4,6,8,10,12,14,16,18,20} in order to guarantee that at least one pair adds up to 22?
a) 5 b) 6 c) 7 d) 8
（ ） 10. Which of the following is false?
a) {x}?{x} b) {x}∈{x, {x}} c) {x}?P({x}), where P({x}) is the power set of {x} d) {x}?{x, {x}}
II. True or False (10%, 10 questions, 1 point each)
（ ） 1. The proposition ((p → q ) ∧ ?p ) → ?q is a tautology. （ ） 2. If pigs can fly, then it will be raining tomorrow. （ ） 3. Suppose A = {a ,b ,c }, then {{a }} ? P (A ).
（ ） 4. “My daughter visited Europe last week” implies the conclusion “Someone visited Europe last week”.
（ ） 5. For all integers a ,b ,c ,d , if a | b and c | d , then (a + c )|(b + d ). （ ） 6. For all real numbers x and y , ?x - y ? = ?x ? - ?y ?.
（ ）
7. ()h x =is defined as a function with domain R and codomain R.
（ ） 8. There exists a simple graph with 6 vertices, whose degrees are 2,2,2,3,4,4.
（ ） 9.
If G is a simple graph with n ≥3 vertices such that the degree of every vertex in G is at least n/2, then G has a Hamilton circuit.
（ ） 10. Let P (m ,n ) be the statement “m|n ,” where the u.d . of m and n is the set of positive integer.
Then ),(n m mP n ??holds.
III. Fill in the Blanks (20%, 10 questions, 2 points each)
1. Suppose A = {x | x ∈ Z and x 2 < 10}. Then ()P A is .
2.
If 11
{|}i A x x R x i i =∈∧-≤≤ then 1
i i A +∞
= is .
3.
Give a relation on {a ,b ,c } that is reflexive and transitive, but not antisymmetric.
.
4.
Suppose g : A → B and f : B → C where A = B = C = {1,2,3,4}, g = {(1,4), (2,1), (3,1), (4,2)} and f = {(1,3),(2,2),(3,4),(4,2)}. Then f g =
. 5.
W rite the negation of the statement “No tests are easy ” in good English:
. 6. The expression of GCD(45,12) as a linear combination of 12 and 45
is . 7.
There are permutations of 7letters A ,B ,C ,D ,E ,F ,G have A immediately to the left of E .
8. If f (n ) = f (n - 1) / f (n - 2), f (0) = 2, f (1) = 5, Then f (2) = . 9.
The negation of the statement ?x ?y (xy = 0) is
.
10. Let }|),{(},|),{(22
21b a b a R b a b a R ≠?∈=≤?∈=
Then 21R R ? is
.
IV. Answer the Questions (35%,7 questions, 5 points each)：
1. Write the truth table for the proposition ：?(r → ?q ) ∨ (p ∧ ?r )
2. Suppose f : R → R where f (x ) = ?x /2?.
(a) If S = {x | 1 ≤ x ≤ 6}, find f (S ). (b) If T = {3,4,5}, find f -1(T ).
3. Find the matrix that represents the relation of R on {1,2,3,4} where aRb means | a - b | ≤ 1. Use
elements in the order given to determine rows and columns of the matrix.
4.Prove that is a tautology using propositional equivalence and the laws of logic.
5.Encrypt the message “HELP” by translating the letters into numb ers, applying the encryption function
f (p) = (3p+ 7) mod 26, and then translatin
g the numbers back into letters.
6.Solve the linear congruence 5x≡ 3 (mod 11).
7.Determine whether these two graphs are isomorphic. If they are isomorphic, give a one-to-one and onto
function f from the one on the left to the one on the right.
A = {(x, y) | x, y ∈R}?{(0, 0)}.
Define a relation on A by the rule: (a, b)R(c, d) (a, b) and (c, d) lie on the same line through the origin.
(a) Prove that R is an equivalence relation.
(b) Describe the equivalence classes arising from the equivalence relation R in part (a).
(c) If A is replaced by the entire plane, is R an equivalence relation?
VI. (7%) Determine whether this argument is valid: Lynn works part time or full time.
If Lynn does not play on the team, then she does not work part time. If Lynn plays on the team, she is busy. Lynn does not work full time. Therefore, Lynn is busy.
VII. (7%) The pseudo-code of Dijstra ’s algorithm is given as following: Procedure Dijkstra (G : weighted connected simple graph) for i :=1 to n L (v i ):=∞ ; L (a ):=0 ; S :=Φ;
While z S Begin
u := a vertex not in S with L (u ) minimal; S :=S ∪{u }; Print S for all vertices v not in S if L (u )+w (u,v ) (a) Find a shortest path between b and f using Dijstra ’s algorithm given above. For every iterative in while-loop, list S ’s elements for “Print S ” statement. (b) Compute the length of the shortest path. 离散数学考试试题（A 卷及答案） 一、（10分）求(P ↓Q )→(P ∧?(Q ∨?R ))的主析取范式 解：(P ↓Q )→(P ∧?(Q ∨?R ))??(?( P ∨Q ))∨(P ∧?Q ∧R )) ?(P ∨Q )∨(P ∧?Q ∧R )) ?(P ∨Q ∨P )∧(P ∨Q ∨?Q )∧(P ∨Q ∨R ) ?(P ∨Q )∧(P ∨Q ∨R ) ?(P ∨Q ∨(R ∧?R ))∧(P ∨Q ∨R ) ?(P ∨Q ∨R )∧(P ∨Q ∨?R )∧(P ∨Q ∨R ) ?0M ∧1M ?2m ∨3m ∨4m ∨5m ∨6m ∨7m 二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断： 甲说：王教授不是苏州人，是上海人。 乙说：王教授不是上海人，是苏州人。 丙说：王教授既不是上海人，也不是杭州人。 王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？ 解 设设P ：王教授是苏州人；Q ：王教授是上海人；R ：王教授是杭州人。则根据题意应有： 甲：?P ∧Q 乙：?Q ∧P 丙：?Q ∧?R 王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有?Q ∧P ，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为： ((?P ∧Q )∧((Q ∧?R )∨(?Q ∧R )))∨((?Q ∧P )∧(?Q ∧R )) ?(?P ∧Q ∧Q ∧?R )∨(?P ∧Q ∧?Q ∧R )∨(?Q ∧P ∧?Q ∧R ) ?(?P ∧Q ∧?R )∨(P ∧?Q ∧R ) ??P ∧Q ∧?R ?T 因此，王教授是上海人。 三、（10分）证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 证明 设R 是非空集合A 上的二元关系，则tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。 若'R 是包含R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r (R )?' R 。则sr (R )?s ('R )＝'R ，进而有tsr (R )?t ('R )＝'R 。 326《离散数学》期末考试题(B ) 一、填空题(每小题3分，共15分) 1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )，)(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元. 5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二．1. 若n B m A ==||,||，则=?||B A ( )，A 到B 的2元关系共有( )个，A 上的2元关系共有( )个. 2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)}，则( )是单射，( )是满射，( )是双射. 3. 下列5个命题公式中，是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(； (2))(q p p ∨→； (3))(q p p ∧→； (4)q q p p →∨∧?)(； (5)q q p →→)(. 4. 设D 24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元( )，4的补元( )，6的补元( ). 5. 设G 是(7, 15)简单平面图，则G 一定是( )图，且其每个面恰由( )条边围成，G 的面数为( ). 《离散数学》试卷（A 卷） 一、 选择题（共5 小题，每题 3 分，共15 分） 1、设A={1,2,3},B={2,3,4,5},C={2,3},则C B A ⊕?)(为(C )。 A 、{1,2} B 、{2,3} C 、{1,4,5} D 、{1,2,3} 2、下列语句中哪个是真命题 ( A ) A 、如果1+2=3，则4+5=9； B 、1+2=3当且仅当4+5≠9。 C 、如果1+2=3，则4+5≠9； D 、1+2=3仅当4+5≠9。 3、个体域为整数集合时，下列公式（ C ）不是命题。 A 、)*(y y x y x =?? B 、)4*(=??y x y x C 、)*(x y x x =? D 、)2*(=??y x y x 4、全域关系A E 不具有下列哪个性质（ B ）。 A 、自反性 B 、反自反性 C 、对称性 D 、传递性 5、函数612)(,:+-=→x x f R R f 是（ D ）。 A 、单射函数 B 、满射函数 C 、既不单射也不满射 D 、双射函数 二、填充题（共 5 小题，每题 3 分，共15 分） 1、设|A|=4，|P(B)|=32，|P(A ?B)|=128，则|A ?B|=??2???. 2、公式)(Q P Q ?∨∧的主合取范式为 。 3、对于公式))()((x Q x P x ∨?，其中)(x P ：x=1， )(x Q ：x=2，当论域为{0,1,2}时，其真值为???1???。 4、设A ＝{1,2,3,4}，则A 上共有???15????个等价关系。 5、设A ＝{a ，b ，c }，B={1,2},则|B A |= 8 。 三、判断题（对的填T ，错的填F ，共 10 小题，每题 1 分，共计10 分） 1、“这个语句是真的”是真命题。 （ F ） 2、“张刚和小强是同桌。”是复合命题。 （ F ） 3、))(()(r q q p p ∧?∧→?∨是矛盾式。 （ T ） 4、)(T S R T R S R ??????。 （ F ） 5、恒等关系具有自反性，对称性，反对称性，传递性。 （ T ） 6、若f 、g 分别是单射,则g f ?是单射。 （ T ） 7、若g f ?是满射，则g 是满射。 （ F ） 8、若A B ?，则)()(A P B P ?。 （ T ） 9、若R 具有自反性，则1-R 也具有自反性。 （ T ） 10、B A ∈并且B A ?不可以同时成立。 （F ） 四、计算题（共 3 小题，每题 10 分，共30 分） 1、调查260个大学生，获得如下数据：64人选修数学课程，94人选修计算机课程，58人选修商贸课程，28人同时选修数学课程和商贸课程，26人同时选修数学课程和计算机课程，22人同时选修计算机课程和商贸课程，14人同时选修三门课程。问 （１）三门课程都不选的学生有多少？ （２）只选修计算机课程的学生有多少？ 安徽大学20 09 — 20 10 学年第 1 学期 《离散数学（上）》考试试卷（A 卷） （时间120分钟） 院/系 专业 姓名 学号 题 号 一 二 三 四 五 总分 得 分 一、单选题（每小题2分，共20分） 1. 设A={a,b,c}，A 上二元关系R={〈a,a 〉，〈b,b 〉,〈a,c 〉}，则关系R 的对称闭包S(R)是( ) A.R ∪I A B.R C.R ∪{〈c,a 〉} D.R ∩I A 2. 设X={a,b,c},I x 是X 上恒等关系，要使I x ∪{〈a,b 〉，〈b,c 〉，〈c,a 〉，〈b,a 〉}∪R 为X 上的等 价关系，R 应取( ) A. ｛〈c,a 〉，〈a,c 〉｝ B.{〈c,b 〉，〈b,a 〉} C. {〈c,a 〉，〈b,a 〉} D.{〈a,c 〉，〈c,b 〉} 3. 下列式子正确的是( ) A. ?∈? B.??? C.{?}?? D.{?}∈? 4. 设解释R 如下：论域D 为实数集，a=0, f(x,y)=x-y, A(x,y):x 离散数学期末试题及答 案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】 326《离散数学》期末考试题(B ) 一、填空题(每小题3分，共15分) 1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )， )(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元. 5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二．1. 若n B m A ==||,||，则=?||B A ( )，A 到B 的2元关系共有( )个，A 上的2元关系共有( )个. 2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)}，则( )是单射，( )是满射，( )是双射. 3. 下列5个命题公式中，是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(； (2))(q p p ∨→； (3))(q p p ∧→； (4)q q p p →∨∧?)(； (5)q q p →→)(. 4. 设D 24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元( )，4的补元( )，6的补元( ). 离散数学期末测验试题（有几套带答案1) ————————————————————————————————作者: ————————————————————————————————日期: ? 离散数学试题(A卷及答案） 一、证明题（10分） １)(?P∧(?Q∧Ｒ)）∨(Q∧R）∨(P∧R）?Ｒ 证明：左端?(?P∧?Q∧R)∨（(Q∨Ｐ)∧R)?（(?P∧?Q)∧R))∨((Ｑ∨Ｐ)∧R） ?(?(P∨Q）∧R)∨((Q∨P)∧Ｒ)?(?(P∨Q)∨(Ｑ∨Ｐ))∧R ?(?(P∨Q)∨(Ｐ∨Ｑ))∧R?T∧R(置换）?R 2）?x(Ａ（ｘ)→B(x)）??xＡ(x）→?xB(x) 证明:?x(A(x)→Ｂ(x））??x（?A（x)∨B(x))??x?A(x)∨?xB(x)???xA（x)∨?xB(x)??xA(x)→?xＢ(ｘ） 二、求命题公式(P∨(Q∧Ｒ))→(Ｐ∧Q∧R）的主析取范式和主合取范式(１０分) 证明:(P∨（Ｑ∧Ｒ））→(P∧Q∧R)??(P∨(Ｑ∧Ｒ）)∨（P∧Q∧R)) ?（?P∧（?Q∨?R)）∨(Ｐ∧Q∧Ｒ） ?(?P∧?Ｑ)∨(?P∧?R)）∨(Ｐ∧Q∧R) ?(?P∧?Q∧R)∨(?P∧?Ｑ∧?R）∨(?Ｐ∧Q∧?R)）∨(?P∧?Q∧?R)）∨(Ｐ∧Ｑ∧R) ?m0∨ｍ1∨m2∨ｍ７ ?Ｍ3∨M4∨M5∨M6 三、推理证明题(10分) 1）Ｃ∨D， (C∨D)→?E, ?Ｅ→(A∧?B), (A∧?B)→(R ∨S)?R∨S 证明:(1) (C∨D）→?E (２) ?E→（A∧?Ｂ) ?? (3）（C∨D）→（A∧?Ｂ) （４) （Ａ∧?B)→(R∨Ｓ) ?? (5) （C∨D）→（R∨Ｓ) ? (6) C∨Ｄ?? (7) R∨S 2) ?x(P(ｘ)→Q(ｙ）∧R(x)），?xP(x)?Q(y）∧?x（P(x)∧R(x)) 证明（1)?xP(ｘ) (2）P(a) （3)?ｘ(P(x)→Q(y）∧R(x)) (4）P（a)→Q(y)∧R(a) (５)Q(y)∧Ｒ(a) (6)Q(y) （７)R(a） (8)P(a) (9)P(ａ)∧R(a) （10)?x(Ｐ(x)∧R(ｘ)) (11)Q（ｙ)∧?x(P（x）∧R(x)） 五、已知Ａ、B、C是三个集合,证明A-(B∪C)=(A-B)∩(A-C) （１5分) 证明∵x∈A-（Ｂ∪C)?x∈A∧x?（Ｂ∪C)?x∈A∧(x?Ｂ∧ｘ?C）?(x∈A∧x?B)∧（x∈A∧x?C）?x∈（Ａ-B)∧ｘ∈(A－C）?x∈(A－B）∩（A-Ｃ)∴A-(B∪Ｃ）=（A-B)∩(A-C） 六、已知R、S是N上的关系，其定义如下：Ｒ=｛＜x，ｙ>| x，y∈N∧y=x2｝，Ｓ={ 一．判断题（共10小题，每题1分，共10分） 在各题末尾的括号内画 表示正确，画 表示错误： 1．设p、q为任意命题公式，则(p∧q)∨p ? p ( ) 2．?x(F(y)→G(x)) ? F(y)→?xG(x)。( ) 3．初级回路一定是简单回路。( ) 4．自然映射是双射。( ) 5．对于给定的集合及其上的二元运算，可逆元素的逆元是唯一的。( ) 6．群的运算是可交换的。( ) 7．自然数集关于数的加法和乘法 列为。 19．n阶无向简单连通图G的生成树有条边。 20．7阶圈的点色数是。 三、运算题（共5小题，每小题8分，共40分） 21．求?xF(x)→?yG(x,y)的前束范式。 22．已知无向图G有11条边，2度和3度顶点各两个，其余为4度顶点，求G 的顶点数。 23．设A={a,b,c,d,e,f}，R=I A?{ 精品文档院术师范学广东技模拟试题 科目：离散数学 120 分钟考试时间: 考试形式：闭卷 姓名：学号：系别、班级： 2分，共10分）一．填空题（每小题__________。?x?y?P(x)∨Q(y) 1. 谓词公式的前束范式是 __)xxQ(?xP(x)????????____，，2. 设全集A?_{4,5}B =__则A∩ {2}__,,?E?1,2,3,4,55,A?21,,32,B_____ __ {1,3,4,5}??BA????b,c}} __________，则3. 设__ ， b?,c,b,a,A?Ba???B(A)?)(_____Φ_______。???)(AB()?4. 在代数系统（N，+）中，其单位元是0，仅有_1___ 有逆元。 ne条边，则G有___e+2-n____个面。5．如果连通平面图G有个顶点，二．选择题（每小题2分，共10分） P?(Q?R)等价的公式是（1. 与命题公式） （A）（B）（C）（D）R?P?Q)()?R)R?(QPP?(Q?R?Q)(P??????b?b,?a,aA??a,b,cR?,不具备关系( 2. 设集合上的二元关系,A)性质 （A）(A)传递性(B)反对称性(C)对称性(D)自反性 G??V,E?中,结点总度数与边数的关系是3. 在图( ) ??E?Edeg(v)deg(v)?2deg(v)?Evdeg()?2E(A)(C)(B) (D) iiiiVv?Vv?4. 设D是有n个结点的有向完全图,则图D的边数为( ) n(n?1)n(n?1)n(n?1)/2n(n?1)/2(A)(B)(D)(C) 5. 无向图G是欧拉图,当且仅当( ) (A)G的所有结点的度数都是偶数(B)G的所有结点的度数都是奇数 精品文档． 精品文档 (C)G连通且所有结点的度数都是偶数(D) G连通且G的所有结点度数都是奇数。 三．计算题（共43分） p?q?r的主合取范式与主析取范式。（1. 求命题公式6分） 解：主合取方式：p∧q∨r?(p∨q∨r)∧(p∨?q∨r)∧(?p∨q∨r)= ∏0.2.4 主析取范式：p∧q∨r?(p∧q∧r) ∨(p∧q∧?r)∨(?p∧q∧r) ∨(?p∧?q∧r) ∨(p∧?q∧r)=∑1.3.5.6.7 1000????0111?????Md,A?a,b,c,的上的二元关集2. 设合系R关系矩阵为求 ??R0000????1000??)tR(),(RsRr()(),(),(rRsRtR),的关系图。R的关系矩阵，并画出分）10（， 安徽大学2006-2007学年第1学期 《离散数学》期末考试试卷（A卷） （时间120分钟） 开课院（系、部）姓名学号. 一、选择题（每小题2分，共20分）1．下列语句中，哪个是真命题（）A、 4 2= + x； B、我们要努力学习； C、如果ab为奇数，那么a是奇数，或b是偶数； D、如果时间流逝不止，你就可以长生不老。 2．下列命题公式中，永真式的是（） A、P Q P→ →) (； B、P P Q∧ → ?) (； C、Q P P? ? ∧) (； D、) (Q P P∨ →。3．在谓词逻辑中，令) (x F表示x是火车；) (y G表示y是汽车；) , (y x L表示x比y快。 命题“并不是所有的火车比所有的汽车快”的符号表示中哪些是正确的（） I.)),()()((y x L y G x F y x →∧??? II.)),()()((y x L y G x F y x ?∧∧?? III. )),()()((y x L y G x F y x ?→∧?? A 、仅I ； B 、仅III ； C 、I 和II ； D 、都不对。 4．下列结论正确的是：（ ） A 、若C A B A =，则 C B =； B 、若B A B A ?，则B A =； C 、若C A B A =，则C B =； D 、若B A ?且D C ?，则D B C A ?。 5．设φ=1A ，}{2φ=A ，})({3φρ=A ，)(4φρ=A ，以下命题为假的是（ ） A 、42A A ∈； B 、31A A ?； C 、24A A ?； D 、34A A ∈。 6．设R 是集合},,,{d c b a A =上的二元关系， },,,,,,,,,,,{><><><><><><=b d d b a c c a a d d a R 。下列哪些命题为真（ ） I.R R ?是对称的 II. R R ?是自反的 III. R R ?不是传递的 A 、仅I ； B 、仅II ； C 、I 和II ； D 、全真。 离散数学试题(Ｂ卷答案１） 一、证明题(10分） 1）(P∧（Ｑ∧Ｒ）)∨(Q∧R）∨（Ｐ∧R)R 证明: 左端(P∧Q∧Ｒ）∨((Q∨P）∧R) ((P∧Q)∧R))∨((Q∨P)∧R) ((Ｐ∨Ｑ）∧R）∨((Ｑ∨P)∧Ｒ) (（P∨Q）∨（Ｑ∨P))∧Ｒ （(P∨Ｑ)∨(Ｐ∨Q))∧R T∧Ｒ(置换)Ｒ 2) x (A(x)B(ｘ）)xA(x)xＢ(ｘ) 证明：x(A(ｘ)B(x))x(Ａ(ｘ)∨B(x)） x A(ｘ)∨xB（ｘ) xA(x)∨xB(x） xＡ(x)xB(x) 二、求命题公式(P∨（Q∧R)）(P∧Q∧R)的主析取范式和主合取范式(10分）。 证明：(P∨（Q∧R))(P∧Q∧R)（P∨(Q∧R)）∨(P∧Q∧R)) (P∧(Q∨Ｒ))∨（P∧Q∧Ｒ） （Ｐ∧Q)∨（P∧R)）∨(P∧Q∧R) (P∧Q∧R)∨(P∧Q∧Ｒ)∨(P∧Q∧Ｒ))∨(P∧Ｑ∧R）)∨(Ｐ∧Q∧R） m0∨ｍ1∨m２∨ｍ７ Ｍ３∨M４∨Ｍ５∨M6 三、推理证明题（１0分) 1）Ｃ∨D，（C∨D)E, E(A∧B)，(A∧Ｂ)(R∨S)R∨Ｓ证明：(１） (C∨D) E ?P (2) E（A∧Ｂ) ??P （3) (Ｃ∨D）（A∧B) Ｔ（1）(2），I (4) （A∧B)(R∨S）??P (5) (Ｃ∨D)(Ｒ∨S) ? T(3)(4)，I (6） C∨Ｄ P (7) R∨S T(5)，I 2) x(P(ｘ)Ｑ(y)∧R(ｘ)），xＰ(ｘ)Q（y)∧x(Ｐ(x)∧R(x)) 证明(1)ｘP(x) Ｐ （2)Ｐ(ａ） T(1），ＥS (3)ｘ（P(x)Q（y)∧R(x）) Ｐ (４)P(a)Q（y)∧R(a） T(3)，ＵS (５)Q（ｙ)∧R(a） T(2)（4），I （6）Q(y) Ｔ(５)，I （7)R(ａ) T(5),I (8)P(a)∧Ｒ（ａ) T(2)(7),I （9)x(Ｐ(x）∧R(x)) Ｔ(8),ＥG (10)Q(ｙ)∧x(P(x)∧R(ｘ)) Ｔ(６）(9)，I 四、某班有２5名学生,其中14人会打篮球,１2人会打排球，6人会打篮球和排球,5人会打篮球和网球,还有2人会打这三种球。而6个会打网球的人都会打另外一种球,求不会打这三种球的人数(10分)。 解：A，B,C分别表示会打排球、网球和篮球的学生集合。则｜A|=1２，|Ｂ|＝6,｜Ｃ|=14，｜A∩C|=6，｜B∩C｜=5，|Ａ∩Ｂ∩C｜=２。 先求|A∩B|。 ∵6＝|（Ａ∪C)∩B|=|（A∩B）∪（Ｂ∩C)|=|（A∩B）|＋|（B∩C）｜-|A∩B∩C|=|(Ａ∩B)|+5-２，∴|(A∩B）|=３。 于是|A∪Ｂ∪C｜=12+6+14-6-5－３＋２=20。不会打这三种球的人数25-20=5。五、已知Ａ、B、Ｃ是三个集合,证明A-(B∪Ｃ)=(A-B)∩(Ａ-C）(10分)。 证明：∵x A-（B∪C） x A∧x（B∪C） xＡ∧(xＢ∧x C） （x A∧x B）∧(x A∧ｘC） x（A-B）∧x(Ａ-C） ｘ（Ａ-Ｂ）∩(A-C） ∴Ａ-（B∪Ｃ)=（Ａ－B）∩(A－Ｃ） 六、已知R、S是Ｎ上的关系,其定义如下：R={ 离散数学期末试卷(A) XXXX大学XX学院2007 ～2008学年第一学期《离散数学》期末试卷年级专业题号得分适用年级专业：2006级软件工程专业试卷说明：闭卷考试，考试时间120分钟一、单项选择题1．下列语句中只有不是命题。C A．今年元旦会下雪。B．1+1=10。C．嫦娥一号太棒了！D．嫦娥奔月的神话已成为现实。2．p?q 的主合取范式是。 B A．(p?q)?(p??q)B．(p??q)?(?p?q) C．(p?q)?(?p??q)D．(p?q)?(?p?q) 3．与p? q等值的命题公式是。D A．?p?q B．p??q C．p??q D．?p?q 4．在一阶逻辑中使用的量词只有个。B A．1B．2 C．3D．4 5．??xA(x)?。C A．??xA(x) B．?x?A(x) C．?x?A(x) D．?xA(x) 6．若|A|=4，则|P(A)|=。 C A．4B．8C．16 D．64 7．设A、B、C为任意集合，集合的对称差运算不具有的性质是。 D A．A?B = B?A B．(A?B)?C = B?(A?C) 班级学号一二三姓名____________ 四总分C．A?A = ?D．A?A = A 8．二元关系是。B A．两个集合的笛卡儿积B．序偶的集合C．映射的集合D．以上都不是9．下面关于函数的叙述中正确的是。D A．函数一定是满射B．函数一定是单射C．函数不是满射就单射D．函数是特殊的关系10．半群中的二元运算一定满足=。B A．交换律B．结合律C．分配律D．幂等律11．环中有个二元运算。 B A．一B．二C．三D．四12．群与独异点的区别是。 C A．满足交换律B．满足结 《离散数学》期末考试试题 一、 填空题（每空2分，合计20分） 1. 设个体域为{2,3,6}D =-, ():3F x x ≤，():0G x x >。则在此解释下公式 ()(()())x F x G x ?∧的真值为______。 2. 设:p 我是大学生，:q 我喜欢数学。命题“我是喜欢数学的大学生”为可符合化 为 。 3. 设{1,2,3,4}A =，{2,4,6}B =，则A B -=________，A B ⊕=________。 4. 合式公式()Q P P ?→∧是永______式。 5. 给定集合{1,2,3,4,5}A =，在集合A 上定义两种关系： {1,3,3,4,2,2}R =<><><>, {4,2,3,1,2,3}S =<><><>， 则_______________S R =ο，_______________R S =ο。 6. 设e 是群G 上的幺元，若a G ∈且2a e =,则1a -=____ , 2a -=__________。 7． 公式))(()(S Q P Q P ?∧?∨∧∨?的对偶公式为 。 8. 设{2,3,6,12}A =, p 是A 上的整除关系，则偏序集,A <>p 的最大元是________，极小元是_ _。 9. 一棵有6个叶结点的完全二叉树，有_____个内点；而若一棵树有2个结点度数为2，一 个结点度数为3，3个结点度数为4，其余是叶结点，则该树有_____个叶结点。 10. 设图,G V E =<>, 1234{v ,v ,v ,v }V =，若G 的邻接矩阵????????????=0001001111011010A ，则1()deg v -=________, 4()deg v +=____________。 二、选择题（每题2分，合计20分） 1．下列各式中哪个不成立（ ）。 A 、)()())()((x xQ x xP x Q x P x ?∨??∨? ； B 、)()())()((x xQ x xP x Q x P x ?∨??∨?； C 、)()())()((x xQ x xP x Q x P x ?∧??∧?； D 、Q x xP Q x P x ∧??∧?)())((。 电子科技大学20 -20 学年第 学期期 考试 卷 课程名称：_________ 考试形式： 考试日期： 20 年 月 日 考试时长：____分钟 课程成绩构成：平时 10 %， 期中 10 %， 实验 %， 期末 80 % 本试卷试题由___2__部分构成，共_____页。 一、填空题（共20分，共 10题，每题2 分） 1. 设随机过程0()cos(),X t A t t ω=+Φ-∞<<∞，其中0ω为常数，A Φ和是相互独立的随机变量， []01A ∈，且均匀分布，Φ在[]02π，上均匀分布，则()X t 的数学期望为： 0 2. 已知平稳随机信号()X t 的自相关函数为2()2X R e ττ-=，请写出()X t 和(2)X t +的协方差12-e 3. 若随机过程()X t 的相关时间为1τ，()Y t 的相关时间为2τ，12ττ>，则()X t 比()Y t 的相关 性要__大___,()X t 的起伏特性比()Y t 的要__小___。 4. 高斯随机过程的严平稳与___宽平稳_____等价。 5. 窄带高斯过程的包络服从___瑞利___分布，相位服从___均匀___分布，且在同一时刻其包络和相 位是___互相独立___的随机变量。 6. 实平稳随机过程的自相关函数是___偶____（奇、偶、非奇非偶）函数。 7. 设)(t Y 是一均值为零的窄带平稳随机过程，其单边功率谱密度为)(ωY F ，且0()Y F ωω-为一偶函 数，则低频过程)()(t A t A s c 和是___正交___。 二、计算题（共80分） 1. (16分)两随机变量X 和Y 的联合概率密度函数为(,)=XY f x y axy ，a 是常数，其中0,1x y ≤≤。求： 1) a ; 2) X 特征函数； 3) 试讨论随机变量X 和Y 是否统计独立。 解：因为联合概率密度函数需要满足归一性，即 （2分） 11 00 1 1 1(,)124 XY f x y dxdy Axydxdy A xdx ydy A ∞∞ -∞-∞= ===?? ????（分） 所以4A = （1分） X 的边缘概率密度函数： 1 ()4201X f x xydy x x ==≤≤? （2分） 所以特征函数 1 1 02 ()2()2122 12j X X j x X j x j x j x j j E e f x e dx xe dx e xe j j e j e ωωωωωωω φωωωωω∞ -∞??=?? ==?? =-??????= --??? ?（分） （分）（分） 容易得1 ()4201Y f y xydx y y ==≤≤? 则有 (,)()()XY X Y f x y f x f y = （2分） 因此X 和Y 是统计独立。 （2分） 2. (12分)设随机过程()0xt X t e t -=<<∞，其中x 在(]0,2π均匀分布，求： 1) 求均值()X m t 和自相关函数(,)X R t t τ+； 1 / 6 北京工业大学经管学院期末试卷 《离散数学》（A ） 学号 姓名： 成绩 一、单项选择题（每题2分，共18分） 1．令P ：今天下雪了，Q ：路滑，则命题“虽然今天下雪了，但是路不． 滑”可符号化为（ D ） A ．P→Q B ．P ∨Q C ．P ∧Q D ．P ∧Q p→q ，蕴涵式，表示假设、条件、“如果，就”。 “→”与此题无关 2. 关于命题变元P 和Q 的极大项M 1表示( C )。 书P1520，此题换作p 、q 更容易理解 A.┐P ∧Q B.┐P ∨Q p ∨┐q 01 1 M 1 ∨┐Q ∧┐Q 3.设R （x ）：x 是实数；S （）：x 小于y 。用谓词表达下述命题：不存在最小的实数。其中错误的表达式是：（ D ） 4.在论域{}中与公式（x ?）A （x ）等价的不含存在量词的公式是（ B ） A.)b (A )a (A ∧ B. )b (A )a (A ∨ C. )b (A )a (A → D. )a (A )b (A → 5．下列命题公式为重言式的是（ C ） A ．Q→（P ∧Q ） B ．P→（P ∧Q ） C ．（P ∧Q ）→P D ．（ P ∨Q ）→Q 牢记→真假条件，作为选择题可直接代入0、1，使选项出现1→0，排除。熟练的可直接看出C 不存在1→0的情况 6. 设｛1，2，3｝，｛｝，下列二元关系R 为A 到B 的函数的是( A ) A. ｛<1>,<2>,<3>｝ B. ｛<1>,<2>｝ C. ｛<1>,<1>,<2>,<3>｝ D. ｛<1>,<2>,<3>,<1>｝ 2 / 6 7.偏序关系具有性质（ D ） 背 A.自反、对称、传递 B.自反、反对称 C.反自反、对称、传递 D.自反、反对称、传递 8.设R 为实数集合，映射:,R R σ→2 ()21,x x x σ=-+-则σ 是( D ). (A) 单射而非满射 (B) 满射而非单射 (C) 双射 (D) 既不是单射也不是满射. 书P96.设函数f ：A→B （1）若，则f 是满射的【即值域为B 的全集，在本题中为R ，该二次函数有最高点，不满足】 （2）若对于任何的x 12∈A , x 1≠x 2,都有f(x 1)≠f(x 2)，则称f 是单射的【即真正一一对应，甚至不存在一个y 对应多个x 。显然，本题为二次函数，不满足】 （3）若f 既是满射的，又是单射的，则称f 是双射的【本题中两个都不满足，既不是单射也不是满射】 二、填空题（每空2分，共22分） １.设Q 为有理数集，笛卡尔集×Q ，*是S 上的二元运算，? 电子科技大学随机信号分析期末测验题 ————————————————————————————————作者：————————————————————————————————日期： 电子科技大学20 -20 学年第 学期期 考试 卷 课程名称：_________ 考试形式： 考试日期： 20 年 月 日 考试时长：____分钟 课程成绩构成：平时 10 %， 期中 10 %， 实验 %， 期末 80 % 本试卷试题由___2__部分构成，共_____页。 题号 一 二 三 四 五 六 七 八 九 十 合计 得分 一、填空题（共20分，共 10题，每题2 分） 1. 设随机过程0()cos(),X t A t t ω=+Φ-∞<<∞，其中0ω为常数，A Φ和是相互独立的随机变量， []01A ∈，且均匀分布，Φ在[]02π，上均匀分布，则()X t 的数学期望为： 0 2. 已知平稳随机信号()X t 的自相关函数为2()2X R e ττ-=，请写出()X t 和(2)X t +的协方差12-e 3. 若随机过程()X t 的相关时间为1τ，()Y t 的相关时间为2τ，12ττ>，则()X t 比()Y t 的相关性 要__大___,()X t 的起伏特性比()Y t 的要__小___。 4. 高斯随机过程的严平稳与___宽平稳_____等价。 5. 窄带高斯过程的包络服从___瑞利___分布，相位服从___均匀___分布，且在同一时刻其包络和相 位是___互相独立___的随机变量。 6. 实平稳随机过程的自相关函数是___偶____（奇、偶、非奇非偶）函数。 7. 设)(t Y 是一均值为零的窄带平稳随机过程，其单边功率谱密度为)(ωY F ，且0()Y F ωω-为一偶函数， 则低频过程)()(t A t A s c 和是___正交___。 得 得 离散数学试题(B卷答案1） 一、证明题（10分） 1)(?P∧(?Q∧R))∨(Q∧R)∨(P∧R)?R 证明: 左端?(?P∧?Q∧R)∨((Q∨P)∧R) ?((?P∧?Q)∧R))∨((Q∨P)∧R) ?(?(P∨Q)∧R)∨((Q∨P)∧R) ?(?(P∨Q)∨(Q∨P))∧R ?(?(P∨Q)∨(P∨Q))∧R ?T∧R(置换)?R 2) ?x (A(x)→B(x))??xA(x)→?xB(x) 证明：?x(A(x)→B(x))??x(?A(x)∨B(x)) ??x?A(x)∨?xB(x) ???xA(x)∨?xB(x) ??xA(x)→?xB(x) 二、求命题公式(P∨(Q∧R))→(P∧Q∧R)的主析取范式和主合取范式（10分）。 证明：(P∨(Q∧R))→(P∧Q∧R)??(P∨(Q∧R))∨(P∧Q∧R)) ?（?P∧(?Q∨?R)）∨(P∧Q∧R) ?(?P∧?Q)∨(?P∧?R))∨(P∧Q∧R) ?(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R))∨(?P∧?Q∧?R))∨(P∧Q∧R) ?m0∨m1∨m2∨m7 ?M3∨M4∨M5∨M6 三、推理证明题（10分） 1）C∨D， (C∨D)→?E，?E→(A∧?B)， (A∧?B)→(R∨S)?R∨S 证明：(1) (C∨D)→?E P (2) ?E→(A∧?B) P (3) (C∨D)→(A∧?B) T(1)(2)，I (4) (A∧?B)→(R∨S) P (5) (C∨D)→(R∨S) T(3)(4)， I (6) C∨D P (7) R∨S T(5)，I 2) ?x(P(x)→Q(y)∧R(x))，?xP(x)?Q(y)∧?x(P(x)∧R(x)) 证明(1)?xP(x) P 离散数学试题(A卷及答案） 一、证明题（10分） 1)(?P∧(?Q∧R))∨(Q∧R)∨(P∧R)?R 证明: 左端?(?P∧?Q∧R)∨((Q∨P)∧R)?((?P∧?Q)∧R))∨((Q∨P)∧R) ?(?(P∨Q)∧R)∨((Q∨P)∧R)?(?(P∨Q)∨(Q∨P))∧R ?(?(P∨Q)∨(P∨Q))∧R?T∧R(置换)?R 2)?x(A(x)→B(x))??xA(x)→?xB(x) 证明：?x(A(x)→B(x))??x(?A(x)∨B(x))??x?A(x)∨?xB(x)???xA(x)∨?xB(x)??xA(x)→?xB(x) 二、求命题公式(P∨(Q∧R))→(P∧Q∧R)的主析取范式和主合取范式（10分） 证明：(P∨(Q∧R))→(P∧Q∧R)??(P∨(Q∧R))∨(P∧Q∧R)) ?（?P∧(?Q∨?R)）∨(P∧Q∧R) ?(?P∧?Q)∨(?P∧?R))∨(P∧Q∧R) ?(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R))∨(?P∧?Q∧?R))∨(P∧Q∧R) ?m0∨m1∨m2∨m7 ?M3∨M4∨M5∨M6 三、推理证明题（10分） 1）C∨D, (C∨D)→?E, ?E→(A ∧?B), (A∧?B)→(R∨S)?R∨S 证明：(1) (C∨D)→?E (2) ?E→(A∧?B) (3) (C∨D)→(A∧?B) (4) (A∧?B)→(R∨S) (5) (C∨D)→(R∨S) (6) C∨D (7) R∨S 2) ?x(P(x)→Q(y)∧R(x))，?xP(x)?Q(y)∧?x(P(x)∧R(x)) 证明（1）?xP(x) (2)P(a) (3)?x(P(x)→Q(y)∧R(x)) (4)P(a)→Q(y)∧R(a) (5)Q(y)∧R(a) (6)Q(y) (7)R(a) (8)P(a) (9)P(a)∧R(a) (10)?x(P(x)∧R(x)) (11)Q(y)∧?x(P(x)∧R(x)) 四、设m是一个取定的正整数，证明：在任取m＋1个整数中，至少有两个整数，它们的差是m的整数倍 证明设 1 a，2a，…，1+m a为任取的m＋1个整数，用m去除它们所得余数 只能是0，1，…，m－1，由抽屉原理可知， 1 a，2a，…，1+m a这m＋1个整 数中至少存在两个数 s a和t a，它们被m除所得余数相同，因此s a和t a的差是m的整数倍。 五、已知A、B、C是三个集合，证明A-(B∪C)=(A-B)∩(A-C) （15分）证明∵x∈ A-（B∪C）? x∈ A∧x?（B∪C）? x∈ A∧（x?B∧x?C）?（x∈ A∧x?B）∧（x∈ A∧x?C）? x∈（A-B）∧x∈（A-C）? x∈（A-B）∩（A-C）∴A-（B∪C）=（A-B）∩（A-C） 六、已知R、S是N上的关系，其定义如下：R={离散数学期末试题
离散数学期末试题及答案
离散数学期末试卷A卷及答案
安徽大学期末试卷离散数学上卷及参考答案.doc
离散数学期末试题及答案完整版
离散数学期末测验试题(有几套带答案1)
离散数学期末试卷及答案
最新离散数学期末考试试题配答案
大学《离散数学》期末考试试卷及答案-(1)
离散数学期末考试试题及答案
离散数学期末试卷(A)
《离散数学》期末考试试题
电子科技大学随机信号分析期末考试题
离散数学期末试卷
电子科技大学随机信号分析期末测验题
离散数学期末考试试题及答案
离散数学期末考试试题(有几套带答案)
相关文档
- 电子科技大学微积分试题及答案
- 2022年西安电子科技大学公共课《C语言》科目期末试卷A(有答案)
- 电子科技大学22春“电子信息工程”《数字信号处理》期末考试高频考点版(带答案)试卷号3
- 西安电子科技大学操作系统期末试题及答案解析
- 2022年西安电子科技大学公共课《大学计算机基础》期末试卷A(有答案)
- 2022年杭州电子科技大学公共课《C语言》科目期末试卷A(有答案)
- 通信原理_电子科技大学中国大学mooc课后章节答案期末考试题库2023年
- 电子科技大学《模拟电路》期末试题及答案
- 电子科技大学微积分试题及答案
- 2022年电子科技大学成都学院数据科学与大数据技术专业《计算机组成原理》科目期末试卷B(有答案)
- 西安电子科技大学数据结构期末复习题
- 杭州电子科技大学单片机原理期末试卷
- 2022年电子科技大学网络工程专业《操作系统》科目期末试卷B(有答案)
- 西安电子科技大学大学物理期末考试试卷(含答案)
- 电子科技大学计算机病毒原理与防范期末考试
- 电子科技大学uml期末考试题B卷 答案
- 自动控制原理_电子科技大学中国大学mooc课后章节答案期末考试题库2023年
- 2022年电子科技大学成都学院公共课《大学计算机基础》期末试卷B(有答案)
- 电子科技大学大学物理期末考试试卷(含答案)
- 电子科技大学2010期末数字电子技术考试题A卷-参考答案