Álgebra y

Matemática

Discreta

Curso: 1º

Ingeniería Técnica Informática de Sistemas

Universidad de Las Palmas de Gran Canaria

Lógica Proposicional

Término: Sinónimo de palabra (con significado propio o no).

Proposición Lógica: Agrupación de términos de la que se puede averiguar si su contenido es verdadero o falso. Ej: “La mesa es redonda” ; “3 + 2 = 5”

Clasificación

Atómicas: Si no puede subdividirse en otras proposiciones más pequeñas y siempre son afirmativas. Ej: “Está lloviendo” ; “3 + 2 = 5”

Moleculares: Pueden subdividirse en otras proposiciones enlazadas y/o modificadas por algunos términos. Ej: “Llueve y es de día”

“La mesa no es redonda” “No la mesa es redonda” Molecular

Conectores Proposicionales

Términos usados para enlazar y/o modificar.

1. Negación: NO Símbolo: ¬ Conector monádico

2. Conjunción: Y y Símbolo: "

3. Disyunción No Exclusiva: o Símbolo: "

4. Disyunción Exclusiva: o o Símbolo: 

5. Condicional: si entonces Símbolo: !

6. Bicondicional: si y sólo si Símbolo: !

Del 2 al 6 son conectores Diádicos.

Formulación Algebraica

Para las proposiciones atómicas se utilizan variables proposicionales que van de la p a la z.

Para las moleculares se utilizan fórmulas lógicas que van de la P a la Z.

“Está lloviendo” = p “Si llueve entonces me mojo” = Q

Valor Lógico de una Proposición: 0 cuando es falsa y 1 cuando es verdadera.

Álgebra de Proposiciones

Se encarga de la construcción y estudio de la proposiciones. Se basa en:

Axioma 1: Toda proposición es verdadera o falsa.

Axioma 2: Toda proposición molecular tendrá un valor de verdadero o falso dependiendo de las proposiciones atómicas que la compongan y de los conectores que la modifican y/o enlazan.

Axioma 3: El valor lógico de las proposiciones se establece en unas tablas llamadas “tablas de verdad”.

Reglas de Inferencia

Argumento Deductivo: Conjunto de proposiciones, una de ellas llamada conclusión que se sigue del resto, llamadas premisas.

p ! q premisas

p

q conclusión

p1

p2

.

. [p1, p2, .. , pn] ! C

pn_

C

Un argumento es válido cuando, siendo ciertas las premisas, la conclusión no puede ser falsa.

Deducción Formal

Es una secuencia finita de fórmulas de forma que a partir de las premisas llegamos a la conclusión. Estas fórmulas pueden ser:

Premisas

Supuestos Provisionales: Fórmula que se introduce transitoriamente y ha de ser cancelada antes de llegar a la conclusión.

Fórmulas de Nueva Creación: Fórmulas que se crean a partir de las reglas de inferencia.

• Clasificación

A). Reglas Básicas de Inferencia: El mínimo conjunto de reglas necesario para llevar a cabo cualquier deducción formal. (Gentzen 1934)

Condicional:

De Inserción: Teorema de la Deducción (TD) p

.

.

q____

p ! q

De Eliminación: Modus Ponen (MP). Si el antecedente vale 1, el consecuente

tiene que valer 1.

p ! q

p_____

q

Conjunción:

De Inserción: Producto (Prod). Si “p” vale 1 y “q” vale 1, “p " q” tiene que valer

p

q__

p " q

De Eliminación: Simplificación (Simp) p " q p " q

p q

Disyunción No Exclusiva:

De Inserción: Adición (Ad) p___ q___

p " q p " q

De Eliminación: Casos (Cas) p " q p

.

.

r

q

.

.

r_

r

Negación:

De Inserción: Absurdo (Abs) p

.

.

q " ¬q

¬ p

De Eliminación: Doble Negación (DN) ¬¬ p

p

Bicondicional:

De Inserción: Introducción del Coimplicador (ICO) p ! q

q ! p_

p ! q

De Eliminación: Eliminación del Coimplicador (ECO) p ! q_ p ! q

p ! q q ! p

El símbolo que se utiliza para representar los conectores lógicos se llama conectiva lógica.

Operación Lógica

Es la aplicación de operadores para modificar y/o enlazar proposiciones y generar una nueva proposición.

1. Negación: Se aplica el operador (¬) a una proposición para cambiar su valor de verdad.

p	¬p
1	0
0	1

