Дизъюнктивная совершенная нормальная форма (ДСНФ)

Любая таблично заданная ФАЛ f(x₁, x₂, …, x_n) (кроме тождественного нуля) может быть представлена в следующем аналитическом виде:

Представление ФАЛ в таком виде называется дизъюнктивной совершенной нормальной формой этой функции (ДСНФ).

Алгоритм перехода от табличного задания функции к ДСНФ

1. Выбрать в таблице все наборы аргументов, на которых функция обращается в единицу.

2. Выписать конъюнкции, соответствующие этим наборам аргументов. При этом если аргумент x_i входит в данный набор как 1, он вписывается без изменения в конъюнкцию, соответствующую данному набору. Если x_i входит в данный набор как 0, то в конъюнкцию вписывается его отрицание.

3. Полученные конъюнкции соединить операцией дизъюнкция.