APUNTES DE LÓGICA

PROPOSICIONAL Y PREDICADOS DE
PRIMER ORDEN
TÉCNICAS BÁSICAS DE PRUEBA

LÓGICA Y ESTRUCTURAS DISCRETAS

UNED
Contenido:
Introducción ................................................................................... 3 
I. Lógica Proposicional .................................................................. 5 
1.  EL LENGUAJE, SINTAXIS Y SEMÁNTICA. EQUIVALENCIA ........................... 5 
1.1  Cómo generar y analizar fórmulas proposicionales ......................................5 
1.1.1  Alfabeto y reglas sintácticas de formación.............................................................. 5 
1.1.2  El lenguaje de la Lógica Proposicional .................................................................. 5 
1.1.3  Árboles de análisis sintáctico .................................................................................. 6 
1.1.4  Variaciones Sintácticas ............................................................................................ 7 
1.2  El significado, cómo de verdadera es una fórmula .......................................8 
1.2.1  Constantes y negaciones .......................................................................................... 8 
1.2.2  Conjunciones y Disyunciones .................................................................................. 9 
1.2.3  Condicionales y Bicondicionales ............................................................................. 9 
1.2.4  Propagación funcional: valor de verdad de una fórmula compleja ..................... 10 
1.2.5  Eliminación de paréntesis ...................................................................................... 11 
1.2.6  Tabla de verdad de una fórmula ............................................................................ 12 
1.2.7  Número de interpretaciones distintas .................................................................... 12 
1.2.8  Satisfacción de un conjunto de fórmulas ............................................................... 12 
1.3  Equivalencia ...............................................................................................13 
1.3.1  Equivalencia: Definición y Propiedades ............................................................... 13 
1.3.2  Equivalencias básicas ............................................................................................ 15 
1.3.3  Generación de equivalencias por reemplazo ........................................................ 16 
1.3.4  Formas normales ................................................................................................... 18 
2.  VALIDEZ Y SATISFACIBILIDAD. CÁLCULO (TABLEAUX) ............................ 21 
2.1  Satisfacibilidad de un conjunto de fórmulas ...............................................21 
2.1.1  Expandir/reducir un conjunto satisfacible/insatisfacible...................................... 23 
2.1.2  Satisfacibilidad y equivalencia. Satisfacibilidad y conjunción ............................. 25 
2.2  Tautologías y contradicciones ....................................................................25 
2.3  Cálculo de insatisfacibilidad: Tableaux ......................................................28 
2.3.1  Introducción ........................................................................................................... 28 
2.3.2  Expansión de un tableaux con conjunciones y disyunciones ................................ 30 
2.3.3  Expansión de los nodos en un tableaux con otras conectivas............................... 32 
2.3.4  Tableaux cerrado. Conjunto insatisfacible de fórmulas ....................................... 33 
3.  CONSECUENCIA: CÁLCULO (DEDUCCIÓN NATURAL).............................. 38 
3.1  Consecuencia. Definición, propiedades y relaciones con otros conceptos .38 
3.1.1  Definición ............................................................................................................... 38 
3.1.2  Propiedades. Reflexiva y Transitiva. Monotonía .................................................. 39 
3.1.3  Consecuencia y condicionales tautológicos .......................................................... 41 
3.1.4  Consecuencia e insatisfacibilidad ......................................................................... 42 
3.2  Cálculo de consecuencias: Deducción Natural ...........................................43 
3.2.1  Conjunción. Regla introducción (E) y eliminación (I) ...................................... 43 
3.2.2  Condicional. Regla eliminación (E). Regla introducción (I).......................... 43 
3.2.3  Disyunción. Regla introducción (I). Regla eliminación (E) .............................. 45 
3.2.4  Bicondicional. Regla eliminación (E). Regla introducción (I) ...................... 46 
3.2.5  Negación. Regla introducción y eliminación ........................................................ 48 

II. Lógica de Predicados .............................................................. 49 

4.  EL LENGUAJE. SINTAXIS Y SEMÁNTICA. EQUIVALENCIA ......................... 49 
4.1  Predicados con términos constantes ...........................................................49 
4.1.1  Predicados monádicos con términos constantes. Sintaxis y semántica ................ 49 
4.1.2  Predicados diádicos con términos constantes. Sintaxis y semántica .................... 52 
1
 4.2  Predicados con términos variables y cuantificadores .................................56 
4.2.1  Cuantificadores y variables ................................................................................... 56 
4.2.2  Ejemplos de interpretación de predicados monádicos .......................................... 58 
4.2.3  Ejemplos de interpretación de predicados diádicos ............................................. 62 
4.3  Predicados con términos con funciones y uso de la identidad ....................68 
4.3.1  Funciones en los términos ..................................................................................... 68 
4.3.2  Identidad ................................................................................................................ 69 
4.3.3  La sintaxis de la lógica de primer orden ............................................................... 70 
4.4  Equivalencia entre fórmulas de lógica de predicados .................................71 
4.4.1  Primeras equivalencias básicas para predicados ................................................. 71 
4.4.2  Segundas equivalencias básicas para predicados ................................................ 72 
4.4.3  Conjunción de cuantificadores universales y disyunción de existenciales ........... 74 
5.  VALIDEZ Y SATISFACIBILIDAD: CÁLCULO (TABLEAUX) ........................... 75 
5.1  Satisfacibilidad y validez............................................................................75 
5.2  Tableaux para fórmulas de lógica de predicados ........................................76 
5.2.1  Introducción ........................................................................................................... 76 
5.2.2  Reglas de expansión de los nodos en un tableaux ................................................. 79 
5.2.3  Tableaux con cuantificadores. Ejemplo ................................................................ 80 
6.  CONSECUENCIA: CÁLCULO (DEDUCCIÓN NATURAL).............................. 82 
6.1  Consecuencia en predicados .......................................................................82 
6.2  Deducción Natural: Introducción y eliminación de cuantificadores ...........83 
6.2.1  Introducción ........................................................................................................... 83 
6.2.2  Cuantificadores universales .................................................................................. 83 
6.2.3  Cuantificadores existenciales ................................................................................ 84 

Resumen ....................................................................................... 86 

2
 INTRODUCCIÓN

Estos apuntes están tomados de las clases virtuales del profesor José Luis
Fernández Vindel, titular de la asignatura de Lógica y Estructuras
Discretas que se imparte en el primer cuatrimestre de primero del Grado de
Ingeniería Informática y en el Grado de Ingeniería en Tecnologías de la
Información de la UNED.

El objetivo que me ha llevado a confeccionar estos apuntes no es otro que

proporcionar una ayuda al estudio de la asignatura, son un complemento a
los contenidos impartidos en las clases virtuales. Por esa razón he querido
incluir en los mismos una gran cantidad de esquemas e ilustraciones
confeccionadas a partir de las capturas de pantalla de dichas clases.

Espero que sirvan de apoyo a quienes estudien está asignatura, y si existe

alguna errata por favor indicarla y podré corregirla.

Juan Miguel Suay Belenguer

jsuay1@alumno.uned.es
Invierno 2013

3
4
 I. LÓGICA PROPOSICIONAL

1. EL LENGUAJE, SINTAXIS Y SEMÁNTICA. EQUIVALENCIA

1.1 CÓMO GENERAR Y ANALIZAR FÓRMULAS PROPOSICIONALES
1.1.1 Alfabeto y reglas sintácticas de formación

Definición de la sintaxis de la Lógica de Proposiciones:

1) ALFABETO:

a) Infinitas letras proposicionales: p1, p2, p3,…

b) Símbolos lógicos: Constantes: ( , ), conectiva monaria (¬),

conectivas binarias (˄, ˅, →, ↔).

c) Símbolos auxiliares de puntuación: paréntesis izquierdo ( y

derecho).

2) REGLAS DE FORMACIÓN:

a) Las proposiciones atómicas son fórmulas (pk)

b) La negación de una fórmula previa es una fórmula (   )

c) La composición binaria de dos fórmulas previas es una fórmula

(   )

El uso correcto de estas reglas produce siempre expresiones que

aceptaremos como fórmulas, bien formadas.

1.1.2 El lenguaje de la Lógica Proposicional

A partir del alfabeto se pueden construir expresiones, entendidas estas

como secuencias de caracteres del alfabeto. No todas ellas se aceptarán
como fórmulas proposicionales. Como mínimo, sabemos que si las
producimos mediante las reglas de generación resultarán indiscutiblemente
correctas, aceptables. En la Fig. 1 vemos que solo el subconjunto de todas
las fórmulas que se pueden construir con el alfabeto que siguen las reglas
de formación son fórmulas válidas en nuestro lenguaje

5
 Fig. 1 Formulas válidas según las reglas establecidas

Además, descartamos que las fórmulas puedan ser producidas de otra

forma (que podría ocurrir, por ejemplo, las secuencias que no se han
producido con estas reglas pero se han generado los martes.). Es decir:
'aceptables sólo si reglas'. En este caso, si alguien nos facilita una fórmula
sabemos exactamente qué tipo de estructura interna deben tener

1.1.3 Árboles de análisis sintáctico

Fig. 2 Descomposición semántica

6
Dada una fórmula no atómica, es posible determinar la conectiva empleada
en su último paso de generación. Si fue una negación (conectiva monaria),
se aplicó a una fórmula previa. Y si fue una conectiva binaria, a dos
fórmulas previas. A esta o estas fórmulas previas se las denomina
subfórmulas inmediatas de la fórmula analizada.

Y en cada una de estas subfórmulas inmediatas, como fórmulas que son, se

puede ejecutar el mismo proceso de descomposición sintáctica (Fig. 2).

La representación gráfica y completa de este proceso se denomina árbol

sintáctico de la fórmula (Fig. 3).

Fig. 3 Árbol sintáctico

1.1.4 Variaciones Sintácticas

Los símbolos que componen el vocabulario no siempre son exactamente los

mismos en unos textos u otros. La relación entre convenios distintos se
hace a través del significado pretendido del símbolo: la conjunción (y en
lenguaje natural) se expresa de una forma u otra, pero se mantiene un
mismo uso.

Al igual que ocurre entre las codificaciones de la conjunción en lenguajes

naturales distintos (y, and, et,...). En la siguiente tabla se muestran otros
convenios de las conectivas y las constantes lógicas.

7
 Negación ¬  ! ¬ p1 No p1
Conjunción ˄ & · p1 ˄ p2 p1 y p2
Disyunción ˅ | + p1 ˅ p2 p1 o p2
Condicional →   p1 → p2 Si p1 entonces p2
Bicondicional ↔   p1 ↔ p2 p1 si y solo si p2

Verdadero 0 Verdadero

Falso 1 Falso

1.2 EL SIGNIFICADO, CÓMO DE VERDADERA ES UNA FÓRMULA

1.2.1 Constantes y negaciones

Fig. 4 Valores de verdad de una proposición y las constantes lógicas

Cada proposición se puede evaluar como verdadera o falsa. Si se ha

escogido evaluar una proposición (p) como verdadera estamos
formalmente obligados a evaluar como falsa la proposición compleja (¬ p).
Además de ilimitadas proposiciones (pk), que admiten ser interpretadas
como verdadera o falsa, reservamos dos nombres especiales de

8
proposición: ( ) que sólo se puede interpretar como verdadera y ( ) como
falsa (Fig. 4).

1.2.2 Conjunciones y Disyunciones

Conjunción: la expresión esto y lo otro (p ˄ q) sólo es verdadera en uno de

los cuatro casos posibles, cuando ambas componentes son verdaderas.

