Estructuras Discretas

César Bautista Ramos

Carlos Guillén Galván
Daniel Alejandro Valdés Amaro

Facultad de Ciencias de la Computación

Benemérita Universidad Autónoma de Puebla

 1. CONJUNTOS Y CLASES 1

1. Conjuntos y Clases
1.1. Predicados y Cuantificadores. Frecuentemente en Matemáticas y Computación
nos encontramos con enunciados en los que se incluyen variables como:
x > 3, x = y + 3 y x + y = z.
A este tipo de enunciados no se les puede asignar un valor de verdad, es decir, no son
ni verdaderos ni falsos si no se especifican los valores de las variables. A continuacin
discutiremos las formas en las que las proposiciones pueden producir tales enunciados.
El enunciado “x es mayor que 3” tiene dos partes: la primera, la variable x que es el
sujeto del enunciado, y la segunda parte denominada predicado, “es mayor que 3”, hace
referencia a una propiedad que puede tener el sujeto. Si denotamos el enunciado anterior
por P (x) donde P denota el predicado “es mayor que 3” y x es la variable. La sentencia
P (x) se dice tambin que es el valor de la función proposicional P en x. Ası́, una vez que se
le asigne un valor a la variable x, la sentencia P (x) se convierte en una proposicin y tiene
un valor de verdad. Veamos un ejemplo.
Ejemplo 1. Si P (x) denota el enunciado “x > 3”, ¿cuáles son los valores de verdad
de P (4) y P (2)?
Solución: Entonces obtenemos la sentencia P (4) haciendo x = 4 en el enunciado “x >
3” y por tanto, P (4) que es el enunciado “4 > 3”, es verdadero. Similarmente para P (2),
el enunciado “2 > 3”, es falso.
También podemos tener sentencias que incluyan más de una variable. Por ejemplo, en
el enunciado “x = y + 3” podemos denotar esta sentencia por Q(x, y), donde x e y son
variables y Q es el predicado. Al asignar valores a x e y , la sentencia tiene una tabla y
valores de verdad.
Ejemplo 2. Q(x, y) denota el enunciado “x = y +3” , ¿cuáles son los valores de verdad
de las proposiciones Q(1, 2) y Q(3, 0)?
Solución: Haciendo x = 1 y y = 2 en Q(x, y) tenemos Q(1, 2) que es el enunciado
“1 = 2 + 3” que es falso. La sentencia Q(3, 0) es el enunciado “3 = 0 + 3” que es verdadero.
De manera similar, podemos denotar como R(x, y, z) el enunciado “x+y=z”, que al
asignarle valores a las variables x, y y z, dicha sentencia tendr una tabla de verdad.
Ejemplo 3. ¿Cules son los valores de verdad de las proposiciones R(1, 2, 3) y R(0, 0, 1)?
Solución: Haciendo x = 1, y = 2 y z = 3 en R(x, y, z) tenemos que R(1, 2, 3) es el
enunciado “1 + 2 = 3” que es verdadero. Tambin se ve que R(0, 0, 1), con el enunciado
“0 + 0 = 1” que es falso.
En general, una sentencia que incluye las n variables x1 , x2 , . . . , xn se puede denotar
como:
P (x1 , x2 , . . . , xn ).
Una sentencia de la forma P (x1 , x2 , . . . , xn ) es el valor de la función proposicional
P en la n-tupla (x1 , x2 , . . . , xn ). A P también se le llama predicado.
2

En el siguiente ejemplo, las funciones proposicionales se usan en la evaluacin de expre-

