apítulo 1

Chapter

Introducción y Fundamentos

1.1 Introducción. Enunciado y Proposición Lógica

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.
Consideremos, por ejemplo, las seis oraciones siguientes:
i) La madera flota en el agua.
ii) Perú está en Norteamérica.
iii) 3 + 3 = 6.
iv) 1 + 3 = 5.
v) ¿A dónde vas?
vi) Haz tu trabajo.
Las cuatro primeras son proposiciones; las dos últimas, no. También, i) y iii) son
verdaderas, pero ii) y iv) 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.
Se usan variables, como p, q y r, para representar las proposiciones, como se usan
letras en álgebra para representar números. Ası́, es posible utilizar una proposición ha-
ciendo 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 proposi-
cional. 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.
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

2
1.2 Tautologı́a y Contradicción. Implicación. Proposi-
ciones 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
Dos formas de enunciado se llaman lógicamente equivalentes si y sólo si, tienen los
mismos valores de verdad para cada posible sustitución de enunciados por sus enunciados
de variables. La equivalencia lógica de las formas de enunciado p y q se denota escribiendo
p ≡ q.
Dos enunciados se llaman lógicamente equivalentes si y sólo si, tienen formas lógicas
equivalentes cuando componentes idénticos de enunciados variables se utilizan para reem-
plazar los enunciados compuestos idénticos.
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.

3
 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

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.

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 negació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

4
 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.
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
proposició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 Reglas de inferencia

Las reglas de inferencia son formas de argumentos cuya validez puede ser demostrada
por tablas de verdad; además, estas reglas permiten establecer conclusiones muy bien
formadas y válidas a partir de otras premisas. En general son usadas para analizar los
argumentos con muchas premisas o cuando se tienen cuatro o más proposiciones simples.

5
 Una forma de argumento que consiste en dos premisas y una conclusión se le llama
un silogismo. La primera y segunda premisas se llaman la premisa mayor y la premisa
menor, respectivamente.

1. Modus ponens
Permite eliminar el antecedente siempre que la segunda premisa sea dicho an-
tecedente.
p→q
p
∴q

El término modus ponens en latı́n significa “método de afirmación” (la conclusión

es una afirmación). Mucho antes de que viera su primera tabla de verdad, sin
duda, que se convenció con argumentos de esta forma. Sin embargo, es instructivo
demostrar que el modus ponens es una forma válida de argumento si no hay otra
razón que la de confirmar el acuerdo entre la definición formal de validez y el
concepto intuitivo. Para hacer esto, se construye una tabla de verdad para las
premisas y la conclusión.

2. Modus tollens
Permite eliminar el consecuente siempre y cuando esté negado en la segunda
premisa,
p→q
∼ q
∴∼ p
dando como consecuencia el antecedente negado.
Modus tollens es latı́n y significa “método de la negación” (la conclusión es una
negación). La validez del modus tollens es que se puede demostrar que se deduce del
modus ponens, junto con el hecho de que un enunciado condicional es lógicamente
equivalente a su contrapositivo. O se puede establecer formalmente usando una
tabla de verdad.

3. Silogismo disyuntivo
Permite eliminar una de las dos disyunciones siempre que una de las dos esté
negada en la segunda premisa.
p∨q
∼p
∴q

4. Silogismo hipotético
Permite eliminar el consecuente de la primera premisa y el antecedente de la se-
gunda premisa, siempre y cuando sean iguales.

p→q
q→r
∴p→r

6
 5. Adición
Permite agregar las variables proposicionales que se necesiten.

p
∴p∨q

6. Simplificación
Permite eliminar las variables proposicionales que no se necesiten.

p∧q
∴p

1.3.2 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.

Ejemplo 1.4. Un principio fundamental del razonamiento lógico establece que

“Si p implica q y q implica r, entonces p implica r.”

Demostrar que este principio es una tautologı́a.

Solución Construimos la tabla de verdad como sigue. Hacemos primero la tabla de

7
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

8
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. Averiguar si el siguiente argumento es válido o no
p → q∨ ∼ r
q → p∧r
∴ p→r
Solución Hacemos la tabla de verdad
p q r ∼ r q∨ ∼ r p∧r p → q∨ ∼ r q →p∧r p→r
V V V F V V V V V
V V F V V F V F
V F V F F V F V
V F F V V F V V F
F V V F V F V F
F V F V V F V F
F F V F F F V V V
F F F V V F V V V
en la tabla, la antepenúltima y la penúltima columnas son las premisas, la última columna
es la conclusión. En ella se ve que en la fila 4 las premisas son verdaderas y la conclusión
es falsa. Las otras son verdaderas. Se concluye que la forma de argumento es no válido.