Fig. 5 Valores de verdad de la conjunción y disyunción

Disyunción: la expresión esto o lo otro (p ˅ q) sólo es falsa en uno de los

cuatro casos posibles, cuando ambas componentes son falsas.

1.2.3 Condicionales y Bicondicionales

Condicional: la expresión (p → q) sólo es falsa en uno de los cuatro casos

posibles, cuando la componente izquierda (antecedente) es verdadera y sin
embargo la componente derecha (consecuente) es falsa.

Bicondicional: (p ↔ q) es verdadero cuando ambas componentes, a

derecha e izquierda, coinciden en valor (ambas falsas o ambas verdaderas).

Fig. 6 Valores de verdad de la condicional y bicondicional

9
1.2.4 Propagación funcional: valor de verdad de una fórmula
compleja

El valor de verdad de una proposición compleja está absolutamente

determinado por el valor de verdad de las proposiciones atómicas (es decir,
por la interpretación escogida para esas proposiciones) y por las conectivas
utilizadas. Una forma de calcular ese valor resultante es asignar la
interpretación a los nodos finales de su árbol sintáctico y propagar ese
valor hacia arriba. Como si fuera un circuito electrónico y cada conectiva
produjese el resultado esperado en cada paso.

Fig. 7 Satisfacibilidad de la fórmula  ante la interpretación I

Sea la formula  representada en la Fig. 7, ante una interpretación:

I = {p3 = 0; p2 = 1; p4 = 1}

Propagando el valor por el árbol obtenemos que  es verdadera ante esa

interpretación, entonces decimos que I satisface a , y se representa por:

I 

Si ahora tomamos otra interpretación para la misma fórmula (Fig. 8):

I = {p3 = 0; p2 = 1; p4 = 0}

10
 Fig. 8 Insatisfacibilidad de la fórmula  ante la interpretación I’

En este caso se dice que I’ no satisface a , y se representa por:

I 

1.2.5 Eliminación de paréntesis

Eliminar paréntesis produce ambigüedad en la interpretación sintáctica: hay

varias opciones posibles de lectura. Se propone un convenio para que, en
estos casos, se sepa exactamente cuál de las opciones se asume en caso de
duda. Una parte del convenio se basa en la precedencia en las conectivas:
en caso de duda, qué conectiva ha decidido que se aplica antes

Otra parte del convenio se basa en la asociatividad de la conjunción y de la

disyunción. Por ejemplo: ((p ˄ q) ˄ r) siempre se va a evaluar, en toda
interpretación, igual que (p ˄ (q ˄ r)); así que podemos expresarlo como (p
˄ q ˄ r). Sintácticamente ambiguo, pero semánticamente no.

p˅q˅r  (p ˅ q ˅ r)  ((p ˅ q) ˅ r), (p ˅ (q ˅ r))

p˄q˄r  (p ˄ q ˄ r)  ((p ˄ q) ˄ r), (p ˄ (q ˄ r))

Criterio de precedencia de las conectivas:

¬>˄>˅>→>↔
¬r ˄ s  ((¬r) ˄ s) ≠ ¬(r ˄ s)
p˅q˄r  (p ˅ (q ˄ r)) ≠ ((p ˅ q ) ˄ r)

11
 r˅q→r  ((r ˅ q ) → r)) ≠ (r ˅ (q → r))
q ↔ r →p  (q ↔ (r →p)) ≠ ((q ↔ r) → p)

1.2.6 Tabla de verdad de una fórmula

Dada una interpretación (para sus componentes atómicas), se obtiene un

valor de verdad final para la fórmula analizada. La tabla de verdad de una
fórmula es un listado exhaustivo de todas sus posibles interpretaciones y
del valor resultante en cada una de ellas.

Fig. 9 Ejemplo de tabla de verdad

1.2.7 Número de interpretaciones distintas

Este vídeo muestra cómo generar las diferentes interpretaciones posibles,

que resultan siempre ser un número calculable a partir del número de letras
proposicionales de la fórmula. Suponga que una fórmula contiene n letras
proposicionales distintas. Con independencia de que algunas se repitan, y
sin incluir entre ellas a las proposiciones atómicas constantes ( ) y ( ). Esa
fórmula admite 2n interpretaciones (líneas de su tabla de verdad) distintas.

1.2.8 Satisfacción de un conjunto de fórmulas

Es posible expresar, a la vez, varios enunciados sobre el mundo: un

conjunto de fórmulas. Una interpretación adecuada a este conjunto tendrá
toda la información necesaria para evaluarlas. Es decir, asignará un valor
12
de verdad a cada una de las proposiciones atómicas que aparezcan en un
punto u otro de ese conjunto de fórmulas. Cuando esa interpretación hace
verdaderas todas las fórmulas del conjunto, diremos que esa interpretación
satisface el conjunto.

Por ejemplo, sea el conjunto  tres fórmulas (1, 2, 3):

 = {1 = (p → (q ˅ r)); 2 = (p ˄ q) ˅ r)); 3 = (q → (r ˅ p))}

La tabla de verdad para cada una de ellas será:

p q r (p → (q ˅ r)) (p ˄ q) ˅ r)) (q → (r ˅ p))

I1 1 1 1 1 1 1 I1 
I2 1 1 0 1 1 1 I2 
I3 1 0 1 1 1 1 I3 
I4 1 0 0 0 0 1 I4 
I5 0 1 1 1 1 1 I5 
I6 0 1 0 1 0 1 I6 
I7 0 0 1 1 1 1 I7 
I8 0 0 0 1 0 1 I8 

Luego las interpretaciones (I4, I6, I8) son insatisfacibles, ya que no

satisfacen al menos una de las fórmulas del conjunto.

1.3 EQUIVALENCIA
1.3.1 Equivalencia: Definición y Propiedades

Definición de equivalencia: Dos fórmulas X e Y son equivalentes cuando

producen exactamente el mismo valor de verdad (ambas falsas o ambas
verdaderas), 'línea a línea', interpretación a interpretación, respecto a cada
una de sus interpretaciones comunes. Es decir, cuando presentan la misma
tabla de verdad, en lógica de proposiciones. Simbólicamente, esta relación
entre fórmulas se expresa como:

X≡Y

13
Donde el símbolo ≡ no es una nueva conectiva sino una abreviatura de X
es equivalente a Y.

Supongamos que se nos facilitan dos fórmulas supuestamente equivalentes.

O que hemos generado una a partir de otra, mediante un cálculo que
debiera producir una fórmula equivalente a la primera. Siempre hay, entre
otros, un procedimiento de confirmar que se está trabajando correctamente:
escriba toda la tabla de verdad conjunta de ambas fórmulas y compruebe
que es la misma. Por ejemplo, de las siguientes cuatro fórmulas hay tres
equivalentes entre sí, y una que no es equivalente a ellas:

p q (p → q) (¬p ∨ q) (¬q→¬p) (q → p)
1 1 1 1 1 1
1 0 0 0 0 1
0 1 1 1 1 0
0 0 1 1 1 1

En términos coloquiales, podemos decir que dos fórmulas proposicionales

son equivalentes si tienen exactamente la misma tabla de verdad. Y poseen
las siguientes propiedades:

 Reflexiva: Toda fórmula es equivalente a sí misma.

X≡X

 Simétrica: Si una fórmula es equivalente a otra, también es cierto

en el sentido contrario.

X≡Y → Y≡X

 Transitiva: Si una fórmula es equivalente a una segunda fórmula, y

ésta a una tercera, resultan ser equivalentes también la primera y la
tercera.

(X≡Y ˄ Y≡Z) → X≡Z

Toda fórmula tiene una determinada tabla de verdad, si consideramos otras

fórmulas que tienen exactamente la misma tabla, es decir que son

14
equivalentes a la fórmula dada y equivalentes entre sí, diremos que formas
una determinada clase de equivalencia.

1.3.2 Equivalencias básicas

Doble negación:

¬¬X ≡ X

Disyunción o conjunción consigo misma (quizá negada) o con ,

X ∨ X ≡ X X ∨ ¬X ≡
X ∧ X ≡ X X ∧ ¬X ≡

X ∨ ≡ X X ∨ ≡
X ∧ ≡ X X ∧ ≡

Propiedades conmutativa, asociativa y distributiva:

X ∨ Y ≡ Y ∨ X X ∨ (Y ∨ Z)≡(X ∨ Y) ∨ Z
X ∧ Y ≡ Y ∧ X X ∧ (Y ∧ Z) ≡ (X ∧ Y) ∧ Z

X ∨ (Y ∧ X) ≡ X X ∨ (Y∧ Z) ≡ (X ∨ Y) ∧ (X ∨ Z)
X ∧ (Y ∨ X) ≡ X X ∧ (Y ∨ Z) ≡ ( X ∧ Y) ∨ (X ∧ Z)

Leyes de De Morgan, condicionales, bicondicionales:

¬(X ∧ Y) ≡ (¬X ∨¬Y) ¬(X ∨ Y) ≡ (¬X ∧¬Y)

X→Y ≡ ¬X ∨ Y X→Y ≡ ¬Y →¬X

X↔Y ≡ (X→Y) ∧ (Y→X) X↔Y ≡ (X ∧ Y)∨(¬X ∧ ¬Y)

15
1.3.3 Generación de equivalencias por reemplazo

A partir de una fórmula cualquiera y de la tabla de equivalencias básicas, se

construye una fórmula equivalente a la primera, por reemplazo de una de
sus subfórmulas.

Por ejemplo, sabiendo que (p → q) ≡ (¬p ∨ q), puede utilizarse para

construir una fórmula equivalente a:

(r ∨ (p → q)) ∧ ¬(p → q)

Por ejemplo, sustituyendo la segunda de las subfórmulas (p → q) por su

equivalente (¬p ∨ q), tenemos la fórmula:

(r ∨ (p → q)) ∧ ¬(¬p ∨ q)

Que hace que sea equivalente a la primera:

[(r ∨ (p → q)) ∧ ¬(p → q)] ≡ [(r ∨ (p → q)) ∧ ¬(¬p ∨ q)]

Las equivalencias se mantienen incluso entre fórmulas más complejas. Es

decir, seguirá siendo cierto que (X→Y) ≡ (¬X ∨ Y) aunque X e Y sean
fórmulas más complejas. Por ejemplo, si X es (r ∧ s) e Y es (p ∨ s),
compruebe que:

[(r ∧ s)→(p ∨ s)] ≡ [(¬(r ∧ s)) ∨ (p ∨ s)]

Veamos a continuación, un ejemplo de aplicación del método del

reemplazo en fórmulas proposicionales. A partir de la siguiente fórmula
inicial:

¬((p → q)) ∨ ¬q)

Se puede generar una cadena de fórmulas equivalentes. Como por ejemplo

la siguiente:

16
Cadena de equivalencia Equivalencia empleada

¬((p → q)) ∨ ¬q) X→Y≡¬X ∨ Y

≡

¬((¬p ∨ q)) ∨ ¬q)

¬(X∨Y)≡(¬X∧¬Y)
≡

(¬(¬p ∨ q)) ∧ ¬¬q)

¬¬X≡X
≡

(¬(¬p ∨ q)) ∧ q)
¬(X∨Y)≡(¬X∧¬Y)
≡

((¬¬p ∧ ¬q) ∧ q)
¬¬X≡X
≡

((p ∧ ¬q) ∧ q)
(X∧Y)∧Z ≡ X∧(Y∨Z)
≡

(p ∧ (¬q ∧ q))
X ∧ ¬X≡
≡