2. Conjunción: Se aplica el operador (") a dos proposiciones “p " q”. Vale 1 sólo cuando las dos proposiciones valen 1.

p	q	p " q
0	0	0
0	1	0
1	0	0
1	1	1

3. Disyunción No Exclusiva: Se aplica el operador (") a dos proposiciones. Vale 1 cuando al menos una de las variables vale 1.

p	q	p " q
0	0	0
0	1	1
1	0	1
1	1	1

4. Disyunción Exclusiva: Se aplica el operador (ð) a dos proposiciones. Vale 1 cuando sólo una de las variables vale 1.

p	q	p ð q
0	0	0
0	1	1
1	0	1
1	1	0

5. Condicional: Se aplica el operador (!) a dos proposiciones. Vale 1 siempre, excepto cuando el antecedente vale 1 y el consecuente 0.

p	q	p ! q
0	0	1
0	1	1
1	0	0
1	1	1

6. Bicondicional: Se aplica el operador (!) a dos proposiciones. Vale 1 cuando ambas variables tienen el mismo valor lógico.

p	q	p ! q
0	0	1
0	1	0
1	0	0
1	1	1

Ecuaciones

p  q " ¬ (p ! q) p ! q " ¬ (p  q)

Hay que tener en cuenta los paréntesis y darles prioridad.

(p ! q) " (q ! p) = p ! q

p	q	(p ! q) (1)	(q ! p) (2)	1 " 2
0	0	1	1	1		Propiedad indeterminada o
0	1	1	0	0	!	contingente (puede ser
1	0	0	1	0		verdadera o falsa)
1	1	1	1	1

p " ¬p

p	¬p	p " ¬p
1	0	1	!	Tautología (siempre es verdadero)
0	1	1

q " ¬q

q	¬q	q " ¬q
1	0	0	!	Contradicción (siempre es falso)
0	1	0

Se llama implicación tautológica a un condicional tautológico (!).

(p ! q) ! (¬p " q)

REGLAS DERIVADAS

Silogismo (Sil). A ! B

B ! C_

A ! C

Regla de Mutación (Mut). A ! (B ! C)_

B ! (A ! C)

Identidad (Id). _A_

A

Contraposición (CPr). _A_____

B ! A

Dilema (Dil). Dil1. A " B Dil2. ¬A " ¬B

A ! C C ! A

B ! C_ C ! B__

C ¬ C

Dil3. ¬A " ¬B

C ! A

D ! B__

¬C " ¬D

Modus Tollens (MT). A ! B

¬B___

¬A

Introducción Doble Negación (IDN). A____

¬¬A

ECQ. A " ¬A_

B

Silogismo Disyuntivo (SD). A " B

¬A__

B

Principio No Contradicción (PNC) TEOREMA

Teorema: Argumento deductivo con 0 premisas.

PTE: A " ¬A

De Morgan (DM) ¬(A " B)_ ¬(A " B)

¬A " ¬B ¬A " ¬B

Identidad (IDN) __A___ - 1. A

¬¬A 2. ¬A

3. A " ¬A Prod 1,2

4. ¬¬A Abs 2-3

ECQ A " ¬A - 1. A " ¬A

B 2. ¬B

3. A Simp 1

4. ¬A Simp 1

5. A " ¬A Prod 3, 4

6. ¬¬B Abs 2 - 5

7. B DN 6

[(p r) " (q s)] [(p " q) (r " s)]

1. [(p r) " (q s)]

2. p " q

3. p Simp 2

4. q Simp 2

5. p r Simp 1

6. q s Simp 1

7. r MP 5, 3

8. s MP 6, 4

9. r " s Prod 7, 8

10. (p " q) (r " s)

11. [(p r) " (q s)] [(p " q) (r " s)]

PTE: A " ¬A 1. ¬(A " ¬A)

2. A

3. A " ¬A Ad 2

4. (A " ¬A) " ¬(A " ¬A) Prod 3, 1

5. ¬A

6. A " ¬A Ad 5

7. (A " ¬A) " ¬(A " ¬A) Prod 6, 1

8. ¬¬(A " ¬A) Abs 1 - 7

9. A " ¬A DN 8

p r -1. p r 8. s

¬q s -2. ¬q s 9. ¬s SD 3, 6

r " ¬s -3. r " ¬s 10. s " ¬s Prod 8, 9

¬r " t -4. ¬r " t 11. ¬s Abs 8 - 10

¬t -5. ¬t 12. ¬¬q MT 2, 11

¬p " q 6. ¬r SD 4, 5 13. q DN 12

7. ¬p MT 1, 6 14. ¬p " q Prod 7, 13

¬(A " B) - 1. ¬(A " B)

¬A " ¬B 2. ¬(¬A " ¬B)

3. A

4. B

5. A " B Prod 3, 4

6. (A " B) " ¬(A " B) Prod 5, 1

7. ¬B Abs 4 - 6

8. ¬A " ¬B Ad 7

9. (¬A " ¬B) " ¬(¬A " ¬B) Prod 8, 2

10. ¬A Abs 3 - 9

11. ¬A " ¬B Ad 10

12. (¬A " ¬B) " ¬(¬A " ¬B) Prod 11, 2

13. ¬¬(¬A " ¬B) Abs 2 - 12

14. ¬A " ¬B DN 13

(p " q) (s " t) -1. (p " q) (s " t) 9. ¬t MT 2, 8

t r - 2. t r 10. ¬s " ¬t Prod 4,9

¬(r " q) - 3. ¬(r " q) 11. ¬(s " t) DM 10

¬s ¬q 4. ¬s 12. ¬(p " q) MT 1, 11

5. q 13. ¬p " ¬q DM 12

6. ¬r " ¬q DM 3 14. ¬q Simp

7. ¬¬q IDN 5 15. q " ¬q Prod 5, 14

8. ¬r SD 6, 7 16. ¬q Abs 5 - 15

17. ¬s ¬q TD 4 - 16

Conjuntos

Conjunto: Colección o reunión de objetos.

Elemento: Cada uno de los objetos de un conjunto.

Simbología

Mayúsculas Conjunto Minúsculas Elemento

x " A x pertenece o está en A.

Determinación de un Conjunto

a). Por extensión: Citando todos los elementos que caen en el conjunto.

A = {a, e, i, o, u}

b). Por comprensión: dando una propiedad característica (todos se pueden definir por esa característica). A = {vocales}

• Conjunto Vacío: es el conjunto formado por 0 elementos. (")

• Conjunto Unitario: es el conjunto formado por 1 elemento. A = {1} A = {x}

Representación Gráfica

Diagrama de Venn:

a e A a " A

i o x " A

u

Simbología Algebraica

". Cuantificador universal (para todo, para cualquier).

: . “Se verifica que..”

". Cuantificador existencial (existe algún, existe al menos uno...).

". “No existe ningún...”

"!. “Existe un único...”

/. “Tal que...”

!. Implicación lógica

!. “Si y sólo si...”

". “Subconjunto de...” ; “Está incluido en...”

". Conjunción ". Disyunción

Subconjunto

A es subconjunto de B, si todo elemento de A también está en B.

Partes de un conjunto

Sea A " E. !(A) = {S / S " A) A = {x, y} !(A) = {", {x, y}, {x}, {y}}

Igualdad de conjuntos

Dos conjuntos son iguales cuando tienen los mismos elementos:

{1, 2} = {2, 1} {1, 2} " {1, 2, 5} A = B ! A " B " B " A

Operaciones con Conjuntos

Unión: Es un nuevo conjunto formado por añadir elementos que están en A a todos los elementos que están en B.

A = {x, y} B = {z} C = {x, y, z} A " B = A " C = {x, y, z}

A " B = {x " E / x " A " x " B} E

A " A " B B " A " B

Propiedades de la Unión:

1º. A " A = A (Ley de Idempotencia)

2º. A " B = B " A (Conmutativa)

3º. (A " B) " C = A " (B " C) (Asociativa)

4º. A " " = A (" es el elemento neutro)

5º. A " E = E (E es el elemento absorbente)

Intersección: Es un nuevo conjunto formado por todos los elementos que están en A y al mismo tiempo están en B.

A " B = {x " E / x " A " x " B} E

A " B = "

Conjuntos disyuntos (no tienen ningún elemento en común)

Propiedades de la Intersección:

1º. A " A = A (Idempotencia)

2º. A " B = B " A (Conmutativa)

3º. (A " B) " C = A " (B " C) (Asociativa)

4º. A " E = A (E es el elemento neutro)

5º. A " " = " (" es el elemento absorbente)

Complementario: Es un nuevo conjunto formado por todos los elementos que no están en A. A = {x " E / x " A} E

Propiedades del Complementario:

1º. A " A = "

2º. A " A = E

3º. A = A

4º. " = E

5º. E = "

6º. A " B ! B " A E

Diferencia: Es un nuevo conjunto formado únicamente por los elementos que están en A y no están en B. A - B = {x " E / x " A " x " B)

E

Propiedades:

1º. A - B = A " B

2º. A - B = " ! A " B

3º. A - B = A ! A " B = "

4º. A - B = B - A = " ! A = B

Diferencia Simétrica: Está formada por todos aquellos elementos que están A o están en B, pero no en los dos al mismo tiempo.

A  B = (A - B) " (B - A) E

Propiedades:

1º. A  B = (A " B) - (A " B)

2º. A  B = B  A

3º. A  (B  C) = (A  B)  C

Cardinales

El cardinal de A está asociado al número de elementos de A.

| A | = card(A) A = {1, 2, 3} | A | = 3 B = {4, 5} | B | = 2

Primer Axioma: " " E : | A | " 0

Segundo Axioma: | A " B | = | A | + | B | ! A " B = "

A = (A - B) " (A " B) Sólo cuando son

| A | = | (A - B) " (A " B) | = | A - B | + | A " B | distintos

| A - B | = | A | - | A " B|

| A " B | genérico

| A " B | = | (A - B) " (A " B) " (B - A) | = | A - B | + | A " B | + | B - A |

| A " B | = | A - B | + | A " B | + | B - A | = [ | A | - | A " B | ] + | A " B | + [ | B | - | A " B |]

| A " B | = | A | + | B | - | A " B | UNIÓN

Diferencia Simétrica

| A  B | = | A - B | + | B - A | = | A | - | A " B | + | B | - | A " B | = |A | + | B | - 2| A " B|

Ejercicios:

[(A " B) " [(A " B) " (A " B)]] " [(A " B) " (A " B)] =

[A " (B " B)] (A " A) " B

• E

[(A " B) " A] " B = [(A " A) " (B " A)] " B = B

"

[[A " (B " C)] " (A " C)] " [B " (A " C)] =

[[A " (A " C)] " [(B " C) " (A " C)] " [B " (A " C)]] =

[[(A " A) " (A " C)] " [(B " C) " (A " C)] " [B " (A " C)] =

E

= [(A " C) " (A " C)] " B " [(B " C) " (A " C)] = "

Producto Cartesiano

Par Ordenado: Conjunto de dos elementos en los que sí se tiene en cuenta el orden en que aparecen los elementos. (x, y).

(x, y) no tiene porqué ser = (y, x). si (x, y) = (u, v) ! x = u " y = v.

Terna Ordenada: Conjunto de tres elementos en los que sí se tiene en cuenta el orden en que aparecen los elementos. (x, y, z).

n - Tupla Ordenada: Conjunto de n elementos en los que sí se tiene en cuenta el orden en que aparecen los elementos.

" A, B " E : A x B = {(x, y) / x " A " y " B}

" A, B, C " E : A x B x C = {(x, y, z) / x " A " y " B " z " C}

Propiedades

A, B " " : A x B " X x Y ! A " X " B " Y.

| A x B | = | A | x | B |

A x B = " ! A = " " B = "

A x B " " ! A " " " B " "

A x B = B x A ! A = B

A x (B " C) = (A x B) " (A x C)

A x (B " C) = (A x B) " (A x C)

(A x B) " (C x D) = (A " C) x (B " D)

(A x B) " (C x D) " (A " C) x (B " D)

(A - B) x C = (A x C) - (A x B)

A x B = (A x B) " (A x B) " (A x B)

Grafos

A cualquier subconjunto de un producto cartesiano de dos conjuntos se le llama grafo. G " A x B

Pr1 (G) " A ; Pr2 (G) " B

Grafo Recíproco o Inverso

G = {(y, x) / (x, y) " G}

G = {(y, 2), (y, 1), (x, 3)} G = {(2, y), (1, y), (3, x)}

Composición entre los grafos

G o F = {(x, z) / " y : ((x, y) " F ; (y, z) " G)

F " A x B ; G " B x C G o F " A x C

R = {(a, 1), (b, 1), (c, 2), (d, 3), (e, 2), (f, 4)}

S = {(a, 4), (b, 3), (c, 2), (1, d), (5, e), (6, f)}

S = {(4, a), (3, b), (2, c), (d, 1), (e, 5), (f, 6)}

R o S = {(4, 1), (3, 1), (2,2), (1, 3), (5, 2), (6, 4)}

S o R = {(a, d), (b, d), (c, c), (d, b), (e, c), (f, a)}

G o F " F o G

(R o S ) = S o R

(G o F) = F o G

" (z, x) " (G o F) : (x, z) " G o F ! (x, y) " F " (y, z) " G } (y, x) " F " (z, y) " G}

} ! (z, x) " G

Establecer una correspondencia entre un conjunto A y B, consiste en asociar elementos de A a elementos de B.

• 2 x f = (F, A, B)

3 4 y z F " A x B

(x, y) " F " y = f(x)

Conjunto Original de F: Elementos del conjunto original que tienen imagen. (or f).

Conjunto Imagen: Elementos del lado final que son imagen de algunos del inicial. Im(f) o f(A).

or f = {x " A / " y " B : y = f(x)}

f (A) = {y " B / " x " A : y = f(x)}

Correspondencia Recíproca

f = (F ; B x A) Está asociado al grafo inverso.

y = f(x) ! x = f (y) x ! y y imagen de x x ! y x antiimagen de y

Composición

g o f = (G o F; A, C) g o f(x) = g (f (x))

Propiedades:

1. x1 " x2 ! f(x1) " f(x2) y " f(A) ! y = f(x) x " A.

2. f(x1 " x2) = f(x1) " f(x2)

3. f(x1 " x2) " f(x1) " f(x2)

f : A ! B es aplicación; g : B ! C es aplicación ! g o f : A ! C también es Aplicación.

Fotocopia

15. G = {(b, b), (b, c), (a, d), (d, b)} H = {(a, a), (c, a), (d, a)}

G = {(b, b), (c, b), (d, a), (b, d)} H = {(a, a), (a, c), (a, d)}

(G o H) = H o G = {(d, a), (d, c), (d, d)}

(H " G) = {(b, b), (b, c), (a, d), (d, b), (a, a), (c, a), (d, a)}

ran(H ) ! ran (F) = {y / " x : (x, y) " F} (conjunto de las segundas proyecciones)

dom(F) ! conjunto de las primeras proyecciones.

dom(F) = {x / " y : (x, y) " F}

16. N ! N F = {(x, y) / 4x + y = 24}

F = {(0, 24), (1, 20), (2, 16), (3, 12), (4, 8), (5, 4), (6, 0)}

dom(F) = {0, 1, 2, 3, 4, 5, 6}

ran(F) = {24, 20, 16, 12, 8, 4, 0}

F = {(24, 0), (20, 1), (16, 2), (12, 3), (8, 4), (4, 5), (0, 6)}

F o F = {(5, 8), (6, 24)}

Relación Binaria

Correspondencia entre un grafo y sí mismo. F : A ! A

f = (R; A, A); f (x) = y; (x, y) " R; x R y la imagen de x es y.

x está Relacionado con y

" x, y " Z : x R y ! x " y 4 no R 3 ! 4 no " 3

" A, B " !(E) : A R B ! A " B

Propiedades que pueden cumplir o no, las Relaciones Binarias:

1. Reflexiva: " x " A : x R x

2. Simétrica: " x, y " A : x R y ! y R x

3. Antisimétrica: " x, y " A : x R y " y R x ! x = y

4. Transitiva: " x, y, z " A : x R y ! y R z ! x R z

5. Conexa: " x, y " A : x R y " y R x

Relaciones de Equivalencia

Es una relación reflexiva, simétrica y transitiva.

Una correspondencia de elementos con sí mismos, en la que todo x está relacionado con x, todo x está relacionado con y, e y con x, y x con y, y con z, luego x con z. Se utiliza el signo “"”.

Sea A, " relación de equivalencia definida en A:

" a " A : [a] = {x " A / x " a} " a " A : a " [a] pues a " a.

clase de equivalencia del elemento a.

En la clase de un elemento están todos los elementos del conjunto relacionados con ese elemento.

Si un elemento no está en la clase de otro, ninguno de los elementos de la última clase puede estar en la clase del primer elemento. Si un elemento está en la clase de otro, todos los elementos de dicha clase estarán en la clase del primer elemento. a " b ! [a] = [b]

• Conjunto Cociente

Contiene las distintas clases de equivalencias.

A/" = {[a], a " A} ! nos da los distintos tipos de elementos que hay en un conjunto.

x + y = 2k k " Z " a " A : [a] = {x " A / x " a ! x + a = 2k; x = 2k - a;

[a] = {x = 2k - a}, k " Z [0] = {x = 2k - 0} = {0, 2, 4, 6, 8 …} Pares

[1] = {x = 2k - 1} = {-1, 1, 3, 5, 7, 9 …} Impares

Z / " = {[0], [1]}

Sea A, {C1, C2, C3, … , Cj}, Ci " A

son partición de A si: 1. " de Ci = A

2. Ci no tienen elementos en común.

9. R - {0} ; " a, b " R : a R b ! a + (1/a) = b + (1/b)

1. Reflexiva: " x " R : x + (1/x) = x + (1/x) ! x " x

2. Simétrica: " x, y " R : x + (1/x) = y + (1/y) ! y + (1/y) = x + (1/x) ! y " x

3. Transitiva: " x, y, z " R : x + (1/x) = y + (1/y); y + (1/y) = z + (1/z) !

x + (1/x) = z + (1/z) ! x " z

" a " R : [a] = {x " R-{0} / x " a} = {x + (1/x) = a + (1/a)} [a] = {a, (1/a)}

11. Reflexiva: " x " R x R : x² + x² = x² + x² ! x " x

Simétrica: " x, y " R x R : x² + y² = y² + x² ! x " y

Transitiva: " x, y, z " R x R : x² + y² = y² + z² ! x " z

" a " R x R [a] = {x " R x R / x " a} = {x² + x² = a² + a²}

Sea N; E(n) : " a, b " N : a R b ! E("a) = E("b)

Reflexiva: " x " N ; x R x ! E("x) = E("x)

Simétrica: " x, y " N ; x R y ! E("x) = E("y) ! E("y) = E("x)

Transitiva: " x, y, z " N ; x R z ! E("x) = E("y) ; E("y) = E("z) ! E("x) = E("z)

" a " N [a] = {x / x " a} = {E("x) = a}

[a²] = {x " [a², (a+1)²)} [a] = {[E("a)]² … ((E("a)+1)²-1)}

N/" = {[a²]}

Relación de Orden

Relación con las propiedades reflexiva, antisimétrica y transitiva.

a < b ! “a anterior a b” o “b posterior a a”

Z; a R b ! a " b N a R b ! a | b (a divide a b) } Divisibilidad

La relación de orden por excelencia es el “"”.

Preorden: Relación que es reflexiva y transitiva.

Aplicaciones

Sea f = (F; A, B) correspondencia. f es una aplicación si:

1. Todo elemento de A tiene imagen ! or f = A

2. La imagen es única. ! f(x) = y1 " f(x) = y2 ! y1 = y2

f : N ! N; f(x) = "x f(4) = ±2 } No es aplicación.

f : Z ! Z; f(x) = x² } Sí es aplicación.

Clasificación de Correspondencia

Inyectiva: Dos elementos no pueden tener la misma imagen.

N ! R; f(x) = "x } Inyectiva f : Z ! Z; f(x) = x² } No Inyectiva

(porque (-1)² = 1 y 1² = 1, dos elementos

distintos con misma imagen)

Sobreyectiva: Todo elemento del conjunto final es imagen de al menos uno del conjunto inicial.

" y " Z : y = f(x); x " Z y = x² ; x = ±"y } No Sobreyectiva

Biyectiva: Cuando es inyectiva y sobreyectiva al mismo tiempo.

f : R ! R; f(x) = x/2 Aplicación; Inyectiva, Sobreyectiva } Biyectiva.

Inyectiva : (x1/2) = (x2/2) ! x1 = x2

" x " A ! " f(x) = y " B ! " g(f(x)) = z " C

g o f (x) = z1 ; g o f (x) = z2 ! g(f(x)) = z1 ; g(f(x)) = z2 ! z1 = z2

Si f y g son inyectivas, g o f también es inyectiva.

Si f y g son sobreyectivas, g o f también es sobreyectiva.

18. f : R² ! R²

a. f(x, y) = (x, x " y -y)

1. Inyectiva: f(x1, y1) = f(x2, y2) ! (x1, x1 " y1 - y1) = (x2, x2 " y2 - y2) ! x1 = x2

x1 " y1 - y1 = x2 " y2 - y2 } y1(x1 - 1) = y2(x1 - 1) ; y1 = y2 " (x -1) / (x -1) !

! si x " 1 ! y1 = y2. Es inyectiva en f : R x R - {1, y}.

2. Sobreyectiva: " (z, t) " R x R : (z, t) = f(x, y) } ! (z, t) = (x, x " y - y) !

! z = x ; t = x " y - y ! t = z " y - y ! t = y(z - 1) ! y = t / (z - 1)

Es sobreyectiva en f : R x R ! R x R - {(1, y)}

Si g o f es inyectiva ! f es inyectiva

f (x1) = f (x2) ! g(f(x1)) = g(f(x2)) ! g o f (x1) = g o f (x2) ! x1 = x2 ! f es inyectiva.

Si g f es sobreyectiva ! g es sobreyectiva

" z " C ! z = g o f(x) ! z = g(f(x)) ! g es sobreyectiva.

Si g o f es biyectiva ! f es inyectiva y g es sobreyectiva

Relación de Equivalencia Inducida por una Aplicación

La relación de equivalencia inducida por una aplicación dice que 2 elementos están relacionados cuando sus imágenes son iguales.

" x1, x2 " A : x1Rx2 ! f (x1) = f (x2).

Estructuras

Ley de Composición Interna (LCI), ", definida sobre un conjunto E, una aplicación de E x E ! E

(a, b) ! a " b

Propiedades que se pueden cumplir:

Conmutativa: " a, b " E : a " b = b " a

Asociativa: " a, b, c " E : (a " b) " c = a " (b " c)

Elemento Regular: a " E es regular : a la izquierda : " b, c " E : a " b = a " c ! b = c

: a la derecha : " b, c " E : b " a = c " a ! b = c

Elemento Neutro: e " E, " x " E : e " x = x " e = x

Elemento Simétrico: a' es simétrico de a ! a " a' = a' " a = e

Distributiva: (E, ", °) (a " b) ° c = (a ° c) " (b ° c)

La estructura más pequeña que existe es un conjunto y una L.C.I. (E, ") " Grupoide o Magma.

Grupoide: Es una estructura formada por un conjunto y su l.c.i. Si un grupoide cumple además la propiedad asociativa, se le llama semigrupo. Si además de esto, cumple la conmutativa, se le llama semigrupo conmutativo o abeliano.

Si el semigrupo tiene elemento neutro se le llama semigrupo unitario o monoide.

Grupo: Es una estructura formada por un conjunto y una l.c.i., que cumple la propiedad del elemento neutro, la asociativa, y todo elemento tiene elemento simétrico. Si además el grupo cumple la conmutativa, se le llama grupo abeliano o conmutativo.

Subgrupo: Si dado un grupo G, tenemos un subconjunto de G, que también cumple las propiedades de grupo, se le llama subgrupo. H " G.

El grupo y subgrupo más pequeños que hay es el formado por el elemento neutro.

Grupo Finito: Grupo formado por un número finito de elementos.

(a " b)' = b' " a' (a')' = a sólo si G es conmutativo: (a " b)' = a' " b'

Homomorfismo: Cuando la imagen de la operación del lado inicial, coincide con la operación de las imágenes del lado final. f(a " b) = f(a) ° f(b)

Clasificación de Homomorfismo:

Si el homomorfismo es inyectivo Monomorfismo

Si es sobreyectivo Edimorfismo

Si es biyectivo Isomorfismo

Dos estructuras son isomorfas si existe un isomorfismo entre las dos (los elementos de un lado se comportan igual que los del otro lado).

Teorema de Caracterización de Subgrupos:

Sea (G,*) grupo, " " H " G, H G ! " a,b " H : a*b' " H

" a,b " H : a*b " H H G

" a " H : a' " H

(Z,+) grupo 2 " Z = {2 " h, h " Z} Demostrar: 2 " Z Z

0 = 2 " 0 ! 0 " 2 " Z " "

" x, y " 2 " Z : x +y' " 2 " Z x = h1 y = h2

x + y' = 2 h1 + (2 h2)' = 2 h1 + (-2 h2) = 2(h1 - h2) " 2 " Z

Congruencias Módulo un Subgrupo

Sea (G, *) grupo, y sea H G

" a, b " G : a ~i b ! a' * b " H congruencia a la izq mod. H

a ~d b ! b * a' " H

~i

1. a' * a = e " H ! a ~i a

2. a ~i b ! a' * b " H ! (a' * b)' " H ! b' * a " H ! b ~i a

3. a ~i b (a' * b) * (b' * c) " H ! a' * c " H ! a ~i c

b ~i c

[a]i = a * H [a]d = H * a

[e]i = e * H = H [h]i = h * H = H (h " G; h " H)

Sea H G ! si [a]i = [a]d " a " G ! H es un Subgrupo de G y se llama

Subgrupo Normal H G

Teniendo en cuenta el Teorema de Caracterización de Subgrupos:

H G ! " a " G : a * H * a' " H

Homomorfismo entre grupos

f : (G,*) ! (G',°) aplicación " a,b " E : f(a*b) = f(a) ° f(b)

1). f(e) = e' ! f(e) = f(e) ° e'

f(e) = f(e*e) = f(e) ° f(e)

f Hom

2). F(a') = (f(a))' f(a') ° f(a) = f(a) ° f(a')

f(a' * a) = f(a*a')

f(e) = e'

Núcleo de un Homomorfismo de Grupos

Ker f = {x " G / f(x) = e'}

Aquellos x del grupo inicial cuya imagen sea el elemento neutro del grupo final. En Ker f sólo ha de estar e para que sea inyectiva, si hay dos elementos en el núcleo ya no es inyectiva.

7). f : (R*, ") ! (R*, ") f(x) = x² demostrar f Hom entre grupos

f(x " y) = f(x) " f(y)

f(x " y) = (x " y)² = (x " y) " (x " y) = x " x " y " y = x² " y² = f(x) " f(y)

Ker f = {x " R* / f(x) = 1} x² = 1 ; x = ± 1; Ker f = {-1, 1}

Ker f G

" " H " G; H G ! " a,b " H : x * y' " H

" " Ker f " G Ker f G ! " x, y " Ker f : x * y' " Ker f

1. Ker f " " ! f(e) = e' ! e " Ker f " "

2. " x, y " Ker f : x * y' " Ker f ! f(x * y') = f(x) ° f(y') = e' ° (f(y))' = e' ° e' = e'

Ker f G f(x) = x² Ker f = {-1,1} [a]i = a " Ker f = {-a,a} Ker f G

[a]d = Ker f " a = {-a,a}

Im f G' " y " G' : y = f(x)

1. f(e) = e' " f(G)

2. " f(a), f(b) " f(G) : f(a) ° f(b)' " f(G) : f(a) ° f(b') = f(a*b') " G

7). Imf = R*,+

" y " R* : y = f(x) y = x² x = ±"y y " 0

(G,*) <a> potencias de a " a " G

n > 0 : a = a " a " a ... a (n veces)

a = n = 0 : a° = e

n < 0 : a = a' " a' " a' ... a' (n veces)

(R*, ") 5 = 5 " 5 " 5 " 5 5° = 1

(Z,+) 5 = 5 + 5 + 5 + 5 5° = 0

Subgrupo engendrado por un elemento

<a> = {a , n " Z} ! <a> G

subgrupos engendrados o generados por a.

" " <a> " G, <a> G ! " x,y " <a> : x * y' " <a>

1. <a> " " e = a° " <a> " "

2. " a ,a " <a> : a * (a )' " <a>

a * (a )' = a * a * a ... * a * (a * a * a ... * a)' = a " <a>

Orden de Grupo. Número de elementos que tiene un grupo.

Si el grupo es de orden contable, se llama grupo finito.

Un Grupo es Cíclico si mediante potencias de un elemento puedo generar todos los elementos del grupo. Se dice que el grupo es engendrado por dicho elemento. Si un elemento genera un grupo, su simétrico también.

La primera potencia no nula, tal que `a' elevado a ella me da el neutro, se llama orden de elemento.

orden (e) siempre 1 ! O(e) = 1

O(a) = K1 / a = e (k entero no nulo más pequeño / a = e)

O(a) = k ! <a> = {a°, a, a², a³, ..., a } |<a>| = k

Teorema de Lagrange para grupos finitos

El orden de un subgrupo divide siempre al orden del grupo.

si O(a) = |G| ! G es cíclico

" a " G; O(a) ha de dividir al |G|

|G| = 1 G = {e} ! cíclico ya que su orden es primo

Orden	Sim	*	e
1	e	e	e

|G| = 2 G = {e,a} ! cíclico engendrado por a

Sim	orden	*	e	a
e	1	e	e	a
a	2	a	a	e

|G| = 3 G = {e, a, a²} ! cíclico generado por a y a² G = <a> = < a²>

Orden	*	e	a	a²
1	e	e	a	a²
3	a	a	a²	e
3	a²	a²	e	a

Orden	*	e	a	a²	a³	Sim
1	e	e	a	a²	a³	e
4	a	a	a²	a³	e	a³
2	a²	a²	a³	e	a	a²
4	a³	a³	e	a	a²	a

|G| = 4 G = <a> = <a³> ! cíclico (a²)² = a = e; luego orden de a²

O(a') = k ! (a') = a' * a'* a' ... * a' (k veces) = (a * a * a... *a)' = (a )' = e' = e

|G| = 4 ! no cíclico G{e, a, b, c} Grupo Klein K4

Sim	orden	*	e	a	b	c
e	1	e	e	a	b	c
a	2	a	a	e	c	b
b	2	b	b	c	e	a
c	2	c	c	b	a	e

Subgrupo Impropio. Subgrupo formado por e o por todo el grupo.

Inducción Matemática e Inducción Completa

Se basa en: siempre n " N

1). Se demuestra la fórmula en cuestión para un primer elemento.

2). Se establece la “Hipótesis de Inducción”, que es, suponer que la afirmación es cierta hasta n = k. 1 + 3 + 5 ... + (2k -1) = k²

3). Demostrar la afirmación para el siguiente elemento, n = k+1.

1 + 3 + 5 ... + (2(k+1) -1) = (k+1) ²

1 + 3 + 5 ... (2k-1) + (2(k+1)-1) =

k² + (2(k+1)-1) =

k² + 2k + 2 -1 = k² + 2k -1 = (k +1) ²

%(A " ¬A)

A B

A B

A

B

A

A B

A B