lunes, 20 de mayo de 2019

Lógica proposicional


Lógica Proposicional


Es una rama de la lógica clásica que estudia las variables proposicionales o sentencias lógicas, sus posibles implicaciones, evaluaciones de verdad y en algunos casos su nivel absoluto de verdad. Algunos autores también la identifican con la lógica matemática o la lógica simbolice, ya que utiliza una serie de símbolos especiales que lo acercan al lenguaje matemático.
Proposiciones

Tautología: se define tautología o validez a aquella formula que siempre es verdadera.

Contradicción: es una proposición que siempre es falsa para todos los valores de verdad. Para cualquier valor de verdad de las proposiciones, sea cual sea el resultado de la formula lógica estudiada siempre va a ser falso.

Conjunción: es aquella formula que es falsa o verdadera. Las expresiones de las que depende la validez de los argumentos se definen constante lógicas.

Conectores

Negación: no -> >, ~

En lógica y matemática, la negación, también llamada complemento lógico, es una operación sobre proposiciones, valores de verdad, o en general, valores semánticos. Intuitivamente, la negación de una proposición es verdadera cuando dicha proposición es falsa, y viceversa. En lógica clásica la negación está normalmente identificada con la función de verdad que cambia su valor de verdadero a falso y viceversa.

Conjunción: Y ∧, Solamente si las componentes de la conjunción son ciertas, la conjunción es cierta.

Disyunción: O ∨,

La disyunción solamente es falsa si lo son sus dos componentes.

Condicional: ⇒ entonces

Típicamente los valores de verdad de dos proposiciones, devolviendo el valor de verdad falso sólo cuando la primera proposición es verdadera y la segunda falsa.

Bicondicional: ⇔ si solo sí.

El Bicondicional o doble implicación es un operador que funciona sobre dos valores de verdad, típicamente los valores de verdad de dos proposiciones, devolviendo el valor de verdad verdadero cuando ambas proposiciones tienen el mismo valor de verdad, y falso cuando sus valores de verdad difieren.
Proposiciones

Variables: En el lenguaje simbólico de la lógica de proposiciones, a los enunciados simples, atómicos o elementales son los que no pueden descomponerse en otros más simples. Se les llama variables, y se escriben con las letras minúsculas del final del abecedario: “p”, “q”, “r”, “s”… para los casos particulares, o con las letras en mayúscula del principio del alfabeto cuando son casos generales: “A”, “B”, “C”, “D”…

Además de las variables, la lógica proposicional tiene otros elementos en su alfabeto: las constantes lógicas y los símbolos auxiliares que forman los enunciados compuestos.

Algunas de las marcas léxicas del lenguaje natural, se traducen con uno de las cinco constantes lógicas siguientes:

¬ NEGACIÓN: No

٧ DISYUNCIÓN INCLUSIVA: o, o bien, tanto si… como si,

٨ CONJUNCIÓN: y, e, o ni (=y no)

→ CONDICIONAL: si…. entonces

↔ BICONDICIONAL: si y solo si


Tabla de la Verdad

La negación: Cuando la variable es verdadera al negarla se convierte en falsa, y si es falsa, al negarla se hace verdadera.



sábado, 18 de mayo de 2019

Características de SWI-PROLOG


SWI-Prolog le proporciona un entorno de desarrollo completo y sólido para el lenguaje de programación lógica Prolog, que está destinado a la lingüística computacional y aplicaciones de inteligencia artificial.
Basándose en una máquina virtual Prolog para definir las instrucciones, SWI-Prolog cuenta con un compilador más rápido y el modo de depuración sólo reduce la velocidad del sistema por un bit.
La aplicación viene con una interfaz flexible e intuitiva que le permite trabajar con el código C / C ++, proporcionando soporte para aplicaciones de gran tamaño y un número ilimitado de valores enteros sin bajar el rendimiento.
Tanto el código estático y dinámico se puede indexar fácilmente ante cualquier argumento, mientras que el depurador a nivel de fuente compatible con gráficos a través XPCE.
SWI-Prolog Prolog tiene una cruzada Referente, un perfilado de ejecución a las estadísticas de instrucción de salida, así como una herramienta de comprobación de errores. El paquete también incluye una colección de bibliotecas que los programadores pueden encontrar útiles, es decir, los componentes de las reglas de restricción de manipulación, las bibliotecas de interfaz HTML, XML, RDF y programas de análisis, una biblioteca de servidor web para los esfuerzos de gestión de sesiones, HTML y HTTP de autorización y así sucesivamente.
El conjunto de características de depuración avanzada comprende un editor de espionaje punto, un depurador excepción, un monitor de hilo y una herramienta de gestión de la dependencia.
El programa proporciona soporte para los juegos de caracteres Único de, lo que lo hace adecuado para la creación de aplicaciones basadas en la Web y multilingüe.
Con alta velocidad de compilación, SWI-Prolog puede ser de gran utilidad para los programadores de Prolog. Su gama de características son suficientes para satisfacer a los usuarios más experimentados, ya que se requiere conocimientos de programación avanzada con el fin de usarlo.





Estrategias de búsqueda

Búsqueda preferente por amplitud: 