(p ∧ )
X ∧ ≡
≡

17
1.3.4 Formas normales

Se denomina literal (L) a toda fórmula atómica o a su negación (q, ¬q).

Una forma normal conjuntiva es aquella que está escrita como una
conjunción de disyunciones de literales:

(L11 ∨ … ∨ L1n) ∧ … ∧ (Lm1 ∨ … ∨ Lmn)

Por ejemplo: (¬p ∨ q ∨ r) ∧ (p ∨ q ∨ ¬r)

Una forma normal disyuntiva es aquella que está escrita como una
disyunción de conjunciones de literales:

(L11 ∧ … ∧ L1n) ∨ … ∨ (Lm1 ∧ … ∧ Lmn)

Por ejemplo: (¬p ∧ q ∧ r) ∨ (p ∧ q ∧ ¬r)

Toda fórmula proposicional puede reescribirse equivalentemente en forma

normal conjuntiva, así como en forma normal disyuntiva. Para ello basta:

1) Eliminar bicondicionales, reescribiéndolos equivalentemente:

X↔Y ≡ (X→Y) ∧ (Y→X)

2) Luego hay que eliminar condicionales, reescribiéndolos como no

antecedente o consecuente:

X→Y ≡ ¬X ∨ Y

3) Luego hay que introducir todas las negaciones hasta que afecten
sólo a letras proposicionales (no a paréntesis más complejos):

¬(X ∧ Y) ≡ (¬X ∨¬Y)

¬(X ∨ Y) ≡ (¬X ∧¬Y)

4) Eliminación de las dobles negaciones:

¬¬X ≡ X

5) Finalmente hay que aplicar la propiedad distributiva para obtener

paréntesis todos ellos con conjunciones o todos ellos con

18
 disyunciones (dependiendo de que se busque la forma normal
disyuntiva o conjuntiva).

X ∧ (Y ∨ Z) ≡ (X ∧ Y) ∨ (X ∧ Z)

X ∨ (Y∧ Z) ≡ (X ∨ Y) ∧ (X ∨ Z)

Por ejemplo, si tenemos la siguiente fórmula:

(p ↔ ¬q) ˅ r

Y queremos hallar forma normal conjuntiva, seguimos los pasos señalados:

