OBJETIVOS DE APRENDIZAGEM:
Ao final desta aula, o estudante será capaz de:

1. Recordar a definição de literal e das formas normais conjuntivas e disjuntivas.
2. Identificar as estruturas de uma expressão em FNC e FND.
3. Utilizar FNC ou FND para simplificar expressões de lógica proposicional.

ÍNDICE
DEFINIÇÃO DE LITERAL
DEFINIÇÃO DE FORMAS NORMAIS
TEOREMA DAS FORMAS NORMAIS

Um resultado interessante e útil da lógica proposicional está relacionado com as formas normais. Para detalhar esses tópicos, primeiro precisamos revisar alguns conceitos.

Definição de Literal

Um literal é qualquer expressão atômica ou a negação de uma expressão atômica. Com base nisso, falamos de literais negativos ou positivos, dependendo se as expressões atômicas são precedidas ou não por uma negação. Por exemplo: A seria um literal positivo e \neg A seria um literal negativo.

Definição de Formas Normais

Uma expressão F está em forma normal conjuntiva (FNC) quando pode ser escrita como uma conjunção de disjunções de literais, ou seja:

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

E, de maneira semelhante, haverá uma forma normal disjuntiva (FND) se for escrita como a disjunção de conjunções de literais:

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

Teorema das Formas Normais

Todas as expressões da lógica proposicional são equivalentes a uma expressão em FND e outra em FNC.

DEMONSTRAÇÃO:

Isso pode ser demonstrado por indução sobre a complexidade das fórmulas F.

• Caso base: Se F é uma expressão atômica, pode ser escrita em FNC e FND ao mesmo tempo, porque: F\equiv F_D \equiv F_C, onde F_C:=((F\vee F)\wedge (F\vee F)) e F_D:=((F\wedge F)\vee (F\wedge F))
• Passo indutivo: Sejam G e H duas expressões quaisquer para as quais o resultado do teorema se aplica; ou seja, existem H_C e G_C em FNC, e H_D e G_D em FND, tais que:

  G\equiv G_D \equiv G_D

  H\equiv H_D \equiv H_D

  Assim podemos escrever:

  \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}

  Sem perda de generalidade, se F:= \neg G, então usando o teorema de substituição sobre as leis generalizadas de De Morgan, teremos 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 outro lado, se F:=G\wedge H, então pelo teorema de substituição:

  \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 é uma forma normal conjuntiva. E de modo análogo, se F:=H\vee G, então:

  \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}

  ou seja, uma forma normal disjuntiva.

  Portanto, a indução está completa e todas as expressões da lógica proposicional podem ser escritas em FND e FNC.

O estudo das formas normais conjuntiva (FNC) e disjuntiva (FND) da lógica proposicional é fundamental para a simplificação e resolução de problemas complexos em matemática e informática. O teorema que estabelece que qualquer expressão lógica pode ser escrita tanto em FND quanto em FNC é de grande relevância, pois permite estruturar as proposições de forma mais gerenciável e padronizada, facilitando sua análise e manipulação. A importância desse resultado reside em fornecer uma base sólida para o design de algoritmos, a otimização de expressões lógicas e a resolução eficiente de problemas em diversas áreas do conhecimento, como inteligência artificial e verificação de software. Além disso, a técnica de demonstração por indução utilizada para provar esse teorema reforça a compreensão das propriedades fundamentais das expressões lógicas e sua aplicabilidade em outros contextos matemáticos.