Ana
Aprobó: V
SECCIÓN 3 · ABRIR LAS AFIRMACIONES
De una letra a un mundo de objetos.
01La lógica proposicional trataba cada afirmación como un bloque.
02Ahora vamos a representar objetos, propiedades, relaciones y reglas generales.
S ⟶ Mortal(sócrates)
3.1 · QUÉ AGREGA
La propiedad se puede reutilizar.
01Mortal(sócrates): una propiedad aplicada a un objeto.
02Mortal(platón): la misma propiedad, otro objeto.
03∀x (Hombre(x) → Mortal(x)): una sola regla general.
3.2 · CONSTANTES Y VARIABLES
Nombrar un objeto o dejar un lugar abierto.
01Constantes: sócrates, ballena_azul, paciente_37.
02Variables: x, y, z recorren el dominio elegido.
03Mortal(x) tiene una variable libre: necesitamos asignarle un objeto o cuantificarla.
3.2 · PROPIEDADES Y RELACIONES
El orden de los argumentos importa.
01Mortal(sócrates): predicado de un argumento.
02Padre(juan, lucía): Juan es padre de Lucía.
03Padre(lucía, juan) afirma otra relación.
Padre(x, y) · x es padre de y
3.2 · FUNCIONES
Un objeto no es un valor de verdad.
01madre(juan) denota una persona: es un término.
02Madre(maría, juan) afirma una relación: puede ser V o F.
03Mortal(madre(juan)) aplica una propiedad al objeto devuelto.
3.2 · COMPROBAR LA DISTINCIÓN
¿Qué expresión denota un objeto?
3.3 · ANTES DE CUANTIFICAR
¿Todos los que están dónde?
01Fijamos un dominio no vacío: Ana, Bruno y Celia.
02En la demostración conocemos el valor de cada propiedad y relación.
03Un F es falso en este modelo completo; no significa simplemente «no lo sabemos».
3.3 · CUANTIFICADOR UNIVERSAL
¿Alcanza con que casi todos aprueben?
MODELO FINITO · ANA, BRUNO Y CELIAUn caso que no cumple
Bruno
Aprobó: F
Celia
Aprobó: V
∀x Aprobó(x)?
¿Cuánto vale ∀x Aprobó(x)?
Buscá un testigo o un contraejemplo antes de revelar.
Modelo completo: conocemos cada V y F. Este cálculo evalúa el modelo mostrado; no decide validez general.
3.3 · CUANTIFICADOR EXISTENCIAL
Un testigo alcanza.
MODELO FINITO · ANA, BRUNO Y CELIAUn caso que no cumple
Ana
Aprobó: V
Bruno
Aprobó: F
Celia
Aprobó: V
∃x Aprobó(x)?
¿Cuánto vale ∃x Aprobó(x)?
Buscá un testigo o un contraejemplo antes de revelar.
Modelo completo: conocemos cada V y F. Este cálculo evalúa el modelo mostrado; no decide validez general.
3.3 · ACOTAR UNA REGLA
Todos los hombres son mortales.
01∀x (Hombre(x) → Mortal(x)) habla de quienes cumplen Hombre.
02∀x Mortal(x) exige que todo objeto del dominio sea mortal.
03Un objeto que no cumple Hombre no refuta la primera regla.
3.3 · APLICAR UNA REGLA
La regla general llega al caso concreto.
01Regla: ∀x (Hombre(x) → Mortal(x)).
02Hecho: Hombre(sócrates).
03Instancia: Hombre(sócrates) → Mortal(sócrates).
∴ Mortal(sócrates)
3.3 · EXPRESAR EXISTENCIA
Algún paciente es alérgico.
01Buscamos un mismo objeto que cumpla ambas propiedades.
02∃x (Paciente(x) ∧ Alérgico(x)) exige un paciente alérgico.
03Usar → puede admitir un testigo que ni siquiera sea paciente.
3.3 · LABORATORIO DE TRADUCCIÓN
¿Un no paciente puede ser el testigo?
MODELO FINITO · ANA, BRUNO Y CELIASin pacientes alérgicos
Ana
Paciente: V
Alérgico: F
Bruno
Paciente: V
Alérgico: F
Celia
Paciente: F
Alérgico: F
∃x (Paciente(x) ∧ Alérgico(x))?
∃x (Paciente(x) → Alérgico(x))?
¿Cuánto vale ∃x (Paciente(x) ∧ Alérgico(x))?
Buscá un testigo o un contraejemplo antes de revelar.
Modelo completo: conocemos cada V y F. Este cálculo evalúa el modelo mostrado; no decide validez general.
3.3 · ELEGIR Y JUSTIFICAR
Todos los pacientes son alérgicos.
3.4 · ORDEN DE LOS CUANTIFICADORES
Alguien para cada uno. ¿El mismo para todos?
01∀x ∃y Ama(x,y): cada persona ama a alguien; y puede depender de x.
02∃y ∀x Ama(x,y): hay al menos una misma persona amada por todos.
03La segunda exige un testigo común; no exige que sea único.
3.4 · EXPLORAR UNA RELACIÓN
Una fila para cada persona.
MODELO FINITO · ANA, BRUNO Y CELIACada uno elige a alguien diferente
| x → y | Ana | Bruno | Celia |
|---|---|---|---|
| Ana | F | V | F |
| Bruno | F | F | V |
| Celia | V | F | F |
∀x ∃y Ama(x,y)?
∃y ∀x Ama(x,y)?
¿Cuánto vale ∃y ∀x Ama(x,y)?
Buscá un testigo o un contraejemplo antes de revelar.
Modelo completo: conocemos cada V y F. Este cálculo evalúa el modelo mostrado; no decide validez general.
3.4 · LEER UNA GARANTÍA
¿Qué implica tener un testigo común?
3.4 · CUANDO EL ORDEN NO CAMBIA
Dos universales. Dos existenciales.
01∀x ∀y Ama(x,y) ≡ ∀y ∀x Ama(x,y).
02∃x ∃y Ama(x,y) ≡ ∃y ∃x Ama(x,y).
03Intercambiar cuantificadores del mismo tipo conserva el significado.
3.5 · NEGAR CUANTIFICADORES
No todos aprobaron ≠ nadie aprobó.
01Negar «todos» pide al menos un contraejemplo.
02Negar «alguno» exige que ningún objeto cumpla.
¬∀x P(x) ≡ ∃x ¬P(x) ¬∃x P(x) ≡ ∀x ¬P(x)
3.5 · COMPROBAR LAS NEGACIONES
Buscá a quien no cumple.
MODELO FINITO · ANA, BRUNO Y CELIAUn caso que no cumple
Ana
Aprobó: V
Bruno
Aprobó: F
Celia
Aprobó: V
¬∀x Aprobó(x) ≡ ∃x ¬Aprobó(x)?
¬∃x Aprobó(x) ≡ ∀x ¬Aprobó(x)?
¿Cuánto vale ¬∀x Aprobó(x)?
Buscá un testigo o un contraejemplo antes de revelar.
Modelo completo: conocemos cada V y F. Este cálculo evalúa el modelo mostrado; no decide validez general.
3.5 · TRANSFERIR A OTRO EJEMPLO
Negá una regla sobre archivos.
3.6 · DOS LENGUAJES
Más estructura permite decir más.
01Proposicional: átomos completos y conectivos; casos particulares.
02Primer orden: objetos, propiedades, relaciones, funciones y cuantificadores.
03Una regla cuantificada evita enumerar por separado cada individuo.
3.6 · EXPRESIVIDAD Y CÁLCULO
Evaluar un modelo no es decidir validez.
01Con n átomos proposicionales, una tabla enumera 2ⁿ interpretaciones.
02En primer orden, los dominios pueden ser infinitos: no hay una tabla finita general.
03La validez de la lógica de primer orden completa es semidecidible.
3.6 · ELEGIR RESTRICCIONES
Podemos limitar el lenguaje para trabajar mejor.
01Fragmentos como Datalog sin funciones, sobre datos finitos, permiten calcular un cierre finito.
02Las cláusulas de Horn sin otras restricciones no garantizan siempre terminación.
03Elegimos representación y método según las necesidades del problema.
CIERRE · RECUPERAR LO APRENDIDO