Download Lógica Proposicional

Lógica Formal
Roberto Moriyón
Introducción
• El objetivo de la Lógica Formal o Lógica
Matemática es proporcionar un sistema formal
único en el que la producción de palabras a
partir de axiomas dé lugar a deducciones
válidas en contextos arbitrarios.
• Hay varios sistemas lógicos formales que son
capaces de formalizar cualquier razonamiento
válido.
• Un sistema lógico formal se puede ver como un
sistema formal deductivo universal, en el mismo
sentido que las máquinas de Turing universales.
Esbozo histórico
• En el siglo IV aC, Aristóteles clasificó los
distintos tipos de razonamiento.
• En el siglo XVII, Arnold y Locke destacaron la
importancia de estudiar las ideas asociadas a
cada afirmación lógica (su interpretación).
• También en el siglo XVII, Descartes y Leibnitz
destacaron los aspectos algebraicos de la
manipulación formal de las fórmulas lógicas.
Esbozo histórico, II
• En el siglo XIX, Frege introdujo la utilización de
variables y cuantificadores para representar
fórmulas lógicas; Peano dio la primera
axiomatización de la aritmética, y Peirce
introdujo la lógica de segundo orden.
• A comienzos del siglo XX, Hilbert propuso un
programa para demostrar la consistencia de las
Matemáticas en base a una axiomatización de
ellas. Posteriormente, Gödel demostró que esto
era imposible.
Esbozo histórico, III
• A lo largo del siglo XX se han desarrollado
particularmente lógicas especiales (modal,
temporal, etc) y lógicas relacionadas con
la teoría de la computación (Cálculo  con
tipos, lenguajes de programación lógicos,
etc)
Lógica proposicional
• Sistema formal deductivo que genera fórmulas
proposicionales basadas en afirmaciones
atómicas que pueden ser verdaderas o falsas.
• Alfabeto:
– Atomos: P, Q, R, P’, Q’, R’, P’’, …
– Operaciones lógicas: ^, v, , ~
– Separadores: (, ) [A veces es útil utilizar separadores
especiales y obligatorios, < y >, para desambiguar la
gramática]
• Ejemplos de fórmulas proposicionales: P v ~P,
~Q  (Q  P)
Operadores lógicos
X
Y
X^Y
XvY
XY
T
T
T
T
T
T
F
F
T
F
F
T
F
T
T
F
F
F
F
T
Operadores lógicos:
Significado de XY
• En principio, el significado de XY es “si
X es cierto, entonces Y también es cierto”.
• Por lo tanto su tabla de verdad será como
sigue:
X
T
Y
T
XY
T
T
F
F
F
T
F
T
?
?
Operadores lógicos:
Significado de XY, II
• Ejemplos con cuantificador universal:
– Para todos los números x, si x es impar,
entonces x+1 es par
x,(impar(x)  par(x+1))
– Para todos los números x, si x es impar,
entonces x+x es par
x,(impar(x)  par(x+x))
– Para todos los números x, si x es impar,
entonces x+1 es impar
x,(impar(x)  impar(x+x))
Operadores lógicos:
Significado de XY, III
X
i(x)
p(x+1) p(x+x) i(x+x) i(x)p(x+1) i(x)p(x+x) i(x)i(x+x)
0
F
F
T
F
?
?
?
1
T
T
T
F
T
T
F
2
F
F
T
F
?
?
?
3
T
T
T
F
T
T
F
4
F
F
T
F
?
?
?
5
T
T
T
F
T
T
F
Operadores lógicos:
Significado de XY, IV
• Para que los ejemplos anteriores tengan
contestaciones razonables hay que
interpretar que la implicación XY es
cierta si “Si X es cierto, entonces Y
también. Si X no es cierto, da lo mismo
que se verifique Y o no”.
• (X ^ Y) v ~X
• Esta definición es consistente en general
con la definición de implicaciones en la
Lógica de Predicados.
Lógica proposicional:
Interpretaciones
• Una interpretación I de una fórmula F es una
asignación de un valor lógico PI (True o False) a
cada átomo P de F. La interpretación asigna un
valor lógico a la fórmula utilizando las tablas de
los distintos operadores.
• Una fórmula es cierta en una interpretación si
le corresponde el valor True mediante ella.
• La tabla asociada a una fórmula tiene una
interpretación en cada fila.
Interpretaciones
en el mundo real
• Normalmente las fórmulas lógicas se
interpretan a un primer nivel haciendo
corresponder a cada símbolo proposicional una afirmación (por ejemplo, llueve o
los eliomartos rusitan). La interpretación
se completa mediante una imagen del
universo en la que cada una de las
afirmaciones asociadas a los símbolos
proposicionales es cierta o falsa.
Lógica proposicional:
Interpretaciones, II
~Q(QP)
P
Q
~Q
QP
~Q(QP)
T
T
F
T
T
T
F
T
T
T
F
T
F
F
T
F
F
T
T
T
Lógica proposicional:
Interpretaciones, III
• Dada una asignación de valores
booleanos a átomos, la función que a
cada fórmula le hace corresponder su
interpretación se puede definir de forma
recursiva utilizando las reglas
– IntI[F^G]  IntI[F]^IntI[G]
– IntI[FvG]  IntI[F]vIntI[G]
– IntI[FG]  IntI[F]IntI[G]
– IntI[~F]  ~IntI[F]
(morfismo entre fórmulas y valores
booleanos)
Lógica proposicional:
Interpretaciones, IV
• Ejemplo:
Si PI True y QIFalse,
IntI[P^~QQ]  IntI[P^~Q]QI 
 (PI^~QI)QI  True
