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

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

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

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

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

Например:

Используя законы алгебры логики преобразовать по шагам функцию F(x,y,z) в ДНФ. Для полученного результата составить таблицу истинности.

Решение:

Выполним преобразования по шагам:

Составим таблицу истинности для полученного результата:

x	y	z

Последний столбец этой таблицы совпадает со столбцом задания функции F(x,y,z), следовательно, перевод в ДНФ верен.

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

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

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