Final de matemática discreta. U.T.N.F.R.B.A.

(Cátedra Lic. María Hortensia Arriola)

04 / 03 / 03

EN TODOS LOS EJERCICIOS RECUADRAR LA ÚNICA RESPUESTA CORRECTA. EL EXAMEN SE APRUEBA CON AL MENOS 9 (NUEVE) RESPUESTAS CORRECTAS. SOLO SE SUMAN LAS RESPUESTAS CORRECTAS, LAS INCORRECTAS NO RESTAN PUNTOS.

1. La cantidad de formas en que se pueden distribuir, en forma ordenada, once personas en dos mesas circulares con seis y cinco asientos respectivamente es de:

2. Sea el conjunto de pares de palabras (p, q) donde la palabra p es una palabra de 10 letras que se obtiene permutando las letras de la palabra elecciones y la palabra q es una palabra de 9 letras obtenida permutando las letras de la palabra alteradas. La cantidad de pares de palabras (p, q) tal que p comienza con "e" y q comienza con "s" es de:

3. De los esquemas de proposiciones categóricas:

p 1: $ x: (p(x) Ù q(x)), p2:" x:(q(x) ® r(x)) definidas en un dominio D, no se desprende en forma válida C:

4. Lo indicado justifica la verdad de la proposición definida en R:

" x: $ y:

5. La familia Barrionuevo, luego del bochorno acontecido en Catamarca, decide tomarse unos días en la playa. Esta familia está compuesta por el padre (x), la madre, un hijo (y) y dos hijas (z y t). Al bañarse, la familia tiene las siguientes precauciones: como a la madre no le gusta demasiado el agua, solo se baña cuando el padre no se baña y el hijo o alguna hija se baña o bien, cuando el padre se baña, las dos hijas se bañan y no se baña el hijo.

La expresión que indica cuando se baña la madre tiene:

6. Es posible que en algún Álgebra de Boole, $ a: $ b: $ c tal que no se cumpla lo indicado:

 7. Dada R Í A x A. y R ¹ Æ : R es simétrica si y sólo si:

8. Dada M = M (R) = con R Í A x A y A = {x, y, z, t}

9. Sea el conjunto X = { I2, I3, I4, I5, I6,….}= {In / n Î N > 1 } con In = {k. n / k Î Z} ordenado por la relación: In R Im sii In Í Im. Los elementos maximales del conjunto son:

10. Dada la relación de equivalencia definida en R2: (a, b) R (c, d) sii a2- b2 = c2-d2, la clase de equivalencia del par (0 0):

11. " a, b, c Î Z : MCD {a, b, c} = (a, b, c) es igual a:

12. " a Î Z :si a Ï y a Ï entonces:

13. En todo árbol no trivial:

14.Sea el grafo simple G cuyos vértices son los elementos del conjunto D30, de modo que dos vértices v y w son adyacentes sii (v, w) = 1

15. La Cantidad de componentes conexas que debe tener un grafo con 1200 vértices, 1000 aristas y sin ciclos es de:

FINAL DE MATEMÁTICA DISCRETA. U.T.N. 1 / 6 / 02.

1.Realizar las siguientes acciones:

a. Demostrar que dado un grafo conexo no Euleriano con 35 vértices entre los cuales veinte vértices son de valencia impar y quince vértices son de valencia par, es posible agregar sólo un vértice junto con algunas aristas que partan de ese nuevo vértice y vayan a los vértices anteriores de tal manera que el nuevo grafo sea Euleriano.

b. A partir de las premisas: p1: $ x:(p(x) Ù q(x)) y p2: " x:( r(x) ® (~ p(x) Ù ~q(x))), determinar una conclusión válida no coincidente con las premisas (probar la validez del razonamiento obtenido mediante el uso de reglas de inferencia)

2. Responder en forma justificada a los siguientes interrogantes:

a. Si se considera un curso de 150 alumnos:

¿De cuántos modos se los puede distribuir en 4 aulas si el aula 406 tiene 35 asientos, cada aula tiene por lo menos 20 alumnos , los alumnos no pueden estar parados y las restantes aulas son lo suficientemente grandes como para albergar a todos? (no interesa distinguir las personas)

b. .¿Es posible que un conjunto ordenado (A, R) con admita máximo diferente del supremo?

c. ¿Puede asegurarse que si un número primo divide al producto de dos enteros no nulos divide al menos a uno de ellos?

3. Analizar el valor de verdad de las siguientes afirmaciones (justificar la respuestas):