Fórmulas satisfactibles y
tautologías
• Una fórmula es satisfactible si es cierta en
alguna interpretación.
– Ejemplos: QP, Q  (Q  P)
• Una fórmula es una tautología si es cierta en
todas las interpretaciones.
– Ejemplos: Qv~Q, ~Q  (Q  P)
• Nota: En lo sucesivo, al igual que se suele hacer
con las expresiones aritméticas, pondremos
paréntesis cuando ello aclare o desambigüe la
lectura de las fórmulas.
Fórmulas satisfactibles y
tautologías en el mundo real
• Cualquier fórmula lógica satisfactible, en
cualquier universo de interpretación
asociado, tiene una interpretación en la
que es cierta. Pero puede que no sea la
interpretación natural en ese universo.
• Cualquier tautología lógica, en cualquier
universo de interpretación asociado, es
cierta en todas sus interpretaciones.
Interpretaciones:
Representación intuitiva
• Es la función característica de un
semianillo que contiene a todas las
tautologías y contiene uno de los radios
que lo limitan.
• No contiene a ninguna fórmula
insatisfactible.
M
Tautologías e insatisfactibilidad
• Una fórmula es insatisfactible si no es satisfactible, es decir si no es cierta en ninguna interpretación.
– Ejemplos: Q^~Q (contradicción), ~(~Q  (Q  P))
• En general, la negación de una tautología es una
fórmula insatisfactible y viceversa.
Tautologías
Insatisfactibes
Satisfactibles
Consecuencias de
familias de fórmulas
• Diremos que una fórmula F es
consecuencia de un conjunto de fórmulas
A (axiomas), y lo escribiremos AF, si
toda interpretación que hace ciertas todas
las fórmulas de A también hace cierta F.
• Ejemplo 1: si F es una tautología,
entonces es consecuencia de cualquier
conjunto de axiomas
• Ejemplo 2: La proposición ~FG es
consecuencia del axioma F.
Consecuencias de familias de
fórmulas, II
• Los problemas típicos de razonamiento
consisten en hallar las consecuencias de
unos axiomas dados, o en demostrar que
una fórmula concreta lo es.
Consecuencias:
Representación intuitiva
• Es la intersección de todos los semianillos que
contienen a A asociados a interpretaciones.
A

Consecuencias:
Representación intuitiva, II
• Otro ejemplo:

Consecuencias:
Representación intuitiva, III
• Un ejemplo más: Las consecuencias
incluyen alguna fórmula insatisfactible

