Lógica para las Ciencias Informáticas

2016

Lógica para las

Ciencias
Informáticas
Computación en P

Licenciatura en Sistemas

Dr. Carlos E. Alvez

[email protected]
Adaptación de: Simari - 2006 - UNS

Formas Normales

 En el Cálculo Proposicional se puede transformar

una FBF arbitraria en otra FBF equivalente que se
encuentre en forma normal conjuntiva.

 En el lenguaje del Cálculo de Predicados tenemos

cuantificadores que introducen una dificultad
adicional para estas transformaciones.

 Existe una forma especial denominada forma prenexa

en la que todos los cuantificadores preceden a una
FBF sin ellos.
 Veremos ahora un procedimiento para obtener la
forma prenexa.

1
Lógica para las Ciencias Informáticas
2016

Cláusulas
Def: Una expresión, término o cláusula se dice fija si no contiene
variables.
Def: Una FBF de está en forma clausal si es una sentencia descripta
por la siguiente pseudo-gramática:

término  constante | variable |

letra-funcional “(” lista-términos “)”
lista-términos  término | término “,” lista-términos
fórmula-atómica  letra-predicativa “(” lista-términos “)”
literal  fórmula-atómica | “”fórmula-atómica
cláusula  “” | “{” literal “}” | “{” literal “}”  cláusula
sentencia  “{” cláusula “}” | “{” cláusula “}”  sentencia
3

Cláusulas
 Obs: Notemos que al igual que en L seguimos interpretando a las
cláusulas como una disyunción de los elementos que la forman
cláusula  “” | “{” literal “}” | “{” literal “}”  cláusula
es equivalente a
cláusula  “” | literal | literal “” cláusula

y una sentencia
sentencia  “{” cláusula “}” | “{” cláusula “}”  sentencia
es equivalente a
sentencia  cláusula | cláusula “” sentencia

 Obs: A pesar de no mencionar cuantificadores supondremos que

todas las sentencias están clausuradas (cuantificadas)
universalmente en todas sus variables.

2
Lógica para las Ciencias Informáticas
2016

Forma Prenexa
Def: Una FBF está en forma prenexa si cada variable está
cuantificada y todos los cuantificadores preceden a una
sentencia sin cuantificadores.
El conjunto de cuantificadores se denomina prefijo y la
sentencia que le sigue, y que representa su alcance, se
denomina matriz.
Por ejemplo, la fórmula bien formada
(((x)A(x)  (y)B(y))  (z)C(z))

se transforma en

(x)(y)(z)((A(x)  B(y))  C(z))

Prefijo Matriz
5

Forma Prenexa
Obs: Dada una FBF arbitraria existe un procedimiento para obtener
una FBF equivalente en forma prenexa.
Los pasos son los siguientes:
1. 1. A  B se transforma en (A  B)  (B  A)
A  B se transforma en A  B
2. Se reubican los cuantificadores a la izquierda de los
conectivos lógicos. Observemos que luego de aplicar las
reglas en 1. solo quedan “”, “”, “” en ella.
a. (x) A se transforma en (x)A
b. (x) A se transforma en (x)A
Ahora se renombran las variables ligadas de manera que
variables diferentes tengan nombres diferentes. Por ejemplo,
(x)(A(x)  B(x))  (x)C(x)
se transformará en
(x)(A(x)  B(x))  (y)C(y)
6

3
Lógica para las Ciencias Informáticas
2016

Forma Prenexa
Luego
c. ( ... (x)A … ) se transforma en (x)( ... A … )
d. ( ... (x)A … ) se transforma en (x)( ... A … )
e. ( ... (x)A … ) se transforma en (x)( ... A … )
f. ( ... (x)A … ) se transforma en (x)( ... A … )
esta notación simplificada describe una conjunción (o
disyunción) genérica donde uno de sus miembros contiene el
cuantificador mencionado en la regla de transformación.
Notemos que no se producen capturas de variables por el
cuantificador que se reubica, dado que las variables de la
fórmula han sido renombradas convenientemente.
Por ejemplo,
A(x)  (y)B(y)  C(z)
se transforma en
(y)(A(x)  B(y)  C(z))
7

Forma Prenexa
3. Si existieran variables libres clausuramos universalmente la FBF
agregando cuantificadores universales al comienzo de la misma.

Por ejemplo, la fórmula

