3.0 Cuantificadores de Lógica de Primer Orden

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 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 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)

Para saber más sobre el tema, dar click en la siguiente liga:

https://es.wikipedia.org/wiki/L%C3%B3gica_de_primer_orden#Cuantificadores

2.9 Lógica de Primer Orden

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.

         La lógica de primer orden tiene el poder expresivo suficiente para definir a prácticamente todas las matemáticas.

Para saber más sobre el tema, dar click en la siguiente liga:
https://es.wikipedia.org/wiki/L%C3%B3gica_de_primer_orden

2.8 Lógica Proposicional

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.

Para saber más sobre el tema, dar click en la siguiente liga:
https://es.wikipedia.org/wiki/L%C3%B3gica_proposicional

2.7 Unificación

Unificación

La unificación se realiza, para cada predicado, de izquierda a derecha, y para cada conjunto de predicados, de arriba a abajo. Se pueden unificar variables con constantes, siempre que la variable no esté instanciada. Si la variable está instanciada, el hecho de hacer unificación entre ambas se corresponde con la situación de unificación de dos constantes. Para que dos constantes se puedan unificar ambas han de ser iguales.

Veamos en la Tabla 4 algunos casos que muestran elfuncionamiento de la unificación.

Variable no instanciada se intenta unificar con cualquier átomo ÉXITO X=5 Variable instanciada se intenta unificar con cualquier átomo distinto al valor que contiene FAIL X que contiene 5, X=6 Constante se intenta unificar con otra constante distinta FAIL 5=6 Expresiones se intentan comparar mediante símbolos de comparación que no "evalúan" y no coinciden totalmente, incluido el orden FAIL 5+3=3+5 Variable se intenta instanciar dos veces en la misma ejecución del programa. En el segundo intento de instanciación FAIL X=6, X=7

Tabla 4

Vemos que las instanciación es un caso de unificación en la que a una variable no instanciada se le asigna un valor.

También podemos observar que no es necesario definir los tipos de las variables locales usadas dentro de cada regla de inferencia. Cuando las variables se instancian a un valor, entonces todas las operaciones que se realicen con dicho valor deberán tener en cuenta el tipo especificado. Por ejemplo, si una variable se instancia al valor 5, todas las comparaciones posteriores se harán con números y no con átomos del tipo pepe, blas ó similar.

El proceso de unificación intenta casar un predicado con otro para comprobar si son absolutamente iguales, cuando es posible hacer sustituciones, éstas se realizan de manera que los predicados que se están unificando se tornen completamente iguales y proporcionen un resultado de ÉXITO.

Para saber más sobre el tema, dar click en la siguiente liga:

http://www.uhu.es/nieves.pavon/pprogramacion/temario/tema1/tema1.html#_Toc495042878

2.6 Backtracking

Vuelta atrás (backtracking)

         En los lenguajes de programación antes mencionados, las instrucciones se ejecutan normalmente en orden secuencial, es decir, una a continuación de otra, en el mismo orden en que están escritas, que sólo varía cuando se alcanza una instrucción de control (un bucle, una instrucción condicional o una transferencia).

         Los programas en Prolog se componen de cláusulas de Horn que constituyen reglas del tipo "modus ponendo ponens", es decir, "Si es verdad el antecedente, entonces es verdad el consecuente". No obstante, la forma de escribir las cláusulas de Horn es al contrario de lo habitual. Primero se escribe el consecuente y luego el antecedente. El antecedente puede ser una conjunción de condiciones que se denomina secuencia de objetivos. Cada objetivo se separa con una coma y puede considerarse similar a una instrucción o llamada a procedimiento de los lenguajes imperativos. En Prolog no existen instrucciones de control. Su ejecución se basa en dos conceptos: la unificación y el backtracking.

         Gracias a la unificación, cada objetivo determina un subconjunto de cláusulas susceptibles de ser ejecutadas. Cada una de ellas se denomina punto de elección. Prolog selecciona el primer punto de elección y sigue ejecutando el programa hasta determinar si el objetivo es verdadero o falso.

En caso de ser falso entra en juego el backtracking, que consiste en deshacer todo lo ejecutado situando el programa en el mismo estado en el que estaba justo antes de llegar al punto de elección.          Entonces se toma el siguiente punto de elección que estaba pendiente y se repite de nuevo el proceso. Todos los objetivos terminan su ejecución bien en éxito ("verdadero"), bien en fracaso ("falso").

Para saber más sobre el tema, dar click en la siguiente liga:
https://es.wikipedia.org/wiki/Prolog

2.5 Prolog

Prolog 

         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 y Philippe 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.

         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,6 hasta que en 1995 se estableció un estándar ISO (ISO/IEC 13211-1), llamado ISO-Prolog.

Prolog se enmarca en el paradigma de los lenguajes lógicos y declarativos, lo que lo diferencia enormemente de otros lenguajes más populares tales como Fortran, Pascal, C o Java.

Para saber más sobre el tema, dar click en la siguiente liga:

https://es.wikipedia.org/wiki/Prolog

2.4 Búsqueda Heurística

Búsqueda Heurística

         Los métodos de búsqueda heurísticas (del griego heuriskein, que significa encontrar) están orientados a reducir la cantidad de búsqueda requerida para encontrar una solución. Cuando un problema es presentado como un árbol de búsqueda el enfoque heurístico intenta reducir el tamaño del árbol cortando nodos pocos prometedores. Estos métodos se llaman métodos fuertes porque ellos son más poderosos que los estudiados hasta aquí al incorporar conocimiento heurístico o heurística. Hay una contradicción entre generalidad y potencia en el sentido que los métodos débiles son esencialmente aplicables universalmente mientras que los fuertes son menos universales en su aplicabilidad y el conocimiento o heurística usada en un problema dado puede no ser totalmente aplicable o ser inaplicable en otro dominio o tarea.

         La Heurística no garantiza que siempre se tome la dirección de la búsqueda correcta, por eso este enfoque no es óptimo sino suficientemente bueno. Frecuentemente son mejores los métodos heurísticos que los métodos de búsquedas a ciegas. Las desventajas y limitaciones principales de la heurística son:

La flexibilidad inherente de los métodos heurísticos pueden conducir a errores o a manipulaciones fraudulentas.

         Ciertas heurísticas se pueden contradecir al aplicarse al mismo problema, lo cual genera confusión y hacen perder credibilidad a los métodos heurísticos.

Soluciones óptimas no son identificadas. Las mejoras locales determinadas por las heurísticas pueden cortar el camino a soluciones mejores por la falta de una perspectiva global. La brecha entre la solución óptima y una generada por heurística puede ser grande.

El significado técnico de la palabra heurística ha variado en la historia de la Inteligencia Artificial. En 1957, George Polya en su libro "How to solve it" usó este término para referirse al estudio de métodos para descubrir e inventar técnicas de solución de problemas.

En otras ocasiones se ha usado como un término opuesto a algorítmico. Por ejemplo, Newell, Shaw y Simón plantearon en 1993 "Un proceso que puede resolver un problema dado, pero no ofrece garantía de hacerlo, es llamado una heurística para ese problema".

Para saber más sobre el tema, dar click en la siguiente liga: http://www.monografias.com/trabajos75/busqueda-heuristica/busqueda-heuristica.shtml#ixzz49XkGMbpG