Excelentes apuntes de lógica de la Universidad Rey Juan Carlos _URJC__ Conjuntos_ Relaciones_ Logica de proposiciones_ tableaux_ predicados___

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

logica/tema1.pdf
Tema 1
Introducción a la teoŕıa de conjuntos
Antes de empezar propiamente con el estudio de la lógica vamos a necesitar unos
conocimientos previos de teoŕıa de conjuntos, tanto para poder dar unas definiciones
formales de alfabetos y otras construcciones como para trabajar con modelos en la
lógica proposicional, además de la relación teórica directa entre estas dos materias, pues
muchos conjuntos se definen a partir de propiedades lógicas.
Las recomendaciones bibliográficas para este material son:
• FERNÁNDEZ LAGUNA, V., Teoŕıa básica de conjuntos, Anaya 2003.
• ROSEN, K.H., Matemática discreta y sus aplicaciones, McGraw-Hill 2004. Las tres
últimas secciones del primer caṕıtulo tratan sobre conjuntos.
• MANZANO,M. y HUERTAS, A., Lógica para principiantes, Alianza 2004.
1 Nociones básicas
De manera intuitiva, un conjunto es cualquier agrupación o colección claramente delimi-
tada de objetos (usualmente abstractos), que determinan dicho conjunto. A los conjuntos
se les suele notar por letras mayúsculas (A,B, C,. . . ) y a los elementos que los forman
por minúsculas (a, b, c,. . . ). Cuando un determinado elemento a forma parte de un de-
terminado elemento A se dice que a pertenece a A, y se escribe a ∈ A. En caso contrario
se dice que a no pertenece a A y se escribe a 6∈ A.
Un conjunto se define al conocer todos los elementos que lo forman. Esto permite
dos maneras de definir conjuntos:
• Conjuntos definidos por extensión: dando una lista de todos sus elementos, usual-
mente entre llaves y separados por comas. Por ejemplo:
– A = {1, 3, 5} es el conjunto formado por los números uno, tres y cinco. En
este caso podemos decir 1 ∈ A, 2 6∈ A, 3 ∈ A, 4 6∈ A, etc. También podemos
decir, por ejemplo, que rojo 6∈ A.
• Conjunto definido por comprensión: dando una propiedad que sea cumplida exacta-
mente por los elementos del conjunto. Si dicha propiedad (expresable en el lenguaje
de la lógica) es P , entonces el conjunto de los elementos que tienen la propiedad
P se escribe como {x : P (x)}, donde los dos puntos (en algunos lugares se utiliza
una barra vertical) se leen como ”tal que”. Por ejemplo:
1
– N = {x : x es un número natural} denota al conjunto de los números natu-
rales.
– B = {x : x es el doble de algún número natural} denota al conjunto de los
números pares.
Cualquier conjunto se puede definir por comprensión (por ejemplo, A = {x : x ∈ 1, 3, 5}),
pero sólo los conjuntos finitos pueden definirse por extensión (de hecho, a efectos prácti-
cos sólo los conjuntos los bastante pequeños pueden definirse por extensión, limitando
el tamaño los recursos f́ısicos de los que dispongamos para la representación, como la
memoria del ordenador).
Pese a esto, la definición de un conjunto por comprensión dada de manera ingenua
presenta ciertos problemas. Por ejemplo, si definimos
M = {x : x 6∈ x}
resulta que no tendremos claro si M ∈ M o M 6∈ M , ya que si M ∈ M , por la
definición de M tendŕıa que ser M 6∈ M y viceversa. Esta situación es conocida como
paradoja de Russell, que indica que hay que tener restricciones considerables a la hora
de manejar conjuntos. La restricción concreta para evitar esta paradoja es el axioma de
especificación: para definir un conjunto a partir de una propiedad P es necesario partir
de algún otro conjunto, digamos C, de manera que los elementos de C que verifican P
śı que forman un conjunto, {x ∈ C : P (x)}.
Seguiremos la notación matemática clásica de conjuntos numéricos:
• N = {1, 2, 3, . . .} representa los números naturales.
• Z = {. . . ,−2,−1, 0, 1, 2, . . .} representa el conjunto de los números enteros.
• Q representa el conjunto de los números racionales (aquellos que se pueden escribir
como fracción, que no es igual al conjunto de las fracciones).
• R representa el conjunto de los números reales.
1.1 Representación de conjuntos
Para representar gráficamente conjuntos generales se suelen representar diagramas de
Venn, que consisten en ĺıneas cerradas que dejan dentro los elementos del conjunto y
fuera los demás.
A veces, con conjuntos numéricos o pequeños interesa representarlos en una recta
(representación muy adecuada para los productos cartesianos).
Por ejemplo, el conjunto {1, 2, 3, 5} podŕıa representarse como (ver página siguiente):
2
1
2
3
5
1
3
5
2
1 2 3 5
Figura 1: Tres representaciones de {1, 2, 3, 5}
1.2 Igualdad de conjuntos
Hemos dicho que un conjunto queda determinado por sus elementos. Esto permite definir
formalmente la igualdad de conjuntos. Dados dos conjuntos A y B, A = B cuando se
verifican estas dos condiciones:
• si x ∈ A, entonces x ∈ B.
• si x ∈ B, entonces x ∈ A.
Por ejemplo, si A = −1, 1 y B =
{
x : x2 − 1 = 0
}
, está claro que todos los elementos
de A verifican la ecuación que define B, y que cualquier solución de la ecuación que
define B está en A, con lo que A = B.
Una situación interesante se da cuando se cumple una de las dos condiciones nece-
sarias para la igualdad. Formalmente, dados dos conjuntos A y B, A está contenido en
B si para cualquier x ∈ A se tiene que x ∈ B, y se escribe A ⊂ B. Hay que tener en
cuenta que la inclusión permite la igualdad como caso extremo (si A = B, ocurre que
A ⊂ B y B ⊂ A).
Por ejemplo, una cadena de contenidos clásica es
N ⊂ Z ⊂ Q ⊂ R
Para conjuntos más concretos, si A = {1, 3, 5, 7, 9} y B = {1, 2, 3, 4, 5, 6, 7, 8, 9},
está claro que A ⊂ B.
Un conjunto extremadamente importante es el conjunto vaćıo, el conjunto que no
tiene ningún elemento, representado por ∅. No debe confundirse con {∅}, que es un
conjunto con un elemento, el propio ∅. El conjunto vaćıo aparece de manera natural
al aplicar el axioma de especificación a conjuntos que no tienen ningún elemento que
verifique la propiedad requerida. Por ejemplo:{
x ∈ R : x2 + 1 = 0
}
= ∅
1.3 Operaciones con conjuntos
A partir de dos conjuntos A y B es posible construir nuevos conjuntos.
3
• La unión de A y B, escrita como A∪B, es el conjunto cuyos elementos pertenecen
a A o a B.
• La intersección de A y B, escrita como A ∩ B, es el conjunto cuyos elementos
pertenecen simultáneamente a A y a B. Dos conjuntos cuya intersección es vaćıa
(A ∩B = ∅) se dice que son disjuntos.
• La diferencia o complemento relativo de A respecto a B, escrito A \ B (léıdo
informalmente como A menos B) es el conjunto formado por los elementos de A
que no están en B
A
B
A
B
A ∪B A
B
A ∩B A
B
A \B
Figura 2: Unión, intersección y diferencia.
Para definir la otra operación interesante de dos conjuntos es necesario un poco de
notación. Dados dos elementos a y b, podemos formar el conjunto que contiene justo a
esos dos elementos (esto es un axioma), es decir, {a, b}, pero dicho conjunto no distingue
el posible orden en el que se encuentren a y b, es decir, {a, b} = {b, a}.
Para arreglar esto definimos el par ordenado (o simplemente par) (a, b) de manera
que dicho par quede especificado por sus dos elementos y su orden, es decir, (a, b) = (c, d)
si y sólo si a = c y b = d. Con esto definimos el producto cartesiano de A y B, escrito
A × B, como el conjunto de todos los posibles pares ordenados en los cuales el primer
elemento pertenece a A y el segundo elemento pertenece a B. Formalmente:
A×B = {(a, b) : a ∈ A, b ∈ B}
El producto cartesiano de dos conjuntos suele representarse a partir de la repre-
sentación en dos rectas perpendiculares de cada conjunto, tomando cada par ordenado
como el punto que tiene por coordenada horizontal el primer elemento del par y como
coordenada vertical el segundo.
Otro conjunto que podemos obtener a partir de un conjunto dado es el conjunto de
las partes de dicho conjunto, P(A), que consiste en el conjunto formado por todos los
subconjuntos de A, es decir:
P(A) = {B : B ⊂ A}
4
a
b
1 2 3
(1, a)
(1, b)
(2, a)
(2, b) (3, b)
(3, a)
Figura 3: El producto cartesiano {1, 2, 3} × {a, b}
En particular, ∅ ∈ P(A) sea cual sea el conjunto A, pues el conjunto vaćıo es subconjunto
de cualquier conjunto.
Por ejemplo, si A = {x, y, z}, entonces
P(A) = {∅, {x} , {y} , {z} , {x, y} , {x, z} , {y, z} , {x, y, z}}
1.4 Propiedades de las operaciones
Las operaciones antes definidas con los conjuntos tienen muchas propiedades. Las más
importantes son las siguientes:
• Idempotencia de la unión y la intersección:
A ∪A = A
A ∩A = A
• Conmutativia de la unión y la intersección:
A ∪B = B ∪A
A ∩B = B ∩A
• Asociativa de la unión y la intersección:
A ∪ (B ∪ C) = (A ∪B) ∪ C
A ∩ (B ∩ C) = (A ∩B) ∩ C
• Distributiva de la unión respecto a la intersección y de la intersección respecto a
la unión:
A ∪ (B ∩ C) = (A ∪B) ∩ (A ∪ C)
A ∩ (B ∪ C) = (A ∩B) ∪ (A ∩ C)
5
• Propiedades del conjunto vaćıo:
A ∪ ∅ = A
A ∩ ∅ = ∅
• Leyes de De Morgan
C \ (A ∪B) = (C \A) ∩ (C \B)
C \ (A ∩B) = (C \A) ∪ (C \B)
• Propiedades de la diferencia de conjuntos:
(A \B) ∪B = A ∪B
(A \B) ∩B = ∅
A \ (A \B) = A ∩B
Todas estas propiedades hacen referencia a la igualdad de conjuntos. Como los con-
juntos se definen por sus elementos, para probar que A = B basta comprobar que A ⊂ B
y B ⊂ A. Por ejemplo, si queremos probar que A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) hay
que probar dos contenidos:
• A ∪ (B ∩ C) ⊂ (A ∪B) ∩ (A ∪ C)
Para ello tomo un x ∈ A∪(B∩C). Dicho x debe estar o bien en A o bien en B y C
simultáneamente. Si x está en A, entonces está tanto en A∪B como en A∪C, con lo
que está en su intersección (que es lo que nos interesa). Si x está simultáneamente
en B y C, entonces también está en A ∪ B y en A ∪ C, con lo que está en su
intersección. Sea cual sea el caso hemos comprobado que x ∈ (A ∪ B) ∩ (A ∪ C),
obteniendo el primer contenido.
• (A ∪B) ∩ (A ∪ C) ⊂ A ∪ (B ∩ C)
Para ello, si x ∈ (A∪B)∩(A∪C), entonces se dan simultáneamente dos situaciones:
– Por un lado, x está o bien en A o bien en B.
– Por otro lado, x está o bien en A o bien en C.
Si x estuviese en A, también estaŕıa en A ∪ (B ∩ C), con lo que los problemas
aparecen si x no está en A, pero en este caso sabemos que, por un lado, x debe
estar en B, y por otro x debe estar en C. Aśı pues, x está en B ∩ C, y por tanto
en A ∪ (B ∩ C), habiendo obtenido el segundo contenido.
6
1.5 Cardinal de un conjunto
Se define el cardinal de un conjunto finito A, Card(A) o |A|, como el número de elemen-
tos de dicho conjunto. Si el conjunto A es infinito, decimos que su cardinal es infinito
(Card(A) = |A| = ∞). Como propiedades bastante sencillas de los cardinales podemos
citar:
• |∅| = 0.
• |A ∪B| = |A|+ |B| − |A ∩B| ≤ |A|+ |B|.
• Combinando las dos propiedades anteriores, resulta que si A ∩ B = ∅, entonces
|A ∪B| = |A|+ |B|.
• |P(A)| = 2|A|.
• |A×B| = |A| · |B|.
Algunos ejemplos sobre cardinales:
• |N| = ∞.
• Si A = {1, 3, 5, 7, 9} y B = {1, 2, 3, 4, 5}, entonces A ∪ B = {1, 2, 3, 4, 5, 7, 9} y
A ∩B = {1, 3, 5}, con lo que
7 = |A ∪B| = |A|+ |B| − |A ∩B| = 5 + 5− 3
2 Relaciones binarias
A veces interesa relacionar elementos de dos conjuntos de manera que podamos ser
capaces de decidir cuando se produce una determinada relación entre elementos. Por
ejemplo, si consideramos todos los alumnos de una facultad (primer conjunto) y todas
las asignaturas que se imparten en ella (segundo conjunto), una relación interesante seŕıa
la que ligase cada alumno con las asignaturas que cursa (relación que seŕıa la misma que
la que asigna cada asignatura con los alumnos). Más formalmente:
Si A y B son dos conjuntos no vaćıos, una relación binaria entre A y B es un
subconjunto R del producto cartesiano A×B. En general, si (a, b) ∈ R se suele escribir
aRb.
Aśı, si A es el conjunto de todos los alumnos de una facultad y B es el conjunto de
todas sus asignaturas, la relación mencionada antes seŕıa:
R = {(a, b) ∈ A×B : El alumno a cursa la asignatura b}
Otro ejemplo seŕıa, dados A = {1, 2, 3} y B = {a, b}, la relación R = {(1, a), (1, b), (2, a), (3, b)}.
Cuando en una relación binaria R resulta que A = B (es decir, R ⊂ A×A), se dice
que R es una relación binaria en A.
Dada una relación binaria R entre A y B, se definen
7
• El dominio de R como
dom(R) = {a ∈ A : hay algún b ∈ B con (a, b) ∈ R}
• La imagen directa o rango de R como
Im(R) = {b ∈ B : hay algún a ∈ A con (a, b) ∈ R}
• La imagen inversa o rećıproca de C ⊂ B como
R−1(C) = {a ∈ A : hay algún b ∈ C con (a, b) ∈ R}
• El codominio de R como el conjunto B.
2.1 Tipos de relaciones binarias en A
El concepto de relación binaria es muy amplio, y por tanto matemáticamente (y lógica-
mente) poco interesante. En general, nos interesaran las relaciones binarias que cumplan
determinados tipos de propiedades. Las más importantes son las siguientes:
• Reflexivas: aquellas en las que aRa para cualquier a ∈ A.
• Simétricas: aquellas en las que, si a, b ∈ A y además se verifica que aRb, entonces
también se tiene que bRa.
• Antisimétricas: aquellas en las que, dados a, b ∈ A, si se verifica simultáneamente
que aRb y que bRa, entonces a = b.
• Transitivas: aquellas en las que, dados a, b, c ∈ A, si se verifica que aRb y que bRc,
entonces también se verifica que aRc.
Como ejemplos de estos tipos de relaciones:
• Si A es el conjunto de personas y R es la relación de paternidad, dicha relación no
es de ningún tipo de las anteriores (no cumple ninguna de las cuatro propiedades).
• Dado un conjunto A, en P(A) podemos definir la relación
R = {(B,C) ∈ P(A)× P(A) : B ⊂ C}, que resulta ser reflexiva, antisimétrica y
transitiva.
• En Z, la relación R = {(m,n) ∈ Z× Z : m− n es par} es reflexiva, simétrica y
transitiva.
• Si A es el conjunto de todas las rectas del plano y R es la relación de ortogonalidad,
dicha relación no es reflexiva, es simétrica y no es transitiva.
8
2.2 Relaciones de equivalencia
Una relación binaria R en un conjunto A es relación de equivalencia si es simultáneamen-
te reflexiva, simétrica y transitiva. Usualmente las relaciones de equivalencia se indican
por a ∼ b en lugar de aRb.
Las relaciones de equivalencia indican similitudes entre los elementos de un conjunto
(de hecho la relación de igualdad es una relación de equivalencia). Por ejemplo, en
el conjunto A de las personas la relación de tener la misma edad es una relación de
equivalencia.
Si ∼ es una relación de equivalencia en un conjunto A, y a es un elemento de A,
podemos considerar el siguiente conjunto:
C(a) = {x ∈ A : a ∼ x}
Dados a, b ∈ A, resulta que sólo hay dos posibles opciones: o bien C(a) = C(b) (cuando
a ∼ b), o bien C(a) y C(b) son disjuntos (cuando a 6∼ b). A cada uno de estos conjuntos
se le llama clase de equivalencia.
Esto nos permite definir una partición del conjunto A en sus distintas clases de
equivalencia, disjuntas dos a dos y de manera que cubren todo el conjunto A.
Por ejemplo, si en Z definimos la relación de equivalencia
R = (m,n) ∈ Z× Z : m− n es par, resulta que sólo hay dos clases de equivalencia, C(0)
formada por todos los enteros pares, y C(1) formada por todos los enteros impares.
Otro ejemplo t́ıpico en matemáticas es el siguiente. Consideramos el conjunto de
referencia
F =
{m
n
: m ∈ Z, n ∈ Z, n 6= 0
}
y en el la siguiente relación de equivalencia:
R =
{
(
m
n
,
p
q
) ∈ F × F : mq = np
}
es decir, dos fracciones están relacionadas cuando son equivalentes (representan el mismo
número). Las clases de equivalencia de F son precisamente los números racionales Q.
3 Relaciones n-arias
En esta sección vamos a extender la idea de relación binaria a otra más general que
va a permitir relacionar más de dos objetos. Por ejemplo, si tenemos tres conjuntos: los
alumnos de una facultad, las asignaturas que se imparten en dicha facultad y las posibles
notas que se pueden obtener, podŕıa resultar útil una relación que ligase cada alumno
con las asignaturas que ha cursado y las notas que ha obtenido en cada una de ellas.
Para empezar necesitamos extender la definición de producto cartesiano a más de
dos conjuntos. Para ello vamos a utilizar una técnica muy usual, definir el concepto de
n-tupla ordenada por inducción.
9
Ya sabemos definir un par ordenado (2-tupla) (a, b). Para definir una terna ordenada
(a, b, c) podemos utilizar la definición de par ordenado de la siguiente manera:
(a, b, c) = (a, (b, c))
Continuando con esto podemos definir, a partir de terna ordenada:
(a, b, c, d) = (a, (b, c, d))
y aśı sucesivamente, de manera que una n-tupla ordenada se define como
(a1, a2, . . . , an) = (a1, (a2, . . . , an))
La propiedad principal de una n-tupla es la siguiente: (a1, a2, . . . , an) = (b1, b2, . . . , bn)
si y sólo si a1 = b1, a2 = b2,. . . , an = bn.
Las n-tuplas o sucesiones finitas son importantes en lógica, pues nos permiten definir
palabras a partir de un alfabeto (el cual, por supuesto, es un conjunto).
Con esto, si A1, A2, . . . , An son conjuntos no vaćıos, se define el producto cartesiano
de dichos conjuntos como
A1 ×A2 × · · · ×An = {(a1, a2, . . . , an) : a1 ∈ A1, a2 ∈ A2, . . . , an ∈ An}
Dados n conjuntos no vaćıos A1, A2, . . . , An, una relación de aridad n o relación n-
aria es un subconjunto R del producto cartesiano a1×A2×· · ·×An. Si (a1, a2, . . . , an) ∈
R, se dice que a1, a2, . . . , an están relacionados.
4 Funciones
Aunque formalmente una función es una relación, intuitivamente es una noción más
dinámica que se suele corresponder con una asignación, de manera que a un objeto
(usualmente un número o una n-tupla de números) se le asigna otro objeto, usualmente
mediante algunos cálculos sobre el objeto de partida.
Formalmente, una función o aplicación f de un conjunto A en otro conjunto B,
f : A → B, es una relación binaria f ⊂ A×B que verifica que
• dom(f) = A.
• Si a ∈ A hay un único b ∈ B de manera que (a, b) ∈ f . A dicho b se le llama
imagen de a por f , y se escribe f(a).
A veces es interesante la estructura del dominio A de la función. Si A ⊂ A1 × A2 ×
· · ·×An, se dice que la función es (n+1)-aria. En este caso, si a = (a1, a2, . . . , an) ∈ A1×
A2×· · ·×An, se escribe f(a1, a2, . . . , an) en lugar de f(a). Cuando A = A1×A2×· · ·×An
se dice que la función es una operación (aunque a veces el término función se utiliza en
el sentido de operación).
Como ejemplo de funciones tenemos:
10
• f : R → R dada por f = {(x, x) ∈ R× R : x ∈ R} es una función de dominio R y
rango R y tal que f(x) = x.
• f : R → R dada por f =
{
(x, x2) ∈ R× R : x ∈ R
}
es una función con dom(f) =
R, Im(f) = [0,+∞) y tal que f(x) = x2
Es muy usual definir funciones a partir de f(x), por ejemplo f(x) = 3
x2−1 . El pro-
blema de este tipo de definiciones es que no se indica el dominio. Siempre supondremos
que el dominio es el conjunto más amplio posible donde está bien definida la imagen de
x. En el ejemplo, dom(f) = R \ {−1, 1}.
De la propia definición de función se deduce que dos funciones f, g ⊂ A × B son
iguales si y sólo si se dan estas dos condiciones:
• dom(f) = dom(g)
• Si a ∈ dom(f) = dom(g), entonces f(a) = g(a).
Una operación muy interesante para funciones (que también puede definirse para
relaciones) es la composición. Si f : A → B y g : B → C, la composición de f y g es la
función g ◦ f : A → C dada por (g ◦ f)(a) = g(f(a)) para a ∈ A, es decir:
g ◦ f = {(a, g(a)) ∈ A× C : a ∈ A}
Por ejemplo, si A es el conjunto de las personas y f es la función que a cada persona
le asigna su madre (es una relación uńıvoca, y por tanto una función), la función f ◦ f
es la que a cada persona le asigna su abuela.
11
logica/tema2.pdf
Tema 2
Sintaxis de la lógica proposicional
El art́ıculo ”Lógica”que aparece en la decimocuarta edición de la Enci-
clopedia Británica (1929) comienza del siguiente modo: ”Lógica es el estudio
sistemático de las condiciones generales de validez de inferencias... Inferen-
cia es el acto o proceso de derivar una proposición de otra u otras.
Este concepto ha ido evolucionando con el tiempo: Aśı, treinta años
más tarde, en la decimoséptima edición de dicha enciclopedia (1959) pode-
mos encontrar la siguiente definición (Alonzo Church): ”Lógica es el estudio
sistemático de la estructura de las proposiciones y de las condiciones gen-
erales de validez de inferencias por un método que abstrae el contenido de
las proposiciones y que tiene que ver sólo con su forma lógica”.
Es importante reflexionar, aunque sea brevemente, sobre la diferencias
entre ambas definiciones, debiendo destacarse, como un primer y gran des-
cubrimiento de la Lógica, que la validez de una deducción depende exclusi-
vamente de la forma que ésta tenga, y no del significado de las sentencias
que en ella intervengan.
Como ahora veremos, la ”forma”de una sentencia tiene que ver con su
”sintaxis”, y su significado, en definitiva, con su valor de verdad (si es ver-
dadera o falsa).
En todo caso, la lógica siempre hace referencia a un lenguaje (es la lógica
de un lenguaje) y, como veremos, cuanto mayor sea la capacidad de expresión
de un lenguaje, menos propiedades tendrá su lógica asociada.
En todo caso al estudiar cualquier lógica (proposicional, de primer orden,
de segundo orden, infinitaria,...) siempre aparecen dos tipos de elementos:
Por una parte están las estructuras (en definitiva, los objetos) y por otra el
lenguaje con el que nos referimos (o enunciamos propiedades) a esas estruc-
turas (objetos).
Para comenzar vamos a estudiar la lógica más sencilla de todas, la lógica
proposicional, que partiendo de proposiciones simples (sentencias o frases
declarativas a las que se les puede asignar el valor verdadero (V) o el valor
falso (F)) permite construir proposiciones compuestas, utilizando para ello
los conectivos lógicos. ”negación”, çonjunción”, ”disyunción”, ı̈mplicación 2
.equivalencia”. A destacar que el lenguaje formal de la ´lógica proposicional
no se preocupa por el çontenido o significado”de las proposiciones, sino por
su verdad o falsedad y por las maneras de conectarse entre ellas.
1
Las recomendaciones biblográficas para este tema son, de la bibliograf́ıa
general, los libros de MANZANO Y HUERTAS, HORTALÁ, LEACH Y
RODRÍGUEZ. Con un tratamiento más ligero es útil el libro de ROSEN, y
con un tratamiento más avanzado el de ENDERTON.
Además, aunque sean libros de lógica recreativa son muy recomendables
los siguientes libros de R. M. SMULLYAN: ¿Cómo se llama este libro?, La
dama y el trigre y Alicia en el páıs de las adivinanzas, todos ellos publicados
en la colección Teorema de Ediciones Cátedra.
1. Introducción a la lógica proposicional
En el lenguaje natural (en este caso el castellano) podemos enunciar mu-
chos tipos de sentencias (oraciones), con diferentes significados. Por ejemplo:
1. Si estudias constantemente la asignatura, seguro que la apruebas.
2. Hay estudiantes que cuando estudian de manera constante, aprueban.
3. Cuando un alumno aprueba una asignatura es debido a que la ha
estudiado de manera seria.
4. Si estudiases seriamente podŕıas aprobar.
5. Debeŕıas estar estudiando.
En todos estos ejemplos estamos hablando de la misma situación, pero los
significados son muy distintos. La sentencia del primer ejemplo es sencilla, y
posiblemente verdadera (quizá pueda ser falsa, pero no puede ser verdadera
o falsa al mismo tiempo). La segunda también puede ser verdadera o falsa,
pero esto depende de circunstancias externas a la estructura directa de la
oración (en concreto, depende de cuales sean los estudiantes y la asignatura).
La tercera es una oración muy parecida a la segunda, pero su significado es
muy distinto, aunque su estructura sea la misma. Las dos últimas oraciones
no tienen un valor de verdad o falsedad claramente definidos, indican más
bien opiniones, sugerencias u ordenes.
En la lógica proposicional vamos a estudiar las sentencias (u oraciones) de
los ejemplos primero y tercero. Es decir, vamos a dejar de lado los enunciados
cuya verdad dependa de circunstancias externas al propio enunciado, y los
enunciados ambiguos, subjetivos o imperativos (aunque estos últimos son
muy útiles a la hora
de programar).
Como un ejemplo antes de empezar, para hacer una traducción direc-
ta, podemos codificar los enunciados estudiar la asignatura por la letra p
y aprobar la asignatura por la letra q. Entonces la estructura del primer
ejemplo seŕıa:
Si p entonces q
2
y la del segundo seŕıa:
Si q entonces p
Lo primero interesante de la formalización que hemos hecho: si nos olvi-
damos de la traducción, tenemos el contenido formal de dos proposiciones
distintas. Para trabajar lógicamente con ellas no es necesario conocer su sig-
nificado, sólo si son ciertas o falsas. Otra diferencia, más importante de lo
que parece: los enunciados originales, aunque teńıan la misma estructura, es-
taban expresados de forma muy distinta, y al formalizarlos han resultado ser
similares. Esta es otra ventaja del lenguaje formal: perdemos ambigüedad.
Antes de continuar hablando de traducciones y de manejar el lenguaje
de la lógica proposicional, debemos definirlo de manera clara para poder
trabajar formalmente (tanto de manera matemática como informática) con
él.
2. Alfabeto de la lógica proposicional
Para empezar, antes de describir la sintaxis de la lógica proposicional
debemos definir claramente el conjunto de śımbolos con los que vamos a
trabajar y el papel de cada uno.
Definición 1. Un alfabeto A es un conjunto de śımbolos. Una palabra sobre
un alfabeto A es una secuencia finita de śımbolos de A. Al conjunto de todas
las posibles palabras del alfabeto A se le denota por A∗.
Un lenguaje sobre un alfabeto A es cualquier subconjunto de A∗. Las
reglas de formación de un lenguaje son reglas que permiten obtener palabras
(o lo que es lo mismo, fórmulas) de dicho lenguaje a partir de palabras
conocidas.
Ejemplo 2. Por ejemplo, podemos describir del modo siguiente el lenguaje
H sobre el alfabeto
A = {♡,♠}
cuyas fórmulas son las cadenas finitas que terminen con el śımbolo ♠
H={♠,♡♠,♡♠♡♠,♡♡♠♠, ...}.
Una vez establecidos los conceptos de alfabeto y lenguaje sobre un alfa-
beto, vamos a definir los elementos del alfabeto de la lógica proposicional:
Las proposiciones atómicas (enunciados simples o variables proposi-
cionales): son proposiciones (oraciones declarativas que son verdaderas
o falsas. Para representarlas se suelen utilizar los śımbolos p, q, r,. . . .
3
Observación 3. La utilización de las letras del abecedario a partir
de la p es muy útil para trabajar con teoŕıa y con ejemplos sencillos,
pero se puede quedar muy corta en casos complicados. Una manera de
resolverlo es reservar una única letra para las proposiciones atómicas,
digamos la p, y utilizar sub́ındices, es decir, usar como śımbolos p1,
p2, p3,. . . . Esto nos permite tener acceso a una cantidad ilimitada de
śımbolos distintos.
Si aún aśı queremos ahorrar más, podemos utilizar un śımbolo como
”′”para distinguir los distintos śımbolos en lugar de los sub́ındices,
teniendo aśı p, p′, p′′, etc. Este tipo de notación es muy incómoda en
la práctica, pero puede ser útil para los resultados teóricos.
Los conectivos lógicos: permiten formar proposiciones compuestas. Se
clasifican según su aridad (el número de proposiciones que conectan).
Son los siguientes:
• Constantes (de aridad 0): son ⊤ (verdadero) y ⊥ (falso).
Observación 4. Cuando estudiemos la semántica veremos que
los conectivos se corresponden con determinadas funciones sobre
valores de verdad. Una función de aridad 0 es una función que no
tiene argumentos, es decir, una constante.
• Conectivos unarios: ¬ (negación).
• Conectivos binarios:∨ (disyunción), ∧ (conjunción), → (condi-
cional o implicación) y ↔ (doble condicional o coimplicación).
Observación 5. Utilizaremos el śımbolo ◦ como comod́ın para
designar cualquier conectivo binario.
Los śımbolos de puntuación: paréntesis izquierdo y derecho y coma.
Ejemplo 6. Si consideramos las siguientes proposiciones simples:
p: el número π es irracional.
q: hoy es martes.
r: el fin justifica los medios.
podŕıamos considerar las siguientes combinaciones:
el fin no justifica los medios: (¬r).
el número π no es racional: (¬p).
Observación 7. La proposición ”hoy es lunes”no se formalizaŕıa como
(¬q), pues no es su negación (que seŕıa ”hoy no es martes”).
4
si hoy es martes entonces el fin justifica los medios: (q → r).
el número π es irracional si y sólo si hoy es martes: (p↔ q).
hoy es martes o el fin no justifica los medios: (q ∨ (¬r)).
hoy no es martes y el número π es irracional: ((¬q) ∧ r).
3. Definición recursiva de las fórmulas bien con-
struidas
Ya tenemos un alfabeto y una cierta noción de traducción para utilizar
dicho alfabeto. Ahora necesitamos una sintaxis, un conjunto claro de reglas
de formación de palabras correctas, es decir, unas reglas que nos permitan
escribir todas las expresiones del lenguaje de la lógica proposicional.
Como es bastante obvio, las expresiones correctas son infinitas, con lo que
no podemos dar una lista. Para caracterizar dichas expresiones daremos una
definición constructiva: indicaremos expĺıcitamente cuales son las fórmulas
más sencillas y también como formar formulas más complejas a partir de las
sencillas.
Definición 8 (Definición recursiva de las fórmulas bien constuidas). Las
fórmulas bien construidas (o simplemente fórmulas) de la lógica proposi-
cional son aquellas que se construyen a partir de las siguientes cuatro reglas:
1. (At): Las proposiciones atómicas y los śımbolos ⊤ y ⊥ son fórmulas.
2. (¬): Si ϕ es una fórmula, entonces (¬ϕ)es una fórmula.
3. (◦): Si ϕ y ψ son fórmulas, entonces (ϕ ◦ ψ) es una fórmula.
4. Si una palabra no puede obtenerse a partir de las tres reglas anteriores,
entonces dicha palabra no es una fórmula.
Observación 9. La segunda regla de formación, la correspondiente a la ne-
gación, se define de vaŕıas maneras según los textos. En algunos la negación
de una fórmula es ¬(ϕ), y en otros simplemente ¬ϕ. La ventaja de cerrar
la negación entre paréntesis es una mayor sencillez a la hora de analizar
sintácticamente una fórmula.
Observación 10. Para representar las fórmulas se utilizan letras griegas
(ϕ, ψ, χ, . . .) como śımbolos metalógicos (dichos śımbolos no están dentro de
la lógica proposicional).
Definición 11. Dadas dos fórmulas ϕ y ψ, se dice que ψ es una subfórmula
de ϕ si ψ consiste en śımbolos consecutivos de ϕ. Una fórmula siempre es
subfórmula de si misma.
5
Ejemplo 12. Veamos que la palabra ((p∧ q) → (¬p)) es una fórmula. Para
ello hay que tener en cuenta que p y q son fórmulas (por (At)). A partir
de estas, por (◦) es fórmula (p ∧ q), y por (¬) es fórmula (¬p). De nuevo
aplicando (◦) resulta que ((p ∧ q) → (¬p)) también es una fórmula.
También resulta que p, q, (p∧q), (¬p) y ((p∧q) → (¬p)) son las subfórmu-
las de la fórmula original.
4. Principio de inducción estructural para las fórmu-
las proposicionales
La definición que hemos dado de fórmula puede parecer poco manejable,
pero tiene varias ventajas. Una de ellas es que nos da una manera bastante
natural (al menos en matemáticas) de probar afirmaciones sobre todas las
fórmulas. Esto nos permite trabajar con propiedades de las mismas. Dicho
método es el principio de inducción estructural, de muchas aplicaciones, tan-
to teóricas como prácticas.
Principio de inducción estructural:
Sea C ⊂ A∗ un subconjunto de fórmulas que verifica que:
1. Base de inducción: ⊤, ⊥ y todas las proposiciones atómicas están en
C.
2. Pasos de inducción:
(¬): si ϕ es una fórmula que está en C, entonces (¬ϕ) también
está en C.
(◦): si ϕ y ψ son fórmulas de C, entonces (ϕ ◦ψ) también está en
C.
Entonces el conjunto C coincide con el conjunto de todas las fórmulas.
Observación 13. Este principio es especialmente interesante cuando el con-
junto C se define a partir de una propiedad P, es decir, cuando los elementos
de C son exactamente las fórmulas que tiene la propiedad P. En este caso,
el principio de inducción estructural nos dice que
si las formulas atómicas y
los conectores 0-arios verifican dicha propiedad, que si cuando una formula
la verifica también la verifica su negación, y que si dos fórmulas verifican la
propiedad también lo hacen su conjunción, su disyunción, su condicional y
su bicondicional, entonces todas las fórmulas verifican dicha propiedad.
Ejemplo 14. Veamos que cualquier fórmula contiene la misma cantidad de
paréntesis abiertos que de paréntesis cerrados. Para ello:
6
1. Base de inducción: las fórmulas atómicas y ⊤ y ⊥ tienen la misma
cantidad de paréntesis abiertos que de cerrados: cero.
2. Si ϕ tiene el mismo número de paréntesis abiertos que de cerrados,
(¬ϕ) añade uno de cada tipo, con lo que las cantidades siguen siendo
iguales. Si ϕ tiene n paréntesis de cada tipo, y ψ tiene m, entonces
(ϕ ◦ ψ) tiene n+m+ 1 paréntesis de cada tipo.
5. Representación de fórmulas
5.1. Forma abreviada
La notación usada para las fórmulas es correcta, pero quizá demasia-
do para ser manejable. En el momento en que las fórmulas son un poco
complejas se hacen dif́ıciles de leer y de escribir. Por ejemplo:
(¬(¬(¬(¬(¬(¬(¬(¬(p ∨ (¬(¬(¬q))))))))))))
La forma abreviada de una fórmula consiste en la eliminación de parénte-
sis declarando una cierta prioridad entre los conectivos (de manera muy
parecida a las prioridades en las operaciones aritméticas). Las reglas son las
siguientes:
(a) Se pueden omitir los paréntesis externos.
Aśı por ejemplo, (p ∧ q) pasa a p ∧ q.
(b) Se introducen las siguientes prioridades en cuanto a la aplicación de
conectivos:
(1) La negación (¬).
(2) La conjunción y la disyunción (∧ y ∨).
(3) El condicional y el bicondicional (→ y ↔).
Por ejemplo, (p ∧ (q → r)) queda en p ∧ (q → r) y ((p ∧ q) → r) queda
en p ∧ q → r.
(c) Los conectivos del mismo nivel asocian por la derecha.
Por ejemplo, p ∧ q ∨ r indica p ∧ (q ∨ r)
La forma abreviada es la manera usual de escribir manualmente fórmulas.
5.2. Principio de unicidad estructural
Si ϕ es una fórmula, entonces ϕ pertenece a una y sólo una de las sigu-
ientes categoŕıas:
1. ϕ es una fórmula atómica.
7
2. ϕ es (¬ϕ1) para cierta fórmula ϕ1.
3. ϕ es (ϕ1 ◦ ϕ2) para cierto conectivo binario ◦ y ciertas fórmulas ϕ1 y
ϕ2.
Además, en cada caso las subfórmulas y el conectivo están determinados de
manera única.
Una primera conclusión de este principio es la posibilidad de representar
una fórmula mediante un árbol binario (podemos analizar sintácticamente
una fórmula). Está representación nos permite recorrer los pasos de forma-
ción de una fórmula en el orden que nos convenga.
Sin entrar en definiciones formales (los grafos y los árboles se estudian en
la asignatura Matemática discreta, se puede consultar el libro de ROSEN),
un árbol es un grafo formado por aristas (representadas por segmentos) y
vértices (representados por puntos o por la intersección de dos aristas) unidos
por aristas, de manera que no hay partes aisladas en el grafo (dentro del
mismo siempre hay un camino entre dos vértices cualesquiera) y de manera
que no hay ciclos (sólo hay un posible camino entre dos vértices).
Un árbol con ráız es un árbol con un determinado vértice (la ráız) desta-
cado. Cada vértice se conecta de manera única con la ráız, y todos los vértices
de dicha conexión son los antecesores de dicho vértice. En particular, la ráız
es antecedente de todos los vértices. Si un vértice u es antecedente de otro
vértice v, también se dice que v es descendiente de u. Si en el camino que
une u con la ráız el primer vértice que encontramos es v, se dice que v es el
padre de u o que u es el hijo de v.
Los vértices sin descendientes se llaman hojas. Un vértice que no es ráız
ni hoja es un vértice interno. Un árbol binario es aquel en el que cada vértice
tiene, como mucho, dos hijos.
Cualquier fórmula de la lógica proposicional se puede representar por un
árbol binario, utilizando el principio de unicidad estructural.
Ejemplo 15. Dada la fórmula ((p ∧ (p → r)) ∨ (q ↔ t)), aplicando repeti-
damente el principio de recursión estructural obtenemos el siguiente árbol
(árbol estructural de la fórmula):
8
Las hojas del árbol representan las proposiciones atómicas que inter-
vienen en la fórmula. Cada nodo sobre una o dos fórmulas indica el conectivo
que se les aplica.
6. El principio de recursión estructural
Como veremos más adelante, este principio nos será muy útil poder
definir funciones en el conjunto de las fórmulas de la lógica proposicional
a partir de los valores de dichas funciones en las fórmulas atómicas. En su
versión más sencilla, el principio de recursión establece un modo de definir
funciones, garantizando su existencia y unicidad siempre que satisfaga las
condiciones establecidas en la definición.
En nuestro caso, si llamamos L al conjunto de fórmulas de la lógica
proposicional, el principio de recursión estructural dice lo siguiente:
Proposición 16 (Principio de recursión estructural). Existe una única fun-
ción f : L → A de manera que:
(a) Base: los valores de f están fijados de manera expĺıcita en el conjunto
de las fórmulas atómicas.
(b) Pasos recursivos:
(i) El valor de ¬Φ depende únicamente del valor de f(Φ).
(ii) El valor de Φ ◦Ψ depende únicamente del conector binario ◦ y de
los valores de f(Φ) y f(Ψ).
Este principio nos permite definir funciones a partir del valor que nos
interesa en las fórmulas atómicas y haciendo que el valor de las fórmulas
más complejas dependa únicamente de las fórmulas atómicas que contienen
y de el árbol estructural de la fórmula.
Ejemplo 17. Vamos a definir el grado (degree) de una fórmula como el
número de conectivos (unitarios o binarios) que dicha fórmula contiene, y
vamos a definirlo a partir del principio de recursión estructural. Llamemos
d : L → N a la función grado.
El primer paso es definir expĺıcitamente el grado de las fórmulas atómi-
cas, pero esto es fácil, pues las fórmulas atómicas no tienen conectivos. Por
tanto
d(p) = 0
Ahora toca dar los pasos recursivos, que tampoco son dif́ıciles. Si ϕ es una
fórmula y la negamos, su negación tendrá un conectivo más, y si ϕ y Ψ
son fórmulas, ϕ ◦ Ψ tendrá un conectivo más que las dos juntas. Por tanto
tendŕıamos
d(¬ϕ) = d(ϕ) + 1
d(ϕ ◦ ψ) = d(ϕ) + d(ψ) + 1
9
Ejemplo 18. De manera intuitiva parece razonable definir una subfórmu-
la de una fórmula como cualquier fórmula que se puede obtener quitando
śımbolos del principio o el final de la fórmula original. Ahora bien, esta
definición no es formal, y por tanto puede ser poco operativa tanto para la
teoŕıa como para la programación.
Formalmente definimos una aplicación S : L → P(L). Esta función S
asocia a una fórmula un conjunto de fórmulas (es decir, un subconjunto de
P(L), que pretendemos que sea precisamente el de las subfórmulas.
Empecemos por la base. Está claro que una fórmula atómica p sólo tiene
una subfórmula: ella misma. Por tanto
S(p) = {p}
¡Atención!, estamos definiendo S(p) como un conjunto con una sola fórmula
(p), no como la fórmula p.
Para los pasos recursivos, tenemos que tener un poco más de cuidado.
Supongamos que ϕ es una fórmula y que conocemos todas sus subfórmulas.
Entonces, al formar la fórmula ¬ϕ la única nueva subfórmula que podemos
añadir es la propia ¬ϕ, pues si quitamos śımbolos únicamente del final de
¬ϕ el resultado no será una fórmula (ya que quitaŕıamos un paréntesis y
rompeŕıamos el equilibrio que sabemos tiene que haber). Por tanto
S(¬ϕ) = S(ϕ) ∪ {¬ϕ} (1)
Para los conectivos binarios la situación es muy parecida. Si ϕ y ψ son
fórmulas, y conocemos el conjunto de subfórmulas de cada una, razonando
sobre los paréntesis resulta que la única subfórmula nueva que ϕ◦ψ añadiŕıa
a las de ϕ y ψ seŕıa la propia ϕ ◦ ψ. Por tanto
S(ϕ ◦ ψ) = S(ϕ) ∪ S(ψ) ∪ {ϕ ◦ ψ}
7. Formalización del lenguaje natural
Una vez tenemos una sintaxis completa de la lógica proposicional, llega
la hora
de aplicarla. Para ello, antes de trabajar formalizando razonamientos
necesitamos ser capaces de traducir estos al lenguaje de la lógica. Para for-
malizar razonamientos se suele utilizar la siguiente notación: si ϕ1, ϕ2, . . . , ϕn
son las premisas y ψ es la conclusión que queremos obtener de las premisas,
escribimos:
ϕ1
ϕ2
...
ϕn
ψ
10
A veces también se escribe
ϕ1 ∧ ϕ2 ∧ · · · ∧ ϕn → ψ
Para realizar una traducción (formalización) correcta debemos tener en
cuenta la semántica de los conectores. Siguiendo el libro de cuena podemos
dar las siguientes indicaciones:
¬ϕ: cierto cuando ϕ es falso y falso cuando ϕ es cierto. Se puede tra-
ducir de las siguientes expresiones:
• no ϕ.
• es falso que ϕ.
• no es cierto ϕ.
ϕ ∧ ψ: cierto cuando son ciertos ϕ y ψ simultáneamente. Se puede
traducir de las siguientes expresiones:
• ϕ y ψ.
• ϕ pero ψ.
• ϕ sin embargo ψ.
• ϕ no obstante ψ.
• ϕ a pesar de ψ.
ϕ∨ψ: falso cuando son falsos ϕ y ψ simultáneamente. Se puede traducir
de las siguientes expresiones:
• ϕ o ψ.
• o phi o ψ o ambas cosas a la vez.
• al menos ϕ o ψ.
• como mı́nimo ϕ o ψ.
ϕ→ ψ: es falsa cuando ϕ es falsa y ψ es verdadera. Se puede traducir
a partir de las siguientes expresiones:
• si ϕ entonces ψ
• ϕ sólo si ψ.
• ψ si ϕ.
• ψ es necesario para ϕ.
• ϕ es suficiente para ψ.
• no ϕ a menos que ψ.
• no ϕ o ψ (en esta última frase falta el paréntesis que nunca aparece
en lenguaje natural que nos indique que la negación sólo se aplica
a ϕ).
11
ϕ↔ ψ: cierto o bien cuando ϕ y ψ son ambos ciertos o bien cuando son
ambos falsos. Se puede traducir a partir de las siguientes expresiones:
• ϕ si y sólo si ψ.
• ϕ es necesario y suficiente para ψ.
• ψ es necesario y suficiente para ϕ.
Observación 19. Una buena manera de comprobar la formalización con-
siste en traducir de nuevo esta al lenguaje natural y comparar el resultado
con el enunciado original.
12
logica/tema3.pdf
Tema 3
Semántica(1) de la lógica proposicional
1 Semántica: valoraciones
La semántica es la definición de un conjunto de significados que pueden asociarse a cada
fórmula (en general verdadero o falso). Esta asignación nos permite comprobar cuando
un resultado es válido o no.
Un sistema de demostración es un sistema formal que permiten averiguar si un
razonamiento es válido o no. Si dichos sistemas son semánticos (se basan en el significado
de las fórmulas del razonamiento) se denominan teoŕıa interpretativa. Hay dos tipos de
sistemas de demostración: directos, que aplican una serie de reglas un número finito de
veces que permite llegar de las premisas a la conclusión, e indirectosn o por refutación,
que aplican la regla de reducción al absurdo.
Hab́ıamos designado por Σ al conjunto de las fórmulas atómicas, que se suele deno-
minar signatura.
Definición 1.1. Si L es el lenguaje de la lógica formal, una valoración en L es cualquier
función
v : Σ → {0, 1}
donde 0 representa el significado de falsedad y 1 el de verdad.
Ejemplo 1.2. Si Σ = {p, q}, sólo hay cuatro posibles valoraciones, que se pueden
representar en una tabla:
x p q
v1(x) 0 0
v2(x) 0 1
v3(x) 1 0
v4(x) 1 1
Si añadimos otra proposición atómica, Σ = p, q, r, tendremos 8 posibles valoraciones,
1
que se indican en la siguiente tabla (se ha prescindido de la primera columna)
p q r
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
Usando inducción sobre el número de proposiciones atómicas se prueba que si |Σ| = n,
entonces hay 2n posibles valoraciones distintas.
Al no estar considerando el significado de las proposiciones, sólo hemos definido
las valoraciones de las proposiciones atómicas, ya que seŕıa deseable poder definir el
valor de verdad de las proposiciones compuestas a partir de los valores de verdad de las
proposiciones atómicas de estas y los conectivos utilizados para su formación. Para eso
necesitamos saber como tratan los conectivos a los valores de verdad.
Valores de verdad de los conectivos lógicos
Cada conectivo lógico define una función sobre los posibles valores de verdad de sus
argumentos (lo que se llaman funciones booleanas). Cada una de estas funciones asocia
un determinado valor de verdad a cada una de todas las distintas combinaciones de
valores de verdad de las fórmulas que conecta.
La negación, por ejemplo, es un conectivo 1-ario, que sabemos que cambia el valor
de verdad de una fórmula, es decir, ¬φ es verdadero cuando φ es falso y ¬φ es falso
cuando φ es verdadero. Por tanto este conectivo produce la siguiente función booleana:
B¬ : {0, 1} −→ {0, 1}
0 7→ 1
1 7→ 0
o, en forma de tabla
B¬
0 1
1 0
Por ejemplo, si p denota ”Hoy llueve”, la negación ¬p, ”hoy no llueve”, será verdadera
cuando hoy no llueva, y falsa cuando hoy llueva.
Para estudiar la semántica de las conectivas binarias debemos estudiar cada uno de
los casos:
2
• (∧): la conjunción de dos proposiciones es verdadera únicamente cuando las dos
proposiciones son verdaderas. Por tanto, para que una conjunción sea falsa bas-
tará con que una de las dos proposiciones sea falsa (por supuesto, la conjunción
también será falsa cuando lo sean las dos proposiciones). Por ejemplo, si p indica
”llueveτ q indica ”hace fŕıo”, la conjunción p ∧ q será cierta únicamente cuando
llueva y haga fŕıo simultáneamente. Si llueve y no hace fŕıo, o no llueve y hace fŕıo,
o ni llueve ni hace fŕıo, tendremos que la conjunción es falsa.
• (∨): la disyunción de dos proposiciones es verdadera cuando alguna de las dos
proposiciones sea verdadera (también será verdadera cuando las dos proposiciones
lo sean), y será falsa únicamente en el caso de que las dos sean falsas. Por ejemplo,
con p y q como antes, la disyunción p∨q será cierta si llueve y hace fŕıo, o si llueve
y no hace fŕıo, o si no hace fŕıo pero llueve. Sólo será falsa si ni llueve ni hace fŕıo.
Observación 1.3. En el lenguaje natural muchas veces da la impresión de que
una disyunción debeŕıa ser falsa cuando las dos proposiciones que la forman son
simultáneamente verdaderas. Por ejemplo: realizo el trayecto en coche o en avión”.
Lo que ocurre en este ejemplo es que las dos alternativas son (o parecen ser)
excluyentes (principalmente por que si el trayecto es combinado se suele decir:
realizo el trayecto en coche y en avión”). Sin embargo, si en una oferta de empleo
se lee ”el candidato debe dominar inglés o francés”, esta claro que una persona
que domine los dos idiomas tiene posibilidades de conseguir dicho trabajo. Por
tanto, la disyunción, incluso en el lenguaje natural, es inclusiva (por contra de
la exclusiva, que es verdadera únicamente cuando una proposición lo es y la otra
no). Sea como sea, a veces el lenguaje natural enfatiza de forma clara disyunciones
no inclusivas, como en el primer ejemplo. Al igual que las traducciones entre dos
idiomas distintos, es imposible eliminar la ambigüedad en la traducción.
• (→): estudiar las asignaciones de verdad que realiza el condicional es más compli-
cado que en los casos anteriores, pues al contrario que estos, el condicional no es
conmutativo. Si el condicional es φ→ ψ, a φ se le llama antecedente o premisa y a
ψ se le llama consecuente o conclusión. Para que un condicional sea falso el ante-
cedente debe ser verdadero y el consecuente falso, siendo el condicional verdadero
en el resto de los casos.
Por ejemplo, si considero el condicional: ”si obtienes una nota superior o igual a
cinco aprobarás la asignatura”, pueden darse varios casos:
– un alumno saca cinco o más y aprueba la asignatura: seguro que no hay
ninguna queja.
– un alumno saca menos de cinco y suspende la asignatura: si se comprue-
ba que la nota es realmente menor que cinco (antecedente falso) tampoco
habrá quejas.
– Un alumno saca menos de cinco y aprueba la asignatura: posiblemente tampo-
co haya quejas. Es posible que la nota sea muy cercana a cinco y se redondee,
3
o que otras circunstancias aparte de la nota permitan que la asignatura se
apruebe.
– un alumno saca una nota mayor
o igual que cinco y suspende la asignatu-
ra: entonces el alumno se va a quejar (y con razón), pues ha cumplido el
antecedente, y según el condicional el consecuente debeŕıa estar garantizado.
• (↔): el bicondicional (de nuevo tenemos conmutatividad) es verdadero cuando o
bien son simultáneamente verdaderas las dos proposiciones que lo componen, o
cuando son simultáneamente falsas. Si las proposiciones tienen distintos valores de
verdad, entonces el bicondicional es falso.
Por ejemplo: ”tomarás postre si y sólo si te comes la sopa”será cierto cuando el
interpelado tome tanto el postre como la sopa o cuando no tome ninguno de los
dos. Si toma postre sin tomar la sopa, o la sopa sin tomar el postre, el bicondicional
será falso. Conviene distinguir el significado de este bicondicional del condicional:
”si te comes la sopa tomarás el postre”. En este caso podŕıa ser que el interpelado
no comiese la sopa pero tomase postre.
Resumiendo todo esto, tenemos cuatro funciones booleanas binarias,B∧, B∨, B→, B↔ :
{0, 1}2 → {0, 1}, definidas en la siguiente tabla:
B∧ B∨ B→ B↔
0 0 0 0 1 1
0 1 0 1 1 0
1 0 0 1 0 0
1 1 1 1 1 1
Si ahora trabajamos con una valoración en la signatura con la que estemos trabajan-
do, nos podemos preguntar el valor de verdad de una fórmula que no sea atómica. Como
dicha fórmula está construida a partir de proposiciones atómicas y conectivos, podemos
definir el valor de verdad de dicha fórmula por el principio de recursión estructural.
Proposición 1.4. Dada una valoración v : Σ → {0, 1}, podemos encontrar una única
extensión de la valoración, v : L → {0, 1}, de la siguiente manera:
• Base: v(p) = v(p) (la extensión coincide con la valoración) y v(>) = 1, v(⊥) = 0.
• Pasos recursivos: v(¬φ) = B¬(v(φ)) y v(φ ◦ ψ) = B◦(v(φ), v(ψ)).
Es decir, que a partir de una valoración, podemos extender esta a todo L de manera
que los valores de esta extensión sean coherentes con el significado de las conectivas, y
además esta extensión es única. Por tanto, el valor de verdad de una proposición com-
puesta sólo depende del valor de verdad de las proposiciones atómicas que la componen
y de su estructura (es decir, de sus conectivos).
4
2 Tablas de verdad
Siguiendo con la idea anterior, hay un método que nos permite encontrar expĺıcitamente
los posibles valores de verdad de una fórmula a partir de los valores de verdad de cada
una de las fórmulas atómicas que lo componen.
Para ilustrar el método consideremos la fórmula (p ∧ (p → r) ∨ (q ↔ t)). Daremos
los siguientes pasos:
• Paso 1: identificamos las fórmulas atómicas de la fórmula y los pasos que hemos
dado para construirla. En el ejemplo, las proposiciones atómicas son p, q, r y t, y
la estructura de la fórmula viene dada por su árbol estructural:
∨s
∧ s
s
p
�
�
�
�A
A
A
A →s
s
p
�
�
�
�A
A
A
As
r
,
,
,
,
,l
l
l
l
l ↔s
s
q
�
�
�
�A
A
A
As
t
• Paso 2: a partir del árbol estructural de la fórmula escribimos la primera fila de
la tabla de verdad con todas las fórmulas del árbol en orden de construcción,
empezando siempre por las fórmulas atómicas. En el ejemplo seŕıa:
p q r s p→ q p ∧ (p→ q) q ↔ t ((p ∧ (p→ q)) ∨ (q ↔ t))
• Paso 3: se rellenan las columnas correspondientes a las proposiciones atómicas
con todas sus posibles valoraciones. Recuerda que si hay n proposiciones atómicas
habrá 2n valoraciones distintas. En el ejemplo hay 4 proposiciones atómicas que
producirán 24 = 16 filas distintas, 17 si incluimos la cabecera.
• Paso 4: se rellenan el resto de las columnas a partir de los valores de verdad ya
calculados y de los conectivos que se usan para construir las fórmulas cada vez
5
más complejas. El ejemplo quedaŕıa:
p q r t p→ r p ∧ (p→ r) q ↔ t ((p ∧ (p→ r)) ∨ (q ↔ t))
0 0 0 0 1 0 1 1
0 0 0 1 1 0 0 0
0 0 1 0 1 0 1 1
0 0 1 1 1 0 0 0
0 1 0 0 1 0 0 0
0 1 0 1 1 0 1 1
0 1 1 0 1 0 0 0
0 1 1 1 1 0 1 1
1 0 0 0 0 0 1 1
1 0 0 1 0 0 0 0
1 0 1 0 1 1 1 1
1 0 1 1 1 1 0 1
1 1 0 0 0 0 0 0
1 1 0 1 0 0 1 1
1 1 1 0 1 1 0 1
1 1 1 1 1 1 1 1
Observación 2.1. Las tablas de verdad son un procedimiento claro y fácilmente progra-
mable para calcular todas las posibles valoraciones de una fórmula (en breve comprobare-
mos que esto es muy importante). Sin embargo, para fórmulas con muchas proposiciones
atómicas distintas el tamaño de la tabla crece muy deprisa. Por ejemplo, con 100 proposi-
ciones atómicas distintas tendŕıamos 2100 = 1267650600228229401496703205376 ĺıneas,
cantidad inmanejable para un ordenador. A lo largo del curso estudiaremos métodos
más eficientes para trabajar con fórmulas.
3 Tautoloǵıas, contingencias y contradicciones
Definición 3.1. Una fórmula φ es satisfacible bajo una valoración v cuando se verifica
que v(φ) = 1. En este caso se dice que v es un modelo de φ. Si φ es satisfacible bajo v
se escribe v |= φ.
Ejemplo 3.2. Si φ = (p ∨ q) ∧ r, la valoración v dada por v(p = 1), v(q) = 0, v(r) = 1
es un modelo de φ. Para encontrar todos los modelos de φ habŕıa que construir su tabla
de verdad.
Definición 3.3. Una valoración v es un contraejemplo de una fórmula φ cuando v(φ) =
0.
Ejemplo 3.4. Considerando la fórmula φ del ejemplo anterior, la valoración v tal que
v(p) = 1, v(q) = 1, v(r) = 0 es un contraejemplo de φ.
Definición 3.5. Una fórmula φ es satisfacible cuando es satisfacible bajo alguna valo-
ración v. En caso contrario se dice que φ es insatisfacible.
6
Ejemplo 3.6. La fórmula φ = p ∧ ¬p es insatisfacible, ya que cualquier valoración
dará valores distintos para p y ¬p, con lo que la conjunción siempre será falsa.
La fórmula Çψ = p → ¬p es falsa para la valoración v1(p) = 1, pero cierta para
v2(p) = 0, con lo que ψ es satisfacible (bajo v2).
Podemos extender estas definiciones a un conjunto de fórmulas:
Definición 3.7. Un conjunto de fórmulas Φ = {φ1, φ2, . . . , φn}
• es satisfacible si y sólo si φ1 ∧ φ2 ∧ · · · ∧ φn es satisfacible.
• es insatisfacible si y sólo si φ1 ∧ φ2 ∧ · · · ∧ φn es insatisfacible.
Observación 3.8. Esta definición indica que un conjunto de fórmulas es satisfacible
cuando todas ellas lo son simultáneamente, es decir, bajo la misma valoración.
Ejemplo 3.9. Si consideramos las fórmulas φ1 = p→ ¬q y φ2 = p ∧ r, la valoración v
dada por v(p) = 1, v(q) = 0, v(r) = 1 es un modelo de Φ = {φ1, φ2}, y por tanto dicho
conjunto es satisfacible.
Sin embargo, si consideramos ψ1 = p ∧ q ∧ r y ψ2 = p ∧ ¬q ∧ r, ambas fórmulas
tienen modelos (p.e: para ψ1 la valoración v1 dada por v1(p) = v1(q) = v1(r) = 1, y
para ψ2 la valoración v2 dada por v2(p) = v2(r) = 1, v2(q) = 0). Ahora bien, es fácil
comprobar que dichas valoraciones son los únicos modelos de sus respectivas fórmulas, y
por tanto ninguna valoración puede ser modelo de ambas simultáneamente. Por tanto,
Ψ = {ψ1, ψ2} no es satisfacible.
Definición 3.10. Fijemos una signatura Σ = {p1, p2, p3, . . .}, y sea φ una fórmula
proposicional construida a través de esa signatura.
• La fórmula φ es lógicamente válida o una tautoloǵıa cuando es verdadera para
cualquier valoración de Σ, es decir, cuando v |= φ para cualquier valoración v de
Σ.
• La fórmula φ es una contradicción cuando es falsa para cualquier valoración de
Σ, es decir, cuando cualquier valoración v de Σ es un contraejemplo de φ.
• La fórmula φ es una contingencia cuando entre las valoraciones de Σ hay al menos
un modelo y al menos un contraejemplo de φ.
4 Sustitución
Como ya iréis viendo, el concepto de tautoloǵıa es fundamental en la lógica. Reconocer
tautoloǵıas, y encontrar tautoloǵıas nuevas a partir de otras es muy importante. El
método de las tablas de verdad tiene varios inconvenientes (principalmente el tiempo
que requiere).
Sin embargo, se puede dar una situación como ésta. Sabemos que p ∨ ¬p es una
tautoloǵıa. Si ahora consideramos (q → (¬r ∧ t)) ∨ ¬(q → (¬r ∧ t)), la nueva fórmula
7
se ha obtenido cambiando p por (q → (¬r ∧ t)) (realizando una sustitución), con lo
cual conserva la estructura de la fórmula original,
que era una tautoloǵıa, y por tanto
también debeŕıa serlo. Comprobar la nueva fórmula por su tabla de verdad es algo
bastante engorroso. Todo esto motiva las siguientes definiciones.
Sea φ una fórmula, y p1, . . . , pn fórmulas atómicas que sean subfórmulas de φ. Con-
sideremos las fórmulas ψ1, ldots, φn y la fórmula φ′ obtenida al sustituir cada aparición
de pi por la fórmula ψi. Por ejemplo, si φ = p ∧ ¬q, podemos considerar la sustitución
de p por (r → s) y q por (p↔ t), obteniendo la fórmula φ′:
(r → s) ∧ ¬(p↔ t)
Es permisible que en las nuevas fórmulas aparezcan los śımbolos de proposición que se
sustituyen. Desarrollando esto formalmente:
Definición 4.1. Sean φ, ψ1, . . . , ψn fórmulas y p1, . . . , pn proposiciones atómicas. Nota-
mos por φ[p1/ψ1, . . . , pn/ψn] a la fórmula φ′ resultante de sustituir en φ cada aparición
de p1, . . . , pn por la fórmula ψ1, . . . , ψn respectivamente. Si una fórmula φ′ se puede
obtener a partir de φ mediante una sustitución de este tipo se dice que φ′ es un caso
particular de φ.
Observación 4.2. Cuando estén claras las fórmulas atómicas sustituidas, y las que las
sustituyen, escribiremos φ[p/ψ].
Lo interesante de las sustituciones es su relación con las valoraciones:
Definición 4.3. Si v es una valoración, p1, . . . , pn son proposiciones atómicas y x1, . . . , xn
son n valores booleanos (es decir, cada xi vale 0 o 1), escribimos v[p1/x1, . . . , pn/xn]
(o, si no hay confusión, abreviadamente v[p/x] a la valoración v′ que asigna el valor de
verdad xi a la proposición pi (para i = 1, . . . , n) y el mismo valor que v a las restantes
proposciones atómicas de la signatura.
¿Qué relación tiene esta nueva valoración con las sustituciones? Dicha relación viene
dada por el siguiente lema:
Lema 4.4 (Lema de sustitución). Para cualquier valoración v se verifica que
v(φ[p1/ψ1, . . . , pn/ψn]) = v[p1/v(ψ1), . . . , v(pn/ψn)](φ)
Observación 4.5. Este lema nos dice que si φ′ es un caso particular de la fórmula
φ, dado por la sustitución de p1 por ψ1,. . . y de pn por ψn, entonces sea cual sea la
valoración v, el valor de φ′ por la extensión de v es el mismo que el valor de la fórmula
original φ por una nueva valoración v′ construida cambiando el valor de verdad de p1
por el de v(ψ1),. . . y el de pn por el de v(ψn).
Este resultado técnico nos permite llegar rápidamente al resultado útil:
Teorema 4.6. Si φ es una tautoloǵıa, cualquier caso particular de φ también es una
tautoloǵıa.
8
Demostración. Sea φ una tautoloǵıa y φ′ = φ[p/ψ] un caso particular de φ. Tenemos que
comprobar que v(φ′) = 1 para cualquier valoración v. Aplicando el lema de sustitución,
resulta que v(φ′) = v′(φ), donde v′ = v[p1/v(ψ1), . . . , v(pn/ψn)], pero como φ es una
tautoloǵıa, todas sus valoraciones son verdaderas, es decir, v(φ′) = v′(φ) = 1, con lo que
φ′ es una tautoloǵıa. ,
5 Consecuencia lógica
Una de las nociones más importantes de la lógica es la de consecuencia. La noción in-
tuitiva suele implicar causalidad, es decir, de unas determinadas hipótesis (usualmente
pensadas como ciertas circunstancias) se sigue una cierta conclusión (una nueva cir-
cunstancia ”provocada”por las anteriores. En lógica, al haber perdido por completo los
significados (salvo en lo que a verdad o falsedad se refiere), no podemos apelar a la
causalidad.
Por tanto, para hablar de consecuencia lógica (o de razonamiento válido), puede ser
útil hacer una clasificación, según la verdad o falsedad de las premisas y de la conclusión,
y la validez o invalidez del razonamiento:
• Razonamiento no válido:
– Premisas falsas y conclusión falsa: la peor de las situaciones. De unas premi-
sas falsas, realizando un razonamiento incorrecto, se llega a una conclusión
falsa. Por ejemplo, si las premisas son �Si la tierra es redonda, entonces el
universo tiene 4000 años� y �El universo tiene 5000 años�, y la conclusión
es �La tierra es plana�, tenemos un razonamiento incorrecto (de la negación
del antecedente no se obtiene la negación del consecuente), con premisas y
conclusión falsas.
– Premisas verdaderas y conclusión falsa. Por ejemplo: si las hipótesis son �En
invierno hace fŕıo� y �Es 15 de diciembre� y la conclusión es �Hace calor�.
– Premisas falsas y conclusión verdadera. Por ejemplo, si las hipótesis son �Si
compro un boleto de loteŕıa seguro que me toca� y �No compro un boleto
de loteŕıa� y la conclusión es �La loteŕıa no me toca�.
– Premisas verdaderas y conclusión verdadera. Por ejemplo, si las premisas son
�Si madrugo llegaré a tiempo a la cita� y �No madrugo�, y la conclusión es
�No llego a tiempo a la cita�.
• Razonamiento válido:
– Premisas verdaderas y conclusión verdadera. Por ejemplo, si las premisas
son �Si una función es derivable, entonces es continua� y �f es una función
derivable� y la conclusión es �f es una función continua�. En general estos
son los razonamientos interesantes.
– Premisas falsas y conclusión falsa. Por ejemplo, si las premisas son �Si una
función es continua entonces es derivable� y �La función 1x es continua� y
9
la conclusión es �La función 1x es derivable�. La moraleja de este ejemplo es
que la validez de un razonamiento no es suficiente para asegurar la verdad de
la conclusión.
– Premisas falsas y conclusión verdadera. Por ejemplo, si las premisas son �To-
das las personas comen carne� y �Mi perro es una persona� y la conclusión
es �Mi perro come carne�.
– Premisas falsas y conclusión falsa. Aqúı no hay ningún ejemplo, debido pre-
cisamente a que esta es la definición de razonamiento correcto: aquel que no
permite obtener conclusiones falsas a partir de premisas verdaderas.
Lo interesante aqúı es que los razonamientos válidos no deben permitir de ninguna
manera juntar hipótesis verdaderas con conclusiones falsas. ¿Qué quiere decir de ninguna
manera? En los ĺımites que nos hemos impuesto en la lógica formal significa que sea cual
sea la valoración que haga verdaderas todas las hipótesis debe hacer también verdadera
la conclusión. Formalmente:
Definición 5.1. Una fórmula φ es consecuencia lógica de un conjunto finito de fórmulas
Φ = {φ1, . . . , φn} si toda valoración v que sea un modelo de Φ también es un modelo de
φ, es decir, si v |= Φ implica que v |= φ. Si φ es consecuencia lógica de Φ también se
dice que Φ implica lógicamente φ, y se escribe Φ |= φ.
Ejemplo 5.2. Un ejemplo t́ıpico de razonamiento válido (el que se ha utilizado en los
correspondientes tres ejemplos) es el siguiente:
{p→ q, p} |= q
Dicho razonamiento es tradicionalmente conocido como modus ponens
Afinando un poco más, un razonamiento válido es aquel en que el valor de verdad
de las premisas conlleva la verdad de la conclusión. Por tanto, si hay varias premisas,
éstas serán verdaderas simultáneamente si y sólo si lo es su conjunción. Ahora bien, si
siempre que dicha conjunción sea verdadera también lo es la consecuencia, esto significa
que la implicación de las premisas a las consecuencias siempre es verdadera (pues no
se puede dar el caso de que el antecedente (la conjunción de hipótesis) sea falso y la
conclusión verdadera). Por tanto, un razonamiento válido conlleva una tautoloǵıa (y ya
sabemos comprobar si una fórmula es una tautoloǵıa). Todo esto nos lleva a la siguiente
definición:
Definición 5.3. Dado un conjunto finito de fórmulas Φ = {φ1, φ2, . . . , φn} y una fórmu-
la φ, se define la deducción o razonamiento de hipótesis (o premisas) Φ y conclusión (o
tesis) φ a la fórmula
(φ1 ∧ φ2 ∧ · · · ∧ φn) → φ
A veces, para distinguir claramente las premisas de la conclusión, el razonamiento se
10
presenta de la siguiente manera:
φ1
...
φn
φ
Observación 5.4. Por lo dicho anteriormente, resulta que (φ1 ∧ φ2 ∧ · · · ∧ φn) → φ es
una tautoloǵıa si y sólo si Φ ∧ φ.
En particular, cualquier fórmula φ es consecuencia lógica de cualquier conjunto de
fórmulas que sea insatisfacible (es decir, lógicamente es posible
extraer cualquier con-
clusión a partir de premisas falsas).
Ejemplo 5.5. Algunos ejemplos de implicaciones lógicas clásicas son
¬¬p |= p Ley de la doble negación
(p ∧ q) |= p Leyes de simplificación
p |= (p ∨ q)
(p→ q) |= (¬q → ¬p) Ley de contraposición
((p→ q) ∧ (q → r)) |= (p→ r) Ley transitiva de →
((p ∧ q) → r) |= (p→ (q → r)) Ley de exportación
(p ∧ (p→ q)) |= q Modus ponens
((p→ q) ∧ ¬q) |= ¬p Modus tollens
Definición 5.6. Se dice que el razonamiento (φ1 ∧ φ2 ∧ · · · ∧ φn) → φ es correcto o
lógicamente válido si
(φ1 ∧ φ2 ∧ · · · ∧ φn) |= φ
Observación 5.7. Esta relación entre razonamientos correctos y tautoloǵıas nos pro-
porciona un método (poco eficiente en la práctica, pero un método al fin y al cabo) de
comprobar la corrección de un razonamiento. Por ejemplo, si queremos comprobar la co-
rrección del modus ponens tendŕıamos que hacer la tabla de verdad de (p∧(p→ q)) → q
(empezando con el árbol sintáctico y todo el procedimiento de las subfórmulas), obte-
niendo
p q p→ q p ∧ (p→ q) (p ∧ (p→ q)) → q
0 0 1 0 1
0 1 1 0 1
1 0 0 0 1
1 1 1 1 1
Y ya hemos comprobado que el razonamiento es una tautoloǵıa, y por tanto válido.
Un buen ejercicio seŕıa comprobar la validez de todos los razonamientos del ejemplo
anterior.
11
6 Equivalencia de fórmulas
Las últimas definiciones parecen dar mucha importancia al valor de verdad de las fórmu-
las, de manera que parece más importar como se comporta dicho valor de verdad que la
estructura sintáctica de las mismas. Dos fórmulas que mantengan siempre (bajo cual-
quier valoración) los mismos valores de verdad están fuertemente relacionadas.
Definición 6.1. Dos fórmulas φ y ψ son lógicamente equivalentes, o que una de ellas
equivale lógicamente a otra si la fórmula (φ ↔ ψ) es una tautoloǵıa. En este caso se
escribe φ ≡ ψ.
Ejemplo 6.2. Una de las más tradicionales (y, al menos al principio, menos intuitiva)
equivalencia lógica es la interdefinición:
(p→ q) ≡ (¬p ∨ q)
Podemos comprobar esta equivalencia comparando las columnas de las tablas de verdad
de las dos fórmulas, pero ya sabemos que ese procedimiento es bastante pesado. Como
las fórmulas son sencillas, podemos atacar directamente: (¬p∨ q) sólo es falsa cuando lo
son simultáneamente ¬p y q, es decir, cuando p es falsa y q es verdadera, exactamente
cuando es falsa la implicación (p→ q). Por tanto ambas fórmulas son equivalentes.
7 Introducción a los tableaux
Casi todos los comentarios hechos a lo largo del curso sobre las tablas de verdad son
negativos: demasiado engorrosas, problemas de computación cuando aumenta el número
de variables,. . . Esta semana vamos a estudiar un nuevo método, basado en la refutación,
que nos va a permitir identificar tautoloǵıas, contradicciones y contingencias, encontrar
modelos, verificar razonamientos válidos y otras muchas utilidades. Además, este método
puede adaptarse (con más complicaciones) a la lógica de primer orden.
La manera más inmediata de empezar es considerar un problema básico: la satisfa-
bilidad de un conjunto de fórmulas. La forma directa (tablas de verdad) ya sabemos que
es engorrosa. Otra posibilidad menos exhaustiva es buscar un modelo del conjunto de
fórmulas.
Por ejemplo, si consideramos Φ = {p→ ¬q,¬p ∨ q,¬q ∧ ¬p}, podemos proceder de
la siguiente manera:
1. El conjunto de fórmulas Φ es satisfacible cuando lo es la fórmula (p→ ¬q)∧ (¬p∨
q) ∧ (¬q ∧ ¬p). Tenemos una conjunción de tres fórmulas, con lo que podemos
representar estas en los nodos de una única rama de un árbol con ráız, que empieza
con cualquiera de las tres fórmulas:
12
p→ ¬qs
¬p ∨ qs
¬q ∧ ¬ps
2. Si nos fijamos en la última fórmula del árbol, esta es una conjunción, con lo que
para que sea cierta deben serlo tanto ¬q como p. Por tanto, añadimos estas dos
fórmulas en la misma rama del árbol (por comodidad, como ya hemos �usado� la
fórmula de la conjunción, la ponemos una señal, digamos
√
):
p→ ¬qs
¬p ∨ qs
¬q ∧ ¬p
√s
¬qs
¬ps
3. Si nos fijamos en la segunda de las fórmulas originales, ¬p ∨ q, resulta ser una
disyunción. Para que sea cierta basta con que sea cierta o bien ¬p o bien q. Esto
produce dos posibilidades, que indicamos dividiendo la rama donde aparece la
conjunción en dos distintas, una con cada fórmula correspondiente de la disyunción
(poniendo de nuevo una señal en la fórmula en la que hemos trabajado):
13
p→ ¬qs
¬p ∨ q
√s
¬q ∧ ¬p
√s
¬qs
¬ps
¬qs
J
J
J
JJ ps
4. Antes de proseguir con la última fórmula, si nos fijamos en la rama derecha, la
etiquetada con p, y recorremos desde alĺı el árbol de manera ascendente hasta
la ráız (que, por construcción del árbol ya sabemos que indica la conjunción de
todas las fórmulas del camino), nos encontramos también con la fórmula ¬p. Por
tanto en esa rama tenemos una conjunción p ∧ ¬p, que ya sabemos que es una
contradicción. Por tanto en esta rama no podemos pretender encontrar ningún
modelo, y la declararemos cerrada para no seguir trabajando con ella, indicándolo
con el śımbolo ⊗:
p→ ¬qs
¬p ∨ q
√s
¬q ∧ ¬p
√s
¬qs
¬ps
¬qs
J
J
J
JJ ps
⊗
14
5. Sólo nos queda el condicional. Este, sin embargo, no tiene una regla distinta en el
árbol a la conjunción o la disyunción. Ya sabemos, por todo lo estudiado de equiva-
lencias de fórmulas, que podemos transformar (por interdefinición) el condicional
en una disyunción. En este caso, y simplificando directamente, p→ ¬q ≡ ¬p∨¬q,
y procedemos abriendo dos ramas en la única hoja que queda abierta, una con
¬p y otra con ¬q, y observando que ninguna de estas dos ramas produce una
contradicción:
p→ ¬q ≡ ¬p ∨ ¬q
√s
¬p ∨ q
√s
¬q ∧ ¬p
√s
¬qs
¬ps
¬qs
¬ps
J
J
J
JJ ¬qs
J
J
J
JJ ps
⊗
6. Ya hemos terminado, no queda ninguna fórmula original por trocear. Sin embargo,
podemos afinar un poco mejor el árbol. Primero, las dos últimas hojas contienen
información redundante (ya sabemos que ¬p∧¬p ≡ ¬p). A partir de ahora tendre-
mos cuidado y no escribiremos ramas redundantes (sobre todo cuando las fórmulas
se compliquen). Por otra parte, ya no podemos seguir y no hemos encontrado nin-
guna otra contradicción, con lo que la (ahora) única rama que queda abierta nos
indica el modelo del conjunto de fórmulas originales, a saber, que tanto p como q
deben ser falsas:
15
p→ ¬q ≡ ¬p ∨ ¬q
√s
¬p ∨ q
√s
¬q ∧ ¬p
√s
¬qs
¬ps
¬qs
J
J
J
JJ ps
⊗
Pues bien, esto es un tableau (plural tableaux).
8 Clasificación de fórmulas
Antes de describir los tableaux tenemos que dar una pauta para escribir cualquier fórmu-
la en forma de conjunción o disyunción. Para ello consideraremos fórmulas del tipo φ◦ψ
o ¬(φ ◦ ψ), y las clasificaremos en dos tipos:
• α-fórmulas, o fórmulas conjuntivas. Son aquellas fórmulas α que se pueden escribir
de la forma α1∧α2. Serán las que alarguen ramas en los tableaux. Son las siguientes:
α α1 α2
φ ∧ ψ φ ψ
¬(φ ∨ ψ) ¬φ ¬ψ
¬(φ→ ψ) φ ¬ψ
φ↔ ψ φ→ ψ ψ → φ
• β-fórmulas o fórmulas disyuntivas. Son aquellas fórmulas β que se pueden escribir
de la forma β1 ∨ β2. Serán las que dividan en dos una rama de un tableaux. Son
las siguientes:
β β1 β2
φ ∨ ψ φ ψ
¬(φ ∧ ψ) ¬φ ¬ψ
φ→ ψ ¬φ ψ
¬(φ↔ ψ) ¬(φ→ ψ) ¬(ψ → φ)
16
Además, en beneficio de la operatividad, consideraremos otro tipo de fórmulas, las
fórmulas simplificables, que pueden sustituirse de manera inmediata por una fórmula
equivalente más sencilla:
• σ-fórmulas o fórmulas simplificables. Son aquellas fórmulas σ que pueden susti-
tuirse de manera inmediata por otra fórmula equivalente más sencilla σ1. En los
tableaux añaden un único descendiente a la rama correspondiente. Son las siguien-
tes:
σ σ1
¬> ⊥
¬⊥ >
¬¬φ φ
Resumiendo lo que cada fórmula producirá en un tableau, tenemos el siguiente esquema:
αs
α1s
α2s
βs
β1 s��
�
�A
A
A
A β2s
σs
σ1s
9 Reglas de formación de tableaux
Esencialmente, un tableau es un árbol binario con ráız etiquetado (es decir, a cada
nodo del árbol le corresponde una etiqueta, que en este caso será
una fórmula). Cada
vez que indiquemos que de una determinada fórmula φ se deduce otra ψ indicaremos
que si dicha fórmula φ está presente en una rama del árbol producirá a la otra como
descendiente directo del último nodo de dicha hoja. Si consideramos un conjunto de
fórmulas Φ = {φ1, . . . , φn}, tenemos las siguientes reglas de formación:
• Regla de inicio: el tableau de Φ empieza por una única rama con n nodos etique-
tados cada uno con una fórmula de Φ:
17
φ1s
φ2s
...
φns
• α-reglas:
1. De φ ∧ ψ se deducen φ y ψ en la misma rama.
2. De ¬(φ ∨ ψ) se deducen ¬φ y ¬ψ en la misma rama.
3. De ¬(φ→ ψ) se deducen φ y ¬ψ en la misma rama.
4. De φ↔ ψ se deducen φ→ ψ y ψ → φ en la misma rama.
• β-reglas:
1. De φ ∨ ψ se deduce φ y en otra rama nueva y distinta a la anterior ψ.
2. De ¬(φ ∧ ψ) se deduce ¬φ y en otra rama nueva y distinta a la anterior ¬ψ.
3. De φ→ ψ se deduce ¬φ y en otra rama nueva y distinta a la anterior ψ.
4. De ¬(φ ↔ ψ) se deduce ¬(φ → ψ) y en otra rama nueva y distinta a la
anterior ¬(ψ → φ).
• σ-reglas:
1. De ¬¬φ se deduce φ en la misma rama.
2. De ¬⊥ se deduce > en la misma rama.
3. De ¬> se deduce ⊥ en la misma rama.
• Regla de cierre: cualquier rama en la que aparezca simultáneamente φ y ¬φ, o ⊥
se cierra. Las ramas cerradas no se ampĺıan.
Estas reglas nos permiten crear y ampliar tableaux, pero no nos indican cuando
hemos terminado. Una opción inmediata es conseguir que todas las ramas estén cerradas,
pero no siempre ocurre. ¿Qué otras posibilidades quedan?
Definición 9.1. Una rama de un tableau está completa cuando:
(i) Si α está en la rama, también lo están α1 y α2.
(ii) Si β está en la rama, también lo está β1 o β2.
18
(iii) Si σ está en la rama, también está σ1
Un tableau está acabado cuando todas sus ramas están, o bien cerradas, o bien completas.
Un tableau está cerrado cuando todas sus ramas están cerradas.
Para entendernos, una rama está completa cuando todas las fórmulas que en ella
aparecen ya han sido descompuestas (utilizadas) en la propia rama. Un tableau acabado
es un tableau que no se puede ampliar más. Un tableau cerrado es aquel en el todas sus
ramas contienen al menos una contradicción directa.
El resultado importante sobre los tableaux (que no demostraremos) se basa en las
ramas abiertas y acabadas. El conjunto de todas las fórmulas que son etiquetas de una
rama abierta y acabada de un tableau se llama conjunto de Hintikka. Lo importante
sobre dichos conjuntos es el siguiente
Teorema 9.2. Todo conjunto de Hintikka es satisfacible.
Este resultado no es únicamente teórico. Como en un conjunto de Hintikka aparecen
las fórmulas de una rama acabada, sea cual sea la proposición atómica del conjunto
original de fórmulas Φ que originó el tableau, o ésta o su negación aparecerá en el
conjunto de Hintikka, lo que nos indica cual es la valoración que modela el conjunto Φ:
aquella que hace verdaderas las proposiciones atómicas que aparecen en el conjunto de
Hintikka y que hace falsas aquellas cuya negación aparece en el conjunto de Hintikka.
Este resultado no es suficiente para que los tableaux sean útiles, pues no nos dice
nada sobre la insatisfabilidad de fórmulas. Sea como sea, el resultado siguiente arregla
todo esto:
Teorema 9.3. Un conjunto de fórmulas Φ es insatisfacible si y sólo si produce un
tableau cerrado.
Y aqúı llega la parte práctica: como las reglas de formación de los tableaux �redu-
cen� las fórmulas, antes o después nos encontraremos con una rama abierta y completa,
o con todas las ramas cerradas, lo que nos dirá si el conjunto original de fórmulas es
satisfacible o no.
Observación 9.4. Para el que tenga interés en estudiar los tableaux de un modo teórico,
puede consultar los apuntes de la página de esta asignatura.
9.1 Consejos prácticos
Las reglas de formación de tableaux dejan mucha libertad (a la hora de elegir a qué fórmu-
la aplicamos dichas reglas). Como consecuencia de esto un mismo conjunto de fórmulas
pueden producir varios tableaux distintos. Por tanto, es importante (para terminar cuan-
to antes) elegir bien las reglas que aplicaremos. En general se pueden dar unos cuantos
consejos:
• Utilizar primero las α-reglas y las σ-reglas, pues no abren ramas nuevas.
• Empezar utilizando las fórmulas que cierren alguna rama.
19
• Parar si se resuelve el problema (por ejemplo, para verificar la satisfabilidad basta
encontrar una rama completa abierta, sin necesitar completar el tableau).
• Si no hay ninguna estrategia clara, quitarse primero las fórmulas más complicadas.
10 Aplicaciones
10.1 Determinar la satisfabilidad de un conjunto de fórmulas
Si Φ es un conjunto de fórmulas, construimos un tableau completo para Φ. Si dicho
tableau tiene alguna rama abierta, el conjunto Φ es satisfacible y además tenemos un
modelo, dado por la rama abierta. Si el tableau es cerrado, el conjunto Φ es insatisfacible.
Ejemplo 10.1. Consideremos Φ = {p→ q, q → r, p ∧ q,¬r}
Un posible tableau asociado seŕıa:
p→ qs
q → rs
p ∧ qs
¬rs
ps
qs
¬q s
⊗
�
�
�
�A
A
A
A rs
⊗
El tableau es cerrado y por tanto Φ es insatisfacible.
10.2 Clasificación de fórmulas
Dada una fórmula φ, podemos construir un tableau completo asociado. Si dicho tableau
es cerrado, la fórmula es una contradicción. En caso contrario todav́ıa no sabemos si la
fórmula es una contingencia o una tautoloǵıa. Para comprobarlo hacemos un tableau
completo de ¬φ. Si dicho tableau es cerrado entonces φ es una tautoloǵıa. Si es abierto,
20
entonces φ es una contingencia. En este último caso cualquier rama abierta del tableau
de φ es un modelo y cualquier rama abierta del tableau de φ es un contraejemplo.
Ejemplo 10.2. Vamos a clasificar la fórmula φ = (p ∨ ¬q) ∧ (¬p ∨ q). Empezamos con
un tableau de φ, por ejemplo:
(p ∨ ¬q) ∧ (¬p ∨ q)s
p ∨ ¬qs
¬p ∨ qs
p s
¬p s
⊗
�
�
�
�A
A
A
A qs
#
#
#
#
#c
c
c
c
c ¬qs
¬p s��
�
�A
A
A
A qs
⊗
Tenemos que φ no es una contradicción (tenemos dos modelos: que p y q sean verdaderas
al mismo tiempo o que sean falsas al mismo tiempo). Para continuar su estudio tenemos
que construir un tableau para ¬φ. Por ejemplo:
¬((p ∨ ¬q) ∧ (¬p ∨ q))s
¬(p ∨ ¬q) s
¬p s
¬¬q s
q s
�
�
�
�A
A
A
A ¬(¬p ∨ q)s
¬¬ps
¬qs
ps
Las ramas abiertas son los contraejemplos de φ, que son dos: cuando p y q tienen distintos
valores de verdad.
21
10.3 Razonamientos
La validez de un razonamiento
φ1
...
φn
φ
es equivalente a que la fórmula φ1 ∧ · · · ∧ φn ∧¬φ sea una contradicción, es decir, a que
el tableau de Φ = {φ1, . . . , φn,¬φ} sea cerrado.
Ejemplo 10.3. Consideremos el razonamiento:
p→ (q ↔ ¬r)
(q ∨ ¬r) → ¬p
(q ∧ r) ∨ p
p ∧ q ∧ ¬r
Para comprobar la validez del razonamiento construiremos el tableau del conjunto de
fórmulas formado por las hipótesis y la negación de la conclusión:
22
p→ (q ↔ ¬r)s
(q ∨ ¬r) → ¬ps
(q ∧ r) ∨ ps
¬(p ∧ q ∧ r)s
¬p s
¬(q ∨ ¬r) s
¬q s
r s
p s
⊗
�
�
�
�A
A
A
A q ∧ rs
qs
⊗
�
�
�
�A
A
A
A ¬ps
!!
!!
!!
!!
!!aaaaaaaaaa q ↔ ¬rs
q → ¬rs
¬r → qs
¬qs
¬¬r s
¬q ∨ ¬r s
¬q s
r s
p s��
�
�A
A
A
A q ∧ rs
qs
⊗
�
�
�
�A
A
A
A ¬ps
ps
⊗
�
�
�
�A
A
A
A qs
⊗
�
�
�
�
��ZZ
Z
Z
ZZ ¬rs
¬¬r s
⊗
�
�
�
�A
A
A
A qs
¬(q ∨ ¬r) s
¬q s
p s
⊗
�
�
�
�A
A
A
A ¬ps
ps
⊗
Como podemos comprobar hay una rama abierta, que nos da un contraejemplo al razo-
namiento: que p y r sean verdaderas y q falsa. Por tanto, el razonamiento no es válido.
23
10.4 Formas normales conjuntivas y disyuntivas
En la sección de equivalencias hemos visto que mediante las reglas de interdefinición el
condicional y el bicondicional pueden escribirse a partir de conjunciones, disyunciones
y negaciones. Ahora bien, una conjunción (disyunción) puede escribirse, aplicando las
leyes de De Morgan, como una disyunción (conjunción). Para afinar un poco esto:
Definición 10.4. (i) Un literal es cualquier fórmula de la forma p o ¬p, donde p es
una proposición atómica.
(ii) Una cláusula disyuntiva es cualquier disyunción de literales.
(iii) Una cláusula
conjuntiva es cualquier conjunción de literales.
(iv) Una fórmula está en forma normal disyuntiva () si es una disyunción de cláusulas
conjuntivas.
(v) Una fórmula está en forma normal conjuntiva () si es una conjunción de cláusulas
disyuntivas.
Observación 10.5. Por comodidad para las definiciones haremos las siguientes consi-
deraciones:
(i) Un literal se puede considerar como una conjunción o como una disyunción.
(ii) ⊥ se puede considerar como una disyunción, una cláusula disyuntiva o una vaćıa
(siempre es falsa).
(iii) > se puede considerar como una conjunción, una cláusula conjuntiva o una vaćıa
(siempre es verdadera).
El resultado interesante (que no demostraremos) es el siguiente:
Teorema 10.6. Dada una fórmula φ, a partir de sus proposiciones atómicas se pueden
construir una forma normal conjuntiva (φ) y una forma normal disyuntiva (φ) equiva-
lentes ambas a φ. Además (por las reglas de De Morgan), (φ) ≡ ¬(¬φ).
Veamos ahora como se utilizan los tableaux para encontrar las formas normales
conjuntiva y disyuntiva de una fórmula. Empecemos con la disyuntiva. Para ello, si φ
es una fórmula, construimos un tableau acabado T de dicha fórmula, y nos fijamos en
sus ramas abiertas (si fuese un tableau cerrado, la fórmula seŕıa una contradicción y su
seŕıa ⊥). Si tiene n ramas abiertas, notamos por φi la fórmula dada por la conjunción
de todos los literales de la rama número i (si alguno se repite sólo lo ponemos una vez).
Con esto
(φ) = φ1 ∨ . . . ∨ φn
Mejor con un ejemplo:
Ejemplo 10.7. Consideremos la fórmula φ = p→ (p∧ q). Un tableau completo de φ es
24
p→ (p ∧ q)s
¬p s��
�
�A
A
A
A p ∧ qs
qs
que tiene dos ramas abiertas que producen dos cláusulas conjuntivas: φ1 = ¬p y φ2 =
p ∧ q. Por tanto
(φ) = φ1 ∨ φ2 = ¬p ∨ (p ∨ q)
Nos falta la forma normal conjuntiva, pero por el teorema anterior, bastará negar la
forma normal disyuntiva de ¬φ. Un tableau completo de ¬φ seŕıa:
¬(p→ (p ∧ q))s
ps
¬(p ∧ q)s
¬p s
⊗
�
�
�
�A
A
A
A ¬qs
Sólo hay una rama abierta, con lo que solo tenemos una cláusula conjuntiva: φ′1 = p∧¬q,
y aśı (¬φ) = p ∧ ¬q. Por tanto:
(φ) = ¬(¬φ) = ¬(p ∧ ¬q) ≡ ¬p ∨ q
25
logica/tema4.pdf
Tema 4: Teoŕıa de la demostración
Ya hemos estudiado dos métodos para verificar la validez de fórmulas y deducciones:
uno directo (las tablas de verdad) y otro por refutación (los tableaux). Ahora vamos a
estudiar otro método distinto, que nos permitirá comprobar si una fórmula es válida y
si una fórmula es consecuencia lógica de unas determinadas premisas. Para ello constru-
iremos una desmostración, que será una construcción lógica realizada a partir de unos
axiomas (nos determinan las propiedades básicas de la teoŕıa en la que trabajamos) y
aplicando sobre estos unas determinadas reglas de derivación que nos permiten generar
nuevas fórmulas a partir de los axiomas o las premisas con las que estemos trabajan-
do. Este tipo de sistemas (sistemas formales axiomáticos) son directos y son los que
mejor simulan el razonamiento natural, son aplicables a lógicas no clásicas pero son de
dif́ıcil automatización. También hay otros métodos refutativos (como los tableaux) que
permiten las mismas comprobaciones.
Como bibliograf́ıa es especialmente recomendable el libro de DEAÑO para el sistema
de deducción natural de Gentzen. Aunque la notación es un poco distinta, la colección
de demostraciones es muy grande y todas ellas son muy claras. Para ampliar el tema se
puede utilizar el libro de FITTING.
1. Sistemas formales axiomáticos
Un sistema de demostración formal o sistema de pruebas S se define a partir de
cuatro conjuntos:
El alfabeto A del sistema: el conjunto de śımbolos que se utilizan.
Las reglas de sintaxix F : definen las fórmulas bien construidas.
Los axiomas X: un conjunto de fórmulas válidas de partida.
Las reglas de inferencia R: son reglas de transformación que permiten producir
fórmulas válidas nuevas a partir de axiomas o premisas.
Resumiendo, S = (A,F,X,R)
Una vez tenemos nuestro sistema de demostración S, podemos dar una definición
recursiva de teorema:
Definición 1.1. Un teorema es una fórmula válida que o bien es un axioma o bien se
obtiene como conclusión de aplicar un conjunto de reglas de inferencia a otros teoremas.
Si la fórmula ϕ es un teorema, se escribe ⊢ ϕ.
1
y también una definición de deducción:
Definición 1.2. Una deducción o razonamiento consiste en un conjunto de fórmulas
Φ = {ϕ1, . . . , ϕn} llamadas premisas y de una fórmula ϕ llamada conclusión de la de-
ducción.
La definición importante en un sistema formal es la de demostración:
Definición 1.3. Una demostración de un teorema ⊢ ϕ es una sucesión de fórmulas
{ϕ1, . . . , ϕn, ϕn+1 = ϕ} de manera que:
cada fórmula de la sucesión es:
• un axioma.
• un teorema ya demostrado.
• un teorema obtenido de las fórmulas anteriores aplicando reglas de inferencia.
la última fórmula de la sucesión es ϕ.
Si {ϕ1, . . . , ϕn, ϕn+1 = ϕ} es una demostración de un teorema, se dice que ϕ es válida o
demostrable y se escribe ⊢ ϕ.
Definición 1.4. Si Φ = {ϕ1, . . . , ϕn} es una sucesión de fórmulas y ϕ es una fórmula,
una demostración de una deducción de premisas Φ y conclusión ϕ es una sucesión finita
de fórmulas
{ϕ1, . . . , ϕn, ϕn+1, . . . , ϕn+m, ϕn+m+1 = ϕ}
donde:
cada fórmula de la sucesión es:
• una premisa (una fórmula de Φ).
• un axioma.
• un teorema ya demostrado.
• un teorema obtenido a partir de las fórmulas anteriores aplicando las reglas
de inferencia.
la última fórmula de la sucesión es ϕ.
Si {ϕ1, . . . , ϕn, ϕn+1, . . . , ϕn+m, ϕn+m+1 = ϕ} es una demostración de una deducción, se
dice que ϕ es consecuencia lógica de las premisas Φ, y se escribe Φ ⊢ ϕ.
Una demostración de un teorema es una demostración de una deducción en la que no
hay premisas (Φ = ∅). El siguiente resultado nos da otra relación entre demostraciones
de teoremas y deducciones:
Teorema 1.5. Sean {ϕ1, . . . , ϕn} una sucesión de fórmulas y ϕ una fórmula. Entonces
{ϕ1, . . . , ϕn} ⊢ ϕ si y sólo si {ϕ1, . . . , ϕn−1} ⊢ (ϕn → ϕ)
2
Si utilizamos varias veces este resultado vamos obteniendo:
{ϕ1, . . . , ϕn} ⊢ ϕ
{ϕ1, . . . , ϕn−1} ⊢ (ϕn → ϕ)
...
⊢ ϕ1 → (ϕ2 → (· · · → (ϕn → ϕ)) . . . )
Esto nos prueba el siguiente resultado:
Corolario 1.6. Dada una demostración de una deducción, siempre es posible encontrar
una fórmula válida que la represente.
2. Subdeducciones
Antes de pasar a un método de deducción concreto hay que hacer especial hincapié en
una situación muy usual en dichos métodos: la introducción de hipótesis provisionales.
Muchas veces necesitamos un determinado condicional (por ejemplo, si tenemos una
fórmula ϕ nos podŕıa ser muy útil tener también como teorema un condicional como
ψ → ϕ, sobre todo si la fórmula a la que intentamos llegar es ¬ψ). Para demostrar
un condicional, necesitamos considerar, de manera provisional, que su antecedente es
cierto, y aśı desarrollar una subdemostración en la cual lleguemos al consecuente busca-
do. Lo interesante es que en dicha subdemostración tenemos una premisa de más, que
nos podemos sacar de la manga si nos conviene (esta es la verdadera utilidad de las
subdemostraciones). Cuando terminamos la subdemostración descargamos la premisa
((fantasma)) y obtenemos como teorema un condicional. Hay muchas maneras de indicar
que se estan realizando demostraciones subordinadas, por ejemplo la del libro de FIT-
TING, pero utilizaré la del libro de DEAÑO (más sencilla manualmente) en la cual si
consideramos ϕ como la premisa auxiliar y realizamos un razonamiento que nos lleve a
ψ, marcamos dicho razonamiento con una ĺınea horizontal a la izquierda, y una vez ter-
minado (la ĺınea termina o se cierra) obtenemos como teorema, fuera de la demostración
auxiliar, el condicional ϕ→ ψ:
...
ϕ
...
ψ
ϕ→ ψ
...
En una demostración una fórmula está activa si aparece a la derecha de alguna
ĺınea que no se haya cerrado. Para
utilizar fórmulas en una demostración tenemos que
3
tener mucho cuidado para asegurarnos de que estén activas (es decir, que no podemos
utilizar las premisas auxiliares salvo en la demostración auxiliar. Cuando ésta se cierra
ya no está activa y por tanto ya no es utilizable. En la demostración general sólo puede
utilizarse el condicional obtenido a partir de la demostración auxiliar, que se escribe
fuera del recuadro).
Un ejemplo muy esquemático de razonamiento seŕıa:
1)ϕ1 (Premisa)
2)ϕ2 (Premisa)
3) ⊢ ϕ3 (R!(1):Regla de derivación 1 aplicada a la ĺınea 1)
4)ϕ4
5) ⊢ ϕ5
6) ⊢ ϕ6
(Premisa auxiliar)
R2(2,1)
R3(5)
7) ⊢ ϕ7 R4(4-6): regla 4 aplicada a la subdeducción
En la segunda columna aparecen aclaraciones que indican la naturaleza del paso que
hemos dado. En general describiran el tipo de proposición que estemos usando o, cuando
proceda, la deducción que hemos realizado. Cuando obtengamos una nueva proposición
aplicando una regla a aquellas que aparecen en determinadas ĺıneas, lo indicaremos como
Rx(a,b,c-d), donde Rx indica la regla que aplicamos, y que se ha aplicado a las ĺıneas a
, b y al intervalo de ĺıneas entre la c y la d.
3. El sistema de deducción natural de Gentzen
Trabajaremos con el sistema que mejor modela el razonamiento intuitivo. Consta de
8 reglas de derivación y no tiene ningún axioma. Hay dos reglas para cada conectivo
lógico del alfabeto que usamos, una de introducción y otra de eliminación. Para utilizar
este sistema es necesario hacer hipótesis, que pueden ser ciertas o no.
Definición 3.1. El sistema de deducción natural de Gentzen es el sistema de de-
mostración axiomático G = (A,F,X,R) donde:
A es el alfabeto compuesto por los śımbolos de proposiciones atómicas (p, q, r,
. . . ), los conectivos ¬, ∨, ∧ y →, y los paréntesis izquierdo y derecho.
F es el conjunto de las fórmulas bien construidas, el cual ya hemos definido re-
cursivamente, pero sólo con los conectivos indicados (se puede usar ϕ ↔ ψ como
abreviatura de (ϕ→ ψ) ∧ (ψ → ϕ)).
X es el conjunto de los axiomas, en este caso el conjunto vaćıo.
R es el conjunto de las reglas de inferencia que se describen a continuación.
4
3.1. Reglas de inferencia del sistema de Gentzen
Para la conjunción:
• Regla de introducción de la conjunción (RI∧): si ϕ y ψ son fórmulas activas,
se deduce ϕ ∧ ψ ({ϕ, ψ} ⊢ ϕ ∧ ψ).
• Regla de eliminación de la conjunción (RE∧): si ϕ∧ψ es una fórmula activa,
se pueden deducir ϕ y ψ (ϕ ∧ ψ ⊢ ϕ, ϕ ∧ ψ ⊢ ψ).
Para la disyunción:
• Regla de introducción de la disyunción (RI∨): la disyunción de dos fórmulas
se puede obtener de cada una de ellas: ϕ ⊢ (ϕ ∨ ψ) y ψ ⊢ (ϕ ∨ ψ).
• Regla de eliminación de la disyunción (RE⊢): en realidad es lo mismo que el
método de demostración por casos. Lo que nos dice es que si tenemos como
premisa una disyunción (ϕ ∨ ψ) y sabemos que a partir de cualquiera de las
fórmulas de la disyunción se deduce una tercera χ, entonces podemos concluir
χ con seguridad: {ϕ ∨ ψ, ϕ→ χ, ψ → χ} ⊢ χ.
Para la negación:
• Regla de introducción de la negación (RI¬): si de una misma fórmula se
pueden deducir otra y su negación, podemos concluir la negación de la fórmula
original (esta regla se suele utilizar en las demostraciones por reducción al
absurdo, donde se busca un condicional de la forma ϕ→ (ψ∧¬ψ) para poder
concluir ¬ϕ): {ϕ→ ψ, ϕ→ ¬ψ} ⊢ ¬ϕ.
• Regla de eliminación de la negación (RE¬): de la doble negación de una
fórmula se concluye la fórmula: ¬¬ϕ ⊢ ϕ.
Para la implicación:
• Regla de introducción de la implicación (RI→): si en una subdeducción
tomamos ϕ como hipótesis auxiliar y deducimos ψ, podemos concluir, fuera
de la subdeducción, ϕ → ψ. En realidad es una versión del teorema de la
deducción, y justifica todo lo hablado sobre subdeducciones.
• Regla de eliminación de la implicación o Modus Ponens (RE→): si tenemos
como hipótesis una implicación y el antecedente de la implicación, podemos
concluir el consecuente: {ϕ, ϕ→ ψ} ⊢ ψ
Vamos a ver algunos ejemplos:
p ∧ (q ∧ r) ⊢ p ∧ r:
1)p ∧ (q ∧ r) P
2)⊢ p RE∧,1
3)⊢ q ∧ r RE∧,1
4)⊢ r RE∧,3
5)⊢ p ∧ r RI∧,2,4
5
p ∧ (q ∨ r) ⊢ (p ∧ q) ∨ (p ∧ r):
1)p ∧ (q ∨ r) P
2)⊢ p RE∧,1
3)⊢ q ∨ r RE∧,1
4)q
5)⊢ p ∧ q
6)⊢ (p ∧ q) ∨ (p ∧ r)
PA
RI∧, 2, 4
RI∨,5
7)q → (p ∧ q) ∨ (p ∧ r) RI→,4-6
8)r
9)p ∧ r
10)(p ∧ q) ∨ (p ∧ r)
PA
RI∧,2,4
RI∨,5
11)r → (p ∧ q) ∨ (p ∧ r) RI→,8-10
12)(p ∧ q) ∨ (p ∧ r) RE∨,3,7,11
{ϕ→ ψ,¬ψ} ⊢ ¬ϕ:
1)ϕ→ ψ P
2)¬ψ P
3)¬¬ϕ
4)⊢ ϕ
5)⊢ ψ
6)⊢ ψ ∧ ¬ψ
PA
RE¬,3
RE→,4,1
RI∧,2,5
7)⊢ ¬¬ϕ→ (ψ ∧ ¬ψ) RI→,3-6
8)⊢ ¬¬¬ϕ RI¬,7
9)⊢ ¬ϕ RE¬,8
Una alternativa a esta demostración seŕıa:
{ϕ→ ψ,¬ψ} ⊢ ¬ϕ:
1)ϕ→ ψ P
2)¬ψ P
3)ϕ
4)⊢ ψ
5)⊢ ψ ∧ ¬ψ
PA
RE→,3,1
RI∧,2,4
6)⊢ ϕ→ (ψ ∧ ¬ψ) RI→,3-5
7)⊢ ¬ϕ RI¬,6
4. Reglas derivadas
En la definición de deducción hemos dejado claro que se pueden utilizar teoremas ya
probados. Tener un buen repertorio de teoremas es muy útil para atacar a demostraciones
complejas, proporcionándonos distintas estrategias y atajos. Vamos a ver una lista en
la que no se incluyen todas las demostraciones (se pueden consultar los libros de la
bibliograf́ıa, especialmente el DEAÑO).
6
1. Teorema de identidad:
ϕ ⊢ ϕ
En efecto,
1)ϕ P
2)¬ϕ
3)ϕ ∧ ¬ϕ
PA
RI∧,1,2
4)¬ϕ→ (ϕ ∧ ¬ϕ) RI→,2-3
5)¬¬ϕ RI¬,4
6)ϕ RE¬,5
2. Regla del silogismo:
{ϕ→ ψ,ψ → χ} ⊢ ϕ→ ψ
3. Modus ponens (MP):
{ϕ→ ψ,¬ψ} ⊢ ¬ϕ
4. Extracontradictione Quodlibet:
{ϕ,¬ϕ} ⊢ ψ
5. Producto condicional:
{ϕ→ ψ, ϕ→ χ} ⊢ ϕ→ ψ ∧ χ
6. Contraposición:
ϕ→ ψ ⊢ ¬ψ → ¬ϕ
ϕ→ ¬ψ ⊢ ψ → ¬ϕ
¬ϕ→ ψ ⊢ ¬ψ → ϕ
7. Interdefinición (1):
ϕ→ ψ ⊢ ¬(ϕ ∧ ¬ψ)
¬(ϕ ∧ ¬ψ) ⊢ ϕ→ ψ
8. Leyes de De Morgan:
¬(ϕ ∨ ψ) ⊢ ¬ϕ ∧ ¬ϕ
¬ϕ ∧ ¬ϕ ⊢ ¬(ϕ ∨ ψ)
¬(ϕ ∧ ψ) ⊢ ¬ϕ ∨ ¬ψ
¬ϕ ∨ ¬ψ ⊢ ¬(ϕ ∧ ψ)
7
9. Interdefinición (2):
ϕ→ ψ ⊢ ¬ϕ ∨ ψ
¬ϕ ∨ ψ ⊢ ϕ→ ψ
10. Propiedad conmutativa de la conjunción:
ϕ ∧ ψ ⊢ ψ ∧ ϕ (1)
11. Propiedad asociativa de la conjunción:
ϕ ∧ (ψ ∧ χ) ⊢ (ϕ ∧ ψ) ∧ χ
(ϕ ∧ ψ) ∧ χ ⊢ ϕ ∧ (ψ ∧ χ)
12. Propiedad distributiva de la conjunción:
ϕ ∧ (ψ ∨ χ) ⊢ (ϕ ∧ ψ) ∨ (ϕ ∧ χ)
(ϕ ∧ ψ) ∨ (ϕ ∧ χ) ⊢ ϕ ∧ (ψ ∨ χ)
13. Propiedad de absorción de la conjunción:
ϕ ∧ (ϕ ∨ ψ) ⊢ ϕ
(ϕ ∨ ψ) ⊢ ϕ ⊢ ϕ
14. Idempotencia de la conjunción:
ϕ ∧ ϕ ⊢ ϕ
ϕ ⊢ ϕ ∧ ϕ
15. Propiedad conmutativa de la disyunción:
ϕ ∨ ψ ⊢ ψ ∨ ϕ
16. Propiedad asociativa de la disyunción:
ϕ ∨ (ψ ∨ χ) ⊢ (ϕ ∨ ψ) ∨ χ
(ϕ ∨ ψ) ∨ χ ⊢ ϕ ∨ (ψ ∨ χ)
17. Propiedad distributiva de la disyunción:
ϕ ∨ (ψ ∧ χ) ⊢ (ϕ ∨ ψ) ∧ (ϕ ∨ χ)
(ϕ ∨ ψ) ∧ (ϕ ∨ χ) ⊢ ϕ ∨ (ψ ∧ χ)
8
18. Propiedad de absorción de la disyunción:
ϕ ⊢ ϕ ∨ (ϕ ∧ ψ)
ϕ ∨ (ϕ ∧ ψ) ⊢ ϕ
19. Idempotencia de la disyunción:
ϕ ⊢ ϕ ∨ ϕ (2)
ϕ ∨ ϕ ⊢ ϕ (3)
20. Regla de introducción de la coimplicación:
{ϕ→ ψ,ψ → ϕ} ⊢ ϕ↔ ψ
21. Regla de eliminación de la coimplicación:
ϕ↔ ψ ⊢ ϕ→ ψ
ϕ↔ ψ ⊢ ψ → ϕ
22. Propiedad reflexiva de la coimplicación:
⊢ ϕ↔ ϕ
23. Propiedad transitiva de la coimplicación:
{ϕ↔ ψ,ψ ↔ χ} ⊢ ϕ↔ χ
24. Propiedad simétrica de la coimplicación:
ϕ↔ ψ ⊢ ψ ↔ ϕ
25. Importación-exportación:
{ϕ→ (ψ → χ), ϕ ∧ ψ} ⊢ χ
{ϕ ∧ ψ → χ, ϕ} ⊢ ψ → χ
Veamos la demostración de la primera de estas dos reglas:
1)ϕ→ (ψ → χ) P
2)ϕ ∧ ψ P
3)⊢ ϕ RE∧,2
4)⊢ ψ → χ RE→,3,1
5)⊢ ψ RE∧,2
6)⊢ χ RE→,5,4
9
26. Mutación de premisa:
ϕ→ (ψ → χ) ⊢ ψ → (ϕ→ χ)
En efecto:
1)ϕ→ (ψ → χ) P
2)ψ
3)ϕ
4)ψ → χ
5)χ
6)ϕ→ χ
PA
PA
RE→,3,1
RE→,2,4
RI→,3-5
7)ψ → (ϕ→ χ) RI→,2-6
27. Carga de premisa
ϕ ⊢ (ψ → ϕ)
En efecto:
1)ϕ P
2)ψ
3)⊢ ϕ
PA
Teorema de Identidad,1
4)⊢ ψ → ϕ RI→,2-3
28. Modus tollens (MT):
{ϕ→ ψ,¬ψ} ⊢ ¬ϕ
29. Tollendo ponens:
{ϕ ∨ ψ,¬ψ} ⊢ ϕ
En efecto:
1)ϕ ∨ ψ P
2)¬ψ P
3)ϕ
4)⊢ ϕ
PA
Teorema de identidad,3
5)ϕ→ ϕ RI→,3-4
6)ψ
7)⊢ ψ ∨ ¬ψ
8)⊢ ϕ
PA
RI∧,2,6
Excontraditione Quodlibet, 6
9)ψ → ϕ RI→,6-8
10)⊢ ϕ RE∨, 1,5,9
30. Dilemas:
{ϕ ∨ ψ, ϕ→ χ, ψ → χ} ⊢ χ
{ϕ ∨ ψ, ϕ→ χ, ψ → ρ} ⊢ χ ∨ ρ
{¬ϕ ∨ ¬ψ, χ→ ϕ, χ→ ψ} ⊢ ¬χ
{¬ϕ ∨ ¬ψ, χ→ ϕ, ρ→ ψ} ⊢ ¬χ ∨ ¬ρ
10
5. Tableaux sintácticos
En las definiciones de los tableaux del tema anterior en ningún momento se hizo
mención a los valores de verdad de las fórmulas que los componen, es decir, los tableaux
son un procedimiento sintáctico (solo
dependen de las fórmulas) que permite, mediante
el método de refutación, comprobar la validez de un razonamiento o una fórmula, y por
tanto permiten demostrar teoremas y deducciones.
6. ¿Qué podemos esperar?
Al trabajar con un sistema axiomático nos interesa saber que relación tiene este
sistema con la interpretación semántica de las fórmulas con las que trabaja. Las tres
propiedades que describen esta relación son las siguientes:
Completitud: un sistema de demostración axiomático es completo si es capaz de de-
mostrar cualquier fórmula semánticamente válida (tautoloǵıa) y deducir cualquier
consecuencia lógica.
Corrección: un sistema de demostración es correcto si todas las fórmulas demostra-
bles en el sistema son tautoloǵıas y todas las fórmulas deducibles a partir de un
conjunto de premisas son consecuencia lógica de dichas premisas.
Decidibilidad: un sistema de demostración es decidible si proporciona un proced-
imiento general y finito para decidir si una fórmula es válida o deducible a partir
de un conjunto de fórmulas.
Aśı, el método de los tableaux semánticos es completo, correcto y decidible. También
lo es el sistema de deducción natura de Gentzen.
11
logica/tema5.pdf
Tema 5: Sintaxis de la lógica de primer orden
1. Contenidos
El alumno conocerá las reglas de formación de fórmulas en LPO.
El alumno conocerá y utilizará en casos sencillos la inducción y la recursión es-
tructural.
El alumno formalizará correctamente enunciados naturales, tanto en notación for-
mal como abreviada.
2. Aproximación intuitiva a la lógica de primer orden:
predicados y objetos
2.1. Introducción: predicados y objetos
Hay deducciones que se realizan habitualmente para las que no es posible analizar
su validez dentro del ámbito de la lógica de proposiciones. Por ejemplo, si consideramos
la deducción:
Todos los hombres son mortales
Sócrates es un hombre
Sócrates es mortal
e intentamos formalizarla (esto es, expresar su forma) en lógica de proposiciones,
obtendŕıamos:
p
q
r
por lo que no es un razonamiento válido (tomando p : V , q : V y r : F ) en contradic-
ción con nuestra intuición. Necesitamos entonces una descripción más fina que permita
distinguir los hombres (los objetos) de sus propiedades (predicados).
Consideremos ahora la deducción:
1
Todos los números primos son impares
3 es un número primo
3 es impar
Si separamos las sentencias:
3 es primo
5 es primo
5 es impar
observamos que, aun siendo distintas, aparecen en ellas partes comunes:
en las dos primeras interviene la propiedad ser primo
en las dos últimas interviene el objeto 5.
Estas sentencias pueden ser simbolizadas del siguiente modo:
x es primo P(x)
x es impar I(x)
3 es primo P(3)
5 es impar I(5)
5 es primo P(5)
O en el ejemplo del comienzo:
x es mortal M(x)
x es hombre H(x)
También es posible simbolizar de este modo propiedades que afectan a varios objetos:
x es el padre de y P(x,y)
x estudia la carrera y E(x,y)
x,y,z están alineados L(x,y,z)
x es igual a y x=y
x es mayor que y x > y
En lógica de predicados se distingue, pues, entre las propiedades (también llamadas
predicados) y los objetos a los que dichas propiedades se refieren.
En lógica, y en general, en matemáticas, se utilizan dos tipos de objetos:
las constantes, que son objetos concretos y que, como tales, forman parte de un
universo de discurso, y
las variables, que son objetos genéricos que normalmente denotamos con las letras
x, y, z.... y que podrán sustituirse por objetos.
2
Por ejemplo, dentro del conjunto de los números naturales N, el 1 es una constante y
representa un elemento de N, mientras que podemos escribir x, una variable que puede
tomar cualquier valor natural.
La caracteŕıstica esencial que diferencia las variables de las constantes es que las
variables pueden ser sustituidas por cualquier objeto del universo de discurso al que
estén referidas en el transcurso de una deducción.
Un predicado es entonces una sentencia que involucra variables de modo que al ser
sustituidas por constantes se convierte en una proposición.
Por ejemplo, el predicado x es primo se convierte en una proposición al sustituir x
por un número natural.
Los predicados se pueden representar por śımbolos del tipo P (x), Q(x), R(x)... que
se denominan funciones proposicionales o también sentencias abiertas. Una vez
que se haya asignado un valor adecuado a la variable x la función proposicional P (x) da
lugar a una proposición de la que es posible afirmar si es verdadera o falsa. Por ejemplo,
si P (x) :=x es primo entonces P (3) es verdadera, y P (4) es falsa.
Por otra las funciones proposicionales pueden tener más de una variable. Aśı por
ejemplo, si Q(x, y, z) designa la sentencia x + y = z, tendremos que las sentencias
Q(1, 2, 3) y Q(2, 2, 4) son verdaderas y que Q(1, 2, 5) es falsa.
2.2. Nociones sobre los cuantificadores universal y existencial
Como hemos visto, una función proposicional (o sentencia abierta) puede dar lugar
a una proposición (o, lo que es lo mismo, se puede cerrar) asignando valores concretos
del universo de discurso a las variables que en ella intervienen. Introducimos ahora
otra manera de cerrar las sentencias abiertas, usando los cuantificadores universal y
existencial.
1) Consideremos la expresión: Para todo objeto x se verifica P (x). La frase para todo
objeto x se denomina cuantificador universal y se representa por ∀x.
Si la función proposicional P (x) resulta ser una proposición verdadera independi-
entemente del objeto por el que sustituyamos a variable x, diremos que la siguiente
sentencia es verdadera:
∀x P (x).
2) Por otra parte, el hecho de que para al menos un elemento a la sentencia P (a) sea
una proposición verdadera, nos permite afirmar que la proposición existe un elemento x
tal que la proposición P (x) es verdadera, que expresamos de forma más breve por
∃x P (x)
es verdadera.
La frase existe un objeto x se denomina cuantificador existencial y se representa
por ∃x.
3
Aśı pues, para poder asociar un valor de verdad (o, lo que es lo mismo, interpretar)
a una sentencia abierta, es necesario cerrarla previamente (se dice que una sentencia
es cerrada si no tiene variables sin cuantificar). Como hemos visto una sentencia se
puede cerrar asignando constantes a las variables que en ella intervienen o cuantificando
dichas variables. Si las variables están cuantificadas, podemos hacer que el valor de
verdad dependa del universo de discurso al que nos queramos referir. Aśı por ejemplo,
la sentencia
∃x (x2 = 2)
es verdadera pues basta considerar x =
√
2. Sin embargo esta sentencia seŕıa falsa en el
universo de discurso de los números enteros (U = Z ya que
√
2 /∈ Z). Para referirnos a
esa sentencia en ese dominio, tendŕıamos que escribir
∀x(x ∈ Z) ∧ P (x))
sentencia de la que diŕıamos que es falsa. En general, se suele escribir, como notación
∀x ∈ U P (x)
en lugar de
∀x(x ∈ U ∧ P (x))
y, análogamente, se suele escribir:
∃x ∈ U P (x)
en lugar de
∃x(x ∈ U ∧ P (x)).
Es importante tener presente que si el universo de discurso es finito, el cuantificador
universal puede sustituirse por un número finito de conjunciones y el cuantificador ex-
istencial por un número finito de disyunciones.
Por ejemplo, si los valores posibles de la variable x son a, b, c, (U = {a, b, c}) la
sentencia cerrada
∀x ∈ U P (x)
es, por definición,
P (a) ∧ P (b) ∧ P (c)
y la sentencia
∃x ∈ U P (x)
es, por definición,
P (a) ∨ P (b) ∨ P (c).
Estas definiciones muestran que los cuantificadores existencial y universal son una forma
abreviada de escribir los conectivos ∨ y ∧.
Teniendo esto presente, y recordando las leyes de De Morgan de la lógica proposi-
cional, es muy importante que tengais presente la relación que existe entre los dos
4
cuantificadores: La negación de la frase Todo objeto x satisface la propiedad P es Ex-
iste al menos un objeto que no satisface la propiedad P. Por ello Todo objeto x verifica
la propiedad
P tiene el mismo significado que No existen objetos que no satisfagan la
propiedad P. Es decir,
∀x P (x)
y
¬(∃x ¬P (x))
significan lo mismo y, por lo mismo, las sentencias
∃x P (x)
y
¬(∀x ¬P (x))
también significan lo mismo.
3. Formalización: Sintaxis de la lógica de primer orden
Hasta ahora la lógica estudiada (la lógica proposicional) nos proporciona una forma
muy basta de formalizar razonamientos. Siguiendo otra vez el ejemplo clásico, si de
nuevo consideramos el razonamiento ((Todos los hombres son mortales. Sócrates es un
hombre. Por tanto, Sócrates es mortal)), formalizado en LP tendŕıamos algo aśı:
p: Todos los hombres son mortales.
q: Sócrates es un hombre.
r: Sócrates es mortal.
Y nuestro razonamiento quedaŕıa {p, q} |= r, que claramente no es válido. Sin embar-
go, parece claro que el razonamiento debeŕıa serlo. El problema es la capacidad expresiva
de la lógica proposicional, que no permite que haya relación entre proposiciones, ni per-
mite sujetos ni predicados ni relaciones ni nada parecido. Para poder usar este tipo
de razonamientos, más usuales en el lenguaje natural y en las aplicaciones, debemos
ampliar nuestro sistema lógico.
Antes de empezar con el formalismo veamos que debemos pedir al nuevo sistema.
Por una parte esta claro que debemos trabajar con determinados individuos, siem-
pre considerados dentro de un sistema claramente delimitado (p.e: Sócrates, dentro de
los filósofos griegos, los seres humanos o los entes que alguna vez ha habido en el sis-
tema solar). Además, debemos hacer distinción muy clara entre considerar un individuo
concreto (constantes) o una designación genérica de un individuo cualquiera (variable).
Además, a veces designamos a un individuo de manera clara (mediante un nombre
propio), pero otras se le designará a partir de otros individuos (p.e: el hijo de Fulanito,
el número siguiente a 7, etc.). Esto debe permitir formar nombres compuestos a partir
de funciones.
También podemos encontrarnos con enunciados del tipo ((Si x > 1, entonces
√
x < x)).
En este caso una parte muy importante del enunciado es una relación entre dos términos
(en el primer caso aparece x, una variable, y 1, una constante, y en el segundo caso una
5
variable y una función sobre la variable, la ráız cuadrada de x), en el antecedente la
relación ((mayor)) (binaria) y en el consecuente la relación ((menor)) (también binaria).
Un caso particular es el signo de igualdad, al que se le da un tratamiento especial.
También necesitaremos un tratamiento de las variables de manera que podamos decir
algo de ellas en general. Esto se consigue con los cuantificadores, que nos permiten dar un
enunciado para todas las variables (cuantificador universal, p.e: todos los hombres son
mortales) o indicar que un resultado es cierto para al menos una constante (cuantificador
existencial, p.e: algunos hombres son morenos).
4. Términos y fórmulas
Para dar una definición precisa de las fórmulas de la lógica de primer orden necesi-
tamos un conjunto bien definido de śımbolos primitivos y unas reglas de formación que
nos permitan combinar dichos śımbolos.
Los śımbolos primitivos de la lógica de primer orden son los siguientes:
Un conjunto Σ de śımbolos de función (a estos los designaremos por FΣ), para
los que reservaremos las letras f, g, h, y de relación (RΣ), para los que reservare-
mos las letras P,Q,R. Además supondremos una función ar : FΣ ∪ RΣ → N
que asigna a cada función o relación su aridad, ar(f) y ar(P ). Se notará FnΣ =
{f ∈ FΣ : ar(f) = n} y RnΣ = {P ∈ RΣ : ar(R) = n}.
A F 0Σ (los śımbolos de función de aridad cero) los consideraremos constantes, y
reservaremos para designarlas las letras c, d, e. A R0Σ (los śımbolos de relación
de aridad cero) los consideraremos śımbolos de proposición, y reservaremos para
designarlas las letras p, q, r.
Los śımbolos lógicos, que son:
• las conectivas proposicionales: ⊤,⊥,¬,∨,∧,→,↔.
• los cuantificadores: ∀,∃.
• el signo de igualdad, =.
Un conjunto infinito numerable de variables, V = {v1, v2, v3, . . .}. Para facilitar la
notación reservaremos las letras x, y, z, u, v, w para representar cualesquiera vari-
ables.
Śımbolos auxiliares: (, ), ,.
Al alfabeto de todos los śımbolos primitivos antes considerados le designaremos por
AΣ.
Ejemplo 4.1. Vamos a considerar un ejemplo muy t́ıpico. Antes de describirlo veremos
cual seŕıa una de sus posibles interpretaciones (que es la que realmente lo motiva). Si
queremos describir la aritmética en los naturales, realmente necesitamos muy poca cosa:
la suma, el producto y una forma razonable (en pocos śımbolos) de escribir todos los
6
números. Para ello consideraremos el cero y la operación sucesor, que a cada número
le asigna el siguiente. En este caso tenemos una constante (el cero), una función 1-aria
(sucesor), dos funciones 2-arias (suma y producto), y por último nos interesa considerar
la importante relación de orden, es decir, una relación binaria.
Formalizando (es decir, olvidándonos de todo el significado anteriormente comenta-
do), consideramos la signatura Σar, que en este caso seŕıa
Σar = {c; f ; g, h;R}
Donde:
c ∈ F 0Σar (es una constante, el cero bajo la interpretación antes mencionada).
f ∈ F 1Σar (una función de una variable, el sucesor).
g, h ∈ F 2Σar (dos funciones de dos variables, la suma y el producto).
R ∈ R2Σar (una relación binaria, la de orden)
Ya tenemos los bloques de construcción, y sólo nos faltan las reglas que nos permitan
construir expresiones correctas. A diferencia de la lógica proposicional, hay que distinguir
entre dos tipos de expresiones, los términos (maneras de designar a los individuos del
universo de discurso) y las fórmulas (que nos designan información acerca de dichos
individuos, que puede ser verdadera o falsa).
4.1. Reglas de formación
Las reglas de formación nos permiten formar y distinguir las expresiones bien con-
struidas el LPO con un determinado alfabeto. Hay dos:
Reglas de formación de términos: se llaman términos de signatura Σ o Σ-
términos a las expresiones, y sólo a aquellas, que se pueden construir mediante la
aplicación de las siguientes reglas de formación un número finito de veces:
1. Las variables y las constantes son términos (los designaremos como términos
atómicos).
2. Si f ∈ FnΣ y t1, . . . , tn son términos, entonces la expresión f(t1, . . . , tn) tam-
bién es un término (términos compuestos).
Al conjunto de Σ-términos lo designaremos por TΣ.
Ejemplo 4.2. En Σar, ejemplos de términos seŕıan c, x, f(c), f(f(c)), g(c, f(c)),
h(c, x), etc. (¿Cuáles son términos atómicos? ¿Cómo se han formado los com-
puestos? ¿Cuál seŕıa su interpretación con los números naturales?).
Reglas de formación de fórmulas: se llaman fórmulas de signatura Σ o Σ-
fórmulas a las expresiones, y sólo aquellas, que se pueden construir mediante la
aplicación de las siguientes reglas de formación un número finito de veces:
7
1. ⊤, ⊥, cada p ∈ P 0Σ son fórmulas. D ados s, t ∈ TΣ, la expresión s = t es
una fórmula. Si P ∈ PnΣ y t1 . . . , tn ∈ TΣ, la expresión P (t1, . . . , tn) es una
fórmula. A estas fórmulas se les llama fórmulas atómicas.
2. Si ϕ es una fórmula, también lo es (¬ϕ) (la negación de ϕ).
3. Si ◦ es una conectiva binaria y ϕ1, ϕ2 son fórmulas, también lo es (ϕ1 ◦ ϕ2).
4. Si ϕ es una fórmula, también lo son ∃xϕ (cuantificación existencial de ϕ)
y ∀xϕ (cuantificador universal de ϕ). En general se utilizará una K para
representar a cualquiera de los dos cuantificadores.
Al conjunto de todas las Σ-fórmulas lo designamos por LΣ
Ejemplo 4.3. De nuevo en Σar, seŕıan Σ-fórmulas:
1. R(f(x), y) (la interpretación seŕıa, en notación matemática estándar, x+1 <
y, donde las letras indican naturales).
2. (¬(h(z, z) = f(y))) (es falso que z2 = y + 1).
3. ∀z(¬(h(z, z) = f(y))) (para cualquier valor de z es falso que z2 = y + 1 ).
4. ∃z(¬(h(z, z) = f(y))) (hay algún z para el cual es falso
que z2 = y + 1 ).
5. Inducción y recursión estructural
La propia definición inductiva de términos y fórmulas nos permite enunciar principios
de inducción y recursión estructural en LPO.
El principio de inducción estructural para términos dice que si P es una
propiedad aplicable a las palabras del alfabeto dado por la signatura Σ y se verifica que:
1. todo término atómico tiene la propiedad P.
2. si f ∈ FnΣ y t1, . . . , tn ∈ TΣ son términos con la propiedad P, entonces el término
f(t1, . . . , tn) también tiene la propiedad P.
entonces todos los Σ-términos tienen la propiedad P.
El principio de inducción estructural para fórmulas dice que si P es una
propiedad aplicable a las palabras del alfabeto dado por la signatura Σ y se verifica que:
1. toda fórmula atómica tiene la propiedad P.
2. si la fórmula ϕ tiene la propiedad P, entonces la fórmula (¬ϕ) tiene la propiedad
P.
3. si ϕ1, ϕ2 son fórmulas con la propiedad P y ◦ es una conectiva binaria, entonces
(ϕ1 ◦ ϕ2) tiene la propiedad P.
4. si la fórmula ϕ tiene la propiedad P, K es un cuantificador y x es una variable,
entonces Kxϕ tiene la propiedad P.
8
entonces todas las Σ-fórmulas tienen la propiedad P.
Consecuencia de esto son los principios de unicidad estructural. El de términos
dice que si t es un Σ-término, entonces o bien t es atómico o bien t es de la forma
f(t1, . . . , tn). El de fórmulas dice que si ϕ es una Σ-fórmula, entonces o bien es atómica
o bien de la forma (¬ϕ1), (ϕ1 ◦ ϕ2) o Kxϕ1.
El principio de recursión estructural para términos dice que si tenemos una
aplicación F : TΣ → C (siendo C un conjunto), está aplicación está completamente
definida si tenemos el siguiente esquema recursivo:
las imágenes de los términos atómicos (F(t)) se definen expĺıcitamente.
si tenemos un término compuesto f(t1, . . . , tn), su imagen depende únicamente de
f y de F(t1), . . . ,F(tn)
El principio de recursión estructural para fórmulas dice que si tenemos una
aplicación F : LΣ → C (siendo C un conjunto), está aplicación está completamente
definida si tenemos el siguiente esquema recursivo:
las imágenes de las fórmulas atómicas se definen expĺıcitamente.
F((¬ϕ)) sólo depende del valor de F(ϕ).
F((ϕ1 ◦ ϕ2) solo depende de ◦, F(ϕ1) y F(ϕ2).
F(Kxϕ) sólo depende de K y de F(ϕ)
Ejemplo 5.1. Si definimos el vocabulario de un término t como el conjunto voc(t)
de todos los śımbolos de función que aparecen en t, podemos utilizar el principio de
recursión estructural de la siguiente manera:
voc(c) = ∅ y voc(c) = {c}.
voc(f(t1, . . . , tn)) = {f} ∪ voc(t1) ∪ · · · ∪ voc(tn).
Podemos definir una aplicación similar que de una Σ-fórmula dé el conjunto de todos
los śımbolos de predicado de la misma.
Ejemplo 5.2. De idéntica manera a como haćıamos en LP, podemos definir los subtérmi-
nos de un término (todos los términos que aparecen en uno dado) y las subfórmulas de
una fórmula. Para ello aplicamos el principio de recursión:
1. Para los términos:
a) sub(t) = {t} si t es atómico.
b) sub(f(t1, . . . , tn)) = {f(t1, . . . , tn)} ∪ sub(t1) ∪ · · · ∪ sub(tn).
2. para las fórmulas:
a) sub(ϕ) = {ϕ)} si ϕ es atómica.
b) sub((¬ϕ)) = {(¬ϕ)} ∪ sub(ϕ).
c) sub((ϕ1 ◦ ϕ2)) = {(ϕ1 ◦ ϕ2)} ∪ sub(ϕ1) ∪ sub(ϕ2).
d) sub(Kxϕ) = {Kxϕ} ∪ sub(ϕ)
9
6. Escritura abreviada
Para comodidad introduciremos convenios que hagan la escritura de fórmulas menos
engorrosa:
Se omitirán los paréntesis exteriores.
Se siguen los mismos convenios que en la lógica de primer orden.
Los cuantificadores tiene prioridad sobre las conectivas (ej: (∀xf(x, y) → g(f(x, y), y)
abrevia ∀xf(x, y)) → g(f(x, y), y)).
7. Cuantificadores
Si una fórmula contiene cuantificadores, tendrá como subfórmula una del tipo Kxϕ.
En este caso se dice que x es la variable cuantificada y que ϕ es el radio de acción de
la cuantificación. Por ejemplo, en ∀x∃yf(x, y), la variable x está cuantificada y su radio
de acción es ∃yf(x, y). Aśı mismo, la variable y está cuantificada y su radio de acción
es f(x, y).
Una aparición de una variable en una fórmula es ligada si está en el radio de acción
de alguna cuantificación. En caso contrario se dice que la variable es libre.
8. Formalización del lenguaje natural
1. Universal afirmativo: representamos por
∀x(ϕ→ ψ)
∀x(¬ψ → ¬ϕ)
frases del tipo:
Todo ϕ es ψ
Sólo los ψ son ϕ
Nadie es ϕ salvo que sea ψ
No hay ningún ϕ que no sea ψ
ϕ es suficiente para ψ
ψ es necesario para ϕ
2. Universal negativo: representamos por
∀x(ϕ→ ¬ψ)
frases del tipo:
Ningún ϕ es ψ
10
Todos los ϕ carecen de ψ
3. Existencial afirmativo:representamos por
∃x(ϕ ∧ ψ)
frases del tipo
Algún ϕ es ψ
Alguien es a la vez ϕ y ψ
4. Existencial negativo: representamos por
∃x(ϕ ∧ ¬ψ)
frases del tipo:
Algún ϕ no es ψ
No todos los ϕ son ψ
Veamos algunos ejemplos de como se expresan en lenguaje formal frases del lenguaje
natural.
La sentencia Todos tenemos exactamente un alma gemela se puede modelizar de la
siguiente forma:
Sea G(x, y) la sentencia y es el alma gemela de x. La sentencia que queremos mod-
elizar dice que para cualquier persona x, existe otra y que es su alma gemela y que
cualquier otra persona z no es el alma gemela de x:
∀x ∃y (G(x, y) ∧ ∀z ((z ̸= y) → ¬G(x, z)))
Hay que tener cuidado con la negación de una sentencia cuando viene afectada por
un cuantificador. Supongamos que queremos negar la sentencia
Todos los alumnos de esta clase han aprobado algún examen en febrero.
Para ello simbolicemos por C(x) el predicado x es un alumno de esta clase, por A(x, y) el
predicado x ha aprobado el examen y y por F (y) y se realizó en febrero. Aśı, la sentencia
dada se puede escribir
∀x [C(x) → (∃y (A(x, y) ∧ F (y)))] .
Su negación seŕıa
¬∀x [C(x) → (∃y (A(x, y) ∧ F (y)))]
que, según sabemos, es lógicamente equivalente a
∃x ¬ [C(x) → (∃y (A(x, y) ∧ F (y)))]
11
que a su vez es lógicamente equivalente a
∃x ¬ [¬C(x) ∨ (∃y (A(x, y) ∧ F (y)))]
que a su vez es lógicamente equivalente a
∃x [¬(¬C(x)) ∧ ¬(∃yA(x, y) ∧ F (y))]
que a su vez es lógicamente equivalente a
∃x [C(x) ∧ (∀y ¬(A(x, y) ∧ F (y))]
que a su vez es lógicamente equivalente a
∃x [C(x) ∧ (∀y (¬A(x, y) ∨ ¬F (y))] .
Es decir, la negación de la sentencia es
Existe algún alumno de esta clase que o no ha aprobado ningún examen (∀y (¬A(x, y)))
o, si lo ha aprobado, no ha sido en febrero.
Si preferimos quedarnos con la sentencia lógicamente equivalente a ésta de la penúltima
ĺınea se podŕıa leer
existe algún alumno de esta clase que no ha aprobado ningún examen en febrero.
9. Ejercicios
1). Escribir de forma simbólica las siguientes sentencias y su negación, de manera
que en la expresión final no haya ningún cuantificador precedido del śımbolo negación:
1. No todos los españoles son periodistas
2. Si algún caminante bosteza, todos los caminantes bostezan
3. Todo el mundo conoce a algún modisto
4. Entre dos números números reales distintos cualesquiera existe algún número
racional
5. No existe un primo mayor que el resto de los números primos
2). Sea xn una sucesión de números reales. Sea R+ el conjunto de los números reales
positivos y N el conjunto de los números naturales. Se dice que
ĺım(xn) = a si ∀ε ∈ R+ (∃n ∈ N(∀m ∈ N(m > n→ |xm − a| < ε))).
Escribir una sentencia que indique formalmente que ĺım(xn) ̸= a.
12
logica/tema6.pdf
Tema 6: Semántica de la Lógica de primer orden
1. Contenidos
El alumno será capaz de realizar evaluaciones semánticas de fórmulas.
El alumno conocerá el concepto de validez semántica.
El alumno conocerá las equivalencias básicas de fórmulas.
2. Evaluación semántica
A diferencia de lo que pasaba en LP, en LPO tenemos individuos, y la ((verdad)) de las
fórmulas (según el análogo a las valoraciones) dependerá de quienes sean los individuos
concretos.
Dando una definición un poco informal , si tenemos una signatura Σ, tendremos que
concretar el SIGNIFICADO de cada uno de sus śımbolos. Para ello, definiremos
una
Σ-estructura (A), que consistirá:
en un universo A, que será un conjunto no vaćıo.
Un significado SA(c) ∈ A para cada constante c de Σ. Dentro del (ahora concreto)
universo de discurso damos un valor concreto a cada constante, de manera que
cada una de ellas designe un individuo (elemento) del conjunto.
Un significado SA(f) que a cada función de aridad n de Σ le hace corresponder una
función de An en A, es decir, una función del número correspondiente de variables
del universo A en A.
Un significado SA(R) que a cada relación de aridad n de Σ le hace corresponder
una relación n-aria en A (es decir, SA(R) ⊂ An.
Un significado SA(p) que a cada śımbolo proposicional de Σ le hace corresponder
un valor en {0, 1}, es decir, se indica si cada śımbolo proposicional denota una
proposición verdadera o falsa.
Ejemplo 2.1. Si recordamos Σar, abusando un poco de la notación tendŕıamos que
una posible Σ-estructura N seŕıa aquella en la que el universo consistiŕıa en los números
naturales (A = N), y SN (c) = 0, SSN (f) = suc, con suc(n) = n + 1, SN (g) = +
(operación suma), SN (h) = · (operación producto) y SN (R) =< (relación de orden).
1
Podemos dar una estructura distinta Z en Σar si tomamos como universo los enteros,
haciendo que el significado de g, h,R sea el mismo que antes (pero con los enteros) y
haciendo SZ(c) = 1 y ScZ(f) = | |.
Podemos sacar dos conclusiones de las definiciones anteriores: por un lado una misma
signatura admite varias estructuras, y por otro, una estructura no hace nada con las
variables. Esto es debido a que una estructura fija los elementos constantes, pero las
variables pueden cambiar (se supone que a su antojo) de valor en una estructura dada.
Esto motiva la siguiente definición:
Dada una signatura Σ y una Σ-estructura A, un estado de las variables es cualquier
aplicación σ : V → A (una asignación arbitraria de valores de las variables sobre el
universo de discurso). Una Σ-interpretación es una Σ-estructura junto con un estado σ,
que se nota por (A, σ)
Una Σ-interpretación permite relacionar cualquier término t ∈ TΣ con un individuo
concreto σA(t) ∈ A y cualquier fórmula ϕ ∈ LΣ con un valor veritativo σA(ϕ) ∈ {0, 1}.
Observación 2.2. Esta situación es parecida al efecto de la asignación de valores deter-
minados a las variables en un lenguaje de programación. Esta idea motiva la siguiente
definición.
Si tenemos un estado σ : V → A y un a ∈ A, definimos el estado σ[x/a] como el
estado que coincide con σ salvo en el caso de x, a la que se le hace corresponder el valor
de a (es decir, una vez fijadas las variables, a la variable x se le asigna el valor a, sin
alterar los valores de las demás variables.
Formalizando un poco:
Definición 2.3. Una Σ-interpretación (A, σ) hace corresponder a cualquier término
t ∈ TΣ un valor σA(t) ∈ A de la siguiente manera:
Base: σA(x) = σ(x) y σA(c) = SA(c)
σA(f(t1, . . . , tn) = S(f)(σA(t1), . . . σA(tn))
y a su vez hace corresponder a cada fórmula ϕ ∈ LΣ un valor veritativo σA(ϕ) definido
recursivamente de la siguiente manera:
Base: σA(⊥) = 0, σA(⊤) = 1 y σA(p) = SA(p)
σA(s = t) =
{
1 si σA(s) = σA(t)
0 si σA(s) ̸= σA(t)
σA(P (t1 . . . , tn)) =
{
1 si SA(P )(σA(t1), . . . , σA(tn))
0 en caso contrario
Pasos recursivos:
• σA(¬ϕ) = B¬(σA(ϕ))
• σA(ϕ ◦ ψ) = b◦(σA(ϕ), σA(ψ))
2
• σA(∀xϕ) = mı́n {σA(ϕ)[x/a] : a ∈ A}
• σA(∃xϕ) = máx {σA(ϕ)[x/a] : a ∈ A}
Ejemplo 2.4. Si consideramos las interpretaciones N y Z de antes
σN (h(x, y)) = σ(x) · σ(y)
σN (f(g(c, c))) = suc(0 + 0) = 1
σZ(f(g(c, c))) = |1 + 1| = 2
Definición 2.5. Si σA(ϕ) = 1 decimos que A satisface ϕ en el estado σ, que (A, σ)
satisface a ϕ o que (A, σ) es un modelo de ϕ, y se nota A |= ϕσ. En caso contrario se
dice que (A, σ) no satisface a ϕ o que (A, σ) no es un modelo de ϕ, y se nota A ̸|= ϕσ.
Extendiendo esto a conjuntos de fórmulas:
Definición 2.6. Si Φ ⊂ LΣ, escribimos
A |= Φσ si A |= ϕσ para toda ϕ ∈ Φ, y decimos que (A, σ) es un modelo de Φ.
̸ A |= Φσ si A ̸|= ϕσ para alguna ϕ ∈ Φ, y decimos que (A, σ) no es un modelo de
Φ.
Definición 2.7. Una fórmula o conjuntos de fórmulas se dicen satisfacibles si admiten
un modelo e insatisfacibles en caso contrario.
3. Validez y consecuencia lógicas
Definición 3.1. Una fórmula ϕ ∈ LΣ es
lógicamente válida si A |= ϕσ para toda interpretación (A, σ).
contradictoria si A ̸|= ϕσ para toda interpretación (A, σ).
contingente si podemos encontrar dos interpretaciones (A1, σ1) y (A2, σ2) de man-
era que A1 |= ϕσ1 y A2 ̸|= ϕσ2
Ejemplo 3.2. Son lógicamente válidas:
∃xP (x) ∨ ¬∃xP (x)
∀x∀y(P (x) ∧ x = y) → P (y)
Son contradicciones:
∃x(P (x)) ∧ ¬P (x)
∃xP (x) ∧ ¬∃xP (x)
Son contingentes:
3
∃xP (x)
∀x∃yP (x, y)
Todo lo que sabemos de la lógica de proposiciones lo podemos utilizar aqúı:
Teorema 3.3. 1. Si ϕ0 es una tautoloǵıa de la lógica proposicional y ϕ es la fórmula
que resulta reemplazando los śımbolos de proposición por fórmulas (es un caso de
ϕ0), ϕ es lógicamente válida.
2. Si ϕ0 es una contradicción de la lógica proposicional y ϕ es un caso de ϕ0, entonces
ϕ es contradictoria.
Teorema 3.4. Sean ϕ, ϕ0 fórmulas de la lógica de predicados, siendo ϕ un caso partic-
ular de ϕ0. Si ϕ0 es lógicamente válida, también lo es ϕ.
Para conseguir más tautoloǵıas necesitamos una definición formal de sustituciones
en LPO, que son un poco más complicadas que en LP:
Definición 3.5. 1. El término s[x/t] obtenido al sustituir las apariciones de la vari-
able x dentro del término s por el término t se define recursivamente como:
Base: x[x/t] ≡ t, y[x/t] ≡ y si y ̸≡ x y c[x/t] ≡ c
Pasos recursivos: f(s1, . . . , sn)[x/t] ≡ f(s1[x/t], . . . , sn[x/t])
2. La fórmula resultante de sustituir las apariciones libres de la variable x en la
fórmula ϕ por el término t se define recursivamente como:
Base:
• ϕ[x/t] ≡ ϕ si ϕ es ⊥,⊤ o p.
• (s1 = s2)[x/t] ≡ (s1[x/t] = s2[x/t])
• P (s1, . . . , sn)[x/t] ≡ P (s1[x/t], . . . , sn[x/t])
Pasos recursivos:
• (¬ϕ)[x/t] ≡ ¬ϕ[x/t]
• (ϕ1 ◦ ϕ2)[x/t] ≡ (ϕ1[x/t] ◦ ϕ2[x/t])
• (Kyϕ)[x/t] ≡ Kyϕ si x ≡ y o x no es una variable libre de ϕ.
• (Kyϕ)[x/t] ≡ Kyϕ[x/t] si y ̸≡ x, x es una variable libre de ϕ e y no es
una variable de t.
• (Kyϕ)[x/t] ≡ Kzϕ[y/z][x/t] si y ̸≡ x, x es una variable libre de ϕ e y
es una variable de t (donde z es la primera de las variables disponibles
distinta de x que no aparece en t y no aparece libre en ϕ).
Ejemplo 3.6. Algunos ejemplos con notación aritmética para que sean más claros:
(x < y + z)[z/u ∗ v] ≡ x < y + u ∗ v
∃z(x+ y = z)[x/u+ v] ≡ ∃z(u+ v + y = z)
4
∃z(x+ y = z)[y/z + 1] ≡ ∃u(x+ z + 1 = u)
Las sustituciones se llevan bastante bien con las valoraciones:
Teorema 3.7 (Lema de sustitución). Sea t un término que va a sustituirse en lugar de
la variable x:
1. Para todo término s y toda interpretación (A, σ):
σA(s[x/t]) = σA(s)[x/σA(t)]
2. Para toda fórmula ϕ y toda interpretación (A, σ):
σA(ϕ[x/t]) = σA(ϕ)[x/σA(t)]
Definición 3.8. Sea Φ ⊂ LΣ un conjunto de fórmulas (que actúan como hipótesis o
premisas) y ψ ∈ LΣ una fórmula (que actúa como conclusión). Se dice que ψ es una
consecuencia lógica de Φ, y se escribe Φ |= ψ, si cualquier interpretación que satisfaga
Φ también satisface ψ.
Mientras que en LP teńıamos métodos finitos (tablas de verdad o tableaux) para
comprobar la validez de un razonamiento, el concepto de interpretación es mucho más
amplio y no permite utilizar estos métodos. Algunos resultados son:
Teorema 3.9. 1. ϕ es lógicamente válida si y sólo si ∅ |= ϕ. En este caso se escribe
|= ϕ.
2. Dados Φ ⊂ LΣ, ϕ, ψ ∈ LΣ,
Φ |= ϕ→ ψ si y sólo si Φ ∪ {ϕ} |= ψ
3. Para Φ ⊂ LΣ, ϕ ∈ LΣ,
Φ |= ϕ si y sólo si Φ ∪ {¬ψ} es insatisfacible
4. La validez de una inferencia se preserva al efectuar una misma sustitución de
śımbolos de proposición por fórmulas en las premisas y en la conclusión.
5. Las siguientes consecuencias lógicas siempre son válidas:
|= t = t (reflexividad de la igualdad)
t = t′ |= t′ = t (simetŕıa de
la igualdad)
t = t′, t′ = t′′ |= t = t′′ (transitividad de la igualdad)
ϕ[x/t], t = t′ |= ϕ[x, t′] (sustitutividad de la igualdad)
∀xϕ |= ϕ[x/t] (hipótesis universal)
ϕ[x/t] |= ∃xϕ (tesis existencial)
5
4. Equivalencia lógica
Dos fórmulas ϕ, ψ de la lógica de predicados son equivalentes, y se escribe ϕ ∼ ψ, si
σA(ϕ) = σA(ψ) para toda interpretación (A, σ).
Teorema 4.1. La relación ∼ es de equivalencia en LΣ. Además, dadas ϕ, ψ ∈ LΣ, son
equivalentes:
1. ϕ ∼ ψ
2. |= ϕ↔ ψ
3. |= ϕ→ ψ y |= ψ → ϕ
4. ϕ |= ψ y ψ |= ϕ
Teorema 4.2. Las siguientes equivalencias lógicas son válidas:
1. ¬∃xϕ ∼ ∀x¬ϕ y ¬∀xϕ ∼ ∃x¬ϕ
2. ∃x∃tϕ ∼ ∃y∃xϕ y ∀x∀tϕ ∼ ∀y∀xϕ
3. Si x no es una variable libre de ϕ, entonces
∃xϕ ∼ ϕ y ∀xϕ ∼ ϕ
4. ∃xϕ ∨ ∃xψ ∼ ∃x(ϕ ∨ ψ)
5. ∀xϕ ∧ ∀xψ ∼ ∀x(ϕ ∧ ψ)
6. Si ◦ indica la conjunción o la disyunción y x no es una variable libre de ϕ, entonces
∃xϕ ◦ ψ ∼ ∃x(ϕ ◦ ψ) y ∀xϕ ◦ ψ ∼ ∀x(ϕ ◦ ψ)
7. Si x no es una variable libre de ϕ,
∃xϕ→ ψ ∼ ∀x(ϕ→ ψ) y ∀xϕ→ ψ ∼ ∃x(ϕ→ ψ)
8. Si x no es una variable libre de ϕ,
ϕ→ ∃xψ ∼ ∃x(ϕ→ ψ) y ϕ→ ∀xψ ∼ ∀x(ϕ→ ψ)
9. Si y ̸≡ x y y no es una variable libre de ϕ,
∃xϕ ∼ ∃yϕ[x/y] y ∀xϕ ∼ ∀yϕ[x/y]
6