Apuntes de Matemática Discreta

2. Preposición, Tablas de
   verdad, Tautología y
   Contradicción
3. Relación de
   pertenencia
4. Conjunto de
   partes
6. Inducción
   matemática
7. Sucesiones por
   recurrencia
8. Reglas de
   divisibilidad
9. Cambio de
   base
10. Producto
    cartesiano
11. Relaciones
12. Funciones
13. Relaciones definidas de
    un conjunto en si mismo
14. Clausura de una
    relación
15. Composición de
    funciones
16. Relación de
    equivalencia
17. Conjunto
    cociente
18. Operaciones
    binarias
19. Conjuntos
    ordenados
20. Grupos
21. Subgrupos
22. Redes, subredes,
    átomos
23. Lenguajes
24. Autómatas
    finitos

LÓGICA Y
CÁLCULO PROPORCIONAL:

Preposición: Cualquier frase susceptible
de adquirir un valor de
verdad. En general se compone de la siguiente manera: (SUJETO +
VERBO + PREDICADO)

Tablas de verdad:

Tautología: El valor de
verdad de toda la columna es Verdadero.

Contradicción: El valor de verdad de toda
la columna es Falso.

———————————————–

Tautología: ~Contradicción.

Contradicción: ~Tautología.

Si el antecedente de una implicación es Falso, el
valor de verdad es Verdadero

Leyes de De Morgan:

 Cuantificadores:

Hay dos tipos:

El cuantificador Universal " ("Para todo") y el cuantificador
existencial $
("Existe").

Hay proposiciones como por ejemplo: "5 > 2"; "X toma
el mismo valor que Y"; "5²=20"; a las que podemos
adjudicarle un valor de verdad (Verdadero o Falso), y hay
expresiones que incluyen variables como
x²+2x-3 = 0 que no podemos decir que sean proposiciones,
puesto que si x=1 resulta verdadero, pero su x=0 entonces resulta
falso.

Si decimos ""
x: x²+2x-3= 0", ahora si es una proposición y
es falsa, puesto que podemos mostrar el contraejemplo,
dándole a x el valor "0".

La expresión: "$ x / x²+2x-3 = 0" es también una
proposición y en este caso es verdadera.

Negación de los cuantificadores:

~ ("
x: P(x) ) Û $ x:
~ P(x)

~ ($
x: P(x) ) Û " x:
~ P(x)

(p1, ^ p2 ^ p3 ^ p4) Þ C

Relación
de pertenencia:

Se define de elemento a conjunto. A la izquierda del
signo Î
(pertenece) debe haber un elemento y a la derecha del signo
un conjunto. Para que la expresión sea verdadera el
elemento de la izquierda debe ser alguno de los elementos del
conjunto de la derecha.

El Æ
(conjunto vacío) es el que no contiene ningún
elemento.

# (cardinal)
es la cantidad de elementos que posee un conjunto.

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

  Inclusión: Igualdad:

A Ì
B Û
x Î
A Þ
x Î
B A = B Û (A Ì B ^ B Ì A )

  CONJUNTO DE PARTES

Dado un conjunto A, llamamos P(A) (partes de A), a un
conjunto cuyos elementos son todos los subconjuntos posibles del
conjunto A.

El conjunto vacío es subconjunto trivial de
cualquier conjunto, y el mismo conjunto A es subconjunto impropio
de si mismo. Todos los otros subconjuntos se llaman propios. En
nuestro caso:

# A =
3 # P(A) =
8

#
A

En general: # P(A) = 2

Por este motivo el conjunto de partes se llama
también Conjunto Potencia.

A = Æ
# =
0

P(A) {0;A} #
= 2º = 1

A = {a} #
= 1

P(A) {0;A} #
= 2¹ = 2

 Partición:

Dado un conjunto "A " y otro conjunto "P", cuyos
elementos son a su vez conjuntos a
los cuales llamamos Pi.

P = {P1, P2, P3, … Pn}

Decimos que P es una partición de A si se cumple
que la intersección de dos elementos cualquiera de P es
siempre el conjunto vacío; la unión de todos los
elementos de P es el conjunto A. Por último, ningún
elemento de P es el conjunto vacío.

Condiciones:

1º) Pi ^ Pj = Æ si i ¹ j

n

2º) U Pi = A

i = 1

3º) Pi ¹ 0 " i

Ejemplificación:

Sea A = {1,2,3,4,5,6}

P1 = {í 1,2,3,4ý ; í 5,6ý } Es
partición

P2 = {í 2,4ý ; í 1,6ý ; í 3,5ý } Es
partición

P3 = {í 1,3,5ý ; í 1,2,4,6ý }

No es partición puesto que no cumple con la
primera condición: el elemento "1" se repite.

P4 = {Æ
;í
2,4,5,6ý
; í
1,3ý
}

No es partición puesto que no cumple con la
tercera condición: el elemento "Æ " no puede formar
parte de una partición.

P5 = {í 1,3,5,7ý ; í 2,4,6ý }

No es partición puesto que no cumple con la
segunda condición: el elemento "7"Ï al conjunto A.

Si todos los conjuntos Py que son elementos de P tienen
en el mismo cardinal, decimos que es una Partición
Regular.

INDUCCIÓN
MATEMÁTICA:

Quinto postulado de Peano:

Si [P1 es Verdadero y {Ph
Þ P(h+1)} es
verdadero] Þ
Pn n Î
N

Sumatoria:

4

