离散数学试题及答案
Mock Exam
Notes
___________________________________________________________________________________ 1. There are 38 questions in this mock exam. The real exam will consist of about 25 questions that will be relatively similar to those here... that does not mean “identical” to those...
2. If you do these well, you should have no big difficulties in the final exam.
3. I encourage you to work these questions first on your own, without help, to see what you do or do not understand. You may seek help after that. Remember that no one will help you or give you hints during the exam. We will clarify the questions if something is not clear but not more than that.
#01 - Page 13 #8
Let p and q be the propositions
p : I bought a lottery ticket this week.
q : I won the million dollar jackpot.
Express each of these propositions as an English sentence.
a) ￢p I did not buy a lottery ticket this week.
b) p ∨q I bought a lottery ticket this week or I won the million dollar jackpot.
c) p → q If I bought a lottery ticket this week then I won the million dollar jackpot.
d) p ∧q I bought a lottery ticket this week and I won the million dollar jackpot.
e) p ? q I bought a lottery ticket this week if, and only if, I won the million dollar jackpot.
#02 - Page 15 #36
Construct a truth table for each of these compound propositions.
a) (p ∨q) ∨r
p q r p ∨q(p ∨q) ∨r
T T T T T
T T F T T
T F T T T
T F F T T
F T T T T
F T F T T
F F T F T
F F F F F
c) (p ∧q) ∨r
∧(p q)
∧∨r
p q r p q
T T T T T
T T F T T
T F T F T
T F F F F
F T T F T
F T F F F
F F T F T
F F F F F
e) (p ∨q)∧￢r
∨∧￢r
p q r p ∨q￢r(p q)
T T T T F F
T T F T T T
T F T T F F
T F F T T T
F T T T F F
F T F T T T
F F T F F F
F F F F T F
#03 - Page 35 #9
Show that each of these conditional statements is a tautology by using truth tables.
c) ￢p → (p → q)
p q￢p p → q￢p → (p → q)
T T F T T
T F F F T
F T T T T
F F T T T
d) (p ∧q) → (p → q)
∧p → q(p q) → (p → q)
∧
p q p q
T T T T T
T F F F T
F T T T T
F F T T T
e) ￢(p → q) → p
p q p → q￢(p → q)￢(p → q) → p T T T F T
T F F T T
F T T F T
F F T F T
#04 - DNF
Write the following proposition in disjunctive normal form:s = (r → p) → (p∧q)
p q r r → p p∧q s
T T T T T T
T T F T T T
T F T T F F
T F F T F F
F T T F F T
F T F T F F
F F T F F T
F F F T F F
s=(p∧q∧r)∨(p∧q∧?r)∨(?p∧q∧r)∨(?p∧?q∧r)=(p∧q)∨(?p∧r)
#05 - Page 53 #8
Let I (x) be the statement “x has an Internet connection” and C(x, y) be the statement “x and y have chatted over the Internet,” where the domain for the variables x and y consists of all students in your class. Use quantifiers to express each of these statements.
b) Rachel has not chatted over the Internet with Chelsea.
C(Rachel, Charles)
e) Sanjay has chatted with everyone except Joseph.
?x(x ≠ Joseph → C(Sanjay, x))
f ) Someone in your class does not have an Internet connection.
?x(￢I(x))
i) Everyone except one student in your class has an Internet connection.
!?y[￢I(y) ∧?x(x ≠ y → I(x))]
j) Everyone in your class with an Internet connection has chatted over the Internet with at least one other student in your class.
?
?x yC(x, y)
m) There is a student in your class who has chatted with everyone in your class over the Internet.
?x?yC(x, y)
#07 – Page 67 #27
Determine the truth value of each of these statements if the domain for all variables consists of all real numbers.
a) ?x?y(x2 = y) True
c) ?x?y(xy = 0)True
e) ?x(x = 0 → ?y(xy = 1))False
∧x ? y = 1)False
i) ?x?y(x + y = 2 2
j) ?x?y?z(z = (x + y)/2)True
Use rules of inference to show that the hypotheses “If it does not rain or if it is not foggy, then the sailing race will be held and the lifesaving demonstration will go on,” “If the sailing race is held, then the trophy will be awarded,” and “The trophy was not awarded” imply the conclusion “It rained.”Define the following literals:
r It rains
f It is foggy
s The sailing race will be held
d Th
e lifesaving demonstration will go on
t The trophy will be awarded
The premises are then
∧
P1(?r ∨ ?f) → (s d)
P2s → t
P3?t
and the conclusion is
r
The proof proceeds as follows:
1?t P3
2s → t P2
3?s Modus tollens with 1 and 2'
∨Addition to 3
4?s ?d
∧De Morgan's law
5?(s d)
∨) → (s d)
∧P1
6(?r ?f
∨)Modus tollens with 5 and 6
7?(?r ?f
∧De Morgan's law
8r f
9r Simplification of 8
#09 – Page 80 #27
Use rules of inference to show that if ?x(P(x) → (Q(x) ∧S(x))) and ?x(P(x) ∧R(x)) are true, then
?x(R(x) ∧S(x)) is true.
?∧Premise
1x(P(x) R(x))
∧Universal instantiation
2P(c) R(c)
3P(c)Simplification from 2
4x(P(x) →
∧Premise
?(Q(x) S(x)))
∧Universal instantiation
5P(c) → (Q(c) S(c))
∧Modus ponens with 3 and 5
6Q(c) S(c)
7S(c)Simplification from 6
8R(c)Simplification from 2
∧Conjunction of 7 and 8
9R(c) S(c)
?∧Universal generalization
10x(R(x) S(x))
Prove that if n is a positive integer, then n is odd if and only if 5n + 6 is odd.
First, assume that n is odd, so that n = 2k+1 for some integer k. Then 5n+6 = 5(2k+1)+6 = 10k + 11 = 2(5k + 5) + 1. Hence, 5n + 6 is odd. To prove the converse, suppose that n is even, so that n = 2k for some integer k. Then 5n + 6 = 10k + 6 = 2(5k + 3), so 5n + 6 is even. Hence, n is odd if and only if 5n + 6 is odd.
#11 – Page 126 #19
What is the cardinality of each of these sets?
a) {a}1
b) {{a}}1
c) {a, {a}}2
d) {a, {a}, {a, {a}}}3
#12 – Page 126 #40
Explain why (A × B) × (C × D) and A × (B × C) × D are not the same.
The tuples in those sets do not have the same composition. The tuplets in (A × B) × (C × D) are pairs of pairs: ((x,y),(u,v)). However, the tuplets in A × (B × C) × D are ordered triplets with two singletons and a pair: (u, (x,y), v).
#13 – Page 136 #27
Draw the Venn diagrams for each of these combinations of the sets A, B, and C.
b) (A ∩ B) ∪(A ∩ C)
c) (A ∩ B) ∪(A ∩ C)
#14 – Page 153 #22
Determine whether each of these functions is a bijection from R to R.
a) f (x) = ?3x + 4Yes
b) f (x) = ?3x2 + 7No: elements greater than 7 have no preimages.
c) f (x) = (x + 1)/(x + 2)No: -2 has no image
d) f (x) = x5 + 1Yes
For each of these sequences find a recurrence relation satisfied by this sequence. (The answers are not unique because there are infinitely many different recurrence relations satisfied by any sequence.)
a) a n= 3
a n= a n-1
c) a n= 2n + 3
a n-1= 2(n - 1)+ 3 = 2n + 3 – 2 = a n – 2. This implies that a n= a n-1+ 2.
f ) a n= n2 + n(e1)
Here we have two independent terms with n. We will need two additional formulas:
a n-1= (n-1)2 + n – 1 = n2 – 2n + 1 + n – 1 = n2 – n(e2)
a n-2= (n-2)2 + n – 2 = n2 – 4n + 4 + n – 2 = n2 – 3n + 2(e3)
From (e1) and (e2), we have a n – a n-1 = 2n(e4)
From (e2) and (e3), we have a n-1 – a n-2 = 2n – 2(e5)
From (e4) and (e5), we have a n – a n-1 – (a n-1 – a n-2) = a n – 2a n-1+ a n-2 = 2, or a n = 2a n-1– a n-2+ 2 g) a n= n + (?1)n(e1)
a n-1 = n – 1 + (?1)n-1 = n – 1 – (?1)n(e2)
From (e1) and (e2), we have a n – a n-1 = 1 + 2(?1)n
or a n = a n-1 + 1 + 2(?1)n
We can split this into the odd an even n's:
a2k = a2k-1 + 1
a2k+1 = a2k? 1
h) a n= n!
a n = n a n-1
#16 – Page 583 #30 (+ additional questions)
Let R1 = {(1, 2), (2, 3), (3, 4)} and R2 = {(1, 1), (1, 2), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3), (3, 4)} be relations from {1, 2, 3, 4} to {1, 2, 3, 4}. Find
a) R1∪R2 = {(1, 1), (1, 2), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3), (3, 4)} = R2
b) R1 ∩ R2 = {(1, 2), (2, 3), (3, 4)} = R1
c) R1 ? R2 = ?
d) R2 ? R1 = {(1, 1), (2, 1), (2, 2), (3, 1), (3, 2), (3, 3)}
e) R1 ? R2 = {(1, 2), (1, 3), (2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)}
f ) R2 ? R1 =
g) Draw the graph of R1 ? R2.
h) Find the reflexive, symmetric and transitive closures of
Reflexive closure = {(1, 1), (1, 2), (2, 2), (2, 3), (3, 4), (3, 4), (4, 4)}
Symmetric closure = {(1, 2), (2, 1), (2, 3), (3, 2), (3, 3), (4, 3)}
Transitive closure = {(1, 2), (1, 3), (2, 3), (2, 4), (3, 1), (3, 4), (4, 1), (4, 2)}
Let R be the relation consisting of all pairs (x, y) such that x and y are strings of uppercase and lowercase English letters with the property that for every positive integer n, the n th characters in x and y are the same letter, either uppercase or lowercase. Show that R is an equivalence relation.
That definition basically means that two strings are equivalent if, and only if, they have the same length and every corresponding characters x i and y i are the same letter, either lower or upper case.
Let c and C stand for the lower and upper cases of a same letter in the English alphabet.
Clearly k, x
?k = x k. So (x, x) ∈ R.So R is reflexive.
If (x,y)∈ R, then k, x
?k∈ {c, C} and y k∈ {c, C}. So (y, x) ∈ R also. So R is symmetric.
If (x,y)∈ R and (y,z)∈ R, then [x k∈ {c, C}, y k∈ {c, C}] and [y k∈ {c, C}, z k∈ {c, C}], which implies that [x k∈ {c, C},z k∈ {c, C}]. So (x, z) ∈ R. So R is transitive.
Therefore R is an equivalence relation.
#18 – Page 631 #34
Answer these questions for the poset ({2, 4, 6, 9, 12, 18, 27, 36, 48, 60, 72}, |).
a) Find the maximal elements.
27, 48, 60, 72
b) Find the minimal elements.
2, 9
c) Is there a greatest element?
No
d) Is there a least element?
No
e) Find all upper bounds of {2, 9}.
18,36 72
f ) Find the least upper bound of {2, 9}, if it exists.
18
g) Find all lower bounds of {60, 72}.
2, 4, 6, 12
h) Find the greatest lower bound of {60, 72},
if it exists.
12
#19 – Group Theory
Consider the set G={a
1
+a2√3 | a1,a2∈?∧a1a2≠0}with the usual multiplication operation.
a) Show that G is a group by verifying the axioms of closure, associativity, existence of an identity element, and existence of an inverse element for every element. Specify what the identity element is and the form an an inverse element.
1. Closure: Let a,b∈G. Then ab=(a
1+a2√3)(b1+b2√3)=(a1b1+3a2b2)+(a1b2+a2b1)√(3)∈G
2 Associativity: Let a ,b ,c ∈G . Then (ab )c =[(a 1+a 2√3)(b 1+b 2√3)]c
=[(a 1b 1+3a 2b 2)+(a 1b 2+a 2b 1)√(3)](c 1+c 2√3)
=[(a 1b 1+3a 2b 2)c 1+3(a 1b 2+a 2b 1)c 2]+[(a 1b 1+3a 2b 2)c 2+(a 1b 2+a 2b 1)c 1]√(3)=a 1b 1c 1+3a 2b 2c 1+3a 1b 2c 2+3a 2b 1c 2+[a 1b 1c 2+3a 2b 2c 2+a 1b 2c 1+a 2b 1c 1]√(3)=[a 1(b 1c 1+3b 2c 2)+3a 2(b 1c 2+b 2c 1)]+[a 2(b 1c 1+3b 2c 2)+a 1(b 1c 2+b 2c 1)]√(3)=(a 1+a 2√3)[(b 1c 1+3b 2c 2)+(b 1c 2+b 2c 1)√(3)]=a [(b 1+b 2√3)(c 1+c 2√3)]=a (bc )3. Identity element. Let this element be e =e 1+e 2√. Then
ea =(e 1+e 2√3)(a 1+a 2√3)=(e 1a 1+3e 2a 2)+(e 1a 2+e 2a 1)√(3)=(a 1+a 2√3).This implies that for every a 1 and a 2:e 1a 1+3e 2a 2=a 1e 1a 2+e 2a 1=a 2
That implies e 1=1and e 2=0. Thus e =1.
4. Inverse element. Consider a =a 1+a 2√3∈G and let its inverse be a ?1=x 1+x 2√3if it exists. Then we must have
a ?1a =(x 1+x 2√3)(a 1+a 2√3)=(x 1a 1+3x 2a 2)+(x 1a 2+x 2a 1)√(3)=1=e This implies
x 1a 1+3x 2a 2=1x 1a 2+x 2a 1=0The solution is
a ?1=a 1?a 2√3a 12?3a 22.
Thus G forms a group.
b) Is G Abelian?
Yes: ab =(a 1+a 2√3)(b 1+b 2√3)=(a 1b 1+3a 2b 2)+(a 1b 2+a 2b 1)√(3)=ba because this expression is symmetric.
#20 – Page 665 #9
Determine the number of vertices and edges and find the in-degree and out-degree of each vertex for the shown directed multigraph:
5 vertices 13 edges
deg+(a) = 1, deg+(b) = 1, deg+(c) = 5, deg+(d) = 4, deg+(e) = 0deg?(a) = 6, deg?(b) = 5, deg?(c) = 2, deg?(d) = 2, deg?(2) = 0
#21 – Page 666 #28
Suppose that a newcompany has five employees: Zamora, Agraharam, Smith, Chou, and Macintyre. Each employee will assume one of six responsiblities: planning, publicity, sales, marketing,
development, and industry relations. Each employee is capable of doing one or more of these jobs: Zamora could do planning, sales, marketing, or industry relations; Agraharam could do planning or development; Smith could do publicity, sales, or industry relations; Chou could do planning, sales, or industry relations; and Macintyre could do planning, publicity, sales, or industry relations.a) Model the capabilities of these employees using a bipartite graph.
b) Find an assignment of responsibilites such that each employee is assigned one responsibility.
Note: the assignment is not unique. The only forced choices are (Z, ma) and (A, de). There is a variety of possibilities for the other 3.
c) Is the matching of responsibilities you found in part (b) a complete matching? Is it a maximum matching?
The matching (from {Z, A, S, C, M} to {ma, de, sa, pl, pu, ir}) is complete because every employee is matched with a job. It is a maximum because |M| = 5 = |{Z, A, S, C, M}|#22 – Page 676 #21 (+ additional questions)
Consider the following graph
a) Find the adjacency matrix A of the graph A =(11
10
100220111210
)
b) Find how many paths of length 3 there are from c to b A 3=A (11
10
100220111210)(111010022011
1210)=(11101002
2
0111210)(412335305441
5125)=(
12109414361318710121512124
)
So there are 6 paths from c to b.
#23 – Page 676 #38
Determine whether the following two graphs are isomorphic. If so, construct an isomorphism.
Notice the second graph can be deformed like this (by moving v 2 all the way down and rotating the other vertices by about a quarter of a turn):
It has 2 circuits of length 4 whereas the graph on the left has only 1. That immediately implies that these graphs are not isomorphic.#24 – Page 692 #31-32
Consider the following graphs
#31#31
a) List the cut vertices c c, d
b) List the cut edges none(c,d)
c) What is the vertex connectivity κ(G)?11
d) What is the edge connectivity λ(G)?21
#25 – Page 704 #22
Determine whether the directed graph shown has an Euler circuit. Construct an Euler circuit if one exists. If no Euler circuit exists, determine whether the directed graph has an Euler path. Construct an Euler path if one exists.
The vertices' total degrees are all even except for vertices b and c. So it has no Euler circuit but there might be an Euler path, although this is not guaranteed because the graph is directed. However every vertex with an even total degree has equal in and out degrees. Beccause the out-degree of c is larger than its in-degree, then the starting point has to be c. In fact, we o find an Euler path:
c → e → b → c → b → f → a → f → e → f →
d →
e → a → b → d → c → b
#26 – Page 716 #8
Find a shortest path (in mileage) between each of the following pairs of cities in the airline system shown in Figure 1.
Note: You must show every steps of the algorithm
B N M A
C
D S L
-0------N 191/N-1090/N760/N722/N-2534/N2451/N B --1090/N760/N722/N-2534/N2451/N C --1090/N760/N-1630/C2534/N2451/N A --1090/N--1630/C2534/N2451/N D --1090/N---2534/N2451/N M ------2534/N2451/N L
Path = N → L Distance = 2451
b) Boston and San Francisco
B N M A
C
D S L
0-------B -191/B--860/B---N --1281/N951N860/B-2725/N2642/N C --1281/N951N-1768/C2715/C2642/N A --1281/N--1768/C2715/C2642/N M -----1768/C2715/C2642/N D ------2715/C2602/D L ------2715/C-S
Path = B → C → S Distance = 2715
c) Miami and Denver
B N M A
C
D S L
--0-----M -1090/M-595/M----A -1090/M--1201/A---N 1281/N---1201/A-3624/N3541/N C 1281/N----2109/C3056/C3541/N B -----2109/C3056/C3541/N D
Path = M → A → C → D Distance = 2109
B N M A
C
D S L
--0-----M
-1090/M-595/M----A
-1090/M--1201/A---N
1281/N---1201/A-3624/N3541/N C
1281/N----2109/C3056/C3541/N B
-----2109/C3056/C3541/N D
------3056/C2943/D L
Path = M → A → C → D → L Distance = 2943
#27 – Page 726 #12
Suppose that a connected planar graph has eight vertices, each of degree three. Into how many regions is the plane divided by a planar representation of this graph?
We have V = 8. Each node has a degree equal to 3. The sum of all the degrees is therefore 24 and we know it is equal to twice the number of edges; thus E = 12. Recall Euler's formula: V – E + F = 2. So we have 8 – 12 + F = 2, which implies that F = 6.
#28 – Page 732 #4
Construct the dual graph for the map shown. Then find the number of colors needed to color the map so that no two adjacent regions have the same color.
#29 – Page 733 #17
Schedule the final exams for Math 115, Math 116, Math 185, Math 195, CS 101, CS 102, CS 273, and CS 473, using the fewest number of different time slots, if there are no students taking both Math 115
and CS 473, both Math 116 and CS 473, both Math 195 and CS 101, both Math 195 and CS 102, both Math 115 and Math 116, both Math 115 and Math 185, and both Math 185 and Math 195, but there are students in every other pair of courses.
The best way to obtain a graph for this is to draw a complete graph and then remove edges according to the description in the above paragraph.
{MAT115, MAT116, CS473}
{MAT185, MAT195}
{CS101}
{CS102}
{CS273}
The scheduling is not unique.
#30 – Page 755 #4
Consider the following rooted tree:
a) Which vertex is the root?a
b) Which vertices are internal?b, d, e, g, h, i, o
c) Which vertices are leaves?c, f, j, k, l, m, n, p, q, r, s
d) Which vertices are children of n?none
e) Which vertex is the parent of g?b
f ) Which vertices are siblings of k?j
g) Which vertices are ancestors of o?a, d, i
h) Which vertices are descendants of d?h, i, n, o, p, q, r, s
#31 – Page 756 #20
How many leaves does a full 3-ary tree with 100 vertices have?
L=(m?1)n+1
n =
(3?1)×100+1
3
=
201
3
=
67
MAT
MAT
MAT
185
MAT
195
CS
473
CS
273
CS
101
CS
102
#32 – Page 769 #2
Build a binary search tree for the words oenology, phrenology, campanology, ornithology, ichthyology , limnology, alchemy , and astrology using alphabetical order.
#33 – Page 770 #24
Use Huffman coding to encode these symbols with given frequencies: A: 0.10, B: 0.25, C: 0.05, D: 0.15, E: 0.30, F: 0.07, G: 0.08. What is the average number of bits required to encode a symbol?
0.050.070.080.100.150.250.30 C F G A D B E
0.080.100.12
0.150.250.30 G
A
D
B
E
0.12
0.150.18
0.250.30 D
B E
0.18
0.250.27
0.30 B
E
0.27
0.300.43
E
oenology
phrenology
campanology ichthyology alchemy astrology
limnology
ornithology
0.43
0.57
1.00
Codes:
A = 110
B = 10
C = 0111
D = 010
E = 00
F = 0110
G = 111
Average nuber of bits = (3 + 2 + 4 + 3 + 2 + 4 + 3) / 7 = 21/7 = 3#34 – Page 783 #10-11
Consider the following rooted tree:
In which order are the vertices visited using a preorder traversal?a, b, d, e, i, j, m, n, o, c, f, g, h, k, p, l
#35 – Page 784 #23
What is the value of the following prefix expression?a) ? 2 / 8 4 3
?? 2 ?/ 8 4 3=? 2 2? 3
=? 4 3=
1
G
A
C
F
C
F
b) ↑ ? 3 3 4 2 5
??
? 5=↑ ? 3 3
? 8 5
? 4 2
↑ ? 3 3
=↑ ? 9 8 5
=↑ 1 5
=1
c) + ? ↑ 3 2 ↑ 2 3 / 6 ? 4 2
+ ? ↑ 3 2 ↑ 2 3 / 6 ? 4 2=+ ? ↑ 3 2 ↑ 2 3 / 6 2
=+ ? ↑ 3 2 ↑ 2 3 3
=+ ? ↑ 3 2 8 3
=+ ? 9 8 3
=+ 1 3
=4
?
d) + 3 + 3 ↑ 3 + 3 3 3
+ 3 + 3 ↑ 3
?↑ 3 6 3
?+ 3 3 3= + 3 + 3
?+ 3 729 3
= + 3
=?+ 3 732 3
?
= 735 3
=2205
#36 – Page 795 #13
Use depth-first search to produce a spanning tree for the following simple graph. Choose vertex 'a' as the root of this spanning tree and assume that the vertices are ordered alphabetically.
a →
b →
c →
d →
e →
f →
g →
h → I
g → j
#37 – Page 802 #3
Use Prim's algorithm to find a minimum spanning tree (and its total weight) for the following weighted graph:
(ef)1
(cf)3
(eh)3
(hi)2
(gh)4
(bc)4
(bd)3
(ad)2
Total weight = 22
#38 – Page 802 #8
Use Kruskal’s algorithm to find a minimum spanning tree for the weighted graph in Exercise 4 (#37). (ef)1
(ad)2
(hi)2
(bd)3
(cf)3
(eh)3
(bc)4
(gh)4
Total weight = 22
The spanning tree is identical to that in Exercise 4 (#37).
(完整版)离散数学试卷及答案
离散数学试题（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) ? M∧1M ? m∨3m∨4m∨5m∨6m∨7m 2 二、（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 上的二元关系，则由定理4.19知，tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。 若'R 是包含R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r (R )?'R 。由定理4.15和由定理4.16得sr (R )?s ('R )＝'R ，进而有tsr (R )?t ('R )＝'R 。 综上可知，tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 四、（15分）集合A ＝{a ，b ，c ，d ，e }上的二元关系R 为R ＝{，，，，，，，，
离散数学期末考试试题(有几套带答案)
离散数学试题(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 卷及答案） 一、（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 。
离散数学试题与答案
试卷二试题与参考答案 一、填空 1、 P:您努力,Q:您失败。 2、 “除非您努力,否则您将失败”符号化为 ; “虽然您努力了,但还就是失败了”符号化为 。 2、论域D={1,2},指定谓词P P (1,1) P (1,2) P (2,1) P (2,2) T T F F 则公式x ??真值为 。 3设A={2,3,4,5,6}上的二元关系}|,{是质数x y x y x R ∨<><=,则 R= (列举法)。 R 的关系矩阵M R = 。 4、设A={1,2,3},则A 上既不就是对称的又不就是反对称的关系 R= ;A 上既就是对称的又就是反对称的关系R= 。 5、设代数系统
二、选择 1、在下述公式中就是重言式为( ) A.)()(Q P Q P ∨→∧; B.))()(()(P Q Q P Q P →∧→??; C.Q Q P ∧→?)(; D.)(Q P P ∨→。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为( ),成真赋值的个数为 ( )。 A.0; B.1; C.2; D.3 。 3、设}}2,1{},1{,{Φ=S ,则 S 2 有( )个元素。 A.3; B.6; C.7; D.8 。 4、设} 3 ,2 ,1 {=S ,定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产 生的S S ?上一个划分共有( )个分块。 A.4; B.5; C.6; D.9 。 5、设} 3 ,2 ,1 {=S ,S 上关系R 的关系图为 则R 具有( )性质。 A.自反性、对称性、传递性; B.反自反性、反对称性; C.反自反性、反对称性、传递性; D.自反性 。 6、设 ο,+ 为普通加法与乘法,则( )>+<ο,,S 就是域。 A.},,3|{Q b a b a x x S ∈+== B.},,2|{Z b a n x x S ∈== C.},12|{Z n n x x S ∈+== D.}0|{≥∧∈=x Z x x S = N 。 7、下面偏序集( )能构成格。
离散数学期末试题及答案完整版
离散数学期末试题及答 案 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的补元( ).
【浙江工商大学】《离散数学》期末考试题(B)
《离散数学》期末考试题(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 是欧拉图. 二、单选题(每小题3分，共15分) 1.设R 是集合A 上的偏序关系，1-R 是R 的逆关系，则1 -?R R 是A 上的 (A)偏序关系 (B)等价关系 (C)相容关系 (D)以上结论都不成立 2.由2个命题变元p 和q 组成的不等值的命题公式的个数有 (A)2 (B)4 (C)8 (D)16 3.设p 是素数且n 是正整数，则任意有限域的元素个数为 (A)n p + (B)pn (C)n p (D)p n 4.设R 是实数集合，≤是其上的小于等于关系，则(R, ≤)是 (A)有界格 (B)分配格 (C)有补格 (D)布尔格 5.3阶完全无向图3K 的不同构的生成子图有 (A)2 (B)3 (C)4 (D)5 三、判断题(每小题3分，共15分): 正确打“√”，错误打“×”. 1.若一个元素a 既存在左逆元l a ，又存在右逆元r a ，则r l a a =. ( ) 2.命题联结词→不满足结合律. ( ) 3.在Z 8 = {0，1，2，3，4，5，6，7}中，2关于“?8”的逆元为 4. ( ) 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 ),
离散数学期末试卷及答案
一．判断题（共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?{
离散数学期末考试试题及答案
离散数学试题(Ｂ卷答案１） 一、证明题(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={
电大离散数学证明题参考题
五、证明题 1．设G 是一个n 阶无向简单图，n 是大于等于3的奇数．证明图G 与它的补图G 中的奇数度顶点个数相等． 证明：设,G V E =<>，,G V E '=<>．则E '是由n 阶无向完全图n K 的边删去E 所得到的．所以对于任意结 点u V ∈，u 在G 和G 中的度数之和等于u 在n K 中的度数．由于n 是大于等于3的奇数，从而n K 的每个结点都是偶数度的（ 1 (2)n -≥度），于是若u V ∈在G 中是奇数度结点，则它在G 中也是奇数度结点．故图G 与它的补图G 中的奇数度结点个数相等． 2．设连通图G 有k 个奇数度的结点，证明在图G 中至少要添加 2 k 条边才能使其成为欧拉图． 证明：由定理3.1.2，任何图中度数为奇数的结点必是偶数，可知k 是偶数． 又根据定理4.1.1的推论，图G 是欧拉图的充分必要条件是图G 不含奇数度结点．因此只要在每对奇数度结点之间各加一条边，使图G 的所有结点的度数变为偶数，成为欧拉图． 故最少要加2 k 条边到图G 才能使其成为欧拉图． 五、证明题 1．试证明集合等式：A ? (B ?C )=(A ?B ) ? (A ?C )． 证：若x ∈A ? (B ?C )，则x ∈A 或x ∈B ?C ， 即x ∈A 或x ∈B 且x ∈A 或x ∈C ． 即x ∈A ?B 且x ∈A ?C ， 即x ∈T =(A ?B ) ? (A ?C )， 所以A ? (B ?C )? (A ?B ) ? (A ?C )． 反之，若x ∈(A ?B ) ? (A ?C )，则x ∈A ?B 且x ∈A ?C ， 即x ∈A 或x ∈B 且x ∈A 或x ∈C ， 即x ∈A 或x ∈B ?C ， 即x ∈A ? (B ?C )， 所以(A ?B ) ? (A ?C )? A ? (B ?C )． 因此．A ? (B ?C )=(A ?B ) ? (A ?C )． 2．对任意三个集合A , B 和C ，试证明：若A ?B = A ?C ，且A ≠?，则B = C ． 证明：设x ∈A ，y ∈B ，则
离散数学期末试卷A卷及答案
《离散数学》试卷（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人同时选修三门课程。问 （１）三门课程都不选的学生有多少？ （２）只选修计算机课程的学生有多少？
离散数学试卷及答案
填空10% （每小题 2 分） 1、若P，Q，为二命题，P Q 真值为0 当且仅当。 2、命题“对于任意给定的正实数，都存在比它大的实数” 令F（x）：x 为实数，L（x, y） : x y 则命题的逻辑谓词公式为。 3、谓词合式公式xP（x） xQ（x）的前束范式为。 4、将量词辖域中出现的和指导变元交换为另一变元符号，公式其余的部分不变，这种方法称为 换名规则。 5、设x 是谓词合式公式A的一个客体变元，A的论域为D，A（x）关于y 是自由的，则被称为存 在量词消去规则，记为ES。 选择25% （每小题分） 1、下列语句是命题的有（）。 A、明年中秋节的晚上是晴天； C、xy 0 当且仅当x 和y 都大于0； D 、我正在说谎。 2、下列各命题中真值为真的命题有（）。 A、2+2=4当且仅当3是奇数； B、2+2=4当且仅当 3 不是奇数； C、2+2≠4 当且仅当3是奇数； D、2+2≠4当且仅当 3 不是奇数； 3、下列符号串是合式公式的有（） A、P Q ； B、P P Q； C、( P Q) (P Q)； D、(P Q) 。 4、下列等价式成立的有（ ）。 A、P QQ P ； B、P(P R) R； C、P (P Q) Q； D 、P (Q R) (P Q) R。 5、若A1,A2 A n和B为 wff ，且A1 A2 A n B 则 （ ）。 A、称A1 A2 A n 为 B 的前 件； B 、称 B 为A1,A2 A n 的有效结论
C 、 x(M (x) Mortal (x)) ； D 、 x(M(x) Mortal (x)) 8、公式 A x(P(x) Q(x))的解释 I 为：个体域 D={2} ，P(x) ：x>3, Q(x) ：x=4则 A 的 真 值为（ ） 。 A 、 1； B 、 0； C 、 可满足式； D 、无法判定。 9、 下列等价关系正确的是（ ）。 A 、 x(P(x) Q(x)) xP(x) xQ(x)； B 、 x(P(x) Q(x)) xP(x) xQ(x)； C 、 x(P(x) Q) xP(x) Q ； D 、 x(P(x) Q) xP(x) Q 。 10 、 下列推理步骤错在（ ）。 ① x(F(x) G(x)) P ② F(y) G(y) US ① ③ xF(x) P ④ F(y) ES ③ ⑤G(y) T ②④I ⑥ xG(x) EG ⑤ A 、②； B 、④； C 、⑤； D 、⑥ 逻辑判断 30% 1、 用等值演算法和真值表法判断公式 A ((P Q) (Q P)) (P Q) 的类型。 C 、当且仅当 A 1 A 2 A n D 、当且仅当 A 1 A 2 A n B F 。 6、 A ，B 为二合式公式，且 B ，则（ ）。 7、 A 、 A C 、 A B 为重言式； B 、 B ； E 、 A B 为重言式。 人总是要死的”谓词公式表示为（ ）。 论域为全总个体域） M （x ） ： x 是人； Mortal(x) x 是要死的。 A 、 M (x) Mortal (x) ； B M (x) Mortal (x)
离散数学期末考试试题及答案
离散数学试题(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
离散数学试卷及答案(1)
一、填空 20% （每小题2分） 1．设 }7|{)},5()(|{<∈=<∈=+x E x x B x N x x A 且且（N ：自然数集，E + 正偶数） 则 =?B A 。 2．A ，B ，C 表示三个集合，文图中阴影部分的集合表达式为 。 3．设P ，Q 的真值为0，R ，S 的真值为1，则 )()))(((S R P R Q P ?∨→?∧→∨?的真值= 。 4．公式P R S R P ?∨∧∨∧)()(的主合取范式为 。 5．若解释I 的论域D 仅包含一个元素，则 )()(x xP x xP ?→? 在I 下真值为 。 6．设A={1，2，3，4}，A 上关系图为 则 R 2 = 。 7．设A={a ，b ，c ，d}，其上偏序关系R 的哈斯图为 则 R= 。
8．图的补图为 。 9．设A={a ，b ，c ，d} ，A 上二元运算如下： 那么代数系统的幺元是 ，有逆元的元素为 ，它们的逆元分别为 。 10．下图所示的偏序集中，是格的为 。 二、选择 20% （每小题 2分） 1、下列是真命题的有（ ） A ． }}{{}{a a ? ； B ．}}{,{}}{{ΦΦ∈Φ； C ． }},{{ΦΦ∈Φ； D ． }}{{}{Φ∈Φ。 2、下列集合中相等的有（ ） A ．{4，3}Φ?； B ．{Φ，3，4}； C ．{4，Φ，3，3}； D ． {3，4}。 3、设A={1，2，3}，则A 上的二元关系有（ ）个。
A．23 ；B．32 ；C．332?；D．223?。 4、设R，S是集合A上的关系，则下列说法正确的是（） R 是自反的； A．若R，S 是自反的，则S R 是反自反的； B．若R，S 是反自反的，则S R 是对称的； C．若R，S 是对称的，则S R 是传递的。 D．若R，S 是传递的，则S 5、设A={1，2，3，4}，P（A）（A的幂集）上规定二元系如下 t s p R= t s ∈ =则P（A）/ R=（） < > ∧ A ) (| || |} ( , {t , | s A．A ；B．P(A) ；C．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}；D．{{Φ}，{2}，{2，3}，{{2，3，4}}，{A}} 6、设A={Φ，{1}，{1，3}，{1，2，3}}则A上包含关系“?”的哈斯图为（） 7、下列函数是双射的为（） A．f : I→E , f (x) = 2x ；B．f : N→N?N, f (n) =
《离散数学》期末考试试题
《离散数学》期末考试试题 一、 填空题（每空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 ∧??∧?)())((。
离散数学试题及答案
离散数学试题及答案 一、填空题 1设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝_____{3}______________; ρ(A) - ρ(B)＝ ____{{3}，{1，3}，{2,3},{1,2,3}}__________ . 2. 设有限集合A, |A| = n, 则|ρ(A×A)| = ___2^(n^2)________. 3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是____A1 = {(a,1), (b,1)}, A2 = {(a,2), (b,2)}, A3 = {(a,1), (b,2)}, A4 = {(a,2), (b,1)},_________ _____________, 其中双射的是______A3, A4__________. 4. 已知命题公式G＝?(P→Q)∧R，则G的主析取式是____P∧?Q∧R (m5)____. 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}_______ . 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)}_________. 10. 设有限集A, B，|A| = m, |B| = n, 则| |ρ(A?B)| = ______2^(m*n)___________. 11设A,B,R是三个集合，其中R是实数集，A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = _____{x | -1 ≤x < 0, x ∈R}_______ , B-A = ______{x | 1 < x < 2, x ∈R}_____ , A∩B = ______{x | 0 ≤x ≤1, x ∈R}__________ , . 13.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除，则R以集合形式(列举法)记为___________ ________{(2, 2),(2, 4),(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(6, 6)}_________. 14. 设一阶逻辑公式G = ?xP(x)→?xQ(x)，则G的前束式是_____?y?x(P(y)→Q(x))________ _____.