PDF de programación - Tema 6: Sintaxis y semántica de la lógica de primer orden

Lógica de primer

orden

Introducción

Sintaxis
Lenguajes de primer
orden
Términos y fórmulas
Sustituciones

Semántica
Estructuras
Interpretación de
términos y fórmulas
Consecuencia lógica y
validez

Tema 6: Sintaxis y semántica de la lógica de

primer orden

Depto. Ciencias de la Computación Inteligencia Artificial

Universidad de Sevilla

Lógica Informática (Tecnologías Informáticas)

Curso 2015–16

Contenido

Introducción

Sintaxis

Lenguajes de primer orden
Términos y fórmulas
Sustituciones

Semántica

Estructuras
Interpretación de términos y fórmulas
Consecuencia lógica y validez

Lógica de primer

orden

Introducción

Sintaxis
Lenguajes de primer
orden
Términos y fórmulas
Sustituciones

Semántica
Estructuras
Interpretación de
términos y fórmulas
Consecuencia lógica y
validez

Lógica de primer

orden

Introducción

Sintaxis
Lenguajes de primer
orden
Términos y fórmulas
Sustituciones

Semántica
Estructuras
Interpretación de
términos y fórmulas
Consecuencia lógica y
validez

Limitaciones de la lógica proposicional

La lógica proposicional posee un semántica sencilla y

existen algoritmos de decisión para sus problemas
básicos, como SAT o la consecuencia lógica.

Sin embargo, la expresividad de la lógica proposicional

es bastante limitada.

Existen problemas cuya descripción mediante lógica
proposicional es complicada, ya que requiere un gran
número de fórmulas o bien fórmulas de gran tamaño.

Más aún, existen formas de razonamiento válido que no
pueden ser expresadas mediante la lógica proposicional,
por ejemplo:

Todos los hombres son mortales
Sócrates es un hombre.
Por tanto, Sócrates es mortal.

La lógica de primer orden extiende a la lógica

proposicional proporcionando mayor expresividad.

Ejemplo

Consideremos las siguientes afirmaciones:

1. Marco era pompeyano.

2. Todos los pompeyanos eran romanos.

3. Cada romano, o era leal a César, o le odiaba.

4. Todo el mundo es leal a alguien.

5. La gente sólo intenta asesinar a aquellos a quienes no es

leal.

6. Marco intentó asesinar a César.

7. Todo pompeyano es leal a su padre.

¿Podemos deducir a partir de esta información que Marco
era leal a César? ¿Podemos deducir que Marco odiaba a
César? ¿Era César el padre de Marco?

Lógica de primer

orden

Introducción

Sintaxis
Lenguajes de primer
orden
Términos y fórmulas
Sustituciones

Semántica
Estructuras
Interpretación de
términos y fórmulas
Consecuencia lógica y
validez

Ejemplo (II)

Podemos formalizar las afirmaciones observando que

todas ellas expresan propiedades de los elementos de un
cierto conjunto de individuos (romanos) y las relaciones
que se dan entre ellos.

Introduzcamos símbolos para expresar estas relaciones y

para referirnos a los individuos de los que estamos
hablando:

P(x) expresa “x es pompeyano”.
R(x) expresa “x es romano”.
L(x, y ): “x es leal a y ”.
O(x, y ): “x odia a y ”.
IA(x, y ): “x intentó asesinar a y ”.
Por último, parece natural introducir una función f tal

que para cada x, f (x) es el padre de x.

Lógica de primer

orden

Introducción

Sintaxis
Lenguajes de primer
orden
Términos y fórmulas
Sustituciones

Semántica
Estructuras
Interpretación de
términos y fórmulas
Consecuencia lógica y
validez

Lógica de primer

orden

Introducción

Sintaxis
Lenguajes de primer
orden
Términos y fórmulas
Sustituciones

Semántica
Estructuras
Interpretación de
términos y fórmulas
Consecuencia lógica y
validez

Ejemplo (III)

Ahora podemos formalizar los enunciados anteriores.
Veámoslo:

1. P(Marco) expresa “Marco es pompeyano”
2. ∀x (P(x) → R(x))

