Logica

Inicio de la L´ogica
Originalmente, la L´ogica trataba con argumentos en el lenguage
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´ı.

1

Inicio de la L´ogica

Otro ejemplo: ¿Qu´e pasa con el siguiente caso?
Algunas personas son mujeres.
S´ocrateses una persona.
Por lo tanto, S´ocrates es mujer.
En este caso deber´ıamos decir que el argumento no es v´alido.

2

Inicio de la L´ogica
Pero los argumentos pueden ser m´as complejos ...
Creo que todos los hombres son mortales.
Creo que 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 reemplazamoscreo que por no
se si?

3

Paradojas en el lenguage 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´e d´ıa voy a hacer la interrogaci´on?

4

Matem´atica en el lenguage natural: Paradoja de Berry

Podemos representar los n´
umeros naturales usando oraciones del
lenguage natural: “Mil quinientosveinte”, “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 palabras tambi´en es finito.

5

Matem´atica en el lenguage 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 delDiccionario
de la Real Academia.
B est´a bien definido, pero con s´olo 25 palabras. ¡Tenemos una
contradicci´
on!
¿Qu´e pas´o?

6

M´as paradojas: Russell (1902)

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

7

M´as paradojas: Russell (1902)

Sea C el conjunto de todos los conjuntos que tienen a lo menosdos
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?
8

¿Por qu´e necesitamos la L´ogica?

Necesitamos un lenguage con una sintaxis precisa y una sem´antica
bien definida.
Queremosusar este lenguage 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 lenguage en computaci´on. ¿Por qu´e?
9

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

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 una proposici´on completa
e indivisible, que puede ser verdadera o falsa.Ejemplo:
P = {socrates es hombre, socrates es mortal}.
11

L´ogica Proposicional: Sintaxis
Conectivos l´ogicos son usados para construir expresiones que
tambi´en pueden ser verdaderas o falsas.
Ejemplos:
socrates es hombre

→ socrates es mortal

socrates es hombre

→ (¬ socrates es mortal)

S´ımbolos de puntuaci´on son usados para evitar ambig¨
uedades.

12

Sintaxis de la L´ogica Proposicional:...