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

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

Аналитическая запись ФАЛ

Выражение одних элементарных функций через другие

Рассмотрим методы перехода от табличного способа задания функций к аналитическому методу (в виде формул).

 

Конъюнкция называется элементарной, если в ней каждая переменная встречается не более одного раза.

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

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

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

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

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

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

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