16 de septiembre de 2012

Escribir Fórmulas con Lógica Predicativa

Verificación y Validación de Software
Entrada 6

Para esta semana hemos seleccionado un ejercicio del Capítulo 4: "The World According to Predicate Logic" del libro llamado "Logic in Action". El enlace al PDF se encuentra al final de esta publicación.

El ejercicio que seleccione trata de escribir la fórmula lógica predicativa de unas oraciones, pero para poder entender que es lo que tenía que hacer, el mismo libro tiene algunos ejemplos, por lo que me gustaría empezar mostrandoles esas oraciones y su respectiva fórmula.

Los ejemplos van desde el uso simple de cuantificadores, hasta las que usan cuantificadores múltiples dentro de la fórmula. Para todos se asume que el dominio son los seres humanos o personas.

Tenemos que:
, todos, para todos.
, alguien, por lo menos uno, algunos, algunas.
Wx, significa que una persona "x" camina (Walk).
Bx, evalúa si "x" es un niño (Boy).
Gx, evalúa si "x" es una niña (Girl).
Sxy,significa que "x" ve a "y" (Sees).

Después de definir estas fórmulas podemos ver los ejemplos:
Alguien camina: ∃xWx
Algún niño camina: ∃x(Bx ^ Wx)
Una niña ve a John: ∃x(Gx ^ Sxj)
Todos los niños caminan: ∀x(Bx ⇒ Wx)
Alguien ve a todos: ∃x∀ySxy

Después de ver estos ejemplos logre aclarar mi mente y empece a contestar mi ejercicio que es el siguiente.

Ejercicio 4.13
Escribe las siguientes oraciones a fórmulas de lógica de predicados. Suponga que el dominio del discurso son los seres humanos.

Necesitamos una expresión que evalúe si alguien ama a alguien, entonces denotamos Lxy, para una "x" que ama a "y", donde L es abreviación de "Love". Además de B y G, que ya mencione anteriormente que evalúan si se es niño o niña.


1. Algún niño no ama a todas las niñas. (Some boy doesn’t love all girls)

∃x(Bx ^ ∀y(Gy ^ ¬Lxy))

Se evalúa si algún "x" es un niño, y si para toda "y" que resulte ser niña, "x" no ama a toda "y".


2. Todo niño que ama a una niña es también amado por alguna niña. (Every boy who loves a girl is also loved by some girl)

∀x((Bx ^ ∃y(Gy ^ Lxy)) ⇒ ∃z(Gz ^ Lzx))

La primer parte es parecida al anterior, pero ahora se habla de "todo niño" lo que nos hace cambiar el cuantificador, y quitamos la negación en L, porque ahora se dice que el niño ama a la niña. Para la segunda parte se dice que el niño "x" es amado también por una niña, y necesitamos una variable más, porque la niña "y" que el niño "x" ama, puede no ser la misma niña que ama a ese niño "x". Se agrega el signo condicional entre las dos partes, ya que la primer parte implica que la segunda también sea cierta.


3. Toda niña que ama todos los niños no ama a todas las niñas. (Every girl who loves all boys does not love every girl)

∀x((Gx ^ ∀y(By ⇒ Lxy)) ⇒ ∀z(Gz ^ ¬Lzx))

Aquí la primera parte de la oración implica a la segunda, y se traduce como, toda niña "x" que ama a niños "y", entonces niña "y" no ama a niñas "z". Otra forma de entender la oración después de haberla escrito en fórmula lógica, es que si una niña ama a los niños, se sabe que esa niña no ama a las niñas.


4. Ninguna niña quién no ama a un niño ama una niña que ama a un niño. (No girl who does not love a boy loves a girl who loves a boy)

∀x(((Gx ^ ∀w(Bw ^ ¬Lxw)) ^ ∀y(Gy ^ ∃z(Bz ^ Lyz))) ⇒ ¬Lxy)

Gx ^ ∀w(Bw ⇒ ¬Lxw): una niña "x" que no ama a todo niño "w".
Gy ^ ∃z(Bz ^ Lyz): una niña "y" que ama a un niño "z".
¬Lxy: si los dos anteriores se cumplen, entonces la niña "x" no ama a la niña "y", y es ahí donde se aplica la negación que refiere a "ninguna niña" (ninguna niña "x" ama a niña "y").


Páginas consultadas:
The World According to Predicate Logic

1 comentario:

  1. Quito un punto por la posición equivocada de la negación en los problemas 1 & 3. 9 pts.

    ResponderEliminar

Nota: solo los miembros de este blog pueden publicar comentarios.