Consecuencias:
Representación intuitiva, IV
• Si hay alguna fórmula insatisfactible entre
las consecuencias de un conjunto de
axiomas, entonces todas las fórmulas son
consecuencia de ellos.
• Demostración: Todas las fórmulas son
consecuencia de cualquier fórmula
insatisfactible, pues no hay ninguna
interpretación en la cual ésta sea cierta.
Consecuencias: Caso particular
• Las fórmulas que son ciertas en una
interpretación concreta forman un
conjunto de axiomas cuyas consecuencias
son ellas mismas.
• Estos conjuntos de fórmulas son
conjuntos satisfactibles maximales.
Criterio para reconocer
consecuencias
• Para ver si una fórmula F es consecuencia de un
conjunto finito A de axiomas se pueden emplear
tres procedimientos:
– Formar una tabla con los valores lógicos de los
axiomas y de F y examinar sus filas.
– Demostrar que A1^A2^…^ANF es una tautología.
– Demostrar que toda interpretación que hace ciertos los
axiomas también hace cierta F.
Los emplearemos para ver que ((~PvQ)R) es
consecuencia de {P, QR}.
Consecuencias de
familias de fórmulas, III
P
T
T
T
T
F
F
F
F
Q
T
T
F
F
T
T
F
F
R
T
F
T
F
T
F
T
F
QR (~PVQ)R
T
T
F
F
T
T
T
T
T
T
F
F
T
T
T
F
Consecuencias de
familias de fórmulas, IV
• {F1, F2}  F  (F1 ^ F2)  F tautología
(P ^ (QR))  ((~PvQ)R) 
~P v (Q^~R) v ((P ^ ~Q) v R) 
~P v (Q^~R) v ((P v R) ^ (~Q v R)) 
(~P v (Q^~R) v P v R) ^
(~P v (Q^~R) v (~Q v R)) es tautología,
luego {P, QR}  ((~PvQ)R)
Consecuencias de
familias de fórmulas, V
• Suponemos que en la interpretación I, PI y
QIRI son ciertas
• Es cierto que entonces (~PIvQI)RI?
– Primer caso: PI=True, QI=False. Entonces,
((~PIvQI)RI)=True, pues ~PIvQI=False.
– Segundo caso: PI=True, QI=True, RI=True.
Entonces, ((~PIvQI)RI)=True, ya que
RI=True.
Consecuencias de
familias de fórmulas, VI
El conjunto de axiomas aceptados puede ser
infinito. Entonces los dos primeros procedimientos no sirven.
Ejemplos:
• A=(P)*Q es un conjunto infinito recursivo de
fórmulas. AQ^(PQ).
• El patrón PP define otro conjunto infinito
recursivo A’ de fórmulas. Todas ellas son
tautologías. A’F si F es cualquier tautología.
Consecuencias de
familias de fórmulas, VII
• Una fórmula F es una tautología si y sólo
si F.
• Una fórmula F es insatisfactible si y sólo si
~F.
Consecuencias de familias de
fórmulas: Ejercicio obligatorio
[CONSPROC] Demostrar por cada uno de
los procedimientos dados lo siguiente:
•
F  (Yv~X)  Y es consecuencia de
A={~Y, X}
•
G  (~Y^X)  Y no es consecuencia de
A={~Y, X}
Ejercicios opcionales
• [PROGVER] Escribir un programa que
comprueba la veracidad de fórmulas con
respecto a una interpretación.
• [PROGSAT] Escribir un programa que
determina si una fórmula es satisfactible y
si es una tautología.
• [PROGCONS] Escribir un programa que
determina si una fórmula proposicional es
consecuencia de otras.
Ejercicio obligatorio
• [CAJ] Entre tres cajas numeradas del 1 al
3 dos están vacías y la otra no. Además,
una de las afirmaciones “La primera caja
está vacía”, “La segunda caja está vacía”
y “La segunda caja está llena” es cierta y
las otras dos no. Demostrar cuál de las
tres cajas está llena y demostrar que las
otras dos cajas no lo están.
Ejercicios opcionales
• [AB] Demostrar que no se pueden colorear
tres objetos A, B y C en blanco y negro de
manera que A y B no tengan el mismo color,
B y C tampoco y A y C tampoco
• [TT] Demostrar que el siguiente razonamiento es correcto: Si la temperatura y la presión
no cambian, no llueve. La temperatura no
cambia. Como consecuencia de lo anterior,
si llueve entonces la presión cambia.
Ejercicio opcional
• [FOTO] Deducir que la foto es de Juan como
consecuencia de los siguientes axiomas:
–
–
–
–
–
La foto es redonda o cuadrada
La foto es en color o en blanco y negro
Si la foto es cuadrada, entonces es en blanco y negro
Si la foto es redonda, entonces es digital y en color
Si la foto es digital o en blanco y negro, entonces es
un retrato
– Si la foto es un retrato entonces es de Juan
Ejercicios opcionales
• [UNIC] Suponemos los siguientes axiomas
acerca del unicornio :
– Si es mítico, entonces es inmortal
– Si no es mítico, es un mamífero mortal
– Si es inmortal o mamífero, entonces tiene
cuernos
– Si tiene cuernos es mágico
• Como consecuencia de todo ellos es
mítico? Es mágico? Tiene cuernos?
Ejercicios opcionales
• [GR1] Decir quiénes dicen la verdad y
quiénes dicen la mentira sabiendo que:
– Alceo dice “los únicos que decimos la verdad
aquí somos Cátulo y yo”
– Safo dice “Cátulo miente”
– Cátulo dice “Safo dice la verdad, o Alceo
miente”
Ejercicios opcionales
• [GR2] Decir quiénes dicen la verdad y
quiénes dicen la mentira sabiendo que:
– Anaximandro dice “Heráclito miente”
– Parménides dice “Anaximandro y Heráclito no
mienten”
– Heráclito dice “Parménides no miente”
Razonamiento
• El razonamiento se utiliza para obtener
nuevos hechos ciertos a partir de otros
que lo son o al menos se supone que lo
son. Por lo tanto razonar consiste en
encontrar las consecuencias de un
conjunto de fórmulas.
Razonamiento, II
• Se puede razonar considerando todas las
fórmulas y todas las interpretaciones y
calculando los valores booleanos correspondientes para ver qué fórmulas son
consecuencia de los axiomas, pero este
algoritmo es inadecuado, especialmente si
se incrementa la capacidad expresiva del
lenguaje lógico y se permiten
razonamientos sobre objetos (Lógica de
Predicados) o si se utiliza un conjunto
infinito de axiomas.
Razonamiento, III
• Es preferible dar un algoritmo que proporcione directamente las fórmulas que son
consecuencia de unos axiomas dados.
• Se hará mediante un sistema formal (un
cálculo lógico) formado por reglas de
inferencia o de deducción.
• En este sistema, una fórmula P se deduce
de un conjunto A de axiomas si y sólo si es
consecuencia de ellos (es decir, AP sii
AP).
Deducción
• Una deducción es una sucesión de fórmulas,
cada una de las cuales se obtiene a partir de las
anteriores mediante una regla formal de
deducción.
• En una regla de deducción XY, X e Y son
fórmulas lógicas que verifican que X  Y. Eso
hace que al generar cualquier fórmula
X1X2…XN
automáticamente se tenga que X1  XN.
Deducción, II
• Si las fórmulas iniciales (hipótesis o
axiomas) de una deducción son ciertas
en una interpretación I, entonces
también lo son todas las fórmulas
deducidas (consecuencias).
• El sistema formal de deducción que
utilizaremos será completo en el sentido
de que producirá todas las fórmulas que
son consecuencia de un conjunto dado
de axiomas.
Ejemplo de deducción
• Axiomas:
- Si llueve está nublado.
- Si está nublado hace frío.
- Llueve.
• Demostrar que hace frío.
Ejemplo de deducción, II
• Los axiomas anteriores se pueden
representar mediante fórmulas como sigue:
– L representa “llueve”
– N representa “está nublado”
– F representa “hace frío”
– Axiomas: A = { LN, NF, L }
Ejemplo de deducción, III
• Deducción:
– De L y LN se deduce N
– De N y NF se deduce F
• Observaciones:
– La deducción anterior aplica una única regla
formal (modus ponens):
,   .
– La deducción anterior es correcta independientemente de la interpretación de L, N y F.
Ejemplo de deducción, IV
• Observaciones:
– El modus ponens, ,    permite que
las implicaciones se utilicen como reglas que
se pueden aprender al razonar.
– Las variables con letras griegas son fórmulas
Agrupamiento de fórmulas
deducidas
• Agrupamiento conjuntivo:
,    ^ 
• Disociación conjuntiva:
^
^
• Conmutatividad conjuntiva:
^^
(se podría haber evitado dejando las
anteriores)
Ejemplo de deducción, V
• Axiomas:
- Si llueve está nublado.
- Si está nublado hace frío.
• Demostrar que si llueve hace frío.
Ejemplo de deducción, VI
• Deducción:
– Suponemos por un momento que L es cierto.
• Entonces, según hemos visto, se deduce F.
– De lo anterior y de los axiomas se deduce que
LF.
• La deducción anterior aplica una regla
formal nueva (deducción de implicación):
,   ()
• Esta regla permite construir reglas nuevas,
de modo análogo a lo ya visto al estudiar
los sistemas formales en general.
Ejemplo de deducción, VII
• Axiomas:
- Si llueve está nublado o hay arco iris.
- Si está nublado hace frío.
- Si hay arco iris está bonito.
• Demostrar que si llueve, o bien hace frío o
está bonito.
• Símbolos nuevos de predicado: A (hay
arco iris), B (está bonito).
Ejemplo de deducción, VIII
• Deducción:
– Suponemos por un momento que L es cierto.
• Como L(N v A), por Modus Ponens se deduce
NvA.
• Suponemos por un momento que ~F^~B es
cierto.
– Entonces ~F y ~B son ciertos.
– Además, como NF, ~F~N. Análogamente, ~B~A.
– De ~F y ~F~N se deduce ~N. De ~B y ~B~A,
resulta ~A.
– De lo anterior se deduce que ~N^~A es cierto.
Ejemplo de deducción, IX
• Por la regla de deducción de implicación,
~F^~B~N^~A
• De lo anterior se deduce que NvAFvB.
• Por el Modus Ponens, FvB es cierto.
– Por la regla de deducción de
implicación, LFvB.
Ejemplo de deducción, X
• Se han utilizado cinco reglas nuevas:
–   ~~
– A~^~B  A~(v)B [A, B cualesquiera]
– A~~B  AB
Equivalencia
• Las implicaciones son reglas que se aplican a
fórmulas completas, pero no a partes de ellas:
XAY, AB  XBY no es una regla.
Por ejemplo, de ~(A^C) y AB no se deduce
~(B^C), aunque de A y AB se deduce B.
Caso particular: Aes de día, Ces de noche,
Bse trabaja.
• Sin embargo, si P y Q son equivalentes, se
pueden intercambiar dentro de cualquier fórmula.
• Ejemplo: No solamente ~~A  A, sino que
X~~AY  XAY.
• Caso particular: el de antes, con Bhay luz.
Lógica proposicional:
Reglas de inferencia
• Agrupamiento conjuntivo:
,    ^ 
• Disociación conjuntiva:
^
^
• Conmutatividad disyuntiva (equivalencia):
AvB  AvB
• Doble negación (equivalencia):
A~~B  AB
AB  A~~B [si bien form]
• Modus ponens (emulación universal):
,   
Lógica proposicional:
Reglas de inferencia, II
• Equivalencias de De Morgan:
A~^~B  A~(v)B
A~(v)B  A~^~B
• Equivalencia de implicaciones a disyunciones:
A~vB  AB
AB  A~vB
• Deducción de implicaciones a partir de inferencias:
A,  A
(recuérdese que en todo sistema formal se pueden
incorporar reglas para la relación ).
Esta regla permite la construcción dinámica de
reglas de deducción. Ejemplo: Teoremas.
Lógica proposicional:
Reglas de inferencia, III
• El sistema se puede completar con más
reglas para hacer más simple la generación
de deducciones
• Por ejemplo,
v
• Para ello hay que demostrar el patrón de
teorema
v
Lógica proposicional:
Reglas de inferencia, IV
• En general, si F y G son dos fórmulas y
FG, entonces al añadir la regla FG a
las reglas de nuestro sistema deductivo
obtenemos otro sistema equivalente al
inicial.
• En general, cada deducción de un patrón
de teorema puede dar a una regla.
Lógica proposicional:
Reglas de inferencia, V
• Otro ejemplo:
  ~~
