¿Como se usa la lógica en la programación? PT 2

En esta nueva entrega de Code Time continuamos explicando conceptos básicos que son importantes en la lógica. Hoy nos centraremos en algunos tipos de lógica y su uso tanto dentro de la programación como en mecanismos de razonamiento.

 

NOTA: Antes de continuar con esta nota te recomendamos que leas la entrada anterior y escuches su respectivo podcast. A lo largo de este artículo se supondrás ciertos temas ya expuestos. Si estás interesado en acceder al contenido sugerido puedes hacerlo mediante el siguiente enlace directo.

 

Listen to “Code Time (74): Tipos de lógica en la programación PT 2” on Spreaker.

Razonamientos empleando lógica proposicional

Hasta el momento definimos la lógica proposicional como una forma de modelar problemas. De esto se desprende una pregunta elemental ¿y ahora qué? ¿Cómo razonamos con esto?.

Para poder realizar razonamientos sobre los modelos que podamos construir existen dos formas principales que detallaremos a continuación.

Justificación Semántica

Esta forma de trabajar consiste en verificar que la fórmula de PROP que codifica el razonamiento es una tautología.

• { (p1 y p2 y … pn) -> C }

Donde pi son las premisas y C es la conclusión. Al realizar el razonamiento lo que se intenta mostrar es que sin importar el resto proposiciones se cumple la propiedad.

A la hora de enseñar esta estrategia suelen emplearse tablas de verdad donde se toman las combinaciones de las proposiciones y se halla que siempre se llega a que la conclusión vale.

Justificación Sintáctica

A diferencia de lo visto en el caso anterior, esta metodología tiene como base dar una demostración matemática que:

• Llegue a la conclusión a partir de las hipótesis.
• Esté constituida de pasos debidamente justificados.

Las reglas de inferencia pertenecen a las especificaciones del sistema lógico, es decir, al metalenguaje. Son reglas sintácticas que permiten deducir a partir de ciertas formas proposicionales otras formas proposicionales.

La prueba consiste en un encadenamiento de pasos de reglas de inferencia que permiten llegar a la conclusión. Algunos ejemplos de reglas son los siguientes:

• Modus Ponens: A -> B, A => B
• Modus Tollens: A -> B, (no B) => (no A)
• Silogismo Disyuntivo: A o B, (no A) => B
• Silogismo Hipotético: A -> B, B -> C => A -> C
• …

¿Qué forma es mejor?

Ambas formas de trabajar son válidas y matemáticamente hablando son equivalentes por lo que da lo mismo cuál escoger. De hecho es posible combinarlas para resolver los problemas más eficientemente.

Aún así existen ciertas diferencias. La forma en la que planteamos estas herramientas es suponiendo que un ser humano realiza los razonamientos, pero a nosotros nos interesan las computadoras. Es posible crear programas para automatizar el proceso de demostración pero hay que tener ciertas consideraciones.

La demostración semántica se basa en el uso de tablas de verdad, equivalencias lógicas y siempre hay un método que responde si un razonamiento es válido o no. Como desventaja tenemos que las tablas de verdad ocupan mucha memoria. Se que podría parecer poco pero si consideramos que agregar una nueva variable o proposición al juego implica duplicar el tamaño de ta tabla, trabajar con un problema que tiene 1.000.000 de variables se hace increíblemente pesado.

Por otra parte la demostración sintáctica es una prueba formal y esto requiere de ingenio. Es aquí donde entra el factor humano. Una máquina como tal puede realizar los pasos pero debe escogerlos en el orden correcto ya que un solo cambio puede llevar a demorar el cálculo mucho más o, peor aún, entrar en bucles infinitos con lo que no siempre habría una solución.

Así que como podemos ver ambas formas de pensar tienen sus ventajas y desventajas. Para lo que estrategia para aprender a resolver problemas respecta se recomienda el uso de la demostración sintáctica. Puede llegar a ser divertido romperse la cabeza un rato en alguna demostración. Realizar estas tareas abre la mente, a veces literalmente.

Las limitaciones de la lógica proposicional

Esta forma de modelar y razonar nos vino muy bien y demostró ser relativamente simple de entender. No obstante hay que destacar que cuenta con ciertas desventajas bastante notables. La más notoria es por ejemplo que no tiene el suficiente poder expresivo para modelar, por ejemplo, la siguiente oración:

• Todos los perros son animales.

Aquí vemos un típico caso de una afirmación universal, o sea, refleja una condición que se cumple siempre. ¿Como podemos modelar esta clase de problemas? La respuesta es simple, hay que utilizar otra forma de modelar.

La lógica de predicados

Para aumentar el poder expresivo de la lógica proposicional presentaremos la lógica de predicados. Está contiene todos los elementos presentados hasta el momento pero además incorpora:

• Cuantificadores universales y existenciales.
• Funciones.
• Predicados.
• Varaibles.

¿Por qué se llama lógica de predicados?

Este tipo de lógica lleva este nombre ya que uno de los elementos que se utilizan se llama predicado. Los predicados son funciones especiales que toman un valor y retornan un booleano. Son muy útiles para determinar el valor de verdad de algo. Esto lo veremos en un ejemplo.

