-Discrete Mathematics - Analysis of final exercises

One 、 choice question

1. In the following sentences ,（ ） It's a proposition .
   A . 2 Is constant
   B. How beautiful this flower is ！
   C. Please close the door ！
   D. Is there a meeting in the afternoon ？

A
A proposition is a statement that can judge whether it is true or not
B It's an exclamation 、C Is an imperative sentence ,D It's a question

2. Make p: it's snowing today ,q: Slippery road ,r： He's late . Then the proposition “ It's snowy and slippery , He's late ” Can be symbolized as （ ）
   A. p∧q→r
   B. p∨q→r
   C. p∧q∧r
   D. p∨qr

A
The priority of the operation is ¬,∧, ∨,→,,
A Can be seen as (p∧q)→r

3. Make p： it's snowing today ,q： Slippery road , Then the proposition “ Although it snowed today , But the road is not slippery ” Can be symbolized as （ ）
   A. p∧¬q
   B. p∧q
   C. p∨¬q
   D. p→¬q

A

4. set up P(x):x It's a bird ,Q(x):x Can fly , proposition “ Some birds can't fly ” Can be symbolized as （ )
   A. ¬(∀x) ( p(x) →Q(x) )
   B. ¬(∀x) ( p(x) ∧ Q(x) )
   C. ¬(∃x) ( p(x) →Q(x) )
   D. ¬(∃x) ( p(x) ∧ Q(x) )

A
Some birds can't fly , Not all birds can fly
In the full quantifier ∀ Later use → connective
In existential conjunctions ∃ Later use ∧ connective

5. set up p(x):x Is an integer ,f(x):x The absolute value of ,L(x,y):x Greater than or equal to y; proposition “ The absolute value of all integers is greater than or equal to 0” The symbol can be （ ）
   A. ∀x( p(x) ∧ L(f(x),0) )
   B. ∀x( p(x)→L(f(x),0) )
   C. ∀xp(x) ∧ L(f(x),0)
   D. ∀xp(x)→L(f(x),0)

B
The absolute value of all integers is greater than or equal to 0, What is used is the full quantifier ∀, The whole proposition should be the same x, In the full quantifier ∀ Later use → connective , So the whole proposition can be signed as ∀x( p(x)→L(f(x),0) )

6. set up F(x):x Is the person ,G(x):x Make a mistake , proposition “ There is no one who does not make mistakes ” The symbol is （ ）
   A. ∀x( F(x) ∧ G(x) )
   B. ¬∃x( F(x) →¬G(x) )
   C. ¬∃x( F(x) ∧ G(x) )
   D. ¬∃x( F(x) ∧ ¬G(x) )

D
A and B The conjunction of is used incorrectly
D, There are no people who make no mistakes

7. The following propositional formulas are not always true （ A ）
   A. (p→q)→p
   B. p→(q→p)
   C. ¬p∨(q→p)
   D. (p→q)∨p
   

