Listas en Prolog

Una lista en Prolog (como en casi cualquier lenguaje que use listas) se divide en dos partes: (1) Cabeza. Es el primer elemento de la lista. Puede ser un ´atomo o una lista, pero a fin de cuentas es el primer elemento de la lista original. (2) Cola. Es el resto de los elementos de una lista, es de nuevo una lista. Ejemplos: (1) L=[perro, gato, raton, queso] (a) cabeza= perro (b) cola=[gato, raton, queso] (2) L=[[perro, gato], [raton, queso]] (a) cabeza=[perro, gato] (b) cola=[[raton, queso]] (3) L=[perro] (a) cabeza=perro (b) cola=[] la lista vac´ıa (4) L=[] (a) cabeza= NO (b) cola=[] la lista vac´ıa

En esta secci´on se ver´a el uso de las listas para determinar la existencia de un elemento en la lista e incluso el uso de recursividad. En primer lugar, la existencia de un elemento en la lista se puede verificaci con una regla como: pertenece(E,L):-L=[E| ]. Que dice que el elemento E pertenece a la lista L si L se puede hacer teniendo una lista cuya cabeza sea E y cualquier cola, incluso la lista vac´ıa. Pero esto solamente nos asegura la pertenencia de la cabeza de la lista, no si un elemento est´a dentro de ella. Para esto se necesita una segunda cl´ausula recursiva: pertenece(E,[ |T]):-pertenece(E,T). Es decir “un elemento E pertenece a una lista compuesta de cualquier cabeza y una cola T, si ese mismo elemento E es la cabeza del resto de la lista T”. As´ı se tiene el siguiente programa en Prolog que verifica la pertenencia de un elemento en una lista: pertenece(E,L):-L=[E|_]. pertenece(E,[_|T]):-pertenece(E,T). :-pertenece(E,[a,b,c,d,e].)

 

Lógica de primer orden
La lógica de primer orden, también llamada lógica de predicados o cálculo de predicados, es un sistema formal diseñado para estudiar la inferencia en los lenguajes de primer orden. Los lenguajes de primer orden son, a su vez, lenguajes formales con cuantificadores que alcanzan sólo a variables de individuo, y con predicados y funciones cuyos argumentos son sólo constantes o variables de individuo.

CUANTIFICADORES

Considérese ahora la siguiente expresión matemática:

x > 3

Esta expresión no es ni verdadera ni falsa, y parece que no lo será hasta que no reemplacemos a la x por algún número cualquiera. Sin embargo, también es posible dar un valor de verdad a la expresión si se le antepone un cuantificador. Un cuantificador es una expresión que afirma que una condición se cumple para un cierto número de individuos.⁵ En la lógica clásica, los dos cuantificadores más estudiados son el cuantificador universal y el cuantificador existencial.  El primero afirma que una condición se cumple para todos los individuos de los que se está hablando,⁵ y el segundo que se cumple para al menos uno de los individuos.⁵ Por ejemplo, la expresión "para todo x" es un cuantificador universal, que antepuesto a "x < 3", produce:

Para todo x, x < 3

Esta es una expresión con valor de verdad, en particular, una expresión falsa, pues existen muchos números (muchos x) que son mayores que tres. Anteponiendo en cambio la expresión "para al menos un x", un cuantificador existencial, se obtiene:

Para al menos un x, x < 3

La cual resulta ser una expresión verdadera.

Adviértase ahora, sin embargo, que el valor de verdad de las dos expresiones anteriores depende de qué números se esté hablando. Si cuando se afirma "para todo x, x < 3", se está hablando sólo de los números negativos, por ejemplo, entonces la afirmación es verdadera. Y si al afirmar "para al menos un x, x < 3" se está hablando solamente de los números 3, 4 y 5, entonces la afirmación es falsa. En lógica, a aquello de lo que se está hablando cuando se usa algún cuantificador, se lo llama el dominio de discurso.

Esta maquinaria puede adaptarse fácilmente para formalizar oraciones con cuantificadores del lenguaje natural. Tómese por caso la afirmación "todos son amigables". Esta oración puede traducirse así:

Para todo x, x es amigable.

Y una oración como "alguien está mintiendo" puede traducirse:

Para al menos un x, x está mintiendo.

También es frecuente traducir esta última oración así:

Existe al menos un x, tal que x está mintiendo.

A continuación se formalizan ambas oraciones, introduciendo a la vez la notación especial para los cuantificadores:

Para todo x, x es amigable.	∀x A(x)
Existe al menos un x, tal que x está mintiendo.	∃x M(x)

