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

En esta nueva entrega de Code Time continuamos con el camino de la programación explorando el mundo de la lógica como recurso de trabajo. La lógica, como se ha hablado en otros episodios del podcast, es un medio que es ampliamente usado en el desarrollo de software para crear modelos y realizar razonamientos.

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

Una introducción a la lógica

La lógica como tal es un medio que permite evaluar la veracidad de ciertos expresiones y razonamientos. Esto en sí podría no parecer demasiado útil dentro del campo computacional. Lamentablemente para los detractores de esta disciplina, la lógica también puede ser utilizada para crear modelos y trabajar con ellos y he allí donde su poder es evidente.

Si se lo ve históricamente además de permitir realizar razonamientos “lógicos”, esta ciencia formal se ha intentado utilizar para demostrar la matemática. Gracias a que esta primera es mucho más simple de procesar pudiendose incluso automatizar era una muy buena opción. Tristemente para los estudiosos Kurt Gödel demostró en 1931 que esto no era posible.

La relación Programación-Lógica

La programación y la lógica están estrechamente relacionadas. De hecho, teóricamente fue demostrado que existe un isomorfismo entre ambas. Esto quiere decir que puede llevarse un sistema de pruebas usado en lógica a los modelos de programación funcional y viceversa (El isomorfismo de Curry).

La lógica booleana

A la hora de programar es normal utilizar, incluso de forma implícita, una forma de razonar booleana. Para entender esto es mejor dar algunas definiciones.

El matemático del siglo 19 George Boole fue una de las personas que desarrolló una forma de álgebra donde los valores solo pueden ser Verdadero (True) y Falso (False). La lógica booleana es muy importante dentro de la ciencia de la computación ya que puede hacerse un perfecto paralelismo con el sistema de numeración binario donde cada bit puede tener como valor el 1 o el 0.

Es normal ver que este sistema se lo utilice para establecer valores de verdad. De hecho a la hora de establecer condicionales y bucles suele emplearse un tipo booleano. Además esta lógica es muy buena para representar elementos que solo pueden adquirir dos valores. Aún así la lógica no se restringe solo a esta forma de pensar y trabajar sino que se extiende mucho más existiendo muchos tipos diferentes.

Modelos y razonamientos empleando la lógica

Un razonamiento es una lista de proposiciones de las cuales la última es llamada conclusión y el resto recibe el nombre de premisas. Un ejemplo de esto podría ser:

• La lógica es importante en la programación
• Leer es una actividad saludable

• Aprender el lenguaje C es interesante

Basándonos en la definición ya dada este es un razonamiento, aunque es de admitirse que es muy malo. La idea de tener buenos conocimientos de lógica es permitir poder distinguir los buenos razonamientos de los malos.

Consideremos el siguiente razonamiento:

• Ustedes estan leyendo una nota

• Esta es una nota sobre la lógica

• Ustedes están aprendiendo algo de lógica

Este parecería ser un argumento razonable, pero desde el punto de vista de la lógica no es válido. La validez de la conclusión no se desprende necesariamente de la validez de las premisas. Aún así existen algunos modelos lógicos que permiten analizar esta clase de argumentos.

Validez Deductiva

Un razonamiento es deductivamente válido si y sólo si es imposible que las premisas sean ciertas y la conclusión falsa. Por ejemplo:

• Las naranjas son frutas o instrumentos musicales

• Las naranjas no son frutas

• Las naranjas son instrumentos musicales

A pesar de obtener una conclusión ridícula, observemos que la forma lógica del razonamiento es correcta. Si ambas premisas son ciertas, necesariamente la conclusión debe ser cierta.

Aún así la validez de las premisas y la conclusión no nos asegura la validez del razonamiento:

• Santa Rosa es la capital de La Pampa.

• La Plata es la capital de Buenos Aires.

• Posadas es la capital de Misiones.

¿Qué sucede si Brasil invade Misiones y la anexa a un estado ya existente? Es lógicamente posible que las premisas sean ciertas y la conclusión falsa, por lo tanto existe un modelo que hace inválido el razonamiento.

Con este último caso hay que destacar dos cosas:

1. El razonamiento no es deductivamente válido.
2. El caso de la invasión es un mero EJEMPLO, no se busca ofender a nadie.

Valores de verdad

Para modelar utilizaremos un lenguaje donde siempre trabajaremos con proposiciones. Esto es, con oraciones a las que se le puede asignar un valor de verdad que en este caso respetarán la forma de trabajar de la lógica booleana.

Validez de la lógica

Consideremos las siguientes proposiciones:

• Ahora Roberto calza zapatos negros.
• Roberto ahora calza zapatos negros o no.
• Ahora Roberto calza zapatos negros, y además no calza zapatos negros.

Observaremos que independientemente de cuando evaluemos estas proposiciones, diferentes resultados se obtendrán.

Contingencia

• Ahora Roberto calza zapatos negros.