å (3i + 1) =
4+7+10+13 = 24

i=1

5

å (2i – 2) =
-1+0+2+6+14+30 = 51

i=0

6

å (2i – 2) =
-1+0+2+6+14+30+62 = 113

i=1

Ejemplificación:

n+1 k n

å 3 = 3/2 (3 –
1)

k=2

1) n = 1

n+1 1 1

å 3 = 3/2 (3 –
1)

k=2

3 = (3/2) × 2

Dándole a "n" el valor de 1, la
igualdad es
válida.

 2) Hipótesis:

n = h

h k h

å 3 = 3/2 (3 –
1) Esto se considera válido siempre

k=2

3) Tesis:

n = h+1

h +1 k h+1

å 3 = 3/2 (3 –
1) Este es el término al que se desea llegar

k=2

4) Demostración:

h k h h+1

å 3 = 3/2 (3 –
1) + 3 Se copia la hipótesis y se agrega el término
h+1

k=2 reemplazando "k" por "h+1"

Se comienza a igualar para llegar a
la Tesis

h h+1

= 3/2 [(3 -1) + 2/3 * 3 ]

h h

= 3/2 [3 -1 + 2 * 3 ]

h

= 3/2 [3 * 3 – 1]

h+1

= 3/2 [3 + 1]

Finalmente, este término
resulta idéntico a la Tesis y la
igualdad queda demostrada.

Inducción completa en propiedades expresadas
con una desigualdad:

Sea A l
B una propiedad
donde A es una función de
n y B también.

Primero debemos probarlo para n=1 y si se cumple, por
hipótesis

A (h) l
B (h)

A (h+1) l
B (h+1)

Para demostrarlo, partimos de A (h) l B (h) y hacemos lo necesario
para transformar A(h) en A (h+1). Una vez que en el primer
término tenemos A (h+1), aún haciendo todas las
operaciones
matemáticas posibles, difícilmente
nos quede en el segundo término B (h+1). Generalmente lo
que queda es la expresión A (h+1) l C(h). Entonces lo que debemos
hacer es probar C(h) l
B (h+1).

De ambas expresiones concluimos que por ser de orden
transitivas A (h+1) l
B (h+1).

SUCESIONES
POR RECURRENCIA O RECURSIÓN:

an = 3an-1 + 2an-2 +5

El orden de una sucesión tiene que ver con la
cantidad de términos anteriores que se utilizan. En el
ejemplo tenemos una sucesión de 2º orden. El grado se
relaciona con el exponente al que están elevados an – i.
Por último, la sucesión es homogénea si no
hay ningún término independiente. En el caso
anterior es no homogénea.

Ejemplificación:

Resolución de ecuaciones
homogéneas de primer grado, segundo orden:

1. Se pasan al primer miembro los términos an,
   an-1, an-2, los cuales también podrían figurar
   como an+2, an+1, an

   n n

2. Se reemplaza an por r², an-1 por r y an-2 por 1,
   quedando una ecuación de segundo grado con raíces
   reales y distintas de r1 y r2.
3. Se plantea a = u · r1 + v ·
   r2
4. Debemos tener como dato los valores
   de los dos primeros términos de la
   sucesión:

A0 = k y A1 = k’. Utilizando estos datos
ordenamos el sistema de
2×2: u + v = k y u·r1 + u·r2 = k’. La
resolución de este sistema no da como resultado los
valores u0
y v0, que son números reales conocidos.

e) la solución general es:

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

Ejemplificación:

an= 2/3an-1 +1/3an-2

a0 = 2 Esto es dato

a1= 5

 Primero efectuamos
el cambio de
variable de la manera indicada

1

r² – 2/3 r – 1/3 = 0

-1/3

Aplicamos la fórmula para
resolver ecuaciones cuadráticas.

Luego reemplazamos los valores de las raíces en
la fórmula general:

n n

a = u · 1 + v · (-1/3)

Ahora debemos usar los datos que nos dieron par resolver
el problema: El polinomio especializado en 0 da como resultado 2,
y especializado en 1 da 5 (Ver llave al inicio del problema donde
se aclara cuales son los datos). Por lo tanto podemos elaborar el
siguiente sistema de ecuaciones:

u + v =2

u – 1/3 = 5

Resolviéndolo, obtenemos que:

v = -9/4

u = 17/4

Por último, escribimos la ecuación
general, que en nuestro ejemplo es así:

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

REGLAS DE DIVISIBILIDAD:

1. Si A·B = C, siendo A, B y C Î Z, decimos que C es
   múltiplo de A, también de B, y A y B son
   divisores de C. Es decir, para que C sea múltiplo de A
   debe existir un B tal que A·B=C. para que A sea divisor
   de C debe existir un B tal que A·B = C
2. 0 es múltiplo de cualquier número,
   porque $
   0 / 0
   · A = 0
3. 0 no es divisor de ningún número,
   puesto que A : 0 = ? Þ 0 · ? = A
4. 1 es divisor de cualquier entero, puesto que N : 1 =
   N
5. 1 es múltiplo de 1 y -1

7)

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

8) El conjunto de divisores de n está formado
por todos los Z que lo dividen exactamente. Por
ejemplo:

D6 = {1,2,3,6} D42 = {1,2,3,6,7,14,42} D13 =
{1,13}

+

D0 = Z – {0} D1 = {1}

9) Decimos que un número es primo cuando tiene
dos divisores: "1" y él mismo.