siones para una condicin de tipo if en un programa:
Ejemplo 4. Consideremos la sentencia
if x > 0 then x := x + 1.
Solución: Cuando el programa llega a esta lı́nea, el valor de la variable x en este punto
de la ejecucin se inserte en P (x), que es ”x > 0”. Si P (x) es verdadera para este valor de
x, la sentencia de asignacin x := x + 1 se ejecuta, por loq ue el valor de x se incrementa
en 1. Si P (x) es falsa para este valor de x, la sentencia de asignación no se ejecuta, por lo
que el valor de x no cambia.
Tarea 1. Denotemos por P (x) la sentencia x ≤ 4. ¿Cuáles son los valores de verdad
siguientes?
(1) P (0)
(2) P (4)
(3) P (6)
Tarea 2. Denotemos por P (x) la sentencia “la palabra x contiene la letra a”. ¿Cuáles
son los valores de verdad siguientes?
(1) P (naranja)
(2) P (verdadero)
(3) P (limón)
(4) P (falsa)
Tarea 3. Denotemos por Q(x, y) la sentencia “y es la capital de x”. ¿Cuáles son los
valores de verdad siguientes?
(1) P (Francia, Parı́s)
(2) P (Bolivia, Tegucigalpa)
(3) P (Honduras, La Paz)
(4) P (Colombia, Cartagena)
Tarea 4. Declarar el valor de x tras ejecutar la sentencia if P (x) then x := 1, donde
P (x) es la sentencia x > 1 si el valor de x cuando se llega a la sentencia es:
(1) x = 0
(2) x = 1
(3) x = 2
1.1.1. Cuantificadores. Cuando a todas las variables de una función proposicional se le
han asignado valores, la sentencia resultante se convierte en una proposición con un cierto
valor de verdad. Sin embargo, hay otra forma importante, llamada cuantificación, de
crear una proposición a partir de una función proposicional.
Cuantifiacador Universal
Muchas sentencias matemáticas imponen que una propiedad es verdadera para todos los
valores de una variable en un dominio particular, llamado el universo de discurso o
 1. CONJUNTOS Y CLASES 3

dominio. Tales sentencias se expresan utilizando un cuantificador universal. La cuan-

tificación universal de una función proposicional es la proposición que afirma que P (x)
es verdaderapara todos los valores de x en el dominio. El dominio especifica los posibles
valores de la variable x.
Definición 1. La cuantificación universal de P (x) es la proposición P (x) es ver-
dadera para todos los valores x del dominio.
La notación
∀x P (x)
denota la cuantificación universal de P (x). Llamaremos al sḿbolo ∀ el cuantificador uni-
versal, tal que la proposición ∀x P (x) se lee como:
• para todo x P (x)
• para cada x P (x) o
• para cualquier x P (x).
Ejemplo 5. Sea P (x) el enunciado x + 1 > x, ¿cuál es el valor de verdad de la
cuantificación ∀x P (x), donde el dominio consiste en todos los números reales?
Solución: Como P (x) es verdadera para todo número real x, la cuantificación
∀x P (x)
es verdadera.
Ejemplo 6. Sea Q(x) el enunciado x < 2, ¿cuál es el valor de verdad de la cuantificación
∀x Q(x), donde el dominio consiste en todos los números reales?
Solución: Q(x) no es verdadera para todo número real x. Por ejemplo, Q(3) es falsa,
por tanto
∀x Q(x)
es falsa.
Cuando todos los elementos del dominio se pueden enumerar (escribiéndolos, por ejem-
plo como x1 , x2 , . . . , xn ) se tiene que la cuantificación universal ∀x P (x) es lo mismo que
la conjunción
P (x1 ) ∧ P (x2 ) ∧ · · · ∧ P (xn ),
puesto que esta conjunción es verdadera si, y sólo si P (x1 ), P (x2 ), . . . , P (xn ) son todas
verdaderas.
Ejemplo 7. ¿Cuál es el valor de verdad de ∀x P (x), donde P (x) es el enunciado
x2 < 10 y el dominio consiste en los enteros positivos menores o iguales que 4?
Solución: La sentencia ∀x P (x) es lo mismo que la conjunción
P (1) ∧ P (2) ∧ P (x3 ) ∧ P (x4 ),
puesto que el dominio consiste en los enteros 1, 2, 3 y 4. Como P (4), la sentencia 42 < 10
es falsa y tenemos que ∀x P (x) es tambin falsa.
4

Ejemplo 8. ¿Qué significa la sentencia ∀x T (x) si T (x) es el enunciado “x tiene un