Paso
(p ↔ ¬q) ˅ r (1)
≡ ((p → ¬q) ∧ (¬q →p)) ˅ r
≡ r ˅ ((p → ¬q) ∧ (¬q →p))
≡ (r ˅ (p → ¬q) ∧ (r ˅ (¬q →p) (2)
≡ (r ˅ (¬p ˅ ¬q )) ∧ (r ˅ (¬¬q ˅ p)) (4)
≡ (r ˅ ¬p ˅ ¬q ) ∧ (r ˅ q ˅ p)

Fig. 10 Tabla de verdad de una forma normal conjuntiva

A partir de esas formas normales, es más inmediato determinar en qué

interpretaciones resulta ser verdadera o falsa la fórmula inicial.

19
Así por ejemplo la forma normal conjuntiva (r ˅ ¬p ˅ ¬q ) ∧ (r ˅ q ˅ p),
está formada por dos conjuntos de literales (r ˅ ¬p ˅ ¬q ) y (r ˅ q ˅ p), si
hacemos la tabla de verdad de cada uno de ellos (Fig. 10), se aprecia que
como cada formula literal está formada por disyunciones la tabla de verdad
será falsa en una sola interpretación, en la figura del ejemplo la primera
será falsa para (0 1 1) y la segunda para (0 0 0). Por lo tanto su conjunción
será falsa para esas dos interpretaciones.

Si tenemos ahora una forma normal disyuntiva, como por ejemplo (r ∧ ¬p

∧ ¬q) ˅ (r ∧ q ∧ p), en este caso está formada por dos fórmulas literales
conjuntivas, que son: (r ∧ ¬p ∧ ¬q) y (r ∧ q ∧ p), si hacemos la tabla de
verdad de cada uno de ellos.

Fig. 11 Tabla de verdad de una forma normal disyuntiva

Ahora se aprecia que como cada formula literal está formada por
conjunciones la tabla de verdad será verdadera en una sola interpretación,
en la figura del ejemplo la primera será verdadera para (1 0 0) y la segunda
para (1 1 1). Por lo tanto su disyunción será verdadera solo en esas dos
interpretaciones.

20
2. VALIDEZ Y SATISFACIBILIDAD. CÁLCULO (TABLEAUX)
2.1 SATISFACIBILIDAD DE UN CONJUNTO DE FÓRMULAS
Una fórmula es satisfacible si existe al menos una interpretación respecto a
la cual esa fórmula resulte verdadera. Existen fórmulas que no son
satisfacibles, que resultan falsas respecto a cada una de sus interpretaciones
posibles. Por ejemplo, (p ∧ ¬p) es insatisfacible, así como (r → q) ∧ ¬(r →
q). Pero, otras fórmulas, como (p → r) son satisfacibles.

Ante la pregunta de si es satisfacible una fórmula, tenemos dos respuestas:

sí y no. En lógica proposicional es un problema que siempre puede
resolverse, en más o menos pasos, el método más costoso es confeccionar
su tabla de verdad, sobre todo para decidir si es insatisfacible, ya que
tenemos que asegurarnos que la fórmula no es verdad para todas las
interpretaciones posibles.

La satisfacibilidad divide en dos al conjunto de todas las fórmulas

proposicionales: las insatisfacibles por un lado y las satisfacibles por otro
(Fig. 12).

Fig. 12 Fórmulas satisfacibles e insatisfacibles

Una fórmula con dos letras proposicionales (p, q) sólo requiere

asignaciones de verdad (verdadero o falso) de cada una de ellas para formar
una interpretación adecuada a la fórmula. Se pueden construir hasta 4
interpretaciones distintas. Por ejemplo:

21
 p q r (p ˅ q) ↔ (¬p ˅ ¬q)
1 0
1 1
0 0
1 0
1 0
0 0
1 0
0 1
0 0
1 0
0 0
0 0

Esa misma fórmula se puede evaluar respecto a interpretaciones que

consideren más letras proposicionales, que no aparecen en la fórmula, por
ejemplo r. Ahora donde hay un cero en la interpretación de p y q,
aparecerán dos una para cada valor de r. Si la interpretación hubiera sido un
uno, también se desdoblaría, ya que la adición de una letra proposicional
que no aparece en la fórmula original no altera la interpretación su
interpretación.

Un conjunto de fórmulas es satisfacible si existe al menos una

interpretación respecto a la cual, a esa misma interpretación, cada una de
esas fórmulas resulta verdadera. Si se construye la tabla de verdad conjunta
de esas fórmulas, por ejemplo de tres fórmulas X, Y, Z (Fig. 13), ese
conjunto de fórmulas es satisfacible si existe al menos una línea de la tabla
de verdad en que todas y cada una de esas fórmulas son verdad ante esa
interpretación, en caso contrario se dice que es insatisfacible.

Fig. 13 Satisfacibilidad de un conjunto de fórmulas

22
2.1.1 Expandir/reducir un conjunto satisfacible/insatisfacible

Dado un conjunto satisfacible de fórmula, por ejemplo X, Y, Z (Fig. 14),

consideramos ahora el conjunto que resulta de añadir una o más fórmulas
(W en la figura). En este último, el ampliado, no puede garantizarse como
conjunto que sea satisfacible necesariamente, ya que depende de las
fórmulas añadidas, en algunos casos resultará un conjunto satisfacible y en
otros no. Solo sabremos que si añadimos una fórmula que siempre es
verdadera ( ), se conservará la satisfacibilidad y si la fórmula es totalmente
falsa ( ) el conjunto se volverá insatisfacible.

Fig. 14 Ampliación de un conjunto satisfacible de formulas

23
Si ahora el conjunto es insatisfacible, y consideramos el conjunto que
resulta de añadir una o más fórmulas. Este último, el ampliado, siempre
puede garantizarse que es un conjunto insatisfacible necesariamente. Por
otro lado, dado un conjunto satisfacible, consideramos el conjunto que
resulta de eliminar una o más fórmulas. Este último, reducido (un
subconjunto del original), puede garantizarse como conjunto satisfacible,
siempre, en todo caso.

Resumiendo las cuatro opciones posibles:

 Dado un conjunto satisfacible, su ampliación con nuevas fórmulas

no garantiza que sea satisfacible o insatisfacible (Fig. 15.a).

 Dado un conjunto insatisfacible su ampliación con nuevas fórmulas

es insatisfacible (Fig. 15.b).

 Dado un conjunto satisfacible un subconjunto del mismo es

satisfacible (Fig. 15.c).

 Dado un conjunto insatisfacible un subconjunto del mismo no se

puede garantizar que sea satisfacible o no (Fig. 15.d).

Fig. 15 Satisfacibilidad de la expansión o reducción de un conjunto de fórmulas

24
2.1.2 Satisfacibilidad y equivalencia. Satisfacibilidad y conjunción

Si dos fórmulas son equivalentes, necesariamente son igual de satisfacibles

(ambas son satisfacibles o ambas son insatisfacibles), ya que al ser
equivalentes tienen la misma tabla de verdad. Es decir se cumple que:

F ≡ F’  (Sat (F) ↔ Sat (F’))

En inverso no es cierto ya que dos fórmulas pueden ser satisfacibles, pero

no ser equivalentes, ya que no tienen por qué tener la misma tabla de
verdad.

Teorema: Una fórmula conjuntiva es satisfacible sí y solo si lo es el

conjunto de sus fórmulas componentes:

Sat ({X ˄ Y ˄ Z}) ↔ Sat ({X, Y, Z})

Una fórmula es tan satisfacible como su fórmula equivalente, si esta la

transformamos en su forma normal conjuntiva, entonces a su vez, será tan
satisfacible como el conjunto de fórmulas componentes de esa conjunción.

Por ejemplo:

2.2 TAUTOLOGÍAS Y CONTRADICCIONES

Una tautología es una fórmula proposicional que resulta ser verdadera
respecto a cualquiera de sus interpretaciones posibles. Es decir, su tabla de
verdad tiene unos en todas las líneas. Denominamos contradicción a toda
formula insatisfacible, es decir que es falsa ante cualquier interpretación.
Las tautologías y las contradicciones están estrechamente relacionadas.

25
Negando una tautología se obtiene una contradicción. Y negando una
contradicción se obtiene una tautología (Fig. 16).

Fig. 16 Tautologías y contradicciones

Partiendo de una tautología se puede reescribir de manera que se garantice

que continúa siendo una tautología. Para ello se escoge una letra
proposicional en la fórmula y se sustituye cada una (todas todas) de las
apariciones de esa letra por la fórmula que se desee (sin restricciones), se
obtiene una fórmula que sigue siendo tautología.

Por ejemplo:

((p ∧ r) → (r ˅ s)) ˅ (q ˅ s)

Si sustituimos r por una formula X cualquiera tenemos:

((p ∧ X) → (r ˅ X)) ˅ (q ˅ s)

Que será una tautología, de forma que si X es igual a la formula (r → ¬q) u

otras cualesquiera, esta nueva fórmula:

((p ∧ (r → ¬q)) → (r ˅ (r → ¬q))) ˅ (q ˅ s)

Seguirá siendo una tautología.

Este es un proceso similar al que usábamos para producir equivalencias por

reemplazo (ver apartado 1.3.3), pero existen algunas diferencias:

26
 1. Para producir equivalencias, se escoge una subfórmula cualquiera
de la fórmula inicial

2. Para producir equivalencias, si esa subfórmula apareciera varias

veces en la fórmula podemos sustituir sólo una de esas apariciones
(o varias, opcionalmente)

3. Para producir equivalencias, no se puede sustituir por lo que se

desee, sino por una fórmula equivalente a la subfórmula que se
sustituye

Para diferenciar ambos procesos, hablaremos de reemplazo (por fórmulas

equivalentes) en un caso y de sustitución uniforme (es decir, en todas y
cada una de las apariciones de la letra proposicional, siempre por la misma
fórmula que deseemos) en el caso que nos ocupa. El primer proceso
garantiza que de una fórmula cualquiera se construye una equivalente. El
proceso de sustitución uniforme garantiza que de una tautología (podría ser
una contradicción) se genera otra tautología (o contradicción,
respectivamente).

Si dos fórmulas son equivalentes, al unirlas por un bicondicional produce

una fórmula tautológica. En el otro sentido, si se parte de un bicondicional
tautológico se puede garantizar que la componente izquierda y la derecha
de ese bicondicional, como fórmulas separadas, son equivalentes. Por lo
tanto se cumple que:

X ≡ Y  ((X ↔ Y) ≡

Comprobar que (p → q) es equivalente a (¬q → ¬p) es inmediato

comparando las tablas de verdad de ambas fórmulas. No es posible hacerlo
(para todos los pares de fórmulas) cuando se afirma que (X→Y) ≡
(¬Y→¬X) ocurre de forma general.

Fig. 17 Demostración gráfica de la fórmula general de una equivalencia

27
La demostración de este esquema de equivalencia abstracto se construye
formalmente por inducción. De momento, si hemos aceptado por qué de
una tautología se produce otra por sustitución (Fig. 17), con este resultado
podemos justificar también estos esquemas generales de equivalencia.

2.3 CÁLCULO DE INSATISFACIBILIDAD: TABLEAUX

2.3.1 Introducción

Las tablas analíticas o tableaux son un procedimiento de decisión sobre la

satisfacibilidad de un conjunto de fórmulas proposicionales. Son un
proceso sistemático de búsqueda de una interpretación que satisfaga el
conjunto de fórmulas dado.

Así, por ejemplo si tenemos un conjunto de dos fórmulas X = (p  q); Y =

(p  q) y queremos encontrar una interpretación que satisfaga a ambas
fórmulas. Ponemos ambas fórmulas una debajo de la otra:

p  q

p  q

Si suponemos que ambas fórmulas se satisfacen, dado que la segunda de las

formulas es una conjunción se debe cumplir que se satisfacen las dos
fórmulas originales X, Y, y p, q:

p  q

p  q

p

En el caso de la primera de las ecuaciones, es una disyunción, por lo tanto

si se satisfacen las cuatro formulas, puede pasar que sea cierta la parte
izquierda de la disyunción (p) o que sea cierta la parte derecha (q) o
ambas. Así puede que sean ciertas las cuatro fórmulas y la parte izquierda,
o las cuatro ecuaciones y la parte derecha:
28
 p  q

p  q

p

p q
Consideremos la primera opción, es decir que satisface las cinco formulas
siguientes:
p  q

p  q

p

Se ve que esta rama es una interpretación, una línea de la tabla de verdad,

se pide que se satisfaga a la vez p y p, cosa que es imposible, por lo tanto
no es posible esa opción. Si ahora consideramos la otra rama:

p  q

p  q

p

q
29
Ocurre lo mismo, tenemos que se debe cumplir q y q, lo que es imposible.

Por lo tanto se cumple que ambas fórmulas son insatisfacibles, ya que no

hay ninguna interpretación que cumpla ninguna de las dos propiedades.

2.3.2 Expansión de un tableaux con conjunciones y disyunciones

Para confirmar si un conjunto de fórmulas proposicionales son satisfacibles

o no, hemos visto que se consideran un conjunto formado por las mismas,
tres en el caso de la Fig. 18.

Fig. 18 Expansión de tres fórmulas, una de ellas conjuntiva

En este conjunto inicial, formado por las tres fórmulas, no descartamos que
haya una interpretación que satisfaga a las mismas. Si en uno de los nodos
hay una formula conjuntiva (nodo 2 de la figura), en el apartado anterior
vimos que esta interpretación necesariamente debe satisfacer las tres
fórmulas de partida junto con las dos fórmulas (X, Y) que la componen.
Esto se denomina expansión de un nodo conjuntivo en una rama.

Si otro de los nodos cualesquiera es disyuntivo (nodo 1 de la figura), la

interpretación que satisface las cinco fórmulas, no puede dejar de satisfacer
las cinco, y además W o bien, las cinco y además T o ambas dos opciones.
Lo que tenemos es que en la rama de la izquierda, la que empieza arriba y
acaba en W, ha sido expandir el nodo disyuntivo en esa rama, donde sólo le
corresponde una de las dos componentes, pero en todo caso está expandido
el nodo 1. En la rama de la derecha también está expandido el nodo 1, y le
ha de corresponder otro de los componentes de la disyunción. Ahora

30
tenemos una hipotética interpretación de partida que satisface
necesariamente las seis fórmulas de la rama izquierda, o bien las de la rama
derecha o bien ambas dos opciones. Esto se denomina expansión de un
nodo disyuntivo en dos ramas. Si otro de los nodos fuera disyuntivo (nodo
3 de la figura), y todavía no se ha expandido en ninguna de las ramas, si
consideramos la rama de la izquierda, esas seis formulas deben ahora
cumplir las seis más U o esas seis más V. Entonces decimos que en la rama
que termina en U se ha expandido el nodo disyuntivo, le ha correspondido,
al menos uno de los dos componentes y en la rama que acaba en V, también
se ha expandido en nodo 3. Sin embargo aún falta que se expanda en la
rama que termina en T, por lo tanto se producen dos nuevas ramas en
donde se expande de nuevo el nodo 3, con las dos componentes de la
disyunción. Veamos un ejemplo, si queremos saber si ((p  q) ˄ ¬r) y (r
˅ s) son satisfacibles, dibujamos su tableaux y su expansión:

(p  q) ˄ ¬r

(r ˅ s)

((p  q)

¬r

p q

r s

Cada nodo sólo es preciso expandirlo una vez (a lo sumo) en cada una de
las ramas que cuelgan de ese nodo. Cuando en una rama están expandidos
todos los nodos posibles, se dirá que es una rama completamente
expandida. Cuando en una rama se detecte en uno de sus nodos una letra
proposicional y en otro esa misma letra negada, se dirá que esa rama está
cerrada, como la marcada en rojo del ejemplo. La otra rama, la que termina
en s, no le ocurre esto, por lo tanto no está cerrada. Esto garantiza que
existe una interpretación que hace satisfacible al conjunto inicial de
fórmulas, además nos proporciona la interpretación que hace esto posible (s
= 1, p = 1, r = 0, para cualquier valor de q).

31
2.3.3 Expansión de los nodos en un tableaux con otras conectivas

Fig. 19

32
Hemos visto en el apartado anterior el objetivo que se persigue en la
expansión de un nodo conjuntivo o disyuntivo. Pero nos podemos
encontrarnos con nodos con otra conectiva principal. En este caso, si bien
se podrían reescribirlos equivalentemente sólo con conjunciones y
disyunciones, existen una serie de reglas de expansión (Fig. 19) para cada
conectiva, según sean implícitamente conjuntivos o implícitamente
disyuntivos.

2.3.4 Tableaux cerrado. Conjunto insatisfacible de fórmulas

Recapitulando podemos decir que el sistema de tableaux para lógica

proposicional, es un sistema de cálculo que se basa en colocar todas las
fórmulas que se quieran analizar una debajo de la otra, expandir
correctamente los nodos, cerrar las ramas cuando podaos cerrarlas, y si nos
queda alguna rama sin cerrar expandirla hasta que esté completamente
expandida. Si no se ha cerrado, afirmamos que efectivamente es satisfacible
el conjunto inicial de fórmulas. En el caso de que estén todas cerradas el
conjunto inicial será insatisfacible.

Veamos un ejemplo de tableaux cerrado (es decir, con todas sus ramas
cerradas):

(p ↔ q)

(q → r)

¬(p → r)

¬r

¬q r

p ¬p

q ¬q

33
Cuando se produce este resultado, garantiza que el conjunto inicial de
fórmulas es insatisfacible.

Si ahora consideramos este otro conjunto de fórmulas:

(p ↔ q)

(q → r)

¬(¬p → r)

¬p

¬r

¬q r

p ¬p

q ¬q

Ahora existe una rama, la que termina en ¬q, que no está cerrada. Esto
garantiza que existe una interpretación que hace satisfacible al conjunto
inicial de fórmulas, además nos proporciona la interpretación que hace esto
posible (p = 0, q = 0, r = 0).

Por último veamos, paso a paso, un ejemplo más complejo. Sea el conjunto
siguiente de fórmulas que queremos comprobar si es satisfacible:

(p ˅ q) ˄ ¬(r → q)

¬(r → ¬s)

(p ˄ r) → (q ˄ r)

Primero expandimos las conjunciones, en este caso la primera fórmula:

34
 (p ˅ q) ˄ ¬(r → q)

¬(r → ¬s)

(p ˄ r) → (q ˄ r)

p˅q

¬(r → q)

Ahora expandimos el nodo ¬(r → q):

(p ˅ q) ˄ ¬(r → q)

¬(r → ¬s)

(p ˄ r) → (q ˄ r)

p˅q

¬(r → q)

¬q

Ahora expandimos el nodo (p ˅ q):

(p ˅ q) ˄ ¬(r → q)

¬(r → ¬s)

(p ˄ r) → (q ˄ r)

p˅q

¬(r → q)

¬q

p q

35
Cerramos una rama. Si ahora en la rama de la izquierda expandimos el
nodo ¬(r → ¬s), tenemos:

(p ˅ q) ˄ ¬(r → q)

¬(r → ¬s)

(p ˄ r) → (q ˄ r)

p˅q

¬(r → q)

¬q

p q

¬r ¬¬s

Cerramos de nuevo otra rama. Ahora si trasformamos ¬¬s en s:

(p ˅ q) ˄ ¬(r → q)

¬(r → ¬s)

(p ˄ r) → (q ˄ r)

p˅q

¬(r → q)

¬q

p q

¬r ¬¬s

36
Si ahora expandimos el nodo (p ˄ r) → (q ˄ r) y por último expandimos los
nodos conjuntivos ¬(p ˄ r) y (q ˄ r):

(p ˅ q) ˄ ¬(r → q)

¬(r → ¬s)

(p ˄ r) → (q ˄ r)

p˅q

¬(r → q)

¬q

p q

¬r ¬¬s

¬(p ˄ r) (q ˄ r)

¬p ¬r s

Luego todas las ramas están expandidas y cerradas, por lo que el conjunto
de fórmulas inicial es insatisfacible.

37
3. CONSECUENCIA: CÁLCULO (DEDUCCIÓN NATURAL)
3.1 CONSECUENCIA. DEFINICIÓN, PROPIEDADES Y RELACIONES CON
OTROS CONCEPTOS

3.1.1 Definición

Fig. 20 C es consecuencia de {X, Y, Z}

Suponemos verdaderas ciertas fórmulas de partida {X, Y, Z}, que en algún

momento llamaremos hipótesis o premisas (Fig. 20). Cualquier fórmula
que aspire a ser etiquetada como consecuencia de esas premisas tiene que
cumplir que: en todas las interpretaciones en que coinciden las premisas en
ser verdad resulta que la consecuencia también lo es (sin fallar en una sola).
Es decir, la consecuencia, para serlo, está obligada a ser verdad en las
líneas marcadas por la premisas (en que coinciden en ser verdad) y quizá,
opcionalmente, pueda ser verdadera en alguna línea más (aunque esto ya no
afecta a su reconocimiento como consecuencia). Es decir, de un conjunto
de fórmulas que coinciden en ser verdad en tres interpretaciones, cualquier
consecuencia tiene que ser verdad como mínimo en tres interpretaciones
(exactamente en esas tres) y luego quizá en otras o no (fuera de esas no
tiene restricciones que cumplir).

Si C es consecuencia de {X, Y, Z} usaremos la siguiente notación:

X, Y, Z ⊨ C

Por lo tanto, para toda posible interpretación, si ésta satisface las premisas
también satisface la consecuencia:

∀I (I ⊨ {X,Y,Z} → I ⊨ C)

38
De acuerdo con lo anterior, por aplicación estricta de la definición, sin
forzar o considerar una excepción, se puede enunciar cómo deben ser las
fórmulas consecuencia de un conjunto insatisfacible. Si el número de líneas
en que las premisas coinciden en ser verdad es cero (ninguna) entonces la
consecuencia tiene restricciones sobre cero líneas y puede tomar cualquier
valor en el resto (o sea, en todas). Es decir, absolutamente cualquier
fórmula se puede considerar consecuencia de un conjunto de fórmulas
insatisfacible, en estricto cumplimiento de la definición.

Cuando se afirma aquí cualquier fórmula observe que esto incluye también
(la fórmula siempre falsa), y tanto una fórmula como su negación. Es
más, esto sólo ocurre cuando se parte de un conjunto de premisas
insatisfacible (trate de visualizarlo gráficamente). Si se parte de un
conjunto de premisas satifacible, donde coinciden en ser verdad en por
ejemplo dos interpretaciones, entonces no puede ser consecuencia, y si
una fórmula lo es no puede serlo también su negación.

3.1.2 Propiedades. Reflexiva y Transitiva. Monotonía

Denominamos consecuencia a una relación, la que se aprecia (o no) entre

una fórmula y un conjunto de fórmulas. Por la forma en que se define esta
relación de consecuencia tiene las siguientes propiedades:

a) Toda fórmula es consecuencia de ella misma (Reflexividad):

X ⊨ X

Fig. 21 Consecuencia de cualquier conjunto de premisas que la incluya

b) Toda fórmula es consecuencia de cualquier conjunto de premisas que la

incluya (Fig. 21):

X, Y, Z ⊨ X
39
c) Transitividad: Si, por un lado, H1,…,Hn ⊨ C y adicionalmente C ⊨ W
entonces se puede afirmar que H1 ,…,Hn ⊨W (Fig. 22).

Fig. 22 Propiedad transitiva

Fig. 23 Monotomía

d) Monotonía: partiendo de un conjunto inicial de fórmulas {X, Y, Z}