10) Decimos que un número es compuesto cuando
tiene más de dos divisores, pero no
infinitos.

11) El 0 y el 1 no son primos ni
compuestos.

12) El teorema fundamental de la aritmética
dice que cada número puede descomponerse en un producto
único de factores primos. Por ejemplo:

6 = 2·3 42 =
2·3·4 13 = 13 36 = 2·2·3·3 =
2²·3²

Para abreviar la escritura
usamos notación exponencial.

13) El Máximo Común Divisor (MCD) entre
dos números es el mayor número que figura en el
conjunto divisores de A Ç divisores de B. MCD(a,b) = (a,
b)

Max (Da Ç Db)

14) El Mínimo Común Múltiplo
(MCM) es el mínimo elemento perteneciente a la
intersección de múltiplos de A y B. MCM(a,b) =
[a,b] Min (Ma Ç Mb)

15) El MCM entre A y B = A·B

MCD (a,b)

Método para hallar el MCM y el
MCD:

* Dividen a toda la fila

5 2 4

M CM = 2 · 3
· 5 = 180.000

2 2

M C D = 2 · 5
= 100

 Consideraciones:

a Î
Z, b Î
Z Þ
(a , b ) = (ï a ï , ï b ï ) = (b, a)

1. (a , b ) = (ï a ï , ï b ï )
2. (a , b ) = (b, a)

1) Por convención, cuando formamos el conjunto de
divisores de un número, consideramos solo los divisores
positivos, sea el número positivo o negativo, por lo tanto
Dn = D-n. Trabajar con a o con ï a ï produce el mismo resultado.

2) (a , b ) = Max (Da Ç Db) = Max (Db Ç Da) = (b, a)

CAMBIO DE
BASE:

Ejemplificación:

Base 5 a base 10 (b5® b10)

430123 =

5 4 3 2 1 0

4·5 + 3·5 + 0·5 + 1·5 +
2·5 + 3·5 =

4 · 3125 + 3 · 625 + 0 · 125 + 1
· 25 + 2 · 5 + 3=

12500+1875+0+25+10+3=

14413

Como se observa, el número
(430123) b5 resulta equivalente a (14413) b10

Base 16 a base 10 (b16® b10)

Como la base 16 o hexadecimal tiene
seis símbolos más que la base 10 o
decimal, la equivalencia entre dichas unidades es la que se
expone en la tabla.

La conversión
de base hexadecimal a base decimal se efectúa de la forma
convencional antes vista

Pasaje de una base a otra que es potencia de
ella:

Caso 1: Para pasar un número de base m a
base m^n, se escribe el número en base m y se lo divide de
derecha a izquierda en grupos de n
números. Cada uno de estos números pasados a base
10 será una de las cifras de este mismo número
expresado en base m^n.

Caso 2: Para pasar un número de base m^n a
base m, escribimos el número separando bien las cifras y
debajo de cada cifra hacemos un rectángulo dividido en n
casilleros. En cada uno escribimos la cifra de arriba en base m,
completando con cero los casilleros vacíos.

Ejemplificación:

Caso 1: Pasaje de la base 2 a la base
16

Caso 2: Pasaje de la base 8 a la base
2

PRODUCTO CARTESIANO:

Sean dos conjuntos A y B, llamamos Producto Cartesiano
A·B al conjunto de todos los pares ordenados que se pueden
armar con el primer componente perteneciente al primer conjunto y
el segundo componente perteneciente al segundo
conjunto.

Ejemplificación:

Sea A = {a,b}, B= {1,2,3}

A·B= (a1, a2, a3); (b1, b2, b3)

RELACIONES:

Llamamos Relación de A en B a cualquier
subconjunto del Producto Cartesiano de A·B

A = {a,b}, B= {1,2,3}

R = {(a,1); (a,3); (b,2); (b,3)}

Gráficos:

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

MR1= 1 0 1

0 1 1

 Matriz booleana Tabla Simple
Doble entrada

Diagrama de Venn Diagrama
Cartesiano

Llamamos Dominio (D) de una relación al
conjunto de elementos del primer conjunto que son primer
componente de algún par de la relación.

Llamamos Imagen ( I) al conjunto de elementos del
segundo conjunto que son segunda componente de algún
par.

La Relación Complementaria (R) de otra
dada es la diferencia entre el producto cartesiano de A·B
y la relación R definida de A® B

La Relación Inversa (R¯¹) es la
relación que contiene a los pares (x,y) / (y,x)
Î R

FUNCIÓN:

Decimos que una relación es una función si
para cada elemento del primer conjunto existe una única
imagen.

Si cada elemento del segundo conjunto es imagen de
alguien, entonces la función es
Sobreyectiva.

Si cada elemento del segundo conjunto es, a lo sumo,
imagen de un elemento del primer conjunto, entonces la
función es Inyectiva.

Si una función es sobreyectiva e inyectiva,
entonces es Biyectiva.

RELACIONES DEFINIDAS DE UN CONJUNTO
EN SI MISMO (A® A)

Reflexividad: Una relación es Reflexiva
cuando para cada x Î A, el par (x,x) Î a la relación. Si
está escrita en forma de pares, deben figurar tantos pares
(x,x) como elementos tenga el conjunto. Si está dado
matricialmente, la diagonal principal debe ser toda de "1". Si
algunos pares (x,x) figuran y otros no, la relación es
No Reflexiva. Si ningún par (x,x) figura, la
relación es Areflexiva.