padre y una madre” y el dominio consiste en toda la gente?
Solución: La sentencia ∀x T (x) significa que toda persona x tiene un padre y una
madre. La sentencia se puede expresar en lenguaje natural como “Toda persona tiene dos
padres”. La sentencia es verdadera excepto para seres clonados (si los hay).
Ejemplo 9. ¿Cuál es el valor de verdad de ∀x(x2 ≥ x), si el dominio consiste en todos
los números reales y cuál es el valor de verdad si el dominio son todos los enteros?
Solución: Teniendo en cuenta que x2 ≥ x si, y sólo si, x2 − x = x(x − 1) ≥ 0.
Consecuentemente, x2 ≥ x si, y sólo si, x ≤ 0 o x ≥ 1. Ası́, tenemos que ∀x(x2 ≥ x)
es falsa si el dominio consiste en todos los números reales (ya que la desigualdad es falsa
para los números reales x tales que 0 < x < 1). Sin embargo, si el dominio consiste en los
enteros ∀x(x2 ≥ x) es verdadera por no haber enteros x tales que 0 < x < 1.
Para mostrar que una sentencia de la forma ∀x P (x) es falsa, donde P (x) es una función
proposicional, sólo necesitamos encontrar un valor de x del dominio para el cual P (x) sea
falsa. Es decir, necesitamos encontrar un contraejemplo x de la sentencia ∀x P (x).
Ejemplo 10. Supongamos que P (x) es x2 > 0. Para mostrar que la sentencia ∀x P (x)
es falsa cuando el dominio sea todos los enteros, daremos un contraejemplo. Vemos que
x = 0 es un contraejemplo, ya que x2 = 0, por lo que no es mayor que 0.

Cuantificador Existencial
Muchas sentencias matemáticas afirman que hay un elemento con una cierta propiedad.
Tales sentencias se expresan mediante cuantificadores existenciales. Con un cuantificador
existencial formamos una proposición que es verdadera si y sólo si P (x) es verdadera para
al menos un valor de x en el dominio.
Definición 2. La cuantificación existencial de P (x) es la proposición “Existe un
elemento x en el dominio tal que P (x) es verdadera”. Usamos la notación
∃x P (x)
para la cuantificación existencial de P (x). El sı́mbolo ∃ se denomina cuantificador exis-
tencial. La cuantificación existencial ∃x P (x) se lee como
• Hay un x tal que P (x)
• Hay al menos un x tal que P (x) o
• Para algún x P (x).
A continuación ilustraremos el uso del cuantificador existencial en los siguientes ejem-
plos.
Ejemplo 11. Sea P (x) el enunciado x > 3. ¿Cuál es el valor de verdad de la cuantifi-
cación ∃x P (x), donde el dominio consiste en todos los números reales?
Solución: Como x > 3 es verdadero, por ejemplo, para x = 4, la cuantificación existen-
cial de P (x) es verdadera.
 1. CONJUNTOS Y CLASES 5

Ejemplo 12. Sea Q(x) el enunciado x = x + 1. ¿Cuál es el valor de verdad de la

cuantificación ∃x Q(x), donde el dominio consiste en todos los números reales?
Solución: Como Q(x) es falsa para todo número real x, la cuantificación existencial de
∃x Q(x) es falsa.
Ejemplo 13. ¿Cuál es el valor de verdad de la cuantificación ∃x P (x), donde P (x) es
el enunciado x2 > 10 y el dominio consiste en los enteros positivos menores o iguales que
4?
Solución: Como el dominio es {1, 2, 3, 4}, la proposición ∃x P (x) es lo mismo que la
disyunción
P (1) ∨ P (2) ∨ P (x3 ) ∨ P (x4 ).
Como P (4), que es el enunciado 42 > 10 es verdadero, tenemos que ∃x P (x) es ver-
dadera.
En la tabla 1 se resume el significado de los cuantificadores universales y existenciales.

Sentencia ¿Cuándo es verdadera? ¿Cuándo es falsa?