a. Dado un conjunto B = {a1, a2 ,a3,…, an } con n Î N ³ 4 y el grafo Gn cuyos vértices son todos los subconjuntos de dos elementos de B en el cual los vértices son adyacentes únicamente en el caso que sean disjuntos: |V| = y |A| =

b. Es posible determinar algún álgebra de Boole en el cual : ⊀

c. Cada clase de equivalencia cl((a, b)) (con a ¹ b) correspondiente a la relación S definida en R2 en la forma: (x, y) S (z, t) sii (x – y)2 = (z – t)2 , está constituida por dos rectas paralelas.

Observaciones

• Para aprobar el examen se necesita resolver correctamente cuatro ítems.
• Al terminar el examen podrás ver la resolución del mismo en cartelera
• Recordá que podés aclarar tus dudas suscribiéndote al grupo de consulta

RESOLUCIÓN FINAL DE MATEMÁTICA DISCRETA.

U.T.N.F.R.B.A 01 / 06 / 02.

1.

a. Dado que un grafo es Euleriano si y sólo si es conexo y admite "0" o "2" vértices de valencia impar, al agregar un vértice (v), para mantener la conexidad bastará conectarlo a cualquiera de los vértices del grafo dado y para forzar el cumplimiento de la segunda condición enunciada, se podrá por ejemplo:

• Agregar 20 aristas que conecten el vértice "v" con los 20 vértices de valencia impar para que de este modo todos los vértices tengan valencia par ("0" vértices de valencia impar)
• Agregar 18 aristas que conecten el vértice "v" con 18 de los 20 vértices de valencia impar para que de este modo queden 2 vértices de valencia impar y 33 vértices de valencia par.

b. Para conjeturar una conclusión válida, convendrá asociar a cada uno de los esquemas proposicionales los conjuntos de verdad respectivos y vizualizar las premisas a través de diagramas de Venn:

p(x) P = {a / v(p(a)) = V}

q(x) Q = {a / v(q(a)) = V}

r(x) R = {a / v(r(a)) = V}

De este modo:

• la primera premisa: p1: $ x:(p(x) Ú q(x)) nos dirá que P È Q ¹ Æ sii

P ¹ Æ o Q ¹ Æ

• la segunda premisa: p2: " x:( r(x) ® (~ p(x) Ù ~q(x))) nos dirá

que R Ì

En consecuencia se podría inferir en forma válida (por ejemplo): $ x: ~r(x)

Hagamos una prueba formal:

1. $ x:(p(x) Ú q(x)) (premisa)

2. p(a) Ú q(a) (particularización existencial en 1.) ("a" es una constante determinada del universo de definición)

3. " x:( r(x) ® (~ p(x) Ù ~q(x))) (premisa)

4. r(a) ® (~ p(a) Ù ~q(a)) (particularización universal en 3.)

5. r(a) ® ~ (p(a) Ú q(a)) ) (ley de De Morgan en 4.)

6. (p(a) Ú q(a)) ® ~ r(a) (contrarecíproco en 5. )

7. ~ r(a) (modus ponens (2, 6)

8. $ x:( ~ r(x)) (generalización existencial en 7.)

2.

a. Dado que de entrada hay que distribuir 20 alumnos en cada aula:

|||

restarán distribuir 150 – 80 = 70 alumnos.

Ahora bien como en el aula 406 no entran más de 35 alumnos la cantidad de alumnos (de los setenta que hay que distribuir) que podrán ir en esa aula será x con 0£ x £ 15 . Las situaciones extremas serían las indicadas:

||| |||

En consecuencia restarán distribuir 70 – x = n con 55£ n £ 70 alumnos en las tres aulas restantes. De donde tomando como modelo de conteo la idea de puntos ( n puntos representativos de los alumnos por distribuir) y barras (2 barras representativas de las tres aulas restantes), el número buscado estará dado por la suma:

b. NO ES POSIBLE , dado que si un conjunto ordenado tiene máximo (M), este coincide con el supremo:

Habrá que probar que:

i)."M" es cota superior de A

ii). si C es cota superior de A. entonces M ≼ C

D/

i) : máximo de A≼

(definición de máximo / definición de cota superior)

ii) C es cota superior de A≼ CM ≼ C

(definición de cota superior / M)

c. SÍ, PUEDE ASEGURARSE

Si y p es primo entonces o

D /

• Si nada habrá que probar
• Si p ∤ a, habrá que probar que

. Dado que p es primo y p ∤ a necesariamente (a,p) = 1 = s.a + t.p con s y t enteros. Entonces multiplicando por "b "ambos miembros quedará