Simetría: Una relación es
Simétrica si todo par tiene su inverso en la
relación. Si algunos pares tienen simétrico y otros
no, la relación es No Simétrica. Si
ningún par tiene simétrico, la relación es
Antisimétrica.

Transitividad: Una relación es Transitiva
si existiendo en la relación dos pares del tipo
(x,y);(y,z), entonces aparece también el par
(x,y).

CLAUSURA DE UNA
RELACIÓN:

Clausura Reflexiva: Es la menor relación
reflexiva que contiene a la dada. Si la relación es
reflexiva, es su propia Clausura Transitiva. Si la
relación está dada por una matriz
booleana, la Clausura Reflexiva se obtiene completando con 1 la
diagonal principal.

Clausura Simétrica: Es la menor
relación simétrica que contiene a la dada. Si una
relación es simétrica, es su propia Clausura
Simétrica. Si la relación está dada como
matriz booleana, se cambian los 1 por 0 necesarios para que sea
simétrica respecto de la diagonal principal.

Clausura Transitiva: Es la menor relación
transitiva que contiene a la dada. Si la relación es
transitiva, es su propia Clausura Transitiva. Si no lo es se
halla usando el siguiente método:

1. t

2. Se encuentran las potencias de R (R², R³,
   etc.)

   t t-1 i

3. Si R es la relación total o producto
   cartesiano, no se buscan más potencias y esa es la
   Clausura Transitiva.
4. Si R es la matriz nula, entonces la C.T es la
   unión generalizada R¥ = U R

t i=1

4) Si R es igual a alguna potencia anterior, entonces no
se buscan más potencias y la C.T es idéntica que en
el punto anterior.

Clasificación de las relaciones por sus
propiedades:

Una relación es de Orden Estricto si es
asimétrica y transitiva. P. Ej.: >

Una relación es de Orden Amplio si es
reflexiva, antisimétrica y transitiva. P. Ej:
³

Una relación es de Equivalencia si es
reflexiva, simétrica y transitiva.

Ejemplificación:

• Al tener en su Diagonal Principal únicamente
  "1", la matriz es simétrica. (Diagonal principal
  sombreada)
• Como los elementos que bordean a la Diagonal
  principal son idénticos, la matriz es reflexiva.
  (Elementos en cursiva)
• Al multiplicar la matriz por si misma se obtiene otra
  matriz idéntica y por lo tanto se halla la clausura
  transitiva.

COMPOSICIÓN DE FUNCIONES:

R: A ® T

T: A ® A

R= {(1,2); (2,3); (3,1);
(3,2)}

T= {(1,1); (2,1); (3,1);
(3,3)}

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

R°
T= {(1,2); (2,2); (3,2); (3,1)}

T°
R= {(1,1); (2,1); (2,3); (3,1)}

Cuando componemos un conjunto con él mismo, lo
podemos anotar con notación exponencial:
R° R =
R²

Cuando componemos una matriz con ella misma puede
ocurrir que obtengamos la matriz nula, entonces, a partir de ella
todas las potencias restantes serán la matriz nula.
Podemos obtener la matriz total (toda de "1"), en cuyo caso, de
ahí en mas, todas las potencias serán iguales a
ella. Puede ocurrir que encontrando las potencias de una
relación obtengamos una que ya había aparecido, de
tal forma que se repetirán cíclicamente.

RELACIONES DE
EQUIVALENCIA:

Una relación es de Relación de
Equivalencia (º
) cuando es reflexiva, simétrica y transitiva. Estas
relaciones tienen una característica muy particular:
producen en el conjunto en el cual las definimos una
partición.

Esta partición se caracteriza porque en cada
conjunto de los que integran la partición encontramos
elementos equivalentes entre si.

Sea el conjunto A y en el definido una relación
de equivalencia. Tomamos el primer elemento y formamos la
clase que lo
contiene. Comparamos el segundo elemento: si son equivalentes, B
quedará en la clase del A, y sino abrimos la clase del B
que lo contiene.

Tomamos el elemento C y lo componemos con A, si es de
equivalencia queda en la clase del A, sino lo comparamos con B, y
sino abrimos la clase del C que lo contiene, y así
sucesivamente.

Si los elementos son infinitos, con algún
criterio podremos interpretar el armado de las clases de
equivalencia.

El conjunto de todas las clases de equivalencia es el
Conjunto Cociente.

CONJUNTO COCIENTE:

Decimos que el Conjunto Cociente es una partición
porque:

1. como cada clase se abre para cada elemento, ninguna
   puede ser Æ
   .

b) Como comparamos todos los elementos de A, la
unión de todas las clases será A.

Sea X1 Î Ca ^ X1 Î Cb

X1 Î
Ca Þ
X1 º
a Þ
a º
X1 Œ

X1 Î
Cb Þ
X1 º
b

Πy
a º
b Þ
b Î
Ca Þ
Ca = Cb

Ca y Cb = Æ

Relación de equivalencia compatible con una
operaciónÛ

Decimos que Û y º son compatibles cuando: si a es
equivalente a b, y c es equivalente a d, entonces
aÛ c
es equivalente a bÛ d.

OPERACIONES BINARIAS

Llamamos Operación Binaria a cualquier
función de A× B en C. Es decir, a un par ordenado con
primer elemento perteneciente a A, y segundo componente
perteneciente a B, le hacemos corresponder un elemento de
C.

