Índice:
- Definição - O que significa Forma Normal Disjuntiva (DNF)?
- Techopedia explica Disjunctive Normal Form (DNF)
Definição - O que significa Forma Normal Disjuntiva (DNF)?
A forma normal disjuntiva (DNF) é a normalização de uma fórmula lógica na matemática booleana. Em outras palavras, diz-se que uma fórmula lógica está na forma normal disjuntiva se for uma disjunção de conjunções com todas as variáveis e sua negação estiver presente uma vez em cada conjunção. Todas as formas normais disjuntivas não são únicas, pois todas as formas normais disjuntivas para a mesma proposição são mutuamente equivalentes.
A forma normal disjuntiva é amplamente usada em áreas como a prova automatizada de teoremas.
Techopedia explica Disjunctive Normal Form (DNF)
Uma fórmula lógica está na forma normal disjuntiva se, e somente se, existir uma alternância de uma ou mais conjunções de um ou mais literais. Uma fórmula é considerada como na forma normal totalmente disjuntiva se todas as variáveis envolvidas forem representadas apenas uma vez em cada cláusula. Semelhante à forma normal conjuntiva, os operadores proposicionais na forma normal disjuntiva são os mesmos: AND, OR e NOT.
Todas as fórmulas lógicas podem ser convertidas em uma forma normal disjuntiva equivalente. No entanto, em alguns casos, a explosão exponencial da função lógica é possível devido à conversão para a forma normal disjuntiva. Outro ponto importante é que qualquer função booleana única pode ser representada por apenas uma e uma forma normal completa disjuntiva única. Com a ajuda de técnicas como o método da tabela verdade, árvores da verdade ou uma tabela de equivalências lógicas, é possível gerar uma forma normal disjuntiva para fórmulas lógicas. O K-DNF, uma variação da forma normal disjuntiva, é amplamente utilizado e popular no estudo da complexidade computacional.