b = s(a.b) + (b.t) p s. (kp) + (b.t) p = (s.k + b.t).p con lo cual

3.

a. VERDADERA

D /

• Dado que los vértices son subconjuntos de dos elementos tomados de un conjunto de n elementos, efectivamente |V| =
• Dado que los vértices adyacentes son aquellos subconjuntos de dos elementos que no tienen elementos en común, el grafo será regular y la valencia o grado de cada vértice será

(para hallar los vértices adyacentes a uno dado (conjunto de dos elementos: x e y) bastará quitar del conjunto de vértices "x" e "y" y determinar todos los conjuntos de dos elementos del conjunto restante).

Si ahora se tiene en cuenta que en todo grafo , de acuerdo a lo dicho anteriormente quedará:

sii |A| =

b. FALSA

Teniendo en cuenta que toda álgebra de Boole está ordenada a través de la relación de orden: x ≼ y sii x + y = y, resultará:

x. (y +z) + = (x + x. (y +z)) + = x + =

(ley asociativa – ley conmutativa / ley de absorción / ley conmutativa)

con lo cual x. (y +z) ≼

c. VERDADERA

De acuerdo a la definición de la relación:

Cl((a, b)) = { (x, y) / (x, y) S (a, b)} y como

(x, y) S (a, b) sii (x – y)2 = (a – b)2 sii x –y = a – b o x – y = b – a sii

y = x – (a –b) o y = x – (b –a) quedará:

Cl((a, b)) = { (x, y) / y = x – (a –b) o y = x – (b –a)} y efectivamente quedarán (si a ¹ b) dos rectas paralelas de pendiente "1" y ordenadas al origen opuestas entre sí.

FINAL MATEMÁTICA DISCRETA 5 / 12 / 02

EJERCICIO Nº 1

Realizar las siguientes acciones:

a. Analizar la validez del siguiente razonamiento (probar o refutar su validez)

Todos los créditos bancarios para compra de inmuebles tienen un plazo de cancelación de 10 años. Algunos créditos para compra de inmuebles tienen un interés mensual del 8%. Por lo tanto todos los créditos bancarios tienen un interés mensual del 8% y un plazo de cancelación de 10 años.

b. A través del uso de propiedades de congruencias, hallar resto ((3.94 + 115.5 -35) :10)

c. Hallar el conjunto mayorante (cotas superiores) -supremo y minorante (cotas inferiores) –ínfimo del conjunto X = Í R2 ordenado a través de la relación definida en R2 en la forma: A R B sii aij ≤ bij " i, j

EJERCICIO Nº 2

Responder a los siguientes interrogantes:

a. ¿Qué forma tiene la matriz de adyacencia de un grafo completo Kn y la matriz de adyacencia de un grafo bipartido completo Km,n.

b. ¿Porqué puede asegurarse que la siguiente afirmación no es tautológica?

En toda Algebra de Boole y cualquiera sea el valor de a, b y c:

a + ( b . c ) a + (b.) Þ c =

c. ¿Puede asumirse el conjunto A = {cl ((0, y)) / y ³ 0}como conjunto cociente correspondiente a la relación de equivalencia definida en R2 :

(a, b) S (c, d) sii |4.a – b| = |4.c – d|?

EJERCICIO Nº 3

¿Verdadero o falso? (justificar)

a. La cantidad de soluciones enteras de la ecuación: x + y + z = 21

con x > 1, y > 4, z > 5 es 45.

b. Si se considera el grafo indicado a través de la tabla de pesos , hay por lo menos tres árboles generadores mínimos distintos del mismo (hallarlos mediante aplicación de algoritmo adecuado).

RESOLUCIÓN FINAL MATEMÁTICA DISCRETA 05 / 12 / 02

EJERCICIO N º 1

a. En U = { x / x es crédito bancario}con :

i (x) : x es crédito para compra de inmuebles

c(x): x es crédito cancelable a 10 años

o(x): x es crédito con interés mensual del 8%

el esquema de razonamiento quedará en la forma:

" x: (i (x) ® c(x)); $ x:(i (x) Ù o(x)) " x: (c (x) Ù o(x))

Ahora entonces si se visualizan las premisas mediante el uso de diagramas de Venn asociando un conjunto a cada forma proposicional (el conjunto de verdad de dicha forma proposicional):

i (x) « I

c (x) « C

o (x) « O

se podría ver que el razonamiento es inválido:

