ДИЗЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА

ДИЗЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА - пропозициональная формула, имеющая вид

где каждое C_ij(i = 1, ... , n; j = 1, ... , m_i) есть либо переменная, либо отрицание переменной. Д. н. ф. (*) выполнима тогда и только тогда, когда при нек-ром i среди С_i1, ..., С_imi не встречаются одновременно формулы вида р и ¬р, где р - переменная. Для всякой пропозициональной формулы А можно построить эквивалентную ей Д. н. ф. В, содержащую те же переменные, что и А. Такая формула В наз. Д. н. ф. формулы А.

С. К. Соболев.

Источники:

1. Математическая энциклопедия: Гл. ред. И. М. Виноградов, т. 2 Д - Коо.-М.: «Советская Энциклопедия», 1979.-1104 стб., ил.