pueden encontrarse (o generarse) múltiples fórmulas consecuencia (Fig.
23):

40
 X, Y, Z ⊨ C1

X, Y, Z ⊨ C2

X, Y, Z ⊨ C3

Todas esas consecuencias continúan siéndolo de cualquier conjunto que

amplíe {X, Y, Z}, por ejemplo:

X, Y, Z, W ⊨ C1

X, Y, Z, W ⊨ C2

X, Y, Z, W ⊨C3

3.1.3 Consecuencia y condicionales tautológicos

De la definición de consecuencia, X, Y, Z ⊨ C, se puede asegurar que la

fórmula X ∧ Y ∧ Z → C es una tautología. Y viceversa (Fig. 24).

Fig. 24 Consecuencia y condicionales tautológicos

Existe también una estrecha relación entre consecuencia y equivalencia.

Dadas dos fórmulas cualesquiera, ocurre que A ≡ B, si y sólo si A es
consecuencia de B y B es consecuencia de A si y sólo si tanto A → B como
B → A son tautologías, si y sólo si A ↔ B es una tautología. Al fin y al
cabo son el mismo enunciado sobre el mundo, en dos expresiones distintas.

41
3.1.4 Consecuencia e insatisfacibilidad

A partir de una relación de consecuencia es posible construir un conjunto

garantizando que es insatisfacible (Fig. 25):

X, Y ⊨ C entonces {X, Y, ¬C} es insatisfacible

Fig. 25

Y viceversa: dado un conjunto insatisfacible, es posible construir relaciones

de consecuencia (Fig. 26). A partir del conjunto {X, Y, Z} insatisfacible,
escójase una fórmula cualquiera, niéguese, y resultará consecuencia de las
restantes:

{X, Y, Z}insatisfacible entonces X, Y ⊨ ¬Z

Fig. 26 Partiendo de un conjunto insatisfacible {X, Y, Z}. (a) Si consideramos {X, Y, ¬Z} se
ve que es insatisfacible pero como cualquier fórmula se puede considerar consecuencia de
un conjunto de fórmulas insatisfacible se cumple X, Y ⊨ ¬Z, lo mismo ocurre con (c) Y, Z ⊨
¬X. Pero en (b) {X, Z, ¬Y} es satisfacible, por lo tanto se cumple también X, Z ⊨ ¬Y

42
3.2 CÁLCULO DE CONSECUENCIAS: DEDUCCIÓN NATURAL
La Deducción Natural, es un sistema de generación de conclusiones
correctas, cada razonamiento se compone de pasos permitidos en el sistema
(porque garantizan el buen comportamiento del cálculo). Los pasos
posibles son, para cada conectiva, uno de introducción y otro de
eliminación.

3.2.1 Conjunción. Regla introducción (E) y eliminación (I)

Fig. 27 Eliminación de la conjunción (E) e introducción de la conjunción (I)

Ejemplo:

1 pq premisa

2 r premisa

3 p E: 1

4 rp I: 2,3

3.2.2 Condicional. Regla eliminación (E). Regla introducción (I)

Fig. 28 Eliminación del condicional (E)

43
Ejemplo:

1 r  q premisa

2 r  p premisa

3 r E: 1

4 p E: 2,3

Fig. 29 Introducción del condicional (I)

Ejemplo:

1 r  q premisa

2 s  t suposición

3 t E: 2

4 r E: 1

5 tr E: 3,4

6 (s  t)  (t  r) I: 2,5

44
3.2.3 Disyunción. Regla introducción (I). Regla eliminación (E)

Fig. 30 Introducción de la disyunción (I)

Ejemplo:

1 r  q premisa

2 r  p premisa

3 r E: 2

4 p E: 2,3

5 r  t I: 3

Fig. 31 Eliminación de la disyunción (E)

45
Ejemplo:

1 prs premisa

2 qr premisa

3 pq premisa

4 p q

5 r

6 rs rs

7 rs E: 3,6

3.2.4 Bicondicional. Regla eliminación (E). Regla introducción

(I)

Fig. 32 Eliminación (E) e introducción (I) del bicondicional

46
Ejemplo de eliminación:

E p  q  r

p qr

qr p

E p  q  r q  r  p

E (p  q  r)  (q  r  p)

Ejemplo de introducción:
I
p  (q  r) pqr

pq p

p
q

qr pq

q r

r qr

pqr p  (q  r)

(p  (q  r))  ((p  q)  r)

47
3.2.5 Negación. Regla introducción y eliminación

Fig. 33 Reglas introducción y eliminación

48
 II. LÓGICA DE PREDICADOS

4. EL LENGUAJE. SINTAXIS Y SEMÁNTICA. EQUIVALENCIA

4.1 PREDICADOS CON TÉRMINOS CONSTANTES
4.1.1 Predicados monádicos con términos constantes. Sintaxis y
semántica

Las proposiciones pueden expresarse de manera más explícitamente

detallada. Si p formaliza Juan es alto, podría escribirse como Pa. Aquí, P
representa la propiedad (por ejemplo ser alto, u otra) y a representa el
sujeto que tiene esa propiedad. Así pues podemos ampliar la sintaxis ya
estudiada en el apartado 1.1.2 para incluir este nuevo tipo de fórmulas
atómicas: predicado y término (Fig. 34).

Fig. 34 Sintaxis con predicados monádicos

El proceso de interpretación de la fórmula p sólo admitía reconocerla

directamente como verdadera o falsa. Si se escribe como Pa el proceso de
interpretación es más complejo, aunque el resultado final será de nuevo
verdadero o falso.

La interpretación ahora requiere escoger un universo U, es decir un

conjunto de elementos, y de entre ellos escoger cuáles de esos elementos
tendrían la propiedad P y qué elemento representa al término abstracto a.

49
 Fig. 35 Semántica de una fórmula con predicados monádicos con constantes

En la Fig. 35 hemos representado el árbol sintáctico de una fórmula con

predicados monádicos con constantes. Definimos el universo U = {1, 2, 3,
4} y los predicados P y Q, que para esta interpretación suponemos que la
propiedad P es satisfecha por los elementos 2 y 3, y propiedad que
representa Q por 1 y 3. Definimos el valor de las constantes para esta
interpretación (aI = 3 y bI = 4), y evaluamos si Pa es verdadera, que ahora
significa que 3 tiene la propiedad P, comprobamos que sí. Ahora
evaluamos Pb, y vemos que es falsa, ya que 4 no posee la propiedad P. Del
mismo modo hacemos con Qa, que será verdadera ya que 3 también tiene
la propiedad Q. A continuación vamos de abajo arriba en el árbol sintáctico
y comprobamos que la fórmula es verdadera para esta interpretación.

Veamos algunos ejemplos de la interpretación de fórmulas con dos

predicados monádicos (P y Q) y dos constantes (a y b) como términos. Si
consideramos las siguientes fórmulas:

Pa ˄ Qb

Pa ˅ ¬Qb

Pa → Qb

Pa ↔ Qb

50
Consideremos el universo U formado por cinco elementos:

U = {1, 2, 3, 4}

En este universo se decide que:

PI = {2, 4, 5}

QI = {1, 4}

Es decir que la propiedad P la posen los elementos 2, 4, 5 y la propiedad Q

los elementos 1, 4 (Fig. 36).

Fig. 36

Si hacemos que a =1 y b = 4 en esta interpretación Pa siempre será falso y

Qb siempre será verdadero. Luego: Pa ˄ Qb (falso), Pa ˅ ¬Qb (falso) Pa
→ Qb (verdadero) y Pa ↔ Qb (falso).

Fig. 37

51
Si ahora cambiamos la interpretación (Fig. 37) y consideramos que

PI = {2, 4, 5} = QI

Para los mismos valores de las constantes a y b vemos que también que Pa
siempre será falso y Qb siempre será verdadero. Luego: Pa ˄ Qb (falso),
Pa ˅ ¬Qb (falso) Pa → Qb (verdadero) y Pa ↔ Qb (falso).

Fig. 38

Si para la misma interpretación anterior:

PI = {2, 4, 5}

QI = {1, 4}

Decidimos que a = b = 4. Tenemos que ahora Pa y Qb siempre serán

verdadero (Fig. 38). Luego: Pa ˄ Qb, Pa ˅ ¬Qb, Pa → Qb, y Pa ↔ Qb
serán todas verdaderas.

4.1.2 Predicados diádicos con términos constantes. Sintaxis y

semántica

Existen multitud de relaciones entre sujetos, como a es vecino de b o a es

mayor que b, que se pueden expresar abstractamente como Rab. También
podemos expresar relaciones entre tres o más términos es decir Sabc. Así
pues tenemos y que hacer es ampliar la sintaxis ya estudiada en el apartado
4.1.1 para incluir estas relaciones (Fig. 39).

