L GicaProposicional

L´ogica Proposicional
IIC2212

IIC2212

–

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´ı.

IIC2212

–

L´
ogica Proposicional2 / 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.

IIC2212

–

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.
Creo queS´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?

IIC2212

–

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 estar sorprendidos.

¿Qu´ed´ıa voy a hacer la interrogaci´
on?

IIC2212

–

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 50 palabrastambi´en es finito.

IIC2212

–

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?IIC2212

–

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.

IIC2212

–

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?

IIC2212

–

L´
ogica Proposicional

9 / 56

¿Por qu´e necesitamos la L´ogica?

Necesitamos un lenguaje con una sintaxis precisa y una sem´antica
bien definida.
Queremosusar 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?

IIC2212

–

L´
ogica Proposicional

10 / 56

¿Por qu´e necesitamosla 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: complejidad descriptiva, algoritmosde
aproximaci´on.
- Criptograf´ıa: verificaci´
on de protocolos criptogr´aficos.
- Procesamiento de lenguaje natural.
- ...

IIC2212

–

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 proposicional representa...