Ingeniería Informática

Estructuras de Datos Laboratorio Curso 1998/99

Universitat de València

PRÁCTICA N 3: 2 sesiones

Motor de Inferencia de Lógica Proposicional
Utilización del Tipo Pila de Enunciados y Tabla de Cláusulas

1. Lógica proposicional

En esta práctica se debe realizar un mecanismo de inferencia o resolución de reglas mediante el uso de la estructura tabla (para almacenar las reglas y los hechos) y una estructura pila (para realizar la inferencia).

• Una regla es una implicación lógica que consta de una conclusión y un cierto número de antecedentes o premisas. Ejemplo:

A Ù B Ù C ® X

donde X es la conclusión y A, B y C son antecedentes o premisas

La misma regla también la podemos representar mediante la siguiente notación:

X :- A, B, C

Esta regla puede interpretarse como: "Para que se cumpla X es necesario que se cumpla A, B y C".

• Un hecho es una afirmación que consideramos cierta. Ejemplo:

A

Este hecho se interpreta como "A se cumple".

Un hecho es un caso particular de regla sin premisas.

A los hechos y las reglas se les conoce como cláusulas.

A partir de lo que conocemos (los hechos) podemos deducir (mediante las reglas) ciertas consecuencias.

2. Unidad para la especificación de la estructura de datos "Pila de Proposiciones"

Definiremos una proposición como una cadena donde guardaremos el texto que la identifica. Los tipos asociados a la Pila de Proposiciones serán:

   Type
      Proposicion = String[20];

      Pila = Record
                Info: Array [1..MAX_PILA] Of Proposicion;
                Cima: 0..MAX_PILA;
             End;

Y las operaciones que definiremos sobre la pila serán, tal y como se ha visto en clase, las siguientes:

   Procedure Iniciar_Pila ( Var s: Pila );
   Function  Vacia_Pila   (     s: Pila                        ): Boolean;
   Function  Apilar       ( Var s: Pila;     prop: Proposicion ): Boolean;
   Function  Desapilar    ( Var s: Pila; Var prop: Proposicion ): Boolean;
   Function  Cima_Pila    ( Var s: Pila; Var prop: Proposicion ): Boolean;

3. Unidad para la especificación de la estructura de datos "Tabla de clausulas"

Definiremos el tipo cláusula con la siguiente estructura:

   Const
      Max_Premisas = 3; (* Limitamos a 3 los antecedentes de cada regla *)
      Max_Clausulas = 20;

   Type
      Indice = 1..Max_Clausulas;

      Premisa = Array [1..Max_Premisas] Of Proposicion;

      Clausula = Record
                    Conclusion : Proposicion;
                    Antecedentes: Premisa;
                 End;

      Tabla = Record
                 Info: Array [Indice] Of Clausula;
                 N: 0..Max_Clausulas;
              End;

Las operaciones que deberemos implementar sobre la tabla serán:

   Procedure Iniciar_Tabla     ( Var t: Tabla );
   Function  Insertar_Final    ( Var t: Tabla; clau: Clausula ): Boolean;
   Function  Buscar_Conclusion (     t: tabla; conc: Proposicion;
                                                            var clau: Clausula ): Boolean;
   Function  Maximo_Indice     (     t: Tabla ): Integer;
   Function  Consultar_Tabla   (     t: Tabla; ind: Indice, Var clau: Clausula ): Boolean;

4. Realización de la Práctica

Tras implementar las unidades, habrá que escribir un programa que realice las siguientes tareas:

1. Insertar una serie de cláusulas en la tabla de cláusulas.
2. Mostrar los hechos y las reglas guardadas en la tabla.
3. Dada una cierta proposición, introducida por teclado, decir si es verdadera o falsa utilizando para ello el mecanismo de resolución.

Mecanismo de Resolución

Supongamos que queremos demostrar la veracidad de una cierta a proposición X, mediante unas cláusulas guardadas en la tabla de cláusulas.

1. Apilamos X.

2. Desapilamos el primer elemento que aparezca en la pila, Cima, y lo buscamos como conclusión en la tabla de cláusulas.
   1. Si la conclusión no se encuentra en la tabla entonces salir con negación.

   2. Sino, apilamos cada una de las premisas que aparezcan en la cláusula (si es un hecho, no aparecerán premisas, y no apilaremos nada).

3. Si la pila está vacía, salir con éxito, sino volver al paso 2.

Supongamos que el conjunto de cláusulas es el siguiente:

   Z :- A, B, C
   A :- F, G
   F
   B
   G
   C

Queremos demostrar la veracidad de la proposición Z.

Apilamos Z, y aplicando el algoritmo previamente enunciado tendríamos los siguientes estados de la pila:

C

B

B

G

Z

A

A

A

F

F

En este caso la pila ha quedado vacía y se ha demostrado la veracidad de Z.

Comprobación del Programa

Comprobaremos el funcionamiento del programa introduciendo las siguientes cláusulas:

Cláusulas:

     Mal_Tiempo :- Llueve, Hace_Frio, Humedad.
     Llueve :- Nublado, Cae_Agua.
     Hace_Frio :- Temperatura_Baja, Viento.
     Nieva :- Nublado, Cae_Nieve.
     Humedad.
     Cae_Agua.
     Temperatura_Baja.
     Viento.
     Nublado.

Y comprobando la veracidad de las siguientes cláusulas:

     Mal_Tiempo
     Nieva

NOTA: Se recuerda a los alumnos que las normas de corrección siguen vigentes y que por lo tanto se tendrán en cuenta a la hora de evaluar la práctica. Uno de los puntos es la presentación correcta de las prácticas siguiendo la Guía de Estilo de Pascal.

Recordar también la necesidad de entregar una hoja con las tareas que se van a realizar en la práctica para poder acceder al laboratorio.

ENTREGA DE PROGRAMAS: Al finalizar la segunda sesión de prácticas.

---

Última actualización: 24 de Marzo de 1999