Los conjuntos A, B y C pueden ser distintos o iguales.
Cuando A=B y tenemos una función A× A en C, como puede ser la
resta definida en nxn que va a parar a Z, vemos que sale fuera de
los números naturales. Ejemplo: 5-12= -7, donde 5 y
12 Î N y
-7 Î
Z.

Puede ocurrir que B y C sean iguales, y tenemos Ley
de Composición Externa. Ejemplo: Producto de un
escalar por un vector, que va de rxb en b.

Puede ocurrir que A=B=C. en este caso la función
no va de A×
A en A y decimos que es una Ley de Composición
Interna, o bien una Operación Cerrada, o que
cumple con la Ley de Cierre.

Propiedades:

• Propiedad Conmutativa: AÛ B =
  BÛ
  A
• Propiedad Asociativa: (AÛ
  B)Û
  C = AÛ (BÛ C)

Elementos Notables:

• Idempotencia: A Û A = A
• Elemento Neutro: A Û e = A
• Elemento Inverso: A Û
  A’ = e
• Elemento Absorbente: µ Û A = µ
• Involución: A Û A = e

Ejemplificación:

Sea AÛ B= A+B – 3AB definida en Z

1) La operación es cerrada, porque lo son la suma
y la multiplicación en Z, y porque lo es la
multiplicación de números enteros.

Propiedad Conmutativa: A+B – 3AB = B+A –
3BA. Esto es válido puesto que la suma y la
multiplicación son operaciones conmutativas.

Propiedad Asociativa:

AÛ
(B + C – 3BC) = A + B + C – 3BC – 3A (B +
C-3BC) = A + B + C – 3BC – 3AB – 3AC + 9ABC Œ

(A + B – 3AB)Û C = A + B – 3AB + C – 3 (A + B – 3AB) C
= A + B + C – 3AB – 3AC -3BC + 9ABC

Nótese que aplicando la asociatividad, en ambos
casos (Œ
y ) se llegó al mismo resultado, por lo
tanto la operación es asociativa.

Idempotencia:

AÛ
A = A + A – 3AA

2A – 3AA = A

2A – 3A² ¹ A

No es idempotente.

Elemento Neutro:

AÛ C = A + C – 3AC

A + e – 3 Ae = A

e – 3 AC = 0

e (1–3A) = 0

e = 0

En este caso el Elemento Neutro es el
Cero

Elemento Inverso:

AÛ
A’ = A +
A’ –
3AA’

A + A’
– 3AA’
= 0

A’ –
3AA’ =
– A

A’
(1–3A)= –
A

A = – A
:
(1–3A)

Obsérvese que Ï Z y que además
A ¹ 1/3,
por lo tanto no existe un Elemento Inverso.

Elemento Absorbente:

AÛ
µ = A +
µ –
3Aµ

A+µ
– 3 Aµ = 0

µ =
–A :
(-3A)

µ =
1/3

Al existir dos soluciones
posibles no existe Elemento Absorbente.

Si la operación no es conmutativa debemos probar
el neutro a derecha y a izquierda. Puede ocurrir que no exista
neutro porque queda en función de A, o bien, que exista
derecha, pero no izquierda o viceversa. Por ejemplo: La potencia
tiene neutro a derecha, pero no tiene neutroizquierda. Para
poder decir
que una operación no conmutativa tiene neutro, debe tener
neutroizquierda, neutroderecha y ambos deben ser
iguales.

CONJUNTOS ORDENADOS

Decimos que dos elementos son comparables cuando una
relación l
, podemos afirmar que Al B o Bl A. Ejemplificación: En Z, 2 y 3 son
comparables respecto de la relación de menor, pues 2 <
3, pero no son comparables respecto de la relación "/"
("Divide a"), puesto que ni 2/3, ni 3/2.

Una relación es de Orden Total cuando
todos los elementos del conjunto en el cual está definida
son comparables entre si. Hay relaciones de orden amplio que son
totales como ³
y relaciones de orden amplio que no lo son, como
/.

Hay relaciones de orden estricto que son totales, como
< y relaciones de orden estricto que no lo son, como la
inclusión propia (Decimos que un conjunto
AÌ B
propiamente, si existe al menos un elemento de B que no pertenece
a A).

Una relación de orden definida en un conjunto A
es un Buen Orden si para cualquier elemento de A
$ siempre un elemento
que l a todos
los otros. Ejemplificación: la relación de menor
definida en N es buen orden, pues cualquier subconjunto de N
tiene siempre un elemento menor que todos los demás. La
relación de mayor definida en N, tiene como primer
elemento el mayor elemento del conjunto, por lo tanto, cualquier
subconjunto infinito de los N no tiene primer
elemento.

Elementos notables:

Dado un conjunto A incluido en otro R, llamamos Cotas
Superiores a todos los elementos de R que siguen a cualquier
elemento del conjunto A, y llamamos Cotas Inferiores a
todos los elementos de R que preceden a cualquier elemento de
A.

La menor de las cotas superiores, si pertenece al
conjunto A es Máximo, y si no pertenece es
Supremo. La mayor de las Cotas Inferiores, si pertenece al
conjunto A es Mínimo y si no pertenece es
Ínfimo.

Si una relación de orden no es total, genera un
gráfico llamado Diagrama de Hasse.

Dado un conjunto A incluido en otro R, llamamos
Minimales a los elementos del conjunto A que no son
precedidos por ningún otro. Llamamos Maximales a
los elementos de A que no son seguidos por ningún otro
elemento de A.