Lógica proposicional                                               

La lógica proposicional o lógica de orden cero es un sistema formal cuyos elementos más simples representan proposiciones, y cuyas constantes lógicas, llamadas conectivas, representan operaciones sobre proposiciones, capaces de formar otras proposiciones de mayor complejidad.

La lógica proposicional trata con sistemas lógicos que carecen de cuantificadores, o variables interpretables como entidades. En lógica proposicional si bien no hay signos para variables de tipo entidad, sí existen signos para variables proposicionales (es decir, que pueden ser interpretadas como proposiciones con un valor de verdad de definido), de ahí el nombre proposicional. La lógica proposicional incluye además de variables interpretables como proposiciones simples signos para conectivas lógicas, por lo que dentro de este tipo de lógica puede analizarse la inferencia lógica de proposiciones a partir de proposiciones, pero sin tener en cuenta la estructura interna de las proposiciones más simples.

TABLAS DE VERDAD

La tabla de verdad (también conocida como tabla de valores de verdad) presenta una proposición compuesta y su valor de verdad para cada una de las combinaciones posibles que se puedan dar con sus elementos. Su autor fue el filósofo y científico norteamericano Charles Sanders Peirce, también conocido como el máximo representante de la semiótica moderna, y la publicó a mediados de 1880.

Los operadores utilizados en una tabla de verdad son:

• Negación: al ejecutarlo sobre un valor de verdad determinado, arroja el opuesto (si originalmente era verdadero, devuelve falso, y viceversa);
• Conjunción: se utiliza para operar con dos valores de verdad, generalmente de dos proposiciones diferentes, y devuelve verdadero cuando las dos lo son, y falso para el resto de los casos;
• Disyunción: similar a la conjunción, pero le basta que una de las dos proposiciones tenga valor verdadero para devolver tal resultado;
• Condicional: también conocido por el nombre de implicación, toma dos proposiciones y arroja falso solamente cuando la primera devuelve verdadero y la segunda, falso. Para los casos restantes, su resultado es verdadero;
• Bicondicional: opera sobre los valores de verdad de dos proposiciones y devuelve verdadero si ambas tienen el mismo valor y falso en el caso contrario.

AGENTES BASADOS EN CONOCIMIENTOS

Se introduce el diseño de un agente basado en el conocimiento Se presenta un lenguaje lógico sencillo pero insuficiente, el de la lógica propositiva, Se ejemplifica con un agente capaz de desempeñarse bien en el mundo de Wumpus, siendo Wumpus un juego que provoca adicción. En este capítulo se aprende a diseñar agentes que – construyen representaciones del mundo, – derivan nuevas representaciones del mundo por inferencia y – usan esas nuevas representaciones para saber qué hacer

función – Un agente conocimiento-intensivo tiene como componente seminal una base de conocimientos. – Una base de conocimientos es un conjunto de representaciones de hechos del mundo. – Cada una de esas representaciones se llama una “oración”. – Las oraciones se expresan en un lenguaje representacional del conocimiento.

El agente opera como sigue (TELL and ASK) 1. Le dice a la base su PERCEPCIÓN – (añade oraciones a la base) 2. Le pregunta a la base qué ACCIÓN encarar – (contesta preguntas de la base) – (mientras, opera un MOTOR DE INFERENCIAS) 3. Ejecuta la ACCIÓN

CARACTERISTICAS DE PROLOG

Existen dos tipos de cláusulas: Hechos y Reglas. Una regla es del tipo:


Cabeza :- Cuerpo.


y se lee como "La cabeza es verdad si el cuerpo es verdad". El cuerpo de una regla consiste en llamadas a predicados, que son llamados los objetivos de las reglas. El predicado ,/2 (es decir, un operador de paridad 2 (que recibe 2 argumentos) y de nombre , ) denota conjunción de objetivos, y el operador ;/2 denota disyunción. Conjunciones y disyunciones pueden sólo aparecer en el cuerpo, no en la cabeza de la regla. En realidad la disyunción no es un operador básico o predefinido, sino que está meta-programado así:

';' (A,_) :- A.

';' (_,B) :- B.


Las cláusulas sin cuerpo (es decir, antecedente) son llamados hechos porque siempre son ciertos. Un ejemplo de un hecho es:

gato(tom).

que es equivalente a la regla:

gato(tom) :- true.

El predicado predefinido true/0 siempre es verdad.

Dado el hecho anterior, se puede preguntar:

¿ es tom un gato?

?- gato(tom).

Yes

¿ que cosas son gatos?

?- gato(X).

