Lógica de primer orden

Definición

La lógica de primer orden extiende la lógica proposicional para representar objetos, propiedades y relaciones. Su lenguaje incluye:

• constantes, como $S\acute{o}crates$;
• variables, como $x$;
• funciones, como $MadreDe(x)$;
• predicados, como $Humano(x)$ o $Ama(x,y)$;
• cuantificadores universal $\forall$ y existencial $\exists$.

Una interpretación fija un dominio de objetos y asigna significado a constantes, funciones y predicados. Una sentencia es consecuencia de una base $KB$ cuando es verdadera en todos los modelos de $KB$.

Ejemplo mínimo

$$\forall x[Humano(x)\to Mortal(x)],Humano(S\acute{o}crates).$$

La primera sentencia expresa una regularidad sobre cualquier objeto del dominio; la segunda identifica un caso. Mediante resolución puede demostrarse $Mortal(S\acute{o}crates)$.

Diferencia respecto de la lógica proposicional

Una proposición como $SocratesEsMortal$ es indivisible. En primer orden, $Mortal(S\acute{o}crates)$ conserva la estructura predicado–argumento, lo que permite expresar una sola regla para todos los humanos y aplicarla a objetos distintos mediante unificación.

Límites

• La consecuencia lógica general de primer orden es semidecidible: si una sentencia es consecuencia puede existir una prueba finita, pero una búsqueda ingenua puede no terminar cuando no lo es.
• Los cuantificadores y el alcance de variables vuelven esencial renombrar variables y evitar capturas.
• Mayor expresividad suele implicar inferencia más costosa que en lógica proposicional.

Relaciones

• Sus fórmulas se preparan para resolución mediante FNC de primer orden.
• Los existenciales se eliminan mediante skolemización.
• Los términos se hacen coincidir mediante unificación.
• Prolog usa un fragmento restringido de este lenguaje.

Procedencia y referencias

• Clase: Inferencia en lógica de primer orden.
• Russell, S. J. y Norvig, P. (2020). Artificial Intelligence: A Modern Approach (4.ª ed.), capítulos 8 y 9; sitio oficial.