Nótese que un mismo elemento puede ser minimal y
maximal a la vez.

Ejemplificación:

Sea el conjunto de los x A={ x / 2 £ x £ 13} , en la relación "/" en Z

Maximales: {
8,12,9,10,11,13}

Minimales: {
2,3,5,7,11,13}

Cotas inferiores: { -1, 1} , 1 es ínfimo.

Cotas superiores: { 360360} , 360360 es supremo.

Diagrama de Hasse:

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

GRUPOS

Condiciones:

(G;Û )

1) Û es cerrada en G

2) Û es asociativa en G

3) $ e
neutro en G para Û

4) $
a’ para cada a de G / a’Û a =
aÛ
a’ = e

Cuando además de ser grupo la
operación es conmutativa, se dice que es Grupo
Abeliano.

Composición de funciones:

Es asociativa, generalmente no es conmutativa. El
elemento neutro es la Identidad. La
función inversa es la que conocemos habitualmente y
decimos que la composición de F con G es otra
función de pares (x,y) / $ k: (x,k) Î g Ù (x,y) Î F.

Ejemplificación:

• La operación es cerrada, como se puede
  observar en la tabla.
• La composición de funciones es
  asociativa.
• F1 es la identidad y funciona como
  neutro.
• Cada elemento tiene inverso.
• No es conmutativa, puesto que

F4°
F3 = F5 y F3° F4 = F6, por lo tanto (F;
° ) es grupo no
abeliano.

Inversos:

F1’ = F1

F2’ = F3

F3’ = F2

F4’ = F4

F5’ = F5

F6’ = F6

SUBGRUPOS

Si un conjunto S ¹ Æ
, incluido en G, tiene a su vez estructura de
grupo, decimos que S es un subgrupo de G.

En el ejemplo anterior S = { F1, F2, F3} , constituye a su vez un grupo,
además abeliano.

Nótese que todo grupo abeliano tiene todos sus
subgrupos abelianos, sin embargo un grupo no abeliano puede tener
grupos abelianos o no abelianos.

El Conjunto generado por un elemento es el
conjunto que se obtiene operando un elemento consigo mismo como
sea necesario hasta que empieza a repetirse.

< F1> = { F1}

< F2> = { F3; F1; F2}

< F3> = { F2; F1; F3}

< F4> = { F1; F4}

< F5> = { F1; F5}

< F6> = { F1; F6}

Todo conjunto tiene como mínimo dos subgrupos: el
Subgrupo Trivial {
e} y el
Subgrupo Impropio, que es G.

Cualquier subgrupo que no sea el trivial ni el impropio
se denomina Subgrupo Propio.

Teorema de Lagrange

Si un conjunto es finito, de cardinal n y tiene un
subgrupo de cardinal d, entonces d divide a n. En consecuencia si
el cardinal de un grupo es primo, no tiene subgrupos
propios.

Grupos de pocos elementos

a) Grupos de un elemento:

El único grupo de un elemento es el grupo trivial
(neutro).

b) Grupos de dos elementos:

Cualquier conjunto que contenga al neutro y a otro
elemento inverso de si mismo es subgrupo del dado.

c) Grupos de tres elementos:

Si queremos encontrar grupos de tres elementos
debemos buscar dos elementos que sean uno inverso del otro y que
además el primero operado con si mismo de el segundo y
viceversa.

d) Grupos de cuatro elementos:

Si el subgrupo de cuatro elementos tiene un inverso
de si mismo y una pareja, debemos comprobar que b
Û b =
c Û c
= a

Grupos Cíclicos

Decimos que un grupo es Cíclico cuando hay por lo
menos un elemento que genera todo el grupo. Los grupos
cíclicos son siempre conmutativos. El ejemplo de las
funciones no es cíclico, porque no existe elemento que
genere a todos.

Ejemplificación:

(Zn; Å
)

a) Por definición la suma de clases es otra
clase, por lo tanto es cerrada.

b) La suma de clases es asociativa y conmutativa porque
lo es la suma en Z.

c) La clase del cero funciona como elemento neutro en
base a la definición dada.

d) Cada clase x tiene su inverso en la clase
n-x

e) Para cualquier n, (Zn; Å ) es un grupo abeliano.

En todos los casos el elemento 1 genera a todos los
demás, por lo tanto son grupos cíclicos.

º 12

0’ = 0

1’ = 11

2’ = 10

3’ = 9

4’ = 8

5’ = 7

6’ = 6

Los números coprimos con n generan todo el
conjunto. Los divisores de n generan al conjunto de sus
múltiplos que constituyen subgrupos.

En las clases Zn con el producto de clases, debemos
retirar la clase del 0, que es absorbente para el producto, si n
es un número primo entonces (Zn -{ 0} ; Ä ) tiene estructura de grupo. El elemento
neutro es la clase del 1 y los inversos los encontramos en la
tabla correspondiente.

En Zn con el producto cuando n no es primo, veremos que
algunos elementos tienen inversos. El conjunto de estos elementos
es con el producto un grupo abeliano.

Si un grupo tiene cardinal infinito para probar que es
un subconjunto es subgrupo de él, debemos probar que la
operación es cerrada, que existe neutro y que cada
elemento tiene inverso.

Si el cardinal del grupo es finito, para probar que un
subconjunto es subgrupo basta mostrar que la operación es
cerrada en él.

Ejemplificación:

{ Z14
-{
0}
; Ä
}

INV = {
1,3,5,9,11,13}

