Lógica de primer orden

La lógica proposicional clásica formaliza la parte más elemental de nuestro lenguaje natural. Concretamente:

• Sólo considera las frases declarativas, llamadas proposiciones o enunciados, a las que es posible considerar o bien verdaderas o bien falsas y con ningún otro valor de verdad (es decir, es bivaluada y trabaja con el Principio del tercero excluido: A ∨ ¬A siempre es verdadera). Este valor de verdad queda completamente determinado por el valor de verdad o falsedad de los enunciados simples que la componen y por las partículas no, o, y, si . . . entonces, si y solo si, utilizadas como elementos de enlace (es decir, es veritativo-funcional).

• La asignación de valores de verdad o falsedad a los enunciados se realiza sin recurrir a consideraciones de contexto alguno y sin considerar la estructura interna de los enunciados simples (es decir, trabaja al nivel más sencillo de análisis: el sujeto y el predicado que componen internamente un enunciado simple son irrelevantes, como entidades aisladas, para la lógica proposicional).

Así, si consideramos el razonamiento:

Todo estudiante es inquieto.

Luis es un estudiante.

Por lo tanto, Luis es inquieto.

Intuitivamente, no dudamos en afirmar que es un razonamiento correcto, ya que responde a la forma “Todo A es B” y “C es un A”. Por lo tanto “C es un B”. Sin embargo, puesto que la lógica proposicional no contempla estructura alguna en los enunciados declarativos simples, su lenguaje únicamente permite representar las expresiones “Todo estudiante es inquieto”, “Luis es un estudiante” y “Luis es inquieto”, por símbolos proposicionales p, q y r respectivamente. Por lo tanto, este razonamiento no es analizado como válido en la lógica proposicional. En efecto, en el marco de dicha lógica su formalización viene dada por

que no es un razonamiento válido en la lógica proposicional clásica.

Del mismo modo, la lógica clásica proposicional no basta para analizar la corrección de programas respecto a una especificación formal. Por ejemplo, la corrección de un programa que calcula el mayor elemento de una lista de números enteros, requiere manejar expresiones del tipo x < y. Esta expresión “predica” una determinada relación entre x e y, y su verdad o falsedad depende de los valores de x y de y.

La insuficiencia de la lógica clásica proposicional, es decir, su escasa potencia expresiva, requiere el desarrollo de una lógica más amplia que permita considerar válidos los razonamientos del tipo anterior. Necesitamos una lógica que permita captar más detalles del lenguaje natural, que no solo contemple las conexiones “externas” entre los enunciados simples, sino que extienda a la lógica clásica proposicional en dos direcciones:

Considere en los enunciados atómicos una determinada estructura interna, la estructura predicativa, que permita diferenciar “qué se predica” (ser estudiante, ser inquieto. . .), de “qué” o “quién” se predica, y permita expresar que, dado un universo del discurso, una cierta propiedad la satisface un ente concreto, o bien todos los entes, o la satisface algún ente o no la satisface ningún ente de dicho universo.

El marco mínimo para dicho propósito lo proporciona la lógica conocida como Lógica de Predicados de Primer Orden o simplemente como la Lógica de Primer Orden, a la que denotaremos por L1.

Wilfred Hodges hace la siguiente reflexión:

. . . la lógica de primer orden es hija de varios padres; al menos tres grupos diferentes de pensadores han tenido que ver en su concepción.

Quizás esta mezcla es la causa de su fuerza. Sin embargo, sea cual sea la razón, la lógica de primer orden es la lógica moderna más simple, más potente y más aplicable. . .

La lógica clásica de primer orden juega en la actualidad un papel destacado en las Ciencias de la Computación por sus aplicaciones en especificación y verificación de programas, en la representación del conocimiento en las bases de datos, en Inteligencia Artificial, etc.

Alfabeto

El alfabeto de un lenguaje de primer orden consta de los siguientes símbolos:

1. Los símbolos de conectivos de la lógica clásica proposicional ¬,→,∧,∨ y ↔.

2. Los símbolos lógicos ⊤ y ⊥.

3. Los símbolos de cuantificación ∀ (universal) y ∃ (existencial).

4. Los símbolos de puntuación “(” y “)”.

5. Un conjunto infinito numerable, V = {x, y, z, v, . . . , x1, y1, z1, v1, . . . , xn, yn, zn, vn, . . .}, de símbolos de variables.

6. Un conjunto numerable (posiblemente vacío), C, de símbolos de constante.

7. Un conjunto numerable (posiblemente vacío), F, de símbolos de función y una función arf : F → N que asigna a cada símbolo de función un elemento de N∗ llamado su aridad (que representa el número de argumentos).

8. Un conjunto numerable y no vacío, P, de símbolos de predicado y una función arp : P → N que asigna a cada símbolo de predicado un elemento de N∗ llamado su aridad (que representa el número de argumentos).

Los símbolos referidos en los puntos 1, 2, 3, 4 y 5 son comunes a todos los lenguajes de primer orden. Por su parte, la elección de los conjuntos C, F y P proporciona un lenguaje específico de primer orden y viene determinada por la aplicación que se pretende. Supondremos que los conjuntos V, C, F y P son disjuntos dos a dos.

Los símbolos de predicado de aridad 1, se denominan propiedades y los símbolos de predicado de aridad mayor que 1 se denominan relaciones.

Consideraremos que la aridad, tanto de los símbolos de predicados como de los símbolos de función, es mayor o igual que 1. Podemos hablar así de:

• Predicados monádicos o monarios o de aridad 1 (como “ser ave”, “ser cuadrado”, “ser par”, “ser actriz”).

