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

Esta es una vista previa del archivo. Inicie sesión para ver el archivo 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