Lp 6

L´ogica Proposicional
IIC2213

IIC2213

–

L´
ogica Proposicional

1 / 56

Inicio de la L´ogica
Originalmente, la L´ogica trataba con argumentos en el lenguaje
natural.

Ejemplo
¿Es el siguiente argumento v´
alido?
Todos los hombres son mortales.
S´
ocrates es hombre.
Por lo tanto, S´
ocrates es mortal.

La l´
ogica deber´ıa poder usarse para demostrar que s´ı.

IIC2213

–

L´
ogicaProposicional

2 / 56

Inicio de la L´ogica

Ejemplo
¿Qu´e pasa con el siguiente caso?
Algunas personas son mujeres.
S´
ocrates es una persona.
Por lo tanto, S´
ocrates es mujer.

En este caso deber´ıamos decir que el argumento no es v´alido.

IIC2213

–

L´
ogica Proposicional

3 / 56

Inicio de la L´ogica

Pero los argumentos pueden ser m´
as complejos ...
Creo que todos los hombres son mortales.
Creoque S´
ocrates es hombre.
Por lo tanto, creo que S´
ocrates es mortal.
¿Es este argumento v´alido? ¿Por qu´e?
¿Qu´e significa creo? ¿Qu´e pasar´ıa si reemplazamos creo que por no
se si?

IIC2213

–

L´
ogica Proposicional

4 / 56

Paradojas en el lenguaje natural

Un d´ıa de la pr´
oxima semana les voy a hacer una interrogaci´
on,
y les aseguro que el d´ıa que se las haga van a estarsorprendidos.

¿Qu´e d´ıa voy a hacer la interrogaci´
on?

IIC2213

–

L´
ogica Proposicional

5 / 56

Matem´atica en el lenguaje natural: Paradoja de Berry

Podemos representar los n´
umeros naturales usando oraciones del
lenguaje natural: “Mil quinientos veinte”, “el primer n´
umero”, ...
El n´
umero de palabras en el Diccionario de la Real Academia es
finito.
El n´
umero de oraciones con a los m´
as 50palabras tambi´en es finito.

IIC2213

–

L´
ogica Proposicional

6 / 56

Matem´atica en el lenguaje natural: Paradoja de Berry

Sea B el siguiente n´
umero natural:
El primer n´
umero natural que no puede ser definido por una
oraci´
on con a lo m´as cincuenta palabras tomadas del Diccionario de la Real Academia.

B est´a bien definido, pero con s´
olo 25 palabras. ¡Tenemos una
contradicci´
on!¿Qu´e pas´
o?

IIC2213

–

L´
ogica Proposicional

7 / 56

M´as paradojas: Russell (1902)

Tambi´en pueden aparecer paradojas usando lenguaje matem´
atico.
Sea A = {1, 2, 3}
¿A ∈ A? No.
Sea B = {{1, 2, 3}, {4, 5}}
¿A ∈ B? S´ı.
¿B ∈ B? No.

IIC2213

–

L´
ogica Proposicional

8 / 56

M´as paradojas: Russell (1902)
Sea C el conjunto de todos los conjuntos que tienen a lo menos
dos elementos: C ={A, B, . . .}
¿C ∈ C ? S´ı.
Entonces podemos definir el siguiente conjunto: U = {X | X ∈ X }.
Tenemos: A ∈ U, B ∈ U, C ∈ U.
¿U ∈ U? Por definici´
on, U ∈ U si y s´
olo si U ∈ U. ¡Tenemos una
contradicci´
on!
¿C´
omo definimos la noci´
on de conjunto?

IIC2213

–

L´
ogica Proposicional

9 / 56

¿Por qu´e necesitamos la L´ogica?

Necesitamos un lenguaje con una sintaxis precisa y una sem´anticabien definida.
Queremos usar este lenguaje en matem´
aticas.
- Definici´
on de objetos matem´aticos: conjunto, n´
umeros naturales,
n´
umeros reales.
- Definici´
on de teor´ıas matem´aticas: teor´ıa de conjuntos, teor´ıa de los
n´
umero naturales.
- Definici´
on del concepto de demostraci´
on.

Tambi´en queremos usar este lenguaje en computaci´on. ¿Por qu´e?

IIC2213

–

L´
ogica Proposicional

10 /56

¿Por qu´e necesitamos la L´ogica en computaci´on?
Algunas aplicaciones:
- Bases de datos: Lenguajes de consulta, lenguajes para restricciones
de integridad.
- Inteligencia artificial: Representaci´on de conocimiento, razonamiento
con sentido com´un.
- Ingenier´ıa de software: Especificaci´on de sistemas (lenguaje Z ),
verificaci´
on de propiedades.
- Teor´ıa de la computaci´on: complejidaddescriptiva, algoritmos de
aproximaci´
on.
- Criptograf´ıa: verificaci´
on de protocolos criptogr´aficos.
- Procesamiento de lenguaje natural.
- ...

IIC2213

–

L´
ogica Proposicional

11 / 56

L´ogica Proposicional: Sintaxis
Tenemos los siguientes elementos:
- Variables proposicionales (P): p, q, r , . . .
- Conectivos l´ogicos: ¬, ∨, ∧, →, ↔
- S´ımbolos de puntuaci´on: (, )

Cada variable...