(se ha utilizado en los ejemplos previos de
deducciones)
• Veremos más adelante que es
consecuencia de las reglas anteriores
Axiomas
• El sistema formal anterior no tiene
axiomas
• La regla de deducción de implicación a
partir de inferencia nos da tautologías que
se pueden ver como axiomas universales:
– ,   ^
– , ^  
– , ~v  



  ^
  ^
  ~v()
• Se pueden construir a partir de
deducciones cualesquiera
Ejemplos simples de deducción
• ~(P^Q)  ~(~~P^Q)  ~(~~P^~~Q) 
 ~~(~Pv~Q)  ~Pv~Q
• La forma habitual de escribirla es:
~(P^Q)
~(~~P^Q)
[Doble negación 2]
~(~~P^~~Q)
[Doble negación 2]
~~(~Pv~Q)
[De Morgan 1]
~Pv~Q
[Doble negación 1]
Ejemplos simples de deducción,
II
• Si ~(P^Q) es cierto, también lo es ~Pv~Q
• Observación: P y Q se pueden sustituir
por fórmulas cualesquiera.
• La regla ~(^)  ~ v~ se puede incluir
como regla de deducción para completar
el sistema utilizado.
Ejemplos simples de deducción, III
•
•
•
•
~Pv~Q
~~(~Pv~Q)
[Doble negación 2]
~(~~P^~~Q)
[De Morgan 2]
~(P^~~Q)
[Doble negación 1]
~(P^Q)
[Doble negación 1]
~Pv~Q  ~(P^Q)
~Pv~Q~(P^Q) es una tautología
Observación: P y Q se pueden sustituir por
fórmulas cualesquiera.
La regla ~v~  ~(^) se puede incluir como
regla de deducción para completar el sistema
utilizado.
Ejemplos simples de deducción, III
PQ
~PvQ
[Equiv. Impl. Disy. 2]
Qv~P
[Conmut. Disy.]
~~Qv~P
[Doble negación 2]
~Q~P
[Equiv. Impl. Disy. 1]
• P y Q se pueden sustituir por fórmulas
cualesquiera.
Ejemplos simples de deducción, IV
• P  P v Q
P
/***** Por reducción al absurdo: *****/
/***** ~(P v Q)  ~P ^ ~Q  ~P *****/
/***** Contradicción!
*****/
~(P v Q)~P
[Deducc. Impl. Inferencia]
PP v Q
[Ejemplo anterior]
PvQ
[Modus ponens]
• En lugar de comentario se ponen corchetes
• P y Q se pueden sustituir …
• La regla    v  se puede incluir …
Deducción:
Representación intuitiva, II
• Contiene a todas las tautologías
• Forman un conjunto radial (si contiene un
punto, contienen todo su radio) y conexo
(si contiene dos radios, contiene todos los
intermedios)
• Si contiene dos radios opuestos, contiene
todas las fórmulas (consecuencia de que
F^~F  G)
• Si contiene una fórmula insatisfactible,
contiene todas las fórmulas (consecuencia
de lo anterior)
Ejemplo de demostración
• (p(qr))((pq)(pr))
• Estrategia: demostrar implicación
mediante deducción
[
p(qr)
[
pq
[
p
pq
q
p(qr)
qr
r]
pr]
(pq)(pr)]
(p(qr))((pq)(pr))
• P y Q se pueden sustituir …
Ejemplo de demostración, II
• (pq)((qr)(pr))
• Demostrar implicación mediante deducción
[ p q
q
[
q r
q r
p q
r]
[
p
pr]
p q
(qr)(pr)]
(pq)((qr)(pr))
• P y Q se pueden sustituir …
Ejemplo de demostración, III
• (pq)v(rp)
[ ~(pq)
~(~p v q)
~~p ^ ~q
p^~q
p
…
pv~r
…
rp]
~(pq)(rp)
(pq)v(rp)
• P y Q se pueden sustituir …
Ejemplo de demostración, IV
• ((PQ)^(~PQ))Q
[
(PQ)^(~PQ)
[
~Q // red. abs.
PQ
P // (sim)
~PQ
Q] // (sim) !!!
~Q~P
~QQ
~QP
Q] // Ver prox ej.
((PQ)^(~PQ))Q
• P y Q se pueden sustituir …
Ejemplo de demostración, V
• P v P  P
PvP
~~(P v P)
~(~P ^~P)
[ ~P
// Reducción al absurdo
~P^~P]
// Contradicción
~P~P^~P
~(~P^~P)~~P
~~P
P
• P se puede sustituir …
• La regla  v    se puede incluir …
Ejemplo de demostración, VI
• P^~PQ
P^~P
P
~P
[ ~Q // Reducción al absurdo
~P] // Contradicción
~Q~P
PQ
Q
• P y Q se pueden sustituir …
• La regla ^~  se puede añadir …
EJERCICIOS OBLIGATORIOS
1. [LL] Damos por válidos los siguientes hechos:
– Si hace calor y está húmedo, entonces está lloviendo
– Si está húmedo, entonces hace calor
– Está húmedo
Deducir a partir de lo anterior que está lloviendo
2. Demostrar la validez de lo siguiente:
• [PR1] P v (P ^ Q)  P
• [PR2] ~(PQ)  (P^~Q)
• [PR3]((X^Y)Z)(X(YZ))
• [PR4]((PQ)^(QR))(PR)
• [PR5] (P v Q) ^ (~Q v R)  (P v R)
Ejercicios Opcionales
• [PROGD1] Escribir un programa que hace
deducciones lógicas a partir de un
conjunto de axiomas.
• [PROGD2] Escribir un programa que
permite al usuario construir paso a paso
deducciones lógicas a partir de un
conjunto de axiomas.
Ejercicio obligatorio
• [OBJSD] Suponiendo que tres objetos A,
B y C están coloreados en blanco y negro
de manera que A y B no tengan el mismo
color, B y C tampoco y A y C tampoco,
deducir de ello una contradicción
Ejercicios obligatorios
• [TD] Demostrar mediante una deducción
que
((P  (Q v R)) ^ ~(Q v R))  ￢ P
es una tautología
• [CD] Deducir una contradicción a partir de
((P v Q)  ~R) ^ (~R v (Q v P))
Ejercicio opcional
• [LLD] Deducir que si llueve entonces la
presión cambia a partir de los axiomas
siguientes:
– Si la temperatura y la presión no cambian, no
llueve
– La temperatura no cambia
Ejercicio opcional
• [FOTOD] Deducir que la foto es de Juan a partir
de los siguientes axiomas:
–
–
–
–
–
La foto es redonda o cuadrada
La foto es en color o en blanco y negro
Si la foto es cuadrada, entonces es en blanco y negro
Si la foto es redonda, entonces es digital y en color
Si la foto es digital o en blanco y negro, entonces es
un retrato
– Si la foto es un retrato entonces es de Juan
Ejercicio opcional
• [UNICD] Suponemos los siguientes
axiomas acerca del unicornio :
– Si es mítico, entonces es inmortal
– Si no es mítico, es un mamífero mortal
– Si es inmortal o mamífero, entonces tiene
cuernos
– Si tiene cuernos es mágico
• Se deduce de todo ello que es mítico?
Que es mágico? Que tiene cuernos?
Ejercicio opcional
• [GRD1] Demostrar mediante una
deducción quiénes dicen la verdad y
quiénes dicen la mentira sabiendo que:
– Alceo dice “los únicos que decimos la verdad
aquí somos Cátulo y yo”
– Safo dice “Cátulo miente”
– Cátulo dice “Safo dice la verdad, o Alceo
miente”
Ejercicio opcional
• [GRD2] Demostrar mediante una
deducción quiénes dicen la verdad y
quiénes dicen la mentira sabiendo que:
– Anaximandro dice “Heráclito miente”
– Parménides dice “Anaximandro y Heráclito no
mienten”
– Heráclito dice “Parménides no miente”
Observaciones, I
• En general, en la Lógica Proposicional, en
toda tautología se puede sustituir
cualquier variable proposicional por una
fórmula arbitraria, siempre y cuando la
sustitución se haga en todas partes, y el
resultado de la sustitución es otra
tautología.
Observaciones, II
• En lo que queda de curso,
constantemente haremos razonamientos
informales acerca de la forma en que se
hacen deducciones formales. Parte de
estos razonamientos informales se podrán
formalizar mediante deducciones, pero
siempre habrá dos niveles de deducción
presentes, uno de los cuales se refiere al
otro.
Teorema de coherencia de la lógica
proposicional
• Teorema de coherencia: Si una fórmula F
se deduce a partir de un conjunto A de
axiomas, entonces es consecuencia de A.
• Demostración:
Es una consecuencia obvia del hecho de
que todas las reglas, que tienen la forma
AF, verifican que AF.
Recordatorio: Consecuencias:
Representación intuitiva

