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 automática de teoremas.
Definirtec explica a forma normal disjuntiva (DNF)
Uma fórmula lógica está na forma normal disjuntiva se e somente se houver uma existência de alternância de uma ou mais conjunções de um ou mais literais. Uma fórmula é considerada na forma normal disjuntiva completa 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 saliente é que qualquer função booleana única pode ser representada por apenas uma e uma única forma normal disjuntiva completa. Com a ajuda de técnicas como o método da tabela verdade, árvores verdade ou uma tabela de equivalências lógicas, podem ser geradas formas normais disjuntivas para fórmulas lógicas. K-DNF, uma variação da forma normal disjuntiva, é amplamente usada e popular no estudo da complexidade computacional.