1’ ® 1

2’ ® No

3’ ® 5

4’ ® No

7’ ® No

9’ ® 11

13’® 13

Subgrupos:

{
1;13}

{
1;3,5}
® No
válido

{
1;9,11}

{
1}

Red de subgrupos

Intersección de subgrupos:

1) Sean H1 y H2 elementos pertenecientes a la
intersección de h y k. eso significa que ambos pertenecen
a H, que por ser subgrupo contiene a H1 con H2.

2) Por pertenecer ambos a la intersección,
pertenecen a k, y como k es un subgrupo contiene a H1
Û H2. Por
pertenecer H1 Û H2 a ambos conjuntos pertenece a la
intersección.

El neutro pertenece a ambos subgrupos, por lo tanto
pertenece a la intersección.

3) La asociatividad se hereda de un grupo grande a
cualquier conjunto, y por lo tanto a la
intersección.

4) Si H pertenece a la intersección es porque
pertenece a H grande, que por ser subgrupo contiene a H’;
pero H pertenece también a k, que por ser subgrupo
contiene a k’; entonces k’ por pertenecer a h y k
pertenece a la intersección.

Congruencia Módulo H

Dado un grupo G, y un subgrupo H de él, definimos
la relación Congruencia Módulo H en G de la
siguiente manera:

a º
h b Û
a’ Û b Î H " a, b Î G Congruencia modulo H a
izquierda.

a º
h b Û
a Û
b’ Î
H " a,
b Î G
Congruencia modulo H a derecha.

a) a º
h a a’ Û a = e Î H Es reflexiva

b) a º
h b Þ
a’ Û b Î H Þ (a’ Û b’)
Î H
Þ b’
Û
(a’)’ Î H Þ b’Û a Î H Þ b º h a

Es Simétrica

c) a º
h b Þ
a’ Û b Î H

b º
h c Þ
b’ Û c Î H

Queda demostrado que º h es de equivalencia, por lo tanto
produce en G una partición en clase de equivalencia. La
clase del neutro es el subgrupo H, porque " elemento de H ° e es un elemento de
H.

La partición que produce es regular, por lo
tanto, cada clase tiene tantos elementos como el subgrupo H, si
G ¹ ¥ , de # n y H tiene # q Þ la cantidad de clases de
equivalencias es n/q, y el índice del subgrupo se obtiene
efectuando # G
/ #
H.

Ejemplificación:

G = (Z12; Å ) H = { 0;4;8}

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

Cuando el grupo es abeliano las coclases a izquierda y a
derecha son iguales.

Si el grupo no es infinito, entonces componiendo los
elementos de G con los del subgrupo se obtienen las coclases a
izquierda, y en cambio si componemos los elementos del subgrupo
con las de G obtenemos las coclases a derecha.

Ejemplificación:

F = {
F1; F2; F3; F4; F5; F6}

S = {
F1; F4}

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

Si un subgrupo genera coclases iguales, decimos que es
normal y entonces se cumple " G Ì al grupo grande, y " H Ì al subgrupo g’
Û h
Û g
Î H.

Una operación binaria definida en A x A, y una
relación definida en A son compatibles (~)
Û a ~ b
Ù c ~ d
Þ a
Û c ~
b Û
d.

Homomorfismos

Sean dos grupos G, G’, decimos que f, definida en
G ® G’
es un Homomorfismo Û

f (a Û b) = f (a) Û f(b).

Si f es sobreyectiva es un Epimorfismo. Si f es
inyectiva, entonces es un Monomorfismo. Si f es biyectiva
es un Isomorfismo. Si está definido un grupo en ese
mismo grupo es un Endomorfismo, y si además es
biyectiva, es un Automorfismo.

REDES

Dado un conjunto A y una relación de orden
definida en él, siendo el orden parcial, decimos que dicha
relación le da estructura de Red (también llamada
Retículo o Lápiz) al conjunto, si para cada par de
elementos existe un único máximo y un único
mínimo.

Toda red tiene un primer elemento que antecede a todos
los demás y uno último que sigue a todos los
demás, llamados Máximo Absoluto y
Mínimo Absoluto.

Decimos que dos elementos son Complementarios
cuando el mayor y el menor entre ellos son el mayor y el menor
absoluto. Si para todos los elementos del conjunto existe
complemento, decimos que la red es
Complementada.

Las operaciones mayor y menor pueden o no ser mutuamente
distributivas. Si lo son, la red es
Distributiva.

Redes del tipo P(A) con la
inclusión

Sea:

A = {
1,2,3}
{
P(A); Ì
}

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

• El mínimo absoluto es Æ .
• El máximo absoluto es A.
• Cada elemento tiene complemento respecto de
  A.
• En estos retículos el máximo es la
  unión y el mínimo la
  intersección.

Átomos de una red

Llamamos Átomos a los elementos del conjunto,
precedidos únicamente por el mínimo absoluto. En
nuestro ejemplo los átomos son los conjuntos de 1
elemento.

Subred

Si el conjunto S Ì A tiene a su vez estructura de red,
decimos que es una Subred.

Ejemplificación: S = { Æ ; 1; 2; 1,2}

Redes de divisores de n, con la relación
"divide a"

(D30; /)

D30 = {
1,2,3,5,6,10,15,30}

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

Mínimo absoluto: 1

Máximo absoluto: 30

Átomos: { 2,3,5}

Inversos: (Elementos que no se tocan entre
si)

1 = 30