∀x P (x) P (x) es verdadera para todo x Hay un x para el que P (x) es falsa
∃x P (x) Hay un x para el que P (x) es verdadera P (x) es falsa para todo x
Tabla 1. Cuantificadores

Los cuantificadores ∀ y ∃ tienen una mayor precedencia que todos los demás operadores
lógicos del cálculo proposicional. Por ejemplo, ∀x P (x) ∨ Q(x) es la disjunción de ∀x P (x)
y Q(x), y signiifica (∀x P (x)) ∨ Q(x) en lugar de ∀x (P (x) ∨ Q(x)).
Cuando se quiere determinar el valor de verdad de una cuantificación, a veces es útil
realizar una búsqueda sobre todos los posibles valores del dominio. Supongamos que hay n
objetos en el dominio de la variable x, para determinar si ∀x P (x) es verdadera podemos
“barrer” los n valores de x y ver si P (x) es verdadera para todos ellos. Si encontramos un
valor de x para el cual P (x) es falsa, habremos demostrado que ∀x P (x) es falsa. En caso
contrario, ∀x P (x) es verdadera. Para ver si ∀x P (x) es verdadera, “barremos” los n valores
posibles de x buscando algún valor para el cual P (x) sea verdadera. si encontramos uno,
entonces ∃x P (x) es verdadera. Si no encontramos tal valor de x, habremos determinado
que ∃x P (x) es falsa. Debido a que este procedimiento de búsqueda no puede ser aplicado
si el dominio se compone de elementos infinitos, aun ası́ sigue siendo una forma útil de
trabajar con cuantificadores.
Tarea 5. Sea P (x) la sentencia x = x2 . Si el dominio consiste en todos los enteros,
¿cuáles son los valores de verdad siguientes?
(1) P (0)
(2) P (1)
(3) P (2)
(4) P (−1)
(5) ∃x P (x)
6

(6) ∀x P (x)

Variables Ligadas
Definición 3. Cuando un cuantificador se usa sobre la variable x o cuando asignamos
un valor a esta variable, decimos que la variable aparece ligada. Una variable que no
aparece ligada por un cuantificador o fijada a un valor particular se dice que es libre.
Todas las variables que aparecen en una función proposicional deben ser ligadas para
convertirla en proposición. Esto se puede hacer utilizando una combinación de cuantifi-
cadores universales, existenciales y asignación de valores.
La parte de una expresión lógica a la cual se aplica el cuantificador se llama ámbito
de este cuantificador. Consecuentemente, una variable es libre si está fuera del ámbito de
todos los cuantificadores de la fórmula.
Ejemplo 14. En la sentencia ∃x Q(x, y), la variable x está ligada por el cuantificador
existencial ∃x, pero la variable y es libre porque no está ligada a un cuantificador y nos se
le asigna valor alguno a esta variable.
En la sentencia ∃x (P (x) ∧ Q(x)) ∨ ∀x R(x) todas las variables están ligadas. El
ámbito del primer cuantificador, ∃x, es la expresión P (x) ∧ Q(x) porque ∃x se aplica sólo
a esta expresión y no al resto de la sentencia. De forma similar, el ámbito del segundo
cuantificador, ∀x, es la expresión R(x). Es decir, el cuantificador existencial liga la variable
x en P (x) ∧ Q(x) y el cuantificador universal liga la variable x en R(x).