Bastará entonces hallar una interpretación que muestre claramente que cabe la posibilidad de que las premisas sean verdaderas y la conclusión falsa.

Por ejemplo:

Sobre U = R,

i (x) : x > 10

c(x): x > 5

o(x): x 18

V(premisa 1) = V

(por definición de "ser mayor que" y considerando que 10 >5)

V(premisa 2) = V (por ejemplo 15 satisface la conjunción).

V(conclusión) = F (por ejemplo 20 no satisface la conjunción)

b. Para determinar el resto de la división planteada (con congruencias), convendrá tener en cuenta las siguientes propiedades relativas al conjunto de los enteros:

1. " a : a º n r con r : resto (a: n)
2. a º n b Þ a p º n b p
3. a º n b Þ a. c º n b. c
4. a º n b Ù c º n d Þ a + c º n b + c
5. a º n b Ù c º n d Þ a . c º n b . d

Entonces si comenzamos considerando las potencias que intervienen en el enunciado se podrá observar lo siguiente:

i. 94 = 92. 92 y como 92 = 81 y 81º 10 1 , resultará 94 º 10 1

  en consecuencia por (3) : 3.94 º 10 3

ii. 11º 10 1 , de donde 115 º 10 15 º 10 1

 en consecuencia por (3): 115. 5 º 10 5

iii. por (1): –35 º 10 5 (-35 = (-4). 10 + 5)

Finalmente por (4) quedará: 3.94 + 115.5 -35 º 10 3 + 5 + 5 º 10 13 º 10 3

 De donde Resto ((3.94 + 115.5 -35): 10) = 3

c. Quizás convenga hacer el diagrama de Hasse restringido a X:

Si se considera :

A : , B: , C: el diagrama quedará:

 Para ver el gráfico seleccione la opción "Descargar" del menú superior

 Y entonces:

X* = con supremo:

X* = con ínfimo:

EJERCICIO Nº 2

a.

1. Teniendo en cuenta la definición de grafo completo con n vértices: grafo simple (sin lazos ni aristas paralelas) con la particularidad que cada vértice es adyacente a los restantes), la matriz de adyacencia de Kn será una matriz cuadrada de orden n, tendrá 0`s en la diagonal principal y 1’ s fuera de la diagonal principal.

2. Teniendo en cuenta la definición de grafo bipartido completo K m, n

con m + n vértices : grafo simple (sin lazos ni aristas paralelas) con la particularidad que cada vértice de V 1 (|V 1 | = m) es adyacente a los vértices de V 2 (|V 2 | = n), la matriz de adyacencia de K m, n será una matriz cuadrada de orden m + n, de la forma indicada:

b.

Si se tiene en cuenta que en toda álgebra de Boole no existen elementos que coincidan con su complemento, el consecuente del condicional planteado será falso para cualquier asignación de valores a " c". Bastará entonces indicar algún álgebra de Boole y valores específicos a las variables a, b y c de modo que el antecedente sea verdadero. Con esto quedará probado que el enunciado no es tautológico.

Sea por ejemplo:

A = (P({1,2, 3}), È , Ç , ` , Æ , {1,2,3}) con a = b = Æ y c = {1}

Efectivamente:

a + ( b . c ) = Æ È (Æ Ç {1}) = Æ