Esto se trata de una contingencia, es decir, que la proposición es satisfactible para algún caso pero no para todos. Puede que en algún comentó Roberto esté calzando zapatos rojos,y será allí cuando la proposición se hará verdadera.

Tautología

• Roberto ahora calza zapatos negros o no.

Este tipo de proposiciones lleva el nombre de tautologías. La característica de esta es que siempre será verdadera. Independientemente de si Roberto está o no usando zapatos negros ahora la frase es válida.

Contradicción

• Ahora Roberto calza zapatos negros, y además no calza zapatos negros.

La contradicción, como su nombre lo indica, es una caso en el que la o las premisas se anulan o invalidan entre sí. Si Roberto estuviera calzando un par de zapatos negros valdría la primer parte pero no la segunda y viceversa.

Equivalencias lógicas

Veamos las siguientes frases:

• Si llueve el domingo me quedaré en casa
• Si salgo el domingo es porque no llueve

Observaremos que ambas proposiciones son contingencias. La validez de una implica la necesariamente la validez de la otra. En estos casos diremos que ambas proposiciones son lógicamente equivalentes. Esto no implica de ninguna manera que sean iguales.

Al igual que en matemática las equivalencias no son igualdades, como muchas veces son mal llamadas. La idea de las mismas es reflejar una misma situación. Un ejemplo claro de esto es un retrato al óleo y otro de acuarelas del mismo paisaje. Ambos se basaron en la misma información pero los resultados son distinto a pesar de mantener un grán parecido. En este caso decimos que son equivalentes.

Para poder asegurar que dos cosas son iguales deberían literalmente serlo. Es decir, ser uno una copia del otro.

 

La lógica proposicional: Un buen modelo para empezar

Una de los tipos de lógicas que podemos utilizar, y de hecho la hemos usado a lo largo de esta nota es la llamada lógica proposicional. Esta se basa en tener un conjunto de proposiciones y combinarlas para formar nuevas proposiciones más complejas que permitirán realizar razonamientos.

Para definir la lógica proposicional formalmente emplearemos un poco de notación específica. Pero no se asusten, es bastante simple de entender. Un último detalle que daremos es que la definición será inductiva.

Sea PROP el conjunto de de proposiciones de la lógica proposicional.

Las proposiciones pi pertenecen a PROP.

• Si “pi” y “pj” pertenecen a PROP “ pi y pj” pertenece a PROP (Conjunción).
• Si “pi” y “pj” pertenecen a PROP “ pi o pj” pertenece a PROP (Disyunción).
• Si “pi” pertenece a PROP “no pi ” pertenece a PROP (Negación).
• Si “pi” y “pj” pertenecen a PROP “ pi -> pj” pertenece a PROP (Implicancia).
• Si “pi” y “pj” pertenecen a PROP “ pi <-> pj” pertenece a PROP (doble Implicancia).

De esta forma es posible establecer la pertenencia al conjunto. Ahora bien ¿cómo se lo utiliza? Bueno estudiar las lógicas no es algo que pueda resumirse en una nota. Estos estudios suelen requerir incluso en algunos casos la lectura de uno o varios libros al respecto (al menos se recomienda). Pero no no se preocupen veremos cómo hacemos una conversión de lenguaje natural a lógica proposicional.

Un buen ejemplo de lógica proposicional para entender

Consideremos las siguientes frases

• Si continúa la lluvia el río aumentará.
• Si el río aumenta entonces el puente será arrastrado.
• Si la continuación de la lluvia hace que el puente sea arrastrado entonces un solo camino no será suficiente para la ciudad.
• O bien un solo camino es suficiente para la ciudad, o los ingenieros han cometido un error.
• Por lo tanto los Ingenieros han cometido un error.

 

De aquí podemos obtener las siguientes proposiciones:

• P: Continúa la lluvia
• Q: El río aumenta
• R: El puente será arrastrado
• S: Un camino es suficiente para la ciudad
• T: Los ingenieros han cometido un error

Con lo cual el modelo proposicional del problema será:

• P -> Q

• Q -> R

• (P -> R) -> (no S)

• S o T

• T

Es es un típico ejercicio de modelado que, como veremos más adelante es bastante útil aprender para poder programar mejor.

Conclusiones

Como ya habrán notado esto de la lógica puede ser algo molesto y extenso pero una de las bases de la programación es esta misma. De hecho muchas veces los errores y pérdidas de tiempo surgen por aplicar una mála lógica razonamiento. Así que ya sin mucho más los exhortamos a seguir el blog ya que haremos más entregas explicando cómo utilizar la lógica.

Esperamos que les haya gustado la nota y les haya sido de utilidad. Recuerden que pueden comentar para dejarnos saber su opinión al respecto y compartir las notas en sus redes sociales para hacer llegar el conocimiento a muchas más personas.

    Gmail

Spreaker    iTunes    Ivoox    Canal de Telegram    Soundcloud