Negaciones
Con frecuencia hace falta considerar la negación de una expresión cuantificada. Por ejem-
plo, consideremos la negacin del enunciado “Todos los estudiantes de la clase han cursado
una materia de cálculo”.
Esta sentencia es una cuantificación universal de la forma ∀x P (x) donde P (x) es la
sentencia “x ha cursado una materia de cálculo”. La negación de esta sentencia es “No se
cumple que todos los estudiantes de la clase hayan cursado una materia de cálculo”, lo cual
es equivalente a “Hay al menos un estudiante en la clase que no ha cursado una materia de
cálculo”. Y esto es simplemente la cuantificación existencial de la negación de la función
proposicional original, es decir, ∃x ¬P (x).
Ası́, tenemos que:
¬∀x P (x) ≡ ∃x ¬P (x).
supongamos que queremos negar una cuantificación existencial. Por ejemplo, consider-
emos la proposición “Hay un estudiante en la clase que ha cursado una materia de cálculo”,
siendo una cuantificación existencial ∃x Q(x), donde Q(x) es el predicado “x ha cursado
una materia de cálculo”. Esto es quivalente a “Ninguno de los estudiantes de la clase ha
cursado una materia de cálculo”, que es justamente la cuantificación universal de la ne-
gación de la función proposicional original. Serı́a equivalente, en lenguaje poco común, a
“Para todo estudiante se cumple que no ha cursado una materia de cálculo”, o expresado
con cuantifiacadores, ∀x ¬P (x).
 1. CONJUNTOS Y CLASES 7

Es decir:
¬∃x Q(x) ≡ ∀x ¬Q(x).
Las negaciones se resumen en la tabla 2.

Negación Fórmula equivalente ¿Cuándo es verdadera? ¿Cuándo es falsa?

¬∃x P (x) ∀x ¬Q(x) Para cada x, P (x) es falsaHay un x para el
que P (x) es ver-
dadera
¬∀x P (x) ∃x ¬P (x) Hay un x para el que P (x) es falsa P (x) es verdadera
para cada x
Tabla 2. Negación de cuantificadores

Observación: Cuando el dominio de un predicado P (x) consiste en n elementos, donde n

es un entero positivo, las reglas de la negación de sentencias cuantificadas son exactamente
las mismas que las leyes de De Morgan. Esto es ası́ porque ¬∀x P (x) es lo mismo que
¬(P (x1 ) ∧ P (x2 ) ∧ . . . ∧ P (xn )), equivalente a ¬(P (x1 ) ∨ ¬P (x2 ) ∨ . . . ∨ ¬P (xn )) por las
leyes de De Morgan, lo que equivale a ∀x ¬P (x).
Ejemplo 15. ¿Cuáles son las negaciones de los enunciados “Hay un polı́tico honesto”
y “Todos los estadounidenses comen hamburguesas”?
Solución: Denotemos como H(x) a “x es honesto”. La sentencia ‘Hay un polı́tico
honesto” se representa por ∃x H(x), donde el dominio consiste en todos los polı́ticos. La
negación de la sentencia es ¬∃x H(x), lo que equivale a ∀x ¬H(x). Esta negación se puede
expresar como “Todo polı́tico es deshonesto”. (Nota: En lenguaje natural, la frase “Los
polı́ticos son deshonestos” puede ser ambigua. A veces esta frase se utiliza para expresar
que “No todos los polı́ticos es honestos”. Por eso no utilizamos esta frase para expresar la
negación).
Sea C(x) el enunciado “x come hamburguesas”, entonces “Todos los estadounidenses
comen hamburguesas” se representa por ∀x C(x), donde el dominio consiste en todos
los estadounidenses. La negación de esta sentencia es ¬∀x C(x), que es equivalente a
∃x ¬C(x). Esta negación se puede expresar de muchas maneras, entre las que se incluyen
“Algunos estadounidenses no comen hamburguesas” y “Hay algún estadounidense que no
come hamburguesas”?.
Ejemplo 16. ¿Cuáles son las negaciones de las sentencias ∀x (x2 > x) y ∃x (x2 = 2)?
Solución: La negación de ∀x (x2 > x) es la sentencia ¬∀x (x2 > x), que es equivalente
a ∃x ¬(x2 > x) y que también se puede escribir de la forma ∃x (x2 ≤ x). La negación
de ∃x (x2 = 2) es ¬∃x (x2 = 2), equivalente a ∀x ¬(x2 = 2) y se pude reescribir como
∀x (x2 6= 2). Los valores de verdad de estas sentencias depende del dominio.

Traducción de oraciones en lenguaje natural a lenguaje formal

Traducir frases del lenguaje natural a expresiones lógicas es una tarea crucial en matemáticas,
8