52
 Fig. 39 Sintaxis con predicados poliádricos

Como la mayoría de los casos se emplean predicados diádicos, vamos a ver

cómo se pueden generar fórmulas con estos predicados que relacionan dos
términos constantes, y cómo generar interpretaciones para evaluar este tipo
de fórmulas.

Consideremos en un universo U = {1, 2, 3, 4, 5, 6} una relación Rab que la

indicamos en la Fig. 40 por medio de un conjunto de flechas orientadas o
por medio de RI = {(3.6), (5,4), (6,2)}

Fig. 40

Si ahora damos valores a las constantes a y b, en esta interpretación vemos

que para a = 6 y b = 4, tenemos que Rab es verdadera, ya que hay una
flecha que parte de 6 y llaga a 4 (Fig. 40), por lo tanto existe esta relación.
Si ahora decimos que a = 2 y b = 6 ocurre que Rab es falsa. También sale
falsa para a = 1 y b = 6, y a = b = 3.

53
Veamos algunos ejemplos de fórmulas, construidas con apariciones de un
único predicado diádico R, con unas u otras constantes, y evaluadas sobre
distintas interpretaciones. Consideremos las siguientes formulas:

¬Raa

Rab ˄ ¬Rab

Rab → Rba

Rac → ¬Rca

(Rab ˄ Rbc) → Rac

Consideremos en un universo U = {1, 2, 3, 4, 5, 6,7} una relación Rab que la
indicamos en la Fig. 41 por medio de un conjunto de flechas orientadas o por
medio de RI = {(1.5), (5,1), (7,2), (7,4), (4,2), (6,6)}. Así para a = 6, ¬Raa resulta
falso, ya que Raa es verdadero dado que existe en la relación del 6 consigo mismo.
Si ahora consideramos que a = 4 ¬Raa resulta verdadero. Para a = 4 y b = 2 Rab ˄
¬Rab resulta falso.

Fig. 41

Fig. 42

54
Consideremos ahora Rab → Rba. Como se puede ver en la Fig. 42 la
fórmula es verdadera para a = 4 y b = 2; a = 1 y b = 5; a = b = 6 y a = 3 y b
= 4.

Consideremos ahora Rac → ¬Rca. Como se puede ver en la Fig. 43 la

fórmula es verdadera para a = 4 y c = 2 y a = 3 y c = 4. Y es falsa para a = 1
y c = 5 y a = c = 6.

Fig. 43

Consideremos ahora una expresión más compleja (Rab ˄ Rbc) → Rac.

Como se puede ver en la Fig. 44 la fórmula es siempre verdadera para todas
las interpretaciones.

Fig. 44

55
4.2 PREDICADOS CON TÉRMINOS VARIABLES Y CUANTIFICADORES
4.2.1 Cuantificadores y variables

Para rellenar los términos de los predicados sólo disponíamos de

constantes, hasta este momento. Ahora se dispone de un segundo conjunto
de términos: las variables. Y de dos nuevos símbolos, denominados
cuantificadores [∀(para todo…), ∃(existe…)], que forzarán una
determinada semántica en estas fórmulas con variables.

Fig. 45 Sintaxis de predicados con variables y cuantificadores

La sintaxis (Fig. 45) indica cual es el orden relativo adecuado entre todos
estos símbolos. En particular, los cuantificadores actúan sintácticamente
como la negación: se anteponen a una determinada fórmula previa, a la que
se denominará ámbito del cuantificador.

Fig. 46 Ámbito de un cuantificador.Variables libres y ligadas

56
Los cuantificadores forzarán una determinada semántica sobre ciertos
predicados con variables. Pero no sobre todos los de la fórmula: sólo sobre
aquellos que estén en su ámbito. Las variables que no son afectadas por
ningún cuantificador se denominan variables libres (Fig. 46).

Como ocurre con las constantes, cuando una fórmula contiene alguna
variable libre hay que precisar qué elemento la representa, al construir una
interpretación de la fórmula. Cuando las variables están afectadas por un
cuantificador (universal o existencial) no es necesaria esta asignación
específica: el cuantificador requiere que se evalúe su ámbito considerando
todas las posibles asignaciones para esa variable.

Fig. 47 Semántica de los cuantificadores

En la Fig. 47 se analiza la semántica de los cuantificadores. Así si tenemos

un universo y un predicado P la expresión Pa indica que se evalúa si la
constante a tiene la propiedad P. Si en vez de una constante se analiza una
variable x, es un caso similar al de una constante solo que su valor varia
dentro del universo. Cuando tenemos la formula ∀xPx, vemos que la
variable x está ligada al cuantificador para todo…, por lo tanto tiene que
recorrer todo el universo y comprobar si la propiedad P se cumple para
todos los elementos del mismo, cosa que en el ejemplo de la figura no
ocurre con el 1 y el 4, por lo tanto la formula ∀xPx no se cumple. Si
consideramos ahora ∃xPx, la variable está ligada al cuantificador existe…,
por lo que para que se cumpla la fórmula solo basta que exista al menos un
elemento que cumpla la propiedad P, que en el caso mostrado en la figura
ocurre para 3, 2 y 5.

57
4.2.2 Ejemplos de interpretación de predicados monádicos

 Todos P y Q: ∀x (Px ∧ Qx)

Esta fórmula expresa que todos los elementos que se consideran, en el

universo-contexto fijado, tienen, cada uno de ellos, tanto la propiedad P
como la Q.

Fig. 48 Semántica de la fórmula ∀x (Px ∧ Qx)

La semántica de la fórmula nos indica que para que sea válida todos los
elementos deben estar en la zona verde de la Fig. 48, y además la zona roja
es una zona prohibida, ya que si existen elementos en esa zona la formula
no se cumplirá.

 Todos P o Q: ∀x (Px ∨ Qx)

Esta fórmula expresa que todos los elementos del universo, cada uno de
ello, o bien tiene la propiedad P, o bien la Q, o bien ambas.

Fig. 49 Semántica de la fórmula ∀x (Px ∨ Qx)

La semántica de la fórmula nos indica que para que sea válida todos los
elementos deben estar en la zona verde de la Fig. 49 , y además la zona roja
es una zona prohibida, ya que si existen elementos en esa zona la formula
no se cumplirá.

58
  Todos los P son Q: ∀x (Px → Qx)

Para resultar verdadera esta fórmula se requiere que todos los elementos del
universo cumplan ese condicional. Esto ocurre incluso en interpretaciones
donde ningún elemento tiene la propiedad P. Es decir, la fórmula no
necesita (para ser verdadera) que existan elementos con la propiedad P.
Pero sí requiere que, si existen elementos con la propiedad P, también
tengan la propiedad Q. Con este comportamiento semántico, esta sentencia
formaliza enunciados del tipo Todos los P son Q.

Fig. 50 Semántica de la fórmula ∀x (Px → Qx)

La semántica de la fórmula nos indica que para que sea válida todos los
elementos deben estar en la zona verde de la Fig. 50, siendo la zona roja es
una zona no permitida, ya que se cumpliría hará valido en antecedente P y
falso el consecuente.

 Algún P y Q: ∃x (Px ∧ Qx)

Para que una interpretación satisfaga la fórmula basta que un elemento del
universo tenga tanto la propiedad P como la Q.

Fig. 51 Semántica de la fórmula ∃x (Px ∧ Qx)

La semántica de la fórmula nos indica que para que sea válida basta que
exista un elemento en la zona verde de la Fig. 51.

59
  Algún P y no Q: ∃x (Px ∧ ¬Qx)

Este ejemplo, respecto a los anteriores, introduce el uso de la negación. En

concreto se pide que exista un elemento que presente la propiedad P pero
no presente la Q.

Fig. 52 Semántica de la fórmula ∃x (Px ∧ ¬Qx)

La semántica de la fórmula nos indica que para que sea válida basta que
exista un elemento en la zona verde de la

 Algún no (P y Q): ∃x ¬(Px ∧ Qx)

Esta fórmula enuncia que existe al menos un elemento que no cumple algo.
Y lo que no cumple es tener a la vez la propiedad P y la propiedad Q.
Quizá porque ese elemento no presente la primera propiedad, o la segunda,
o ninguna.

Fig. 53 Semántica de la fórmula ∃x ¬(Px ∧ Qx)

La semántica de la fórmula nos indica que para que sea válida basta que
exista un elemento en la zona verde de la Fig. 53.

60
  Negación cuantificador

Se estudian las siguientes fórmulas:

Todos… ∀xPx Algún… ∃xPx

Ninguno… ∀x¬Px Alguno n… ∃x¬Px
No todos… ¬∀xPx No existe ningún… ¬∃xPx

1 4

2 5

3 6

Fig. 54 Semántica de la negación de los cuantificadores

En la Fig. 54.1 se aprecia que la semántica de ∀xPx obliga que todos los
elementos del universo tengan la propiedad P, luego deben estar situados
en la zona verde del diagrama. Si ahora tenemos ∀x¬Px la semántica
obligará a que los elementos se encuentren en la zona roja del diagrama, ya
que la formula se interpreta como que ningún elemento tiene la propiedad P
(Fig. 54.2). La fórmula ¬∀xPx indica que no todos los elementos tiene la
propiedad P, luego solo hace falta que exista un elemento en la zona verde
del diagrama (Fig. 54.3).

La semántica de ∃xPx obliga que al menos un elemento se encuentre en la

zona verde del diagrama (Fig. 54.4). Por otro lado ∃x¬Px que existe algún
elemento que no cumple la propiedad P, luego tiene que encontrarse en la
zona verde del diagrama (Fig. 54.5). La formula ¬∃xPx indica que no
existen ningún elemento que cumpla la propiedad P, es decir que todos los
elementos están en la zona verde del diagrama no pudiendo estar ninguno
en la zona roja del mismo (Fig. 54.6).

61
Se observa que la semántica de la fórmula ¬∃xPx es similar a ∀x¬Px, ya
que es lo mismo decir que no existen ninguno que cumpla la propiedad P,
que decir que Ninguno cumple P (Fig. 55).

Fig. 55 Equivalencia entre ∀x¬Px y ¬∃xPx

4.2.3 Ejemplos de interpretación de predicados diádicos

 Constante y variable

Consideremos las siguientes fórmulas con predicados diádicos, en la que

tenemos relacionados una constante a y una variable ligada x a un
cuantificador:

∀x Rax ∃x Rax
∀x Rxa ∃x Rxa

Consideremos que tenemos un Universo y una relación R definida sobre el

mismo. La interpretación de la fórmula ∀xRax exige que definamos el valor
de la constante a (Fig. 56).

Fig. 56 Semántica de las fórmulas ∀xRax, ∀xRxa, ∃xRax y ∃xRxa

62
Para a = 2, se comprueba que este valor en todos elementos del universo se
cumple que Rax, luego se cumple que ∀xRax. Pero si cambiamos el valor
de la constate a = 3, entonces no se cumple ∀xRax, ya que existe la relación
(1,3) pero no existe la (3,1), que es lo que exige la semántica de la fórmula.

Con carácter general, una vez asignada la constante a a un determinado

elemento del universo, hay que fijarse en su posición relativa en la relación,
para ver si se requiere que sea emisora o receptora de arcos que
representan la relación.

En ∀xRax se cumple que a está relacionado con cada elemento del

