¿Quiere encontrar una copia de las preguntas del examen final de Matemáticas Discretas de la Universidad de Nantong, preferiblemente del año pasado?

Preguntas del examen de matemáticas discretas (prueba A y respuestas)

1. (10 puntos) Es necesario asignar un trabajo a 2 personas de 4 personas A, B, C y D. Según las siguientes 3 condiciones, ¿cuántos métodos de asignación existen? ¿Cómo enviar?

(1) Si A va, uno de C y D debe ir

(2) B y C no pueden ir al mismo tiempo

( 3) Si C se va, D se queda.

Solución Supuesto A． A va a trabajar; B: B va a trabajar; C: C va a trabajar; D: D va a trabajar: D va a trabajar. Entonces, según el significado de la pregunta, debería ser A?C?D, (B∧C), y C?D debe ser verdadero al mismo tiempo. Por lo tanto

(A?C?D)∧?(B∧C)∧(C?D) (?A∨(C∧? D)∨(?C∧D))∧(?B ∨?C)∧(?C∨?D) (?A∨(C∧? D)∨(?C∧D))∧((?B∧?C)∨(?B∧?D)∨(C ∧?D)∧(?C∧?D) (?A∧?B∧?C)∨(?A∧?B∧?D)∨(?A∧?C)∨(?A∧?C∧? D)

∨(C∧? D∧?B∧?C)∨(C∧? D∧?B∧?D)∨(C∧? D∧?C)∨(C∧? D∧?C)∨(C∧?C∧?D∧?D)

∨(?C∧D∧?B∧?C)∨(?C∧D∧?B∧?D )∨(?C∧D∧?C)∨(?C∧D∧?C∧?D) F∨F∨(?A∧?C)∨F∨F∨(C∧? D∧?B)∨ F∨F∨(?C∧D∧?B)∨F∨(?C∧D)∨F (? A∧?C)∨F∨F∨(C∧? D∧?B)∨F∨F∨ (?C∧D∧?B)∨F∨(?C∧D)∨F (?(?A∧?C)∨(?B∧C∧? D)∨(?C∧D∧? B)∨ (?C∧D) (?A∧?C)∨(?B∧C∧? D)∨(?C∧D) T

Por lo tanto hay tres extensiones: B∧D, A∧ C , A∧D.

II. (15 puntos) Utilice la lógica de predicados para construir una prueba del siguiente razonamiento: Cada miembro de una conferencia académica es un experto y un trabajador, y algunos de los miembros lo son. jóvenes. Por lo tanto, algunos miembros son jóvenes expertos.

Solución: Dominio: el conjunto de todas las personas ( ): son trabajadores; ( ): son jóvenes.

( ( ) ∧ ( )), ( ) ( ) ∧ ( ))

La prueba es la siguiente:

(1) ( ) P

(2) (c) T(1), ES

(3) ( ( ) ∧ ( ))P

(4) ( c) ∧ ( c) T (3 ), EE.UU.

(5) ( c) T(4), I

(6) ( c) ∧ (c) T(2)(5), I

(7) ( ( ) ∧ ( ))T(6) , EG

Tercero, (10 puntos) Supongamos que A, B y C son tres conjuntos, ¿entonces A? B ?(B?A

Demostración: A?B?x(x∈A→x∈B)∧?x(x∈B∧x?A)?x(x?A∨). x ∈B)∧?x(x∈B∧x?A)

x(x∈A∧x?B)∧?x(x?B∨x∈A)x(x∈A) ∧ x?B)∨?x(x∈A∨x?B) (?x(x∈A∧x?B)∧?x( x∈A∨x?B))?(?x(x∈A) ∧ x?B)∧?x(x∈B→x∈A)) (B?A).

IV. } , R es una relación binaria en A y R = {<2, 1>, <2, 5>, <2, 4>, <3, 4>, <4, 4>, <5, 2> } , encuentre r(R), s(R), t(R).

Resolver r(R) = R ∪ IA = {<2,1>, <2,5>, <2,4>, <3,4>, <3,4>, <4 ,4>, <5,2>, <1,1>, <2,2>, <3,3>, <4, 4>, <5, 5>}