programación lógica, inteligencia artificial, ingenierı́a de software y muchas otras áreas.

Formalizar expresiones del lenguaje natural en expresiones lógicas se hace más complejo
cuando se requieren cuantificadores, además de que puede haber diferentes formas de tra-
ducir una frase particular. Utilizaremos algunos ejemplos para ilustrar cómo se formalizan
afirmaciones del lenguaje natural en lógica de predicados. El objetivo es producir expre-
siones lógicas simples y útiles.
Ejemplo 17. Expresar la frase “Todo estudiante de esta clase ha estudiado cálculo”
utilizando predicados y cuantificadores.
Solución: Primero, reescribimos la sentencia de tal forma que podamos identificar con
claridad los cuantificadores que debemos emplear. Ası́, obtenemos:
“Para todo estudiante de esta clase, ese estudiante ha estudiado cálculo”.
Luego introducimos la variable x, de tal forma que nuestra sentencia se convierte en:
“Para todo estudiante x de esta clase, x ha estudiado cálculo”.
Continuando, introducimos el predicado C(x), que esl enunciado “x ha estudiado
cálculo”. Por lo tanto, si el dominio de x consiste en los estudiantes de la clase, pode-
mos traducir nuestra frase como ∀x C(x).
No obstante, hay otras opciones correctas ya que se pueden considerar diferentes domin-
ios o diferentes predicados. La opción que seleccionemos dependerá del razonamiento que
queremos realizar a continuación. Por ejemplo, podemos estar interesados en un grupo de
personas más amplio que el de esa clase en particular. Si cambiamos el dominio, tomando
el conjunto de todas las personas, habremos de expresar nuestro enunciado como:
“Para toda persona x, si la persona x es un estudiante de esta clase, entonces x ha
estudiado cálculo”.
Si S(x) representa el predicado de que la persona x está en la calse, nuestra sentencia
se puede expresar como ∀x (S(x) ⇒ C(x)). Sin embargo debemos tener cuidado, recuerde
que nuestra sentencia no puede expresarse como ∀x (S(x)∧C(x)), puesto que esta sentencia
afirmarı́a que todas las personas son estudiantes de la clase y han estudiado cálculo.
Finalmente, cuando estamos interesados en los estudios de una persona, aparte del
cálculo, podrı́amos preferir usar un cuantificador de dos variables Q(x, y) para la frase
“el estudiante x ha estudiado la asignatura y”. Ası́ podrı́amos reemplazar C(x) por
Q(x, cálculo) en las dos opciones que hemos elegido para obtener ∀x Q(x, cálculo) o ∀x (S(x) ⇒
Q(x, cálculo)).
Ejemplo 18. Formalizar las frases “Algún estudiante de esta clase ha visitado Inglaterra”
y “Todo estudiante de esta clase ha visitado bien Inglaterra o bien Argentina”.
Solución: La frase “Algún estudiante de esta clase ha visitado Inglaterra” significa que
“Hay algún estudiante en esta clase que tiene como atributo que ese estudiante ha
visitado Inglaterra”.
Introduciendo una variable x, de tal forma que nuestra frase se convierte en
“Hay un estudiante x en esta clase que tiene como atributo que x ha visitado Inglaterra”.
 1. CONJUNTOS Y CLASES 9

Introducimos el predicado I(x), que es el enunciado “x ha visitado Inglaterra”. Si el