universo. En ∀xRxa se cumple que cada elemento del universo está
relacionado con a. En ∃xRax se cumple que a está relacionado al menos
con un elemento del universo. En ∃xRxa se cumple que al menos un
elemento del universo está relacionado con a.

 ∃y ∀x Ryx

En el universo existe algún elemento (∃y) que está relacionado con todos
los demás (∀x) (Fig. 57).

Fig. 57 Semántica de la fórmula ∃y∀xRyx

 ∃x ∀y Rxy

Veamos la respuesta semántica de esta fórmula. Para ello definimos un

universo y una relación R, como la mostrada en la Fig. 58. Ahora habrá que
comprobar si existe un elemento en el universo que está relacionado con el
resto. Si elegimos por ejemplo en el elemento 3 se comprueba que con el 1
no está relacionado, por lo tanto para este elemento no se cumple. Si ahora
escogemos el 1, se comprueba que esté si está relacionado con el resto de
elementos del universo por lo tanto hemos hallado que se cumple la
fórmula para esta interpretación

63
 Fig. 58 Semántica de la fórmula ∃x∀yRxy

 Forma prenexa

Vemos las diferencias entre las siguientes fórmulas: ∃x∃yRxy; ∃x∃yRxy;

∃x∀yRxy e ∀x∀yRxy.

∃x ∃y Rxy

Elegimos un universo y la relación mostrada en la Fig. 59. La fórmula nos

indica que debemos buscar si existen dos elementos al menos que estén
relacionados en la interpretación, cosa que ocurre entre el 2 y el 3.

∃x ∀y Rxy

Elegimos un universo y la relación mostrada en la Fig. 60. Ajora hay que

encontrar si existe un elemento que está relacionado con todos, en este caso
existe para el 2.

∀x ∀y Rxy

Elegimos un universo y la relación mostrada en la Fig. 61. Ahora hay que

comprobar todo elemento del universo, está relacionado con todos los
demás, cosa que se comprueba que es cierta.

64
Fig. 59 Semántica de la formula ∃x∃yRxy Fig. 60 Semántica de la formula ∃x∀yRxy

Fig. 61 Semántica de la fórmula ∀x∀yRxy Fig. 62 Semántica de la fórmula ∀x∃yRxy

65
∀x ∃y Rxy

Elegimos un universo y la relación mostrada en la Fig. 62. Ahora tenemos

que comprobar que para todo elemento del universo, existe al menos uno
de ellos que está relacionado con él.

 Permutación de cuantificadores

Fig. 63 Semántica de la permuta de cuantificadores

Cuando se parte de una fórmula como ∃x∀yRxy y se permutan los

cuantificadores, la fórmula resultante ∀y∃xRxy no siempre es verdadera en
las mismas interpretaciones que la original. Cuando se parte de una fórmula
como ∃x∀yRxy y se permutan las variables en el predicado, la fórmula
resultante ∃x∀yRyx no siempre es verdadera en las mismas interpretaciones
que la original (Fig. 63).

 ∀x (Px ∧ ∃y Rxy)

Fig. 64 Semántica de la fórmula ∀x(Px ∧ ∃yRxy) para I1

66
 Fig. 65 Semántica de la fórmula ∀x(Px ∧ ∃yRxy) para I2

En las Fig. 64 y Fig. 65, se presentan dos interpretaciones de la fórmula

∀x(Px ∧ ∃yRxy) una que resulta falsa y otra verdadera.

 ∀x (Px → ∃y Rxy)

Fig. 66 Semántica de la fórmula ∀x(Px → ∃yRxy)

67
4.3 PREDICADOS CON TÉRMINOS CON FUNCIONES Y USO DE LA
IDENTIDAD

4.3.1 Funciones en los términos

Entre los elemento de un universo, podríamos haber definido lo que

denominamos función, que es una aplicación que hace corresponder a un
elemento del universo otro elemento del universo, un ejemplo de función
sería ser padre de…

Fig. 67 Sintaxis y semántica del uso de funciones en los términos

Si tenemos una relación Rab entre dos términos de un universo, estamos

diciendo que existe una relación entre esos dos términos. Si ahora
consideramos la relación Raf(b) lo que queremos decir es que un término a
se relaciona, no con b sino con su imagen que será otro elemento del
universo (Fig. 67).

Fig. 68 Semántica de la fórmula ∀x(Px ∨ Qf(x))

68
Veamos un ejemplo de uso de una función. Consideremos que tenemos las
fórmulas ∀x(Px ˅ Qx) y ∀x(Px ˄ Qx) definidas en un determinado universo
como el representado en la Fig. 68. Se comprueba que ambas no se
satisfacen en dicho universo. Si consideramos la fórmula:

∀x(Px ∨ Qf(x))

Para analizar su semántica necesitaremos definir los valores que toma la

función f, para ello los mostramos en forma de una tabla:
f(1) = 3
f(2) = 2
f(3) = 2

Con esta definición comprobamos que la se cumple (Fig. 68).

4.3.2 Identidad

Fig. 69 Sintaxis y semántica de la relación de identidad

Consideremos un predicado diádico I y lo interpretamos en un universo en

que solo tiene tres elementos, sobre los mismos definimos la relación I
como {(1,1), (2,2), (3,3)} (Fig. 69). Si tenemos que interpretar Iab, si a = 1
y b = 3 este es falso pero si a = b = 1 será verdadero. Si definimos este
predicado diádico que denotamos por el símbolo (=), y lo forzamos para
que sólo admita una interpretación: aquella que relaciona cada elemento
consigo mismo y con ningún otro, estamos definiendo lo que se denomina
identidad.

Si lo negamos ahora tenemos ¬Iab o lo que es lo mismo ¬(a = b), pero lo

habitual para decir que a ≠ b. Una fórmula como Rxy ∧ Qxy, para ser
69
interpretada, requiere fijar qué elementos están relacionados por R (R-
pares, R-arcos) y qué elementos están relacionados por Q. Podría
formalizar un enunciado como x es vecino de y y x es amigo de y. Una
fórmula como Rxy ∧ x = y también requiere precisar qué elementos están
relacionados por R y cuáles por =. En este caso, x es vecino de y y x es el
mismo elemento que y.

4.3.3 La sintaxis de la lógica de primer orden

Así podemos definir la sintaxis de la lógica de primer orden con Identidad

de la siguiente manera:

Estos son algunos ejemplos de fórmulas atómicas en la lógica de

predicados de primer orden:

Pa Rab a=b
p4 Px Rax x=b
Rxy
Pf(a) Rf(a)z f(a) = b
Pf(x) Rf(a)g(b) f(a) = g(x)
Ph(a,b) Rf(a)g(x)
Ph(x,b) h(a,b) = h(b,a)
Ph(x,f(a)) R(f(a))x h(a,b) = g(x)

A partir de las mismas se pueden generar fórmulas más complejas, como

por ejemplo:

