ED - Apunte v.24
ED - Apunte v.24
Discretas.
Apunte de clase
JULIETA MATTEUCCI
– LICENCIATURA EN GESTIÓN DE
TECNOLOGÍAS DE LA INFORMACIÓN
– ESTRUCTURAS DISCRETAS (6004)
UNPAZ – LGTI (6004)
2024
Estructuras Discretas
¿Así que has decidido embarcarte en este maravilloso viaje de la matemática? Bien, mi joven
aprendiz, antes de arrancar, has de saber algunas reglas importantes.
Reglas
1) Equivocarse está bien. No te olvides que de los errores aprendemos así que los celebramos.
Thomas Alva Edison, un gran inventor de principio del siglo XX, famoso por inventar,
entre otras cosas, la bombilla eléctrica (lo que conocemos como lamparita)
dijo: “No fracasé 999 veces, descubrí 999 maneras de cómo NO hacer
una bombilla”. Así que te sugiero lo siguiente: No borres tus errores.
Cuando te equivoques, en lugar de borrar, hazles una gran X tachándolos
(pero que aún se vean) y escribe al lado por qué no es correcto. De esta
forma, cuando vuelvas a tus apuntes a repasar o estudiar, podrás verlo y
recordar que esa no es una forma correcta de hacerlo. Es preferible tener 10
páginas tachadas que una sola correcta después de haberla borrado 10 veces.
3) Mi objetivo no es que apruebes. Se que suena feo y ahora querrás ir corriendo a cambiarte a
otra comisión con alguien más accesible (y capaz pienses que estoy loca, y puede que
tengas algo de razón), pero es cierto. Mi objetivo para esta materia no es que apruebes,
busco algo más grande y es que aprendas. Si aprendes, seguramente vayas a aprobar,
pero se puede aprobar sin aprender y eso es lo que no quiero que pase. Si solo
apruebas, te olvidarás las cosas muy rápido y lo vas a sufrir más adelante. Sin embargo,
si aprendes, es más fácil reflotar lo que se puede escapar de la cabeza y, además, no
todo el aprendizaje de esta materia es de matemática. Quiero que aprendas otras
habilidades también que, aunque no las reconozcas de entrada, las usarás por mucho
tiempo.
Ahora que ya sabes cómo vamos a manejarnos, supongo que te interesará saber la
modalidad de trabajo y la forma de aprobar (ya que la malvada docente, parece, no tiene eso
como objetivo y dependerá de ti).
Hoja de Ruta
“-Lee las instrucciones y claramente serás
dirigida en la dirección correcta.” Le dijo a
Alicia la perilla de la puerta.
Lewis Carrol – Alicia en el país de las
maravillas.
Acá les voy a contar un poco sobre la materia y cómo está organizada.
Esta es una materia que en gran parte es de matemática, pero muy inclinada a la computación,
por eso muchos de los temas que vamos a ver no se parecen tanto a los temas “clásicos” de
matemática.
La materia está dividida en 5 unidades y, desde el día uno, tienen acceso a la totalidad del
material teórico-práctico en un apunte hecho especialmente para ustedes. Lo que nos lleva,
ahora, a hablar de la metodología de las clases.
Como saben, esta materia tiene un total de 4 horas de cursada semanales. Pero esto no quiere
decir que, por tener clases presenciales, estas siguen una modalidad “Clásica”. En esta materia,
se espera dediquen gran parte de las horas al trabajo del material.
Durante los días de cursada, trabajarán en grupos con el material y, en la última parte de la
materia realizaremos una puesta en común y resolveremos algunas cosas. En general,
trabajaremos con una modalidad taller. Lo ideal sería que, semana a semana, traigan el
material leído para poder aprovechar al máximo el trabajo en el aula. No habrá clase expositiva.
Buscamos que empiecen a generar un poco de autonomía.
No todos los ejercicios se resuelven de una única manera, por lo que el intercambio va a ser muy
rico para todo el grupo. No se espera que sólo participen aquellos y aquellas que NO tienen
dudas o tienen las respuestas correctas. En esta materia nos interesa que todos y todas
participen, que hagan preguntas y de esta manera podamos aprender entre todos y todas. El
trabajo en grupo está para debatir, compartir información, ayudarnos entre todos y todas y
trabajar mucho.
Al finalizar las primeras 3 unidades y al final del cuatrimestre, tendremos las dos instancias de
evaluación (parciales) que serán individuales. Ambos parciales pueden ser recuperados, pero,
cuidado, la nota del recuperatorio tapa la nota del parcial, para bien o para mal.
Para regularizar la materia, deberán tener ambos parciales aprobados (con nota 4 o más), lo que
les habilitará la posibilidad de rendir, al finalizar la cursada, un examen integrador. La materia
se aprueba, al aprobar este integrador. Si aprobaron los parciales, pero no el integrador, la
materia les queda regular (pueden cursar las que siguen) y deberán rendir final. Pero como no
quiero que piensen que en la materia somos malévolas, la materia es promocionable. Esto
significa que, si lo hacen lo suficientemente bien en los parciales reciben un premio. Y ese
premio es que no tienen que rendir integrador y con los parciales alcanza. Ahora, ¿qué es hacer
las cosas lo suficientemente bien como para acceder a este maravilloso premio? Tienen que
tener un mínimo de 7 en cada parcial (o recuperatorio). Es bien fácil.
Arranquemos ejercitando las neuronas… Miren (y piensen, antes de seguir leyendo) el siguiente
problema:
En cada una de las siguientes cajas hay un metal, que puede ser oro, plata o cobre. No sabemos
en qué caja está cada metal. Lo único que sabemos es que las tres cajas están etiquetadas, y
que una (SOLO UNA) de esas etiquetas está mal. ¿Puedes averiguar en qué caja está cada metal?
Ahora que ya lo pensaron un buen rato (espero que no hayan abandonado rápido), vamos a ir
analizando la situación, y en el medio ir viendo algunos conceptos e ideas…
Cada caja tiene una afirmación1 que puede ser cierta o no (pero no ambas). Eso es lo que en
lógica denominamos una proposición.
Enunciemos esto:
Definición:
Llamamos proposición a un enunciado que puede ser verdadero o falso (pero no ambos).
Normalmente, a las proposiciones, se las nombra con las letras del abecedario, arrancando en
la letra 𝑝.
1
Usamos la palabra “afirmación” aunque esté el negativo. Así frases como “Acá no está la plata” es una
afirmación desde el punto de vista de la lógica.
Prof. Julieta Matteucci 4
UNPAZ – LGTI (6004)
2024
Estructuras Discretas
A) Que las proposiciones “En la caja naranja está el oro” y “En la caja verde no está la plata”
sean Verdaderas y “En la caja azul está la plata” sea Falsa.
B) Que las proposiciones “En la caja naranja está el oro” y “En la caja azul está la plata”
sean Verdaderas y “En la caja verde no está la plata” sea Falsa.
C) Que las proposiciones “En la caja azul está la plata” y “En la caja verde no está la plata”
sean Verdaderas y “En la caja naranja está el oro” sea Falsa.
Si A) es la combinación correcta, queda que la caja azul es la que miente al decir que tiene la
plata, quedando:
Lo que lleva a una problema, ya que la plata no podría estar en ninguna caja. Por lo que
concluimos que A) no es una combinación correcta.
Si B) es la combinación correcta, queda que la caja verde es la que miente al decir que no tiene
la plata (es decir, que sí tiene plata), quedando:
Lo que lleva, nuevamente, a una problema, ya que la plata estaría en dos cajas, sin dejar lugar
al cobre. Por lo que concluimos que B) no es una combinación correcta.
Si C) es la combinación correcta, queda que la caja naranja es la que miente al decir que tiene el
oro quedando:
Lo que lleva, a que la plata esté en la caja azul, dejando oro y cobre libres. Como en la naranja
no hay oro, el oro debe estar en la verde y el cobre, en la que queda:
Este razonamiento, lo hicimos sin apelar a grandes conceptos ni teoría, pero nos sirve para
pensar y sacar algunas conclusiones. Por ejemplo, las tres afirmaciones que analizamos, fueron
construidas “juntando” las proposiciones originales. Formalicemos un poco esto antes de
seguir:
• ¬ No (Negación)
• ∧ Y (Conjunción)
• ∨ O (Disyunción)
• ⇒ Implica (Condicional)
• ⇔ Si y sólo si (Bicondicional)
Así es que, esta parte de la materia se llama “lógica proposicional” 2 , ya que trabaja con
proposiciones y analiza el proceso a través del cual, partiendo de enunciados más simples,
capaces de formar proposiciones de mayor complejidad, se pueden deducir conclusiones.
Antes de seguir avanzando, miremos con un poco más de detalles estos conectores lógicos y
cómo influyen en el valor de verdad de una proposición:
¬ No (Negación)
Si tenemos una proposición 𝑝, podemos definir una nueva proposición, llamada ¬𝑝 (lo leemos
como “no p” cuyo valor de verdad es el opuesto al que tenía 𝑝.
𝒑 ¬𝒑
𝑉 𝐹
𝐹 𝑉
2
También se llama lógica de enunciados o cálculo proposicional.
Prof. Julieta Matteucci 6
UNPAZ – LGTI (6004)
2024
Estructuras Discretas
falsa, entonces una nueva proposición que sea “en la caja naranja no está el oro” será
verdadera.
∧ Conjunción (Y)
Si tenemos dos proposiciones 𝑝, 𝑞, podemos definir una nueva proposición, llamada 𝑝 ∧ 𝑞 (lo
leemos como “p y q” cuyo valor de verdad dependerá del valor de verdad de ambas.
Pensémoslo un poco. Si un aviso de búsqueda de trabajo, solicita a alguien que maneje lenguaje
JAVA y sepa INGLES, las únicas personas que servirán para ese trabajo, son las que verifiquen
ambas condiciones. Lo mismo ocurre con una conjunción, la nueva proposición sólo será
verdadera (solo sirve para el trabajo) si las dos que la generaron lo son (si sabe Inglés y Java).
Como ahora tenemos dos proposiciones (y cada una puede ser V o F) tenemos 4 combinaciones.
(que las dos sean verdaderas, que las dos sean falsas, que 𝑝 sea verdadera y 𝑞 sea falsa, o que
𝑝 sea falsa y 𝑞 verdadera):
𝒑 𝒒 𝒑∧𝒒
𝑉 𝑉 𝑉
𝑉 𝐹 𝐹
𝐹 𝑉 𝐹
𝐹 𝐹 𝐹
Como vemos, la única fila en la que el resultado de la conjunción da verdadera, es cuando las
dos originales son verdaderas.
∨ Disyunción (O)
Si tenemos dos proposiciones 𝑝, 𝑞, podemos definir una
¿Y en programación?
nueva proposición, llamada 𝑝 ∨ 𝑞 (lo leemos “p o q” )
cuyo valor de verdad dependerá, al igual que con la Por ejemplo, en muchos de los lenguajes, el
conjunción, del valor de verdad de ambas. Pensémoslo “o” se denota por || y el “y” se usa con &&.
un poco. Si un aviso de búsqueda de trabajo, solicita a En las expresiones que incluyen algunos o
alguien que maneje lenguaje JAVA o PYTHON, las únicas todos los operadores es importante la
personas que servirán para ese trabajo, son las que presencia de paréntesis que jerarquicen los
verifiquen alguna de las dos condiciones (podrían operadores. Ante la ausencia de éstos,
verificar ambas, pero no es requisito). Dicho de otra primero se evalúa el “no” , después el “y” y,
finalmente el “o”. Esta convención se
forma, las únicas personas que no sirven para el trabajo
conoce como precedencia del operador y es
son las que no saben ninguna de las dos cosas. Lo mismo parecido a lo que se hace en matemática,
ocurre con una disyunción, la nueva proposición sólo dándole prioridad al producto (y cociente)
será falsa (no sirve para el trabajo) si las dos que la por sobre la suma (y la resta).
generaron lo son (si no sabe Java ni Python). Como, al
igual que con la conjunción, tenemos dos proposiciones (y cada una puede ser V o F) tenemos 4
combinaciones. (que las dos sean verdaderas, que las dos sean falsas, que 𝑝 sea verdadera y 𝑞
sea falsa, o que 𝑝 sea falsa y 𝑞 verdadera):
𝒑 𝒒 𝒑∨𝒒
𝑉 𝑉 𝑉
𝑉 𝐹 𝑉
𝐹 𝑉 𝑉
𝐹 𝐹 𝐹
Como vemos, la única fila en la que el resultado de la disyunción da falsa, es cuando las dos
originales son falsas.
⇒ Implica (Condicional)
Si tenemos dos proposiciones 𝑝, 𝑞, podemos definir una nueva proposición, llamada 𝑝 ⇒ 𝑞 (lo
leemos como “p implica q” o “Si P entonces q” cuyo valor de verdad, al igual que en los
casos anteriores, dependerá del valor de verdad de ambas.
Pensémoslo un poco. Acá las cosas son un poco distintas a las anteriores, ya que hay una
implicancia involucrada. Cuando hablamos de 𝑝 ⇒ 𝑞, a la p (que está antes de la flecha) la
llamamos antecedente, premisa o hipótesis, mientras que, a la q, es el consecuente o la
conclusión. Entonces, analizar el valor de verdad de este conector nos lleva a analizar la manera
en la que antecedente y consecuente se vinculan (la ⇒). No establece una relación de causa
entre antecedente y consecuente.
Entonces, ahora ya estamos en condiciones de resumir la relación que hay entre el valor de
verdad de la implicancia con el de las proposiciones que la forman:
𝒑 𝒒 𝒑⇒𝒒
𝑉 𝑉 𝑉
𝑉 𝐹 𝐹
𝐹 𝑉 𝑉
𝐹 𝐹 𝑉
⇔ Si y sólo si (Bicondicional)
Si tenemos dos proposiciones 𝑝, 𝑞, podemos definir una nueva proposición, llamada 𝑝 ⇔ 𝑞 (lo
leemos como “p s1 y sólo si q” cuyo valor de verdad, al igual que en los casos anteriores,
dependerá del valor de verdad de ambas.
𝑝 ⇔ 𝑞 es lo mismo que (𝑝 ⇒ 𝑞) ∧ (𝑞 ⇒ 𝑝)
Analicemos el valor de verdad de lo que pusimos en la derecha:
(𝑝 ⇒ 𝑞) ∧ (𝑞 ⇒ 𝑝)
Al igual que un ejercicio combinado de matemática, lo vamos mirando de adentro hacia
afuera. Partimos de las proposiciones originales, p y q lo que nos da 4 combinaciones:
𝒑 𝒒
𝑉 𝑉
𝑉 𝐹
𝐹 𝑉
𝐹 𝐹
𝑉 𝑉 𝑉 𝑉
𝑉 𝐹 𝐹 𝑉
𝐹 𝑉 𝑉 𝐹
𝐹 𝐹 𝑉 𝑉
𝑉 𝑉 𝑉 𝑉 𝑉
𝑉 𝐹 𝐹 𝑉 𝐹
𝐹 𝑉 𝑉 𝐹 𝐹
𝐹 𝐹 𝑉 𝑉 𝑉
𝒑 𝒒 𝒑⇔𝒒
𝑉 𝑉 𝑽
𝑉 𝐹 𝑭
𝐹 𝑉 𝑭
𝐹 𝐹 𝑽
Vemos que un “si y sólo sí”, solo es verdadero si 𝒑 y 𝒒 tienen el mismo valor de verdad (o ambas
verdaderas, o ambas falsas).
Tablas de verdad
Como dijimos antes, la idea de una tabla de verdad, es una tabla que nos permite analizar los
distintos valores de verdad que puede tomar una proposición compuesta, para cada una de las
posibles combinaciones de verdad-falsedad que toman las proposiciones simples que la forman.
Trabajaremos con fórmulas, armadas con letras proposicionales, valores de verdad, conectores
y paréntesis. Las fórmulas (o enunciados o proposiciones compuestas) con las que trabajemos,
deben estar bien formuladas. Para esto hay que cuidar, por ejemplo, que los conectores estén
aplicados correctamente. Si es un conector binario (es decir, uno de los que unen 2
proposiciones) debe vincular dos proposiciones. Si es una negación, debe tener alguna
proposición a negar.
(𝒑 ⇒ 𝒒) ∧ (𝒒 ∨ ¬𝒑)
[(𝒑 ⇒ ¬𝒒) ∨ (𝒒 ∧ 𝒑)] ⇔ 𝒓
(𝒑 ∨ 𝑽) ∧ (𝑭 ⇒ 𝒑)
Ejemplos de fórmulas mal formuladas:
(𝒑 ⇒ 𝒒) ∧ (𝒒 ∨)
𝒑⇔¬
𝒑¬ ∧ 𝑭
Otra cosa que tendremos en cuenta es el orden o jerarquía de los operadores. Como fue dicho
en el 2do recuadro ¿Y en programación? la jerarquía de los conectores, que es algo que
determina en qué orden se van a realizar las operaciones, viene dada por:
¬ ∧ ∨ ⇒ ⇔
Analizar Analizar
Primero último
Ahora sí, realicemos la tabla de verdad de algunas fórmulas. Por ejemplo, analicemos:
(𝒑 ⇒ 𝒒) ∧ (𝒒 ∨ ¬𝒑)
Como este es un primer ejemplo, vamos a ir paso a paso (después iremos salteándonos algunos
o haciéndolos de manera simultánea)
Lo primero que identificamos es cuántas opciones vamos a tener. En este caso, hay solo 2 letras
proposicionales, por lo que tenemos 4 combinaciones diferentes:
𝒑 𝒒
𝑉 𝑉
𝑉 𝐹
𝐹 𝑉
𝐹 𝐹
Analizando de adentro hacia afuera. Vemos que tenemos un “¬𝒑” por lo que es lo primero que
hacemos:
𝒑 ¬𝒑 𝒒
𝑉 𝐹 𝑉
𝑉 𝐹 𝐹
𝐹 𝑉 𝑉
𝐹 𝑉 𝐹
Ahora nos vamos a preocupar por hacer una columna para el resultado de cada paréntesis:
𝒑 ¬𝒑 𝒒 𝒑⇒𝒒 𝒒 ∨ ¬𝒑
𝑉 𝐹 𝑉
𝑉 𝐹 𝐹
𝐹 𝑉 𝑉
𝐹 𝑉 𝐹
Para completar la columna verde la de la implicancia, miro solamente los valores de verdad de
𝒑 y de 𝒒 (columnas blancas). Es una implicancia, por lo que solo es falsa si el antecedente es
verdadero y el consecuente falso:
𝒑 ¬𝒑 𝒒 𝒑⇒𝒒 𝒒 ∨ ¬𝒑
𝑉 𝐹 𝑉 𝑉
𝑉 𝐹 𝐹 𝐹
𝐹 𝑉 𝑉 𝑉
𝐹 𝑉 𝐹 𝑉
Para completar la columna azul la de la disyunción, miro solamente los valores de verdad de
𝒒 (columna blanca) y de “¬𝒑” (columna naranja). Es una disyunción, por lo que solo es falsa si
ambas partes lo son:
𝒑 ¬𝒑 𝒒 𝒑⇒𝒒 𝒒 ∨ ¬𝒑
𝑉 𝐹 𝑉 𝑉 𝑉
𝑉 𝐹 𝐹 𝐹 𝐹
𝐹 𝑉 𝑉 𝑉 𝑉
𝐹 𝑉 𝐹 𝑉 𝑉
Finalmente, para el operador final, solo vamos a tener en cuenta las últimas dos columnas, ya
que son las que se vinculan con el conector. Como es una conjunción, sabemos que solo es
verdadero, si ambas proposiciones lo son. De esta forma, ya estamos en condiciones de
completar la tabla:
𝒑 ¬𝒑 𝒒 𝒑⇒𝒒 𝒒 ∨ ¬𝒑 (𝒑 ⇒ 𝒒) ∧ (𝒒 ∨ ¬𝒑)
𝑉 𝐹 𝑉 𝑉 𝑉 𝑉
𝑉 𝐹 𝐹 𝐹 𝐹 𝐹
𝐹 𝑉 𝑉 𝑉 𝑉 𝑉
𝐹 𝑉 𝐹 𝑉 𝑉 𝑉
Veamos otro ejemplo, hacer la tabla de verdad de: (𝒑 ∧ 𝒒) ⇒ (𝒑 ∨ ¬𝒓) . Acá tenemos 3
variables, por lo que nos va a dar 8 posibles combinaciones:
𝒑 𝒒 𝒓
𝑉 𝑉 𝑉
𝑉 𝑉 𝐹
𝑉 𝐹 𝑉
𝑉 𝐹 𝐹
𝐹 𝑉 𝑉
𝐹 𝑉 𝐹
𝐹 𝐹 𝑉
𝐹 𝐹 𝐹
Ahora, entonces, tenemos que ir completando los valores de verdad para ¬𝒓 , (𝒑 ∧ 𝒒),
(𝒑 ∨ ¬𝒓) y (𝒑 ∧ 𝒒) ⇒ (𝒑 ∨ ¬𝒓). ¿Se animan a pensarlo? (Nuevamente: NO HAGAN TRAMPA,
Completen y después pasen de página):
𝒑 𝒒 𝒓 ¬𝒓 𝒑∧𝒒 𝒑 ∨ ¬𝒓 (𝒑 ∧ 𝒒) ⇒ (𝒑 ∨ ¬𝒓)
𝑉 𝑉 𝑉
𝑉 𝑉 𝐹
𝑉 𝐹 𝑉
𝑉 𝐹 𝐹
𝐹 𝑉 𝑉
𝐹 𝑉 𝐹
𝐹 𝐹 𝑉
𝐹 𝐹 𝐹
𝒑 𝒒 𝒓 ¬𝒓 𝒑∧𝒒 𝒑 ∨ ¬𝒓 (𝒑 ∧ 𝒒) ⇒ (𝒑 ∨ ¬𝒓)
𝑉 𝑉 𝑉 𝐹 𝑉 𝑉 𝑉
𝑉 𝑉 𝐹 𝑉 𝑉 𝑉 𝑉
𝑉 𝐹 𝑉 𝐹 𝐹 𝑉 𝑉
𝑉 𝐹 𝐹 𝑉 𝐹 𝑉 𝑉
𝐹 𝑉 𝑉 𝐹 𝐹 𝐹 𝑉
𝐹 𝑉 𝐹 𝑉 𝐹 𝑉 𝑉
𝐹 𝐹 𝑉 𝐹 𝐹 𝐹 𝑉
𝐹 𝐹 𝐹 𝑉 𝐹 𝑉 𝑉
Definamos algo:
Definición: Si una fórmula es verdadera para todos los posibles valores de verdad de las
proposiciones que la componen, esa fórmula es una tautología.
Si una fórmula es falsa para todos los posibles valores de verdad de las proposiciones que la
componen, esa fórmula es una Contradicción.
Si una fórmula es verdadera para algunos de los posibles valores de verdad de las proposiciones
que la componen y falsa para otros, esa fórmula es una contingencia.
Es decir, que la fórmula: (𝒑 ∧ 𝒒) ⇒ (𝒑 ∨ ¬𝒓) es una tautología, mientras que la primera que
hicimos, (𝒑 ⇒ 𝒒) ∧ (𝒒 ∨ ¬𝒑) es una contingencia.
Definición: Dos fórmulas son EQUIVALENTES si tienen la misma tabla de verdad. En estos
casos, si 𝐴 y 𝐵 son fórmulas equivalentes, lo notamos: 𝐴 ≡ 𝐵
También se puede decir que dos fórmulas 𝐴 y 𝐵 son equivalentes, si 𝐴 ⇔ 𝐵 es una tautología
Por ejemplo, cuando hicimos la tabla de verdad del conector bicondicional, lo hicimos armando
la tabla de (𝒑 ⇒ 𝒒) ∧ (𝒒 ⇒ 𝒑). Eso se debe a que [(𝒑 ⇒ 𝒒) ∧ (𝒒 ⇒ 𝒑)] ≡ (𝒑 ⇔ 𝒒)
Ejercicios:
1) Escribir la tabla de verdad para cada una de las siguientes fórmulas:
a. (𝑝 ⇒ 𝑞) ∨ (¬𝑝)
b. [(𝑝 ⇒ 𝑞) ⇒ 𝑟] ⇒ [𝑝 ⇒ (𝑞 ⇒ 𝑟)]
c. (𝑝 ⇒ 𝑞) ∧ 𝑝
d. (𝑝 ∨ (¬𝑟)) ⇔ 𝑞
e. ((¬𝑝 ∧ 𝑟) ∧ 𝑞) ⇔ (𝑞 ∨ ¬𝑟)
f. (𝑝 ⇒ 𝑞) ∨ (¬𝑞 ⇒ ¬𝑝 )
g. [(𝑝 ⇒ 𝑞) ∧ (𝑝 ∨ 𝑞)] ⇒ 𝑞
h. (𝑝 ⇒ 𝑞) ⇔ (¬𝑞 ⇒ ¬𝑝 )
3) Para cada par de fórmulas decidir si son equivalentes realizando sus correspondientes
tablas de verdad:
a. 𝐴: ¬(𝑝 ⇒ 𝑞) ∨ (𝑟 ∧ ¬𝑟) 𝐵: 𝑝 ∧ ¬𝑞
b. 𝐴: (𝑝 ∨ ¬𝑞) ∧ (¬𝑝) 𝐵: ¬(𝑝 ∨ 𝑞)
c. 𝐴: (¬𝑝 ∨ 𝑞) ⇒ (𝑝 ∨ 𝑞) 𝐵: (¬𝑝 ⇒ ¬𝑞) ∨ 𝑞
d. 𝐴: (𝑝 ∧ 𝑞) ⇒ 𝑟 𝐵: (𝑝 ⇒ 𝑟) ∨ (𝑞 ⇒ 𝑟)
e. 𝐴: ¬(𝑝 ∧ 𝑞) 𝐵: ¬𝑝 ∨ ¬𝑞
Ahora vamos a adentrarnos en otras maneras de probar que dos fórmulas son equivalentes.
Vamos a pensarlas desde las siguientes propiedades.
NOTA: No vamos a demostrar estas propiedades, pero si alguien quisiera, puede hacer las
tablas de verdad para confirmarlo.
Propiedades:
Augustus De Morgan
La historia de Augustus de Morgan se puede resumir universidad debía ser neutral respecto a las creencias
en la palabra coherencia. A lo largo de su carrera, religiosas. Por lo cual, cuando intentó ser profesor en
renunció al éxito oficial con tal de no traicionarse a sí la Universidad de Cambridge y le explicaron que
mismo. No tuvo una vida exactamente debía expresar por escrito su adhesión
fácil. Quedó ciego de un ojo a los pocos religiosa a la Iglesia de Inglaterra,
meses de nacer y eso le valió la burla de prefirió quedarse sin trabajo. Como
sus compañeros en la infancia y siempre investigador, escribió sobre cálculo,
tuvo cierto complejo por causa de su astronomía, filosofía del método
defecto físico. Pero no era un hombre matemático, historia de las
amargado. No fue el mejor estudiante, a matemáticas, teoría de la probabilidad y
pesar de su enorme capacidad. La razón fue capaz de unir para siempre la lógica
es que no se adaptó de aquella época, que y la matemática inspirando a otros
se centraba en la preparación para los autores como George Boole. Aunque
exámenes que establecían un ranking de no fue el más claro o el más maduro, si
alumnos. La competencia era feroz. Pero se percató de que el álgebra podía ser
a Augustus le gustaba aprender, mucho más que concebido como un sistema de símbolos cuyas leyes
competir. Y en matemáticas, estudiaba de todo. Ello pudieran ser codificadas independientemente. Su
le impidió estudiar lo que quería y donde quería. Lógica seguía la misma pauta: una codificación
Tampoco fue de ayuda que pensara que la independiente basada en símbolos.
¿Para qué sirven, entonces, esas propiedades? ¿Me las tengo que aprender?
Sirven para demostrar que dos expresiones (o fórmulas) son equivalentes, sin necesidad de usar
las tablas de verdad. Veamos un ejemplo:
𝑝 ⇒ (𝑞 ⇒ 𝑟) ≡ 𝑞 ⇒ (𝑝 ⇒ 𝑟)
Nuevamente, vamos a ir paso por paso… Vamos a arrancar de la parte que está a la izquierda y,
a través de las propiedades, vamos a tratar de llegar a lo que está a la derecha.
Algo importante: Recuerden que las propiedades se leen en el sentido que nos sirva, de
izquierda a derecha o de derecha a izquierda.
Para demostrar estas relaciones, lo que hacemos es tomar una de las expresiones (la de la
izquierda o la de la derecha) y, usando las propiedades que enunciamos antes, vamos pasando
de una expresión equivalente a la otra, hasta llegar a lo que estaba del otro lado de la
equivalencia.
Arranquemos.
𝑝 ⇒ (𝑞 ⇒ 𝑟)
Si aplicamos una de las equivalencia de la implicancia ( 𝑝 ⇒ 𝑞 ≡ ¬𝑝 ∨ 𝑞) , nos queda:
𝑝 ⇒ (𝑞 ⇒ 𝑟) ≡ 𝑝 ⇒ (¬𝑞 ∨ 𝑟)
Pero si a esto a lo que llegamos, que sigue teniendo una implicancia, volvemos a aplicarle la
misma equivalencia:
𝑝 ⇒ (¬𝑞 ∨ 𝑟) ≡ ¬𝑝 ∨ (¬𝑞 ∨ 𝑟)
Ahora veo que, a la derecha hay dos disyunciones, por lo que puedo aplicar la propiedad
asociativa:
¬𝑞 ∨ (¬𝑝 ∨ 𝑟) ≡ 𝑞 ⇒ (¬𝑝 ∨ 𝑟)
Y una última vez, dentro del paréntesis:
𝑞 ⇒ (¬𝑝 ∨ 𝑟) ≡ 𝑞 ⇒ (𝑝 ⇒ 𝑟)
¡¡Y llegamos a lo que queríamos!! Si quisiéramos, podríamos hacer la cadena directa:
3
Estos hermosos ejercicios son una maravillosa creación de la prof. Marina Oviedo. ¡¡Gracias Mari por
tu trabajo y aporte!!
Prof. Julieta Matteucci 17
UNPAZ – LGTI (6004)
2024
Estructuras Discretas
a) (𝑟 ∧ 𝑞) ∨ 𝑠 ≡ (𝑟 ∨ 𝑠) ∧ (𝑞 ∨ 𝑠)
b) ¬(𝑎 ∧ 𝑏) ≡ (¬𝑎 ∨ ¬𝑏)
c) (𝑞 ∧ 𝑟) ∨ 𝔽 ≡ (𝑞 ∧ 𝑟)
d) 𝕍 ∧ ¬𝑠 ≡ ¬𝑠
e) (𝑟 ∧ 𝑡) ∧ 𝑞 ≡ (𝑟 ∧ 𝑞) ∧ 𝑡
f) (𝑎 ⇒ 𝑏) ∧ (𝑐 ∨ 𝑏) ≡ [(𝑎 ⇒ 𝑏) ∧ 𝑐] ∨ [(𝑎 ⇒ 𝑏) ∧ 𝑏]
a) (𝑝 ⇒ 𝑞) ∧ (𝑝 ∨ 𝑞) ≡ 𝑞
b) (𝑝 ∧ 𝑞) ⇒ 𝑟 ≡ (𝑝 ⇒ 𝑟) ∨ (𝑞 ⇒ 𝑟)
c) (𝑝 ∧ 𝑞) ⇒ 𝑟 ≡ 𝑝 ⇒ (𝑞 ⇒ 𝑟)
d) (𝑝 ∨ 𝑞) ⇒ 𝑟 ≡ (𝑝 ⇒ 𝑟) ∧ (𝑞 ⇒ 𝑟)
e) ¬[(𝑟 ⟹ 𝑝) ∨ (¬𝑞 ⟹ 𝑟)] ≡ ¬𝑝 ∧ ¬𝑞
f) (𝑟 ⟹ ¬𝑞) ∧ (𝑝 ∨ ¬𝑟) ≡ ¬(𝑟 ∧ (𝑝 ⟹ 𝑞))
g) (𝑟 ⟹ 𝑝) ∨ (¬𝑞 ∧ 𝑟) ≡ (𝑟 ∧ 𝑞) ⟹ 𝑝
h) (𝑟 ⟹ ¬𝑞) ∨ (𝑝 ∨ 𝑟) ≡ 𝑉
i) ¬ (𝑟 ⟹ (𝑞 ∧ (𝑝 ∨ 𝑟))) ≡ 𝑟 ∧ ¬𝑞
j) (𝑟 ⟹ ¬𝑝) ⟹ (𝑞 ∨ ¬𝑟) ≡ (𝑟 ⟹ 𝑝) ∨ 𝑞
k) [(𝑝 ⟹ 𝑞) ⟹ 𝑟] ≡ [(𝑝 ∨ 𝑟) ∧ (¬𝑞 ∨ 𝑟)]
La lógica que estuvimos viendo en esta primera parte, referente a proposiciones es incapaz de
describir la mayoría de las afirmaciones en matemática y en computación. Toma como
elemento básico las proposiciones y las considera como un todo. No nos permite hacer un
estudio de la estructura interna de una oración. En cambio, la lógica de predicados considera la
estructura interna de las oraciones. Toma como elementos básicos los objetos y las relaciones
entre dichos objetos. Es decir,
𝑝: 𝑛 𝑒𝑠 𝑢𝑛 𝑒𝑛𝑡𝑒𝑟𝑜 𝑖𝑚𝑝𝑎𝑟
Una proposición es una afirmación que es verdadera o falsa. La afirmación 𝑝 no es una
proposición, porque el hecho de que 𝑝 sea verdadera o falsa depende del valor de 𝑛. Por
ejemplo, 𝑝 es verdadera si 𝑛 = 103 y falsa si 𝑛 = 8. Como casi todas las afirmaciones en
matemática y computación usan variables, debemos ampliar el sistema de lógica para incluir
estas afirmaciones.
Incluso podríamos armar fórmulas, juntando, con los conectores, distintas proposiciones:
En símbolos:
∃𝒙 ∈ 𝐷 ; 𝑝(𝑥)
El símbolo ∃ se llama cuantificador existencial. En esencia, quiere decir que hay, al menos
un elemento para el cual se verifica una propiedad. Podría verificarse para más de un elemento,
pero eso no nos importa. Cuando aparece el “Existe” solo refiere a la existencia y no a la
cantidad de elementos.
Todos los elementos 𝑥 en el conjunto 𝐷 = {3; 5; 7; 11} verifican que 𝑝(𝑥) es verdadera.
En símbolos:
∀𝒙 ∈ 𝐷 ; 𝑝(𝑥)
El símbolo ∀ se llama cuantificador universal. En esencia, quiere decir que, todos los
elementos verifican una propiedad.
En esta materia no vamos a trabajar con la lógica de predicados, pero es importante entender y
manejar los cuantificadores para poder hablar de demostraciones y poder justificar afirmaciones
y enunciados.
Es fácil ver que sí. Si uno muestra una distribución particular de las fichas
de dominó que cubran todo el tablero, estaríamos respondiendo
afirmativamente y, además justificándolo al mostrar cómo se hace, por
ejemplo:
La pregunta ahora es la misma: ¿Se pueden cubrir las 62 casillas de este nuevo tablero con las
fichas de dominó? Si piensan que la respuesta es SI, denme una distribución de las fichas que lo
logre; pero si piensan que la respuesta es NO, tienen que darme razones suficientes para
convencerme. ¡¡A PENSAR!!
Teníamos este tablero truncado y la pregunta era si se podía cubrir la totalidad de las casillas
con las piezas de ajedrez. Uno puede pensar que el tablero tiene 62 casillas y que cada ficha
cubre 2, por lo que creeríamos que con 31 fichas alcanzaría. Seguro probaron mucho y no lo
consiguieron y dijeron: No, no se puede. Pero eso no es una demostración. Porque podría
pasar que hubiera una única forma de acomodarlas y aun no la hayan encontrado.
Entonces, ¿Cómo se responde? ¿qué es demostrar? Es pensar más allá y pensar con
cuantificadores.
“Existe una combinación de fichas de dominó que cubre las 62 casillas del nuevo tablero”
Como se dijo antes, el “existe” no indica si hay una única combinación o varias. Solo habla de la
existencia.
Si “negamos” esa afirmación, estamos negando la existencia. Por lo tanto, la negación sería:
“Ninguna combinación de fichas de dominó cubre las 62 casillas del nuevo tablero”
“Para todas las combinaciones de fichas de dominó, se verifica que no cubren las 62 casillas
del nuevo tablero”
Y viceversa:
Más allá de este problema puntual, esto significa que, si tenemos que decidir que algo es cierto
o no, dependerá de cómo está enunciado.
• “Todos los profesores y todas las profesoras de la UNPAZ son personas muy agradables”
Si queremos decir que es una afirmación verdadera, tendríamos que conocer a todos y
todas y ver si son agradables. Otra forma, sería apelar a propiedades generales que ya
sepamos que valen. Dado que la afirmación refiere a un ∀, para decir que es verdadero,
tenemos que apelar a cosas que se verifiquen ∀. No podemos decir que, como las profes
de esta materia son muy agradables, todxs lo son. Porque podría haber algún docente
en, por ejemplo, la carrera de derecho, que no lo sea.
Si en cambio, quisiéramos decir que es una afirmación falsa, es decir, queremos negar
el ∀, nos alcanza con el ∃. Es decir, acá, con encontrar a ese o esa profe que no sea tan
agradable, alcanza. Un ejemplo “mata” el para todo. Es lo que se llama un
“contraejemplo”.
• “Por lo menos un egresado o una egresada de UNPAZ está trabajando en Suiza desde
hace 15 años”
Acá pasa algo parecido (pero al revés). La afirmación está planteada con un ∃. Por lo
tanto, para demostrar que es verdadera, tendríamos que encontrar a, por lo menos, un
egresado de UNPAZ que, haya encontrado trabajo en Suiza y esté trabajando allá desde
hace 15 años. Si encontramos a este NN, le preguntamos cómo lo logró y aprovechamos
demostramos el ∃.
Sin embargo, si no es verdadera, tenemos que apelar a un ∀. Es decir, preguntarles a
todos los egresados y todas las egresadas de UNPAZ dónde trabajan y desde hace cuánto
tiempo o, apelar a propiedades generales que no dependan de casos puntuales. Por
ejemplo, podríamos decir que los primeros egresados y egresadas de la universidad son
del 2016, por lo que, como no pasaron 15 años desde ese momento, no hay forma que
haya alguno o alguna trabajando en Suiza desde hace ese tiempo.
Volviendo al problema del tablero, decir que, si bien el tablero tiene 62 casillas, las dos casillas
que se sacaron son del mismo color oscuro, lo que hace que queden 32 casillas claras, y solo 30
oscuras. Además, cada ficha de dominó cubre SIEMPRE una de cada color, por lo que siempre
van a sobrar dos casilleros claras que no se podrán cubrir. Eso es demostrar. Dar razones que
van más allá del ejemplo concreto. Pensar en cuantificadores.
UNIDAD: Conjuntos
La tienda parecía estar repleta de toda clase de curiosidades...
pero lo más raro de todo es que cuando intentaba examinar
detenidamente lo que había en algún estante para ver de qué
se trataba, resultaba que estaba siempre vacío.
10.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000
.000.000.000.000.000.000.000
En su libro Matemáticas e imaginación, Kasner recordaba que la conversación con su sobrino continuó así: «Al mismo
tiempo que sugería "gúgol", me dio un nombre para un número todavía más largo: "gúgolplex"». Un gúgolplex es
mucho más largo que un gúgol, pero sigue siendo finito, como se apresuró a señalar el inventor del nombre. Primero
se sugirió que un gúgolplex debía de ser un 1 seguido de ceros hasta que te canses de escribir”.
El tío sentía, con toda razón, que entonces el gúgolplex sería un número algo arbitrario y subjetivo, de modo que
sugirió que el gúgolplex se redefiniera como 10𝑔ú𝑔𝑜𝑙 . Es decir, un 1 seguido de un gúgol de ceros, que son muchos
más ceros de los que caben en un trozo de papel del tamaño del universo observable, aunque se use el tipo de letra
más diminuto imaginable. Estos términos (gúgol y gúgolplex) son relativamente conocidos hoy en día, incluso entre
miembros del público en general, el término “googol” (gúgol) fue adoptado por Larry Page y Sergey Brin como nombre
de su motor de búsqueda. Sin embargo, prefirieron la versión vulgar y errónea del
nombre, de modo que la empresa se llama Google, y no Googol (gúgol). El
nombre indica que el motor de búsqueda proporciona acceso a enormes
cantidades de información. El cuartel general de Google, cómo no, se llama
Googleplex.4
Según la página de Google, el nombre, que refiere a la expresión matemática del número 1
seguido de todos esos ceros, reflejaba con exactitud el objetivo de Larry y Sergey: organizar la
información del mundo y hacerla útil y accesible de forma universal.
4
Singh, S. (2013). Los Simpson y las matemáticas. Barcelona: Editorial Ariel.
*Imagen de la portada, extraída de: Lavado, J. S. (1997). Todo Mafalda. Buenos Aires: Ediciones de la
Flor
Prof. Julieta Matteucci 25
UNPAZ – LGTI (6004)
2024
Estructuras Discretas
Entonces… ¡Se trata de poder organizar toda la información del mundo, y yo sin poder organizar
mi biblioteca!
Definamos:
Entonces, un conjunto, es solo la colección de los objetos (a los que llamamos elementos). Algo
importante es eso de que no importa el orden de los elementos (Mi biblioteca agradece esto).
Aunque hay algunos conjuntos que tienen la particularidad de ser ordenados, pero eso es un
extra, la idea de conjunto no presupone orden.
Cuando los conjuntos tienen una cantidad finita de elementos, a veces, se pueden definir
indicando uno por uno los elementos que lo componen. Esto depende, por supuesto, de la
cantidad de elementos que tenga, porque si tengo un gúgol de libros (casi casi), por más que sea
finito, no es algo posible.
Cuando sí se puede, decimos que podemos escribir al conjunto por extensión, que no es otra
cosa que enumerar todos los elementos. Ya que hablamos de libros, podría definir el conjunto:
A= {“Harry Potter y la piedra filosofal” , “Harry Potter y la cámara secreta” , “Harry Potter y
el prisionero de Azkaban” , “Harry Potter y el cáliz de fuego” , “Harry Potter y la Orden del
Fénix” , “Harry Potter y el misterio del príncipe” , “Harry Potter y las Reliquias de la Muerte”}
Cuando definimos un conjunto por extensión, vamos haciendo una lista de los elementos, entre
llaves y separados con comas. Otros ejemplos de conjuntos por extensión:
B={-1, 1}
D={a,e,i,o,u}
En algunos casos, es posible hacer la definición por extensión, pero en otras no. En esos casos,
necesitamos dar algo que defina al conjunto. Para esto, necesitamos un poco de notación
primero.
Con todo esto podemos definir por comprensión (es decir, dando algo que nos permita
comprender cómo se forma) al conjunto. Veamos los conjuntos anteriores, definidos por
comprensión:
𝐵 = {𝑥 ∈ ℝ / 𝑥 2 − 1 = 0}
Es importante que la definición no incluya elementos que no quisiéramos incluir y que incluya a
todos los que sí queremos incluir. Por eso tiene que ser los más específica posible. En el caso
del ejemplo del conjunto 𝐴, hay que aclarar las dos cosas, que sea de Harry Potter y que sea
escrito por J.K. Rowling ya que, si faltara alguna de las dos podrían entrar otros libros escritos
por la misma autora (y que no sean de Harry Potter) o que sean de Harry Potter pero que no los
hubiese escrito ella (por ejemplo, Harry Potter y el legado maldito), los que no formaban parte
del conjunto inicial. Tampoco se podría definir como “Películas de Harry Potter”, porque el
último libro se adaptó en dos películas.
Mientras se cumpla la condición de que describa exactamente a los elementos que queremos,
podría haber distintas formas de definirlos, por ejemplo, el conjunto B, podría definirse también
como:
𝐵 = {𝑥 ∈ ℝ / 𝑥 4 − 1 = 0}
𝐵 = {𝑥 ∈ ℝ / |𝑥| = 1}
𝐵 = {𝑥 ∈ ℤ / 𝑥 2 − 1 = 0}
−𝑏 ± √𝑏 2 − 4𝑎𝑐
𝐵 = {𝑥 ∈ ℤ / 𝑥 = , 𝑐𝑜𝑛 𝑎 = 1, 𝑏 = 0, 𝑐 = −1}
2𝑎
Dicho de otra forma, A es el conjunto de los números pares. Es bueno que nos vayamos
acostumbrando a este tipo de notación.
Arranquemos con unos pequeños ejercicios para entrar en calor. No se los salteen. Aunque
algunos les parezcan poca cosa o demasiado simples. No se olviden que, sobre las cosas más
simples se van construyendo los otros conceptos. Para algo están acá. Aprovéchenlos. Si no
conocen alguna de las referencias, ¡¡Googleen, en algún lugar de ese gúgol de información, está
lo que necesitan!!
Ejercicios:
1) Definir los siguientes conjuntos, por extensión:
a. El conjunto formado por los números impares no negativos y menores que
diez.
b. El conjunto formado por los personajes principales de Los Simpson.
c. El conjunto formado por los siete ríos más largos del mundo.
d. El conjunto formado por los enteros no negativos menores que cinco.
e. El conjunto de los números primos entre 4 y 22.
2) Definir los siguientes conjuntos, por comprensión. En los casos en los que sea posible,
dar dos definiciones diferentes de los conjuntos:
a. 𝐴 = {−5, −4, −3, −2, −1,0,1,2,3,4,5}
b. 𝐵 = {𝐼𝑟𝑜𝑛 𝑚𝑎𝑛, 𝐶𝑎𝑝𝑖𝑡á𝑛 𝐴𝑚é𝑟𝑖𝑐𝑎, 𝑉𝑖𝑢𝑑𝑎 𝑛𝑒𝑔𝑟𝑎, 𝑂𝑗𝑜 𝑑𝑒 ℎ𝑎𝑙𝑐ó𝑛, 𝑇ℎ𝑜𝑟}
1 3 5
c. 𝐶 = { , 1, , 2 , , 3}
2 2 2
d. 𝐷 = {1,3,5,7,9,11, … } (Los puntos suspensivos indican que el conjunto es
infinito y que sigue con la misma tendencia.
e. 𝐸 = {"𝐿𝑎 ℎ𝑖𝑠𝑡𝑜𝑟𝑖𝑎 𝑜𝑓𝑖𝑐𝑖𝑎𝑙", "𝐸𝑙 𝑠𝑒𝑐𝑟𝑒𝑡𝑜 𝑑𝑒 𝑠𝑢𝑠 𝑜𝑗𝑜𝑠"}
f. 𝐹 = {“𝐻𝑒𝑛𝑟𝑖 𝐶𝑎𝑟𝑡𝑎𝑛”, “𝐶𝑙𝑎𝑢𝑑𝑒 𝐶ℎ𝑒𝑣𝑎𝑙𝑙𝑒𝑦” , ”𝐽𝑒𝑎𝑛 𝐶𝑜𝑢𝑙𝑜𝑚𝑏”,
“𝐽𝑒𝑎𝑛 𝐷𝑒𝑙𝑠𝑎𝑟𝑡𝑒”, “𝐽𝑒𝑎𝑛 𝐷𝑖𝑒𝑢𝑑𝑜𝑛𝑛é”, “𝐶ℎ𝑎𝑟𝑙𝑒𝑠 𝐸ℎ𝑟𝑒𝑠𝑚𝑎𝑛𝑛”,
“𝑅𝑒𝑛é 𝑑𝑒 𝑃𝑜𝑠𝑠𝑒𝑙”, "𝑆𝑧𝑜𝑙𝑒𝑚 𝑀𝑎𝑛𝑑𝑒𝑙𝑏𝑟𝑜𝑗𝑡” , “𝐴𝑛𝑑𝑟é 𝑊𝑒𝑖𝑙”}.
3) Esta tarea tiene varias partes:
a. Elijan y ármense dos conjuntos: Uno matemático (es decir con números) y otro
coloquial. Y escriban su definición por comprensión. Luego, vayan al foro de
esta semana y publiquen sus dos conjuntos (¡OJO! Solo publiquen la definición
por comprensión de los dos conjuntos, nada más). Para no complicarse con la
escritura matemática, pueden sacarles foto a sus definiciones y subir la foto.
b. Busquen la publicación de alguno de sus compañeros o de alguna de sus
compañeras y escriban el conjunto por extensión de la definición que hayan
publicado.
c. Corrijan las respuestas que hayan recibido a sus publicaciones (las de las
definiciones que publicaron) y vean si definieron bien el conjunto que querían
o si quienes interpretaron sus definiciones incluyeron algún elemento extra o le
faltó alguno. Si hace falta, ¿Cómo se mejoraría la definición?
Prof. Julieta Matteucci 28
UNPAZ – LGTI (6004)
2024
Estructuras Discretas
𝐵 = {𝑥 ∈ ℝ / 𝑥 2 − 1 = 0}
𝐵 = {𝑥 ∈ ℤ / 𝑥 2 − 1 = 0}
En este ejemplo, que venía de definir, por comprensión, un conjunto que había sido dado por
extensión, sin más información; ambas definiciones aportan el mismo conjunto. Sin embargo,
si fuéramos a trabajar con estos conjuntos y vincularlos con otros conjuntos, ahí la cosa cambia.
Necesitamos asegurarnos de que están en el mismo universal de los otros conjuntos. Pensemos
en un ejemplo coloquial:
¿A qué universo creen que pertenece? Piénselo un rato. Den varios universales posibles. Antes
de seguir con la lectura.
Prof. Julieta Matteucci 29
UNPAZ – LGTI (6004)
2024
Estructuras Discretas
Supongamos que, ahora, quiero ver quiénes de ese conjunto A verifican, también una serie de
condiciones. Elijan uno de los Universales que hayan pensado y respondan en función de ese
universal: ¿Cuáles de los elementos del conjunto 𝐴, verifican…
Si el universal es: “Nombre de mascotas” y el conjunto A representa los nombres que una
persona le puso a sus mascotas, las respuestas a las primeras dos preguntas serán 0 y la última,
dependerá si las mascotas se llaman así o tienen un nombre más completo.
Por otro lado, si el universal fuera: “Diminutivos de los nombres” y el conjunto A representa a
los diminutivos de los nombres de mis vecinos y vecinas, la respuesta a la última pregunta será
4 y para responder a las otras 2, deberían conocer a mis vecinos y vecinas. Les cuento que son:
{Agustina, Fernando, Marcela, Francisco} por lo que son, 2 hombres y 2 mujeres.
Ya dijimos que usábamos el símbolo ∈ para indicar pertenencia. Pero no se dijo mucho más.
Podríamos preguntarnos si un cierto objeto, pertenece en un conjunto.
Si el conjunto está dado por extensión, hay que revisar la lista de los elementos, y ver si lo
encontramos o no. Si, en cambio, el conjunto fue definido por comprensión, debemos verificar
si el objeto cumple o no con la definición que se haya dado.
Como el conjunto está dado por extensión, podemos simplemente chequear y vemos que el
único que pertenece es el 3, mientras que el 5 y el 7 no pertenecen. Eso lo notamos:
3∈𝐴
5∉𝐴
7∉𝐴
3∈𝐴
5∉𝐴
7∉𝐴
Si un conjunto A está formado exclusivamente por elementos que también están presentes en
otro conjunto B, y ambos pertenecen a un mismo universal, decimos que A es un subconjunto
de B. Por ejemplo:
𝐵 = {𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓, 𝑔, ℎ, 𝑖, 𝑗, 𝑘, 𝑙, 𝑚, 𝑛, ñ, 𝑜, 𝑝, 𝑞, 𝑟, 𝑠, 𝑡, 𝑢, 𝑣, 𝑤, 𝑥, 𝑦, 𝑧}
𝐴 = {𝑎, 𝑒, 𝑖, 𝑜, 𝑢}
A es un subconjunto de B.
IMPORTANTE:
Cuando decimos que un elemento pertenece a un conjunto usamos el símbolo ∈. Sin embargo,
si hablamos de que un conjunto está dentro de otro (es un subconjunto) usamos el símbolo ⊂
En el ejemplo:
𝐵 = {𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓, 𝑔, ℎ, 𝑖, 𝑗, 𝑘, 𝑙, 𝑚, 𝑛, ñ, 𝑜, 𝑝, 𝑞, 𝑟, 𝑠, 𝑡, 𝑢, 𝑣, 𝑤, 𝑥, 𝑦, 𝑧}
𝐴 = {𝑎, 𝑒, 𝑖, 𝑜, 𝑢}
𝑨⊂𝑩
𝒂∈𝑩
Ejemplos:
∑ = {1,2,3} ; ∑ = { 𝑎, 𝑏, 𝑐, 𝑑 } ; ∑ = {0,1} ; 𝑉 = {☻, ♣, , ♫}
Con los símbolos del alfabeto podemos formar cadenas de símbolos o palabras o hileras; éstas
contienen un número finito de símbolos del alfabeto. La palabra vacía o cadena vacía, denotada
por 𝜆 (se lee lambda), es la cadena que no contiene símbolos.
Ejemplo:
Sea el alfabeto 𝑉 = {0,1}
Algunas de las palabras que se pueden formar son: 𝑤1 = 001; 𝑤2 = 100; 𝑤3 = 10101010
El conjunto de todas las palabras que se pueden formar con el alfabeto 𝑉, es un nuevo conjunto
(que puede tener infinitos elementos) y que se nota agregándole un * al alfabeto (y lo leemos
como estrella). En nuestro caso:
Existen muchas interpretaciones posibles sobre los elementos de 𝑉 ∗ , según lo que sea o
represente 𝑉 . Si 𝑉 es un conjunto de “palabras”
entonces 𝑉 ∗ será la colección de todas las Alfabetos y lenguajes
“oraciones” posibles formadas con las palabras de 𝑉, Si al alfabeto le adicionamos un conjunto de
tengan o no sentido o una estructura evidente. las reglas que nos permitan formar las
palabras del lenguaje (a este conjunto de
Ejemplo reglas se lo llama la gramática formal (o
V = {Ana, Luis, mariposa, come, reír, rápido, sintaxis)) y la palabra que conseguimos
lento,} armándola de acuerdo con una gramática
dada se llama una fórmula bien formada
Algunas palabras de V:
(palabra, fórmula bien definida o simplemente
w1=Ana come; fórmula) del lenguaje. Dado un cierto
alfabeto, el conjunto de todas sus fórmulas
w2=reír rápido Luis; w3=Luis mariposa Ana
bien formadas nos da el lenguaje. A
V*= {λ, Ana Luis mariposa, Ana come rápido, Luis diferencia de lo que ocurre con el alfabeto
reír , Luis Juan , …} (que debe ser un conjunto finito) y con cada
fórmula bien formada (que debe tener una
Sigamos avanzando con los temas. Ahora hablemos longitud también finita), un lenguaje formal
del tamaño de los conjuntos. puede estar compuesto por un número infinito
de fórmulas bien formadas.
Cuando nos referimos al tamaño que tienen los
conjuntos, hacemos referencia a la cantidad de El alfabeto utilizado por muchos de los
llamados lenguajes de programación (como
elementos que tiene ese conjunto. El nombre que
Pascal o C) es el conjunto de caracteres
usamos para indicar ese valor es cardinalidad. ASCII (o un subconjunto de él) que incluye,
por lo general, las letras mayúsculas y
La cardinalidad de un conjunto A usualmente se minúsculas, los símbolos de puntuación y los
denota | 𝐴 |, con las barras; esta es la misma notación símbolos matemáticos disponibles en los
que la del módulo o valor absoluto y el significado teclados estándares.
depende del contexto 5 . Alternativamente, la
cardinalidad de 𝐴 se puede denotar por 𝑛(𝐴), 𝑐𝑎𝑟𝑑(𝐴), o #𝐴 (acá leemos cardinal de A, no
Hashtag).
Si un conjunto 𝐴 tiene una cantidad finita de elementos, diremos que es un conjunto finito; si
el conjunto tiene una cantidad no finita de elementos diremos que es un conjunto infinito y que
su cardinal es infinito6.
Ejemplos
5
Aunque el símbolo y la notación sea lo mismo, tienen significados diferentes, un conjunto no tiene valor
absoluto, de la misma forma que un número o variable, no tiene cantidad de elementos.
6
A fines de este apunte (y de esta materia) no vamos a centrarnos en los distintos tamaños que tienen
los infinitos, aunque es un tema muuuuuy interesante.
Prof. Julieta Matteucci 32
UNPAZ – LGTI (6004)
2024
Estructuras Discretas
En el caso en que estemos frente a una palabra (o cadena) formada a partir de un alfabeto, la
longitud de esa cadena será la cantidad de símbolos del alfabeto que tiene la cadena o palabra,
contadas tantas veces como aparezcan. Lo notamos como 𝑙𝑜𝑛𝑔(𝑤)
Ejemplo:
Ahora que ya tenemos la parte inicial, podemos empezar a operar con los conjuntos. Pero antes,
veamos una forma de representarlos que nos va a ayudar a entender las operaciones.
Una representación gráfica para los conjuntos son los diagramas de Venn. El conjunto
universal se representa por el interior de un rectángulo y todos los demás conjuntos se
representan por regiones cerradas incluidos en el mismo. Esta representación sirve para ver
visualmente relaciones entre conjuntos y sus elementos.
Ejemplos. Supongamos que el universal es el conjunto de todas las letras del abecedario y
tenemos un conjunto 𝐴 que representa a las vocales, 𝐵 el conjunto de las letras que están en la
última fila de un teclado qwerty (justo arriba de la barra espaciadora). En diagrama de Venn
queda:
U
A
t p u
k r
j a
i
B w d
x f ee
z o
m
v q ñ
h
c n l g
b s y
Algunas consideraciones.
✓ En este dibujo, las letras están en “globitos” pero no significa que sean conjuntos, solo
es una forma de representarlas visualmente. Los conjuntos acá son el 𝐴, el 𝐵 y el
universal.
Ahora sí, continuemos con las operaciones. En el ejemplo que acabamos de ver los conjuntos
no tienen elementos en común, pero a veces eso sí ocurre. Cuando hablamos de los elementos
que dos o más conjuntos tienen en común, hablamos de intersección y el símbolo que usamos
para notarla es: ∩
Formalmente diremos:
𝐴 ∩ 𝐵 = {𝑥 / 𝑥 ∈ 𝐴 ∧ 𝑥 ∈ 𝐵}
El símbolo ∧ significa “y” y quiere decir que se deben cumplir las dos condiciones7. En esencia,
esta definición quiere decir que la intersección es el conjunto formado por los elementos que
están al mismo tiempo en 𝐴 y en 𝐵.
𝐴 𝐵
1
12
2
3 6 8
4 9
5
𝐶 7
Antes de ponerme a responder a las consignas, noto que todos los elementos de 𝐵 también
están en 𝐶, entonces una mejor representación sería:
7
En la unidad de Lógica se trabaja bastante con este símbolo y sus propiedades.
Prof. Julieta Matteucci 34
UNPAZ – LGTI (6004)
2024
Estructuras Discretas
𝐴
1
12 2
3 6 8
4 𝐵
9
𝐶 5
7
Ahora sí, vamos a ponernos a responder lo pedido. En el primer ítem, tenemos que ver qué
tienen en común 𝐴 y 𝐵. Vemos que solo tienen en común al 6, entonces:
a) 𝐴 ∩ 𝐵 = {6}
En el segundo ítem, tenemos que ver qué tienen en común 𝐴 y 𝐶. Vemos que tienen en común
al 4 y al 6, entonces:
b) 𝐴 ∩ 𝐶 = {4,6}
En el tercer ítem, tenemos que ver qué tienen en común los tres conjuntos. Vemos que tienen
en común solo al 6, entonces:
c) 𝐴 ∩ 𝐵 ∩ 𝐶 = {6}
Y ahora, hablemos del último ítem, tenemos que ver qué tienen en común 𝐵 y 𝐶. Vemos que
tienen en común a todos los elementos de 𝐵, por lo que podríamos dar la respuesta de dos
maneras:
𝐵 ∩ 𝐶 = {6,8,9}
O diciendo directamente:
𝐵∩𝐶 =𝐵
Otra de las operaciones con las que vamos a trabajar es la unión. En este caso, unir, es
exactamente eso: juntar todos los elementos en un nuevo conjunto que llamamos unión y que
notamos con ∪. Formalmente diremos:
𝐴 ∪ 𝐵 = {𝑥 / 𝑥 ∈ 𝐴 ∨ 𝑥 ∈ 𝐵}
El símbolo ∨ significa “o” y quiere decir que se deben cumplir una de las dos condiciones8. En
esencia, esta definición quiere decir que la unión es el conjunto formado por los elementos que
están en, al menos, uno de los conjuntos (en 𝐴 o en 𝐵)
8
En la unidad de Lógica se trabaja bastante con este símbolo y sus propiedades.
Prof. Julieta Matteucci 35
UNPAZ – LGTI (6004)
2024
Estructuras Discretas
𝐴
1
12
2
3 6 8
4 𝐵
9
𝐶 5
7
En el primer ítem, tenemos que ver qué forman juntos 𝐴 y 𝐵. Vemos que queda:
a) 𝐴 ∪ 𝐵 = {1,2,3,4,6,12,8,9}
En el segundo ítem, tenemos que ver qué forman juntos 𝐴 y 𝐶. Vemos que queda:
b) 𝐴 ∪ 𝐶 = {1,2,3,4,6,12,5,7,8,9}
En el tercer ítem, tenemos que ver qué forman juntos los tres conjuntos. Vemos que queda
igual que en el ítem anterior.
c) 𝐴 ∪ 𝐵 ∪ 𝐶 = {1,2,3,4,6,12,5,7,8,9}
Y ahora, hablemos del último ítem, tenemos que ver qué forman juntos 𝐵 y 𝐶. Vemos que
tienen en común a todos los elementos de 𝐵 , por lo que podríamos, nuevamente, dar la
respuesta de dos maneras:
Enunciando, por extensión todos los elementos:
𝐵 ∪ 𝐶 = {4,5,6,7,8,9}
O diciendo directamente:
𝐵∪𝐶 =𝐶
Sigamos con las operaciones, ahora que vimos qué forman juntos y qué tienen en común, vamos
a ver qué los diferencia. Para eso, tenemos la operación diferencia de conjuntos. Es ver
cuáles de los elementos del primer conjunto no están en el segundo. Lo notamos con el guion
(o signo “menos”): −
Formalmente diremos:
𝑨 𝑩
𝐴 − 𝐵 = {𝑥 / 𝑥 ∈ 𝐴 ∧ 𝑥 ∉ 𝐵}
𝐴 − 𝐵 = {𝑥 / 𝑥 ∈ 𝐴 ∧ 𝑥 ∉ 𝐵}
Miremos lo que está dentro de las llaves y leámoslo con un poco de cariño. Si leemos más o
menos textual, diríamos (eso que se dijo antes):
“Es el conjunto formado por los elementos que están en 𝐴 y, al mismo tiempo, no están en 𝑩.”
Esas frases… ¿No las habíamos usado antes? ¡Si! La de “al mismo tiempo” la usamos para
intersección y la de “no están en 𝑩” es la del complemento. Esto nos permite dar una nueva
definición para la diferencia que dependa, exclusivamente, de las operaciones anteriores:
𝐴 − 𝐵 = 𝐴 ∩ 𝐵𝑐
En varios de los ejercicios que haremos después, cuando dejemos de usar tanto los diagramas
de Venn y trabajemos con propiedades, esta es la definición de diferencia que vamos a usar.
Nuevamente, nos vamos a aprovechar que ya teníamos hecho el diagrama de Venn de estos
conjuntos:
𝐴
1
12
2
3 6 8
4 𝐵
9
𝐶 5
7
En el segundo ítem, tenemos que ver cuál es la diferencia entre 𝐵 y 𝐴. Observemos que el único
elemento que comparten sigue siendo el 6, pero ahora se lo tenemos que sacar a 𝐵 Por lo que
queda:
𝐵 − 𝐴 = {8,9}
𝐶 5 𝐴 − 𝐶 = {1,2,3,12}
7
Y ahora, hablemos del último ítem, tenemos que cuál es la diferencia entre 𝐵 y 𝐶.
Nuevamente, hacemos hincapié en la inclusión. Vemos que tienen en común a todos los
elementos de 𝐵, nos queda:
𝐵−𝐶 = ∅
Igualdad de conjuntos: Dos conjuntos A y B son iguales si cada uno contiene al otro:
𝐴 = 𝐵 si (𝐴 ⊂ 𝐵) ∧ (𝐵 ⊂ 𝐴)
El último par de operaciones que vamos a ver son el complemento y el conjunto partes.
Estas operaciones se realizan sobre un solo conjunto y no sobre más de uno como las anteriores.
Por ejemplo, si tenemos que el universal es el conjunto de todas las letras del abecedario y un
conjunto 𝐴 que representa a las vocales, entonces, 𝐴𝑐 = {𝑥 / 𝑥 𝑒𝑠 𝑐𝑜𝑛𝑠𝑜𝑛𝑎𝑛𝑡𝑒}
Por su lado, hacer el conjunto partes de otro conjunto es hacer un nuevo conjunto con todos
los posibles subconjuntos del conjunto original. Lo notamos como 𝒫(𝐴)
Por ejemplo, si 𝐴 = {𝑎, 𝑏, 𝑐}, entonces 𝒫(𝐴) = {∅, {𝑎}, {𝑏}, {𝑐}, {𝑎, 𝑏}, {𝑎, 𝑐}, {𝑏, 𝑐}, {𝑎, 𝑏, 𝑐}}
Este es un buen momento para detenerse y hacer un poco de práctica. Así que acá va una
pequeña lista de ejercicios para que practiquen un poco:
Ejercicios:
1) Sean los conjuntos:
a) Indicar, justificando en todos los casos, cuáles de las siguientes afirmaciones son
verdaderas y cuáles falsas:
I. 𝐴=𝐵
II. 1∈𝐶
1
III. 2
∈𝐶
IV. |𝐷| = 3
V. |𝐶| = 2
VI. 𝐶⊂𝐷
VII. 𝐶∈𝐷
b) Dar, por extensión los conjuntos 𝒫(𝐴), 𝒫(𝐶) y 𝒫(𝒫(𝐶))
3) Para el siguiente diagrama de Venn, pintar (volverlo a dibujar para cada ítem) el sector
resultante de:
𝑈 a. 𝐴 ∪ (𝐵 ∩ 𝐶)
𝐴 𝐵 b. 𝐴 ∩ (𝐵 ∪ 𝐶)
c. 𝐴𝑐 ∪ (𝐵 − 𝐶)
d. (𝐴 ∪ 𝐵) − (𝐴 ∩ 𝐵)
𝑐
e. ((𝐴 ∪ 𝐵) − (𝐴 ∩ 𝐵))
f. 𝐶 − (𝐵 ∩ 𝐶)
g. (𝐴 ∪ 𝐵 ∪ 𝐶) − (𝐴 − (𝐵 ∪ 𝐶))
𝑐
𝐶 h. (𝐶 − (𝐵 ∪ 𝐴))
i. (𝐴 ∩ 𝐵) ∪ (𝐶 ∩ 𝐵) ∪ (𝐴 ∩ 𝐶)
j. (𝐵 − 𝐶) ∪ (𝐶 − 𝐵)
4) Para cada uno de los siguientes diagramas, dar una operación entre los conjuntos que
corresponda al área sombreada:
a. b.
c. d.
e. f.
g. h.
Volvamos a los contenidos… Ahora dejemos los dibujitos un rato y centrémonos en las
propiedades que tienen estas operaciones.
NOTA: No vamos a demostrar estas propiedades, pero si alguien quisiera, puede hacer los
diagramas de Venn, para verificarlas.
Propiedades:
¿Para qué sirven, entonces, esas propiedades? ¿Me las tengo que aprender? ¿No se
puede probar todo con diagramas de Venn?
Sirven para demostrar que dos expresiones son equivalentes, sin necesidad de usar los
diagramas de Venn. Estos diagramas, aunque útiles y relativamente simples, muchas veces no
permiten demostrar algunas propiedades ya que, si no conocemos cómo están compuestos los
conjuntos, la representación que hagamos (el dibujito) será solo una de las muchas formas en
las que podrían estar vinculados entre sí, y existe la posibilidad de que no estemos demostrando,
realmente, lo que queríamos. Con las propiedades, por otro lado, nos independizamos del
dibujo y las demostraciones son más universales, ya que solo dependen de esas “verdades” que
sabemos que cumplen.
Veamos un ejemplo:
a) 𝐴 ∩ 𝐵 = 𝐴 − 𝐵𝑐
b) 𝐴 ∪ (𝐴𝑐 ∩ 𝐵) = 𝐴 ∪ 𝐵
c) 𝐴 − (𝐴𝑐 ∪ 𝐵) = 𝐴 − 𝐵
Este tipo de demostraciones se pueden realizar de varias maneras:
𝐴 ∩ 𝐵 = 𝐴 − 𝐵𝑐
Una buena forma de empezar acá es, antes de aplicar las propiedades, arrancar reescribiendo
la expresión. Si se acuerdan, no tenemos propiedades de la diferencia, pero teníamos una
segunda definición que la expresaba en términos de las otras operaciones.
Habíamos dicho que: 𝐴 − 𝐵 = 𝐴 ∩ 𝐵𝑐 . Entonces, si miro lo que tengo que probar, voy a
arrancar de la derecha, que es donde tengo la diferencia:
𝐴 − 𝐵𝑐
𝐴 − 𝐵𝑐 = 𝐴 ∩ ((𝐵𝑐 )𝑐 )
Pero teníamos, también la Ley de Involución, que me decía que el complemento del
complemento, me daba el conjunto original:
𝐴 − 𝐵𝑐 = 𝐴 ∩ ((𝐵𝑐 )𝑐 )
𝐴 − 𝐵𝑐 = 𝐴 ∩ 𝐵
Y llegamos a lo que, originalmente, estaba a la izquierda, por lo que termina la demostración.
En este caso, como a la derecha solo hay una unión (y no se puede hacer mucho ahí), vamos a
arrancar de la izquierda y aplicar, por ejemplo, una de las Leyes distributiva:
𝐴 ∪ (𝐴𝑐 ∩ 𝐵) = (𝐴 ∪ 𝐴𝑐 ) ∩ (𝐴 ∪ 𝐵)
Sabemos, por las leyes de complemento, que la unión entre un conjunto y su complemento
nos da el universal:
𝐴 ∪ (𝐴𝑐 ∩ 𝐵) = (𝐴 ∪ 𝐴𝑐 ) ∩ (𝐴 ∪ 𝐵)
𝐴 ∪ (𝐴𝑐 ∩ 𝐵) = 𝑈 ∩ (𝐴 ∪ 𝐵)
Por las Leyes de Identidad sabemos que la intersección entre el Universal y un conjunto nos
da el mismo conjunto:
𝐴 ∪ (𝐴𝑐 ∩ 𝐵) = 𝑈 ∩ (𝐴 ∪ 𝐵)
𝐴 ∪ (𝐴𝑐 ∩ 𝐵) = 𝐴 ∪ 𝐵
Y llegamos a la unión que queríamos llegar, terminando esta demostración.
𝐴 − (𝐴𝑐 ∪ 𝐵) = 𝐴 − 𝐵
Acá vamos a arrancar con las dos expresiones (por separado), aplicándoles a cada una la
definición de diferencia.
A la derecha, mucho más no podemos hacer, así que seguimos operando a la izquierda.
Tenemos unas propiedades que nos “distribuyen” el complemento, son las leyes de De
Morgan. Aplicamos la que corresponde a la unión (Complemento de la unión, equivale a la
intersección de los complementos)
𝐴 − (𝐴𝑐 ∪ 𝐵) = 𝐴 ∩ ((𝐴𝑐 )𝑐 ∩ 𝐵𝑐 )
Al igual que en el primer ejemplo, recordamos que teníamos, también la Ley de Involución,
que me decía que el complemento del complemento me daba el conjunto original:
𝐴 − (𝐴𝑐 ∪ 𝐵) = 𝐴 ∩ ((𝐴𝑐 )𝑐 ∩ 𝐵𝑐 )
𝐴 − (𝐴𝑐 ∪ 𝐵) = 𝐴 ∩ (𝐴 ∩ 𝐵𝑐 )
Ahora observamos que hay dos intersecciones, por lo que podemos aplicar la ley
asociativa:
𝐴 − (𝐴𝑐 ∪ 𝐵) = 𝐴 ∩ (𝐴 ∩ 𝐵𝑐 )
𝐴 − (𝐴𝑐 ∪ 𝐵) = (𝐴 ∩ 𝐴) ∩ 𝐵𝑐
Y, por las Leyes de idempotencia tenemos que la intersección entre un conjunto y él mismo,
nos dan el mismo conjunto
𝐴 − (𝐴𝑐 ∪ 𝐵) = (𝐴 ∩ 𝐴) ∩ 𝐵𝑐
𝐴 − (𝐴𝑐 ∪ 𝐵) = 𝐴 ∩ 𝐵𝑐
¡¡Y listo!!
Ejercicios (nivel 0)
Ejercicios (nivel 1)
Ejercicios (nivel 2)
9
Estos hermosos ejercicios son una joyita salida de la cabeza de la prof. Marina Oviedo. ¡¡Gracias Mari
por tu trabajo y aporte!!
Prof. Julieta Matteucci 44
UNPAZ – LGTI (6004)
2024
Estructuras Discretas
Ejercicios (nivel 3)
𝒰 = {−2, −1,0,1,2,3,4,5,6,7}
𝐴 = {−2,4,7}
𝐵 = {𝑏 ∈ 𝒰: 𝑏 𝑒𝑠 𝑝𝑎𝑟}
𝐶 = {𝑐 ∈ 𝒰: 𝑐 > 0}
1) Realizar las siguientes operaciones, dar los conjuntos por extensión y graficarlos en un
diagrama de Venn (cada uno por separado)
a) 𝐴 ∪ (𝐵 − 𝐶) =
b) 𝐵 − (𝐶 𝑐 ∪ 𝐴) =
c) (𝐴 − 𝐵) ∩ (𝐶 ∪ 𝐴𝑐 )𝑐 =
2) Hallar:
a) |𝐷|, siendo 𝐷 = 𝐴 − 𝐵
b) 𝒫(𝐸), siendo 𝐸 = 𝐵 ∪ 𝐶
c) |𝒫(𝐹)|, siendo 𝐹 = (𝐶 − 𝐵) ∩ 𝐴
UNIDAD: Relaciones
Llamar a la puerta serviría de algo, si tuviéramos
la puerta entre nosotros dos. Por ejemplo, si tú
estuvieras dentro, podrías llamar, y yo podría
abrir para que salieras.
Ahora que ya dominan el trabajo con conjuntos (no se rían tan fuerte que los escucho), vamos
a seguir trabajando con conjuntos y sus elementos.
Supongamos que una persona tiene 5 remeras de colores diferentes y 3 pantalones (también de
colores diferentes. Entonces, tenemos dos conjuntos: el de remeras, y el de pantalones:
Ahora no nos interesa cuántas opciones de vestimenta tiene (lo que sí nos interesa en la unidad
de conteo), sino cuáles son esas combinaciones. Además, importa el orden en el que armamos
el conjunto, la remera va arriba y el pantalón abajo (al menos en este ejemplo, después, Uds.
vístanse como quieran)
Enunciemos algo:
𝐴 × 𝐵 = {(𝑥; 𝑦): 𝑥 ∈ 𝐴 ∧ 𝑦 ∈ 𝐵}
Entonces, si el conjunto de las remeras es: 𝐶 = {𝑐𝑒𝑙𝑒𝑠𝑡𝑒, 𝑣𝑒𝑟𝑑𝑒, 𝑟𝑜𝑗𝑎, 𝑙𝑖𝑙𝑎, 𝑎𝑧𝑢𝑙 } y el de los
pantalones: 𝑃 = {𝑟𝑜𝑗𝑜, 𝑔𝑟𝑖𝑠, 𝑏𝑙𝑎𝑛𝑐𝑜}
Otro ejemplo:
𝐴 × 𝐵 = {(1; 𝑎), (1; 𝑏), (2; 𝑎), (2; 𝑏), (3; 𝑎), (3; 𝑏)}
𝐵 × 𝐴 = {(𝑎; 1), (𝑎; 2), (𝑎; 3), (𝑏; 1), (𝑏; 2), (𝑏; 3)}
𝐵 × 𝐵 = {(𝑎; 𝑎), (𝑎; 𝑏), (𝑏; 𝑎), (𝑏; 𝑏)}
𝐴×∅=∅
∅×𝐴=∅
En general, si partimos de dos conjuntos que no son vacíos, entonces 𝐴 × 𝐵 ≠ 𝐵 × 𝐴.
Lo que es, en el mejor de los casos, un lío bárbaro con todas las flechas. Sin embargo, es
importante que lo que une ambos conjuntos sea una flecha y no una línea simple, ya que indica
sentido y orden.
A veces, sin embargo, no nos interesan todas esas flechas y solo necesitamos algunas, es decir,
que no nos hace falta todo el producto cartesiano, sino un subconjunto. Aprovechemos,
entonces, para dar una nueva definición:
Entonces, por ejemplo, si el conjunto de las remeras es: 𝐶 = {𝑐𝑒𝑙𝑒𝑠𝑡𝑒, 𝑣𝑒𝑟𝑑𝑒, 𝑟𝑜𝑗𝑎, 𝑙𝑖𝑙𝑎, 𝑎𝑧𝑢𝑙 }
y el de los pantalones: 𝑃 = {𝑟𝑜𝑗𝑜, 𝑔𝑟𝑖𝑠, 𝑏𝑙𝑎𝑛𝑐𝑜}
Son Relaciones de 𝐶 en 𝑃:
ℛ1 = {(𝑐𝑒𝑙𝑒𝑠𝑡𝑒; 𝑏𝑙𝑎𝑛𝑐𝑜), (𝑣𝑒𝑟𝑑𝑒; 𝑟𝑜𝑗𝑜), (𝑣𝑒𝑟𝑑𝑒; 𝑏𝑙𝑎𝑛𝑐𝑜), (𝑟𝑜𝑗𝑎; 𝑔𝑟𝑖𝑠), (𝑟𝑜𝑗𝑎; 𝑏𝑙𝑎𝑛𝑐𝑜),
(𝑙𝑖𝑙𝑎; 𝑔𝑟𝑖𝑠), (𝑙𝑖𝑙𝑎; 𝑏𝑙𝑎𝑛𝑐𝑜), (𝑎𝑧𝑢𝑙 ; 𝑟𝑜𝑗𝑜)}
• Son relaciones de 𝐴 en 𝐵:
• Son relaciones de 𝐵 en 𝐴:
ℛ = {(𝑥; 𝑦) ∈ ℤ × ℕ / 𝑥 2 = 𝑦}
En todos estos casos, ¡no olvidar que importa el orden!
En el caso, por ejemplo, de 𝐴 = {1,2,3}, 𝐵 = {𝑎, 𝑏}, habíamos definido varias relaciones de las
que podemos decir: 1ℛ1 𝑎, 𝑏ℛ5 2
Cuando 𝐴 es finito, una relación ℛ en 𝐴 se puede representar por medio de un grafo dirigido.
Los vértices del grafo son los elementos del conjunto A y las flechas se corresponden con los
elementos relacionados (hay una flecha de 𝑥 a 𝑦 si 𝑥ℛ𝑦).
Ejemplos:
ℛ1 = {(1; 1), (1; 2), (1; 3), (2; 3), (3; 2)}
ℛ2 = {(1; 1), (2; 2), (3; 3)}
ℛ3 = ∅
ℛ4 = {(1; 1), (1; 2), (2; 1), (2; 2), (3; 3)}
Estas relaciones las podemos dibujar con grafos dirigidos10.
𝟐
10
Por ahora, lo único que vamos a considerar como Grafo, es este tipo de esquema formado por los
puntitos (a los que llamamos nodos o vértices) y las flechas que indican, cómo se vinculan estos nodos.
Prof. Julieta Matteucci 49
UNPAZ – LGTI (6004)
2024
Estructuras Discretas
Al igual que cuando definimos a los conjuntos, que presentamos algunos conjuntos especiales,
también vamos a darle nombre a algunas relaciones importantes:
ℛ 𝑒𝑠 𝑟𝑒𝑓𝑙𝑒𝑥𝑖𝑣𝑎 ↔ 𝑥ℛ𝑥, ∀𝑥 ∈ 𝐴
Importante: Esto se tiene que verificar Para todos los elementos del conjunto
Se dice que una relación ℛ en 𝐴 es simétrica si cada vez que un (𝑥; 𝑦) ∈ ℛ , entonces el par
(𝑦; 𝑥) ∈ ℛ también.
Importante: Esto se no se tiene que verificar, necesariamente para todos los elementos del
conjunto, pero si hay dos elementos vinculados por ℛ en un sentido deben estar vinculados en
el sentido opuesto.
Se dice que una relación ℛ en 𝐴 es antisimétrica si cada vez que un (𝑥; 𝑦) ∈ ℛ con 𝑥 ≠ 𝑦,
entonces el par (𝑦; 𝑥) ∉ ℛ.
Importante: Esto se no se tiene que verificar, necesariamente para todos los elementos del
conjunto, pero si hay dos elementos distintos vinculados por ℛ en un sentido No deben estar
vinculados en el sentido opuesto.
Se dice que una relación ℛ en 𝐴 es transitiva si cada vez que un (𝑥; 𝑦) ∈ ℛ y un (𝑦; 𝑧) ∈ ℛ ,
entonces el par (𝑥; 𝑧) ∈ ℛ también.
Importante: Esto se no se tiene que verificar, necesariamente para todos los elementos del
conjunto, pero si hay dos elementos vinculados por ℛ en un sentido y el segundo, está vinculado
con un tercero, entonces el primer debe estar vinculado con el tercero.
Finalmente, tampoco es transitiva, porque, por ejemplo, 2ℛ1 3, 3ℛ1 2 pero no ocurre que
2ℛ1 3 y 2ℛ1 2.
Finalmente, también es transitiva, porque, por ejemplo, 1ℛ2 1, 1ℛ2 1 y 1ℛ2 1 (lo mismo ocurre
con los otros elementos).
Veamos ℛ3 = ∅:
Observamos que sí es reflexiva, porque cada uno de los 3 elementos está relacionado consigo
mismo. Es decir, los pares (1; 1), (2; 2), (3; 3) ∈ ℛ4 .
ℛ2 es de orden y de equivalencia.
ℛ3 no es de orden ni de equivalencia porque no es reflexiva.
Es un buen momento para detenernos a practicar todo lo visto. Por eso, acá viene una linda
(muy linda) tanda de ejercicios:
Ejercicios
1) Sean 𝐴 = {𝑎, 𝑏, 𝑐, 𝑑}, 𝐵 = {1,2,3,4}
a. Hallar 𝐴 × 𝐵
b. Hallar 𝐵 × 𝐴
c. Hallar 𝐴 × 𝐴
d. Hallar 𝐵 × 𝐵
2) Sean los conjuntos 𝐴 = {−2, −1}, 𝐵 = {𝑥 ∈ ℕ; 1 ≤ 𝑥 ≤ 3} y 𝐶 = {𝑎, 𝑏}. Hallar:
a. 𝐴 × 𝐶
b. 𝐶 × 𝐴
c. 𝐴 × 𝐵
d. (𝐴 × 𝐵) × 𝐶
e. (𝐴 × 𝐴) × 𝐴
3) Sea 𝐴 = {𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓, 𝑔, ℎ}. Para cada uno de los siguientes gráficos de una relación
sobre A, determinar si es reflexiva, simétrica, antisimétrica o transitiva.
a) b)
𝒈
𝒃 𝒈
𝒃
𝒉 𝒂
𝒂 𝒄
𝒉
𝒄
𝒅 𝒆
𝒅 𝒆
𝒇
𝒇
c) d)
𝒃 𝒈 𝒃
𝒂 𝒂
𝒄 𝒈
𝒉
𝒄
𝒅 𝒅
𝒇 𝒆 𝒉
𝒆
𝒇
b. 𝐴 = {1,2,3,4,5,6}, ℛ = {(1; 1), (2; 2), (3; 3), (4; 4), (5; 5)}
c. 𝐴 = {1,2,3,4,5}, ℛ = {(1; 1), (2; 2), (3; 3), (4; 4), (5; 5), (2; 3), (2; 4), (3; 5), (2; 5)}
d. 𝐴 = {3,4,5,6,7}, ℛ = {(3; 4), (4; 6), (3; 6)}
Un tipo de relaciones muy particulares (y muy útiles son las funciones) y aunque sea posible que
sepan perfectamente lo que es, de todas maneras, vamos a definirlas:
Observemos que hay algunas palabras que son clave en esta definición. Estas palabras son:
todos único
Veamos lo que significan con diagramas de Venn.
𝑨 𝑩
𝓡𝟐
𝑨 𝑩
La relación ℛ2 soluciona el problema del todos. El elemento que antes no tenía ningún vínculo
(a través de ℛ1 ) con algún elemento de 𝐴 ahora está vinculado con, no uno, sino dos elementos
del 2do conjunto. Eso hace que, la relación ℛ2 no sea una función ya que no verifica la segunda
de las palabras importantes. No verifica la palabra: único que aparece en: “…estan
relacionados con un único elemento de… ” y eso es lo que no se cumple. Tenemos un elemento
de 𝐴 del que salen dos flechas.
𝑨 𝑩
La relación ℛ3 soluciona los problemas del todos y del único que aparecían en las relaciones
anteriores. Acá vemos que, de todos los elementos de 𝐴, sale una única flecha hacia 𝐵. Eso
hace que, la relación ℛ3 sí sea una función ya que verifica la definición.
En matemática, como la que ven en Análisis Matemático 1, se trabaja con funciones en las que
los conjuntos 𝐴 y 𝐵, son conjuntos “densos” como los son los conjuntos numéricos de ℝ o ℚ.
Pero en una materia como “estructuras discretas” vamos a trabajar con objetos matemáticos
discretos (aun algunos con infinita cantidad de elementos).
Importante: Una función siempre se define con una terna. Hay que decir quiénes son los
conjuntos dominio (lo que llamamos 𝐴) y codominio (lo que llamamos 𝐵) y dar la regla de
asignación (cómo están relacionados los dos conjuntos).
Se escribe: 𝑓: 𝐴 → 𝐵/𝑓(𝑥) =
Por ejemplo:
𝑓: ℝ → ℝ/𝑓(𝑥) = 3𝑥 − 2
La expresión 𝑓(𝑥), que se lee “ 𝑓 de 𝑥”, significa que la flecha que sale de 𝑥 llega a…
𝑓: 𝐴 → 𝐵 / 𝑓(𝑥) = ⋯
Al elemento al que llega una flecha que partió de un 𝑥 ∈ 𝐴, se lo nota con la expresión 𝑓(𝑥) y se
llama la imagen de un elemento. Esta imagen puntual de un elemento de 𝐴, es un elemento
de 𝐵. Al conjunto de todas las imágenes de todos los elementos de 𝐴, se lo llama conjunto
imagen, se lo nota 𝐼𝑚(𝑓) y verifica que 𝐼𝑚(𝑓) ⊂ 𝐵
Veamos esto en los ejemplos que trabajamos, para eso vamos a ponerle nombre a los elementos
de cada conjunto:
Analicemos el ejemplo de las madres, la imagen de, por ejemplo, cada persona sería el nombre
de la madre biológica. Por ejemplo:
Algo que, suele ser muy útil es enganchar funciones. Miremos en lo que pasó con el ejemplo
del nieto de Maradona (e hijo del Kun)…
Podríamos haber aplicado la función ℛ4 directamente desde el renglón que refería a Benjamín
Agüero:
𝑩
𝑷
𝑮𝒊𝒂𝒏𝒏𝒊𝒏𝒂
𝑩𝒆𝒏𝒋𝒂𝒎í𝒏 𝑴𝒂𝒓𝒂𝒅𝒐𝒏𝒂 𝑪𝒍𝒂𝒖𝒅𝒊𝒂
𝑨𝒈ü𝒆𝒓𝒐 𝑽𝒊𝒍𝒍𝒂𝒇𝒂ñ𝒆
Formalicémoslo:
Como podemos ver la nueva función 𝑔 ∘ 𝑓 tiene como dominio, el mismo dominio que tenía la
función que primero se aplica y como codominio el codominio de la segunda. Y es condición
super necesaria que la imagen de la primera que se aplique esté incluida en el dominio de la
segunda.
Un par de ejemplos matemáticos, pero con conjuntos discretos, así que voy a definir los
conjuntos:
𝐴 = {−1,0,1,2,3,4}
𝐵 = {𝑥 ∈ ℤ/−1 ≤ 𝑥 ≤ 20}
𝐶 = {𝑥 ∈ ℕ /𝑥 𝑒𝑠 𝑝𝑎𝑟 𝑦 𝑚𝑒𝑛𝑜𝑟 𝑎 41}
𝑓: 𝐴 → ℤ / 𝑓(𝑥) = 𝑥 2 + 1
𝑔: 𝐵 → ℤ / 𝑔(𝑥) = 2𝑥
4+𝑥
ℎ: 𝐶 → ℤ / ℎ(𝑥) =
𝑥
Para poder hacer 𝑔 ∘ 𝑓 la imagen de 𝑓 debe estar incluida en el dominio de 𝑔. Entonces veamos
la imagen de 𝑓. Los cálculos de imágenes suelen ser bastante trabajosos. Por eso (y porque los
dominios de estas funciones tienen pocos elementos), vamos a hacerlo de a poco y lo vamos a
ver en diagramas de Venn.
𝑓(−1) = (−1)2 + 1
𝑓(−1) = 2
Lo mismo hacemos con el resto de los valores del dominio. Una vez que hicimos todas las
operaciones, miramos qué nos queda como conjunto imagen:
𝑔 ∘ 𝑓: 𝐴 → ℤ
Y para hallar la expresión o la regla de asignación, hacemos la composición:
(𝑔 ∘ 𝑓)(𝑥) = 𝑔(𝑓(𝑥))
(𝑔 ∘ 𝑓)(𝑥) = 𝑔(𝑥 2 + 1)
(𝑔 ∘ 𝑓)(𝑥) = 2 ⋅ (𝑥 2 + 1)
Para poder hacer ℎ ∘ 𝑔 la imagen de 𝑔 debe estar incluida en el dominio de ℎ. Entonces veamos
la imagen de 𝑔. Nuevamente podemos hacer el cálculo de la imagen a mano. Ahora voy a evitar
el diagrama de Venn.
Para calcular a qué elemento de ℤ llegaría cada flecha, solo hacemos la cuenta que nos indica la
regla de asignación. En este caso, lo que hace la función es solo multiplicar por 2, por lo que a
imagen estará compuesta por los dobles de los elementos del dominio.
𝐷𝑜𝑚(𝑔) = {−1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}
𝐼𝑚(𝑔) = {−2,0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40}
Como el dominio de ℎ es el conjunto 𝐶, que está formado por todos los naturales pares que son
menores a 41, vemos que, en este caso, no pasa que 𝐼𝑚(𝑓) ⊂ 𝐵 ya que los naturales arrancan
en el 1 y la imagen de 𝑔 incluye al −2 y al 0, por lo que no podríamos hacer la composición.
Les queda a ustedes ver si se pueden hacer otras composiciones mezclando estas 3 funciones.
Sigamos avanzando, ahora pregunto…. Y si “damos vuelta las flechas del dibujo de 𝓡𝟑 , ¿Será
función de 𝐵 en 𝐴?
El segundo problema es que, en la función original, hay un elemento (podrían ser más) de los
que salen dos flechas distintas. No queremos que eso pase, porque si eso pasa, al invertir el
sentido de las flechas, no se verificaría la palabra único. Definamos eso:
Definición: Decimos que una función 𝑓: 𝐴 → 𝐵 es inyectiva, si ∀𝑎, 𝑏 ∈ 𝐷𝑜𝑚(𝑓) se verifica que
𝑓(𝑎) ≠ 𝑓(𝑏)
Es decir que es condición necesaria (y suficiente), que una función sea biyectiva para que exista
la función inversa, y que la composición entre ambas (en cualquier orden) vuelve al punto inicial.
Ejemplo:
𝑔: 𝐵 → ℤ / 𝑔(𝑥) = 2𝑥
𝐵 = {𝑥 ∈ ℤ/−1 ≤ 𝑥 ≤ 20}
Pero en lugar de usarla así, la vamos a cambiar, al cambiarle el codominio. Tomemos, entonces
las siguiente función:
𝐷 = {−2,0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40}
𝐵 = {𝑥 ∈ ℤ/−1 ≤ 𝑥 ≤ 20}
𝑔: 𝐵 → 𝐷 / 𝑔(𝑥) = 2𝑥
La imagen de 𝑔 no cambió respecto a la que habíamos calculado antes:
𝐼𝑚(𝑔) = {−2,0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40}
Vemos que ahora coincide con el codominio, por lo que es sobreyectiva. Además, como el
cálculo de “multiplicar por 2” no me genera elementos repetidos (como sí podría generar, por
ejemplo, un elevar al cuadrado) entonces, cada elemento del dominio va a parar a un elemento
distinto del codominio, por lo que la función es inyectiva.
Como es inyectiva y sobreyectiva, es, además, biyectiva por lo que admite inversa:
1
𝑔−1 : 𝐷 → 𝐵; 𝑔−1 (𝑥) = 𝑥
2
Yo creo que es un buen momento para repasar todo esto con una linda tanda de ejercicios, ¿no
crees lo mismo?
Ejercicios
1) Sean 𝐴 = {𝑎, 𝑏, 𝑐, 𝑑}, 𝐵 = {1,2,3,4} , se define el conjunto 𝑅 formado por los pares
{(𝑎; 1), (𝑏; 1); (𝑐; 2), (𝑑; 3)},
a. ¿Corresponde 𝑅 a una función? ¿Por qué?
b. En caso de que la respuesta anterior fuera afirmativa, indicar Dominio,
Codominio e Imagen de la función. En caso de que no fuera función agregar o
quitar la mínima cantidad de pares para que resulte una función y, de ésta,
indicar Dominio, Codominio e Imagen.
2) Sean 𝐴 = {𝑎, 𝑏, 𝑐, 𝑑}, 𝐵 = {1,2,3,4} , se define el conjunto 𝑅 formado por los pares
{(𝑑; 1), (𝑐; 2); (𝑎; 2), (𝑎; 3)},
a. ¿Corresponde 𝑅 a una función? ¿Por qué?
b. En caso de que la respuesta anterior fuera afirmativa, indicar Dominio,
Codominio e Imagen de la función. En caso de que no fuera función agregar o
quitar la mínima cantidad de pares para que resulte una función y, de ésta,
indicar Dominio, Codominio e Imagen.
3) Sean 𝐴 el conjunto formado por todos las personas inscriptas en la materia “Estructuras
Discretas” y 𝑅 la relación definida por “… tiene como altura …”,
a. ¿Corresponde 𝑅 a una función? ¿Por qué?
b. En caso de que la respuesta anterior fuera afirmativa, indicar Dominio,
Codominio e Imagen de la función. En caso de que no fuera función agregar o
quitar la mínima cantidad de pares para que resulte una función y, de ésta,
indicar Dominio, Codominio e Imagen.
10) Considerar las funciones del ejercicio 8). Decidir, en cada caso, si es posible hacer las
siguientes composiciones, justificando en cada caso. En los casos en los que sea posible
dar la composición (fórmula o pares)
a. 𝑓1 ∘ 𝑓3
b. 𝑓3 ∘ 𝑓1
c. 𝑓2 ∘ 𝑓4
d. 𝑓4 ∘ 𝑓2
e. 𝑓3 ∘ 𝑓4
A pensar:
La idea de estos problemas es empezar a familiarizarnos con los números y sus operaciones.
Vemos que podemos contar sin contar. Por ejemplo, en el primer problema, podríamos haber
hecho la lista de todos los números enteros desde el 25 hasta el 79:
25 – 26 – 27 – 28 – 29 – 30 – 31 – 32 – 33 – 34 – 35 – 36 – 37 – 38 – 39 – 40 – 41 – 42 – 43 – 44
– 45 – 46 – 47 – 48 – 49 – 50 – 51 – 52 – 53 – 54 – 55 – 56 – 57 – 59 – 60 – 61 – 62 – 63 – 64 –
65 – 66 – 67 – 68 – 69 – 70 – 71 – 72 – 73 – 74 – 75 – 76 – 77 – 78 – 79
Y contar uno por uno, lo que nos va a dar el gran total de 54 números. Pero si la “distancia”
entre el 25 y el 79 hubiese sido mayor, ya esto se vuelve un camino muy tedioso. Alguien capaz
que se dio cuenta que justo ese 54 se puede conseguir haciendo 79 – 25. ¿Será casualidad?
Con el 2do problema podríamos haber hecho algo parecido. Arrancar con el 86 y hacer una lista
de 53 números y ver a cuál llegamos. Eso es muy poco práctico.
54
25 79 79 – 25 = 54
Yo no sé qué piensan ustedes, pero a mí eso me parece que se puede parecer a lo del problema
2, ya que, si pensamos en esa lista de números que escribimos arriba, el 25 ocupa el 1er lugar y
el 79 ocupa el lugar 54.
53
86 ?? ?? – 86 = 53
𝑥 − 86 = 53
Entonces cuando, los ejercicios 4 y 5 hablan de una lista de “𝑟” números consecutivos en donde
el menor es “𝑛” (o donde el mayor es “𝑚”):
𝒓
𝒏 𝒎 𝒎−𝒏= 𝒓
Ahora vamos a contar otras cosas. Vamos a analizar distintos caminos. Igual, vamos a arrancar
con unos problemas:
1) Un negocio que vende ropa quiere organizar los cinturones que tiene en stock. Se sabe
que tiene 3 modelos diferentes (𝐴, 𝐵 𝑦 𝐶) y, que cada uno, está disponible en 7
tamaños diferentes (1 a 7). ¿Cuántos tipos de cinturones diferentes tiene (considerando
modelo y tamaño)?
2) En un almuerzo de un picnic se ofrece un sándwich (a elegir entre 4 opciones distintas),
una bebida (se puede elegir entre gaseosa, jugo o leche) y un helado (se puede elegir
entre 3 sabores diferentes). ¿Cuántas opciones de menú diferentes tiene, para su
elección, una persona?
𝐴 4
5
6
7
1
2
3
Cinturones 𝐵 4
5
6
7
1
2
3
𝐶 4
5
6
7
Así, la primera separación entre 3 modelos de cinturones nos abre, en el esquema, 3 caminos.
Y cada uno de estos caminos, se puede abrir en 7 nuevas posibles opciones. Entonces, nos queda
que el total de cinturones es de 3 ⋅ 7 = 21. Este esquema que se realizó recién, se llama
esquema de tipo “árbol” y cada camino se llama “rama”.
Como vemos, por cada una de las 4 opciones de sándwich, hay 3 opciones de bebida y por cada
una de estas, hay 3 de sabor de helado. Lo que nos da:
𝑇𝑜𝑡𝑎𝑙 = 4 ⋅ 3 ⋅ 3
𝑇𝑜𝑡𝑎𝑙 = 36
Enunciemos esto:
Este principio puede ser extendido más allá de una clasificación que considera solo 2 eventos.
Puede aplicarse a 3, 4 o más propiedades. Lo esencial de este principio es la palabra
independientemente, ya que este no es válido si el segundo evento depende de la decisión del
primero.
Virus Melissa
A fines de los 90, un virus de computadora Por ejemplo, si una persona tiene 5 remeras de colores
llamado Melissa causó estragos al acabar diferentes y 7 pantalones (también de colores
con los recursos del sistema. El virus se
esparció por un correo electrónico que diferentes), podría formar 35 combinaciones diferentes.
contenía un archivo adjunto de Sin embargo, si le preocupa la combinación de colores,
procesador de texto con un macro por ejemplo, si fuese una persona fanática de River y no
maligno. Cuando se abría el documento,
quiere combinar el azul con el amarillo, la elección del
el macro reenviaba el mensaje junto con
el archivo del documento a las primeras 50 color del pantalón no será tan libre ya que dependerá del
direcciones obtenidas de la libreta de color de la remera. En este caso, el principio de
direcciones del usuario. Cuando se multiplicación, como fue enunciado, no serviría para
recibían estas copias y se abrían, el macro
contemplar los posibles atuendos de esta persona.
de nuevo reenviaba el mensaje por correo
electrónico y el documento de procesador
Analicemos este caso:
de textos, y así sucesivamente. El virus
causó problemas creando mensajes más
Supongamos que tiene 5 remeras:
rápido de lo que podían enviarse. Los
mensajes listos para enviarse se
almacenaban temporalmente en un disco.
Si el disco se llenaba, el sistema podía
caer en bloqueo permanente (congelarse
o lo que se conoce habitualmente como
“inhibirse”) o incluso descomponerse. Y tiene 7 pares de pantalones:
Después de que el virus enviaba el correo
a las primeras 50 direcciones, cada uno de
esos receptores enviaba entonces el
correo a 50 direcciones. Por el principio de
la multiplicación, se tenían 50 · 50 = 2500
receptores más. Cada uno de ellos
enviaba el correo a 50 direcciones. De
nuevo, por el principio de la multiplicación,
ahora había 50 · 50 · 50 =125.000
receptores adicionales. ¿Cuántas combinaciones diferentes de remera y
Después de más iteraciones, habría 50 ·
pantalón puede hacer si, bajo ningún motivo, junta los
50 · 50 · 50 = 6.250.000 receptores
adicionales. colores azul con el amarillo?
Así, después de sólo cuatro iteraciones se
habían enviado 6.250.000 + 125.000 + Pensarlo antes de seguir leyendo.
2500 + 50 + 1 = 6.377.551 copias del
mensaje.
Si no hubiera restricciones para los colores, podría elegir entre 5 remeras y 7 pantalones:
5 7 𝑇𝑜𝑡𝑎𝑙: 5 ⋅ 7 = 35
Remeras Pantalón
Pero sabemos que hay restricciones. Entonces analicemos el problema más “a mano”:
¿Qué pasa si, de entrada, elige una remera que no es ni azul, ni amarilla? En ese caso tenemos
solo para elegir 3 remeras y no hay restricciones para los pantalones:
3 7 𝑇𝑜𝑡𝑎𝑙: 3 ⋅ 7 = 21
Remeras Pantalón
¿Y si elige de entrada la azul? En este caso hay una sola opción para remera (ya que solo hay
una azul) y hay 6 opciones de pantalones (porque la amarilla queda descartada):
1 6 𝑇𝑜𝑡𝑎𝑙: 1 ⋅ 6 = 6
Remeras Pantalón
¿Y si elige de entrada la amarilla? En este caso, igual que en el caso anterior, hay una sola opción
para remera (ya que solo hay una amarilla) y hay 6 opciones de pantalones (porque la azul queda
descartada):
1 6 𝑇𝑜𝑡𝑎𝑙: 1 ⋅ 6 = 6
Remeras Pantalón
¿Te animás a dibujar el árbol de esta situación? Ahora, no todas las ramas que salgan de cada
opción de remera tendrán la misma cantidad sub-ramas.
Enunciemos algo:
Este principio, al igual que el principio de multiplicación, puede ser extendido más allá de una
clasificación que considera solo 2 eventos. Puede aplicarse a 3, 4 o más propiedades. Lo
esencial de este principio es que estos eventos no pueden ocurrir de manera simultánea.
Resumiendo: Si tenemos que contar eventos u objetos que se forman con pasos
sucesivos, (Cosa 1 Y Cosa 2 Y Cosa 3 Y …) se usa el principio de la multiplicación.
Sin embargo, en el caso de tener que contar eventos u objetos que no pasan de
manera simultánea (Cosa 1 Ó Cosa 2 Ó Cosa 3 Ó …) se usa el principio de la suma.
Para pensar:
Un grupo de 6 estudiantes debe organizarse para rendir un examen oral e individual.
Supongamos que el orden en el que pasen a rendir no depende de cuánto estudiaron, ni de lo
que digan los que ya rindieron, ¿De cuántas maneras diferentes se pueden organizar para entrar
a rendir?
Como siempre:
Este problema puede pensarse desde un esquema de árbol o, directamente, con el principio de
la multiplicación.
• Pasa primero
• Pasa segundo
• Pasa tercero
• Pasa cuarto
• Pasa quinto
• Pasa sexto
Una vez que identificamos esto, tenemos que preguntarnos ¿Cuántas opciones hay para cada
uno de estos eventos? Y si estos eventos pasan de manera simultánea (o sucesiva) o si no.
Observamos que, en este caso, la elección de quien pase a rendir primero no condiciona la
elección de quien pasa segundo (solo reduce el número de posibles candidatos). Entonces
tenemos:
6 5 4 3 2 1 𝑇𝑜𝑡𝑎𝑙: 6 ⋅ 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1 = 720
Pasa 1ro Pasa 2do Pasa 3ro Pasa 4to Pasa 5to Pasa 6to
Entonces, ¿Cuántos anagramas se pueden armar con las letras de la palabra ESPACIO?
El problema, en esencia es igual al del examen. Se trata de ordenar esas letras, de una forma
análoga a la de ordenar estudiantes. En este caso, la palabra ESPACIO tiene 7 letras, por lo que,
siguiendo la misma lógica, será:
𝑇𝑜𝑡𝑎𝑙 = 7 ⋅ 6 ⋅ 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1 = 7! = 5040
Ejemplos
A R QUE T I P O
Lo que, en realidad, nos dice que tenemos que mezclar, solamente 7 objetos. Por lo que el total
sería 7! = 5040.
Algo parecido tenemos que pensar para el segundo ejercicio. Sabemos que la QU tienen que
estar juntas pero solo hay dos opciones para lo que sigue: O tenemos QUE o tenemos QUI. Por
lo tanto, parecido a lo que hicimos con las remeras y los pantalones, analicemos los casos por
separado.
El caso en el que esté la QUE, es el mismo que el del primer problema. Nos dan 7! opciones.
El caso en el que esté la QUI, es muy muy muy muy parecido al del primer problema. Ahora
tenemos:
A R QUI T E P O
A R QUE T I P O
A R QEU T I P O
A R EUQ T I P O
A R EQU T I P O
A R UEQ T I P O
A R UQE T I P O
Vemos que, mezclar las letras Q U E nos aporta 6 opciones. Y en cada una de estas opciones,
tenemos que mezclar 7 bloques. Por lo que:
Entonces:
𝑇𝑜𝑡𝑎𝑙 = 3! ⋅ 7!
Vamos ahora con un ejemplo clásico (que van a encontrar en cualquier libro que trate estos
temas):
Antes que nada, veamos lo que nos pide este ejercicio. Tenemos 6
personas (A, B, C, D, E, F) y queremos ver de cuántas maneras distintas
se pueden sentar acá:
Pero tenemos una aclaración y es que, si las sentamos, por ejemplo, así:
F
E A
D B
C
O, los hacemos sentar así, en donde todos se corrieron un lugar:
E
D F
C A
B
Eso lo consideramos como una sola forma. En otras palabras, al preguntarnos ¿De cuántas
maneras se pueden sentar seis personas alrededor de una mesa circular?, nos preguntamos
formas de sentarse respecto de las personas y no tanto el lugar “físico” en la mesa ya que las
mesas redondas no tienen una cabecera ni lugares diferenciados. El “truco” de este tipo de
problemas es dejar un punto fijo. Es decir, tomamos a una de las personas y la fijamos a una
silla (a esta persona, no la movemos). Y nos preocupamos, entonces, por mezclar al resto. Al
asignar, por ejemplo, a A en un lugar, esto da lugar a 5 posibles posiciones concretas: A la
derecha de A, a la izquierda de A, frente a A, etc. Y el problema, entonces, se reduce a mezclar
a 5 personas (la 6ta es la que queda fija en una posición).
Entonces, ¿De cuántas maneras se pueden sentar seis personas alrededor de una mesa circular?,
de 5! maneras diferentes.
IMPORTANTE:
Es usual que este tipo de problemas den como resultados números bastante
grandes. Por eso, en muchas oportunidades dejamos expresada la solución y no
la calculamos hasta el final. Es una de las razones por las que, en muchos de los
ejemplos anteriores, aparecen como respuesta 5! o 3! ⋅ 7! en lugar de los
números que resultan de hacer las cuentas.
Es un buen momento para detenernos a hacer unos ejercicios para afianzar lo que acabamos de
ver. Traten de hacerlos antes de avanzar con la lectura.
Ejercicios
1. ¿De cuántas formas se puede cruzar un río una vez, si se cuenta con 1 bote y 2 barcos?
2. ¿De cuántas formas se puede vestir una persona que tiene 2 pantalones y 3 camisas?
3. ¿Cuántos resultados se pueden obtener si se lanza un dado 2 veces?
4. ¿De cuántas formas se puede pedir una pizza, si hay 2 opciones de masa (a la piedra y
media masa), y 4 sabores (Muzzarella, Napolitana, Jamón y Morrones y Calabresa)? Solo
se puede pedir una masa y un sabor.
5. ¿Cuántos resultados se pueden obtener si se lanza una moneda o un dado?
6.
a) ¿Cuántos resultados distintos se puede obtener si se lanza una moneda 3 veces?
b) ¿Y si se lanza 5 veces?
7. Un repuesto de automóvil se vende en 3 negocios de José C. Paz y en 8 negocios de Pilar.
¿De cuántas formas se puede adquirir el repuesto?
8. ¿De cuántas formas distintas puede cenar una persona si hay: 5 aperitivos, 3 entradas,
4 platos principales, 3 bebidas y 2 postres? Tener en cuenta que solo se puede elegir
una opción de cada cosa.
9. Una sala de lectura tiene 5 puertas:
a) ¿de cuántas maneras puede entrar a la sala un estudiante y salir por una puerta
diferente?
b) ¿y si sale por cualquier puerta?
10. De la ciudad 𝐴 a la ciudad 𝐵, se puede ir mediante 2 colectivos o 3 trenes. De la ciudad
B a la ciudad C se puede ir mediante 2 barcos, 2 trenes o 3 aviones. ¿De cuántas formas
se puede ir de la ciudad A a la ciudad C, pasando por B?
11. ¿Cuántos números de dos cifras pueden formarse con los dígitos: 1; 2; 3; 4 y 5, si:
a) Si se pueden repetir los dígitos.
b) No se pueden repetir los dígitos.
12. ¿Cuántos números de tres dígitos se pueden formar sin dígitos repetidos?
13. ¿Cuántas patentes diferentes de autos se pueden formar con 2 letras, seguidas de 3
números del 0 al 9 y seguido de otras 2 letras? (consideremos un abecedario de 27
letras)
14. ¿Cuántos números pares de 3 cifras empiezan con 5 o 7?
15. ¿Cuántos números del 1 al 1000, no contienen la cifra 4?
23.
a. ¿Cuántos anagramas distintos se pueden formar con la palabra MURCIELAGO?
b. ¿Cuántas de esas palabras empiezan con vocal?
c. ¿Cuántas empiezan con vocal y terminan con O?
d. ¿Cuántas de la palabras tienen todas las vocales juntas?
e. ¿Cuántas de la palabras tienen todas las vocales juntas y en orden (a-e-i-o-u)?
Ahora que terminaron de hacer estos ejercicios y que ya tenemos claro algunos conceptos como
los principios de multiplicación y de adición, y la idea de las permutaciones, podemos seguir
avanzando un poco.
De la misma forma que pensamos los anagramas y analizamos el orden en el que estudiantes
iban a rendir un examen, podríamos pensar problemas del estilo:
¿Cuántas palabras de 5 letras (Sin que se repitan las letras) se pueden formar con las letras de
alfabeto dactilográfico argentino (Observen que la CH tiene seña propia)11?
1ra letra 2da letra 3ra letra 4ta letra 5ta letra
𝑇𝑜𝑡𝑎𝑙 = 28 ⋅ 27 ⋅ 26 ⋅ 25 ⋅ 24 = 11.793.600
En este último caso parece que es “casi” una permutación, solo que incompleta, ya que no
llegamos al 1 (truncamos el factorial en 24).
Si tuviéramos palabras de 28 letras, en donde solo tuviéramos que mezclar las letras del
abecedario, sería:
𝑇𝑜𝑡𝑎𝑙 = 28!
𝑇𝑜𝑡𝑎𝑙 = 28 ⋅ 27 ⋅ 26 ⋅ 25 ⋅ 24 ⋅ 23 ⋅ … ⋅ 3 ⋅ 2 ⋅ 1
Sin embargo, en el ejemplo original, tenemos que cortar todas estas multiplicaciones en el 24.
Pudimos hacerlo “a mano” multiplicando los números del 24 al 28 sin grandes problemas.
Ahora, si la palabra fuera de 10 letras o de 15, ya sería mucho más molesto hacer estas cuentas
a mano, por lo que estaría bueno generalizar esta idea de “permutación truncada”.
Si tratamos de generalizar esto, deberíamos pensar alguna forma de anular todas las
multiplicaciones que vienen despues del 24.
11
Este es el alfabeto en Lengua de Señas Argentina, una ilustración del dibujante sordo Jorge Bossio.
12
LSA: Lengua de Señas Argentina
Prof. Julieta Matteucci 76
UNPAZ – LGTI (6004)
2024
Estructuras Discretas
28 ⋅ 27 ⋅ 26 ⋅ 25 ⋅ 24 ⋅ 23 ⋅ … ⋅ 3 ⋅ 2 ⋅ 1
Lo dividimos por
23 ⋅ 22 ⋅ 21 ⋅ 20 ⋅ … ⋅ 3 ⋅ 2 ⋅ 1
Nos queda justo:
28 ⋅ 27 ⋅ 26 ⋅ 25 ⋅ 24 ⋅ 23 ⋅ 22 ⋅ 21 ⋅ 20 ⋅ … ⋅ 3 ⋅ 2 ⋅ 1
= 28 ⋅ 27 ⋅ 26 ⋅ 25 ⋅ 24 = 11.793.600
23 ⋅ 22 ⋅ 21 ⋅ 20 ⋅ … ⋅ 3 ⋅ 2 ⋅ 1
Y todo eso es lo mismo que decir:
28!
𝑇𝑜𝑡𝑎𝑙 =
23!
En el problema, teníamos un conjunto de 28 letras (señas) y teníamos que seleccionar 5 (y
ordenarlas) para armar nuestras palabras. Y sabemos, ademas, que 23 = 28 – 5
Generalizamos:
𝑛!
𝑃(𝑛, 𝑘) =
(𝑛 − 𝑘)!
Nota: En algunos libros y apuntes este tipo de permutaciones puede aparecer con el nombre
de Variaciones 𝑉(𝑛, 𝑘).
Lo importante de esta definición es que los elementos son diferentes, hay un orden que respetar
y los elementos no se pueden repetir.
Entonces (y repito la pregunta que resolvimos antes), ¿Cuántas palabras de 5 letras (Sin que se
repitan las letras) se pueden formar con las señas de alfabeto dactilográfico argentino?
Como el total de señas es 28 y las palabras son de 5 letras, serán las permutaciones de 28
elementos tomados de a 5 (𝑛 = 28 ; 𝑘 = 5)
𝑛!
𝑃(𝑛, 𝑘) =
(𝑛 − 𝑘)!
28!
𝑃(28,5) =
(28 − 5)!
28!
𝑃(28,5) = = 11.793.600
23!
Sigamos analizando situaciones…
Supongamos que en un curso hay 28 estudiantes y hay que elegir a 5 para que vayan a la
biblioteca a buscar (y traer al aula) el material necesario para hacer un trabajo. ¿De cuántas
formas diferentes se pueden elegir a esos 5 estudiantes del total de 28?
Tomense unos 5 o 10 minutos para pensar este problema antes de seguir leyendo. Piensen
cómo se vincula con las permutaciones de 𝑛 elementos tomadas de a 𝑘, que acabamos de
definir y con las permutaciones de todos los elementos que vimos antes.
Ahora que pasaron esos valiosos minutos pensando, continuamos. Espero que, entre las cosas
que pensaron, se hayan dado cuenta que, a diferencia de los casos anteriores, acá no tenemos
un orden establecido para elegir estudiantes. Es lo mismo elegir a alguien primero o último.
Cada estudiante tendrá un mismo rol. No hay diferencias.
Arranquemos llevándolo a los casos que conocemos: SUPONGAMOS que nos importa el orden
en el que los elegimos. En este caso, el problema es igual al del las palabras de 5 letras que se
pueden escribir con el alfabeto en lengua de señas. Vuelve a ser, elegir 5 objetos (en este caso,
estudiantes) de un total de 28:
28!
𝑃(28,5) =
(28 − 5)!
28!
𝑃(28,5) = = 11.793.600
23!
Pero ahora, recordamos que, en realidad no nos importa el orden en el que se elijen. En
definitiva, es lo mismo elegir a ABCDE que EDCBA o que cualquier otra mezcla (o permutación),
ya que no nos importa el orden. Esto es algo parecido al problema que analizamos, cuando
vimos los posibles anagramas de la palabra ARQUETIPO y pedíamos que las letras Q-U-E tenían
que quedar siempre juntas (pero no necesariamente en ese orden). Ese problema, lo
solucionamos, multiplicando por el factorial de 3, ya que eso nos permitía “mezclar” las letras
Q-U-E.
Bueno, ahora es parecido. Con 𝑃(28,5), obtenemos los nombres de quienes deben ir a buscar
el material a la biblioteca, pero con un orden. Por ejemplo, supongamos que elegimos a A-B-C-
D-E.
A B C D E
E D C B A
A B C E D
B A E D C
Y muchas más… A diferencia del caso de las letras Q-U-E que, cuando hicimos solo el anagrama
de
A R QUE T I P O
Nos faltaban considerar los otros casos, y por eso, tuvimos que multiplicar por el factorial de 3,
ahora estamos considerando muchos más casos de los que necesitamos ya que, como no nos
importa el orden de la elección, todos estos casos:
E D C B A
A B C E D
B A E D C
(y todos los otros casos que no estamos escribiendo acá) son casos repetidos. Es lo mismo que
elegir
A B C D E
Tenemos, entonces que “quitar” todas estas mezclas. No queremos contarlas tantas veces. Si
para agregar las mezclas, lo que hicimos fue multiplicar por el factorial de la cantidad de
elementos, ahora, para quitarlas, dividimos.
𝑛!
𝐶(𝑛, 𝑘) =
𝑘! (𝑛 − 𝑘)!
Lo importante de esta definición es que los elementos son diferentes, pero No hay un orden que
respetar y los elementos no se pueden repetir.
Ejemplo:
Acá no lo podemos pensar con las casillas y el principio de la multiplicación, porque sería
demasiado complejo analizar todos los posibles casos. Pero lo que sí sabemos es que, de esos
8 bits (que están bien diferenciados, porque cada cadena de bits, en la computadora, identifica
un carácter diferente), tiene solo 4 unos. Por lo que, lo que tenemos que hacer es elegir, de
esos 8 bits cuáles son los cuatro que van a tener un 1 y listo!. Las cadenas de bits solo pueden
tener “unos” y “ceros”, por lo que al elegir las 4 posiciones en las que van a estar los 1, las otras
quedan automaticamente asignadas a un cero.
De esta forma, el problema se puede pensar como: ¿De cuántas maneras diferentes se pueden
elegir 4 bits de una cadena de 8 bits? Y la respuesta será:
8! 40320
𝐶(8,4) = = = 70
4! (8 − 4)! 24 ⋅ 24
¿Cómo hacemos estas cuentas con la calculadora?.
La mayoria de las calculadoras científicas tienen unas teclas que nos sirven para hacer estas
cuentas:
Una para factorial con el símbolo de 𝒙! (normalmente está como una función inversa, es decir
dibujada en color arriba de la tecla)
Acá vemos dos ejemplos de los modelos más comunes de calculadoras y vemos dónde están
esas funciones:
factorial
𝒏𝑷𝒓
𝒏𝑪𝒓
Así, por ejemplo, si quiero calcular 𝐶(8,4), tengo que usar la tecla 𝑛𝐶𝑟. Entonces, si la tecla es
directa (es decir, si en la calculadora aparece directamente en la tecla, escrito en blanco, como
en la imagen de la derecha), para calcular lo que queremos tenemos que colocar:
𝟖 𝒏𝑪𝒓 𝟒 =
Si, en cambio, la tecla es indirecta (es decir, si en la calculadora aparece arriba de la tecla, escrito
en amarillo, como en la imagen de la izquierda).
𝟖 𝒔𝒉𝒊𝒇𝒕 𝒏𝑪𝒓 𝟒 =
Un detalle importante, es que, aunque casi todas las calculadoras tienen la tecla de factorial, no
todas tienen las teclas de combinaciones y permutaciones de 𝑛 elementos tomados de a 𝑟.
Si no tenemos calculadora, tenemos otras opciones, por ejemplo, hay apps que se pueden
descargar al celular que presentan una calculadora científica como las de las imágenes de arriba,
otra opción es usar Geogebra que es una aplicación que permite hacer muchísimas cosas en
matemática. Se puede descargar (Geogebra Suite Calculator) en dispositivos móviles o usarla
desde una computadora (descargándola o desde el navegador) accediendo desde
https://www.geogebra.org/ .
Por ejemplo, para hacer
𝐶(8,4) con Geogebra
tenemos que escribir,
simplemente el comando
𝑛𝐶𝑟 o 𝑛𝑃𝑟 y después
colocar, entre paréntesis, los
dos valores. Y listo. De todas
formas, recuerden que no
hace falta llegar al número
final. Podemos dejar todo
expresado si no tenemos
algún dispositivo a mano, o si el resultado es un número muy grande.
Otro ejemplo:
Si una persona juega al truco, del total de 40 cartas, solo usa 3. ¿De cuántas maneras diferentes
se pueden elegir las 3 cartas que va a tener en juego en una mano de truco, del total del mazo
de 40 cartas españolas (sin los 8 y 9)?
Rta: Como no nos importa el orden en el que se eligen las cartas, nos queda:
40!
𝐶(40,3) = = 9880
3! (40 − 3)!
Creo que ya podemos seguir avanzando un poco, y agregando cosas que se repitan
Según relatan las tradiciones chinas, miles de años atrás (se estima
que en 2852-2738 A.c.), antes del nacimiento de la historia escrita,
vivió un gran sabio chino de nombre Fu Hsi. Existe la creencia de
que Fu Hsi fue el hombre que unificó la China, tornándose así su
primer Emperador. Como suele ocurrir en el caso en este tipo de historias, Fu Hsi estaba
sentado en la orilla del río Amarillo, meditando sobre el significado de la vida, cuando una
tortuga (considerada un animal sagrado en la antigua China) emergió del agua. En su caparazón
vio las marcas:
En uno de los libros más antiguos de la humanidad, el I Ching (Libro de los cambios) se sugiere
que la suerte de cada persona, en cada momento, viene dada por un mensaje, que se obtiene
al azar, expresado con 6 símbolos (cada símbolo es un Yang o un Yin). He aquí algunos mensajes:
dice así:
Como siempre, espero que estén pensando en estas preguntas y traten de resolverlas ANTES
de seguir con la lectura.
En cierta forma, esto es muy parecido al problema de los anagramas o de quienes iban a rendir
un examen. La diferencia sustancial es que ahora tenemos menos cantidad de símbolos. Pero
se puede pensar de manera similar. Necesitamos cadenas (o arreglos) de 6 elementos:
1ra línea 2da línea 3ra línea 4ta línea 5ta línea 6ta línea
Y, sabemos, que en cada una de esas líneas solo puede ir uno de dos símbolos un Yin o un Yang;
entonces:
2 2 2 2 2 2 𝑇𝑜𝑡𝑎𝑙: 2 ⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2 = 26 = 64
1ra línea 2da línea 3ra línea 4ta línea 5ta línea 6ta línea
Este fue un ejemplo en el que el objeto con el que formamos la cadena se repite (Yin o Yang).
Veamos otro ejemplo similar:
En cada uno de los lugares puede ir un relieve o estar liso. Es decir, puede estar en relieve o no.
Por lo que, para cada uno de los casos, tenemos 2 opciones:
2 2 2 2 2 2 𝑇𝑜𝑡𝑎𝑙: 2 ⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2 = 26 = 64
Lugar 1 Lugar 2 Lugar 3 Lugar 4 Lugar 5 Lugar 6
Lo que nos da suficiente para todos los símbolos del idioma español, el espacio, los 10 dígitos y
signos de puntuación. A continuación, vemos cómo se distribuyen esos puntos y espacios para
los símbolos y letras más comunes en Braille:
a b c d e f g h i j , ;
k l m n ñ o p q r s t : .
h
u v w x y z - ¡! ¿ “ ( )
?
á é í ó ú
Dicho de otra forma, ¿Cuántos subconjuntos se pueden formar con los elementos del conjunto
𝐴? (Pensarlo antes de seguir leyendo)
Como dijimos, es muy similar al caso del alfabeto Braille. Cuando vimos la cantidad de
combinaciones de letras y símbolos que podíamos armar con esos puntos, partimos de que un
punto podía tener dos estados (liso o en relieve) y ahora pasa lo mismo. Cuando pensamos en
un subconjunto, cada elemento puede formar parte o no del subconjunto. Por lo que, si
tenemos 4 elementos la cantidad de subconjuntos viene dado por:
2 2 2 2 𝑇𝑜𝑡𝑎𝑙: 2 ⋅ 2 ⋅ 2 ⋅ 2 = 24 = 16
Elemento Elemento Elemento Elemento
1 2 3 4
Ejercicios
1) Sea 𝑋 = {𝑎, 𝑏, 𝑐, 𝑑}, ¿De cuántas formas diferentes se pueden seleccionar 3 elementos
del conjunto X sino importa el orden en el que se seleccionan?
2) ¿De cuántas maneras se puede seleccionar un comité de tres entre un grupo de 11
personas?
3) ¿De cuántas maneras se puede elegir un equipo de trabajo de 5 personas de un grupo
de 13 personas?
4) De un total de 6 hombres y 7 mujeres se tiene que elegir un comité de 4 personas. ¿De
cuántas maneras se puede seleccionar si, como máximo, el comité debe incluir un
hombre?
5) ¿De cuántas maneras se puede elegir un comité de 4 republicanos, 3 demócratas y 2
independientes entre un grupo de 10 republicanos, 12 demócratas y 4 independientes?
6) ¿De cuántas maneras se puede seleccionar el presidente, vicepresidente y secretario de
un grupo de 11 personas?
7) ¿De cuántas maneras pueden terminar 12 caballos en el orden ganador, segundo lugar,
tercer lugar?
8) De un total de 6 hombres y 7 mujeres se tiene que elegir presidente, un vicepresidente,
un secretario y un tesorero, ¿De cuántas maneras se puede hacer la selección si,
a. no hay condiciones ni restricciones?
b. tiene que haber 2 hombres y 2 mujeres?
c. tiene que haber como mínimo 2 mujeres?
9) De un total de 6 hombres y 7 mujeres se tiene que elegir 4 representantes, ¿De cuántas
maneras se puede hacer la selección si,
a. no hay condiciones ni restricciones?
b. tiene que haber 2 hombres y 2 mujeres?
c. tiene que haber como mínimo 2 mujeres?
10) ¿De cuántas maneras pueden acomodarse 6 personas:
En esta última parte de la unidad, vamos a retomar algunos ejemplos que ya pensamos, pero
dándoles una vuelta de tuerca.
¿Cuántas palabras de 5 letras se pueden formar con las letras de abecedario dactilográfico
argentino si ahora se pueden repetir las letras?
1ra letra 2da letra 3ra letra 4ta letra 5ta letra
28 28 28 28 28
1ra letra 2da letra 3ra letra 4ta letra 5ta letra
Lo que le agregamos a este ejemplo, fue la posibilidad de que las letras se repitan. Cuando, a
diferencia del caso de las Permutaciones de 𝑛 elementos tomados de a 𝑟, donde no repetíamos,
aunque en ambos casos importa el orden ya que, no es lo mismo decir CASA que SACA. En
general, esto es un caso, que, si bien se puede reducir a una fórmula, puede ser pensado, como
lo hicimos recién, con el principio de la multiplicación.
𝑃𝑅 (𝑛, 𝑘) = 𝑛𝑘
Nota: En algunos libros y apuntes este tipo de permutaciones puede aparecer con el nombre
de Variaciones con repetición 𝑉𝑅 (𝑛, 𝑘).
Lo importante de esta definición es que los elementos son diferentes, hay un orden que respetar
y se pueden repetir los elementos. A este punto, ya nos estamos dando cuenta qué es lo que hay
que mirar en cada ejercicio de conteo: ¿Los elementos son diferentes? ¿Importa el orden en el
que se eligen los elementos? ¿Se pueden repetir?
Ya que hablamos de permutaciones con repetición, ¿qué pasa con los anagramas si las letras se
repiten?
Hace unas páginas, cuando pasamos de las permutaciones a las combinaciones, tuvimos que
“descontar” esos casos que habíamos contado de más. Con el caso de las permutaciones con
repetición va a pasar lo mismo. Supongamos que queremos calcular cuántos anagramas
posibles tiene la palabra CASA.
Si solamente hacemos uso de las permutaciones nos quedaría que el total es el factorial de 4, es
decir, 24, pero miremos algunos casos. Para arrancar voy a diferenciar las dos A con dos colores
diferentes: CASA. Miremos los posibles anagramas:
Ejemplo
¿Cuántos anagramas diferentes se pueden formar con las letras de la palabra MATEMATICA?
¿Listo? Veamos. La palabra MATEMATICA tiene un total de 10 letras, de las cuales algunas se
repiten. Hay dos M, dos T y tres A. Entonces, siguiendo la lógica de antes, tendremos que
quitarle todas las permutaciones de esas dos M (dividimos por el factorial de 2), todas las
permutaciones de esas dos T (dividimos por el factorial de 2) y todas las permutaciones de esas
tres A (dividimos por el factorial de 3).
10! 3.628.800
𝑇𝑜𝑡𝑎𝑙 = = = 151.200
2! ⋅ 2! ⋅ 3! 2⋅2⋅6
¡Muy bien! Ya casi terminamos con la idea de conteo. Solo nos queda un ejemplo más por
analizar. Este es el clásico ejemplo (tan clásico como el de la mesa redonda) de: “bolitas en
cajitas”.
¿De cuántas formas diferentes se pueden acomodar 5 bolitas en 4 cajas si las bolitas son todas
iguales?
¿Se animan a pensarlo un poco antes de seguir con la lectura? (esta es una pregunta retórica,
para no decirles, otra vez, que lo piensen antes de leer lo que sigue)
Analicemos algunos casos, como para ver cómo lo podemos pensar, podríamos tener:
OO OOO
O OOOO
OOOO O
Cada una de las filas que aparecen arriba es una posible combinación para las bolitas en las cajas,
entonces, ¿cómo podemos pensar esto? ¡¡Con un poco de ingenio!! Imaginemos una de esas
situaciones, pero, ahora, le voy a poner división a las cajas:
OO O O O
Esta combinación que armamos, la podría escribir como: OO|O|O|O y, por ejemplo, si
hiciéramos lo mismo con alguna de las otras que están dibujadas más arriba, tendríamos:
OO|OOO|| pero también ||O|OOOO
El “truco”, entonces, está en pensar esas divisiones como objetos. De esta forma, el ejercicio se
transforma en todas las maneras de “mezclar” 5 bolitas y 3 divisiones. Como los anagramas con
letras repetidas.
¿De cuántas formas diferentes se pueden acomodar 5 bolitas en 4 cajas si las bolitas son todas
iguales?
8! 40320
𝑇𝑜𝑡𝑎𝑙 = = = 56
5! ⋅ 3! 120 ⋅ 6
Y con eso (y unos ejercicios más) terminamos esta unidad. Pero antes vuelvo a la pregunta
inicial, si les pregunto si saben contar, ¿qué me responden ahora?
Ejercicios
1) ¿Cuántos resultados distintos pueden aparecer al lanzar un dado 4 veces?
2) El alfabeto Morse utiliza los signos ● y −. Utilizando como máximo cuatro de estos
signos, ¿cuántas secuencias distintas puedes formar?
3) Una cafetería vende 10 tipos de café diferentes. Cinco amigos quieren tomar cada uno
un café. ¿Cuántas formas posibles tienen de hacerlo?
4)
a. ¿Cuántos números de 6 cifras puedes escribir con los dígitos 1, 2 y 3?
b. ¿Cuántos de ellos contienen todos los dígitos 1, 2 y 3 al menos una vez?
5) En una clase de 20 alumnos se van a conceder 3 premios: uno al más destacado en
matemática, otro al mejor en historia y otro al mejor deportista. ¿De cuántas formas
distintas podemos hacerlo?
6) ¿De cuántas maneras distintas se pueden guardar 4 fibrones azules en 3 cajones?
7) ¿Cuántos anagramas diferentes se pueden formar con las letras de la palabra
ESTRUCTURAS?
8) ¿Cuántos anagramas diferentes se pueden formar con las letras de la palabra DISCRETAS
que tengan el bloque DIS junto?
9) ¿De cuántas maneras distintas se pueden poner 6 bolitas en 4 cajas?
10) ¿De cuántas maneras pueden ordenarse 6 libros en un estante si:
a. es posible cualquier ordenación?
b. 3 libros determinados deben estar juntos?
c. dos libros determinados deben ocupar los extremos?
d. tres libros son iguales entre sí?
La ciudad de Königsberg era la antigua capital de Prusia Oriental y fue, por ejemplo, donde
vivió el filósofo Kant y desarrolló gran parte de su pensamiento. Hoy no queda
prácticamente ningún alemán en la ciudad que, se llama ahora Kaliningrado y es parte de
Rusia, desde que se la incorporó en 1945, como botín de la II Guerra Mundial, y que tras la
disolución de la Unión Soviética
se ha quedado como parte de la
Federación Rusa.
¿Es posible recorrer los siete puentes sobre el río Pregel, que para ese entonces poseía la
ciudad, de tal manera que, si se iniciaba el recorrido en un determinado punto y se pasaba
una sola vez por cada uno de los puentes, en cualquier orden y se regresara al punto de
inicio? Este hecho se constituyó en uno de los retos más difíciles y atractivos de la época,
poniendo a prueba la preparación y habilidad de los matemáticos de ese entonces.
Entonces, ¿es posible dar un paseo cruzando nada más que una vez cada uno de los
puentes?
¿Se animan a intentar pensarlo un poco al problema y ver qué les dice el instinto?
Dejen unos minutos de leer y piensen en el problema.
Ahora que lo pensaron, veamos algunas cosas que pudieron haber pensado/razonado:
b d
c
Pero aún se puede mejorar más, ya que las distancias, tampoco nos importan demasiado. Solo
nos interesan las porciones de tierra y los puentes. De hecho, tampoco nos interesa el río. Solo
los puentes.
Pensando en este último dibujo, al que le agregamos las letras para poder hacer referencia a los
sectores con tierra y, recordando lo que hablamos en la unidad de relaciones, podríamos decir
que la información de cada uno de los puentes (que unen dos sectores de tierra) se puede
escribir:
Porque a las relaciones las podíamos dibujar usando grafos, y eso podemos hacer ahora:
𝒃 𝒅
La palabra grafo se utiliza para describir cierto tipo de estructuras que surgen de diversos
planteamientos como ser mapas de rutas, diagramas de circuitos o de flujo. Ampliamente,
son diagramas, que, interpretados de forma correcta, proporcionan variada información y
nos interesan por las relaciones que se dan entre sus elementos.
Veamos algunos ejemplos, antes de ponernos a definir mil cosas (ok, no son 1000, pero a
veces se sienten como si lo fueran):
Cara
Inicio
t=2*s
Cara Cruz Cara Cruz
s=s+1
F
t>10
Final
Podríamos decir que “Un grafo es un conjunto de puntos y líneas que unen pares de esos puntos”,
lo que no está mal, pero se puede formalizar un poco…
Los elementos de una arista 𝑒 son llamados sus extremos. Una arista se dice incidente en sus
extremos. Generalmente un grafo es dibujado en forma tal que cada vértice queda
representado por un punto en el plano, y cada arista por una curva que une los representantes
de sus extremos.
Si las aristas tienen un sentido, como en el caso de los grafos que representan las relaciones, el
grafo se llama grafo dirigido. Un ejemplo de grafo dirigido lo constituye la red de aguas de
una ciudad ya que cada tubería sólo admite que el agua la recorra en un único sentido, por el
contrario, la red de carreteras de un país representa, en general, un grafo no dirigido, puesto
que una misma carretera puede ser recorrida en ambos sentidos.
Observemos, también, que la definición de grafo va más allá del “dibujito” que solo es una forma
en la que representamos al grafo. Sin embargo, en lo que se refiere a esta materia
puntualmente, podemos pensar en el dibujito y en las distintas representaciones que vértices y
aristas generan. Normalmente trabajaremos con grafos que no son dirigidos, pero la mayoría
de los resultados se puede extender a uno dirigido.
𝑉(𝐺) = {𝑥, 𝑦, 𝑧, 𝑤, 𝑝, 𝑠}
𝐸(𝐺) = {𝑥𝑦, 𝑧𝑤, 𝑧𝑝, 𝑠𝑤, 𝑠𝑥}
Como en los conjuntos normalmente no ponemos los elementos que se repiten, si una arista
tiene sus dos extremos en un mismo vértice (como pasaba en las relaciones que eran reflexivas,
aunque, de nuevo, ahora no nos importa el orden), la arista sería de la forma: 𝑒 = {𝑥, 𝑥} por
lo que se escribe directamente 𝑒 = {𝑥}, 𝑥 ∈ 𝑉. En ese caso, decimos que tenemos un bucle
(en inglés: Loop)
13
Cuando hablamos de Multiconjunto, vamos a entender que es lo mismo que lo que habíamos visto
como conjunto, solo con una diferencia y es que, en un multiconjunto, los elementos pueden repetirse.
Prof. Julieta Matteucci 92
UNPAZ – LGTI (6004)
2024
Estructuras Discretas
Importante: Por convención y salvo que se indique lo contrario, a fines de esta materia (y de
este apunte), cuando se mencione un grafo, vamos a suponer que no es nulo y que es finito.
Dos vértices 𝑢 y 𝑣 de un grafo son adyacentes (o cada uno es vecino del otro) si ambos son
extremos de una misma arista. En este caso escribimos 𝑢 ↔ 𝑣. La cantidad de aristas incidentes
a un vértice 𝑣 es llamada el grado de 𝑣, y lo denotamos 𝑔𝑟𝑎𝑑𝑜(𝑣) o 𝑔𝑟(𝑣).
∑ 𝑔𝑟𝑎𝑑𝑜(𝑣) = 2|𝐸|
𝑣∈𝑉
El símbolo Σ significa sumatoria. Es decir que lo que se escribió recién se lee como: “La suma
del grado de todos los 𝑣 en 𝑉 (es decir, todos los vértices), es igual al doble de la cantidad de
elementos del conjunto 𝐸 (es decir, la cantidad de aristas)”
Por ejemplo:
𝑉(𝐺) = {𝑥, 𝑦, 𝑧, 𝑤, 𝑝, 𝑠}
𝐸(𝐺) = {𝑥𝑦, 𝑧𝑤, 𝑧𝑝, 𝑠𝑤, 𝑠𝑥}
Entonces:
∑ 𝑔𝑟𝑎𝑑𝑜(𝑣) =
𝑣∈𝑉
En caso de los multigrafos o con bucles, pasa lo mismo, solo que en los bucles, se cuentan los
dos extremos de la arista que forma el
rulo:
Entonces:
∑ 𝑔𝑟𝑎𝑑𝑜(𝑣) =
𝑣∈𝑉
Un vértice que no tiene vecinos se dice aislado. Así, por ejemplo, un grafo es trivial si y sólo si
todos sus vértices son aislados
Se que estamos viendo muchas definiciones que, cada una es bastante simple, pero en el
montón pueden llegar a marear. Por eso les sugiero que se vayan haciendo un resumen de cada
una de estas definiciones, porque hay más. Así las tienen a mano.
Es habitual, en las diferentes industrias, hacer agujeros en hojas de metal o soldar ciertos puntos
metálicos en una placa. En general, este tipo de tareas se lleva a cabo con algún brazo robótico
controlado por una computadora, que sea
el encargado de taladrar o soldar los El más grande de los grandes14
puntos requeridos. Como en la mayoría de
los casos “el tiempo es dinero”, por lo que Leonhard Euler es el matemático más prolífico de la historia.
el brazo robotico debe moverse tan rápido Uno de los más creativos y que abordó problemas
matemáticos con ingenio, variedad y profundidad. Nació en
como sea posible. Otro problema similar Basilea, un pueblito de Suiza en
es el de un camion de reparto que debe 1707, en una familia muy pobre,
pasar por distintos puntos para hacer pero con una mente millonaria.
entregas, para ahorrar en tiempo y Consiguió entrar a la
universidad cuando tenía 13
combustible, también se busca que el años y a los 16 ya tenía un
camino que recorra el camión (al igual que master en filosofía (en su tesis
el recorrido del brazo robótico) sea el que comparo los sistemas
15 filosóficos de Newton con los de
minimice el tiempo necesario . Este tipo Descartes). Su padre era
de situaciones, se modela con grafos. pastor de iglesia y quería que el
joven Leonhard se dedicara a la
Los vértices del grafo corresponden a las teología como él, pero uno de sus amigos que trabajaba en
posiciones por las que se debe pasar (lugar la universidad (Johann Bernoulli) lo convenció de que lo
donde se debe perforar / soldar o por dejara estudiar matemática con sus propios hijos y así el
mundo terminó ganando a este matemático. Le
dónde se hace una entrega). Cada par de consiguieron un trabajo en San Petersburgo y ahí, Euler
vértices se conecta por una arista. En cada superó todas las expectativas y empezó a producir
arista se escribe el tiempo para mover el matemática de un nivel altísimo a un ritmo jamás antes visto
brazo robótico o la distancia que separa y que nunca decayó. A los 28 años enfermó y esto junto con
sus trabajos de cartografía y de estudios del sol, colaboraron
esos dos puntos. Un grafo con números en para que perdiera la vista en el ojo derecho y, unos años
las aristas, se llama grafo ponderado y al después la del izquierdo. Durante los últimos 20 años de su
número que aparezca en la arista, se lo vida, estuvo ciego, pero ese detalle no consiguió detener
llama peso de la arista. Una ruta de su carrera matemática. Gracias a su grandiosa memoria y
su capacidad innata para el cálculo mental, pudo seguir con
longitud mínima que visita todos los sus estudios de matemática dictando a sus colaboradores y
vértices exactamente una vez representa a su hijo mayor todos sus hallazgos. Fue tan prolífico que
la ruta óptima que debe seguir el brazo 50 años después de su muerte, aun se seguían publicando
robótico o el camión. trabajos originales de él ya que la academia de ciencias no
alcanzaba a publicar al ritmo que lo que producía. No
alcanza, ni este margen, ni el apunte completo, para plasmar
su grandeza.
14
Por supuesto, esta es una opinión completamente objetiva.
15
Para el caso del camión de reparto, vamos a ignorar factores que intervienen en el tiempo del recorrido,
como son tráfico, manifestaciones y cuestiones climáticas.
Prof. Julieta Matteucci 95
UNPAZ – LGTI (6004)
2024
Estructuras Discretas
Por ejemplo:
1 0 1 0 0
1 2 2 0 1 𝐶 es una matriz de 5
𝐶= 0 1 3 0 1 filas y 5 columnas, es
0 1 3 2 0
decir de 5 × 5
(0 1 1 2 1)
Cada posición en una matriz viene dada por 2 números, como si fueran coordenadas. El primero
de los números indica la fila (contando de arriba hacia abajo) y el segundo indica la columna (de
izquierda a derecha). Así, por ejemplo decimos que 𝐴(3,2) = 7 lo que quiere decir que en la
posición “fila 3, columna 2” de la matriz 𝐴, hay un 7. Otros ejemplos de las matrices anteriores:
𝐵(5,3) = 0
𝐶(4,4) = 2
Las matrices son super útiles en programación ya que nos permiten guardar 3 datos en un solo
lugar: El valor que ponemos en una posicion, el número de la fila, el número de la columna. Por
Prof. Julieta Matteucci 96
UNPAZ – LGTI (6004)
2024
Estructuras Discretas
ejemplo, los programas que trabajan con fotos e imágenes, toman a las imágenes como
matrices. Cada pixel es una posición en la matriz donde guardan el código del color que
corresponde a ese pixel. Así, la manipulación de imágenes se reduce a operar
“matemáticamente” con matrices.
En computación, muchas de las cosas que utilizamos, se manejan con un sistema binario
compuesto por 0 y 1. En general, el 0 significa “no” o “falso” y el 1 significa “si” o “verdadero”.
Incluso en los circuitos, el 1 y el 0 se traducen en “pasa corriente” o “no pasa corriente” por
cierto lugar.
Cuando hablamos de grafos, la idea es similar. Tenemos que dar una manera de definir o de
representar un grafo con algo que no sea el dibujito. Nos vamos a valer de la misma lógica de 0
y 1.
Por ejemplo:
𝟓
0 1 0 0 0 0
𝟔
𝟏 1 0 1 0 0 0
𝟑 𝐴= 0 1 0 1 0 0
0 0 1 0 1 0
0 0 0 1 0 1
𝟒 (0 0 0 0 1 0)
𝟐
𝟑 0 1 0 0 0 0 0
𝟏 𝟐 1 0 0 1 0 0 1
𝟓 0 0 0 0 1 1 0
𝟔 𝐴= 0 1 0 0 1 1 1
0 0 1 1 0 1 0
𝟒 0 0 1 1 1 0 0
(0 1 0 1 0 0 0)
𝟕
En el caso de los grafos no dirigidos, las matrices de adyacencia son simétricas, es decir que si
en la posición (𝑖, 𝑗) hay un 1, quiere decir que hay una arista que une esos dos vértices, por lo
que también habrá un 1 en la posición (𝑗, 𝑖). En el caso de los grafos dirigidos, como nos importa
el orden, entonces, en la posición (𝑖, 𝑗) habrá un 1 si hay una flecha que va del vértice 𝑖 al 𝑗. Pero
en la posición, (𝑗, 𝑖) no necesariamente tendrá un 1, eso dependerá si hay o no, una flecha que
va del vértice 𝑗 al 𝑖 .
Importante: Existe una matriz de adyacencia única para cada grafo (dígrafo) (sin considerar las
permutaciones de filas o columnas, en el caso de los grafos, ya que dependen del orden que le
asignemos), y viceversa
En los grafos no dirigidos, al sumar cada fila o cada columna se obtiene el grado de cada vértice,
salvo el caso de una arista bucle a la cual le corresponde uno en la matriz de adyacencia pero su
grado es 2.
En el caso de los grafos no dirigidos, cada columna, entonces, siempre sumará 2 ya que
representa una arista, y cada arista solo une dos vértices, salvo que se trate de un bucle (ahí
sumará 1. Además, la suma de los elementos de cada fila, al igual que en la matriz de adyacencia,
dará el grado del vértice.
Por ejemplo: En cada uno de los siguientes grafos, se les agregó un nombre (numerado) a las
aristas, para identificarlas en la matriz. Así, la primer columna, corresponde a la arista 𝑎1 , la
segunda a 𝑎2 y así sucesivamente.
𝟓 𝒂𝟓
1 0 0 0 0
𝟔
𝟏 1 1 0 0 0
𝟑 𝒂𝟑
𝒂𝟒 𝐴= 0 1 1 0 0
0 0 1 1 0
𝒂𝟏 0 0 0 1 1
𝒂𝟐 𝟒 (0 0 0 0 1)
𝟐
𝟑
𝟏 𝒂𝟏 𝒂𝟗
𝟐 𝒂𝟏𝟎 1 0 0 0 0 0 0 0 0 0
𝟓 𝒂𝟖 1 1 0 0 0 1 0 0 0 0
𝒂𝟐 𝟔 0 0 0 0 0 0 0 0 1 1
𝒂𝟑
𝐴= 0 1 1 1 1 0 0 0 0 0
𝒂𝟒 𝒂𝟔 0 0 1 0 0 0 0 1 1 0
𝟒
0 0 0 1 0 0 0 1 0 1
𝒂𝟓 𝟕 (0
𝒂𝟕 0 0 0 1 1 1 0 0 0)
Dicho de otra forma, un grafo será conexo si todos sus vértices están conectados por un camino,
en caso contrario es disconexo.
𝒅
𝒆
En el año 1994, el actor Kevin Bacon, dijo en una
entrevista que había trabajado en tantas películas que,
o si agarraban a cualquier actor o actriz de Hollywood,
él, o había trabajado directamente con ese actor o actriz es un grafo conexo, ya que no importa qué par
o había trabajado con alguien que había trabajado con de vértices o nodos elija, siempre se puede
ese actor o actriz. Entonces, unos estudiantes encontrar un camino de uno al otro.
universitarios decidieron probar esto, y tomando como
base la página IMDB.com (Internet Movie Data Base), Hay una teoria que dice que cualquier par de
elaboraron el “número de Bacon” que es el menor
personas en el mundo estan conectadas entre
número que conecta a cualquier actor con Kevin
Bacon. La actriz argentina Norma Aleandro, por sí por hasta 6 grados de separación. En
ejemplo, tiene número de Bacon de 2. Ella trabajó en la términos de grafos, significa que, si
película "Vital Signs" de 1990 con Diane Lane. Que a su hicieramos un super mega archi gran grafo
vez trabajó en la película "My Dog Skype" de 2000 con
Kevin Bacon. Podría existir un camino alternativo que
con todas las personas del mundo y las aristas
pase por 3 actores. Pero el camino 2 seguiría siendo la indican que dos vertices (o sea, dos personas)
distancia menor y es por eso que también se lo conoce se conocen, esta teoria dice que cualquier
como camino mínimo. Otro ejemplo, Lali Espósito, tiene camino entre un par de personas de ese mega
número de Bacon 3, porque trabajó en 2018 en
“Acusada” con Gael García Bernal, quien trabajó en grafo tiene grado 6 o menos. Esto supone,
2008 en “Fidel” con Tony Plana quien trabajó en “JFK”, por ejemplo, que ese super grafo, es conexo,
en 1991, con “Kevin Bacon”. Se puede encontrar el porque si hubiera alguna población en el
número de Bacon en https://oracleofbacon.org/ y, si planeta, que esté completamente aislada, y
quieren un poco más de información del número de
Bacon y de otras versiones de la teoría que nadie conozca, entonces eso no sería
de los 6 grados de separación, pueden posible, ya que esa población, no estaría
ver este video que pueden acceder conectada con ninguna persona del mundo.
desde el QR o haciendo click en el link
de la palabra “video”. Un ejemplo de un grafo disconexo, sería:
La idea de los subgrafos es análoga a la de subconjuntos, ya que como los grafos se definen
como conjuntos, los subgrafos pasan a ser subconjuntos de los conjuntos de vértices y aristas.
En este ejemplo, si al grafo global disconexo, lo llamamos 𝐺, y a los dos grafos conexos 𝐺1 y 𝐺2 ,
decimos que 𝐺1 ⊂ 𝐺 y que 𝐺2 ⊂ 𝐺 . No hace falta que el grafo sea disconexo para tener
subgrafos, ya que se definen solo con la idea de subconjuntos y no tienen la condición de que
sean o no conexos. Así, podríamos definir el subgrafo: 𝐺3 = {𝑉3 , 𝐸3 } definido por los conjuntos
𝑉3 = {1,2,3,4,5,6}, 𝐸3 = {{1,2}, {1,4}, {2,4}, {3,5}} que gráficamente es:
𝟑
𝟏 𝟐
𝟓
𝟔
Este es un subgrafo del anterior, que tambíen resultó disconexo (y hasta tiene un nodo aislado).
Un grafo 𝐻, se dice que es un subgrafo de 𝐺, si todos los vértices y todas las aristas de 𝐻 están
en 𝐺 y cada arista de 𝐻 tiene el mismo vértice final en 𝐻 como en 𝐺.
Obviamente al considerar un subgrafo, el grafo original no debe ser alterado al identificar los
vértices ni agregando nuevas aristas o vértices. Observemos que:
Ejercicios
1) Dibuja los grafos, especificando el tipo de grafo que utilizas, que representen las rutas
aéreas diarias de Aerolíneas Argentinas sabiendo que ofrece los siguientes vuelos
diarios: tres vuelos que unen Buenos Aires y Córdoba, dos entre Córdoba y Mendoza,
uno entre Mendoza y Neuquén, cuatro entre Neuquén y La Pampa, uno entre La Pampa
y Buenos Aires, uno entre Mendoza y Córdoba y uno entre La Pampa y Córdoba, de
modo que:
a. Hay una arista conectando cada par de vértices que representan ciudades para
las que hay algún vuelo de la una a la otra (en cualquiera de los dos sentidos).
b. Hay una arista conectando dos ciudades por cada vuelo que opere entre las dos
ciudades ( en cualquiera de los dos sentidos)
c. Hay una arista que sale de cada vértice asociado a una ciudad de la que despega
algún vuelo y que llega al vértice correspondiente a la ciudad en que aterriza el
vuelo.
d. Hay una arista por cada vuelo, que sale del vértice que representa a la ciudad
en que se inicia el vuelo y llega al vértice que representa a la ciudad en que
aterriza.
2) Para el grafo realizado en el ítem a) del punto anterior, agregarle la información de las
distancia entre ciudades. Puedes buscar la información en Google o, si no tienes acceso,
inventa el número.
4) ¿Cuáles de los siguientes grafos son simples? Para los grafos no simples, ¿Cuál es el
menor número de aristas que se deben quitar para hacerlos simples?
a) b)
𝟏 𝟐
𝟏
𝟐
𝟓 𝟓
𝟑
𝟑
𝟒
𝟒
c) d)
𝒃
𝒃 𝟔
𝟑
𝒅
𝟏 𝟐 𝟒 𝟒 𝟐
𝟑 𝟔
𝒄
𝒄
𝟓
𝒅 𝒂
𝒂 𝟓
5) Para los grafos de los ejercicios 3) y 4), armar la matriz de adyacencia e indicar qué grado
tiene cada vértice.
6) Para los grafos no dirigidos de los ejercicios 3) y 4), armar la matriz de Incidencia e indicar
qué grado tiene cada vértice.
9) ¿Cuál es el grado de cada uno de los grafos de los ejercicios 7 y 8? ¿Son conexos o
disconexos?
El formalismo de la definición significa que se parte del vértice 𝑣0 , se sigue la arista 𝑎1 hasta 𝑣1 ,
se sigue la arista 𝑎2 hasta 𝑣2 y así sucesivamente.
Uniendo estas dos definiciones, podemos definir, también, un circuito simple o ciclo simple a
esos circuitos que no repiten vértices salvo el caso trivial 𝑣𝑜 = 𝑣𝑛 (es decir, cuando el vértice
inicial, coincide con el final)
Estos conceptos son los mismos para grafos dirigidos, salvo que las direcciones de las aristas
deben concordar con la dirección del camino. Además, en el caso dirigido el ciclo recibe el
nombre de circuito.
Ejemplos de esto
El camino:
𝟑
(6, 𝑒7 , 5, 𝑒5 , 2, 𝑒4 , 4, 𝑒3 , 3, 𝑒2 , 2, 𝑒1 , 1)
𝒆𝟐
𝟐 𝒆𝟑
𝒆𝟒 No es un camino simple, dado que pasa
𝟒 dos veces por el vértice 2. Además, como
𝒆𝟏 el vértice inicial y el final no coinciden, no
𝒆𝟔 es un circuito ni ciclo.
𝒆𝟓
𝟏 𝒆𝟖 𝟕 Importante: En el caso de los grafos que
𝒆𝟕 no son multigrafos, como hay una única
𝟓 𝟔
arista entre dos nodos, se puede indicar el
camino, diciendo solamente los vértices que lo componen. En ese sentido, el camino de este
ejemplo podría haberse escrito: (6, 5, 2, 4, 3, 2, 1).
Para el mismo grafo, pensemos en el camino dado por (6, 5, 2, 4). En este caso sí tenemos un
camino simple, ya que ningún vértice se repite, pero como el vértice inicial y el final no coinciden,
no es un circuito ni ciclo.
Nuevamente, mirando el mismo grafo, pensemos en el camino dado por (2, 6, 5, 2, 4, 3, 2). En
este caso no tenemos un camino simple, ya que el vértice 2 se repite. Sin embargo, como el
vértice inicial y el final coinciden forma un ciclo, aunque, como repitió el 2, el ciclo no es simple.
Si tomáramos, el camino: (5, 6, 2, 5), vemos que no es un camino simple (por repetir el 5) pero,
como el que se repite es solo el inicial con el final, entonces, es un ciclo y, más aun, es un ciclo
simple.
En el caso en el que se tomara un camino solo compuesto por un vértice sin aristas, este sería
un camino simple, pero no un ciclo.
Bueno, creo que, después de esta pequeñísima introducción a la teoria de grafos, ya estamos en
condiciones de pensar, seriamente, el problema de los puentes de Königsberg.
Esto no quiere decir que no lo podíamos pensar antes, sin tanta definición. Es posible. La
diferencia, ahora, es que tenemos suficientes conceptos como para que nuestro
razonamiento y nuestras justificaciones queden bonitas.
En el último avance que habiamos hecho, llegamos a modelizar el problema con este grafo:
𝒃 𝒅
¿Qué pasa con los vértices extremos? Si los extremos no coinciden (o sea, el camino no es un
circuito) entonces la primera salida desde el vértice inicial no es compensada por ninguna
entrada. De la misma forma, la última entrada en el vértice final no es compensada por ninguna
salida.
Así, si el camino no es un circuito, los vértices inicial y final deben tener grado impar. Si el camino
es un circuito, la primera salida y la última entrada se compensan mutuamente, y el vértice
inicial/final tiene grado par, igual que los otros vértices.
¿Qué significa todo esto? Que no hay forma de hacerlo, porque si fuera un circuito, todos los
grados deberían ser pares, y si no es un circuito, solo 2 de los vértices deberían tener grado
impar, mientras que el resto, par. Como todos los nodos del problema de los puentes tienen
grado impar, es imposible recorrerlos sin pasar dos veces por un mismo puente.
Definición: 𝐺 tiene un circuito Euleriano si existe un circuito en 𝐺 que recorra cada arista
del grafo exactamente una vez.
Es decir que un circuito euleriano es un camino que empieza y termina en el mismo vértice, pasa
por cada vértice al menos una vez y sólo una vez por cada arista.
Si existe un camino no cerrado de 𝑎 a 𝑏 en 𝐺 que recorre cada arista de 𝐺 exactamente una vez,
este camino se llamará camino Euleriano.
• 𝐺 es conexo
• Todos los vértices de 𝐺 tienen grado par.
Importante: Si 𝐺 tiene un vértice de grado impar, en 𝐺 no puede existir un ciclo de Euler, pero
podría ser posible determinar un camino de Euler.
Entonces, cualquier camino de Euler, debe comenzar en un vértice de grado impar y terminar
en el otro. Si 𝐺, tiene más de dos vértices de valencia impar, no existe un camino de Euler en 𝐺.
Ejemplo:
Decidir si las siguientes figuras se pueden dibujar sin levantar el lápiz, es decir con un solo trazo:
En el caso de la primera de las figuras, sí se puede, ya que es un grafo que solo tiene dos vértices
de grado impar, por lo que podemos arrancar de cualquiera de esos dos y hacer un recorrido
cerrado que pase una vez por cada arista. Sin embargo, en el
segundo caso, no hay ciclo Euleriano ya que hay 4 vértices que
tienen grado 5. Es decir que, en cada uno de esos vértices alguna
línea debe empezar o terminar, y como son 4, mínimo se requerirían
2 trazos.
Sean 𝐺1 = {𝑉1 , 𝐸1 } y 𝐺2 = {𝑉2 , 𝐸2 } grafos simples se dicen isomorfos si y sólo sí existe una
función biyectiva 𝑓: 𝑉1 → 𝑉2 tal que ∀𝑒𝑖 = {𝑣𝑗 , 𝑣𝑘 } ∈ 𝐸1 𝑐𝑜𝑛 𝑣𝑗 , 𝑣𝑘 ∈ 𝑉1 , la arista formada por
las imágenes de los vértices, 𝑒 = {𝑓(𝑣𝑗 ), 𝑓(𝑣𝑘 )} ∈ 𝐸2
Por lo tanto, hay una función biyectiva entre los vértices de los dos grafos que preserva la
relación de adyacencia. 𝐺1 y 𝐺2 se denominan isomorfos, y son matemáticamente iguales,
solo varía la apariencia, o sea, que se mantienen las adyacencias, estructura, caminos y ciclos,
por lo tanto, deben tener las mismas propiedades y características.
Ambos grafos han de tener el mismo número de vértices y el mismo grado de cada uno. Si, por
ejemplo, en un grafo tenemos un vértice de grado 7 y en el otro no, no podrán ser isomorfos.
Cada vértice ha de mantener sus relaciones de vecindad. De todas formas, esto no alcanza,
pero es un requisito. Además, y como sabemos que en todo grafo la suma de los grados coincide
con (dos veces) el número de aristas, deducimos que dos grafos isomorfos han de tener el mismo
número de aristas.
Ejemplo
𝒂 𝒃 𝟏
𝟐 𝟒
𝟑
𝒄 𝒅
Estos dos grafos son isomorfos. Son isomorfos pues existe la biyección 𝑓: 𝑉1 → 𝑉2 definida por
𝑓(𝑎) = 2
𝑓(𝑏) = 1
𝑓(𝑐) = 3
𝑓(𝑑) = 4
que conserva la adyacencia ya que los vértices que están unidos entre sí siguen unidos después
de aplicar la función, mientras que los que no están unidos (por ejemplo, el 𝑐 con el 𝑏) siguen
sin estar unidos tras aplicar la función: (por ejemplo, el 𝑓(𝑐) con el 𝑓(𝑏), es decir, el 3 con el 1)
Otro ejemplo
Estos dos grafos no son isomorfos. Aunque ambos tienen seis vértices, cinco aristas y su vértices
tienen los mismos grados es (1, 1, 1, 2, 2,3). Sin embargo, no son isomorfos porque, por ejemplo,
el vértice de grado 3 es, en un caso, vecino de dos de grado 1 y de uno de grado 2; y en el otro,
de uno de grado 1 y de dos de grado 2.
Dos grafos 𝐺1 y 𝐺2 son isomorfos si y sólo si para cierto orden de sus vértices las matrices de
adyacencia son iguales
Un ejemplo
𝑨
𝒆 𝒂𝟏
𝒆𝟏 𝒂𝟐
𝒆𝟐 𝑪 𝒂𝟒 𝑫
𝒆𝟓 𝒃 𝒂𝟓
𝒂
𝒆𝟑
𝒅 𝒂𝟑
𝒆𝟒 𝒄 𝑬 𝑩
1 1 0 0 0 1 1 0 0 0
0 1 1 0 0 0 1 1 0 0
𝐴1 = 0 0 1 1 0 𝐴2 = 0 0 1 1 0
0 0 0 1 1 0 0 0 1 1
(1 0 0 0 1) (1 0 0 0 1)
Un árbol es un tipo especial de grafo. Es un grafo donde entre cualquier par de nodos existe
un único camino que los conecta (notar que, en particular, todos los nodos tienen que estar
conectados entre sí). Es decir, son grafos, dirigidos y no dirigidos, conexos y acíclicos
Observen que, lo que se definió muuuuuy elementalmente cuando arrancamos a contar sin
contar, verifica esta definición.
• 𝐺 es conexo y todas sus aristas son puentes. Al eliminar cualquier arista 𝐺 quedará
desconectado en dos subgrafos que serán árboles.
• 𝐺 es acíclico; la adición de una arista nueva origina un ciclo.
• 𝐺 es acíclico y la cantidad de aristas es igual a la cantidad de vértices menos uno:
|𝐴| = |𝑉| − 1
Por ahora nos detenemos. Los grafos y los árboles, son tremendamente útiles en la informática
porque permiten organizar la información y secuenciar ideas y programas.
Son muchas ideas que, en principio pueden parecer sueltas, pero si hacen un resumen y se
organizan, no solo no se van a confundir con las ideas sino que van a tener sentido.
Hacer una infografía resumiendo el tema de Grafos. Pueden hacerla en grupos de 2 o 3 (no más)
y súbanla al foro correspondiente. Una infografía es un resumen, pero con imágenes y no tanto
texto. Es como si hicieran un poster, afiche o cartulina. Pero lo fuerte de la infografía es la parte
visual y gráfica.
Pueden hacerla en cualquier programa que quieran o, si no tienen la posibilidad de usar una
compu, a mano y luego suben la foto.
Ejercicios
1) Para el siguiente grafo 𝐺 ,
𝒃 𝒆𝟒 𝒆
determinar: 𝒆𝟖
a. Un camino simple de 𝑏 a 𝒆𝟏 𝒈
𝒆𝟕
𝑑. 𝒂 𝒆𝟑 𝒆𝟔 𝒆 𝟗
𝒇
b. Un camino no simple de 𝑏 𝒆𝟐 𝒆𝟓
a𝑑
c. Un ciclo simple de 𝑏 a 𝑏. 𝒄 𝒅
d. Un ciclo no simple de 𝑏 a
𝑏.
e. Todos los caminos simples de 𝑏 a 𝑓.
f. Sabiendo que la distancia de 𝑥 a 𝑦 en un grafo no dirigido conexo 𝐺 es la longitud
de camino más corto de 𝑥 a 𝑦, hallar la distancia desde 𝑑 a los restantes vértices de
𝐺.
4) Para cada uno de los siguientes esquemas, decidir si es posible hallar un ciclo o un
camino Euleriano:
c.
b.
a.
e. g.
d.
f.
9) Dado el grafo 𝐺 con matriz de adyacencia 𝑀, indicar, justificando, cuál o cuáles de las
siguientes afirmaciones son verdaderas:
1 2 1 2
𝑀 = (2 0 0 1)
1 0 0 1
2 1 1 0
a)
b)
c)
Un mundo de soluciones…
Antes que te emociones, te recuerdo que las soluciones que aquí aparecen pueden no servirte
de nada. Todo depende del uso que le des. Si vas a venir al poco tiempo de arrancar con algún
ejercicio, seguro que no te van a servir. Esto es solo una lista de respuestas, no te dice cómo se
resuelven ni reemplaza las consultas a tus compañeros, compañeras y profe. Además, en
algunos de los ejercicios la solución NO es única, esto quiere decir que la respuesta que aquí
aparece podría no ser la misma a la que vos llegaste, pero no por eso estar mal.
Algunas cosas que no vas a encontrar acá: No vas a encontrar ninguna de las respuestas que
vengan del texto, de la parte donde se piensan las cosas, las respuestas que están acá son de las
listas de ejercicios, no de la parte global. Tampoco vas a poder encontrar acá los ejercicios que
involucren demostrar algo. Eso corre por tu cuenta. No tiene sentido ponerlos acá.
Los ejercicios 1 y 2 refieren a las mismas proposiciones. No te voy a dejar las tablas de verdad,
pero sí algo que te permita revisar algunas cosas, es decir, los resultados del 2do ejercicio.
1) Propiedad Utilizada:
a. Distributiva
b. Ley de DeMorgan
c. Equivalencia de la disyunción
d. Equivalencia de la conjunción
e. Asociativa y Conmutativa
f. Distributiva
2) Este es un ejercicio bastante libre, por lo que no hay solución única.
En estos ejercicios se trata de verificar que son equivalentes, es decir, es algo que tenés que
demostrar. Por lo que no encontrarás solución acá.
UNIDAD: Conjuntos
Ejercicios:
Ejercicios:
c) Indicar, justificando en todos los casos, cuáles de las siguientes afirmaciones son
verdaderas y cuáles falsas:
I. 𝐴 = 𝐵 Verdadero, porque no nos importa el orden
II. 1 ∈ 𝐶 Falso, porque 2(1)2 − 7 ⋅ 1 + 3 = −2 ≠ 0
1
III. 2
∈𝐶 Falso porque no es un número entero
IV. |𝐷| = 3 Falso, tiene dos elementos, el 3 y el conjunto {0,1}
1
V. |𝐶| = 2 Falso, porque si bien las raíces de la cuadrática son { , 3}, solo el
2
3 es entero, por lo que la cantidad de elementos de 𝐶 es 1.
VI. 𝐶 ⊂ 𝐷 Verdadero.
VII. 𝐶 ∈ 𝐷 Falso, el conjunto 𝐶 = {3} no es un elemento de D (el elemento 3,
sí, pero el conjunto, como elemento, no)
d) Dar, por extensión los conjuntos 𝒫(𝐴), 𝒫(𝐶) y 𝒫(𝒫(𝐶))
En este ejercicio hay muchas respuestas posibles, así que acá se muestran algunas…
del ítem a)
𝐴 6
3 8 𝐵
0 1
5 9
4 2 7
𝑈
del ítem b) 𝐴
1 2
0
3 6 8
𝐶 𝐵
5 9
4 7
𝑈
del ítem c) 𝐴
1 𝐵
2 5
8
0 6
3 9
𝐶 4 7
𝑈
del ítem d) 𝐴
1 1 𝐵 12 5
2 5 2 5
8 8 8
0 6 0 6 𝐶 0 6
3 9 4
3
7
9 3 7 9
4 7 4
𝑈 𝑈 𝑈
7) Este ejercicio
a. 𝐴 ∪ (𝐵 ∩ 𝐶) b. 𝐴 ∩ (𝐵 ∪ 𝐶)
c. 𝐴𝑐 ∪ (𝐵 − 𝐶) d. (𝐴 ∪ 𝐵) − (𝐴 ∩ 𝐵)
𝑐
e. ((𝐴 ∪ 𝐵) − (𝐴 ∩ 𝐵)) f. 𝐶 − (𝐵 ∩ 𝐶)
𝑐
g. (𝐴 ∪ 𝐵 ∪ 𝐶) − (𝐴 − (𝐵 ∪ 𝐶)) h. (𝐶 − (𝐵 ∪ 𝐴))
i. (𝐴 ∩ 𝐵) ∪ (𝐶 ∩ 𝐵) ∪ (𝐴 ∩ 𝐶) j. (𝐵 − 𝐶) ∪ (𝐶 − 𝐵)
8) Nuevamente, acá hay muchas respuestas posibles. Estas son solo algunas de las
opciones. En muchos de los casos, se pueden encontrar otras operaciones que den el
mismo resultado, por ejemplo, operando con las propiedades:
a. 𝐴 − (𝐵 ∪ 𝐶)
b. (𝐴 ∪ 𝐵 ∪ 𝐶) − [(𝐴 ∩ 𝐵) ∪ (𝐶 ∩ 𝐵) ∪ (𝐴 ∩ 𝐶)]
c. (𝐴 ∩ 𝐵) ∪ (𝐶 ∩ 𝐵) ∪ (𝐴 ∩ 𝐶)
d. [(𝐴 ∪ 𝐵 ∪ 𝐶) − [(𝐴 ∩ 𝐵) ∪ (𝐶 ∩ 𝐵) ∪ (𝐴 ∩ 𝐶)]] ∪ (𝐴 ∩ 𝐵 ∩ 𝐶)
e. (𝐴 ∩ (𝐵 ∪ 𝐶)) − (𝐵 ∩ 𝐶)
f. (𝐴 ∪ 𝐵 ∪ 𝐶)𝑐 ∪ (𝐴 ∩ 𝐵 ∩ 𝐶)
g. [(𝐴 ∩ 𝐵) ∪ (𝐶 ∩ 𝐵) ∪ (𝐴 ∩ 𝐶)]𝑐
h. (𝐵 ∪ 𝐶)𝑐 ∪ [(𝐵 ∩ 𝐶) − 𝐴]
Aunque sean ejercicios para demostrar, como ya pasamos la unidad de lógica, en la que
aprendieron la primer tanda de demostraciones, les dejo acá algunas posibles secuencias de
pasos que permitan demostrar lo pedido. Revisá la forma en la que están escritas, así se espera
que lo escribas en el parcial.
b. 𝐴 ∪ 𝐵 = (𝐴 ∩ 𝐵𝑐 ) ∪ 𝐵
𝑃𝑜𝑟 𝐿𝑒𝑦 𝑑𝑖𝑠𝑡𝑟𝑖𝑏𝑢𝑡𝑖𝑣𝑎:
(𝐴 ∩ 𝐵𝑐 ) ∪ 𝐵 = (𝐴 ∪ 𝐵) ∩ (𝐵 ∪ 𝐵𝑐 )
𝑃𝑜𝑟 𝐿𝑒𝑦 𝑑𝑒𝑙 𝑐𝑜𝑚𝑝𝑙𝑒𝑚𝑒𝑛𝑡𝑜:
(𝐴 ∪ 𝐵) ∩ (𝐵 ∪ 𝐵𝑐 ) = (𝐴 ∪ 𝐵) ∩ 𝑈
𝑃𝑜𝑟 𝑙𝑒𝑦 𝑑𝑒 𝑖𝑑𝑒𝑛𝑡𝑖𝑑𝑎𝑑
(𝐴 ∪ 𝐵) ∩ 𝑈 = 𝐴 ∪ 𝐵
c. (𝐴 ∪ 𝐵𝑐 ) ∩ (𝐴𝑐 ∪ 𝐵) = (𝐴 ∩ 𝐵) ∪ (𝐴𝑐 ∩ 𝐵𝑐 )
𝑃𝑜𝑟 𝑐𝑜𝑛𝑚𝑢𝑡𝑎𝑡𝑖𝑣𝑖𝑑𝑎𝑑:
(𝐵 ∩ 𝐴 ) ∪ (𝐴 ∩ 𝐵) = (𝐴 ∩ 𝐵) ∪ (𝐴𝑐 ∩ 𝐵𝑐 )
𝑐 𝑐
d. (𝐴 ∪ 𝐵) − 𝐶 = (𝐴 − 𝐶) ∪ (𝐵 − 𝐶)
𝑃𝑜𝑟 𝑐𝑜𝑛𝑚𝑢𝑡𝑎𝑡𝑖𝑣𝑖𝑑𝑎𝑑
𝐶 ∩ (𝐴 ∪ 𝐵) = (𝐴 ∪ 𝐵) ∩ 𝐶 𝑐
𝑐
e. 𝐴 − (𝐵 − 𝐶) = (𝐴 − 𝐵) ∪ (𝐴 ∩ 𝐶)
f. (𝐴 ∪ 𝐵) ∪ (𝐴 ∩ 𝐵)𝑐 = 𝑈
UNIDAD: Relaciones
Ejercicios resueltos (de la pág. 47)
𝐴 × 𝐵 = {(𝑎; 1), (𝑎; 2), (𝑎; 3), (𝑎; 4), (𝑏; 1), (𝑏; 2), (𝑏; 3), (𝑏; 4), (𝑐; 1), (𝑐; 2), (𝑐; 3), (𝑐; 4),
(𝑑; 1), (𝑑; 2), (𝑑; 3), (𝑑; 4)}
b. Hallar 𝐵 × 𝐴
𝐵 × 𝐴 = {(1; 𝑎), (1; 𝑏), (1; 𝑐), (1; 𝑑), (2; 𝑎), (2; 𝑏), (2; 𝑐), (2; 𝑑), (3; 𝑎), (3; 𝑏), (3; 𝑐), (3; 𝑑),
(4; 𝑎), (4; 𝑏), (4; 𝑐), (4; 𝑑)}
c. Hallar 𝐴 × 𝐴
𝐴 × 𝐴 = {(𝑎; 𝑎), (𝑎; 𝑏), (𝑎; 𝑐), (𝑎; 𝑑), (𝑏; 𝑎), (𝑏; 𝑏), (𝑏; 𝑐), (𝑏; 𝑑), (𝑐; 𝑎), (𝑐; 𝑏), (𝑐; 𝑐), (𝑐; 𝑑),
(𝑑; 𝑎), (𝑑; 𝑏), (𝑑; 𝑐), (𝑑; 𝑑)}
d. Hallar 𝐵 × 𝐵
𝐵 × 𝐵 = {(1; 1), (1; 2), (1; 3), (1; 4), (2; 1), (2; 2), (2; 3), (2; 4), (3; 1), (3; 2), (3; 3), (3; 4),
(4; 1), (4; 2), (4; 3), (4; 4)}
d. (𝐴 × 𝐵) × 𝐶
En este caso, se suele escribir como terna ordenada (Aunque es válido escribir cosas
como ((−2; 1); 𝑎) es más común escribirlo directamente como (−2; 1; 𝑎))
𝐴 × 𝐵 × 𝐶 = {(−2; 1; 𝑎), (−2; 2; 𝑎), (−2; 3; 𝑎), (−1; 1; 𝑎), (−1; 2; 𝑎), (−1; 3; 𝑎),
(−2; 1; 𝑏), (−2; 2; 𝑏), (−2; 3; 𝑏), (−1; 1; 𝑏), (−1; 2; 𝑏), (−1; 3; 𝑏)}
e. (𝐴 × 𝐴) × 𝐴
(𝐴 × 𝐴) × 𝐴 = {(−2; −2; −2), (−2; −2; −1), (−2; −1; −2), (−2; −1; −1),
(−1; −2; −2), (−1; −2; −1), (−1; −1; −2), (−1; −1; −1)}
13) Sea 𝐴 = {𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓, 𝑔, ℎ}. Para cada uno de los siguientes gráficos de una relación
sobre A, determinar si es reflexiva, simétrica, antisimétrica o transitiva.
a. Para que sea reflexiva, hay que agregar “bucles” en los 4 elementos que no lo tengan:
(𝑏; 𝑏), (𝑐; 𝑐),(𝑑; 𝑑), (𝑓; 𝑓).
b. Para que sea simétrica, hay que agregar un solo par: el par (𝑐, 𝑏).
c. Para que sea transitiva, hay que agregar un solo par, el (𝑑, 𝑑). Esto se debe a que están
los pares (𝑑, 𝑒) y (𝑒, 𝑑), pero no el que une el primero con el último, es decir (𝑑, 𝑑).
d. Para que sea reflexiva y simétrica hay que agregar los 4 pares requeridos en el punto a)
y el par del punto b), es decir 5 pares: (𝑏; 𝑏), (𝑐; 𝑐),(𝑑; 𝑑), (𝑓; 𝑓), (𝑐, 𝑏).
e. Para que sea simétrica y transitiva hay que agregar el par (𝑐, 𝑏) que me garantiza la
simetría y los bucles, (𝑏; 𝑏), (𝑐; 𝑐),(𝑑; 𝑑), para que se verifiquen las condiciones de
transitividad.
f. Para que sea reflexiva y transitiva hay que agregar 4 pares requeridos en el punto a) y
nada más, ya que eso alcanza para verificar la transitividad: (𝑏; 𝑏), (𝑐; 𝑐),(𝑑; 𝑑), (𝑓; 𝑓).
g. Para que sea de equivalencia, hay que agregar los 4 pares requeridos en el punto a) que
me garantizan que sea reflexiva, el par (𝑐, 𝑏) para la simetría y con eso alcanza para que
sea transitiva y, por lo tanto, de equivalencia.
Hago esquema para ayudarme (las líneas de punto indican que ese par no debe estar en ℛ):
Para que sea de equivalencia, necesito, primero, que sea reflexiva, por lo que agrego los pares:
(2; 2), (3; 3), (4; 4) , (5; 5) , (6; 6) , (7; 7) ,
𝟖
(8; 8), (9; 9) y (10; 10). Además, necesito
𝟏𝟎
que sea simétrica, es decir que por cada par
𝟐 𝟓
que pertenezca a la relación debe estar el
𝟗 𝟏
par opuesto, para eso agrego
𝟒
(3; 1), (2; 3), (5; 4), (6; 7), (10; 8), (10; 9)
𝟑
𝟕 Después de haberla hecha reflexiva y
simétrica me queda el siguiente dibujo:
𝟔
ℛ = {(1; 1), (1; 3), (3; 2), (4; 5), (7; 6), (8; 10), (9; 10), (2; 2), (3; 3), (4; 4), (5; 5), (6; 6),
(7; 7), (8; 8), (9; 9), (10; 10), (3; 1), (2; 3), (5; 4), (6; 7), (10; 8), (10; 9),
(1; 2), (2; 1), (8; 9), (9; 8)}
Prof. Julieta Matteucci 120
UNPAZ – LGTI (6004)
2024
Estructuras Discretas
16) En cada uno de los siguientes casos, determinar si la relación ℛ definida sobre 𝐴 es
reflexiva, simétrica, antisimétrica, transitiva, de equivalencia o de orden.
a. 𝐴 = {1,2,3,4,5}, ℛ = {(1; 1), (2; 2), (3; 3), (4; 4), (5; 5)}
b. 𝐴 = {1,2,3,4,5,6}, ℛ = {(1; 1), (2; 2), (3; 3), (4; 4), (5; 5)}
A diferencia del ítem anterior no es reflexiva porque no está el par (6; 6) pero sí es
simétrica, antisimétrica y transitiva. Al no ser reflexiva, no es ni de equivalencia, ni de
orden.
c. 𝐴 = {1,2,3,4,5}, ℛ = {(1; 1), (2; 2), (3; 3), (4; 4), (5; 5), (2; 3), (2; 4), (3; 5),
(2; 5)}
Habrá una flecha si la suma del primero con el doble del segundo es par. Entonces:
Esto se debe a que, del 4 y del 2 (los únicos pares del grupo) salen flechas a todos los elementos.
Generalizando lo del ítem anterior, si agregamos más números, (todos los naturales) va a pasar
lo mismo que en el ítem anterior. No será reflexiva, simétrica, ni antisimétrica. Sí será transitiva,
porque, de nuevo, todos los pares van a estar relacionados con todos los números, entonces,
para cualquier flecha que salga de un número par (𝑥) a otro número par (𝑦), va a garantizarse
que del 𝑥 van a salir flechas a todos los números (igual que con 𝑦)
𝟖 b. 𝐴 = ℤ . Determinar si la
𝟏𝟎 relación ℛ es reflexiva, simétrica,
antisimétrica, transitiva, de
equivalencia y/o de orden. Justificar
19) Dado el conjunto 𝐴 = {𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓 } definir una relación sobre 𝐴 que sea
simultáneamente
a. Simétrica y antisimétrica
ℛ = {(𝑎; 𝑎), (𝑏; 𝑏), (𝑐; 𝑐), (𝑑; 𝑑), (𝑒; 𝑒), (𝑓; 𝑓)}
b. De equivalencia y de orden
ℛ = {(𝑎; 𝑎), (𝑏; 𝑏), (𝑐; 𝑐), (𝑑; 𝑑), (𝑒; 𝑒), (𝑓; 𝑓)}
20) ¿Existe alguna relación sobre 𝐴 = {1,2,3,4,5,6} que no sea simétrica ni antisimétrica?
Ejercicios
11) Sean 𝐴 = {𝑎, 𝑏, 𝑐, 𝑑}, 𝐵 = {1,2,3,4} , se define el conjunto 𝑅 formado por los pares
{(𝑎; 1), (𝑏; 1); (𝑐; 2), (𝑑; 3)},
a. ¿Corresponde 𝑅 a una función? ¿Por qué?
Sí. Porque a cada elemento de 𝐴 le corresponde un único elemento de 𝐵
b. En caso de que la respuesta anterior fuera afirmativa, indicar Dominio,
Codominio e Imagen de la función. En caso de que no fuera función agregar o
Prof. Julieta Matteucci 123
UNPAZ – LGTI (6004)
2024
Estructuras Discretas
quitar la mínima cantidad de pares para que resulte una función y, de ésta,
indicar Dominio, Codominio e Imagen.
𝐷𝑜𝑚(𝑅) = {𝑎, 𝑏, 𝑐, 𝑑}
𝐶𝑜𝑑𝑜𝑚(𝑅) = {1,2,3,4}
𝐼𝑚(𝑅) = {1,2,3}
12) Sean 𝐴 = {𝑎, 𝑏, 𝑐, 𝑑}, 𝐵 = {1,2,3,4} , se define el conjunto 𝑅 formado por los pares
{(𝑑; 1), (𝑐; 2); (𝑎; 2), (𝑎; 3)},
a. ¿Corresponde 𝑅 a una función? ¿Por qué?
No, porque el elemento “𝑏” del conjunto A, no tiene ningún correspondiente en
B. Además, el elemento “𝑎” tiene dos posibles imágenes.
b. En caso de que la respuesta anterior fuera afirmativa, indicar Dominio,
Codominio e Imagen de la función. En caso de que no fuera función agregar o
quitar la mínima cantidad de pares para que resulte una función y, de ésta,
indicar Dominio, Codominio e Imagen.
Hay que eliminar uno de los pares que tienen a “a” como primer elemento y
agregar uno que tenga a “b”, por ejemplo: 𝑅 = {(𝑑; 1), (𝑐; 2); (𝑎; 2), (𝑏; 3)}.
Para esta función:
𝐷𝑜𝑚(𝑅) = {𝑎, 𝑏, 𝑐, 𝑑}
𝐶𝑜𝑑𝑜𝑚(𝑅) = {1,2,3,4}
𝐼𝑚(𝑅) = {1,2,3}
13) Sean 𝐴 el conjunto formado por todos las personas inscriptas en la materia “Estructuras
Discretas” y 𝑅 la relación definida por “… tiene como altura …”,
a. ¿Corresponde 𝑅 a una función? ¿Por qué?
Sí, porque cada estudiante tiene una y solo una altura.
b. En caso de que la respuesta anterior fuera afirmativa, indicar Dominio,
Codominio e Imagen de la función. En caso de que no fuera función agregar o
quitar la mínima cantidad de pares para que resulte una función y, de ésta,
indicar Dominio, Codominio e Imagen.
𝑓3 : 𝐷 → 𝐷/𝑓3 (𝑛) = 𝑛
𝑆 𝑇
𝑎 1
𝑏
𝑐 2
𝑑 3
𝑆 𝑇
𝑎 1
𝑏
𝑐 2
𝑑 3
20) Considerar las funciones del ejercicio 8). Decidir, en cada caso, si es posible hacer las
siguientes composiciones, justificando en cada caso. En los casos en los que sea posible
dar la composición (fórmula o pares)
a. 𝑓1 ∘ 𝑓3 , no es posible, porque la imagen de 𝑓3 no está incluida en el dominio de
𝑓1
b. 𝑓3 ∘ 𝑓1 , sí es posible, porque la imagen de 𝐼𝑚(𝑓1 ) = {2,3} que es un
subconjunto del Dominio de 𝑓3 . Entonces, (𝑓3 ∘ 𝑓1 ) =
{(𝑎; 5), (𝑏; 3), (𝑐; 5), (𝑑; 3)}
c. 𝑓2 ∘ 𝑓4 , no es posible, porque la imagen de 𝑓4 no está incluida en el dominio de
𝑓2
d. 𝑓4 ∘ 𝑓2 , sí es posible, porque la 𝐼𝑚(𝑓2 ) = {1,2} que es un subconjunto del
Dominio de 𝑓4 . Entonces, (𝑓4 ∘ 𝑓2 ) = {(𝑎; 4), (𝑏; 1), (𝑐; 4), (𝑑; 1)}
e. 𝑓3 ∘ 𝑓4 , no es posible, porque 𝐼𝑚(𝑓4 ) = {0,1,4} no es un subconjunto del
Dominio de 𝑓3.
Ejercicios
1) 3 2) 6 3) 36 4) 8 5) 8
6) a)8 7) 11 8) 360 9) a)20 10) 35
b)32 b)25
11) a)25 12) 648 13) 531.441.000 14) 100 15) 730
b)20
16) 200 17) 7.000.000 18) 3.628.800 19) 120 20) 720
21) 172.800 (si 22) 2.880 23) a)3.628.800 24) a)120 25) 967.680
los nenes y b)1.814.400 b)24
las nenas c)161.280 c)24
se separan) d)86.400 d)6
79.833.600 e)720 e)48
(si se f)96
pueden
alternar)
Ejercicios
Ejercicios
Ejercicios
1) item a) Item b)
𝑪𝒃𝒂
𝑪𝒃𝒂
𝑴𝒅𝒛
𝑴𝒅𝒛
𝑩𝒔 𝑨𝒔
𝑩𝒔 𝑨𝒔
𝑵𝒒𝒏
𝑵𝒒𝒏
𝑷𝒂𝒎
𝑷𝒂𝒎
item c) Item d)
𝑪𝒃𝒂 𝑪𝒃𝒂
𝑴𝒅𝒛 𝑴𝒅𝒛
𝑩𝒔 𝑨𝒔 𝑩𝒔 𝑨𝒔
𝑵𝒒𝒏 𝑵𝒒𝒏
𝑷𝒂𝒎 𝑷𝒂𝒎
2)
𝟔𝟎𝟓𝑲𝒎
𝑪𝒃𝒂
𝟔𝟗𝟔𝑲𝒎 𝑴𝒅𝒛
𝟕𝟖𝟖𝑲𝒎
𝑩𝒔 𝑨𝒔 𝟕𝟕𝟔𝑲𝒎
𝑵𝒒𝒏
𝟖𝟑𝟒𝑲𝒎
𝑷𝒂𝒎 𝟑𝟖𝟏𝑲𝒎
3)
𝒗𝟏
𝒗𝟒
𝒗𝟐
𝒗𝟑
4) Grafos simples:
a. Es grafo simple
b. No es grafo simple, hay que quitar como mínimo 2 aristas
c. No es grafo simple, hay que quitar como mínimo 2 aristas
d. No es grafo simple, hay que quitar como mínimo 2 aristas
5)
Del ejercicio 3:
0 2 0 1
𝐴 = (2 0 1 2)
0 1 0 1
1 2 1 0
Del ejercicio 4:
0 1 0 1 0 0 2 1 1 0
1 0 1 1 1 2 0 0 1 1
Item a) 𝐴= 0 1 0 1 1 Item b) 𝐴 = 1 0 0 1 2
1 1 1 0 0 1 1 1 0 1
(0 1 1 0 0) (0 1 2 1 0)
0 1 0 1 0 1 1 0
Item c) 𝐴 = (1 0 2 1) item d) 𝐴 = (0 0 1 0)
0 2 0 0 0 1 0 0
1 1 0 1 0 0 0 1
Grados:
Ejercicio 3 Ejercicio 4a Ejercicio 4b Ejercicio 4c Ejercicio 4d
Vértice Grado Vértice Grado Vértice Grado Vértice Grado Vértice Grado
𝑣1 3 1 2 1 4 𝑎 2 𝑎 2
𝑣2 5 2 4 2 4 𝑏 4 𝑏 3
𝑣3 2 3 3 3 4 𝑐 2 𝑐 3
𝑣4 4 4 3 4 4 𝑑 4 𝑑 2
5 2 5 4
6) Recuerda que cada matriz de incidencia puede ser diferente, en todo caso, para la misma
distribucion y orden de los vértices, puede haber alguna permutación de columnas
1 1 0 0 0 0 0
1 1 1 0 0 0 0
1 0 1 1 1 0 0
𝐼𝑒𝑗3 = (1 1 0 1 1 1 0) 𝐼𝑒𝑗4𝑎) = 0 0 1 0 0 1 1
0 0 0 0 1 0 1 0 1 0 1 0 0 1
0 0 1 1 0 1 1
(0 0 0 0 1 1 0)
1 1 1 1 0 0 0 0 0 0
1 1 0 0 0 0
1 1 0 0 1 1 0 0 0 0
𝐼𝑒𝑗4𝑏) = 0 0 1 0 0 0 1 1 1 0 𝐼𝑒𝑗4𝑐) = (1 0 1 1 1 0)
0 0 0 1 1 0 1 0 0 1 0 0 1 1 0 0
0 1 0 0 1 1
(0 0 0 0 0 1 0 1 1 1)
Por ahora, no están las respuestas del resto de ejercicios… Así que solo te queda consultar…