Teorema de coherencia:
Representación intuitiva

Teorema de completitud de la Lógica
Proposicional
• Teorema de completitud: Si una fórmula F
es consecuencia de un conjunto A de
axiomas, entonces se deduce de A.
• La demostración se dará más adelante.
Se demostrarán como pasos intermedios
dos casos particulares.
Recordatorio: Consecuencias:
Caso especial
• Las consecuencias incluyen fórmulas
insatisfactibles

Calculo proposicional:
Consistencia
• Definición: Un conjunto de proposiciones es
consistente si de él no se deduce ninguna
proposición contradictoria de la forma F^~F.
• Por ejemplo, {PQ, P^~Q} es inconsistente.
• A es inconsistente si y sólo si todas las proposiciones lógicas se deducen a partir de A.
Demostración: Suponemos A  F^~F.
Según el ejemplo VI de demostración que
hemos visto, dada cualquier proposición G,
F^~FG. Por lo tanto, AG.
Consistencia:
Representación intuitiva
• Caso en que las formulas deducidas no
incluyen contradicciones

Inconsistencia:
Representación intuitiva
• Caso en que las formulas deducidas
incluyen contradicciones

Caso particular obvio del
Teorema de Completitud
• Si un conjunto de axiomas es
inconsistente, entonces todas sus
consecuencias se deducen de él
• Demostración:
Todas las fórmulas se deducen de él
Teorema De Completitud:
Segundo caso a estudiar
• Si un conjunto de axiomas es consistente
maximal, entonces todas sus
consecuencias se deducen de él.
• Demostración (pendiente): Es un conjunto
satisfactible maximal, por lo que todas sus
consecuencias pertenecen a él.
Teorema De Completitud:
Segundo caso a estudiar, II
• Todo conjunto de fórmulas consistente
maximal es el conjunto de fórmulas ciertas
en una interpretación
• Demostración: La interpretación tiene que
ser I(F)  FA
Tenemos que ver que
– I(~F)  ~I(F)
– I(F^G)  I(F)^I(G)
Teorema De Completitud:
Segundo caso a estudiar, III
• I(~F)=~I(F)