2 = 15

3 = 10

5 = 6

S = { 3,6,15,30}

Máx = [a,b]

Mín = (a,b)

Redes complementadas:

Las redes del tipo P(A) con la
inclusión son siempre complementadas, y el complemento de
cada elemento es el complemento respecto del conjunto.

En las redes divisores de n con la relación
"divide a"; si dos números son complementados, su producto
es n, pero no todos son complementados.

Para que una red de este tipo sea
complementada n debe ser el producto de factores primos
distintos.

Ejemplificación:

30 = 2•3•5 Es complementada

/ de 12, siendo 12 = 2•2•3 No es
complementada

LENGUAJES

Llamamos Vocabulario a cualquier conjunto finito.
Siendo V un vocabulario cualquiera,

cada elemento de V es llamado Letra. Concatenar
dos o más letras es escribir una junto a la otra. La
concatenación de varias letras se llama Palabra
(también denominada Cadena o String).

Cualquier secuencia continua de letras de una palabra
que contenga a la primera letra es un Prefijo, si contiene
a la última letra es un Sufijo.

La palabra vacía o sin letras se simboliza con la
letra griega Lambda (l
).

R

La reflexión de una palabra W es la que tiene sus
letras invertidas. La reflexión es involutiva.

Ejemplificación:

Lidia = Aidil Juan = Nauj Pedro = Ordep

V* es el conjunto de palabras que pueden formarse con
las letras del alfabeto V. es un conjunto infinito siempre y
cuando V ¹
Æ .

Llamamos Lenguaje sobre un vocabulario V a
cualquier subconjunto de V*

Ejemplificación:

Sea N= {
0;1}

L1 = {
w Î
N* / long (w) £ 2} = {
0; 1; 00; 01; 10; 11}

L2 = {
w Î
N* / long (w) ³ 1} = {
0; 1; …}

L3 = {
w Î
N* / w termina en 1} = {
1; 01; 11; 001; 001; …}

L4 = {
w Î
N* / ç
ç
wç
ç
=2}
= { 00;
01; 10; 11}

L5 = {
w Î
N* / ç
ç
wç
ç = 4 y tiene un
1 solamente}
= { 1000;
0100; 0010; 0001}

Concatenar dos lenguajes es obtener otro lenguaje donde
cada palabra es concatenación de una palabra del primer
lenguaje con otra del segundo lenguaje.

L1 °
L2 = { w/w
= w1·
w2 w1 Î
L1 Ù
w2 Î
L2 }

Ejemplificación:

Sea:

L1 = {
l , 0, 1,
100}

L2 = {
0, 1, 01}

L1 L2 = {
0, 1, 01, 00, 001, 10, 11, 101, 1000, 1001,
10001}

ï ï L1 L2ç ç £
ç ç L1ç ç
° ç ç L2ç ç

Para la concatenación de lenguajes usamos la
notación exponencial

L³ = L¹ L¹ L¹

Lº = {
l } = L

L¹ =
L

Lª = Lª¯¹ L

¥

Clausura de Kleene U Lª

n=0

¥

Clausura Positiva U Lª

n=1

Producción:

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

Gramática:

Componentes: (Vt; Vn; S; P)

Vt es un conjunto finito de símbolos no
terminales.

Vt ¹
Æ , Vn
¹ Æ , Vt Ç Vn = Æ

S = Símbolo no terminal, inicial o cabecera del
lenguaje.

P = Conjunto de producciones X® Y con X ¹ l

Sea: Vt = {
a,b}

Vn = {
S,A,B}

S ®
a / A / B

A ®
l / Ab

B ®
b / bbB

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

Clasificación de Chomsky

Las gramáticas de Tipo 0 o Irrestrictas permiten
cualquier tipo de producción.

Las gramáticas del Tipo 1 o Sensibles al Contexto
son tales que en cada producción del tipo

X ®
Y la longitud de Y es mayor que la longitud de
X.

Las gramáticas de Tipo 2 o Independientes del
Contexto son las que admiten en las producciones X como un
único símbolo no terminal. En las de Tipo 3 o
Regulares X solo puede ser un símbolo no terminal, e y
puede ser la palabra vacía, un único
símbolo, o bien dos: uno terminal y otro no
terminal.

Dos gramáticas son equivalentes cuando generan el
mismo lenguaje.

AUTÓMATAS FINITOS

Componentes: (AE; E; e0; f; F)

AE: Es el lenguaje de
entrada, constituido, en el caso de lenguajes, por los elementos
del vocabulario.

E: Conjunto de estados necesarios para hacer el
reconocimiento.

e0: Estados iniciales.

f: Función que hace corresponder a cada estado con la
letra de entrada el estado
siguiente.

F: Conjunto de estados finales que se marcan con doble
círculo.

Ejemplo de autómata:

 Autor:

Banfield Crítico

Editado en febrero/marzo de 2005 por Banfield
Crítico.

Todos los textos presentes en esta edición
fueron extraídos durante la cursada de la materia
homónima en la Universidad
Tecnológica Nacional durante los meses de agosto de 2004 y
febrero de 2005.

El autor de esta obra no se responsabiliza por el
contenido de la misma, ni garantiza su funcionalidad en el
estudio.

Queda autorizada la duplicación por cualquier
medio óptico o digital en tanto no se utilice para fines
de lucro.

Si desea obtener una copia digital en formato PDF
escriba a la dirección de correo
electrónico citada arriba, solicitando dicho
material.