En esta búsqueda todos los nodos que están en la profundidad d del árbol de búsqueda se expanden antes de los nodos que estén en la profundidad d+1.

• Si son varias las soluciones, este tipo de búsqueda permitirá siempre encontrar primero el estado meta más próximo a la raíz. 
• En esta búsqueda el tiempo y la cantidad de memoria necesaria crece exponencialmente con respecto a la profundidad. 
• Es óptima y completa.

Búsquedas de costo uniforme: 

En esta búsqueda se modifica la estrategia preferente por amplitud en el sentido de expandir siempre el nodo de menor costo en el margen (medido por el costo de la ruta g(n)) en vez del nodo de menor profundidad.

Este tipo de búsqueda permitirá siempre encontrar la solución mas barata siempre y cuando el costo de ruta nunca disminuya conforme avanzamos por la ruta.
En esta búsqueda el tiempo y la cantidad de memoria necesaria crece exponencialmente con respecto a la profundidad.

• Es óptima y completa.

Búsqueda preferente por profundidad:

En esta búsqueda siempre se expande uno de los nodos que se encuentren en los mas profundo del árbol. Solo si la búsqueda conduce a un callejón sin salida, ser revierte la búsqueda y se expanden los nodos de niveles menos profundos.

Esta búsqueda o se queda atorada en un bucle infinito y nunca es posible regresar al encuentro de una solución, o a la larga encontrará una ruta de solución mas larga que la solución óptima.

• En esta búsqueda el tiempo necesario crece exponencialmente con respecto a la profundidad, mientras que el espacio requerido en memoria lo hace en forma lineal

• No es óptima ni completa. 


Búsqueda limitada por profundidad: 

Esta búsqueda es similar a la búsqueda preferente por profundidad con la diferencia que se impone un límite a la profundidad máxima de una ruta.Se utilizan operadores que informan constantemente de la profundad del nodo. 


• En esta búsqueda el tiempo necesario crece exponencialmente con respecto a la profundidad, mientras que el espacio requerido en memoria lo hace en forma lineal

• No es óptima, pero si completa cuando la profundidad del límite es menor o igual a la profundidad de la solución. 
Búsqueda por profundización iterativa: 

Esta búsqueda es similar a la búsqueda limitada por profundidad con la diferencia que se repiten las búsquedas dando en cada iteración un valor distinto de profundiad para la misma.

En esta búsqueda el tiempo necesario crece exponencialmente con respecto a la profundidad, mientras que el espacio requerido en memoria lo hace en forma lineal
Es óptima y completa. 

Búsqueda bidireccional: 

Esta es una búsqueda que avanza a partir del estado inicial y que retrocede a partir de la meta y que se detiene cuando ambas búsquedas se encuentran en algún punto intermedio. 
En esta búsqueda el tiempo y el espacio requerido en memoria crecen exponencialmente con respecto a la mitad de la profundidad (bd/2). 
Es óptima y completa.

Cuantificadores de lógica de primer orden


Un cuantificador es un operador sobre un conjunto de individuos, se trata de un recurso expresivo que permite construir proposiciones sobre conjuntos o, dicho de otra forma, 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 solo 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 se puede adaptar fácilmente para formalizar oraciones con cuantificadores del lenguaje natural. Tómese por caso la afirmación "todos son amigables". Esta oración se puede traducir 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.    

4 métodos de búsqueda con los criterios que evalúan

Criterio con el que se relaciona
Comparación de Métodos de búsqueda
Completes: si garantiza o no encontrar la solución si es que existe.

·         Búsqueda por amplitud
·         Búsqueda por profundización iterativa
·         Búsqueda bidireccional
Complejidad espacial: cantidad de memoria necesaria para encontrar la solución.

·         Búsqueda por amplitud
·         Búsqueda por profundización iterativa
·         Búsqueda bidireccional
Complejidad temporal: cantidad de tiempo necesario para encontrar la solución.
·         Búsqueda por amplitud
·         Búsqueda limitada por profundidad
·         Búsqueda por profundización iterativa
·         Búsqueda bidireccional

Optimidad: si se encontrará o no la mejor solución en caso de que existan varias.

·         Búsqueda por amplitud

Lenguaje Prolog


¿Qué es el lenguaje Prolog?
Es un lenguaje de programación lógico e interpretado usado habitualmente en el campo de la Inteligencia artificial.


Historia
Prolog es un lenguaje de programación simple pero poderoso desarrollado en la Universidad de Aix-Marseille (Marsella, Francia) por los profesores Alain Colmerauer y Philippe Roussel, como una herramienta práctica para programación lógica. Nació de un proyecto que no tenía como objetivo la implementación de un lenguaje de programación, sino el procesamiento 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 1971 y apareciendo la versión definitiva en 1972. 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.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 1980, en cuyo contexto se desarrolló la implementación paralelizada del lenguaje llamada KL1 y del que deriva parte del desarrollo moderno de Prolog. Las primeras versiones del lenguaje diferían, en sus diferentes implementaciones, en muchos aspectos de sus sintaxis, empleándose mayormente como forma normalizada el dialecto propuesto por la Universidad de Edimburgo , hasta que en 1995 se estableció un estándar ISO (ISO/IEC 13211-1), llamado ISO-Prolog.