离散数学第五版--模拟试题--及答案

一、填空1．不能再分解的命题称为____________，至少包含一个联结词的命题称为____________。

2．一个命题公式A(P, Q, R)为真的所有真值指派是000, 001, 010, 100，则其主析取范式是__________________，其主合取范式是_________________。

3．设A={a,b,c}，B={b,c,d,e}，C={b,c}，则( A ⋃ ⊕＝____________。

4．幂集P(P(∅)) ＝________________。

5．设A为任意集合，请填入适当运算符，使式子A________A=∅；A________A’=∅成立。

6．设A={0，1，2，3，6}，R={〈x,y〉|x≠y∧(x,y∈A)∧y≡x(mod 3)}，则D(R)=____________，R(R)=____________。

7．称集合S是给定非空集合A的覆盖：若S={S1，S2，…，S n}，其中S i⊆A，S i≠Ø，i=1，2，…，n，且______ _____；进一步若_____ _______，则S是集合A的划分。

8．两个重言式的析取是____ ____式，一个重言式和一个永假式的合取式是式。

9．公式┐(P∨Q) ←→(P∧Q)的主析取范式是。

10. 已知Π={{a}{b,c}}是A={a,b,c}的一个划分，由Π决定的A上的一个等价关系是。

二、证明及求解1．求命题公式（P→Q）→（Q∨P）的主析取范式。

2．推理证明题1）⌝P∨Q，⌝Q∨R，R→S⇒P→S。

2) (∀x)(P(x)→Q(y)∧R(x))，(∃x)P(x)⇒Q(y)∧(∃x)(P(x)∧R(x))x)}，S={〈x,y〉|x,y∈A∧（x=y+2）}。

3．设A={0，1，2，3}，R={〈x,y〉|x,y∈A∧(y=x+1∨y=2试求R S R。

4．证明：R是传递的⇔R*R⊆R。

5．设R是A上的二元关系，S={<a, b>| 存在c∈A，使<a, c>∈R，且<c, b>∈R}。

P125 21.a)N={1,3} Φ(4)=2b)N={1,3,7,9}Φ(10)=4c)N={1,2,3,…,12}Φ(13)=12P149 25b) 5^2003 mod 1001=983P183 4“the sailing race will be held and the lifesaving demonstration will go on”: this sentence should be split into two propositions ,one is the “sailing race will be held “, the other is “the lifesaving demonstration will go on.”P202 64N is odd and not divisible by 3 , so we can express n=6k+1 or 6k+5(k>=1) Basis step: It is easy to prove the correction of the proposition when n=7 and n=11.Inductive step: assume that if n=6k+1, the proposition is true,and if n=6(k+1)+1=(6k+1)+6, as shown in the figure below :the square is split into 4 parts asa)(6k+1)*(6k+1), b) 7*7-1 ( pleaseallow me to write this way), c)6k*6 andd)6*6k . it is clear that a) is fit to theproposition , b) can be filled withL-shaped pieces and c),d) can be filled with a rectangle consist of 2 L-shaped pieces.If n=6(k+1)+5 , the proposition can be also proved as above.So , we can believe that the proposition is true.P259 49a)We need to find something to count so that the left-hand side of theequation counts it in one way and the right-hand side counts it in different way. After much thought , we might try the following. We will count the number of bit strings of length n+r+1containing exactly r 0’s and n+1 1’s . There are C(n+r+1,r) such strings , sincea string is completely specified by deciding which r of the bits areto be the 0’s . To see that the left-hand side of the identity counts the same thing,let l+1 be the position of the last 1 in the string . Since there are n+1 1’s , we know that l cannot be less than n . thus there are disjoint cases for each l from n to n+r . For each such l, we completely determine the string by deciding which of the l positionsI the string before the last 1 are to be 0’s . Since there are n 1’s inthis range, there are l-n 0’s. Thus there are C(l,l-n) .ways to choose the positions of the 0’s . Now by the sum rule , the total number of bit strings will be ∑(l=n to n+r)C(l,l-n) . By making the change of variable k=l-n,this transforms into the left-hand side, and we arefinished.P243 33a)there can clearly be no one-to-one function from {1,2,…n} to {0,1}if n>2. if n=1 ,then there are 2 such functions , the one that sends 1 to 0, and the one that sends 1 to 1. if n=2 , then there are again 2 such functions since once it is determined where 1 is sent , the function must send 2 to the other value in the codomain.b)If the function assigns 0 to both 1 and n , then there are n-2 functionvalues free to be chosen. Each can be chosen in 2 ways. Therefore by product rule, there are 2^n-2 such functions ,as long as n>1. if n=1 ,then clearly there is just one such function.c)If n=1, then there are no such functions.If n>1, we will decide which of the numbers from 1 to n-1 , inclusive,will get sent to 1. there are n-1 ways to make this choice.finally , we are free to specify the value if the function at n,and this may be done in 2ways ,hence by the product rule ,the answer is 2(n-1).P383 25b)for each unordered pair {a.b} of distinct elements of A, we have a3-way choice----either include (a,b) only, include (b,a) only , orinclude neither .For each element of A we have a 2-way choice .Therefore the answer is (3^C(n,2))*(2^n) .c)as in part (b) we have a 3-way choice for a!=b . there is no choiceabout including (a,a) in the relation——the definition prohibits it.Therefore the answer is 3^C(n,2)。