1.4 Predicados y cuantificadores

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 . Es decir
P : X → {V, F }
x 7→ P (x)
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)}.

9
Ejemplo 1.6. 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.
Solución
a. El conjunto de verdad es {1, 2, 4, 8} ya que éstos son exactamente los enteros
positivos que dividen a 8 de manera exacta.
b. El conjunto de verdad es {1, 2, 4, 8, −1, −2, −4, −8} porque los enteros negativos
−1, −2, −4 y −8 también se dividen entre 8 sin dejar residuo.
Ejemplo 1.7. Sea P (x) ”x + 2 > 7”, x ∈ Z+ . Su conjunto de verdad es {6, 7, 8, ...},
que consta de todos los enteros mayores que 5.
Ejemplo 1.8. Sea P (x) “x + 5 < 3”, x ∈ Z+ . Su conjunto de verdad es el conjunto
vacı́o ∅. Es decir, P (x) no es verdadera para ningún entero en Z+ .
Ejemplo 1.9. Sea P (x) “x + 5 > 1”, x ∈ Z+ . Su conjunto de verdad es Z+ . Es decir,
P (x) es verdadera para todo elemento en Z+ .
Una forma segura de cambiar predicados en los enunciados es asignar valores es-
pecı́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
forma de obtener enunciados de predicados es agregar cuantificadores. Los cuantifi-
cadores 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.10. La proposición (∀n ∈ N) (n + 4 > 3) es verdadera puesto que {n/n+4 >
3} = {1, 2, 3, ...} = N.
Ejemplo 1.11. La proposición (∀n ∈ N) (n + 2 > 8) es falsa puesto que {n/ n + 2 >
8} = {7, 8, ...} 6= N.
Ejemplo 1.12. 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.

10
Ejemplo 1.13. La proposición (∃n ∈ N)(n + 4 < 7) es verdadera puesto que {n/n + 4 <
7} = {1, 2} 6= ∅ .

Ejemplo 1.14. La proposición (∃n ∈ N)(n + 6 < 4) es falsa puesto que {n/n + 6 <
4} = ∅ .

Ejemplo 1.15. 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.16. 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.17. Considere la afirmación

∀x∀y((x > 0) ∧ (y < 0) → (x + y 6= 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 6= 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)

11
 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.18. Todo número natural primo, mayor que 2 es un número impar.
Prueba. Pongamos P (x) : x es un número primo mayor que 2 y Q (x) : x es un
número impar. Ası́, la firmación la podemos escribir en la forma

∀x ∈ N, P (x) → Q (x)

La negación es
∃x ∈ N, P (x) ∧ ∼ Q (x)
esto es, se supone que existe unh número natural x que es primo y mator que 2, y que
no es impar. Supongamos que es cirta la negación. Entonces, como x no es impar, x
debe ser par y, por lo tanto 2 divide a x. Pero x es primo, sus únicos divisores son 1 y
el mismo; y como x es mayor que 2, 2 no es un divisor; es decir, 2 no divide a x; esto
da ∼ R (x) es decir

∼ (∀x ∈ N, P (x) → Q (x)) → R (x) ∧ ∼ R (x)

es una contradicción. En consecuencia la afirmación dada es verdadera.

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 proposició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.19. 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.

12
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 batman 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.
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 pede 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 prob-
lemas 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 backtrack-
ing automático. La sintaxis del lenguaje incluye la declaración de hechos, preguntas y
reglas. 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.
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 lenguaje

13
se requieren técnicas de búsqueda e inferencia para responder las preguntas que se de-
ducen 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 pre-
gunta.

14
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 colonos,
entonces Bernardo es elegido vicepresidente y Carlos es elegido tesorero”. “Bernardo
no es elegido vicepresidente, por tanto Alfredo no es elegido presidente de la aso-
ciación de colonos”, verificar su validez por tablas de verdad.
9. Considerar el siguiente argumento: “Si Enrique estudia, entonces aprobará lógica
y geometrı́a. Enrique no aprobó lógica, en consecuencia, Enrique 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 con-
stitució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 6= 3”
y supongamos que el dominio de 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).

15