FA  ~FA
– Como A es consistente, FA  ~FA
– FA  A~F (si no, A no sería maximal) 
 A{~F} consistente
 ~FA.
• I(F^G)=I(F)^J(G)
 F^GA  FA ^ GA
– F^GA  FA
(si no, A no sería maximal, pues F^GF)
– FA, GA  F^GA
(si no, A no sería maximal, pues F, GF^G)
Teorema De Completitud:
Caso general
• Si un conjunto de axiomas es consistente,
entonces todas sus consecuencias se
deducen de él.
• Demostración: Si F no se deduce de A,
A{~F} es consistente (pendiente de ver),
por lo que A{~F} está contenido en un
conjunto consistente maximal (pendiente
de ver) y entonces hay una interpretación
en la que todas las fórmulas de A son
ciertas y F es falsa
Teorema De Completitud:
Final de la demostración, I
• Si la fórmula F no se deduce de un
conjunto A de axiomas, entonces A{~F}
es consistente
• Demostración: Si A{~F} fuera
inconsistente, entonces
A{~F}  Gv~G  F
luego tendríamos que A  ~FF  F
Teorema De Completitud:
Final de la demostración
• Si A es consistente, entonces está
contenido en un conjunto satisfactible
maximal de proposiciones.
Demostración: Si {Fj | j0} es una
numeración de todas las proposiciones, se
van añadiendo a A consecutivamente Fj o
~Fj si con ello sigue siendo consistente
(con uno de ellos lo es por la consistencia
del conjunto previo y por la consideración
anterior). El conjunto resultante es
consistente maximal.
Consecuencia:
Teorema de satisfactibilidad
• Teorema: Todo conjunto consistente de
fórmulas A es satisfactible
• Demostración: Si A es un conjunto
consistente maximal ya lo hemos
demostrado. Si no lo es, está contenido en
otro conjunto M que sí es consistente
maximal. Entonces la interpretación que
satisface M también satisface A.
Relación entre los Teoremas de
completitud y satisfactibilidad
• Enunciados equivalentes del Teorema de
satisfactibilidad:
– Si A es insatisfactible, entonces es
inconsistente
– Si A tiene como consecuencia alguna
contradicción, ésta se deduce a partir de A
Hipótesis necesarias en el
teorema de Completitud
• Las propiedades del sistema formal de
deducción utilizadas en la demostración del
Teorema de Completitud son las siguientes:
–
–
–
–
–
–
–
F^~F  G
F, G  F^G; F^G  F; F^G  G
((A, F)  G)  (A  (FG))
(~FF)  F
F v G  ~(~F^~G)
F  F v G; G  F v G
F, FG  G
• Cualquier sistema formal deductivo que cumpla
estas condiciones puede sustituir al que hemos
utilizado.
Lógica proposicional:
Cálculo frente a satisfactibilidad
• En la práctica, la determinación de teoremas en
base a un cálculo lógico como el descrito es un
problema de búsqueda en un árbol, por lo que
puede ser más ineficiente que en base al
cálculo directo de todas las interpretaciones
posibles y la interpretación correspondiente del
supuesto teorema.
• En la lógica de predicados no se pueden utilizar
tablas de verdad y habrá que recurrir a un
cálculo lógico del tipo del anterior.