70
 ∀x∀y(Rxy → ∃z(Rxz ˄ Rzy)

∀x∀y(Rxy ˄ Ryx → x = y)

∀x∀y(x ≠ y → f(x) ≠ f(y))

∀x∀y(h(x,y) = h(y,x))

4.4 EQUIVALENCIA ENTRE FÓRMULAS DE LÓGICA DE PREDICADOS

Fig. 70 Al igual que pasaba en lógica proposicional, dos fórmulas en lógica de predicados
son equivalentes cuando dan el mismo valor de verdad para cada interpretación, pero en este
caso se debe cumplir para las posibles infinitas interpretaciones.

Antes de abordar las equivalencias conviene fijar una idea intuitiva sobre
los cuantificadores que puede ayudar. Una sentencia como ∀xPx si se
evalúa sobre un universo finito, por ejemplo de tres elementos, sería
intuitivamente igual a la siguiente afirmación conjuntiva: (P1˄ P2 ˄ P3).
Una sentencia como ∃xPx si se evalúa sobre un universo finito, por ejemplo
de tres elementos, sería intuitivamente igual a la siguiente afirmación
disyuntiva: (P1 ˅ P2 ˅ P3). Así, ∀x¬Px se podría visualizar como (¬P1 ˄
¬P2 ˄ ¬P3). Y es lo que habría resultado, por leyes de De Morgan, de la
negación ¬∃xPx si se hubiera contemplado como ¬(P1 ˅ P2 ˅ P3).

4.4.1 Primeras equivalencias básicas para predicados

Podemos enunciar la primera equivalencia básica.

∀xPx ≡ ∀yPy

71
Es decir dado un cuantificador, solo hay que renombrar, la variable y
cambiarla en todo el ámbito del cuantificador (ver Fig. 71.arriba).

Fig. 71 Primeras equivalencias básicas

La siguiente equivalencia básica nos enlazan los dos cuantificadores (Fig.

71. abajo):

¬∀xPx ≡ ∃x¬Px

¬∃xPx ≡ ∀x¬Px

4.4.2 Segundas equivalencias básicas para predicados

Fig. 72

(X ˄ ∀xY) ≡ ∀x(X ˄ Y) si en la fórmula X no hay variables libres x

(X ˅ ∀xY) ≡ ∀x(X ˅ Y) si en la fórmula X no hay variables libres x

(X ˄ ∃xY) ≡ ∃x(X ˄ Y) si en la fórmula X no hay variables libres x

(X ˅ ∃xY) ≡ ∃x(X ˅ Y) si en la fórmula X no hay variables libres x

72
Esto permite generar cadenas de equivalencias como las siguientes:

(∀x∃yRxy ˅ ∃x∀zQxz) ≡ ∀x(∃yRxy ˅ ∃x∀zQxz)

≡ ∀x(∃yRxy ˅ ∃w∀zQwz)
≡ ∀x∃w(∃yRxy ˅ ∀zQwz)
≡ ∀x∃w∃y(Rxy ˅ ∀zQwz)
≡ ∀x∃w∃y∀z(Rxy ˅ Qwz)

Donde el orden de salida de cuantificadores es el que queramos, siempre y

cuando respeten la restricción fijada. En la segunda línea, cuando
intentábamos sacar ∃x no podíamos porque hubiésemos incluido x en su
nuevo ámbito, haciéndolas dependientes de ese ∃x en el exterior. Pero se
soluciona renombrando antes la variable del ∃x por otra, ∃w

Veamos otro ejemplo, sea la siguiente formula:

(∀x∃yQxy ˅ ∀y∀zRzy)

Queremos conseguir una fórmula equivalente a la misma en donde hemos

conseguido sacar todos los cuantificadores fuera del paréntesis y se
encuentren estén a la cabeza de la formula y dentro del paréntesis no haya
ninguno. Esto es lo que se conoce como forma prenexa.

Primero sacamos el ∀x, ya que en la segunda fórmula de la disyunción no

hay ninguna variable x libre:

∀x (∃yQxy ˅ ∀y∀zRzy)

Ahora sacamos el ∃y:

∀x∃y (Qxy ˅ ∀y∀zRzy)

Esto es válido porque la segunda fórmula de la disyunción no tiene

variables y libres. Ahora procedemos a reescribir la variable y:

∀x∃y (Qxy ˅ ∀w∀zRzw)

Ahora sacamos el ∀w:

∀x∃y∀w (Qxy ˅ ∀zRzw)

73
Y por último sacamos el ∀z, quedando la formula final:

∀x∃y∀w∀z (Qxy ˅ Rzy)

Hay que resaltar que las equivalencias pueden aplicarse siempre en los dos
sentidos. Es decir, si partimos de la fórmula final, podemos introducir los
cuantificadores en vez de sacarlos del paréntesis. Por ejemplo, de
∀x∃y∀w∀z (Qxy ˅ Rzy) se obtendría ∀x∃y∀w (Qxy ˅ ∀zRzy). Donde ahora
el orden de aplicación sí está marcado, debe operarse sobre el cuantificador
más cercano al paréntesis, y se acaba situando en la componente de la
disyunción donde hay variables referenciadas por ese cuantificador.

4.4.3 Conjunción de cuantificadores universales y disyunción de

existenciales

Fig. 73

En la Fig. 73 se muestra como a la formula (∀xPx ˄ ∀xQx) se le ha

aplicado las reglas de equivalencia, y se ha llegado a la fórmula prenexa:

∀x∀y (Px ˄ Qy)

Ahora hay que preguntarse si la formula inicial es equivalente a:

∀x (Px ˄ Qx)

Esta fórmula es válida en la zona verde del diagrama, ya que deben

considerarse todos los elementos que cumplan P y Q simultáneamente.
Luego también es equivalente a la fórmula inicial. Por lo tanto se cumple:

∀x (Px ˄ Qx) ≡ ∀x∀y (Px ˄ Qy)

74
Pero si en vez de tener una conjunción se tiene una disyunción:

(∀xPx ˅ ∀xQx)

Como se aprecia en la parte de debajo de la Fig. 73, la equivalencia con:

∀x (Px ˅ Qx)

Solo es válida en un sentido pero no en el otro. Por lo tanto se cumple lo

mostrado en la Fig. 74.

Fig. 74 Conjunción de cuantificadores universales y disyunción de existenciales

5. VALIDEZ Y SATISFACIBILIDAD: CÁLCULO (TABLEAUX)

5.1 SATISFACIBILIDAD Y VALIDEZ
Todas las definiciones, así como sus relaciones básicas, explicadas para la
lógica proposicional se mantienen en lógica de predicados. Con la salvedad
de que incluso la expresión más simple en predicados admite infinitas
interpretaciones. Esto afecta sobre todo a la capacidad algorítmica de
decidir si se cumple o no una de estas propiedades semánticas simplemente
confrontándola con todas las interpretaciones posibles. En lógica de
proposiciones estas siempre eran un número finito, aunque quizá muy
grande, aquí no hay manera de recorrer todas las opciones semánticas.

Incluso los diagramas abstractos que se usaban en proposiciones pueden

reutilizarse aquí. Normalmente eran tablas de verdad abstractas, en una
primera aproximación, esa aproximación iconográfica sigue siendo útil,
considerando ahora que hay infinitas líneas en esas tablas.

75
5.2 TABLEAUX PARA FÓRMULAS DE LÓGICA DE PREDICADOS
5.2.1 Introducción

Vamos a proceder a aplicar a la lógica de predicados lo visto en el apartado

2.3 para tableaux en lógica proposicional.

Ahora, expandir un nodo del tipo:

¬∀xPx  ∃yQy

No es más que expandir una conjunción: resultaría en dos nodos, uno

debajo de otro: ∀xPx y debajo ∃yQy:

¬∀xPx  ∃yQy

¬∀xPx

∃yQy

Por el contrario, una fórmula como ∀x(Px  Qx) no estamos ante una
conjunción, sino en un nivel sintáctico más alto, ya que es la cuantificación
universal de una fórmula previa. Veamos cómo se expanden formulas del
tipo:

∀xW, ∃xW, ¬∀xW, ¬∃xW

Como en todo cálculo, lo que podemos reescribir o generar tiene que

cumplir unas reglas. Como contrapartida, si se cumplen, el sistema
garantiza algo. Aquí se garantiza que si las fórmulas de partida son
insatisfacibles, debería existir algún tableaux cerrado. Y lo que se requiere
ahora, para expandir nodos de los cuatro tipos mencionados, es:

1. Cuando se enuncia algo de todos, no puede dejar de cumplirlo

cualquiera del universo; se omite la cuantificación en el nodo
expandido y se afirma eso de quien queramos, sin restricciones y
para tantos individuos en particular como necesitemos.

2. Cuando se enuncia que hay alguien que tiene una propiedad, y

queremos simplemente adelantar un nombre abstracto para ese
elemento, por ejemplo a cumple P, esta particularización no

76
 debiera dar problemas, si existe alguien, llámale a. Sólo hay que
mantener una medida de cautela: ese a abstracto, no puede haber
sido referenciado antes, tiene que ser una constante nueva.

En resumen, sólo hay que tener cuidado con las instancias de los
existenciales (o negación de universales): siempre hay que escoger
constante nueva. Así por ejemplo, si tenemos ∃xPx y ∀xPx, y queremos
demostrar su insatisfacibilidad, que es obvia, ya que estamos afirmando que
existe alguien con la propiedad P y luego afirmamos que todos no cumplen
P. Para demostrarlo expandiremos la primera formula particularizándola
para un elemento a, ya que la formula nos garantiza de que existe al menos
un elemento que cumple la propiedad P, para eso eliminamos el existencial
y particularizamos x con el valor a:

∃xPx

∀xPx

Pa

Si ahora expandimos la segunda formula particularizada para a, es decir

como todo x no cumple P, tendremos:

∃xPx

∀xPx

Pa

Pa

Ya hemos cerrado el tableaux, pero se podría haber elegido más elementos

de universo y hubiéramos llegado a la misma conclusión.

Consideremos un segundo ejemplo, partimos de que ∃xPx y ∃xPx, es

decir que afirmamos que existe alguien que cumple la propiedad p y a la

77
vez existe alguien que no la cumple. Ahora no hay contradicción. Si ahora
expandimos la primera:

∃xPx

∃xPx

Pa

Si ahora queremos expandir la segunda debeos hacerla con otra constante

que no se haya utilizado antes en esa rama ya que podemos llegar a
conclusiones equivocadas:

∃xPx

∃xPx

Pa

Pb

Ahora no podemos expandir más, por lo tanto se queda un tableaux abierto,

y las formulas son satisfacibles.

Si en el primer ejemplo hubiéramos expandido la segunda fórmula:

∃xPx

∀xPx

Pa

Si ahora queremos instanciar la primera formula, debemos hacerlo con un

elemento distinto, ya que como hemos visto en el ejemplo anterior hay que
usar un elemento no empleado en la misma rama, por lo tanto tenemos:

78
 ∃xPx

∀xPx

Pa

Pb

Todavía no hemos llegado a cerrar la rama, solo lo haremos cuando

volvamos a aplicar la segunda fórmula:

∃xPx

∀xPx

Pa

Pb

Pb

Hay que tener en cuenta algunas precauciones cuando expande una rama,
por ejemplo si tenemos dos fórmulas como ∃xPx y ∃yQy podemos obtener
en principio de la expansión de la primera formula Pa, hasta aquí, ningún
problema, pero nunca luego Qa, ya que hemos forzado, por un mal uso, que
el elemento a tenga tanto la propiedad P como la Q, y las dos fórmulas de
partida no requieren que esto ocurra necesariamente.

5.2.2 Reglas de expansión de los nodos en un tableaux

En la Fig. 75 se recopilan todas las reglas de expansión de tableaux, tanto

las proposicionales como las que específicamente expanden
cuantificadores. Volvemos a insistir en que sólo hay que tener cuidado con
las instancias de los existenciales (o negación de universales), siempre hay
que escoger constante nueva (símbolo + en la Fig. 75).

79
 Fig. 75 Reglas de expansión de tableaux

5.2.3 Tableaux con cuantificadores. Ejemplo

Supongamos que tenemos dos premisas ∀x(Px  Qx), ∃x(Px  Rx). Para
demostrar que la fórmula ∃x(Qx  Rx) es una consecuencia de esas dos
premisas, negamos la conclusión, y comprobamos si la expansión tableaux
tiene todas las ramas cerradas:

∀x(Px  Qx)

∃x(Px  Rx)

 ∃x(Qx  Rx)]

80
Primero instanciamos la segunda fórmula:

∀x(Px  Qx)

∃x(Px  Rx)

 ∃x(Qx  Rx)]

Pa  Ra

A continuación expandimos Pa  Ra, e instanciamos la primera fórmula,

tenemos:

∀x(Px  Qx)

∃x(Px  Rx)

 ∃x(Qx  Rx)]

Pa  Ra

Pa

Ra

Pa  Qa

Pa Qa

81
Hemos cerrado una rama. Ahora instanciamos la fórmula  ∃x(Qx Rx)]
y continuamos la expansión, legando a un tableaux cerrado en todas sus
ramas:

∀x(Px  Qx)

∃x(Px  Rx)

 ∃x(Qx  Rx)]

Pa  Ra

Pa

Ra

Pa  Qa

Pa Qa

 Qa  Ra)

Qa Ra

Qa

6. CONSECUENCIA: CÁLCULO (DEDUCCIÓN NATURAL)

6.1 CONSECUENCIA EN PREDICADOS
El concepto de consecuencia es similar al enunciado en lógica
proposicional, a lo sumo, volvemos a recordar que el número de
interpretaciones posibles es ahora infinito. Es decir, para descartar que una

82
fórmula es consecuencia de otras se puede operar como en proposicional:
basta encontrar una interpretación que satisface todas las hipótesis pero no
la supuesta consecuencia. No obstante, para confirmar que una fórmula es
consecuencia de otras ya no podemos usar la vía de la confirmación una a
una para toda interpretación posible.

6.2 DEDUCCIÓN NATURAL: INTRODUCCIÓN Y ELIMINACIÓN DE

CUANTIFICADORES

6.2.1 Introducción

Las reglas de Deducción Natural permiten ir generando (o comprobando,

según se usen) consecuencias a partir de un conjunto de premisas. Pero
construir demostraciones a ese nivel de detalle es equiparable a escribir
programas sólo con unos pocos microinstrucciones de un procesador. Lo
que se pretende en esta asignatura no es garantizar que se sabe construir
demostraciones, sino más bien que se sabe reconocer cuándo una que se
nos facilita (completamente explicitada) es correcta. Es decir, poder validar
que todos los pasos son correctos.

6.2.2 Cuantificadores universales

Fig. 76 Reglas de eliminación e introducción del cuantificador universal

Ejemplo eliminación:
1 ∀y(Py Qy) premisa

2 Pa premisa

3 Pa  Qa ∀yE: 1

4 Qa E: 2,3

83
Ejemplo de introducción

1 ∀x(Px  Qx) premisa

∀y(Qy  Sy) premisa

2

3 Pa  Qa ∀xE: 1

4 Qa  Sa ∀yE: 2

5 Pa suposición

6 Qa E: 3,5

7 Sa E: 4,6

8 Pa  Sa I: 5,7

9 ∀x(Px  Sx) ∀xI: 8

6.2.3 Cuantificadores existenciales

Fig. 77 Reglas de introducción y eliminación del cuantificador existencial

84
Ejemplo introducción

1 ∀x(Px  Qx) premisa

2 Pa  Qa ∀xE: 1

3 Pa E: 2

4 Pa  Sa I: 3

5 ∃x(Px  Sx) ∃xI:4

Ejemplo de eliminación

1 ∃x(Px  Qx) premisa

2 Pa  Qa Suposición

3 Pa E: 2

4 ∃xPx ∃xI 3

5 ∃xPx ∃xE:1,2

85
 RESUMEN
LÓGICA PROPOSICIONAL

Tablas de verdad

86
Equivalencias

87
Reglas de expansión de los nodos en un tableaux

88
Reglas básicas de la Deducción Natural

89
LÓGICA DE PREDICADOS

Reglas de expansión de los nodos en un tableaux

90
Deducción Natural: Introducción y eliminación de cuantificadores

91