a + (b.) = Æ È ((Æ Ç {2,3}) = Æ

con lo cual Æ Í Æ es verdadero (recordar que en esta álgebra de Boole : Í

c.

Si consideramos las clases de equivalencia correspondientes a la relación de equivalencia indicada, quedará:

Cl ((a, b)) = {(x, y) Î R2 / |4. x – y| = |4. a – b|} y teniendo en cuenta que:

|4. x – y| = |4. a – b| sii 4. x – y = 4. a – b o 4. x – y = – 4. a + b sii

y = 4. x + (b – 4. a) o y = 4. x + ( 4. a – b), quedará:

Cl ((a, b)) = {(x, y) Î R2 / y = 4. x + (b – 4. a) o y = 4. x + ( 4. a – b)}

(o sea que cada clase consta de dos rectas con pendiente = 4 y ordenada al origen variable en función de a y b siempre que b ¹ 4.a en cuyo caso se reduce a un sóla recta, la recta de ecuación: y = 4.x

Entonces como para armar el conjunto cociente habrá que elegir un representante de cada clase, se puede optar por elegir como representante al punto intersección con el eje positivo de las ordenadas, incluyendo también al (0, 0) como representante de la recta y = 4.x, tal como se propone en el enunciado.

EJERCICIO Nº 3

a. VERDADERO

Dado que el problema se reduce al de distribuir objetos idénticos (en este caso 21 unidades) en casilleros (en este caso tres casilleros asociadas a las tres variables que entran en juego) y con la consideración que x > 1, y > 4, z > 5, el estado de situación será el siguiente:

· · | · · · · · | · · · · · ·

 con lo cual restan distribuir 21 – (2 + 5 + 6) = 8 en tres casilleros (dos barras) y la respuesta entonces estará dada por el númeor combinatorio

b. VERDADERO

Efectivamente por aplicación de algoritmo de Prim, pueden hallarse por lo menos tres árboles generadores mínimos diferentes de peso = 6. Mostremos en detalle la construcción de los mismos:

Consultas – dudas: matemdiscreta[arroba]gruposyahoo.com.ar

 FINAL DE MATEMÁTICA DISCRETA. U.T.N. 12 / 12 / 02.

EJERCICIO Nº 1. ¿Verdadero o falso? (justificar)

a. Los dos grafos de la figura

Para ver el gráfico seleccione la opción "Descargar" del menú superior

son isomorfos pues tienen el mismo número de vértices y de aristas.

b. Es posible determinar un subconjunto no vacío S de modo tal que el álgebra de Boole

(P(S),È , Ç , ` ,Æ , S) sea isomorfa al álgebra de Boole (D 30, +, · , ` , 1, 30)

c. Se puede asumir el conjunto A = como conjunto cociente correspondiente a la relación de equivalencia definida en R2 x 2 : A S B sii Traza (A) = Traza (B)

(Recordar que la traza de una matriz está dada por la suma de los elementos de la diagonal principal).

EJERCICIO Nº 2. Responder en forma razonada a los siguientes interrogantes:

1. ¿Es posible hallar al menos un árbol generador del grafo indicado, que tenga sólo tres puentes y cuatro puntos de articulación (o puntos de corte)?

Para ver el gráfico seleccione la opción "Descargar" del menú superior

b. Si se considera el esquema de razonamiento:

" x: P(x) ® $ x: P(x), $ x: (P(x) Ù Q(x)), $ x: (Q(x) Ù R(x)) ∴ $ x: (P(x) Ù R(x)) y la interpretación:

U = ℝ, P(x) : |x| > 4, Q(x):x2 < 25 R(x): |x| ≤ 4

¿puede afirmarse si la conclusión es válida o no?

c. Para dar el examen de matemática discreta del día 12/12, un alumno de primer año de sistemas dedicó 30 hs de estudio a lo largo de diez días y a partir del 3 / 12. ¿De cuántas formas pudo distribuir las horas de estudio (se supone que cada día lo ha hecho un número entero de horas) si el martes 4/ 12 no pudo estudiar porque tuvo fiebre y el fin de semana por lo menos le dedicó 2 hs cada día?

EJERCICIO Nº 3. Demostrar:

a. en Z: (a, b) = d Û (d | a Ù d | b Ù (a|d, b|d) = 1

b. que si el conjunto ordenado (A, ≼) ,con A Í B, tiene un máximo : x, entonces x coincide con el supremo. 

RESOLUCIÓN FINAL DE MATEMÁTICA DISCRETA . 12 / 12 / 02

EJERCICIO Nº 1.

a. FALSO

Si bien es cierto que los grafos tienen la misma cantidad de vértices (6) y de aristas (9), estas son condiciones necesarias pero no suficientes para que los grafos sean isomorfos. Si se observa las valencias de los vértices, el primer grafo tiene dos vértices de valencia 4 mientras que el segundo grafo tiene

tres vértices de valencia 4.El hecho de encontrar un atributo no invariante en los mismos permite afirmar que no son isomorfos.

b. VERDADERO

Teniendo en cuenta que D30 = {1, 2, 3, 5, 6, 10, 15, 30}y que a partir de los factores primos de este conjunto se podrán obtener los restantes (recordar que todo elemento de este conjunto será de la forma 2a.3b.5c con a, b y c Î {0,1}, el conjunto buscado será por ejemplo S = {2, 3, 5} con |P(S)| = 8 = | D 30| y un isomorfismo posible:

Observación:

• Dado que toda álgebra de Boole está ordenada, si confeccionáramos los diagramas de Hasse correspondientes (D30 ordenada por la relación " es divisor de " y P(S) ordenada por la relación "está incluido en") veríamos que son idénticos, lo que garantiza que se cumplan las condiciones:

f(x + y ) = f(x) + f(y) y f(x. y) = f(x). f(y)

• Por otra parte como los neutros se corresponden, se cumplen las condiciones: f(0A) = 0B y f(1A) = 1B
• Finalmente la función definida resulta ser biyectiva.

De lo dicho se arriba a que efectivamente f es isomorfismo

c. FALSO

Dado que la traza de las matrices tomadas como "supuestos representantes" de las distintas clases de equivalencia resulta ser un número real positivo, no representan a las matrices con traza negativa como por ejemplo a la matriz de traza = -3 + 0 = -3, con lo cual el conjunto definido no puede asumirse como conjunto cociente.

EJERCICIO Nº 2.

a. NO ES POSIBLE

Esto se debe al hecho de que si bien es posible hallar más de un árbol generador del grafo indicado, todas las aristas de un árbol son puentes, en este caso habrá exactamente 11 puentes (12 extremos) con la particularidad de que sus extremos o bien son hojas o bien puntos de corte. Así podrás hallar por ejemplo árboles generadores con 3 hojas y 9 puntos de corte o bien árboles generadores con 4 hojas y 8 puntos de corte por ejemplo.

b. PUEDE AFIRMARSE QUE LA CONCLUSIÓN NO ES VÁLIDA, debido a que con la interpretación indicada las premisas resultan ser verdaderas y la conclusión falsa, condición necesaria y suficiente para afirmar que el esquema de razonamiento es inválido.

• V (p1: " x: P(x) ® $ x: P(x)) = V

En realidad esta premisa " x: P(x) ® $ x: P(x), es verdadera cualquiera sea la interpretación considerada: si todos las constantes del universo de definición son raíces del esquema proposicional P(x), en particular alguna constante es raíz de P(x).

• V (p2: $ x: (P(x) Ù Q(x))) = V

Por ejemplo la constante a = 4.5 es raíz del esquema P(x) Ù Q(x)

• V (p3: $ x: (Q(x) Ù R(x)))) = V

Por ejemplo la constante a = 0 es raíz del esquema Q(x) Ù R(x)

• V (C: $ x: (P(x) Ù R(x))) = F

Esto se debe a que P(x) º Ø R(x)

c. Si se considera la idea de " distribución de elementos indistinguibles en cajas" (visualizadas a través de puntos y barras), en este caso los elementos indistinguibles serán las horas de estudio (30 horas: 30 puntos) y las cajas serán los días de estudio (10 días : 9 barras). En consecuencia como el martes 4 no pudo estudiar por la fiebre, el casillero correspondiente estará vacío y como el sábado y el domingo estudió al menos 2 hs, en las cajas correspondientes se pondrá de entrada dos puntos. De este modo el esquema de análisis será entonces:

|vacío | | | · · | · · | | | |

Y entonces restarán distribuir 30 – 4 = 26 horas (26 puntos) en 9 días (8 barras). La respuesta a esta cuestión la dará el número:

EJERCICIO Nº 3.

a.

D /

Þ ) H ) (a, b) = d T ) d | a Ù d | b Ù (a|d, b|d) = 1

D /

Como de la hipótesis y por definición de máximo común divisor se desprende en forma inmediata que d | a Ù d | b, restará probar que a|d, b|d) = 1

De la hipótesis y por propiedad del máximo común divisor, existen enteros s y t de modo tal que: d = s. a + t. b.

Dividiendo ambos miembros por d quedará: 1 = s. (a/d) + t. (b/d) lo que por teorema de Bézout significa que (a|d, b|d) = 1

Ü )

H ) d | a Ù d | b Ù (a|d, b|d) = 1

T ) (a, b) = d sii

Como de la hipótesis se desprende i), resta probar ii):

Por Teorema de Bézout e hipótesis: existen enteros s y t de modo tal que:

1 = s.(a/d) + t. (b/d) lo que significa (multiplicando ambos miembros por d) que d = s. a + t. b.

Ahora bien de x | a Ù x| b se desprende (propiedad de divisibilidad):

x | a. s Ù x| t. b y de esta afirmación a su vez se desprende (propiedad de divisibilidad) que x | a. s + t. b. En consecuencia x | d

b.

Habrá que probar que:

i)."x" es cota superior de A

ii). si c es cota superior de A. entonces x ≼ c

D/ i). : máximo de AÛ " a Î A: a≼ x Þ x: cota superior de (A, ≼)

(definición de máximo / definición de cota superior)

ii). c es cota superior de A Û " a Î A: a≼ c Þ x≼ c

(definición de cota superior / x)