Capítulo 1
Introducción y Fundamentos
1.1. Introducción. Enunciado y Proposición Lógica
La lógica se considera una ciencia formal cuyo objeto de estudio son los distintos
principios de demostración que permitan comprobar que una afirmación pueda ser con-
siderada como válida.
La metodología de trabajo de la lógica consiste en examinar la validez o la invalidez
de una afirmación mediante la aplicación de una sistematización en los argumentos y,
por ende, de un análisis de su estructura lógica, sin tener en cuenta el contenido de lo
que se ha argumentado ni considerar siquiera el lenguaje utilizado, y sin contemplar el
estado de realidad del contenido.
Una proposición o enunciado constituye una oración que tiene un valor de verdad, es
decir, puede ser verdadera o falsa, pero no ambas. La proposición es uno de los elementos
fundamentales en lógica.
Si la oración es una pregunta, una orden, carece de sentido o es muy imprecisa,
entonces no puede ser clasificada como verdadera o falsa, y por tanto no puede ser una
proposición.
Considere, por ejemplo, las seis oraciones siguientes:
1,) La madera flota en el agua.
2.) Perú está en Norteamérica.
3.) 3 + 3 = 6.
4.) Si p es primo entonces p es impar.
5.) ¿A dónde vas?
6.) Haz tu trabajo.
Las cuatro primeras son proposiciones; las dos últimas, no. También, 1.) y 3.) son
verdaderas, pero 2.) y 4.) son falsas.
Los métodos lógicos se usan en matemáticas para demostrar teoremas; en ingeniería
es de gran utilidad en la electrónica, para el diseño de circuitos mediante compuertas
lógicas y, en las ciencias de la computación, para el diseño de programas que requieren la
unión de operadores lógicos. Supongamos, por ejemplo, que se asigna a un estudiante el
desarrollo de un programa para calcular las rutas más cortas entre ciudades. Es necesario
que el programa acepte como entrada un número arbitrario de ciudades y las distancias
entre las ciudades con conexión directa por carretera, y que produzca como salida las
rutas más cortas entre cada par distinto de ciudades. Después de escribir el programa,
es fácil para el estudiante probarlo con un número reducido de ciudades. Con papel y
lápiz, puede enumerar todas las rutas posibles entre pares de ciudades y encontrar las
más cortas. Esta solución se compara con la salida del programa. Sin embargo, para un
número grande de ciudades, esta técnica sería muy lenta. ¿Cómo puede el estudiante
estar seguro de que el programa trabaja bien para muchos datos (casi seguro el tipo
de entrada con la que el profesor probaría el programa)? Él tendrá que usar la lógica
para argumentar que el programa es correcto. El argumento puede ser informal o formal
usando las técnicas presentadas; pero se requerirá un argumento lógico.
Se usarán variables, como p, q y r, para representar las proposiciones, casi como se
usan letras en álgebra para representar números. Así, es posible utilizar una proposi-
ción haciendo referencia solo a la variable proposicional utilizada. En lógica se pueden
encontrar dos clases de proposiciones: simples o atómicas y compuestas o moleculares.
El área de la lógica que trata de proposiciones se llama cálculo proposicional o lógica
proposicional. Muchos enunciados matemáticos se construyen combinando una o más
proposiciones. Las nuevas proposiciones son las fórmulas o proposiciones compuestas.
Para tal efecto se usan los llamados operadores lógicos.
Las proposiciones simples o atómicas son aquellas que están estructuradas por una
única oración. Para su representación, a la proposición se le asigna una variable propo-
sicional. Así, por ejemplo
p : Los únicos enteros positivos que dividen a 7 son 1 y el mismo 7.
q : Está lloviendo.
r : Hace frío.
son proposiciones simples.
Las proposiciones compuestas o moleculares son aquellas que están estructuradas
por dos o más proposiciones simples. En el caso de las proposiciones compuestas, a
cada proposición simple que la forma se le puede asignar una variable proposicional. Por
ejemplo
p : Está lloviendo y hace frío.
es una proposición compuesta, y es el resultado de la combinación de las proposiciones
q y r anteriores las cuales son simples.
1.1.1. Operadores lógicos
Los operadores lógicos son aquellos símbolos que permiten decidir qué valor de verdad
tiene una proposición. El valor de verdad de una proposición simple puede ser verdadero
o falso, y los únicos operadores lógicos que se pueden utilizar en estas proposiciones son
la negación y la doble negación.
El valor de verdad de una proposición compuesta es verdadero o falso y depende de
los valores de verdad de las proposiciones simples que la estructuran, las cuales están
combinadas por operadores lógicos.
2
Los básicos a estudiar son: la conjunción, denotada por ∧; la disyunción denotada
por ∨, y la negación, denotada por ¬.
Una tabla de verdad es una tabla que muestra las relaciones entre los valores de
verdad de proposiciones sean simples o compuestas. Las siguientes tablas definen los
operadores básicos considerados.
p q p∧q p q p∨q p ¬p
V V V V V V V F
V F F V F V F V
F V F F V V
F F F F F F
También se define el conectivo lógico o exclusivo de p y q, denotado por p ⊕ q, mediante
la tabla
p q p⊕q
V V F
V F V
F V V
F F F
1.2. Tautología y Contradicción. Implicación. Pro-
posiciones equivalentes
Una tautología es una proposición que es verdadera para todos los posibles valores
de verdad de sus componentes simples. Un enunciado cuya forma es una tautología es
un enunciado tautológico.
Una contradicción es una forma de enunciado que siempre es falso, independiente-
mente de los valores de verdad de los enunciados individuales de los enunciados variables
sustituidos. Un enunciado cuya forma es una contradicción es un enunciado contradic-
torio.
Una proposición es una contingencia cuando puede ser verdadera o falsa, dependiendo
de los valores de verdad de sus componentes simples.
Ejemplo 1.1. En la tabla siguiente vemos un ejemplo de una tautología p ∨¬ p y de
una contradicción p ∧¬ p.
p ¬p p ∨¬ p p ∧¬ p
V F V F
F V V F
Ejemplo 1.2. Una contingencia se ve en la siguiente tabla
p q ¬p ¬p∨q
V V F V
V F F F
F V V V
F F V V
3
Si p y q son proposiciones, la proposición ”si p entonces q” se llama proposición
condicional y se denota por p → q. La proposición p se llama hipótesis (o antecedente)
y la proposición q recibe el nombre de conclusión (o consecuente). Su tabla de verdad es
p q p→q
V V V
V F F
F V V
F F V
Ejemplo 1.3. Sean p : estudio bastante y q : aprobaré Matemáticas Discretas. Entonces
la oración, si estudio bastante aprobaré Matemáticas Discretas, denotada por
p → q,
es una proposición condicional.
Otra proposición común es de la forma “p si y sólo si q”. Estas proposiciones se
denominan bicondicionales y se denotan por p ↔ q. Su tabla de verdad es
p q p↔q
V V V
V F F
F V F
F F V
Sean p y q proposiciones. Entonces se dice que p y q son lógicamente equivalentes si
p ↔ q es una tautología. Una definición alternativa (pero equivalente) es que p y q son
equivalentes si tienen la misma tabla de verdad. Es decir, si tienen el mismo valor de
verdad para todas las asignaciones de valores de verdad a las variables.
Cuando p y q son equivalentes, escribimos p ≡ q.
Nota: p ≡ q no es una proposición compuesta, sino una afirmación sobre la relación
entre dos proposiciones.
Existen muchas equivalencias lógicas (o identidades, reglas, leyes) que resultan útiles
cuando se trabaja con proposiciones compuestas. Muchas de ellas (por ejemplo, conmu-
tativas, asociativas, distributivas) se asemejan a las leyes aritméticas que se aprendieron
en la escuela primaria. Otras son muy diferentes. Las más comunes se muestran, más
adelante, como leyes lógicas.
Una manera alternativa de establecer “p si y sólo si q” es “p es una condición necesaria
y suficiente para q”.
Una condición necesaria es sólo eso: una condición que se necesita para lograr un
resultado en particular. La condición no garantiza el resultado; pero si no se cumple, el
resultado no se logrará.
Análogamente, una condición suficiente es una condición que basta para garantizar
un resultado en particular. Si la condición no se cumple, el resultado puede lograrse de
otras formas o tal vez no se logre; pero si la condición se cumple, el resultado está
garantizado.
4
1.2.1. Orden de uso de los operadores lógicos
En general se utilizan paréntesis para especificar el orden en el que deben aplicarse
los operadores lógicos en una fórmula. Por ejemplo, (p ∨ q) ∧ (¬ r) es la conjunción de
p ∨ q y ¬ r.
Sin embargo, para reducir el número de paréntesis, especificamos que el operador
negación se aplica antes que los operadores lógicos. Esto significa que el operador nega-
ción ¬ p ∧ q que es la conjunción de ¬ p y q, es decir, (¬ p) ∧ q, no la negación de la
conjunción de p y q, es decir, ¬ (p ∧ q).
Otra regla de orden es que el operador conjunción se aplica antes que el operador
disyunción, de tal forma que p∧q ∨r significa (p ∧ q)∨r y no p∧(q ∨ r). Finalmente, otra
regla es que los operadores condicional y bicondicional tienen precedencia inferior que
los operadores conjunción y disyunción. Consecuentemente, p ∨ q → r es lo mismo que
(p ∨ q) → r. El operador condicional tiene precedencia sobre el operador bicondicional.
1.3. Leyes lógicas. Inferencia y consecuencia lógica.
Las proposiciones satisfacen varias leyes o tautologías. Son las siguientes:
1. Leyes idempotentes: p ∨ p ≡ p y p ∧ p ≡ p
2. Leyes asociativas: (p ∨ q) ∨ r ≡ p ∨ (q ∨ r) y (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
3. Leyes conmutativas: p ∨ q ≡ q ∨ p y p ∧ q ≡ q ∧ p
4. Leyes distributivas: p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) y p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
5. Leyes de identidad: p ∨ F ≡ p, p ∨ V ≡ V , p ∧ V ≡ p, p ∧ F ≡ F
6. Leyes de doble negación: ¬¬ p ≡ p
7. Leyes de complementos: p ∨ ¬ p ≡ V , ¬ V ≡ F , p ∧ ¬ p ≡ F , ¬ F ≡ V
8. Leyes de absorción: p ∧ (p ∨ q) ≡ p, p ∨ (p ∧ q) ≡ p
9. Ley de contraposición: p → q ≡ ¬ q → ¬ p
10. Ley condicional: p → q ≡ ¬ p ∨ q
11. Ley del bicondicional: p ←→ q ≡ (p → q) ∧ (q → p) ≡ (¬ p ∨ q) ∧ (¬ q ∨ p) ≡
(p ∧ q) ∨ (¬ p ∧ ¬ q)
12. Leyes de De Morgan: ¬ (p ∨ q) ≡ ¬ p ∧ ¬ q y ¬ (p ∧ q) ≡ ¬ p ∨ ¬ q
Los razonamientos que estudia la lógica se llaman argumentos y su tarea consiste en
descubrir qué es lo que hace que un argumento sea válido y constituya una inferencia
correcta.
Por su parte, la inferencia es una actividad con la cual se afirma una proposición
sobre otra y otras proposiciones se aceptan como punto de partida del proceso.
Un argumento es un conjunto de una o más proposiciones, la última de las cuales se
denomina conclusión, mientras que las anteriores se llaman premisas.
5
De manera intuitiva, las premisas son la evidencia o las razones que deben convencer-
nos de la veracidad de la conclusión, y el argumento es la concatenación de las primeras
con la última.
Es habitual representar los argumentos haciendo un listado de las premisas y la
conclusión, separándola última mediante una línea.
La proposición q es consecuencia lógica de las proposiciones p1 , p2 , · · · , pn si la pro-
posición
(p1 ∧ p2 ∧ · · · ∧ pn ) → q
es una tautología.
Otra manera de representar los argumentos es haciendo un listado de las premisas y
la conclusión, separándolos con el símbolo ∴, que significa por tanto.
Decir que una forma de argumento es válida significa que no importan qué argu-
mentos particulares sean sustituidos por los enunciados variables en sus premisas, si las
premisas resultantes son todas verdaderas, entonces la conclusión también es verdadera.
Decir que un argumento es válido significa que su forma es válida.
El hecho crucial acerca de un argumento válido es que lo verdadero de su conclusión
se deduce necesariamente o inevitablemente o por la forma lógica sólo de lo verdadero
de sus premisas. Es imposible tener un argumento válido con premisas verdaderas y una
falsa conclusión. Cuando un argumento es válido y sus premisas son verdaderas, se dice
que lo verdadero de la conclusión se infiere o se deduce de lo verdadero de las premisas.
Si una conclusión “no es necesariamente así”, entonces no es una deducción válida.
Un argumento que no es válido se denomina falacia.
1.3.1. Pasos para demostrar la validez de un argumento
La prueba formal de validez consiste en deducir la conclusión del argumento en
función de sus premisas, esto es, que las premisas infieran la conclusión. A fin de que
una demostración, por la prueba formal de validez, resulte perfectamente clara, se deben
seguir los siguientes pasos:
1. Asignar variables proposicionales a cada proposición simple.
2. Realizar la traducción lógica de las premisas.
3. Organizar el argumento con sus premisas en forma vertical, escribiendo antes de
cada premisa un número de premisa consecutivo.
4. Utilizar las reglas de inferencia y/o de reemplazo que conduzcan a nuevas premisas
(inferencias).
Estas siempre deben ser antecedidas por un nuevo número de premisa. Al utilizar
las reglas se debe escribir su abreviatura y el número o números de las premisas de las
que se ha deducido.
5. El proceso de inferencia termina cuando se llega a la conclusión del argumento.
Además del proceso anterior, también es necesario considerar algunas condiciones
para la demostración:
1. Utilizar todas las premisas.
2. Utilizar todas las nuevas premisas obtenidas.
3. Es posible utilizar las premisas las veces que sean necesarias.
En el siguiente ejemplo se traducen los pasos a una tabla de verdad.
6
Ejemplo 1.4. Un principio fundamental del razonamiento lógico establece que: “Si p
implica q y q implica r, entonces p implica r.”
Solución Construimos la tabla de verdad como sigue. Hacemos primero la tabla de
la primera implicación p → q incluyendo a r
p q r p → q
V V V V V V
V V F V V V
V F V V F F
V F F V F F
F V V F V V
F V F F V V
F F V F V F
F F F F V F
Luego la de q → r
p q r q → r
V V V V V V
V V F V F F
V F V F V V
V F F F V F
F V V V V V
F V F V F F
F F V F V V
F F F F V F
Seguidamente, la de p → r
p q r p → r
V V V V V V
V V F V F F
V F V V V V
V F F V F F
F V V F V V
F V F F V F
F F V F V V
F F F F V F
Luego, la de (p → q) ∧ (q → r)
p q r (p → q) ∧ (q → r)
V V V V V V
V V F V F F
V F V F F V
V F F F F V
F V V V V V
F V F V F F
F F V V V V
F F F V V V
7
Finalmente queda la tabla
p q r ((p → q) ∧ (q → r)) → (p → r)
V V V V V V V V V V V V V V
V V F V V V F V F F V V F F
V F V V F F F F V V V V V V
V F F V F F F F V F V V F F
F V V F V V V V V V V F V V
F V F F V V F V F F V F V F
F F V F V F V F V V V F V V
F F F F V F V F V F V F V F
Lo que demuestra la tabla es que la proposición [(p → q) ∧ (q → r)] → (p → r) es
una tautología.
Ejemplo 1.5. Probar la Ley de DeMorgan ∼ (p ∨ q) ≡ ∼ p∧ ∼ q
Solución Hacemos la tabla de verdad
p q ∼ p ∼q p∨q ∼ (p ∨ q) ∼ p∧ ∼ q
V V F F V F F
V F F V V F F
F V V F V F F
F F V V F V V
en la tabla, vemos que ∼ (p ∨ q) y ∼ p∧ ∼ q tienen el mismo valor de verdad.
1.4. Predicados y cuantificadores
Un predicado o función proposicional es una declaración que contiene una o más
variables, cuya verdad o falsedad depende del valor o valores asignados a la(s) variable(s).
Sea X un conjunto dado. Un predicado o función proposicional (oración o proposición
abierta) es una expresión P (x) definida sobre X que tiene un valor de verdad para cada
x ∈ X. X se llama el dominio de la función proposicional P .
Si P (x) es un predicado y x tiene dominio X, el conjunto de verdad de P (x) es el
conjunto de todos los elementos de X que hacen a P (x) verdadera cuando se sustituyen
por x. El conjunto de verdad de P (x) se denota por {x/P (x)}.
Ejemplo 1.6. Sea P (x) “x < 0”. Observemos que hasta que no le asignemos un valor
a x, P (x) no es ni verdadera ni falsa.
P (3) es la proposición “3 < 0”, que es falsa.
Si hacemos que Q(x) sea “x2 ≥ 0”, entonces Q(3) es “32 ≥ 0”, que es verdadera.
Ejemplo 1.7. Sea Q(n) el predicado “n es un factor de 8”. Determine el conjunto de
verdad de Q(n) si
a. el dominio de n es el conjunto Z+ de todos los enteros positivos.
b. el dominio de n es el conjunto Z de todos los enteros.
Ejemplo 1.8. Determine el conjunto de verdad de P(x) si:
8
1. P (x) ”x + 2 > 7”, x ∈ Z+ .
2. P (x) “x + 5 < 3”, x ∈ Z+ .
3. P (x) “x + 5 > 1”, x ∈ Z+ .
Una forma segura de cambiar predicados en los enunciados es asignar valores espe-
cíficos a todas sus variables. Por ejemplo, si x representa el número 35, la frase “x es
(exactamente) divisible entre 5” es un enunciado verdadero ya que 35 = 5 × 7. Otra for-
ma de obtener enunciados de predicados es agregar cuantificadores. Los cuantificadores
son palabras que se refieren a las cantidades tales como “algunos” o “todos” y nos dicen
para cuántos elementos de un predicado dado es verdadero.
El símbolo ∀ denota “para todo” y se llama cuantificador universal.
Sea P (x) un predicado y X el dominio de x. Un enunciado universal es un enunciado
de la forma “∀x ∈ X, P (x)”. Se define como verdadero, si y sólo si, P (x) es verdadera
para toda x en X. Se define como falso si y sólo si P (x) es falso para al menos un x en
X. Un valor para x, para el cual P (x) es falso se llama un contraejemplo del enunciado
universal.
Ejemplo 1.9. Sea P (x) el enunciado “x + 3 > x”. ¿Cuál es el valor de verdad de la
cuantificación ∀xP (x), donde el dominio consiste en todos los números reales?
Ejemplo 1.10. Sea Q(x) el enunciado “x > 0”. ¿Cuál es el valor de verdad de la
cuantificación ∀xQ(x), donde el dominio consiste en todos los números reales?
Ejemplo 1.11. Averiguar la verdad o falsedad de la proposición (∀n ∈ N) (n + 4 > 3).
Ejemplo 1.12. Averiguar la verdad o falsedad de la proposición (∀n ∈ N) (n + 2 > 8).
Ejemplo 1.13. ¿Cuál es el valor de verdad de ∀x(x2 ≥ x) si el dominio consta de todos
los números reales? ¿Cuál es el valor de verdad de esta afirmación si el dominio consta
de todos los números enteros?
Ejemplo 1.14. El símbolo ∀ define la intersección de una colección indexada {Ai /i ∈ I}
de conjuntos Ai como sigue ∩ (Ai /i ∈ I) = {x/∀i ∈ I, x ∈ Ai }
Sea P una función proposicional con dominio X. Se dice que la afirmación existe
x, P (x) es una afirmación cuantificada existencialmente. El símbolo ∃ significa “existe”.
Así, la afirmación existe x, P (x) se escribe ∃xP (x).
El símbolo ∃ se llama cuantificador existencial.
P (x) se define como verdadero, si y sólo si P (x) es verdadero para al menos una x
en X. Es falso, si y sólo si, P (x) es falso para toda x en X.
Ejemplo 1.15. Averiguar la verdad o falsedad de la proposición (∃n ∈ N)(n + 4 < 7) .
Ejemplo 1.16. Averiguar la verdad o falsedad de la proposición (∃n ∈ N)(n + 6 < 4).
Ejemplo 1.17. Sea P (x) el enunciado “x > 3”. ¿Cuál es el valor de verdad de la
cuantificación ∃xP (x), donde el dominio consiste en todos los números reales?
Ejemplo 1.18. Sea Q(x) el enunciado “x > x + 1”. ¿Cuál es el valor de verdad de la
cuantificación ∃xQ(x), donde el dominio consiste en todos los números reales?
9
Ejemplo 1.19. El símbolo ∃ define la unión de una colección indexada {Ai /i ∈ I} de
conjuntos Ai como sigue ∪(Ai /i ∈ I) = {x/∃i ∈ I, x ∈ Ai }
Ejemplo 1.20. Considere la afirmación cuantificada existencialmente
( )
x 2
∃x =
x2 + 1| 5
con dominio R. La afirmación es verdadera porque es posible encontrar al menos un
número real x para el que la proposición dada se verifica. Por ejemplo, si x = 2, se
obtiene la proposición verdadera.
Consideremos escribir la afirmación: La suma de cualesquiera dos números reales
positivos es positiva, simbólicamente.
Primero se observa que se trata de dos números, se necesitan dos variables, digamos
x y y. La aseveración se puede reestablecer como: Si x > 0 y y > 0, entonces x + y > 0.
La afirmación dice que la suma de cualesquiera dos números reales positivos es positiva,
de manera que se necesitan dos cuantificadores universales. Así, la afirmación se escribe
simbólicamente como
∀x∀y((x > 0) ∧ (y > 0) → (x + y > 0)).
En palabras, para cada x y para cada y, si x > 0 y y > 0, entonces x + y > 0. El
dominio es el conjunto de números reales. Se dice que los cuantificadores múltiples como
∀x∀y son cuantificadores anidados.
Ejemplo 1.21. Considere la afirmación
∀x∀y((x > 0) ∧ (y < 0) → (x + y ̸= 0)),
con el conjunto de números reales como dominio. Esta afirmación es falsa porque si
x = 1 y y = −1, la proposición condicional
(x > 0) ∧ (y < 0) → (x + y ̸= 0)
es falsa. Se dice que el par x = 1 y y = −1 es un contraejemplo.
1.5. Leyes de predicados
Sean P (x) y Q (x) dos predicados. Entonces
1. ¬ (∀x/P (x)) ≡ ∃x/¬ P (x)
2. ¬ (∃x/P (x)) ≡ ∀x/¬ P (x)
3. ∀x/ (P (x) ∧ Q (x)) ≡ (∀x/P (x)) ∧ (∀x/Q (x))
4. ∃x/ (P (x) ∨ Q (x)) ≡ (∃x/P (x)) ∨ (∃x/Q (x))
5. (∀x/P (x)) ∨ (∀x/Q (x)) → ∀x/ (P (x) ∨ Q (x))
6. ∃x/ (P (x) ∧ Q (x)) → (∃x/P (x)) ∧ (∃x/Q (x))
Ejemplo 1.22. Todo número natural primo, mayor que 2 es un número impar..
10
1.6. Variables ligadas y variables libres
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 propo-
sición. Esto se puede hacer utilizando una combinación de cuantificadores universales,
cuantificadores 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 en la fórmula.
Ejemplo 1.23. En el enunciado ∃x(x + y = 1), la variable x está limitada por la
cuantificación existencial ∃x, pero la variable y es libre porque no está limitada por
un cuantificador y no se le asigna ningún valor a esta variable. Esto ilustra que en el
enunciado ∃x(x + y = 1), x está limitada, pero y es libre.
Ejemplo 1.24. En X = Z × Z se define P (x, y) : x + y = 0. Entonces
i) ∀x/x + y = 0 es un predicado en la variable y; la variable x está ligada y la variable
y está libre.
ii) ∃y/x+y = 0 es un predicado en la variable x; la variable y está ligada y la variable
x es libre.
iii) ∀x∃y/x + y = 0 es una proposición verdadera.
iv) ∃y∀x/x + y = 0, es una proposición falsa.
1.7. Hechos y reglas
Una cláusula de Horn es una secuencia de literales que contiene a lo sumo uno de sus
literales positivos (disyunción de literales). A continuación un ejemplo de una cláusula
de Horn, y se indica que una fórmula como esta también puede reescribirse de forma
equivalente como una implicación: ¬p ∨ ¬q ∨ · · · ∨ ¬t ∨ u que puede reescribirse en forma
equivalente como (p ∧ q ∧ · · · ∧ t) → u.
Un hecho es un predicado que sabemos que es verdadero. Por ejemplo, es un hecho
que supermán es un personaje de ficción.
Una regla es un conjunto de proposiciones lógicas escritas como cláusulas de Horn
que permiten inferir el valor de verdad de nuevas proposiciones, permitiendo ampliar la
base de conocimientos, a la vez que son utilizadas para definir el dominio del problema.
Por ejemplo, si humano(pepe) es un hecho, entonces mortal(x) : −humano(x) es una
regla.
Dos tipos de cláusulas son los hechos y las reglas.
1.8. Programa lógico
Un programa lógico es un conjunto de declaraciones basadas en hechos y reglas.
Algunos lenguajes de programación se han diseñado para razonar usando las reglas de
la lógica de predicados. Uno de estos es el Prolog.
11
Por ejemplo, consideremos el programa que usa los predicados prof esor(p, a) y
matriculado(c, a) para representar que el profesor p es el que da el curso a y que el
alumno c está matriculado en el curso a, respectivamente. Explícitamente, se podría
tener
profesor(delgado, mate273)
profesor(perez, análisis1)
profesor(mendoza, cc301)
matriculado(pedro, mate273)
matriculado(rosa, cc301)
matriculado(teresa, cc301)
matriculado(alfredo, mate273)
matriculado(alfredo, cc301)
Entonces, por ejemplo, un nuevo predicado enseña(p, c) se puede definir en Prolog,
haciendo uso de la regla:
enseña(p, c) : −prof esor(P, A), matriculado(C, A).
Nota: en Prolog, una coma significa conjunción, mientras que un punto y coma
indica una disyunción.
Prolog es un lenguaje de programación especialmente indicado para modelar pro-
blemas que impliquen objetos y las relaciones entre ellos. Está basado en los siguientes
mecanismos básicos: unificación, estructuras de datos basadas en árboles y backtracking
automático. La sintaxis del lenguaje incluye la declaración de hechos, preguntas y re-
glas. Con la definición de este pequeño conjunto de conceptos se consigue un lenguaje
de programación muy potente y flexible, ampliamente utilizado (junto con el lenguaje
de programación LISP) en aplicaciones que utilizan técnicas de Inteligencia Artificial.
La idea es que en lugar de darle a la máquina instrucciones de cómo hacer algo, sim-
plemente le damos algunas reglas lógicas y hechos y el sistema deduce las soluciones. Por
último, se le pregunta si existe alguna serie de movimientos que resuelvan ese problema
y, por arte de magia, te responde. No es, por supuesto, magia. Prolog usa las reglas de
la lógica para razonar y ver cuál es la solución. De esta forma, se evita tener que decirle
cómo resolver la pregunta. Puede parecer un ahorro trivial, pero no lo es cuando se tiene
montones de hechos, reglas y preguntas posibles: un sistema lógico puede enfrentarse a
preguntas que su creador ni siquiera habría imaginado. La lógica difusa permite trabajar
con conceptos imprecisos como ”mucho frío” o ”llueve poco”.
Un simple programa Prolog se compone de un conjunto de enunciados que describen
una situación, junto con preguntas acerca de la situación. Para construirlo en el len-
guaje se requieren técnicas de búsqueda e inferencia para responder las preguntas que
se deducen de las respuestas de los enunciados dados. Esto libera al programador de
la necesidad de tener que escribir programas distintos para responder a cada tipo de
pregunta.
12
1.9. Ejercicios
1. Supongamos que x es un número real particular. Sea que p, q y r, simbolicen
“0 < x”, “x ≤ 3” y “x = 3”, respectivamente. Escriba las siguientes desigualdades
simbólicamente: a.) x ≤ 3 b.) 0 < x < 3 c.) 0 < x ≤ 3
2. Construya una tabla de verdad para la forma de enunciado (p ∧ q) ∨ ∼ r.
3. Construya la tabla de verdad para la forma de enunciado (p ∨ q) ∧ ∼ (p ∧ q).
4. Probar que
(p ∧ q) ∨ p ⇔ p
usando una tabla de verdad.
5. Probar, usando tablas de verdad, que las proposiciones (p ∧ q)∨r y (p ∨ r)∧(q ∨ r)
no son equivalentes.
6. Demuestre que las formas de enunciado ∼ (p ∧ q) y ∼ p ∧ ∼ q no son lógicamente
equivalentes.
7. Construir la tabla de verdad de la proposición compuesta: Pedro no vino a clase
y no pudo hacer la tarea.
8. Dados los argumentos: “Si Alfredo es elegido presidente de la asociación de co-
lonos, entonces Leandro es elegido vicepresidente y Pedro es elegido tesorero”.
“Leandro no es elegido vicepresidente, por tanto Alfredo no es elegido presidente
de la asociación de colonos”, verificar su validez por tablas de verdad.
9. Considerar el siguiente argumento: “Si Pedro estudia, entonces aprobará lógica y
geometría. Pedro no aprobó lógica, en consecuencia, Pedro no estudió y no aprobó
geometría”. Verificar su validez por tablas de verdad.
10. Considerar el siguiente argumento: “Si la ley no fue aprobada, entonces la cons-
titución del país queda sin modificaciones. Si la constitución del país queda sin
modificaciones no se puede elegir nuevos congresistas. O se eligen nuevos congre-
sistas o el informe del presidente del país se retrasará. El informe no se retrasó un
mes. Por lo que la ley fue aprobada”. Verificar su validez usando prueba formal de
validez.
11. Si t es una tautología y c es una contradicción, demuestre que p ∧ t ≡ p y p ∧ c ≡
c.
12. Sea
Q(n) : “n es un f actor de 8”,
R(n) : “n es un f actor de 4”,
S(n) : “n < 5 y n ̸= 3”
y supongamos que el dominio es n ∈ Z+ , el conjunto de los enteros positivos.
Utilice los símbolos ⇒ y ⇔ para indicar las relaciones verdaderas entre Q(n),
R(n) y S(n).
13