((x)A(x)  B(y))  C(z)
tiene las variables y y z libres, entonces se transforma en
(y)(z)(((x)A(x)  B(y))  C(z))
Notemos que no se producen capturas de variables por los
cuantificadores que se agregan dado que las variables fueron
renombradas un paso anterior.

 Ver procedimiento completo y ejemplos en “Truth, Deduction,

and Computation”,
R. Davis, pág. 67 y 68.

4
Lógica para las Ciencias Informáticas
2016

Forma de Skolem

 La transformación de una FBF cualquiera a forma

prenexa es algorítmica, i.e. existe un procedimiento
efectivo que permite transformar una FBF cualquiera en
otra equivalente que se encuentra en forma prenexa.

 Sin embargo, todavía no logramos estar en

condiciones similares a las del Cálculo Proposicional.

 Es posible transformar la forma prenexa en una forma,

llamada forma de Skolem con variables libres, que
solo contiene cuantificadores universales en el prefijo.

Skolemización
 Sea A una FBF en forma prenexa y supongamos que el prefijo de
A contiene un cuantificador existencial (x).

 Se reemplaza cada aparición de la variable x en la matriz de A

por un término ski(x1, x2, ..., xn) donde ski es una función n-aria
que no aparece en la matriz de A.
La lista de variables x1, x2, ..., xn está formada por las variables
que aparecen en los cuantificadores universales del prefijo de A
que aparecen a la izquierda de (x).

 Si no aparece ningún cuantificador universal a la izquierda de

(x) se reemplaza la variable x en la matriz de A por una
constante (que es una función 0-aria), que no aparezca en la
matriz de A.
 El proceso se repite hasta que no queden cuantificadores
existenciales en el prefijo de A.

10

5
Lógica para las Ciencias Informáticas
2016

Forma de Skolem (Ejemplo)

 La fórmula bien formada prenexa
