OBJETIVOS DE APRENDIZAJE:
Al finalizar esta clase, el estudiante será capaz de:

1. Aplicar el algoritmo FND/FNC a expresiones concretas para encontrar sus formas normales conjuntiva y disyuntiva.
2. Comprender el uso de interruptores simples y compuestos en la lógica proposicional.
3. Identificar la estructura de los interruptores compuestos y las cajas negras.
4. Utilizar la tabla de verdad para resumir información sobre un dispositivo.
5. Extraer la FND y la FNC de un dispositivo a partir de su tabla de verdad.
6. Diseñar un interruptor compuesto que tenga el mismo funcionamiento que un dispositivo dado.

ÍNDICE
EL ALGORITMO FND/FNC
ALGORITMO PARA OBTENER LA FORMA NORMAL A PARTIR DE LAS TABLAS DE VERDAD: CAJAS NEGRAS E INTERRUPTORES COMPUESTOS
EJERCICIOS DE EJEMPLO

Si bien hemos probado que todas las expresiones de la lógica proposicional son equivalentes a una forma normal, nada hemos dicho sobre cómo encontrar tales formas normales. Para lograr esto, revisaremos un algoritmo cuyo objetivo es generar expresiones en forma normal y, finalmente, revisaremos las aplicaciones que emergen de estos temas.

El Algoritmo FND/FNC

El algoritmo FND/FNC es una serie de pasos que te permitirá encontrar, a partir de cualquier expresión de la lógica proposicional, su expresión equivalente en FND o FNC (según corresponda). Se realiza se la siguiente manera:

• PASO 1: Remplaza todas las sub-expresiones de la forma (F\rightarrow G) por (\neg F\vee G), de igual forma con (F\leftrightarrow G). Repetir este paso hasta eliminar todas las implicancias y doble implicancias de la expresión.
• PASO 2: Eliminar dobles negaciones y aplicar las leyes de De Morgan donde sea posible. Se deben aplicar los siguientes remplazos
  • \neg\neg G \longmapsto G
  • \neg(G\wedge H) \longmapsto (\neg G \vee \neg H)
  • \neg(G\vee H) \longmapsto (\neg G \wedge \neg H)

    Cuando ya no queden sub-expresiones de la forma \neg\neg G, \neg(G \wedge H) ni \neg(G \vee H), continúa con el paso 3.

• Paso 3: Este paso se divide en dos partes según si se desea llegar a una FND o a una FNC
  • Si que quiere llegar a una FNC:

    Utilizar \vee-distribución donde sea posible. Es decir, se deben aplicar los siguientes remplazos:

    \left.\begin{matrix}G\vee(H\wedge K) \\ \\ (H\wedge K)\vee G \end{matrix} \right\} \longmapsto (G\vee H)\wedge (G\vee K)

    Cuando ya no queden expresiones de la forma G\vee(H\wedge K) o (H\wedge K)\vee G, se habrá llegado a una FNC

  • Si que quiere llegar a una FND:

    Utilizar \wedge-distribución donde sea posible. Es decir, se deben aplicar los siguientes remplazos:

    \left.\begin{matrix}G\wedge(H\vee K) \\ \\ (H\vee K)\wedge G \end{matrix} \right\} \longmapsto (G\wedge H)\vee (G\vee K)

    Cuando ya no queden expresiones de la forma G\wedge(H\vee K) o (H\vee K)\wedge G, se habrá llegado a una FND

Ejemplos

Utilice el Algoritmo FND/FNC las siguientes expresiones en su forma normal conjuntiva y disyuntiva.

1. (A\rightarrow (B\rightarrow A)) [SOLUCIÓN]
2. ((A\vee B)\rightarrow(\neg B \wedge A)) [SOLUCIÓN]

Algoritmo para obtener la Forma Normal a partir de las Tablas de Verdad: Cajas Negras e Interruptores Compuestos

El algoritmo FND/FNC nos permite encontrar, para cualquier expresión de la lógica proposicional, su expresión equivalente en forma normal. Pero hay situaciones en que no tenemos una expresión inicial con qué trabajar en primer lugar. Tal es el caso cuando tenemos el resultado de una tabla de verdad de alguna expresión F cuya estructura proposicional desconocemos. Explicar esto en palabras es un proceso largo; la técnica, sin embargo, se entiende mucho mejor mostrando con ejemplos de cómo se desarrolla, así que dejaré unos ejemplos que desarrollaré en vídeo, pero antes debe revisar los siguientes conceptos:

• Cable: Medio por el que circula una señal
• Nodo: Punto donde se unen 3 o más cables.
• Interruptor simple: Dispositivo que admite los estados de encendido (1) y apagado (0), estando siempre en uno, y sólo uno, de esos estados. El estado de encendido permite el paso de una señal y el de apagado lo impide.
• Interruptor compuesto: Es un dispositivo compuesto de interruptores simples y cables.
• Caja Negra: Es cualquier dispositivo cuya estructura interna no se puede observar.

Los interruptores simples son modelados a través de variables proposicionales, y los compuestos mediante expresiones de la lógica proposicional. Los casos más sencillos son los que se obtienen de los conectores de disyunción y conjunción que se muestran a continuación

Esquema de la Conjunción

Esquema de la Disyunción

Ejercicios de Ejemplo

1. Se tiene un dispositivo formado por una caja negra y 4 interruptores ordenados. La activación del dispositivo ocurre bajo las siguientes condiciones
   • Condición 1: Se activa si hay dos interruptores consecutivos encendidos. Esta condición deja de funcionar si hay tres interruptores consecutivos encendidos.
   • Condición 2: Se activa si están todos los interruptores apagados.
   • Excepción: Si las condiciones anteriores no se cumplen, entonces el dispositivo se apaga.

   a) Resuma esta información en una tabla de verdad [SOLUCIÓN]

   b) A partir de la tabla de verdad, extraiga la FND y la FNC que reproduzca el funcionamiento de la máquina. [SOLUCIÓN]

   c) Utilice la FNC o la FND obtenida en el paso anterior (la más sencilla) para diseñar un interruptor compuesto que tenga el mismo funcionamiento que el dispositivo. [SOLUCIÓN]

2. Lo mismo que en el ejercicio anterior, sólo que ahora el dispositivo tiene 5 interruptores. [DESAFÍO PARA EL LECTOR]