First, multiple-choice questions (2 points for each small question, 20 points for * * *)

1, the assignment that makes the propositional formula p→(p∧q) false is (a)

a . 10 b . 0 1 c . 00d . 1 1

2. Suppose P: it snows today and Q: the road is slippery, then the proposition "Although it snows today, the road is not slippery" can be symbolized as (a).

A.p∧┐q B.p∨┐q

D.p→┐q

3, let b does not contain x, the following first-order logical equivalence is incorrect ()

A.

B.

C.

D.

4, let x, y, z is a set, the following conclusion is incorrect (b)

A. if X Y, then x y = x B. (x-y)-z = x-(y ∩ z)

C.D.

5. Let R be a binary relation on set A, IA be an identity relation on set A, and IA R is true for the following four propositions (A).

A.R is reflexive, B.R is transitive, C.R is symmetric and D.R is antisymmetric.

6. Let the function f: n → n (n is natural number set), f(n)=n+ 1, and the following four propositions are true (a).

A.f is injective, B. f is surjective, C. f is bijective, and D.f is not injective or surjective.

7, let A={ 1, 2, 3, 4}, then the elements of a are correctly classified as (d).

A.{，{ 1，2}，{3，4}} B. {{ 1，2，3}，{3，4}}

C.{{ 1}，{3，4}} D. {{ 1，2，3，4}}

8. An undirected complete graph has (d) edges.

A.n b . N2 c . n(n- 1)d . n(n- 1)/2

9. Let G be a connected planar graph with 6 vertices and 8 edges, then the number of faces of G is (c).

A.2 B.3 C.4 D.5

10, the result of postorder traversal of binary tree is bdeca, and the result of midorder traversal is badce, then

The subtree to the right of the root node has node (c).

A. 1

Two. Fill in the blanks (2 points for each question, *** 10)

1, quantifier negates the equivalent formula _ _ _ _ _ _ _ _ _ _ _.

2. Let R be a binary relation on a = {1, 2,3,4}, and R = {

3.A = {1, 2}, which is a symmetric difference operation of a group and a set. The unit elements of this group are

The reciprocal of {1} is.

4. Graph G is a planar graph if and only if there are no subgraphs contracted to _K3, 3__ or K5.

5, undirected graph g =

0 1 1 1

0 0 1 0

0 0 0 0

The complement of this graph has 12 edges.

Two Problems of Discrete Mathematics

I. True or false questions (each question 1 point, * * *1point)

1. Any propositional formula has a unique disjunctive paradigm. (ton)

2. A closed formula becomes a proposition under any explanation. ( )

The number of layers of 3 is 3 ()4 ... ()

5. Let A, B and C be three sets. If A B = A C is known, then B = C. (F) must exist.

6. Equivalence, similarity and contraction of matrices are all equivalence relations. (ton)

7. It is known that A is the second-order element of the cluster, then

8. If an element in a bounded lattice has more than one complement, then it is not an distributive lattice. (6)

9. If a directed graph is strongly connected, then it must be unidirectionally weakly connected. (ton)

10. A bipartite graph is both an Otto graph and a Hamilton graph. (6)

Fill in the blanks (2 points for each small question, 20 points for * * *)

1. From the type of formula, it belongs to the formula.

2.___________________。

3. Let F(x):x be a person and H(x):x breathe. In first-order logic, the proposition "mortal"

The symbolic form of "muttering" is _ _ (f (x)->; H(x))______ .

A cyclic group of order 4.6 has four subgroups.

5.A={a, b}, then the power set P(A) of A has _ _ 24 bijections to itself.

6.A={ 1, 2, 3}, where S is the set of all permutations on A to form a group, then the unit element is Ia (unit permutation), and the inverse of it is that it is a ordinal element.

7. The degree sequence of the third-order directed graph is 2, 2, 4, the in-degree sequence is 2, 0, 2, and the out-degree sequence is 0, 2, 2.

8. An undirected graph has a spanning tree if and only if G is a connected graph.

9. If the optimal binary tree has n leaves, it has n- 1 branches.

10. The following point connectivity is equal to and the edge connectivity is equal to _ _ _ _ _ _ _.