s( R) = R∪R-1 = {<2, 1>, <2, 5>, <2, 4>, <3, 4>, <4, 4>, <5, 2>, <1.2>, <4, 2>, <4, 3>}

R2 = {<2, 2>, <2, 4>, <3, 4>, <4, 4>, <5, 1 >, <5, 5>, <5, 4>}

R3 = {<2, 1>, <2, 5>, <2, 4>, <3, 4>, <4, 4>, <5, 2>, <5, 4>}

R4 = {<2, 2>, <2, 4>, <3 ,4>, <4,4>, <5,1 >, <5,5>, <5,4>} = R2

t(R) = Ri = {<2,1>, <2,5>, <2,4>, <3,4>, <4,4>, <5, 2>, <2, 2>, <5, 1>, <5, 4>, <5, 5>}.

V. (10 puntos) R es una relación binaria en el conjunto no vacío A. Si R es simétrico, entonces r(R) y t(R) son simétricos.

Demostración Para cualquier x, y∈A, si xr(R)y, entonces según r(R)=R∪ IA, tenemos xRy o xIAy. Como R es simétrico con IA, tenemos yRx o yIAx, por lo que yr(R)x. Entonces r(R) es simétrico.

Lo siguiente que hay que demostrar es que para cualquier entero positivo n, Rn es simétrico.

Como R es simétrico, existe xR2y?z(xRz∧zRy)?z(zRx∧yRz)?yR2x, por lo que R2 es simétrico. Si es simétrico, entonces x y?z(x z∧zRy)?z(z x∧yRz)?y x, entonces es simétrico. Por tanto, para cualquier entero positivo n, simétrico.

Para cualquier x, y∈A, si xt(R)y, entonces existe m tal que xRmy, entonces existe yRmx, es decir, existe yt(R)x. Por tanto, t(R) es simétrica.

VI. (10 puntos) Si f : A → B es biyectivo, entonces f-1 : B → A es biyectivo.

Demostración Dado que f: A → B es biyectiva, entonces f-1 es una función de B a A.

Para cualquier x∈A, debe existir y∈B tal que f(x) = y, por lo tanto f-1 (y) = x.

Para cualquier y1, y2∈B, si f-1(y1) = f-1(y2) = x, entonces f(x) = y1, f(x) = y2. Dado que f : A → B es una función, y1 = y2, entonces f-1 es una inyección.

En resumen, f-1 : B → A es una biyección.

7. (10 puntos) Supongamos que es un semigrupo. Si S es un conjunto finito, entonces debe haber a∈S tal que a*a = a.

Demostrar que como es un semigrupo, para cualquier b∈S, según la clausura de *, b2 = b*b∈ S, b3 = b2*b∈ S, .. , bn∈ S, ....

Debido a que S es un conjunto finito, debe haber j > i tal que = . Sea p = j - i, entonces = * . Entonces para q ≥ i, tenemos = * .

Como p ≥ 1, siempre podemos encontrar k ≥ 1 tal que kp ≥ i. Para ∈ S, tenemos = * = *( * ) = ... = * .

Supongamos que a = , entonces a ∈ S, y a * a = a.

VIII. (20 puntos) (1) Si G es un grafo plano conexo, y cada The El grado de una cara es al menos l (l≥3), entonces el número de aristas m y el número de nodos n de G tienen la siguiente relación:

m ≤ (n-2).

Demostración Supongamos que G tiene r caras, entonces 2m = ≥lr. Según la fórmula de Euler, n - m + r = 2. Por tanto, m ≤ (n-2).

(2) Supongamos que el gráfico plano G = es un gráfico autodual, entonces | E|

Demuestre que suponiendo que G* = es un gráfico binario de un gráfico plano conectado G = , entonces G*?G, entonces |F| V* | = |V|, sustitúyalo en la fórmula de Euler |V| - |E| + |F| y obtenga |E|

Preguntas del examen de matemáticas discretas (prueba B y respuestas)

I. (10 puntos) Demostrar (P∨Q)∧(P?R)∧(Q?S) S∨R