dominio para x consiste en los estudiantes de esta clase, se puede traducir esta primera
frase como ∃x I(x).
No obstante, si estamos interesados en otras personas además de las de la clase,
tomamos la frase de forma diferente y la frase se puede expresar como:
“Hay una persona x que tiene como atributos que x es un estudiante de esta clase y que
x ha visitado Inglaterra”.
En este caso, el dominio para la variable x son todas las personas. Introducimos
el predicado S(x), “x es un estudiante de esta clase” y nuestra solución se convierte en
∃x (S(x)∧I(x)), ya que la frase hace referencia a una persona x que es estudiante de la clase
y que ha visitado Inglaterra. Nota: La sentencia so puede expresarse como ∃x (S(x) ⇒
I(x)), la cual es correcta cuando todos en la clase han visitado Inglaterra.
De forma similar, la segunda frase se puede expresar como:
“Para toda persona x, si x tiene como atributo que x ha visitado Inglaterra o x ha
visitado Argentina”.
Sea C(x) la sentencia “x ha visitado Argentina”. Siguiendo el razonamiento anterior,
vemos que si el dominio de x consiste en los estudiantes de esta clase, esta segunda sentencia
se puede expresar ∀x (C(x) ∨ I(x)). Sin embargo, si el dominio de x consiste en todas las
personas, la frase se puede expresar como:
“Para toda persona x, si x es un estudiante de esta clase, entonces x ha visitado
Inglaterra o x ha visitado Argentina”.
En este caso la sentencia se puede expresar como ∀x (S(x) ⇒ (C(x) ∨ I(x))).
En lugar de utilizar los predicados I(x) y C(x) para representar que x ha visitado
Inglaterra y que x ha visitado Argentina, respectivamente, podrı́amos haber usado un
predicado de dos variables V (x, y) para representar “x ha visitado el paı́s y”. En este
caso, V (x, Inglaterra) y V (x, Argentina) tendrı́an el mismo significado que I(x) y C(x) y
podrı́an reemplazarlas en nuestras respuestas. Si estamos trabajando con muchas frases
relacionadas con gente que visita diferentes paı́ces, podrı́amos preferir la opción de un
predicado de dos variables. En otros casos, por simplicidad, nos quedarı́amos con los
predicados de una variable I(x) y C(x).
Tarea 6. Sea P (x) la sentencia “x asiste a más de cinco horas de clase al dı́a”, donde
el dominio de x consiste en todos los estudiantes. Expresar las siguientes cuantificaciones
en lenguaje natural:
(1) ∃x P (x)
(2) ∀x P (x)
(3) ∃x ¬P (x)
(4) ∀x ¬P (x)
Tarea 7. Sea N (x) la sentencia “x ha visitado Alemania”, donde el dominio de x
consiste en todos los estudiantes de tu clase. Expresar las siguientes cuantificaciones en
lenguaje natural:
10

(1) ∃x N (x)
(2) ∀x N (x)
(3) ¬∃x N (x)
(4) ∃x ¬N (x)
(5) ¬∀x N (x)
(6) ∀x ¬N (x)
Tarea 8. Traducir las siguientes sentencias en el lenguaje natural, donde C(x) la
sentencia “x es un cómico” y F (x) es “x es divertido”, y el dominio consiste en todos las
personas.
(1) ∀x (C(x) ⇒ F (x))
(2) ∀x (C(x) ∧ F (x))
(3) ∃x (C(x) ⇒ F (x))
(4) ∃x (C(x) ∧ F (x))
Tarea 9. Traducir las siguientes sentencias en el lenguaje natural, donde R(x) la
sentencia “x es un conejo” y H(x) es “x salta”, y el dominio consiste en todos los animales:
(1) ∀x (R(x) ⇒ H(x))
(2) ∀x (R(x) ∧ H(x))
(3) ∃x (R(x) ⇒ H(x))
(4) ∃x (R(x) ∧ H(x))
Tarea 10. Sea P (x) la sentencia “x habla ruso” y Q(x) es “x conoce el lenguaje de
programación C++”. Expresar cada una de las siguientes sentencias en términos de P (x),
Q(x), cuantificadores y conectivos lógicos. El dominio para los cuantificadores consiste en
todos los estudiantes de tu facultad:
(1) Hay un estudiante en tu facultad que habla ruso y conoce C++.
(2) Hay un estudiante en tu facultad que habla ruso pero no conoce C++.
(3) Todos los estudiantes de tu facultad hablan ruso o conocen C++.
(4) Ningún estudiante de tu facultad habla ruso o conoce C++.
Tarea 11. Sea C(x) la sentencia “x tiene un gato”, D(x) es “x tiene un perro” y F (x)
es “x tiene un hámster”. Expresar cada una de las siguientes sentencias en términos de
C(x), D(x), F (x) cuantificadores y conectivos lógicos. El dominio para los cuantificadores
consiste en todos los estudiantes de tu clase:
(1) Un estudiante de tu clase tiene un gato, un perro y un hámster.
(2) Todos los estudiantes de tu clase tienen un gato, un perro o un hámster.
(3) Algún estudiante de tu clase tiene un gato y un hámster, pero no un perro .
(4) Ningún estudiante de tu clase tiene un gato, un perro y un hámster.
(5) Para cada uno de los tres animales, gatos, perros y hámsters, hay un estudiante
de tu clase que tiene uno de esos animales como mascota.
Tarea 12. Sea Q(x) la sentencia x+1 > 2. Si el dominio consiste en todos los enteros,
¿cuáles son los valores de verdad siguientes?
(1) Q(0)
 1. CONJUNTOS Y CLASES 11

