martes, 28 de agosto de 2012

Tarea 3: Lógica Proposicional - Aplicaciones

Para la tercera tarea de Verificación y Validación de Software, tenemos que investigar las aplicaciones de la lógica proposicional.

Para esto encontré algunas aplicaciones como: Inteligencia Artificial, Circuitos Lógicos, y Acertijos Lógicos, pero solo explicaré estos dos últimos.

Aplicación - Acertijos Lógicos:

Una aplicación de la lógica proposicional que me pareció interesante, fue la de la creación de acertijos en base a proposiciones lógicas. El uso de la lógica para crear desafios mentales complicados, si bien no es una aplicación profeional, es un enfoque diferente a lo usual que estoy acostumbrado(circuitos, computación lógica, y demás).


Los acertijos que están basados en la lógica proposicional retan a las personas a obtener la respuesta correcta a partir de un conjunto de oraciones, las cuales pueden ser verdaderas o falsas según los condicionantes del propio acertijo.

Ejemplos:

[2]Guardian mentiroso

En una prisión de la que debemos salir, existen dos puertas. Una lleva a la salida. La otra, a la muerte segura. Cada puerta está custodiada por un guardián. Sabemos que uno de ellos dice siempre la verdad y que el otro miente siempre, pero no sabemos cuál es cada uno. La cuestión es: si pudieras hacer sólo una pregunta a uno de los dos, ¿qué pregunta le harías para saber qué puerta es la buena?

Solución: La pregunta que le haría es: "¿Cuál es la puerta que diría tu compañero que es la correcta?". En todo caso, la respuesta será la falsa.

[1]Knights and Knaves

Un visitante encuentra a tres habitantes de la isla de los caballeros y escuderos. Se acerca al primero y le pregunta: "¿Tú eres caballero o escudero?". Éste responde, pero el visitante no le entiende bien. Por su parte, el segundo dice: "Ha dicho que es escudero". Y el tercero apostilla: "Eso es mentira". ¿Qué son los habitantes segundo y tercero? (Tomando en cuenta que los caballeros siempre dicen la verdad, y los escuderos siempre mienten)

Solución: Nadie puede decir de sí mismo que es escudero, puesto que, si es caballero, debe decir la verdad y, si es escudero, dirá igualmente que es caballero porque miente siempre. Por lo tanto, el segundo habitante miente: es escudero. Y, el tercero, dice la verdad, por lo tanto, es caballero.

[2]Acertijo de los Cofres

Tenemos 4 cofres y dentro de uno hay un tesoro. Cada cofre contiene una inscripción y sabemos que 2 dicen la verdad y 2 mienten. ¿Dónde está el tesoro?

Cofre 1: El tesoro no está aquí.
Cofre 2: El cofre 1 dice la verdad.
Cofre 3: El tesoro no está en el cofre 2.
Cofre 4: El cofre 3 está vacío.

Solución: Para que se cumpla que dos digan la verdad y dos mientan, el tesoro debe estar en el cofre 1


Aplicación - Circuitos Lógicos

La aplicación quizás más conocida de la lógica proposicional son los circuitos lógicos.

[3]Un circuito lógico es un dispositivo que tienen una o más entradas y exactamente una salida.  En cada instante cada entrada tiene un valor, 0 o 1; estos datos son procesados por el circuito para dar un valor en su salida, 0 o 1.
Los valores 0 y 1 pueden representar ciertas situaciones físicas como, por ejemplo, un voltaje nulo y no nulo en un conductor.

Los circuitos lógicos se construyen a partir de ciertos circuitos elementales denominados compuertas lógicas, entre las cuales diferenciaremos:
  • Compuertas lógicas básicas:  OR, AND, NOT. 
  • Compuertas lógicas derivadas:  NOR, NAND
Un ejemplo de un circuito lógico, es el siguiente:

Compuerta OR 

En una compuerta OR con entradas A y B, la salida Y resulta: Y = A + B, donde dicha suma esta definida por la siguiente tabla.

ABY = A + B
000
011
101
111

La compuerta OR se representa del siguiente modo(aunque también puede tener más de dos entradas): 

Compuerta AND 

En una compuerta AND con entradas A y B, la salida Y resulta: Y = A * B, donde el producto se define por la siguiente tabla:

ABY = A * B
000
010
100
111


La compuerta AND se representa del siguiente modo(también puede tener más de dos entradas): 
Compuerta NOT 

En una compuerta NOT con entrada A, la salida Y resulta: Y = !A, donde el complemento se define por la siguiente tabla:

A
Y = !A
1
0
0
1

La compuerta NOT se representa del siguiente modo:
Compuertas NOR y NAND 

Las compuertas NOR y NAND no son básicas.  Una  compuerta NOR equivale a una compuerta OR seguida de una compuerta NOT.  Una  compuerta NAND equivale a una compuerta AND seguida de una compuerta NOT.





Por lo tanto, cuando las entradas son A y B, las salidas de estas compuertas resultan: 


Referencias

2 comentarios: