Exámenes finales de Nantong
Preguntas de Matemáticas Discretas (Prueba A y Respuestas)
1 (10 puntos) Es necesario asignar dos de las cuatro personas A, B, C y D para completar una determinada tarea. tarea. ¿Cuántas formas hay basadas en las siguientes tres condiciones? ¿Cómo enviarlo?
(1) Si A va, habrá una persona de C y D
(2) B y C no pueden ir ambos
(3); ) Si C se va, D se queda.
Conjunto a: a funciona; B: b se pone a trabajar; C: c se pone a trabajar; D: d se pone a trabajar. Según el significado de la pregunta, debería ser: a? ¿do? d,? (B∧C), el CD debe establecerse al mismo tiempo. Por lo tanto
(A?c?D)∧? (B∧C)∧(CD)
(?A∨(C∧?D)∨(?C∧D))∧(?B∨?C)∧(?C∨?d)
(?A∨(C∧?D)∨(?C∧D))∧((?B∧?C)∨(?B∧?D)∨?C∨(?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∧?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)∨(?B∧C∧?D)∨(?C∧D ∧?B)∨(?C∧D)
(?A∧?C)∨(?B∧C∧?D)∨(?C∧D)
T
Entonces hay tres escuelas: B∧D, A∧C, A∧D.
(15) Utilice la lógica de predicados para construir la siguiente prueba: cada miembro de la conferencia académica es un experto y trabajador, y algunos miembros son jóvenes, por lo que algunos miembros son jóvenes expertos.
Solución: Universo: el conjunto de todas las personas.
(): experto (): trabajador; (): persona joven; la forma de razonamiento es:
( ( )∧ ( )), ( ) ( ( )∧ ( ))
Da la siguiente prueba:
(1) ( ) P
(2) (c) T(1), ES
(3) ( ( )∧ ( )) P
(4) ( c)∧ ( c) T(3), Estados Unidos
(5) ( c) T(4), I
(6) ( c)∧ (c) T(2)(5), I
(7) ( ( )∧ ( )) T(6), por ejemplo
(7) p>
3. (10 puntos) Supongamos que A, B y C son tres grupos, ¿entonces A? B(B? Respuesta.
Prueba: a? Bx(x∈A→x∈B)∧?x(x∈B∧x?A)x(x?A∨x∈B)∧ ?x(x∈B∧x? Respuesta
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)∧? , 5}, R es una relación binaria en A, R = {
Solución r (r) = r ∪ ia = {
s(R) = R∪R- 1 = {lt;2,1 gt;,lt2,5>,lt2,4>,lt3,4>,lt4,4>,lt5,2>,lt1,2 gt;,lt4,2 >,lt4,3 >}
R2 = {lt;2,2 gt;,lt2,4>,lt3,4>,lt4,4>,lt5,1 gt;,lt5,5> ,lt5,4> }
R3 = { lt2, 1 >, lt2, 5 >, lt2, 4 >, lt3, 4 >, lt4, 4 >, lt5, 2 >, lt5, 4 > }
R4 = {lt; 2, 2 gt;, lt2, 4 >, lt3, 4 >, lt4, 4 >, lt5, 1 gt;, lt5, 5 >, lt5, 4 >} =R2
t(R)= Ri = {lt;2,1 gt;, lt2,5>, lt2,4>, lt3,4>, lt4,4>, lt5,2>, lt2,2 gt ;, lt5, 1 gt;, lt5, 4 >, lt5, 5 >}.
(10 puntos) R es una relación binaria en un conjunto no vacío a. simétrico, entonces r(R) Simétrico con t(R).
Se demuestra que para cualquier x, y∈A, si xr(R)y, entonces r (r) = r ∪ ia, Se obtiene xRy o xIAy. IA es simétrica, por lo que existe yRx o yIAx, por lo que yr (r) x . Entonces r (r) es simétrico.
Lo siguiente demuestra que es simétrico con respecto a cualquier entero positivo. n, r n
Porque R. Simétrico, entonces xR2yz(xRz∧zRy)z(zRx∧yRz)? es simétrico.
Para cualquier x, y∈A, si xt(R)y, existe m tal que xRmy, entonces existe yRmx, es decir, existe yt (r) X. Por lo tanto, t(R ) es simétrico.
(10 puntos) Si F: A → B es una biyección, entonces F-1: B → A es una biyección.
Está demostrado que F: A → B es biyectiva, entonces F-1 es la función de B a A..F-1 es biyectiva.
Para cualquier x∈A, debe haber y∈B tal que f (x) = y, por lo que f-1 (y) = x, por lo que f-1 es sobreyectiva.
Para cualquier y1 e y2∈B, si f-1(y 1)= f-1(y2)= x, entonces f (x) = y1, f (x) = y2. Dado que f: a → b es una función, entonces y1 = y2. Entonces f-1 es inyectivo.
Resumiendo, F-1: B → A es biyectivo.
7. (10 puntos) Conjuntos
Demuestra que como
Debido a que s es un conjunto finito, debe haber j > I, entonces = sea p = j-i, Entonces = *. Entonces para q≥i, tenemos = *.
Debido a que p≥1, k≥1 siempre se puede encontrar, entonces KP ≥ I. Para ∈S, hay = * = * (*) = … = *.
Supongamos a =, entonces a∈S y a*a = a.
8. (20 puntos) (1) Si G es un gráfico plano conexo y el grado de cada cara de G es al menos l (l≥3), entonces el número de aristas m de G y el número de nodos n Existe la siguiente relación:
m≤ (n-2).
Se demuestra que si G tiene r caras, entonces 2m= ≥lr. Según la fórmula de Euler, n-m r = 2. Por tanto, m ≤ (n-2).
(2) Programa de diseño G =
Demostrar G * =
Preguntas de prueba de matemáticas discretas (Prueba B y respuestas)
I (10) Demuestre que (P∨Q)∧(P?R)∧(Q?S) S∨R
Demuestre que porque S∨RR? s, por lo tanto, es necesario demostrar que (P∨Q)∧(P?R)∧(Q?s)? r? s.
(1)?rPremisas adicionales
(2)P? R P
(3)?P T(1)(2), I
(4)P∞Q P
(5)Q T(3)(4 ), pregunté
(6)? Standard & Poor's
(7) Artículo 5, apartado 6, punto 1
(8)?r? S CP
(9)S∞R T(8), E
(15) Según la teoría del razonamiento, está demostrado que todo candidato es diligente o inteligente, y todo diligente personas Todos marcarán la diferencia, pero no todos los candidatos marcarán la diferencia, por lo que algunos candidatos deben ser inteligentes.
Supongamos P (E): E es candidato, Q (E): E sabe hacer las cosas, A (E): E es diligente, B (E): E es inteligente, y el dominio personal es 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), EE.UU.
(9)A(A)∞B(A)T(8)(5), I
(10 )?x(A(x)?Q(x)) P
(11)A(a)? Estados Unidos Q(a) T(10)
(12) ? A(a) T(11)(6), I
(13)B(a) T(12)(9), I
(14)P(a) ) ∧B(a)T(5)(13), I
(15)?x(P(x)∧B(x)) T(14), por ejemplo
(10) Hay 25 estudiantes en una clase, 14 de ellos pueden jugar baloncesto, 12 pueden jugar voleibol, 6 pueden jugar baloncesto y voleibol, 5 pueden jugar baloncesto y tenis, 2 pueden jugar estos tres tipos de pelotas y 6 pueden jugar baloncesto. Las personas que juegan tenis pueden jugar otro tipo de pelota. Pregunte el número de estudiantes que no pueden jugar estos tres tipos de pelotas.
Las soluciones A, B y C representan el conjunto de estudiantes que. puede jugar voleibol, tenis y baloncesto respectivamente. Entonces:
|A|=12, |B|=6, |C|=14, |A∩C|=6, |B∩C|. =5, |A∩B∩C|= 2, |(A∩C)∩B | = 6.
Porque |(A∩C)∩B | B∩C)| = |(A∩B )| |(B∩C)|-| A∪B∪C | 20 = 5. No sé jugar.
4. (10 puntos) Si A1, A2 y A3 son subconjuntos del conjunto completo U, entonces el conjunto con forma Ai (Ai? ? es Ai o) se llama A1, Los elementos generados por A2 y A3 Se demuestra que el conjunto de todos los elementos no vacíos generados por A1, A2 y A3 constituye una división del conjunto completo u. p>Hay ***8 elementos de prueba, r. Elementos no vacíos s1, s2,..., sr (r≤8).
Para cualquier a∈U, entonces uno de a∈. Ai o a∈ deben ser verdaderos. ¿Es Ai o lo contiene? ¿El elemento a∈Ai? Entonces, ¿obviamente hay si? sq. sp≠sq, debe haber un Ai y aparecerá en sp y sq respectivamente, entonces SP ∩ SQ =?
En resumen, {s1, s2,...,sr} es uno. de u. Divide.
5. (15 puntos) Supongamos que R es una relación binaria en A, entonces: ¿R es transitivo? ¿R*R? r .
Demuestre (5) Si R es transitivo, entonces
Por otro lado, si R*R? r, para cualquier x, y, z∈A, si xRz y zRy, entonces
6 (15 puntos) Si G es un plan conexo, entonces N-M R = 2, donde N, M, R. respectivamente es el número de nodos, aristas y caras de G.
Se demuestra que el número de lados m de g es inducido.
Cuando m = 0, debido a que G es un gráfico conexo, G es un gráfico trivial. En este momento, n = 1, r = 1, la conclusión se establece naturalmente.
Suponiendo que el número de aristas es menor que m, la conclusión del gráfico conectado es válida. Consideremos el caso en el que el número de aristas de un gráfico plano conectado G es m.
Supongamos que e es una arista de g. ¿Cuál es el símbolo que se obtiene al eliminar e de g? ¿Y supongamos que el número de nodos, aristas y caras es n? ,¿metro? ¿Qué pasa con r? . e se divide en las siguientes situaciones para discutir:
Si e está podando, entonces g? Hay dos ramas conectadas G1 y G2. El número de nodos, aristas y caras de Gi son ni, mi y ri respectivamente. ¿Obviamente N1 N2 = n? =n，m1 m2=m? =m-1，r1 r2=r? 1=r 1. Supongamos por inducción que existen N1-M1 R1 = 2 y N2-M2 R2 = 2, entonces (n 1 N2)-(m 1 M2) (r 1 R2).
Si e no corta bordes, entonces n? =n,m? =m-1,r? = r-1, suponiendo que haya n por inducción? -¿metro? r? = 2, entonces n-(m-1) r-1 = 2, es decir, n-m r = 2.
Según la inducción matemática se establece esta conclusión.
7. (10 puntos) Supongamos que la función g: a → b, f: b → c, entonces:
(1) La niebla es una función de a a c;
p>
(2)Para cualquier x∈A, niebla (x) = f (g (x)).
Se demuestra que (1) para cualquier x∈A, debido a que G: A → B es una función, entonces existe y∈B hace
Para cualquier x∈A, si y1 e y2 ∈C existen, entonces < x, y 1 gt;, ltx, y2 gt∈ fog = g * f, entonces t1 existe, lo que hace
En resumen, la niebla es de a a función c.
(2) Para cualquier x∈A, g: a → b es un conjunto con
Ocho, (15 puntos)
Se demuestra que para cualquier a∈G, debe haber un -1 ∈ g tal que a-1 * a = e ∈ h, entonces < a, a gt∈R.
Si
Si
En resumen, r es una relación de equivalencia en g.
Para todos, hay