(2) Q(−1)
(3) Q(1)
(4) ∃x Q(x)
(5) ∀x Q(x)
(6) ∃x ¬Q(x)
(7) ∀x ¬Q(x)
Tarea 13. Determinar el valor de verdad de cada una de las siguientes sentencias si
el dominio consiste en todos los números enteros
(1) ∀n (n + 1 > n)
(2) ∃n (2n = 3n)
(3) ∃n (n = −n)
(4) ∀n (n2 ≥ n)
Tarea 14. Determinar el valor de verdad de cada una de las siguientes sentencias si
el dominio consiste en todos los números reales
(1) ∃x (x3 = −1)
(2) ∀x ((−x)2 = x2 )
(3) ∃x (x4 < x2 )
(4) ∀x (2x > x)
Tarea 15. Suponer que el dominio de la función proposicional P (x) consiste en los
enteros 0, 1, 2, 3 y 4. Escriba cada una de esas proposiciones usando disyunciones, con-
junciones y negaciones.
∃x P (x)
∀x P (x)
∃x ¬P (x)
∀x ¬P (x)
¬∃x P (x)
¬∀x P (x)
Tarea 16. Suponer que el dominio de la función proposicional Q(x) consiste en los
enteros -2, -1, 0, 1 y 2. Escriba cada una de esas proposiciones usando disyunciones,
conjunciones y negaciones.
∃x P (x)
∀x P (x)
∃x ¬P (x)
∀x ¬P (x)
¬∃x P (x)
¬∀x P (x)
Tarea 17. Traducir de dos formas cada una de estas frases a expresiones lógicas
utilizando predicados, cuantificadores y conectivos lógicos. En primer lugar, el dominio
consistirá en los estudiantes de la clase, y en segundo lugar, consistirá en los estudiantes
de tu clase, y en segundo lugar, será el conjunto de todas las personas.
12

(1) Alguien de tu clase habla hindú.

(2) Todos en tu clse son amigables.
(3) Hay una persona en tu clase que no nacó en Puebla.
(4) Un estudiante de la clase ha visto una pelácula.
(5) Ningún estudiante de la clase ha cursado la asignatura de Cálculo.
Tarea 18. Traducir de dos formas cada una de estas frases a expresiones lógicas
utilizando predicados, cuantificadores y conectivos lógicos. En primer lugar, el dominio
consistirá en los estudiantes de la clase, y en segundo lugar, consistirá en los estudiantes
de tu clase, y en segundo lugar, será el conjunto de todas las personas.
(1) Todos en la clase tienen un telé fono celular.
(2) Alguien en la case ha visto una pelı́cula francesa.
(3) Hay una persona en la clase que no sabe nadar.
(4) Todos los estudiantes de la clase saben resolver ecuaciones de segundo grado.
(5) Algún estudiante de clase no quiere ser rico.
1.2. Teorı́a de Conjuntos Ingenua (Naive Set Theory). A pesar de que exis-
ten serias formalizaciones de la teorı́a de conjuntos, nos contentaremos con desarrollar su
álgebra usando el punto de vista inocente.