-paranoid
Discrete Mathematic Test
Editor: Jin
Peng
Date: 2008.5.6
Contents:
Discrete Mathematic Test (Unit 1) .....
..................................................
................................ 2
Discrete Mathematic Test (Unit 2) .....
..................................................
................................ 8
Discrete Mathematic Test (Unit 3) .....
..................................................
.............................. 13
Discrete Mathematic Test 1 ............
..................................................
.................................. 17
Discrete Mathematic Test 2 ............
..................................................
.................................. 22
Appendix1 Answer to Discrete Mathematic
Test(Unit 1)
..................................................
26
Appendix2 Answer to
Discrete Mathematic Test 2 .......................
.....................................
31
Discrete
Mathematic Test (Unit 1)
Part I (T/F
questions, 15 Scores)
In this part, you
will have 15 statements. Make your own judgment,
and then
put T (True) or F (False)
after each statement.
1.
Let A, B, and C be sets
such that A
∪
B=A
∪<
/p>
C, then B=C.
(
)
2.
Let A and B be subsets of a set U, and
A
B, then
A
△
B=A
B
and A∩B’=
.
(
)
3.
Let p a
nd q and r be three
statements. If ~p?~q ≡ ~p?~r, then q and r have
the same
value.
(
)
4.
Let A, B be sets such that
both A?
B and A?
B is
possible.
(
)
5.
Let p and q be two
statements, then (p?
～
q) ?(
（
～
p?
～
q
）
(p?
～
q)) is a tautology.
(
)
A,
B
be
sets,
P(A)
is
the
power
set
of
A,
then
P(A
B)=P(A)
P(B).
(
)
7.
Let A, B, and C be sets, then if A?
B
，
B?
C
，
then A?
C.
(
)
8.
Let A, B be sets, if A={?}, B=P(P(A)),
then {?}?
B and{?}?
B.
(
)
9.
Let
x
be
real
number,
then
x?
{x}
{{x}}
and
{x}?
{x}
{{x}}.
(
)
10.
Let
A,
B,
and
C
be
sets,
then
A
(B
∪
C)
=
(A
B)
∪
(A
C).
(
)
11.
If
A={x}
∪
x, then x?
A
and x?
A.
(
)
12.
(
x)
（
P(x)
< br>∧
Q(x)
）
and
(
x)P(x)
∧
(
x)Q(x)
are
equivalent.
(
)
13.
Let
A
and
B
be
sets,
then
A×
(B
C)=(A×
B)
(A×
C).
(
)
14.
The argument
formula (p?q)? (r
s), (s?t)?w╞ p?w is
valid.
(
)
15.
(
x)
（
P(x)
?Q(x)
）
and
(
x)P(x)
?
(
x)Q(x)
are
equivalent.
(
)
Part II (1 Foundations: Sets Logic, and
Algorithms , 85 Scores)
1. (8
points)What sets so each of the Venn diagrams in
following Figure represent?
2.
(8
points)Let
U={1,2,3,4,5,6,7,
8,9,10,11,12,13,14,15}.
Let
A={1,5,6,9,10,15}
and
B={5,6,8,9,12,13}. Determine the
following:
Find a. SA
b. SA’
c. SB
d. SA∩B .
3. (8 points) A class of 45
students has 3 minors for options, respectively A,
B and C. A is
the set of students
taking algebra, B is the set of students who play
basketball, C is the set
of students
taking the computer programming course. Among the
45 students, 12 choose
subject A, 8
choose B and another 6 choose C. Additionally, 9
students choose all of the
three
subjects.
What is the at
least number of students do not taking the algebra
course and the computer
programming
course and playing basketball?
4.
(8 points)Find a formula A that uses the variables
p and q such that A is true only when
exactly one of p and q is true.
5. (8
points)Prove the validity of the logical
consequences.
Anne plays golf or Anne
plays basketball. Therefore, Anne plays golf.
6. (9 points)Prove the
validity of the logical consequences.
If the budget is not cut then prices
remain stable if and only if taxes will be raised.
If the
budget is not cut, then taxes
will be raised. If price remain stable, then taxes
will not be
raised. Therefore, taxes
will not be raised.
7.
(8
points)
(1)
What
is
the
universal
quantification
of
the
sentence:
x2
+x
is
an
even
integer, where x is an
even integer? Is the universal quantification a
true statement?
(2) What is the existential
quantification of the sentence: x is a prime
integer, where x is an
odd integer? Is
the existential quantification a true statement?
8.
(12
points)Symbolize
the
following
sentences
by
using
predicates,
quantifiers,
and
logical connectives.
(1)
Any nature
number has only one successor number.
(2)
For all x,y
N, x+y=x if and
only if y=0.
(3)
Not all nature number x
N, it
exist a nature number y
N, such that
x≤y.
9. (8 points)Show that
x
（～
F(x)
∨
A(x
)
）
，
x
（<
/p>
A(x)
→B(x)
）
，
x F(x)
|=
x B(x)
10.
(8 points)In the bubble sort algorithm, if
successive elements L[j] and L[j+1] are such
that L[j]>L[j+1], then they are
interchanged, that is, swapped. Therefore, the
bubble sort
algorithm may require
elements to be swapped. Show how bubble sort sorts
the elements 7
5 6 3 1 4 2 in
increasing order. Draw figures.
Discrete Mathematic Test
(Unit 2)
Part I (T/F questions, 15
Scores)
In this part, you will have 15
statements. Make your own judgment, and then put T
(True)
or F (False) after each
statement.
1.
Let A and B be sets such that any
subsets of A
B is a relation from A to
B.
(
)
2.
Let
R={(1,1),(1,2),,(3,3)
,(3,1)
,(1,3)}
be
relations
on
the
set
A={1,2,3}then
R
is
transitive.
(
)
3.
Let
R={(1,1),(2,2),(2,3),(3,3)} be relations on the
set A={1,2,3}then R is symmetric.
(
)
4.
Let
R
be
a
symmetric
relation.
then
Rn
is
symmetric
for
all
positive
integers
n.
(
)
5.
Let
R
and
S
are
reflexive
relations
on
a
set
A
then
maybe
not
reflexive.
(
)
6.
Let
R={(a,a),(b,b),(c,c)
,(a,b)
,(b,c)}
be
relations
on
the
set
A={a,b,c}then
R
is
equivalence
relation.
(
)
7. If R is
equivalence relation,then the transitive closure
of R is R.
(
)
8.
Let R be relations on a set A,then R
maybe
symmetric and antisymmetic. (
)
9.
If
and
are
partition of a given set A,then
∪
is also a partition of A.(
)
R and S are equivalence relations on a
set A, Let
?
be the set of
all equivalence
class of R,and
?
be the set of all
equivalence class of S, if
R
?
S, then
?
∩
?
=
?
. (
)
11.
Let
(S,
)
be
a
poset
such
that
S
is
a
finite
nonempty
set,then
S
has
ninimal
element,and the
elements is unique.
(
)
12.
Let R and S
are relations on a set A,then
MR∩S
MR
∧
MS.
(
)
13.
If a
relation R is symmetric .then there is loop at
every vertex of its directed graph.
(
)
14.
A directed graph of a
partial order relation R cannot contain a
closed directed path
other than loops.
(
)
15.
The poset
,where P(S) is the power
set of a set S is not a chain.
(
)
Part II (1
Foundations: Sets Logic, and Algorithms , 85
Scores)
1. (8 points) Let R be the
relation {(1, 2), (1, 3), (2, 3), (2, 4), (3, 1)},
and let S be relation
{(2, 1), (3, 1),
(3, 2), (4, 2)}. Find S R3.
2.
(8
points)Determine
whether
the
relations
represented
by
the
following
zero-one
matrices are
partial orders.
3.
(8
points)Determine
the
number
of
different
equivalence
relations
on
a
set
with
three
elements by listing them.
4. (8 points)Let R ={ (a ,
b)
∈
A| a divides b }, where
A={1,2,3,4}. Find the matrix MR of
R.
Then determine whether R is reflexive, symmetric,
or transitive.
5.
(8
points)Determine
whether
the
relation
R
on
the
set
of
all
people
is
reflexive,
symmetric,
antisymmetric, and/or transitive, where (a, b) R
if and only if
a) a is taller than b.
b) a and b were born on the
same day.
c) a
has the same first name as b.
6.
(8
points)
Define
a
equivalence
relations
on
the
set
of
students
in
your
discrete
mathematics class .Determine the
equivalence classes for these equivalence
relations.
7. (10 points)
Let R be the relation on the set of ordered pairs
of positive integers such that
if and only if
. Show that R is an equivalence
relation.
8.
(8
points)
Answer
the
following
questions
for
the
partial
order
represented
by
the
following Hasse diagram.
9. (9 points) Let R be the relation on
the set A={a,b,c,d} such that the matrix of R is
find
(1)
reflexive
closure of R.
(2)
symmetric
closure of R.
(3)
transitive
closure of R.
10. (10 points)
(1)Show that
there is exactly one greatest element of a poset,
if such an element exists.
(2) Show
that the least upper bound of a set in poset is
unique if it exists.
Discrete Mathematic Test
(Unit 3)
Part I (T/F questions, 15
Scores)
In this part, you will have 15
statements. Make your own judgment, and then put T
(True)
or F (False) after each
statement.
1. There exist a
simple graph with four edges and degree sequence
1,2,3,4.
(
)
2.
There are at least two people whith exactly the
same number of friends in any gathering
of n>1 people.
.
(
)
3. The number of edges in a complete
graph with n vertices is n(n-1).
(
)
4. The complement of graph
G is not possible a subgraph of G
.
(
)
5.
Tthat
any
cycle-free
graph
contains
a
vertex
of
degree
0
or
1.
(
)
6. The graph
G, either G or its complement G’, is a connected
graph.
(
)
7. Any graph G and its
complement G’ can not be isomorphic
(
)
8.
An
Eulerian
is
a
Hamiltonian
graph,but
a
Hamiltonian
graph
is
not
An
Eulerian .
(
)
9.
If every
member of a party of six people knows at least
three people ,prove that they
can sit
around a table in such a way that each of them
knows both his neighbors.
(
)
10. A circuit either is a cycle or can
be reduced to a cycle.
(
)
11. A graph G
with n vertices .G is connected if and only if G
is a tree.
(
)
12. A connected graph is a circuit if
the degree of each vertex is 2.
(
)
13.A circuit either is a cycle or can
be reduced to a cycle.
(
)
any simple
connected planar gragh G that X (G)
6.
(
)
15.
．
The sum of the odd degrees
of all vertices of a graph is even.
(
)
Part II (1 Foundations:
Sets Logic, and Algorithms , 85 Scores)
1. (10 points) Does there exist a
simple graph with degree sequence 1,2,3,5? Justify
you
answer.
2.
(10 points) Suppose there are 90 small towns in a
country. From each town there is a
direct bus route to a least 50 towns.
Is it possible to go from one town to ant other
town by
bus possibly changing from one
bus and then taking another bus to another town?
3. 10 points) Find the
number of distinct paths of length 2 in graphs K5.
4.
(5 points Draw all different graphs with two
vertices and two edges.
5. (10 points)
Determine where the graphs in Figure 1 have Euler
the graph has an
Euler trail, exhibit
one.
6
．
(10 points) Use
a K-map to find the minimized sum-of-product
Boolean expressions of
the expressions.
xyzw+xyzw’+xyx’w’+xy’zw’+x’yzw+x’yzw’+x’y
’z’w’+x’y’z’w
7.
(10
points)
Insert
5,
10,
and
20,
in
this
order,
in
the
binary
search
tree
of
following
Figure. Draw the
binary search tree after each insertion.
8
．
(8 points) Does
there exist a simple connected planar graph with
35 vertices and 100
edges?
9.
(10 points) Let G be a simple connected graph with
n vertices. Suppose the degree of
each
vertex is at lease n
1. Does it imply
the existence of a Hamiltonian cycle in G?
Discrete Mathematic Test 1
Part I (T/F questions)
Directions: in this part, you will have
15 statements. Make your own judgment, and then
put T (True) or F (False) after each
statement.
1. Let A and B
be nonempty sets .Then
A
?
B
if and only
if
A
?
B
??
.
(
)
2. Let A and B be nonempty
sets.
If B≠Φ
，
then
A-B
?
A.
(
)
3.
“Is
Hangzhou a beautiful
city?
”
This sentence is a
statement.
(
)
4. Let
P and Q and R be three P
?
Q≡P
?
R,then Q and R
have the same value.
(
)
5. Let
P and Q be two
（～
p
?
～
q
）
?
(p
?
～<
/p>
q) is not a tautology.
(
)
6. (x)
< br>（
P(x)
∧
Q(x)
）
and
(x)P(x)
∧
(x)Q(x)
are equivalent.
(
)
7. Let A and B
be subset of A×
B is a relation.
(
)
A={ 1,2,3}and R=={<1, 1>, <2, 2>, <1, 3>, <3, 1>,
<2, 3>},so R is an equivalence
Relation on A.
(
)
R be a relation on set R
is an equivalence Relation on A if and only if
R
?
R
?
R.
(
)
10. R is an equivalence Relation on
A.R- equivalence class is not a partition of A .(
)
a mathematical system has an
identity,so the cayley table has no equal
Lines.
(
)
12. Let A be a nonempty
?
is identity of
(
?
(A)
，
∩).
(
)
13
．
The sum of the
odd degrees of all vertices of a graph is even.
(
)
14.
Any graph G
and its complement G’can not be
isomorphic.
(
)
15. A graph G with n
vertices .G is connected if and only if G is a
tree.
(
)
Part
Ⅱ
(
set
questions)
Directions: in
this part,you need to provide solutions for
question 16~17 based on the
theory of
Knowledge Set .
A,B,and C
be sets.
Prove A∩(B
-
C)=(A∩B)
-
(A∩C).
17
.
A class of 40
students has 3 minors for options, respectively A,
B and C. Among the
40
students,
15
choose
subject
A,
10
choose B
and
another
6
choose
C. Additionally,
5
students
choose all of the three subjects. Our question is
at least how many students do not
choose any subject.
Part
Ⅲ
(
LOGIC
questions)
Directions: in
this part, you need to provide solutions for
question 17~19 based on the
theory of
knowledge logic .
that
～（
P
∧～
Q
）
，～
Q
∨
R
，～
R
19
、
show that
?
x
（
F(x) →<
/p>
～
A(x)
）
，
?
x
（
A(x
)
∨
B(x)
，
?
x
～
B(x)
|=
?
x
～
F(x)
|=
～
P