Download Logica

lógica proposicional
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
CONTENIDO
Fórmulas y su semántica [H6.2].
Funciones de verdad [H6.2]. Formas
normales [H6.2]. Razonamiento formal:
reglas de inferencia, pruebas, sistemas
axiomáticos [H6.3]. Completitud y
sensatez [H6.2].
HEIN, JAMES. Discrete Structures,
Logic and Computability. Jones and
Bartlett Publishers. 1995 - 2001
conceptos básicos:
la lógica
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
§ La lógica es la disciplina que trata con métodos
de razonamiento.
§ La lógica provee reglas y técnicas para
determinar si un argumento dado es válido .
Augustus De Morgan
(1806-1871)
George Boole
(1815-1864)
conceptos básicos:
la lógica
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
§ Pregunta:
¿Qué relación existe entre la lógica y la
computación?
mecanizar tareas complejas.
n verificación de programas ( ¿coincide lo que se
cree que hace el programa y lo que realmente
hace?).
n los ordenadores lo constituyen circuitos
lógicos.
n la lógica formal puede considerarse como una
especie de lenguaje de programación.
n
¿cómo razonamos?
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
¿Cómo razonamos en nuestras vidas
cotidianas?
§ Declaramos hechos y luego declaramos
conclusiones en base a esos hechos.
§ Utilizamos palabras o frases de la
siguiente lista para indicar que se realiza
cierta conclusión:
por lo tanto
entonces
de esto se concluye que
de esto sigue que
…
¿cómo razonamos?
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
La regla de inferencia más común se
denomina modus ponens y funciona de
la siguiente manera:
§ Supongamos A y B son sentencias y
asumamos que
A entonces B es verdadera y
A es verdadera
§ Entonces podemos concluir
B es verdadera
¿cómo razonamos?
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
Ejemplo típico de inferencia por modus
ponens:
Si llueve entonces hay nubes en el cielo
Llueve
Por lo tanto hay nubes en el cielo
¿Cómo se aprende la regla de modus
ponens?
Probablemente
durante la infancia
¿cómo razonamos?
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
Otra regla que se aprende durante la
infancia es llamada modus tollens y
funciona de la siguiente manera:
§ Supongamos A y B son sentencias y
asumamos que
A entonces B es verdadera y
B es falsa
§ Entonces podemos concluir
A es falsa
¿cómo razonamos?
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
Falacias lógicas
Non sequitur: no se sigue
Ío es la luna de Júpiter
Titán es la luna de Saturno
La Tierra es el tercer planeta más cercano al sol
Si un objeto es de oro, brilla.
Esta daga brilla.
Esta daga es de oro.
Si es Bahiense es Argentino
No es Bahiense
No es Argentino
cálculo proposicional
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
Una oración que es verdadera o falsa se
denomina proposición:
Ejemplos
§ El verano comienza en junio en el
hemisferio Sur.
§ 2+2=4.
§ Si llueve, entonces hay nubes en el cielo.
§ Puedo ir o no ir al cine esta noche.
§ Todos los enteros son pares.
§ Existe un número primo mayor que 10 100
(googol).
cálculo proposicional
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
Conectivos lógicos
§ ┐ (o ’) negación
§ Λ conjunción
§ V disyunción
§ → implicación
Otros conectivos se
introducen para
simplificar notación
ej: ↔ equivalencia
A
B
┐A
AΛB
AVB
A→B
V
V
F
V
V
V
V
F
F
V
F
F
V
F
V
V
F
F
F
F
V
V
sintaxis vs. semántica
LENGUAJES
FORMALES
Y
AUTÓMATAS
Sintaxis:
§ ¿Es esta sentencia gramaticalmente
correcta?
lógica
proposicional
Semántica
§ ¿Cuál es el significado de la siguiente
expresión?
sintaxis
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
Conjunto de símbolos:
§ Símbolos de verdad: v, f
§ Conectivos : Λ,V,→,┐
§ Variables Proposicionales: P, Q, R
§ Símbolos de puntuación: ( , )
sintaxis
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
Definición informal de fórmula bien
formada (fbf)
Una fórmula bien formada es
§ un símbolo de verdad
§ una letra proposicional
§ la negación de una fbf
§ la conjunción de dos fbf
§ la disyunción de dos fbf
§ la implicación de una fbf a otra fbf
§ una fbf rodeada de paréntesis
sintaxis
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
Ejemplos de fbf:
verdadero, falso, P, ┐Q, P ΛQ, P→Q,
(PVQ) ΛR, PΛQ → R
Ejercicios
§ Dar una gramática BNF para las fbf del
cálculo proposicional.
§ Mostrar que PΛQVR es una fbf.
§ Mostrar que P→QV(RΛ┐Q) es una fbf.
sintaxis
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
¿Es posible asociar una tabla de verdad
a cada fbf?
Sí, pero antes debemos establecer una
jerarquía de precedencia para los
conectivos:
┐
(mayor precedencia, aplicar primero)
Λ
V
→ (menor precedencia, aplicar último)
Además Λ, V y → son asociativos a
izquierda
Notar analogía con expresiones aritméticas
sintaxis
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
PVQΛR
significa
P V (Q Λ R)
P→Q→R
significa
(P → Q) → R
┐P V Q
significa
(┐P) V Q
┐P → P Λ Q V R
significa
(┐P) → ((P Λ Q) V R)
┐┐P
┐ (┐ P)
significa
Toda fbf tiene un árbol de sintaxis natural que muestra
claramente la jerarquía de los conectivos.
Λ
Ejemplo:
V
P
P Λ (Q V
┐
R)
Q
┐
R
árbol sintáctico
mostrando jerarquía
de conectivos
semántica
A continuación planteamos algunos
ejercicios para repasar el concepto de tablas
de verdad.
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
Ejercicio
n
n
Asumamos que P→Q es falso
¿Cuáles son los posibles valores de verdad
para las siguientes fbf?
§ PVQ
§ ┐P → Q Λ R
¿Y si asumimos P→Q es verdadero?
¿Qué valores de verdad deben tener P, Q,
R, S y T para que la siguiente fbf sea falsa?
( P ΛQ ) Λ R ® ( S V T )
semántica
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
Tautologías, Contradicciones y
Contingencias
§ Una fbf cuyos valores de verdad son
siempre verdaderos (v) es llamada
tautología.
§ Una fbf cuyos valores de verdad son
siempre falsos (f) es llamada
contradicción.
§ Una fbf cuyos valores de verdad son a
veces v y otras f es llamada
contingencia.
semántica
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
Dos fbf son equivalentes si tienen la misma
tabla de verdad.
Se nota A ↔ B o A≡B
Ya vimos algunos ejemplos. Repasémoslos y
veamos algunos nuevos.
Algunas equivalencias básicas
Negación Disyunción Conjunción
┐┐A ≡ A
AVv≡v
AΛv ≡A
AVf ≡A
AΛf ≡f
AV A≡ A
AΛA ≡ A
A V ┐A ≡ v A Λ ┐A ≡ f
Implicación
A→ v≡v
A → f ≡ ┐A
v →A≡A
f → ┐A ≡ v
A→A≡v
semántica
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
Algunas conversiones
A→B≡ ┐ A VB
┐(A→B) ≡AΛ┐B
A→B ≡ AΛ┐B → f
AVB≡BVA
A Λ B≡ B Λ A
(A V B) V C ≡ A V (B V C)
(A Λ B) Λ C ≡ A Λ (B Λ C)
A Λ (B V C) ≡ (A Λ B) V (A Λ C)
A V (B Λ C) ≡ (A V B) Λ (A V C)
semántica
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
Leyes de absorción
A Λ (AVB)≡ A
A V (AΛB)≡ A
A Λ (┐AVB)≡ AΛB
A V (┐AΛB)≡ A VB
Leyes de De Morgan
┐(AΛB)≡ ┐ A
V┐B
┐(AVB)≡ ┐ A Λ ┐ B
semántica
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
Propiedades de la equivalencia:
n ≡ es una relación de equivalencia.
n Cualquier sub-fbf de una fbf puede ser
reemplazada por una fbf equivalente
sin cambiar el valor de verdad de la fbf
original.
funciones booleanas
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
¿Que otros conectivos unarios existen
además de ‘Ø’?
P
g1(P)
P
g2(P)
P
g3(P)
P
g4(P)
v
f
v
v
v
f
v
f
v
f
f
v
f
f
f
¿Cuántos
conectivos
binarios diferentes
podríamos definir?
En general
podemos
n
2
definir 2 conectivos
n-arios
v
P Q
g(P,Q)
v
v
v/f
v
f
v/f
f
v
v/f
f
f
v/f
forma normal disyuntiva
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
Expresando otros conectivos en términos de
Λ,V y Ø
P Q
g(P,Q)
paso 1:
v
v
f
v
f
v
Þ PÙØQ
f
v
v
Þ ØPÙQ
f
f
f
paso 2:
Þ (PÙØQ) Ú (ØPÙQ)
Toda fbf es equivalente a una forma normal
disyuntiva (FND)
forma normal conjuntiva
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
De manera análoga
P Q
g(P,Q)
v
v
f
v
f
v
f
v
v
f
f
f
paso 1:
paso 2:
Þ ØP Ú ØQ
Þ (ØP Ú ØQ ) Ù (P Ú Q)
ÞPÚQ
Toda fbf es equivalente a una forma
normal conjuntiva (FNC)
conjunto completo de conectivos
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
Dado que se puede expresar cualquier
función de verdad utilizando sólo ‘Ù’,
‘Ú’, e ‘Ø’, decimos que el conjunto de
operadores {Ø, Ù, Ú} es completo.
Recordemos las leyes de De Morgan:
Ø(P Ù Q) ≡ ØP Ú ØQ
Ø(P Ú Q) ≡ ØP Ù ØQ
Por la propiedad de substitución, dado
que {Ø, Ù, Ú} es un conjunto completo,
de conectivos también lo son los
conjuntos {Ø, Ù} y {Ø, Ú}
un poco de terminología
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
n
Un literal es una letra proposicional o su negación
Ejemplos: P, Q, ØP, ØQ
n
Una conjunción fundamental es un literal o una
conjunción de dos o más literales
Ejemplos: P, PÙØQ
n
Una forma normal disyuntiva (FND) es
§ una conjunción fundamental, o
§ la disyunción de una o más conjunciones
fundamentales
Ejemplos:
P Ú (ØPÙQ)
(P ÙQ) Ú (ØQ ÙP)
(P ÙQ ÙR) Ú (Ø P ÙQ ÙR)
P
ØP
PÚØP
Ø P ÙQ
seguimos con funciones de verdad y formas normales …
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
Previamente presentamos un método
que permite obtener la FND y la FNC
para cualquier función de verdad.
Pregunta:
¿Qué ocurre cuando queremos obtener
la FND (FNC) a partir de una tabla que
no tiene ningún valor verdadero
(falso)?
P Ù Ø P ≡ falso
P Ú Ø P ≡ verdadero
dos maneras para obtener FND
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
Podemos construir
una FND para
cualquier función de
verdad utilizando el
método visto en la
clase previa
Otra manera es
mediante el uso de
equivalencias que
permiten transformar
una fbf en una fbf en
FND
P Q g(P,Q)
v
v
f
f
v
f
v
f
paso 1:
paso 2:
f
v Þ PÙØQ
Þ (PÙØQ) Ú (ØPÙQ)
v Þ ØPÙQ
f
¿Existe un método
automático para
tal fin?
método para transformar una fbf a FND
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
1.
2.
Remover todas las apariciones del
conectivo →
A→B≡ Ø A VB
Llevar las negaciones hacia adentro para
crear literales utilizando leyes de De
Morgan
1.
2.
3.
Ø(A Ù B) ≡ ØA Ú ØB
Ø(A Ú B) ≡ ØA Ù ØB
Aplicar las leyes distributivas para obtener
una FND
A Ù (B Ú C) ≡ (A Ù B) Ú (A Ù C)
A Ú (B Ù C) ≡ (A Ú B) Ù (A Ú C)
método para transformar una fbf a FND
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
Ejemplo
Escribir la siguiente fbf en FND
Ø((P Ú Q) Ù (Q → R))
Ø((P Ú Q) Ù (Q → R))
Ø (P Ú Q) Ú Ø (Q → R)
(Ø P Ù Ø Q) Ú Ø (Q → R)
(Ø P Ù Ø Q) Ú Ø (Ø Q Ú R)
(Ø P Ù Ø Q) Ú (Q Ù Ø R)
≡
≡ (De Morgan)
≡ (De Morgan)
≡ (implicación)
(De Morgan)
más terminología: el caso de FNC
LENGUAJES
FORMALES
Y
AUTÓMATAS
n
Una disyunción fundamental es un literal o
una disyunción de dos o más literales.
Ejemplos: P, P Ú ØQ
lógica
proposicional
n
Un forma normal conjuntiva (FNC) es una
disyunción fundamental o la conjunción de
dos o más disyunciones fundamentales.
Ejemplos: P Ù (ØP Ú Q),
(P Ú Q) Ù (ØQ Ú P)
(P Ú Q Ú R) Ù (Ø P Ú Q Ú R)
P
ØP
PÙØP
ØPÚQ
dos maneras para obtener FNC
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
De manera análoga a la FND, existen dos
maneras para obtener una FNC para
cualquier función de verdad
n Utilizando el
paso 2:
P Q g(P,Q) paso 1:
método de la
Þ ØP Ú ØQ
f
v v
tabla de verdad v f v
Þ (ØP Ú ØQ ) Ù (P Ú Q)
f v
v
visto en la
f f
f
ÞPÚQ
clase previa
n
Mediante el uso de equivalencias que
permiten transformar una fbf en una fbf en
FNC
formas completa
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
Supongamos que una fbf W tienen n letras
proposicionales diferentes. Una FND para W
se denomina forma norma disyuntiva
completa si cada conjunción fundamental
tiene exactamente n literales, uno para cada
una de las n letras que aparecen en W.
Ejemplo
§ (P Ù Q Ù R) Ú (Ø P Ù Q Ù R) es una FND
completa.
§ P Ú (Ø P Ù Q) es una FND pero no es una FND
completa.
La definición para forma norma conjuntiva
completa es análoga.
método para transformar una fbf a FND completa
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
Ejemplo
Escribir la siguiente fbf en FND completa
Ø((P Ú Q) Ù (Q → R))
Ø((P Ú Q) Ù (Q → R))
Ø (P Ú Q) Ú Ø(Q → R)
(ØP Ù Ø Q) Ú Ø (Q → R)
(ØP Ù Ø Q) Ú Ø (ØQ Ú R)
(ØP Ù Ø Q) Ú (Q Ù ØR)
≡
≡ (De Morgan)
≡ (De Morgan)
≡ (implicación)
(De Morgan)
La obtenida no es una forma completa.
Realizamos los siguientes pasos adicionales aplicando
equivalencias básicas y la ley distributiva:
(ØPÙØQ) Ú (Q Ù ØR) ≡
(ØPÙØQ) Ù (RÚØR ) Ú (QÙØR) Ù (PÚØP) ≡
(ØPÙØQÙR) Ú (ØPÙØQÙØR) Ú (PÙQÙØR) Ú (ØPÙQÙØR)
razonamiento formal
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
Las tablas de verdad son suficientes
para determinar si una fbf es
verdadera.
Sin embargo, construir una tabla de
verdad para una fbf con muchas
variables y conectivos puede volverse
una tarea muy compleja.
Alternativa: utilizar un sistema de
razonamiento formal.
reglas de inferencia
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
Regla de inferencia:
Patrón sintáctico que establece que a
partir de un conjunto de premisas
(hipótesis o antecedentes) podemos
derivar una conclusión.
P1
…
Pk
\C
“\” significa “por lo tanto”
reglas de inferencia
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
Queremos que nuestras reglas de
inferencia preserven la verdad.
Pregunta: ¿Cuándo podemos
asegurar que una regla de
inferencia preserva la verdad?
P1
…
Pk
\C
Cuando P1 Ù ... Ù Pk → C
es una tautología
(recordar definición de argumento
válido)
reglas de inferencia
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
Modus Ponens (MP)
A
A→B
\B
A
B
A→B
A Ù (A→B)
A Ù (A→B) → B
v
v
f
f
v
f
v
f
v
f
v
v
v
f
f
f
v
v
v
v
Cualquier tautología condicional de la forma P 1 Ù ... Ù
Pk → C puede ser usada como regla de inferencia.
Por ejemplo, la tautología
(A → B) Ù Ø B → Ø A
da lugar a la regla de
Modus tollens (MT)
ØB
A®B
\ØA
reglas de inferencia
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
Listemos otras reglas de inferencia
Regla de Conjunción (Conj.)
A,B .
\ AÙB
Regla de Simplificación (Simp.)
A Ù B.
\A
Regla de Adición (Ad.)
A
.
\ A ÚB
reglas de inferencia
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
Silogismo Disyuntivo (SD)
A Ú B, ØA .
\B
Silogismo Hipotético (SH)
A →B, B →C
\A→C
axioma
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
Un axioma es una fbf que queremos usar
como base a partir de la cual podremos
razonar.
Un axioma es usualmente una fbf que
conocemos como verdadera (por ejemplo,
luego de verificar su valor de verdad usando
una tabla de verdad).
Cuando la lógica es aplicada a cierto tema,
entonces un axioma podría ser algo que
“queremos que sea verdadero” (ejemplo,
“dos puntos determinan una única recta”).
prueba
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
Una prueba es una secuencia finita de
fbf con la propiedad de que cada fbf en
la secuencia es
n un axioma, o
n puede ser inferido de fbf previas en la
secuencia
La última fbf en la secuencia es llamada
teorema.
pruebas
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
Escribiremos las pruebas en forma de
tabla, donde cada línea está
numerada y contiene una fbf junto
con la razón por la cual fue incluida.
Prueba
1.
W 1 Razón para W1
2.
W 2 Razón para W2
M
n.
W n Razón para Wn
prueba condicional (PC)
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
1.
2.
3.
k.
A
B
C
P (premisa)
P
P
M
M
D
…
1,2,3,k,PC
k+1. A ÙB ÙC → D
prueba condicional
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
Ejemplo
Probar la siguiente sentencia
(A Ú B) Ù (A Ú C) Ù ØA → B ÙC
1.
2.
3.
4.
5.
6.
7.
AÚB
AÚC
ØA
B
C
BÙC
(A Ú B) Ù (A Ú C) Ù ØA → B ÙC
P
P
P
1,3,SD
2,3,SD
4,5,Conj
1,2,3,6,PC
prueba condicional: simplificaciones
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
Ejemplo
Probar la siguiente sentencia
((A Ú B) → (B ÙC)) → (B → C) Ú D
1. ((A Ú B) → (B ÙC))
P
2.
B
P – sub-prueba (B → C)
3.
AÚB
2,Ad.
4.
B ÙC
1,3,MP
5.
C
4,Simp.
6. B → C
2,5,PC – fin sub-prueba
7. (B → C) Ú D
6,Ad.
8. ((A Ú B) → (B ÙC)) → (B → C) Ú D 1,7,PC
Advertencia: no usar líneas de la sub-prueba
para inferir líneas que aparezcan luego de que la
sub-prueba haya finalizado
prueba condicional: simplificaciones
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
Ejemplo
Probar la siguiente sentencia
Ø(A Ù B) Ù (B Ú C) Ù (C → D) → (A → D)
1. Ø(A Ù B)
P
Nota: podemos
utilizar reglas de
2. B Ú C
P
equivalencia
3. C → D
P
4. ØA Ú ØB
1, Ø(A Ù B) ≡ ØA Ú ØB
5.
A
P
6.
ØB
4,5,SD
7.
C
2,6,SD
8.
D
3,7,MP
9. A → D
5,8,PC
10. Ø(AÙB)Ù(BÚC)Ù(C→D)→(A→D) 1,2,3,9,PC
prueba indirecta (PI)
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
1.
2.
3.
A
B
C
P
P
P
4.
ØD
P para PI
M
M
falso
…
1,2,3,4,k,PI
k.
k+1. A ÙB ÙC → D
prueba indirecta
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
Ejemplo
Probar la siguiente sentencia
(A Ú B) Ù ØA Ù (ØC → ØB) → C
1. A Ú B
P
2. ØA
P
3. ØC → ØB
P
4. ØC
P para PI
5. ØB
3,4,MP
6. A
1,5,SD
7. ØA Ù A
2,6,Conj
11. falso
7,ØAÙA ≡ falso
12.(A Ú B) Ù ØA Ù (ØC → ØB) → C
1,2,3,4,11,PI
pruebas
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
Ejercicio
Supongamos que tenemos las siguientes
premisas:
“No está soleado y no hace frío”
“Si no está soleado entonces no vamos a
nadar”
“Si no vamos a nadar entonces vamos al
cine”
“Si vamos al cine entonces regresamos a
casa tarde.”
Probar que las premisas anteriores implican
“Regresamos a casa tarde”
pruebas
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
Ejercicio:
Mostrar que los siguientes argumentos
son válidos:
§ “Pedro sacó dos A’s, pero si Pedro no
promocionó entonces Pedro no sacó dos A’s,
entonces Pedro promocionó”.
§ “Si el programa es eficiente, entonces ejecuta
rápidamente. O bien el programa es eficiente o
bien tiene un error. Sin embargo, el programa no
ejecuta rápidamente. Por lo tanto el programa
tiene un error”.
sensatez y completitud
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
Sensatez:
(correctitud/sanidad):
Queremos que todas
las pruebas de
teoremas devuelvan
tautologías.
tautologías
teoremas
tautologías
Completitud:
Queremos que todas
las tautologías puedan
ser probadas como
teoremas.
teoremas
sistema de Hilbert (similar al original)
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
Axiomas
1. A Ú A → A
2. A → A Ú B
3. A Ú B → B Ú A
4. (A → B) → (C Ú A → C Ú B)
5. A → B ≡ Ø A Ú B ≡ Ø (A Ù Ø B)
David Hilbert
(1862-1943)
Reglas
n Regla de inferencia Modus Ponens
(MP)
n Regla de Prueba Condicional (PC)
pruebas usando el sistema de Hilbert
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
Teorema 1: (A → B) Ù (B → C) → (A → C)
1. (A → B)
P
2. (B → C)
P
3.
A
P
4.
B
1,3,MP
5.
C
2,4,MP
6. A → C
3,5,PC
7. (A → B) Ù (B → C) → (A → C) 1,2,6,PC
Podemos usar teoremas previamente probados para
probar nuevos teoremas
Teorema 2: A → A
1. A → A Ú A
axioma 2
2. A Ú A → A
axioma 1
3. A → A
1,2, Teorema 1,MP
pruebas usando el sistema de Hilbert
LENGUAJES
FORMALES
Y
AUTÓMATAS
lógica
proposicional
Ejercicios
Dar una prueba para los siguientes
teoremas usando el sistema de Hilbert
Teorema 3:
Teorema 4:
Teorema 5:
Teorema 6:
Teorema 7:
ØAÚA
AÚØA
ØAÚØØA
A →Ø Ø A
Ø Ø A→ A