Aplicaciones de la Lógica Proposicional

Verificación y Validación de Software
Entrada 3

En esta publicación hablaré de una de las aplicaciones de la lógica proposicional, primeramente veremos algunos términos y cosas básicas para entrar en el tema, y después hablaré del caso en específico.

Antes de empezar, cabe mencionar que la lógica proposicional es usada en muchos ámbitos, sobre todo computacionales, por lo que su uso suele ser básico en muchos sistemas. De entre varios usos aplicados que me ha tocado leer en internet son la representación del conocimiento o razonamiento con sentido común, dentro del campo de inteligencia artificial, verificación de propiedades en ingeniería de software, algoritmos de aproximación mediante teoría de la computación, verificación de protocolos criptográficos y diseño de circuitos digitales, entre muchos más.

Lógica proposicional

Definición:
"La lógica proposicional es la parte de la lógica que estudia la formación de proposiciones complejas a partir de proposiciones simples, y la inferencia de proposiciones a partir de proposiciones, pero sin tener en cuenta la estructura interna de las proposiciones más simples." [1]

Sintaxis usada en la lógica proposicional

Variables proposicionales (P): p, q, r, s, t...
(Se puede usar cualquier letra del abecedario, pero normalmente se usan letras a partir de la "p")

Conectivos lógicos: ¬, ∨, ∧, →, ↔
(Los conectivos anteriores suelen ser los que se usan, pero existen simbologías diferentes)

Símbolos de puntuación: (, )
(Se usan paréntesis para separar expresiones y evitar confusión, tal y como se hace en álgebra, y también puede ser usados corchetes y llaves)

Es importante saber que cada variable proposicional es una entidad completa y que no se puede dividir, y que solamente puede tomar uno de dos diferentes valores: verdadero (1) o falso (0).

Tablas de conectivas lógicas

Nombre	Lenguaje natural	Ejemplo	Símbolo
Negación	no	No hace frío	¬
Conjunción	y	Hace frío y está nublado	∧
Disyunción	o	Hace frío o hace calor	∨
Condicional	si-entonces	Si hace frío, entonces uso abrigo	→
Bicondicional	si y sólo si	Está nublado si y sólo si hay nubes visibles	↔

Para cada una de estas conectivas lógicas existen tablas de verdad, que me imagino ya hemos visto en algún momento dentro de nuestras clases, les dejo aquí una imagen con las tablas de verdad de los conectivos anteriores, obtenida de Wikipedia y que compare con algunos apuntes, para verificar que están correctas.

Uso de la lógica en computación

"Debido a que los computadores trabajan con información binaria, la herramienta matemática adecuada para el análisis y diseño de su funcionamiento es el Álgebra de Boole. El Álgebra de Boole fue desarrollada inicialmente para el estudio de la lógica. Hoy en día, esta herramienta resulta fundamental para el desarrollo de los computadores ya que, con su ayuda, el análisis y síntesis de combinaciones complejas de circuitos lógicos puede realizarse con rapidez." [2]

Todo lo anterior son nociones básicas que ya debemos de saber, y es solo una breve introducción, para poder entrar en el caso particular.

Diseño de circuitos

La realización del diseño de un circuito puede involucrar la creación de un sistema electrónico complejo, como el de una placa madre de una computadora, o circuitos menos complejos como el de un sistema integrado.

Cuando son diseños "pequeños" es fácil que una sola persona pueda hacerlos, pero cuando se habla de algo complejo, se requiere a un equipo de personas que hagan un diseño con enfoque sistemático y del cuál se puedan hacer pruebas mediante un simulador, antes de la fabricación del mismo.

La etapa del diseño del circuito, es donde se genera el esquema del circuito integrado, y se considera una etapa media entre el diseño lógico (donde se dice qué debería de hacer el circuito en base a que entradas) y el diseño físico (parte en la que se estructura el diseño del circuito a imprimir a una placa).

[Al hablar de un circuito impreso en una placa me refiero a algo como en la siguiente imagen]

[http://www.arqhys.com/contenidos/diseno-circuitos.html]

Un circuito lógico es aquél que interpreta la información y hace una operación en base a el voltaje de entrada, que puede ser "alto" (1) o "bajo" (0).

El circuito ejecutará una serie de funciones lógicas, a través de puertas lógicas como los conectivos NOT, AND y OR, así como de combinaciones de las mismas como XOR.

Puertas lógicas

En seguida imagen con las puertas lógicas mencionadas. Estas no son todas las existentes.

[http://blogpumaagl.blogspot.mx/2010/10/circuitos-logicos.html]

Como podemos observar cada puerta tiene dos valores de entrada, a excepción del NOT, y solamente pueden tener un valor de salida 0 o 1, y para cada una de ellas existe una tabla de verdad, las mismas que en los conectivos lógicos correspondientes mencionados en la primer parte de esta publicación.

Ejemplo de diseño de un circuito

Para realizar un circuito lo primero que necesitamos es saber las especificaciones del cliente, es decir, saber que es lo que se quiere que el circuito de como resultado.

Enseguida les comparto un ejemplo de mis apuntes de sistemas digitales, donde podemos aplicar el diseño de un circuito.

"Diseñar un circuito que indique al operador de la torre de control de un aeropuerto cuando un avión Jumbo 747 puede aterrizar. Se tienen 3 pistas en el aeropuerto (p, q y r), y cuando una de ellas esta disponible, se obtiene una entrada lógica de 1. Además este tipo de avión solo puede aterrizar cuando existen dos pistas contiguas disponibles."

Ahora sabemos que lo que se desea es un indicador para el operador de la torre, este puede ser un led que encienda cuando es posible aterrizar. Se enciende cuando la salida del circuito es 1, se mantiene apagado cuando la salida es 0. Como entrada tenemos 0 si la pista no esta disponible, y 1 cuando si lo esta.

Creamos una tabla de verdad con las salidas que necesitamos.

p	q	r	Salida
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

La tabla queda así, porque solo cuando tenemos dos unos contiguos en las entradas (dos pistas contiguas disponibles), significa que la salida sera 1 (puede aterrizar el Jumbo 747).

Ahora mediante mapas de Karnaugh, obtendremos la proposición de salida.

r \ pq	00	01	11	10
0	0	0	1	0
1	0	1	1	0

Con esto podemos obtener la función lógica del circuito.
S = qr + pq
S = (q^r) ∨ (p^q)

Y el diseño de este circuito usando puertas lógicas quedaría así:

Podemos simplificar:
S = q(r + p)
S = q^(r ∨ p)

[Imágenes creadas desde http://www.circuitlab.com/editor]

Con este circuito podemos dar solución al problema planteado, y básicamente los pasos que seguí son los que se utilizan para el diseño de circuitos.

Verificación y pruebas del diseño de un circuito

"Una vez que el circuito ha sido diseñado, debe ser a la vez verificado y probado. La verificación es el proceso de pasar a través de cada etapa de diseño y asegurando que va a hacer lo que la especificación exige que haga. Esto es frecuentemente un proceso altamente matemático y puede involucrar a gran escala simulaciones por ordenador del diseño. En cualquier diseño complejo que es muy probable que los problemas se encuentran en esta etapa y puede implicar una gran cantidad del trabajo de diseño de hacerse de nuevo con el fin de solucionarlos." [3]

Referencias y documentos consultados:
[1] y [2] Lógica proposicional
[3] Circuit design
Lógica proposicional - PDF
Diseño de circuitos lógicos - PDF