Demostración Porque S∨R?R?S, por lo tanto, es necesario demostrar ( P∨Q )∧(P?R)∧(Q?S) ?R?S.

(1) ?R premisa adicional

(2 )P?R P

(3)?P T(1)(2), I

(4) P∨Q P

(5) Q T(3)(4), I

(6) Q?S P

(7) S T(5)(6), I

(8) ?R?S CP

(9) S∨R T(8), E

II (15 puntos) De acuerdo con la teoría del razonamiento, demuestre que todo candidato es diligente o inteligente, y todos. las personas diligentes lograrán algo excelente, pero no todos los candidatos marcarán la diferencia, por lo que debe haber algunos candidatos que sean inteligentes.

Supongamos que P(e): e es un candidato; Q(e): e marcará la diferencia; A(e): e es una persona diligente; B(e): e es una persona inteligente; ; Dominio personal: un conjunto de personas, entonces la proposición se puede simbolizar como: ??x(P(x)?(A(x)∨B(x))), ?x(A(x)?Q(x); )) , ?x(P(x)?Q(x)) ?x(P(x)∧B(x)).

(1) ?x(P(x)?Q( x) )P

(2) ?x(?P(x)∨Q(x))T(1), E

(3) ?x(P(x )∧ ?Q(x))T(2), E

(4) P(a) ∧ ?Q(a) T(3), ES

(5) P( a) T(4).I

(6)?Q(a) T(4), I

(7)?x(P(x)?( A( x)∨B(x))P

(8) P(a)?(A(a)∨B(a)) T(7), Estados Unidos

(9 )A(a)∨B(a) T(8)(5), I

(10)?x(A(x)?Q(x))P

(11)A(a)?Q(a) T(10), EE.UU.

(12)?A(a) T(11)(6), I

( 13)(a)? P>(13)?B(a) T(12)(9), I

(14) P(a) ∧ B(a) T(5) (13 ), I

(15)?x(P(x) ∧ B(x)))T (14), EG

3 (10 puntos) Hay. 25 estudiantes en una clase determinada. Entre los estudiantes, 14 pueden jugar baloncesto, 12 pueden jugar voleibol, 6 pueden jugar baloncesto y voleibol, 5 pueden jugar baloncesto y tenis y 2 pueden jugar los tres tipos de pelotas. Y las 6 personas que saben jugar tenis también pueden jugar otro tipo de pelota. Calcula la cantidad de personas que no pueden jugar tres tipos de pelota.

Solución Sean A, B y C el conjunto de estudiantes que pueden jugar voleibol, tenis y baloncesto respectivamente. Entonces:

|A| = 12, |B| = 6, |C| = 14, |A ∩ C| = 2, |(A ∪ C) ∩ B| = 6.

Porque |(A∪C)∩B| = (A∩B)∪(B∩C)| = |(A∩B)| B∩C| = |(A∩B)| + 5 - 2 = 6, entonces |(A∩B)| + 2 = 20 y = 25 - 20 = 5. Por lo tanto, el número de personas que no pueden golpear estas tres bolas es ****5.

IV. (10 puntos) Supongamos que A1, A2 y A3 son subconjuntos del conjunto completo U. Demuestre que el conjunto de todos los minitérminos no vacíos generados por A1, A2 y A3 forma parte del conjunto completo U.

Demuestra que hay 8 términos menores ****, y que hay r términos menores no vacíos s1, s2,..., sr (r ≤ 8).

Para cualquier a∈U, a∈Ai o a∈, una de estas dos condiciones debe ser verdadera, y Ai? se toma como Ai que contiene el elemento a o, entonces a∈Ai ?, es decir, hay a∈si, entonces ¿U?

Tome dos subtérminos no vacíos sp y sq. Si sp ≠ sq, debe haber un cierto Ai y, que aparecen en sp y sq respectivamente. , entonces sp ∩ sq = ?

En resumen, {s1, s2,..., sr} es una división de U.

(15 puntos) Supongamos que R es una relación binaria en A, entonces: ¿R es una relación transitiva?R*R?R.

