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

1. Recordar la definición de literal y de las formas normales conjuntivas y disyuntivas.
2. Identificar las estructuras de una expresión en FNC y FND.
3. Utilizar FNC o FND para simplificar expresiones de la lógica proposicional.

ÍNDICE
DEFINICIÓN DE LITERAL
DEFINICIÓN DE FORMAS NORMALES
TEOREMA DE LAS FORMAS NORMALES

Un resultado interesante y útil de la lógica proposicional está relacionado con las formas normales. Para detallar en estas cosas necesitamos primero revisar algunos conceptos.

Definición de Literal

Un literal es cualquier expresión atómica o la negación de una expresión atómica. En función de esto, hablamos de literales negativos o positivos según sean expresiones atómicas precedidas o no por una negación. Por ejemplo: A sería un literal positivo y \neg A sería un literal negativo.

Definición de Formas Normales

Una expresión F está en forma normal conjuntiva (FNC) cuando se puede escribir como una conjuntoria de la disyuntoria de literales, es decir:

\displaystyle F=\bigwedge_{i=1}^n \left( \bigvee_{j=1}^m L_{ij}\right)

Y análogamente, se tendrá una forma normal disyuntiva (FND) si se escribe como la disyuntoria de la conjuntoria de literales

\displaystyle F=\bigvee_{i=1}^n \left(\bigwedge_{j=1}^m L_{ij}\right)

Teorema de las Formas Normales

Todas las expresiones de la lógica proposicional son equivalentes a una expresión en FND y otra en FNC.

DEMOSTRACIÓN:

Esto se puede demostrar por inducción sobre la complejidad de las fórmulas F.

• Caso inicial: Si F es una expresión atómica, entonces se puede escribir en FNC y FND al mismo tiempo porque: F\equiv F_D \equiv F_C, donde F_C:=((F\vee F)\wedge (F\vee F)) y F_D:=((F\wedge F)\vee (F\wedge F))
• Paso inductivo: Sean G y H dos expresiones cualesquiera para las que se cumple el resultado del teorema; es decir, que existen H_C y G_C en FNC, y H_D y G_D en FND tales que

  G\equiv G_D \equiv G_D

  H\equiv H_D \equiv H_D

  Así que podemos escribir:

  \displaystyle G_D := \bigvee_{i=1}^n \bigwedge_{j=1}^m L_{ij}^{GD} ; \displaystyle G_C := \bigwedge_{i=1}^n \bigvee_{j=1}^m L_{ij}^{GC}

  \displaystyle H_D := \bigvee_{i=1}^n \bigwedge_{j=1}^m L_{ij}^{HD} ; \displaystyle H_C := \bigwedge_{i=1}^n \bigvee_{j=1}^m L_{ij}^{HC}

  Sin pérdida de generalidad podemos ver que si F:= \neg G, entonces utilizando el teorema de sustitución sobre las leyes generalizadas de De Morgan se tendrá que:

  \displaystyle F:= \neg G \equiv \left\{ \begin{matrix} \neg G_D := \neg \bigvee_{i=1}^n \bigwedge_{j=1}^m L_{ij}^{GD} \equiv\bigwedge_{i=1}^n \neg \bigwedge_{j=1}^m L_{ij}^{GD} \equiv \bigwedge_{i=1}^n \bigvee_{j=1}^m \neg L_{ij}^{GD} \\ \\ \neg G_C := \neg \bigwedge_{i=1}^n \bigvee_{j=1}^m L_{ij}^{GC} \equiv \bigvee_{i=1}^n \neg \bigvee_{j=1}^m L_{ij}^{GC} \equiv \bigvee_{i=1}^n \bigwedge_{j=1}^m \neg L_{ij}^{GC} \end{matrix}\right.

  Por otro lado, si F:=G\wedge H se tendrá que, por el teorema de sustitución:

  \displaystyle F:=G\wedge H \equiv G_C \wedge H_C := \bigwedge_{i=1}^n \bigvee_{j=1}^m L_{ij}^{GC} \wedge \bigwedge_{i=1}^{n^\prime} \bigvee_{j=1}^{m^\prime} L_{ij}^{HC}

  que es una forma normal conjuntiva. Y de modo completamente análogo se tendrá que, si F:=H\vee G, entonces:

  \displaystyle F:=G\wedge H \equiv G_D \vee H_D := \bigvee_{i=1}^n \bigwedge_{j=1}^m L_{ij}^{GD} \vee \bigvee_{i=1}^{\overline{n}} \bigwedge_{j=1}^{\overline{m}} L_{ij}^{HD}

  es decir, una forma normal disyuntiva.

  Por lo tanto, la inducción es completa y todas las expresiones de la lógica proposicional se pueden escribir en FND y FNC.

El estudio de las formas normales conjuntiva (FNC) y disyuntiva (FND) de la lógica proposicional es fundamental para la simplificación y resolución de problemas complejos en matemáticas e informática. El teorema que establece que cualquier expresión lógica puede escribirse tanto en FND como en FNC es de gran relevancia, ya que permite estructurar las proposiciones de manera más manejable y estandarizada, facilitando así su análisis y manipulación. La importancia de este resultado radica en que proporciona una base sólida para el diseño de algoritmos, la optimización de expresiones lógicas y la resolución eficiente de problemas en diversas áreas del conocimiento, como la inteligencia artificial y la verificación de software. Además, la técnica de demostración por inducción utilizada para probar este teorema refuerza la comprensión de las propiedades fundamentales de las expresiones lógicas y su aplicabilidad en otros contextos matemáticos.