、选择：(满分20分，每小题2分)1 •下列语句中不是命题的有( )⑴ 9+5 <12 ；⑵ x+3=5 ；⑶我用的计算机CPU主频是1G吗？；⑷我要努力学习。

2. 命题"我不能一边听课，一边看小说”的符号化为( )⑴ P -Q ；⑵-P— Q ；⑶—Q —P ；⑷ 一(P Q)。

3•下列表达式正确的有( )⑴—(P— Q)= Q ；⑵ P Q= P ；⑶(P Q) (P —Q)：二P ；⑷ Pr (Pr Q) ：= T。

4. n个命题变元可产生( )个互不等价的小项。

⑴ n ；⑵ n2；⑶2n ；⑷2n。

5•若公式(P Q) (一P R)的主析取范式为m001m011叶10m111则它的主合取范式为( )⑴m ooi m oii Bio m m ；⑵M 000 ：M op ：M I。

M pi ；⑶M ooi M oii 八M iio 找M iii ；⑷ m°oo m°io 入m ioo A m ioi 。

6. 命题"尽管有人聪明，但未必一切人都聪明”的符号化(P(x): x是聪明的，M(x) : x是人) ( )⑴ x(M (x) > P(x)) 一(-x(M(x) > P(x)))⑵ x(M (x) P(x)) —(-x(M(x) P(x)))⑶ x(M (x) P(x)) 一(-x(M(x) > P(x)))⑷ x(M (x) P(x)) 一(-x(M(x) > P(x)))7. 设A=｛门｝，B= P (P (A)) 下列( )表达式成立。

⑴®二B ；⑵竝；二B ；⑶讥〉：:-B ；⑷"W B。

8. A是素数集合，B是奇数集合，则A-B=( )⑴ 素数集合；⑵ 奇数集合；⑶ 门；⑷｛2｝。

9. 集合A={2 , 3, 6, 12, 24, 36}上偏序关系R的Hass图为则集合B={2 , 3, 6, 12}的上确界_____________ 。

离散数学试题及答案一、填空题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 变成完全图。

16.设谓词的定义域为{a, b},将表达式∀xR(x)→∃xS(x)中量词消除，写成与之对应的命题公式是.17. 设集合 A＝{1, 2, 3, 4}，A 上的二元关系 R＝{(1,1),(1,2),(2,3)}, S＝{(1,3),(2,3),(3,2)}。