(x)(y)(z)((A(x)  B(y))  C(z))
se transforma en la forma skolemizada
(x)((A(x)  B(sk1(x)))  C(sk2(x))
donde sk1 y sk2 son funciones de Skolem distintas.
 La fórmula bien formada prenexa
(x)(y)(z)(A(x)  (B(y)  C(z)))
se transforma en la forma skolemizada
(y)(A(a)  (B(y)  C(sk3(y)))
donde a es una constante arbitraria y sk3 es una función de
Skolem.
11

Forma de Skolem

!Esta forma de Skolem no es equivalente a la forma

prenexa pero la implica lógicamente, es decir, cada
vez que la forma skolemizada es verdadera la forma
prenexa también lo es. Sin embargo, la forma
prenexa es satisfacible si y solo si la forma de
Skolem es satisfacible.!

 Una vez obtenida la forma de Skolem se puede

continuar con los procedimientos conocidos.

12

6
Lógica para las Ciencias Informáticas
2016

Resolución
en P

13

Computación
 Recordemos que el mecanismo lógico de computación es el
cálculo de resolventes a través de la eliminación de literales
complementarios.

 La forma prenexa skolemizada contiene un prefijo de

cuantificadores universales y una matriz en forma clausal que
fácilmente puede transformarse a forma normal conjuntiva
reducida.

 Una vez que se hace esto se puede eliminar el prefijo asumiendo

que todas las variables que figuran en la matriz se encuentran
cuantificadas universalmente.
 Por ejemplo, la fórmula skolemizada
(y)(A(a)  (B(y)  C(sk3(y))) se transforma en
(A(a)  (B(y)  C(sk3(y)))

14

7
Lógica para las Ciencias Informáticas
2016

Resolución
 En la lógica proposicional, se utiliza la eliminación de
literales complementarios entre cláusulas para obtener
resolventes.

 Por ejemplo, p y p son literales complementarios.

 En el cálculo de predicados también se utilizará la

eliminación de literales complementarios, pero en P hay
constantes, variables y funciones lo que introduce
dificultades.

 Por ejemplo, si consideramos el par p(a) y p(f(x)) ¿sus

literales serán complementarios?

15

Pares Complementarios (?)

p( a )  p(a)
p( a )   p( b)
p( x )  p(x)
p( x )  p(y)
p(f(a))  p(x)
p(f(f(a)))  p(f(x))
p(f(f(a)))  p(g(x))

16

8
Lógica para las Ciencias Informáticas
2016

La Variable Lógica
 Una variable lógica representa un individuo no especificado,
pero único.

 Esto contrasta con las variables en los lenguajes de programación

convencionales en los que una variable representa
almacenamiento en forma abstracta.

 La forma por la que se refina la especificación del individuo

representado por la variable lógica es la instanciación.
El mecanismo para producir esta instanciación involucra el uso de
substituciones.

 Una vez instanciada la variable lógica esta no podrá ser re-

instanciada a menos que esta instanciación se vuelva atrás (i.e.,
se vuelve al punto anterior a haberla hecho y se elige otro
individuo).

17

Substituciones

18

9
Lógica para las Ciencias Informáticas
2016

Substituciones y Unificación

 Existen descripciones de individuos que al ser

substituidas en las variables hacen que pares que no son
sintácticamente complementarios produzcan pares
complementarios.

 Esto se logra utilizando una substitución particular que

restrinja la especificación de los individuos en los literales
que forman el par, de manera de evidenciar la forma en que
serían complementarios.

 El proceso de encontrar descripciones adecuadas para

utilizar en estas substituciones de las variables se
denomina unificación.

19

Términos
 Los términos son designadores de individuos (constantes
individuales).

 Por definición:
• Una constante y una variable son términos.
• Un término compuesto está formado por un functor, i.e. una
letra funcional, con una aridad determinada y la lista de
términos de longitud correspondiente a la aridad del functor:
fkn(t1, t2, ..., tn)

 Los términos fijos, que no contienen variables designan un único

individuo.

 Los términos que contienen variables designan conjuntos de

individuos.

20

10
Lógica para las Ciencias Informáticas
2016

Términos fijos

Los términos fijos, que

no contienen variables
a f( a ) designan un único
individuo.

D D

21

Términos “no fijos”

Los términos que

contienen variables
designan conjuntos de
individuos.
f ( x)

D D

22

11
Lógica para las Ciencias Informáticas
2016

Substituciones
Def: Una substitución es un conjunto finito , posiblemente
vacío, de pares de la forma (ti, xi), donde xi es una variable y ti
es un término, y además:
1. Si xi  xk si i  k
2. xi no aparece en tk cualesquiera sean i y k.

 Una substitución  se denotará:

[(t1, x1), (t2, x2), ..., (tn, xn)] o también
[t1 /x1, t2 /x2, ..., tn /xn]
donde cada uno de los componentes (ti, xi) expresa el
requerimiento de que se reemplace con el término ti en cada
aparición de xi. ( Análogamente para ti /xi )

23

Substituciones
 Obs: Las dos condiciones
1. Si xi  xk si i  k
2. xi no aparece en tk para cualquier i y k.
aseguran que si dos substituciones 1 y 2 son iguales como
conjuntos entonces tendrán el mismo efecto al aplicarse sobre
cualquier expresión.

Concretamente, establecen que el orden de aplicación de las

substituciones individuales no afecta al resultado.

 Ejercicio: Dar ejemplos de substituciones y de términos

(o FBFs) en donde substituciones mal formadas (no
satisfagan las condiciones 1 y 2) y esto sea evidente en
el resultado. Esto es, aplicarlas en orden distinto afecte
el resultado.
24

12
Lógica para las Ciencias Informáticas
2016

Substituciones
 Obs: Una substitución puede aplicarse a un término o FBF y
usaremos la palabra expresión para referirnos a esto.

 Def: La aplicación de una substitución  a una expresión A,

denotado A, es el término o FBF obtenido de A reemplazando
cada aparición de x por t en A, para cada par (t, x) en .

 Obs: La substitución vacía, , no afecta a la expresión al que se

aplique, i.e. A  A.

 Ejemplo: El resultado de aplicar la substitución   [(a, x)] al

término f(x, b) es f(a, b), y puede notarse
f(x, b)  f(x, b)[(a, x)]  f(a, b)

 Def: A se dice que es una instancia de substitución de B si

existe una substitución  tal que A  B.

25

Substituciones
Def: Sean   [(t1, x1), (t2, x2), ..., (tn, xn)] una substitución
arbitraria y   [(s, v)] una substitución unitaria con la
característica de que v  xi y xi no aparece en s cualquiera sea
i, 1  i  n. Entonces, definimos la composición de  y  de la
siguiente manera:

  [(t1, x1), (t2, x2), ..., (tn, xn)][(s, v)] 

[(t1 [(s, v)], x1), (t2 [(s, v)], x2), ..., (tn [(s, v)], xn), (s, v)]

 Ejemplo:   [(f(x), y), (a, w)];  [(a, x)]

  [(f(x)[a/x], y), (a[a/x], w), (a, x)]  [(f(a), y), (a, w), (a, x)]

 Lema: Sea A un término o una FBF y sean  y  dos

substituciones, entonces: (A)  A()

 Lema: Sean ,  y  tres substituciones, entonces: ()  ()

26

13
Lógica para las Ciencias Informáticas
2016

Substituciones Unificadoras
Par de literales Substitución

p(a) p(a)  (subst.vacía)

p(a) p(b) No existe

p(x) p(x)  (subst. vacía)
p(x) p(y) x/y ó y/x
p(f(a)) p(x) f(a)/x
p(f(f(a))) p(f(x)) f(a)/x
p(f(f(a))) p(g(x)) No existe

Obs: Recordemos que la notación   [t1 /x1, t2 /x2, ..., tn /xn] es una
notación alternativa para   [(t1, x1), (t2, x2), ..., (tn, xn)]
27

Substituciones Unificadoras
 Def: Sea   { L1, L2, ..., Ln } un conjunto de expresiones
(términos o FBFs) y  una substitución. Decimos que  es
unificado por  si L1  L2 ...  Ln. La substitución  recibe
el nombre de substitución unificadora o simplemente unificador.

 Obs: Si  es un unificador de  entonces el conjunto

  { L1, L2, ..., Ln }
es un conjunto con un solo elemento.

 Def: Sea  = { L1, L2, ..., Ln } un conjunto de expresiones

(términos o FBFs) y  una substitución. Decimos que  es la
substitución unificadora más general o unificador más general
si para cualquier otro unificador  existe una substitución  tal
que   .
28

14
Lógica para las Ciencias Informáticas
2016

Substituciones Unificadoras

 Por ejemplo,   { p(x), p(y) } tiene varios posibles

unificadores:
1.   [ a/x, a/y ] unifica como   { p(a) }
2.   [ x/y ] unifica como   { p(x) }

 El segundo unificador es más general dado que permite que

las variables permanezcan, esto es, el término resultante es
menos específico.
Esto es importante para futuras unificaciones.
Además,    con   [a/x] de acuerdo a la definición.

29

Substituciones Unificadoras

 Intuitivamente, un unificador más general de un

conjunto de expresiones es aquel que hace la menor
cantidad y la más general de las substituciones
necesarias para unificar ese dado conjunto de
expresiones.

 Claramente, es posible que para un conjunto de

expresiones particular no exista una substitución
unificadora.

 Sin embargo, si existiera un unificador entonces

siempre es posible hallar un unificador más general.

30

15
Lógica para las Ciencias Informáticas
2016

Conjunto de Desacuerdo
Def: Sea   { L1, L2, ..., Ln } un conjunto de expresiones (términos o
FBFs del mismo tipo). El conjunto de desacuerdo de  es el conjunto
de subexpresiones bien formadas de las expresiones de  que
comienzan en la primera posición, comenzando desde la izquierda,
en la que no todas las expresiones coinciden.
Ejemplos: p(x, f(x, g(y)), v)
p(x, f(x, z), w)
Si   { p(x, f(x, g(y)), v), p(x, f(x, z), w) } vemos que
p(x, f(x, g(y)), v), p(x, f(x, z), w) la parte roja coincide y
entonces su conjunto de desacuerdo es { g(y), z }.
 Si   { p(x, f(y,z)), p(x, a), p(x, g(h(k(x)))) } vemos que
p(x, f(y, z)), p(x, a), p(x, g(h(k(x)))) la parte roja coincide
entonces su conjunto de desacuerdo es { f(y, z), a, g(h(k(x))) }.

31

Conjunto de Desacuerdo
Obs: Dado   { L1, L2, ..., Ln } un conjunto de expresiones
(términos o FBF, pero del mismo tipo) el conjunto de
desacuerdo de  es o bien el conjunto  en cuyo caso el
conjunto es no unificable, o bien el conjunto vacío en cuyo
caso  tiene un solo elemento, o bien contiene un
elemento de cada uno de los miembros de .

Obs: Notemos que si

  { p(x, f(y, z),u), p(x, a, v), p(x, a, w) }

su conjunto de desacuerdo es { f(y, z), a } y se tiene una

subexpresión de cada una de las expresiones de 
aunque en este caso particular, dos de ellas (a) coinciden.

32

16
Lógica para las Ciencias Informáticas
2016

Orden Lexicográfico
 Introduciremos un orden lexicográfico entre los elementos
del lenguaje del Cálculo de Predicados, suponiendo que
trabajamos con FBFs en la forma de Skolem:
1. Variables 1ro. ordenadas por subíndice, luego alfabéticamente.
2. Constantes.
3. Letras funcionales ordenadas primero por el superíndice, i.e. su
aridad, y dentro de las que tienen la misma aridad por
subíndice, luego alfabéticamente.
4. Letras predicativas ordenadas primero por aridad (superíndice)
y dentro de las que tienen la misma aridad por subíndice, luego
alfabéticamente.
5. Conectivos lógicos en el siguiente orden: “”, “”, “”, “”, “”

33

Procedimiento de
Unificación

34

17
Lógica para las Ciencias Informáticas
2016

Procedimiento de Unificación (Robinson)

1. Sea  un conjunto de expresiones.
1   ( también se denota [ ] )
k
2. kk+1
Si los elementos de k son todos iguales entonces se asigna
0  k y se detiene emitiendo 0 como substitución unificadora.
Si k no es un conjunto unitario continuar.
3. Sea sk y tk las dos expresiones minimales en el orden lexicográfico
dentro del conjunto de desacuerdo de k.
Si sk es una variable y sk no aparece en tk
entonces
k+1  k[(tk, sk)] y volver a 2.
si no es así
detenerse señalando que no existe unificador.
35

Procedimiento de Unificación (Robinson)

 Obs: Dado cualquier conjunto finito, no vacío, de expresiones el
algoritmo de unificación siempre termina. Si no fuera así se
generaría una secuencia infinita 1, L2, … Ln, … donde cada
i es un conjunto de expresiones.
Notemos que i+1 se obtiene de i, y i+1 contiene una
variable menos que i. Como las expresiones originales
contenidas en  solo incluyen un número finito de variables no
es posible prolongar la secuencia indefinidamente.

 Def: El test del paso 3. del algoritmo en el que se pregunta si sk

es una variable y sk no aparece en tk, recibe el nombre de occur
check.

 Teo: Sea  un conjunto finito, no vacío, de expresiones. Si  es

unificable entonces el algoritmo de unificación siempre termina
y el unificador encontrado es un unificador más general de .
36

18
Lógica para las Ciencias Informáticas
2016

Ejemplo 1
Sea   { p(a, x, f(g(y))), p(z, f(z), f(w))}
1ra Iteración: 1  , 1  , D1(1)  {z, a }, s1  z y t1  a, luego
2  1[ (a, z) ], es decir 2  [ (a, z) ]
2da Iteración: 2  2, i.e. 2  [ (a, z) ]
2  { p(a, x, f( g(y))), p(a, f(a), f(w))}
D2(2)  { x, f(a) }, s2  x y t2  f(a), luego 3  2[ (f(a), x) ],
es decir 3  [ (a, z), (f(a), x) ]
3ra Iteración: 3  3, 3  [ (a, z), (f(a), x) ]
3  { p(a, f(a), f(g(y))), p(a, f(a), f(w))}
D3(3)  {w, g(y)}, s3  w y t3  g(y), luego 4  3[ (g(y), w) ],
es decir 4  [ (a, z), (f(a), x), (g(y), w) ]
4ta Iteración: 4  4, 4  [ (a, z), (f(a), x), (g(y), w) ],
es decir 4  { p(a, f(a), f(g(y)))}
Terminando en el unificador más general 4  [(a, z), (f(a), x), (g(y), w)]
37

Ejemplo 2
Sea   {h(x, f(g(a, x))) ; h(f(y), f(g(a, f(c)))) }
1ra Iteración: 1  , 1  , D1(1)  {x, f(y) }, s1  x y t1  f(y),
luego 2  1[ (f(y), x) ], es decir 2  [ (f(y), x) ]

2da Iteración: 2  2, i.e. 2  [(f(y), x)]

2  {h(f(y), f(g(a, f(y)))) ; h(f(y), f(g(a, f(c)))) }
D2(2)  { y, c }, s2  y y t2  c, luego 3  2[ (c, y) ], es decir
3  [(f(y), x)[(c, y)], (c, y) ] , es decir 3  [(f(c), x), (c, y)]

3ra Iteración: 3  3, 3  [(f(c), x), (c, y)] , es decir

3  {h(f(c), f(g(a, f(c)))) }
Terminando en el unificador más general 3  [(f(c), x), (c, y)]

38

19
Lógica para las Ciencias Informáticas
2016

Bibliografía

“Truth, Deduction, and Computation,”

R. Davis,
desde página 64 a 72 y desde 74 a 76.

39

20