8. set up R(x):x For a reasonable number ;Q(x):x It's a real number . proposition “ Any rational number is a real number ” Is symbolized as ( C )
   A.( Yes x) ( (R(x)∧Q(x) )
   B.(∀x)( (R(x)∧Q(x) )
   C.(∀x)( (R(x)→Q(x) )
   D. Yes x( R(x)→Q(x) )

9. Set individual domain D={a,b}, And formula ∀xA(x) The equivalent propositional formula is ( A )
   A. A(a)∧A(b)
   B. A(a)→A(b)
   C. A(a) ∨ A(b)
   D. A(b)→A(a)

Known individual domains , Eliminate quantifiers ,∀xA(x) There are full quantifiers in , Then put all x All values of are listed
Should be A(a)∧A(b)

10. The following equivalence is incorrect ( A )
    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(x) ) ⇔ ∃xP(x) ∨ ∃xQ(x)
    D. ∀x(P(x)∧Q) ⇔ ∀xP(x)∧Q

A

11. Set individual domain D={a,b}, And the formula xA(x) The equivalent propositional formula is ( C )
    A.A(a) ∧A(b
    B.A(a)→A(b)
    C. A(a) ∨ A(b)
    A(b)→A(a)

12. set up X={Ø,{a}{a,Ø}}, Then the following statement is correct (
    A. a∈X
    B. {a,Ø}⊆X
    C. { {a,Ø}}⊆X
    D. {Ø}∈X

C
The relationship between elements and sets is used to belong to
The relationship between sets is expressed as containing
A It belongs to , but a No X The elements of , Because you need to put the whole set {a} as X Of An element
B It belongs to , Explain that {a,Ø} Think of it as a collection ,a and Ø It has to be X The elements of ,a No X The elements of , So it's not right , It can also be interpreted as {a,Ø} It's just X An element of , It doesn't mean a collection
C correct , There are double brackets , In the first bracket {a,Ø} Namely X An element of ,{ {a,Ø}} Namely X A subset of
D It belongs to , Describe the whole {Ø} Be seen as an element , but X There are only Ø But not {Ø}

13. Directed graph D It's a connected graph , If and only if ( D ）
    A. chart D There is at least one path in the
    B. chart D There is a path through each vertex at least once
    C. chart D The number of connected branches of is one
    D. chart D There are loops that pass through each vertex at least once

D
The connected graph here should refer to the strongly connected graph
Yes C Pay special attention to , With the first chapter of propositional logic, we know “ If and only if ” A necessary and sufficient condition , The number of connected branches of a connected graph is indeed one , But if the number of connected branches is one, it does not mean that it is a connected graph , therefore C It's wrong.

14. set up A={a,b,c}, Then the following is the set A Yes ( B)
    A. { {b,c},{c}}
    B. { {a},{b,c}}
    C. { {a,b},{a,c}}
    D. { {a,b},c}

B

We can know π Is a subset family , All of them should be subsets ,D error
Then each subset cannot have duplicate elements ,AC error

15. In the following predicate formulas, what is the bundle normal form is ( D )
    A. ∀xF(x)∧¬(∃x)G
    B. ∀xP(x) ∧ ∀yG( y)
    C. ∀x(P(x)→∃yQ(x,y)
    D. ∀x∃y(P(x)→Q(x,y))

D
The foreshore paradigm is that all quantifiers are in front of each other

16. set up M={x | f1(x)=0},N={x | f2(x)=0}, Then the equation f1(x)*f2(x)=0 The solution of is （ B　）　
    A. M∩N
    B. M∪N
    C. M⊕N
    C. M-N

f1(x)*f2(x)=0 Only = There should be one for 0 The result is 0
Obviously M and N Union

In mathematics , A group represents a group that has a satisfying closeness 、 Satisfied combination law 、 There are unit yuan 、 Algebraic structure of binary operations with inverse elements , Including Abelian group 、 Homomorphism and conjugate classes .
set up G It's a group , be

1. G Satisfy the law of elimination （ Left and right erasures ）, namely ∀a,b,c∈G, if ab=ac, be b = c
2. The inverse of the inverse of any element is itself ,A correct
3. (ab)^-1 = b ^-1 * a ^-1, C error
   For the rest, please see the group's detailed introduction

18. In the set of integers Z On , The operations defined below satisfy the law of association （ ）
    A. ab=b+1
    B. ab=a-1
    C. ab=ab-1
    D. ab=a+b+1

D
If the law of association is satisfied , be (a*b)*c=a*(b*c)

19. Set a simple graph G The sum of the degrees of all nodes is 50, be G The number of sides is （ ）
    A. 50
    B. 25
    C. 10
    D. 5

B
A graph with neither parallel edges nor rings is a simple graph
By the handshake theorem ： The sum of degrees is variable 2 times , The variable is 25

20. Let a simple undirected graph G Is a 5 Vertex 4- Regular graph , be G Yes （ ） side .
    A. 4
    B. 5
    C. 10
    D. 20

C
A regular graph is an undirected simple graph whose vertices have the same degree
It's meaningful , The sum of degrees is 5*4=20, Number of edges =20 / 2 = 10

21. A collection of A={1,2,3,4},A The equivalence relationship on R= {<1,1>, <.3,2>,<2,3>,<4,4>} U IA ( Identity ), The corresponding to the R The division is （ ）
    A. { {1},{2,3},{4} }
    B. { {1,3},{2,4} }
    C. { {1,3},{2},{4} }
    D. { {1},{2},{3},{4} }

A
IA Denotes an identity relation , set up A={a,b,c}, Then the above relationship R={<a,a>,<b,b>,<c,c>},R Is the identity relationship
In this question IA It should be complemented <2,2><3,3>,2 and 3 Should be divided into another piece , Should choose A

D
In mathematics , If you perform an operation on the members of a set , What is generated is still the elements of this collection , Then the set is called closed under this operation .
Compare the maximum number , The result is still A in
Compare the minimum number , The result is still A in
greatest common divisor ,1 and 10 The greatest common divisor of is 1,L For any number , Find the greatest common divisor with other numbers , Can be in 1,2,10,L Get in
if L by 3,3 and 10 The minimum common multiple of is 30, be not in A in ,D It's not closed

C
First look at the full shot , Definition of injectivity and bijection

F The relationship is one-to-one , Satisfy the single shot , but ｆ There is no... In the value field of ｄ, The condition of surjection is not satisfied

B
Take off the cutting point and edge fingers Some point or Some edges , The number of connected branches increases
Cut point set and Bridge finger are removed Some points or An edge , The number of connected branches increases

D
A circuit that passes through every edge of a graph only once and through every vertex in the graph （ access ）, It's called Euler's loop （ Euler pathway ）, Graphs with Euler loops , It is called eulatus
Undirected graph G There is an Euler loop if and only if G Is a connected graph and has no singular vertices
Only Euler path if and only if chart G There is exactly ２ A vertex of singularity , These two points are the endpoints of Euler path

A
The leaf node degree is only １, Obviously not
The rest are equivalent conditions of trees

A
The number of power sets is 2^n

C
Inference of handshake theorem ： The number of vertices with odd degrees in any graph is even
Can be ruled out A and D
Yes B Options , All in all 6 A little bit , There are two degrees 5 The point of , And the degree is 5 Indicates that it is connected to other vertices , In turn, every other point is connected to these two points , The degree cannot be less than 2,B error

There are no singular vertices in Euler graphs , exclude A,C
The sum of degrees of any two nonadjacent vertices in a Hamiltonian graph >=n-1
D Select the two degrees on the right in the 2 The summit of , The sum of degrees is 4<6,D There is no Hamiltonian circuit

C
share 6*3=18 degree
Number of edges = Sum of degrees / 2 = 9

B
Reflexivity is that all vertices have self rings
Reflexivity is that all vertices have no self rings
Symmetry is when there are edges between vertices , It's all two-way sides
Antisymmetry is when there are edges between vertices , All unidirectional edges

B

R2 Yes, it will R1 The unidirectional edge of is complemented by the bidirectional edge , It should be a symmetric closure

D
f(x) in x And y It's not one-to-one , So it's not a single shot ,f(x) The maximum of 6, Not a set of real numbers R, It's not a volley

C
A,B,D There are singular vertices in , Can not constitute an eulato

Two . Completion

1. Propositional formula ¬(p→q) It's true _____, False assignment ____.

really ：1 0 , false ： 0 0, 0 1, 1 1.

2. Propositional formula (p ∨ q)→p It's true ____, False assignment ____.

really ：0 0, 0 1 , 1 1. false ：1 0.

3. Propositional formula p→(p∧q) It's true ____, False assignment _____.

really ：00,01,11, false ：10

4. The formula ( ∀x)( ∀x)( P(y)→Q(x,z) ) ∧ (∃y)R(x,y) The constraint argument is ____, The free argument is ____.

x,y x,z
On the left side ∀x ∀y explain x,y It is the constraints that arise ,z It's free
Right ∃y explain y It's constrained ,x It's free

5. The formula ∀x(P(x) ∨ ∃yR(x) )→Q(x,z) The constraint argument is ____, The free argument is _____.

constraint : x,y
free : x,z

6. set up A = {a,b,{a,b} }, B={a,b}, be B-A=____,A⊕B=_____.

B-A=Ø
A⊕B={ {a,b} }

7. set up A={1,2,3},A Relationship on R={<1,2>,<2,1>}, Then symmetric closure s( R ) = ______, Pass closures t( R )= _____.

s( R ) = {<1,2>,<2,1>} // Itself is a two-way edge , No change required
t( R )={<1,2>,<2,1>,<1,1>,<2,2>} //<1,2><2,1> add to <1,1>, It can also be regarded as <2,1>,<1,2> You want to add <2,2>

8. set up A={a,b,{a,b} },B= {a,b,c}, be A⊕A= ______,A⊕B=______.

be A⊕A=Ø
A⊕B={ {a,b},c}

9. The number of vertices of an undirected tree n And the number of sides m The relationship is ____,6 An undirected connected graph of order has at most ____ Different spanning trees .

m = n-1
6 star

10. set up f(x)=x-1,g(x)=x^2, Then the composite function (f g)(x)=_____,(g f)(x) =____.

It is uniformly specified as right compound
(f g)(x) = g(f(x))=(x-1)^2
(g f)(x) =f(g(x))=x^2-1

synthesis
R°S={<zx,z>|∃y<x,y>∈R∧∃z<y,z>∈S}

18. The number of vertices of an undirected tree n And the number of sides m The relationship is _____, set up G Yes. 8 Number of vertices , be G increase ____ Only a narrow edge can make G Become a complete graph .

m =n-1
21 strip
Undirected complete graph Number of edges m = (n*(n-1))/2
Directed complete graph Number of edges m = (n*(n-1))
The total number of edges m = 8*7/2=28, Trees G Yes 7 side
increase 28-7=21 strip

3、 ... and 、 Calculation questions

2.

4. A tree ( Undirected ) The tree has 2 The degree of the node is 2,1 The degree of nodes is 3,3 The degree of nodes is 4, The rest are leaf nodes , How many leaf nodes does the tree have ?

In a finite graph , The sum of degrees of each node is equal to the number of edges 2 times , The number of edges in the tree is the number of nodes -1
Equipped with x A leaf node , First find the sum of degrees ,d=2* 2 +1* 3 + 3*4+x;
d=19+x
Number of vertices ：n = 2+1+3+x=6+x
Number of edges : m=n-1 = 5+x
d=2m
19+x=10+2x
x=9
Yes 9 Leaf nodes

5. An undirected tree T Yes 5 A leaf ,3 individual 2 Degree bifurcation point , The rest of the branching points are 3 Degree vertex , ask T There are several vertices

Set others 3 The degree vertex has x individual
Total degree d=5* 1 + 3* 2 + 3*x =11+3x
Number of vertices : n=5+3+x =8+x
Opposite and undirected tree , Number of edges : m=n-1 =7+x
d=2m
11+3x = 14+2x
x=3
The number of vertices is 11

Four 、 Short answer

An undirected graph is a bipartite graph if and only if G There is no circuit with odd length in
All this should be a bipartite graph
Or see if it can be transformed into a bipartite graph

A circuit that passes through each vertex of a graph once and only once is called a Hamiltonian circuit , A graph with a Hamiltonian loop is called a Hamiltonian graph .
If G The sum of degrees of any pair of nonadjacent vertices in is greater than or equal to n, be G It's a Hamiltonian graph

5、 ... and 、 Proof problem

6、 ... and 、 Practical questions

2.

3.