Modelando con lógica de predicados

Dada la oración “Rex es un perro” podemos establecer distintos modelos válidos:

• Es(Rex, Perro)
• Es-Perro(Rex)
• Es-Rex(Perro)
• Perro(Rex)
• Rex(Perro)

Notaremos que en algunos casos no hay casi diferencias y justamente esa es la ventaja de poder crear los modelos. Es posible hacerlo como uno quiera o vea conveniente.

La grán diferencia que podremos notar con respecto a la lógica proposicional es que si escogieramos esta la oración entera sería una proposición. Esto que podría no parecer más simple acarrea la gran desventaja de que no permite hacer ningún trabajo algebraico. Es una simple unidad atómica. Ya por esto vemos que hay mucho más poder expresivo con esta nueva forma de trabajar.

Los cuantificadores

Uno de los elementos característicos de la lógica de predicados es el uso de cuantificadores. Estos sirven para establecer comportamientos sobre variables. Por ejemplo la cuantificación:

• ∀x (Perro(x) -> Mamifero(x))

Representa que todos los perros son mamíferos. El símbolo ∀ se lo emplea para indicar una cuantificación universal (para todo).

También existe otro cuantificador llamado existencial el cual sirve para indicar que una condición ocurre en al menos un caso. Por lo tanto si se cumple una cuantificación universal la existencial automáticamente vale. EJ:

• ∃x (Hombre(x) y Argentino(x))

Con esto reflejamos que existe al menos un hombre que es Argentino.

Demostraciones en lógica de predicados

Para realizar demostraciones podemos seguir utilizando las dos formas de trabajar que usabamos hasta ahora. Pero existe una gran traba: los cuantificadores. ¿Cómo demostramos que una condición se cumple sobre un cuantificador? Para esto debemos analizar los siguientes casos:

• Cuantificación Universal: Para demostrar esto es necesario realizar la prueba sobre cada caso posible. Consideremos ahora que una condición se realiza sobre un número entero ¿cuántos enteros existen? Infinitos. Ya podemos ver que no es viable realizar pruebas caso por caso. Para resolver los problemas se requiere utilizar propiedades matemáticas, inducción, etc.
• Cuantificaciones Existenciales: Este caso es mucho más simple. Para probar que existe un caso favorable simplemente hay que encontrarlo. Con un ejemplo basta.
• Negación de Cuantificación Universal: Este es un caso particular del caso anterior. Es lo mismo decir que algo no se cumple en todos los casos a decir que existe uno donde no se cumple.
• Cuantificadores existenciales negados: Con esto volvemos a caer en otra equivalencia. Vale lo mismo decir que no existe algo a expresar que para todos los casos no se cumple. La demostración nuevamente es algo muy complejo.

Para poder hacer las demostraciones es necesario recurrir a conversiones a fórmulas equivalentes sin cuantificadores y emplear mecanismos automatizables de demostración como ser el uso de resolución. Esto está fuera del alcance de la nota pero es bueno saberlo.

¿Cuantos tipos de lógica existen?

Si nos ponemos a estudiar esta ciencia notaremos que existen tipos como ser la lógica proposicional, de predicados, no clásicas, dentro de la cual tenemos lógicas multivaluadas (Fuzzy Logic), Modales (temporal, epistémica, etc). La diferencia entre cada una radica en las utilidades que se les pueden dar. Dependiendo la tarea a realizar algunas son más convenientes que otras.

Es por esto que es imposible aprender todo esto en simples artículos. La idea de estas notas es difundir algunos conocimientos básicos para despertar la curiosidad de ustedes los lectores y llevarlos así a investigar aún más.

La lógica como herramienta dentro de la programación

Hasta ahora todo muy bonito. Sabemos que existen muchos tipos de lógica e incluso nos adentramos un poco en dos casos particulares ¿para qué sirve esto a la hora de programar?. Es bien sabido por los programadores que por ejemplo las sentencias condicionales son fundamentales para hacer que el flujo de un programa se adapte diversas circunstancias especiales que se le puedan presentar. Pero esto puede no parecer suficiente.

Una de las cosas que pareciera estar en boca de todos en estos días es el uso de la inteligencia artificial, ya sea tanto como una moda sobre películas y noticias poco realistas como una herramienta que facilita y mejora el trabajo en la vida cotidiana. La verdad es que para crear un programa y más aún uno que emplee inteligencia artificial es fundamental saber crear modelos sobre los cuales se cumplan ciertos invariantes. Es aquí donde la lógica se incorpora y resuelve todos estos problemas.

De hecho sistemas de comprobación y representación emplean sistemas lógicos para funcionar. Un típico caso de esto es el uso de las bases de datos las cuales deben ser siempre consistentes.

Si revisamos los fundamentos de la inteligencia artificial tenemos modelos los cuales gracias a una base de conocimiento pueden tomar decisiones de una forma “inteligente”. Así que no hay excusa, Si quieres ser un buen programador no te queda otra que saber lógica.

    Gmail

Spreaker    iTunes    Ivoox    Canal de Telegram    Soundcloud