Vista previa del material en texto
[61.07] Matemática Discreta
Resumen para el parcial
Francisco Pirra
Índice
La idea de este resumen es que sirva como ayudamemoria y tener definiciones sin mucho
lenguaje matemático para estudiar de forma práctica, faltan varios temas, tiene el enfoque
de lo que creo que se suele tomar en el parcial.
Relaciones de orden
● Determinar si es relación de orden
● Matriz de adyacencia
● Orden total
● Orden parcial
● Retículo
● Elementos particulares
Relaciones de equivalencia
● Determinar si es relación de equivalencia
● Clases de equivalencia
● Conjunto cociente
● Partición
Algebra de Boole
● Probar que es un álgebra de Boole
● Determinar cantidad de subalgebras
● Hallar elementos del conjunto divisores de X
● Átomos
● Isomorfismos
● Probar propiedades
● Resolver ecuaciones y sistemas de ecuaciones
● Minterminos y Maxterminos
Principio de inducción
● Sumatorias
● Divisores
● Productorias
● Desigualdades
Ecuaciones de recurrencia
● Resolución de ecuaciones
● Construir ecuación en base a soluciones
● Construir ecuación en base a enunciado
Relaciones de orden
Determinar si es relación de orden
Se debe verificar que se cumpla:
● Reflexividad: xRx
(el elemento x está relacionado con si mismo)
● Antisimetría: xRy ᴧ yRx > y=x
(x está relacionado con y, y relacionado con x, entonces son el mismo elemento)
● Transitividad: xRy ᴧ yRz > xRz
(x está relacionado con y, y relacionado con z, entonces x está relacionado con z)
Matriz de adyacencia
Es una matriz binaria, que representa en la posición (f,c):
● Con 1: El elemento f (correspondiente a la fila) está relacionado con el elemento c
(Correspondiente a la columna)
● Con 0: El elemento f, no está relacionado con el elemento c
Por lo que podemos notar que la matriz se lee: “elementoFila” R “elementoColumna”
Orden total
Todos los elementos del conjunto deben estar relacionados, osea todos son comparables
con los demás
(Si lo vemos desde un diagrama de hasse, debe ser una línea única)
Orden parcial
Existe algún elemento que no está relacionado con otro del conjunto, por lo tanto no es
comparable con dicho elemento
(Lo más común de ver, cuando vemos que hay varias ramas, no podemos comparar un
elemento de una rama con otro de otra rama, ya que no sabemos cual precede a cual)
Retículo
Si el conjunto es parcialmente ordenado, y el ínfimo y supremo pertenecen al conjunto,
entonces es un retículo
Elementos particulares
Dado que tenemos un conjunto, en general vamos a analizar sobre su diagrama de Hasse,
algunos elementos particulares.
Vamos a dividir los mismos en dos grupos, aquellos que necesariamente pertenecen al
conjunto y aquellos que no necesariamente
No necesariamente pertenecen al conjunto:
● Cotas superiores: Pueden ser varias, y son aquellos elementos para los cuales,
cualquier elemento del conjunto está relacionado con dicho elemento (x es cota
superior del conjunto A, si para cualquier elemento a de A, aRx)
● Cotas inferiores: Pueden ser varias, y son aquellos elementos para los cuales, estan
relacionados con cualquier elemento del conjunto (x es cota inferior del conjunto A,
si para cualquier elemento a de A, xRa)
● Supremo: La menor de las cotas superiores
● Ínfimo: La mayor de las cotas inferiores
Necesariamente pertenecen al conjunto:
● Máximo: Es el supremo, pero debe estar en el conjunto (Por lo que si no hay
supremo, no hay máximo)
● Mínimo: Es el ínfimo, pero debe estar en el conjunto (Por lo que si no hay ínfimo, no
hay mínimo)
● Maximales: Los elementos maximales, son aquellos que no se relacionan con otro
elemento del conjunto (osea que x es maximal, x noR m ), si se relaciona con otro
elemento que no sea del conjunto, sigue siendo maximal
● Minimales: Los elementos minimales, son aquellos para los cuales no hay
elementos, del conjunto, que se relacionen con ellos (osea que x es minimal, m
noR x ), si tiene a otro elemento que no es del conjunto y se relaciona con el, sigue
siendo minimall
Relaciones de equivalencia
Determinar si es relación de equivalencia
Se debe verificar que se cumpla:
● Reflexividad: xRx
(el elemento x está relacionado con si mismo)
● Simetría: xRy > yRx
(x está relacionado con y, entonces y relacionado con x)
● Transitividad: xRy ᴧ yRz > xRz
(x está relacionado con y, y relacionado con z, entonces x está relacionado con z)
Clases de equivalencia
Si tenemos un elemento a1 que pertenece a un conjunto A, entonces llamaremos clase de
equivalencia de a1 al conjunto que tiene como elementos todos los b que pertenecen a A y
están relacionados con a1
[a1] = { b1, b2, … } siempre que b1, b2, … estén relacionados con a1, osea b1Ra1,
b2Ra1.
Conjunto cociente
Es el conjunto de todas las clases de equivalencia, se nota: A/R = { [a1], [a2], …, [an] }
Partición
Una partición de un conjunto, es una división del mismo en subconjuntos disjuntos (osea
que no tienen elementos en común) no vacíos
Algebra de Boole
Probar que es un álgebra de Boole
Para verificar que se trate de un álgebra de Boole, lo que debemos chequear es que se
cumplan los axiomas.
La forma más sencilla, aunque puede ser larga si tiene varios elementos, es hacer las tablas
de la suma y el producto.
A continuación veremos los axiomas a cumplir, y como los justificamos con las tablas:
● Neutros: Son aquellos, que en su respectiva tabla, dan el mismo valor al cual se lo
está operando (si 15 fuera neutro del producto, 2 . 15 = 2; si 8 fuera neutro para la
suma, 8 + 5 = 5)
● Conmutatividad: Se ve con la simetría de la tabla
● Asociatividad: Se puede probar para cada elemento, o justificar en base al
producto y suma definido
● Distributividad: Se puede probar para cada elemento, o justificar en base al
producto y suma definido
● Complementos: Son aquellos que nos muestre la tabla que al “sumarlos” nos dan el
1 del álgebra, osea el neutro del producto
Determinar cantidad de subalgebras
Dada un álgebra de Boole, un conjunto no vacío de B es una subalgebra si para
todo x e y pertenecientes a A:
● x + y pertenece a A
● x * y pertenece a A
● x ' pertenece a A
Toda subalgebra deberá tener los mismos elementos neutros para la suma y
producto que la álgebra principal, asi como tambien deben estar los complementos
de los elementos que elijamos para el subalgebra.
Hallar elementos del conjunto divisores de X
Divisores de 210, divisores de 6, divisores de 12… suelen ser conjuntos que se piden en la
materia, la forma de encontrar los elementos de estos conjuntos es descomponer el número
en factores primos y luego ir variando el exponente (0 y 1) para armar todos los posibles
valores.
Ej: Divisores de 42
● 2^1 * 3^1 * 7^1 = 42
● 2^0 * 3^1 * 7^1 = 21
● 2^1 * 3^0 * 7^1 = 14
● 2^1 * 3^1 * 7^0 = 6 Vemos como variando los exponentes,
● 2^0 * 3^0 * 7^1 = 7 obtenemos todos los divisores de 42.
● 2^0 * 3^1 * 7^0 = 3
● 2^1 * 3^0 * 7^0 = 2
● 2^0 * 3^0 * 7^0 = 1
Átomos
Los átomos son los elementos que están relacionados inmediatamente con el 0 para el
álgebra de boole, osea relacionados con el neutro para la suma
Si tiene el álgebra de Boole tiene n átomos, entonces tiene 2^n elementos
El producto de cualquier elemento con un átomo, es cero o el átomo.
Isomorfismos
Para poder encontrar un isomorfismo entre dos álgebras de Boole, se debe cumplir:
● Para todo elemento de B1: F(X +1 Y) = F(X) +2 F(Y)
(Osea que la transformada de la suma definida en la primer álgebra de boole, debe
ser igual a la suma definida en la segunda álgebra de Boole, de las transformadas)
● Para todo elemento de B1: F(X *1 Y) = F(X) *2 F(Y)
(Osea que la transformada del producto definido en la primer álgebra de boole, debe
ser igual al producto definido en la segunda álgebrade Boole, de las transformadas)
● Para todo elemento de B1: F(X’1) = F(X)’2
(Osea que la transformada del complemento definido en la primer álgebra de boole,
debe ser igual al complemento definido en la segunda álgebra de Boole, de la
transformada)
Propiedades:
● Los átomos de B1, al transformarse, deben ir a átomos de B2
● La transformada del cero de B1, debe ir al cero de B2 y lo mismo con el uno.
● Si xRy entonces F(x) R F(y)
● La cantidad de isomorfismos entre dos álgebras de boole, es n! siendo n el numero
de atomos (Notar que para que haya un isomorfismo, deben tener la misma cantidad
de átomos)
Probar propiedades
Para probar propiedades de álgebra de boole hay que usar los cinco axiomas mencionados
anteriormente
Resolver ecuaciones y sistemas de ecuaciones
La clave para resolver ecuaciones y sistemas de ecuaciones, es tener en cuenta los
elementos neutros para la suma y el producto
Lo que va a ir sucediendo es que nos quedan términos cada vez más chicos y luego
podremos despejar
Es importante tener en cuenta que para cualquier álgebra de boole, vale que:
xRy: x<y <> x.y=x ᴧ x+y=y ᴧ x.y’=0
Propiedades para utilizar en operaciones de álgebras de boole
x + y = 0 > (x = 0) ᴧ (y = 0)
x . y = 1 > (x = 1) ᴧ (y = 1)
(x + y’ = z + y’ ᴧ x + y = z + y ) > x = z
x + y’ = x . y > x = y
NO es válido:
x . y = 0 > (x = 0) ᴧ (y = 0)
x + y = y + z > x = z
Minterminos
Son de la forma m = x . y . z
Están asociados a la forma disyuntiva (que es sumatoria de productos)
Cuando se habla de la forma normal disyuntiva, es agregar todos los términos para que en
cada mintérmino, figuren todas las variables de la función
Maxterminos
Son de la forma M = x + y + z
Están asociados a la forma conjuntiva (que es productoria de sumas)
Cuando se habla de la forma normal conjuntiva, es agregar todos los términos para que en
cada maxtérmino, figuren todas las variables de la función
Principio de inducción
Dada una afirmación P(n) queremos probar que sea cierta para cualquier valor de n natural
Lo que nos dice el principio de inducción es que:
● P(n0) es verdadero
(osea tomamos el primer valor de n, en general 1)
● P(n) → P(n+1) es verdadero
(Siendo P(n) la hipótesis inductiva, y P(n+1) la tesis inductiva)
Si ambos puntos se cumplen, entonces P(n) vale para todo valor de n a partir del tomado
como n0
La idea en general será suponer cierta la hipótesis inductiva, y tratar de utilizarla para llegar
a probar la tesis
Sumatorias
En general, son sumatorias igualadas a unos términos.
Se plantea la primer parte de la igualdad, y se saca para afuera de la sumatoria el término
con n+1, entonces nos va a quedar la sumatoria igual que la de la hipótesis y ahí podremos
utilizarla para reemplazar.
Para facilitar el trabajo, lo que se puede hacer es “desglosar” el lado de la igualdad a la cual
queremos llegar en P(n+1), de forma que sea más fácil y no tengamos problemas de cómo
agrupar los términos.
Divisores
Si me dan un enunciado del tipo x | y, me estan diciendo que y = x*k osea que x divide a y.
En este tipo de ejercicios se suele tener que desarmar todo el término cuando evaluamos
en n+1 y buscamos cómo reagrupar para que podamos reemplazar la hipótesis.
La clave está en agrupar valores que podamos definir en una nueva constante k’ por
ejemplo y de esa forma simplificar la expresión para poder llegar a demostrar la igualdad.
También puede ser que tengamos que pasar algun termino en la hipótesis, para que nos
quede de una forma que podamos usar fácilmente en la tesis.
Productorias
Se procede de la misma forma que con las sumatorias
Desigualdades
En este caso, en general se multiplican, dividen, suman o restan valores a la hipótesis (de
ambos lados para mantener el valor intacto) buscando que nos quede algo de la misma
forma que una de las partes de la tesis, entonces podamos utilizar la hipótesis para llegar a
probarla.
Otro truco es que si tenemos un número en la hipótesis, lo podemos reescribir como suma
de otros dos, por ejemplo 7 = 4 + 3, y eso haga capaz que podamos usar el 4 o 3, según
nos convenga, para poder hacer cuadrar con la tesis.
El enfoque va a estar orientado sobretodo a “trabajar” el término de la hipótesis.
Ecuaciones de recurrencia
Son ecuaciones definidas de forma recursiva, cada término está relacionado con el anterior
Resolución de ecuaciones
La solución general a cualquier ecuación de recurrencia será de la forma:
Xn = Xh + Xp
Siendo Xh la solución de la homogénea (osea la que está igualada a cero) y Xp una
solución particular (Si es que tenemos alguna función, con la cual igualar la ecuación, sino
la particular es cero)
Solución del homogéneo Xh:
Una vez igualada a cero la ecuación, se escribe el “polinomio característico”, que es
simplemente reemplazar por λ^n = Xn+1, y luego busco las raíces de dicho polinomio.
Acá podemos tener varios casos:
● Si k es la única solución, porque solo tiene una raíz, entonces Xh = A*k^n
● Si hay dos raíces, k y j:
○ k = j, entonces Xh = A*k^n + B*n*k^n
○ k ≠ j, entonces Xh = A*k^n + B*j^n
Solución a la particular Xp:
Para encontrar una solución particular, la idea es proponer una solución (siguiendo la
siguiente tabla), para evaluar la solución propuesta en la ecuación, y buscar despejar los
valores de las constantes y así tener definida la particular buscada.
F(n) a la cual está igualada la ecuación Xp propuesta en base a dicha función
C*a^n (a no es raíz del poli. característico) D*a^n
C*a^n (a es raíz de multiplicidad j del poli.) D*n^j * a^n
Polinomio de grado k y 1 no es raíz del
poli. característico
Polinomio genérico de grado k
Polinomio de grado k y 1 es raíz de
multiplicidad j del poli. característico
Polinomio genérico de grado k, multiplicado
por n^j
A*Sen(Xn) o B*Cos(Xn) D*Sen(Xn) + C*Cos(Xn)
Notar que el valor de a, es el que tiene realmente en la función a la cual está igualada la
ecuación, osea que no ponemos un a genérico, sino el valor directamente.
Es importante tener en cuenta, que si en la ecuación de recurrencia, tenemos términos que
son variables (osea que estan multiplicados por n por ejemplo) debemos hacer un cambio
de variables para lograr que quede con términos constantes
Construir ecuación en base a soluciones
Tengo que construir una ecuación de la forma: Xn+1 = an*Xn + bn*Xn, y la idea es que me
dan las soluciones Vn y Un.
Entonces simplemente lo que debo hacer es reemplazar cada una en la ecuación, y luego
resolver para encontrar el valor de an y bn.
A modo de ejemplificar de mejor modo, veamos como quedaría reemplazada la ecuación:
● Con Vn: Vn+1 = an*Vn + bn*Vn
(Si Vn = n > n+1 = an*n + bn*n )
● Con Un: Un+1 = an*Un + bn*Un
(Si Un = 2n+1 > 2(n+1)+1 = an*(2n+1) + bn*(2n+1)
Luego resolvemos el sistema de dos ecuaciones con dos incógnitas, y listo, reemplazamos
en la ecuación Xn+1 = an*Xn + bn*Xn el valor de an y bn encontrados.
Construir ecuación en base a enunciado
Es el caso más complejo, la idea es la siguiente:
● Leer el enunciado y reescribir de forma explícita y lo más simple posible
● Graficar, si es que se puede, para tener mejor visualización
● Escribir los primeros pasos (para 1, para 2, etc) para ir viendo cómo evolucionan los
valores, a medida que aumenta
● Escribir una ecuación que cumpla con la lógica que vimos al hacer los pasos, y
verificamos poniéndole valores