Prueba (5) Si R es una relación transitiva, entonces ∈R*R?z(xRz∧zSy)?xRc∧cSy Como R es una relación transitiva, podemos obtener xRy, es decir, tenemos ∈R, entonces R*R?R.

Por el contrario, si R*R?R, entonces para cualquier x, y, z∈A, si xRz y zRy, entonces ∈R*R, entonces hay ∈R, lo que significa que el autor tiene xRy, por lo que R es transitivo.

Seis (15 puntos) Si G es un gráfico plano conectado, entonces n - m + r = 2, donde n, m y r son el número de nodos, aristas y caras de G respectivamente.

Demostración por Inducción basada en el número de lados m de G.

Cuando m = 0, dado que G es un gráfico conectado, G es un gráfico domesticado. En este momento, n = 1, r = 1, la conclusión se establece naturalmente.

Supongamos que la conclusión es válida para gráficos planos conectados con menos de m aristas. A continuación, considere el caso de un gráfico plano conexo G con m aristas.

Sea e una arista de G. El gráfico obtenido después de eliminar e de G se denota como G?, y sea su número de nodos, aristas y caras n?, m y r? Divida e en los siguientes casos para su discusión:

Si e es un borde cortante, entonces G tiene dos ramas conectadas G1 y G2. El número de nodos, aristas y caras de Gi son ni, mi y ri respectivamente. +1 = r + 1. Según la hipótesis inductiva, existen n1 -m1 + r1 = 2, n2 - m2 + r2 = 2, por lo que (n1 + n2) - (m1 + m2) + (r1 + r2) = 4, n - (m - 1) + (r + 1) = 4, es decir, n -m + r = 4.

Si e no es una arista tangente, entonces n?=n, m?=m-1, r?=r-1. Según la hipótesis inductiva, tenemos n?m?+r? =2, por lo tanto n-(m -1) + r-1 = 2, es decir, n - m + r = 2.

Según la inducción matemática se establece la conclusión.

VII.(10 puntos) Supongamos que la función g: A→B, f: B→C, entonces:

(1) niebla es la función de A a C <; /p>

p>

(2) Para cualquier x∈A, existe fog(x)=f(g(x)).

Demuestre (1) Para cualquier x∈A, debido a que g : A → B es una función, existe y∈B tal que ∈g para y∈B, porque f : B → C es una función, por lo que existe z∈C tal que ∈f. Según la definición de relaciones compuestas, tenemos ∈g y ∈f por ∈f ∈g*f, es decir, por lo tanto Dfog = A .

Para cualquier x ∈ A, si existen y1, y2 ∈ C tales que , ∈fog = g*f, entonces existe t1 tal que ∈ g y<. t1, y1> ∈f, y existe t2 tal que ∈g, y ∈f. Como g:A → B es una función, t1 = t2. Y como f:B → C es una función, y1 = y2. Por tanto, cada elemento de A corresponde a un único elemento de C.

Resumiendo, la niebla es una función de A a C.

(2) Para cualquier x∈A, g: A → B es una función, tenemos ∈g y g(x)∈B, f: B → C es una función, tenemos ∈f, entonces ∈g*f = niebla. Como la niebla es una función de A a C, podemos escribir niebla(x) = f(g(x)).

VIII.(15 puntos) Sea un subgrupo de , y defina R = {|a, b ​​​​∈ G y a-. 1 *b∈H}, entonces R es una relación de equivalencia en G, y [a]R = aH.

Demostración: Para cualquier a∈G, debe haber un -1∈G, tal que a-1*a = e∈H, entonces ∈ R.

Si ∈ R, entonces a-1*b∈ H. Dado que H es un subgrupo de G, (a-1*b)*(b-1*c) = a-1*c∈ H, entonces ∈ R.

En resumen, R es una relación de equivalencia en G.

Para cualquier b∈ [a]R, existen ∈ R, a-1*b∈ H, entonces existe h∈ H tal que a-1*b = h, b = a*h, entonces b∈ aH, [a]R?aH. Para cualquier b∈aH, existe h∈H tal que b = a*h, a-1*b = h∈H, 〈a, b〉∈R, entonces aH?[a]R. Por lo tanto, [a]R = aH.