Lógica proposicional.

L´gica Proposicional
o
IIC2212

IIC2212

–

L´gica Proposicional
o

1 / 56

Inicio de la L´gica
o

Originalmente, la L´gica trataba con argumentos en el lenguaje
o
natural.

Ejemplo
¿Es el siguiente argumento v´lido?
a
Todos los hombres son mortales.
S´crates es hombre.
o
Por lo tanto, S´crates es mortal.
o

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

IIC2212

–

L´gica Proposicional
o

2 / 56

Inicio de la L´gica
o

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

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

IIC2212

–

L´gica Proposicional
o

3 / 56

Inicio de la L´gica
o

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

IIC2212

–

L´gica Proposicional
o

4 / 56

Paradojas en el lenguaje natural

Un d´ de la pr´ximasemana les voy a hacer una interrogaci´n,
ıa
o
o
y les aseguro que el d´ que se las haga van a estar sorprendidos.
ıa

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

IIC2212

–

L´gica Proposicional
o

5 / 56

Matem´tica en el lenguaje natural: Paradoja de Berry
a

Podemos representar los n´meros naturales usando oraciones del
u
lenguaje natural: “Mil quinientos veinte”, “elprimer n´mero”, ...
u
El n´mero de palabras en el Diccionario de la Real Academia es
u
finito.
El n´mero de oraciones con a los m´s 50 palabras tambi´n es finito.
u
a
e

IIC2212

–

L´gica Proposicional
o

6 / 56

Matem´tica en el lenguaje natural: Paradoja de Berry
a

Sea B el siguiente n´mero natural:
u
El primer n´mero natural que no puede ser definido por una
u
oraci´ncon a lo m´s cincuenta palabras tomadas del Diccionao
a
rio de la Real Academia.

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

IIC2212

–

L´gica Proposicional
o

7 / 56

M´s paradojas: Russell (1902)
a

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

IIC2212

–

L´gica Proposicional
o

8 / 56

M´s paradojas: Russell (1902)
a
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´n, U ∈ U si y s´lo si U ∈ U. ¡Tenemosuna
o
o
contradicci´n!
o
¿C´mo definimos la noci´n de conjunto?
o
o

IIC2212

–

L´gica Proposicional
o

9 / 56

¿Por qu´ necesitamos la L´gica?
e
o

Necesitamos un lenguaje con una sintaxis precisa y una sem´ntica
a
bien definida.
Queremos usar este lenguaje en matem´ticas.
a
- Definici´n de objetos matem´ticos: conjunto, n´meros naturales,
o
a
u
n´meros reales.
u- Definici´n de teor´ matem´ticas: teor´ de conjuntos, teor´ de los
o
ıas
a
ıa
ıa
n´mero naturales.
u
- Definici´n del concepto de demostraci´n.
o
o

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

IIC2212

–

L´gica Proposicional
o

10 / 56

¿Por qu´ necesitamos la L´gica en computaci´n?
e
o
o
Algunas aplicaciones:
- Bases de datos: Lenguajes deconsulta, lenguajes para restricciones
de integridad.
- Inteligencia artificial: Representaci´n de conocimiento, razonamiento
o
con sentido com´n.
u
- Ingenier´ de software: Especificaci´n de sistemas (lenguaje Z ),
ıa
o
verificaci´n de propiedades.
o
- Teor´ de la computaci´n: complejidad descriptiva, algoritmos de
ıa
o
aproximaci´n.
o
- Criptograf´ verificaci´n de protocolos...