• Predicados poliádicos o de aridad mayor a 1 (como “ser tío de” (binario); “estar sentado entre . . . y . . . ” (ternario); “ser dueño de . . . , . . . y . . . ” (de aridad 4), etc).

Habitualmente, usaremos como símbolos:

• Las primeras letras del alfabeto a, b, c, . . . (posiblemente subindizadas) para representar los símbolos de constantes.
• Las últimas letras del alfabeto x, y, z, . . . (posiblemente subindizadas) para representar los símbolos de variables.
• Las letras f, g, h, . . . (posiblemente subindizadas) para representar los símbolos de función.
• Las letras P, Q, R, . . . (posiblemente subindizadas) para representar los símbolos de predicado.

Usando la terminología de los lenguajes de programación, podemos pensar en:

• Los conectivos, como conjunto de instrucciones.
• Los cuantificadores, como llamadas a procedimientos.
• Los símbolos de constantes, como constantes.
• Los símbolos de variables, como parámetros formales.
• Los términos en los que intervienen símbolos de función, como estructuras de datos.
• Los símbolos de predicados, como procedimientos.

Reglas de Inferencia

La lógica de predicados de primer orden se ocupa de métodos de argumentación válidos y sólidos. Éstos se denominan reglas de inferencia. Si se da un conjunto de axiomas que son aceptados como verdaderos, las reglas de inferencia garantizan que sólo serán derivadas consecuencias verdaderas.

Inferir es concluir o decidir a partir de algo conocido: llegar a una conclusión. A su vez, razonar es pensar coherente y lógicamente, establecer inferencias a partir de hechos conocidos.

El proceso de razonamiento, involucra la realización de inferencias a partir de hechos conocidos. Realizar inferencias significa derivar nuevos hechos a partir de un conjunto de hechos conocidos como verdaderos. Las reglas de inferencia de la lógica de predicados de primer orden se componen de las reglas de inferencia de la lógica proposicional, además se incluyen otras para manejar las oraciones de la lógica de predicados de primer orden cuando se tienen cuantificadores.

En la eliminación universal se tiene que para toda oración α, variable v y término de base g:

Por ejemplo en ∀x Legusta(x,ElHelado), se puede utilizar la sustitución {x/Ben} e inferir que Legusta(Ben, ElHelado).

Término de base es aquel en el que no hay variables, es decir, un símbolo constante o un símbolo de función aplicado a algunos términos base.

En la eliminación existencial se tiene que para toda oración α, variable v y símbolo constante k que no aparezca en ninguna parte de la base de conocimientos.

Por ejemplo, en ∃x Mata(x, Victima) se puede inferir que Mata(Asesino, Victima) en tanto Asesino no aparezca en ninguna parte de la base de conocimientos .

Por otra parte, en la introducción existencial se tiene que para toda oración α, variable v que no esté en α y término de base g que no esté presente en α:

Por ejemplo en LeGusta (Miguel, ElHelado) podemos inferir que ∃x LeGusta(x, ElHelado).

Es muy importante tener en cuenta que la constante empleada para sustituir la variable en las reglas de eliminación existencial sea una variable nueva. De no cumplirse con este requisito es fácil que se de lugar a consecuencias ilógicas.

 Unificación

Cuando se tienen oraciones compuestas por predicados y conectivos lógicos, se debe evaluar la veracidad de cada uno de sus componentes para determinar si toda la oración es verdadera o falsa. Para ello, se busca en el conjunto de axiomas la forma de establecer la veracidad de los predicados componentes. Un predicado componente se dice que es verdadero si se identifica con un axioma de la base de información. En la lógica de predicados, este proceso es algo complicado ya que las oraciones pueden tener términos variables. A los predicados que tienen variables por argumentos, se los denomina patrones.

La unificación consiste en convertir dos oraciones p y q en una sustitución mediante la que p y q resulten idénticas.

Unificar(p,q)= θ donde SUST(θ,p)=SUST(θ,q).

Se conoce a θ como el unificador de dos oraciones, se ilustra el concepto de unificación a continuación:

Conoce(Miguel,x) → Quiere(Miguel,x).

Supongamos que contamos con los siguientes hechos en una base de conocimientos:

Conoce(Miguel, Evelia)

Conoce(y, Lourdes)

Conoce(y, Madre(y))

Conoce(x, Leticia)

Conoce(Silvia, Miguel)

Conoce(x,y).

Al unificar el antecedente de la regla con cada uno de los hechos proporcionados obtendremos:

Falla porque x no puede asumir el valor de Miguel y de Leticia al mismo tiempo.

Aún así, de manera intuitiva se sabe que Miguel quiere a todos los que conoce, por lo tanto se puede inferir que Miguel quiere a Leticia. Lo cierto es que para la base de conocimientos lo mismo da que se tenga:

Conoce(x, Leticia).

O se tenga

Conoce(y, Leticia).

Una forma de resolver  este problema consiste en normalizar por separado las dos oraciones que se van a unificar, lo que significa renombrar las variables de una de ellas para evitar que haya repetición de nombres. Luego de normalizar por separado, se tendrá:

Unificar(Conoce(Miguel, x1), Conoce(x2, Leticia))={x,/Leticia, x2/Miguel}.

La unificación fue introducida por Robinson como el paso principal de la regla de inferencia llamada resolución.

Resolución

La manera de probar un teorema es mediante un procedimiento de prueba. Estos utilizan las manipulaciones conocidas como reglas de inferencia para producir nuevas expresiones a partir de las anteriores de forma tal que se garantiza que los modelos de las expresiones anteriores sean modelos de las nuevas.

El procedimiento de prueba más directo consiste en aplicar las reglas de inferencia a los axiomas y a los resultados de aplicar tales reglas hasta que aparezca el teorema deseado.