X = tom

Debido a la naturaleza relacional de muchos predicados, pueden ser usados revertidos sus argumentos. Por ejemplo, length/2 puede ser usado para determinar el tamaño (longitud) de una lista: length([a,b,c], L), así como para generar un esqueleto de lista para un largo dado (length(X, 5)). Similarmente, append/3 puede ser usado también para unir o anexar dos listas: append([a,b], [c,d], X), así como para dividir una lista en dos partes: append(X, Y, [a,b,c,d]). Todo depende de qué argumentos sean variables libres y cuáles sean instanciados. En analogía con la programación imperativa, las variables libres son argumentos de salida y el resto son argumentos de entrada. Pero en Prolog, a diferencia de los lenguajes imperativos, dicho rol es intercambiable en la mayoría de los predicados. Esta característica se denomina reversibilidad, y las combinaciones válidas de argumentos de salida o entrada se denomina modos de uso. Por ejemplo, el predicado length/2 es reversible y tiene tres modos de uso: los dos argumentos instanciados, el primer argumento instanciado pero el otro no, y viceversa. El modo de uso con los dos argumentos sin instanciar no tiene mucho sentido, pero podría ser admitido según algunas implementaciones, en tal caso, generaría todas los esqueletos de lista de todas las longitudes posibles...

Por esta razón, una biblioteca relativamente pequeña de predicados basta para muchos programas en Prolog. Todos los predicados pueden también ser usados para realizarpruebas unitarias: las consultas pueden ser incrustados en programas y permitir pruebas automáticas de regresión en tiempo de compilación.

Como un lenguaje de propósito general, Prolog también posee varios predicados predefinidos para interacción con el sistema operativo, como entrada/salida, gráficos y comunicaciones de datos. Estos predicados no tienen un significado relacional y son sólo útiles por los efectos laterales que exhiben en el sistema. Por ejemplo, el predicadowrite/1 muestra un término en la pantalla, pero no tiene relevancia su valor de verdad o falsedad.

PROLOG

El Prolog (o PROLOG), proveniente del francés PROgrammation en LOGique,1 es un lenguaje para programar artefactos electrónicos mediante el paradigma lógico con técnicas de producción final interpretada. Es bastante conocido en el área de la Ingeniería Informática para investigación en Inteligencia Artificial.

Se trata de un lenguaje de programación ideado a principios de los años 70 en la Universidad de Aix-Marseille I (Marsella, Francia) por los estudiantes Alain Colmerauer yPhilippe Roussel. Nació de un proyecto que no tenía como objetivo la traducción de un lenguaje de programación, sino la clasificación algorítmica de lenguajes naturales. Alain Colmerauer y Robert Pasero trabajaban en la parte del procesado del lenguaje natural y Jean Trudel y Philippe Roussel en la parte de deducción e inferencia del sistema. Interesado por el método de resolución SL, Trudel persuadió a Robert Kowalski para que se uniera al proyecto, dando lugar a una versión preliminar del lenguaje Prolog a finales de 19712 y apareciendo la versión definitiva en 1972.3 Esta primera versión de Prolog fue programada en ALGOL W.

Inicialmente se trataba de un lenguaje totalmente interpretado hasta que, en 1983, David H.D. Warren desarrolló un compilador capaz de traducir Prolog en un conjunto de instrucciones de una máquina abstracta denominada Warren Abstract Machine, o abreviadamente, WAM. Desde entonces Prolog es un lenguaje semi-interpretado.



Si bien en un principio se trataba de un lenguaje de uso reducido, la aparición de intérpretes del mismo para microordenadores de 8 bits (ej: micro-PROLOG) y para ordenadores domésticos de 16 bits (ej: Turbo Prolog de Borland, entre otros muchos) a lo largo de la década de 1980 contribuyó notablemente a su popularización.4 Otro importante factor en su difusión fue la adopción del mismo para el desarrollo del proyecto de la quinta generación de computadoras a principios de la década de los 80,5 en cuyo contexto se desarrolló la implementación paralelizada del lenguaje llamada KL1 y del que deriva parte del desarrollo moderno de Prolog.

Arbolo de Búsqueda

Representación de un conjunto de estados nos permite mostrar los estados a través de nodos.

También es representado por punteros.

Conformado por:

· Nodo Raíz: estado Inicial

· Expansión: es la generación de los nodos siguientes.

· Nodo hoja: cuando ya no se puede expandirse

· Estado Meta: cuando ya hayamos encontrado el estado meta entonces podremos marcar como terminado.

El estado meta puede ser implícito o explícito.