“Todos los pompeyanos son romanos”
3. ∀x (R(x) → (L(x, Cesar) ∨ O(x, Cesar))
“Todo romano es leal a César o le odia”

4. ∀x ∃y L(x, y )

“Todo el mundo es leal a alguien”.

5. ∀x ∀y (IA(x, y ) → ¬L(x, y ))

“La gente sólo intenta asesinar a aquellos a quienes no

es leal”.

6. IA(Marco, Cesar)

“Marco intentó asesinar a César”.

7. ∀x (P(x) → L(x, f (x)))

“Todo pompeyano es leal a su padre”.

Ejemplo (IV)

Para las preguntas podemos escribir:

a. L(Marco, Cesar): Marco es leal a César.
b. O(Marco, Cesar): Marco odia a César.

Sin embargo, no podemos expresar que “Marco es el

padre de César” sin considerar algún símbolo más.

Una posibilidad es añadir a nuestro lenguaje el símbolo

“=” para expresar al igualdad entre dos objetos. De
este modo tendríamos:

f (Marco) = Cesar: César es el padre de Marco.
Como puede verse, hemos ampliado el conjunto de
símbolos disponibles en la lógica proposicional. El
conjunto de símbolos introducidos constituye lo que
denominamos un lenguaje de primer orden.

Lógica de primer

orden

Introducción

Sintaxis
Lenguajes de primer
orden
Términos y fórmulas
Sustituciones

Semántica
Estructuras
Interpretación de
términos y fórmulas
Consecuencia lógica y
validez

Lógica de primer

orden

Introducción

Sintaxis
Lenguajes de primer
orden
Términos y fórmulas
Sustituciones

Semántica
Estructuras
Interpretación de
términos y fórmulas
Consecuencia lógica y
validez

Lenguajes de primer orden

Un lenguaje de primer orden L consta de:

Símbolos lógicos (comunes a todos los lenguajes):

1. Un conjunto de variables: V = {x0, x1, . . .}.
2. Conectivas lógicas: ¬, ∨, ∧, →, ↔.
3. Cuantificadores: ∃ (existencial), ∀ (universal).
4. Símbolos auxiliares: Paréntesis“(”, “)” y coma “,”

Símbolos no lógicos (propios de cada lenguaje):

1. Un conjunto LC de constantes.
2. Un conjunto de símbolos de función

LF = {f0, f1, . . .}, cada uno con su aridad.
3. Un conjunto de símbolos de predicados
LP = {p0, p1, . . .}, cada uno con su aridad.
(Los conjuntos V , LF , LC y LP son disjuntos)

Los símbolos de predicado de aridad 0 son símbolos

proposicionales.

El símbolo = no es un predicado común a todos los

lenguajes de primer orden. Cuando está incluido en el
lenguaje decimos que se trata de un lenguaje de primer
orden con igualdad.

Ejemplos

Lógica de primer

orden



En el ejemplo de los romanos se introdujo el lenguaje:

LR = {Marco, Cesar
constantes



, P, L, O, R, IA

,

símb. de predicado



f

}
símb. de función

P, R y f tienen aridad 1, L, O, IA aridad 2.

El lenguaje de la Aritmética (números naturales):

LA = { 0 ,

1



,

constantes

<, + y · tienen aridad 2.



símb. de predicado

< , =



,

·

}
símb. de función

, +



Introducción

Sintaxis
Lenguajes de primer
orden
Términos y fórmulas
Sustituciones

Semántica
Estructuras
Interpretación de
términos y fórmulas
Consecuencia lógica y
validez



Un lenguaje para el parentesco:

LP = {Padre, Madre, Hijo, Hermano, Casados
}



símb. de predicado

Todos de aridad 2.

Términos

Los términos de un lenguaje L se definen como sigue:

1. Las variables y las constantes son términos.
2. Si t1, . . . , tn son términos y f es un símbolo de función
de L de aridad n, entonces f (t1, . . . , tn) es un término.

Ejemplos:

Son términos del lenguaje LR:

Marco, Cesar, f (x), f (Cesar), f (f (Cesar)), . . .

Son términos del lenguaje de la Aritmética:
0, +(x, y ), ·(x, +(y , 1)), . . .

Utilizando la notación infija tradicional se escriben

x + y , x · (y + 1)

Lógica de primer

orden

Introducción

Sintaxis
Lenguajes de primer
orden
Términos y fórmulas
Sustituciones

Semántica
Estructuras
Interpretación de
términos y fórmulas
Consecuencia lógica y
validez

Fórmulas

Las fórmulas atómicas de L son las expresiones

p(t1, . . . , tn), donde p es un símbolo de predicado de
aridad n y t1, . . . , tn son términos.

Las fórmulas de L se definen como sigue:

1. Las fórmulas atómicas de L son fórmulas de L.
2. Si F y G son fórmulas de L, entonces ¬F , (F ∨ G )
(F ∧ G ), (F → G ) y (F ↔ G ) también lo son.
∃x F y ∀x F también lo son.

3. Si x es una variable y F es una fórmula de L, entonces

Lógica de primer

orden

Introducción

Sintaxis
Lenguajes de primer
orden
Términos y fórmulas
Sustituciones

Semántica
Estructuras
Interpretación de
términos y fórmulas
Consecuencia lógica y
validez

Ejemplos de fórmulas
En LA, ¬∃x(x · 0 = y )
En LP,

∃x(Padre(x, y ) ∧ Padre(x, z))

Pero ∃xPadre(Padre(x, y ), z), NO es una fórmula.

En LR,

∀x ∃y L(x, y )

∀x (R(x) → (L(x, Cesar) ∨ O(x, Cesar)))

Notación: Para facilitar la lectura de las fórmulas y

reducir el número de paréntesis adoptamos los mismos
convenios que para la lógica proposicional.

Omitiremos los paréntesis externos.
Daremos a las conectivas una precedencia de asociación.
De mayor a menor, están ordenadas por: ¬,∧,∨,→,↔.

Lógica de primer

orden

Introducción

Sintaxis
Lenguajes de primer
orden
Términos y fórmulas
Sustituciones

Semántica
Estructuras
Interpretación de
términos y fórmulas
Consecuencia lógica y
validez

Árboles de formación
Análisis sintáctico de la expresión ∃x(y + y = x · 0 ∨ 1 < y )

∃x
∨

HHHHH
=
HHH

·
+
 HH
 HH
0
x
y
y

<

 HH
1
y

Lógica de primer

orden

Introducción

Sintaxis
Lenguajes de primer
orden
Términos y fórmulas
Sustituciones

Semántica
Estructuras
Interpretación de
términos y fórmulas
Consecuencia lógica y
validez

Árboles de formación

El árbol de formación de la fórmula

∃x(y + y = x · 0 ∨ 1 < y )

puede escribirse también de este modo:

∃x(y + y = x · 0 ∨ 1