Аналитическая запись ФАЛ
Рассмотрим методы перехода от табличного способа задания функций к аналитическому методу (в виде формул).
Дизъюнктивная нормальная форма (ДНФ) Элементарная конъюнкция – конъюнкция, в которой каждая переменная встречается не более одного раза. Дизъюнктивная нормальная форма (ДНФ) – дизъюнкция элементарных конъюнкций. Например: Используя законы алгебры логики преобразовать по шагам функцию F(x,y,z) в ДНФ. Для полученного результата составить таблицу истинности. Решение: Выполним преобразования по шагам:
Составим таблицу истинности для полученного результата:
Последний столбец этой таблицы совпадает со столбцом задания функции F(x,y,z), следовательно, перевод в ДНФ верен.
Дизъюнктивная совершенная нормальная форма (ДСНФ) Любая таблично заданная ФАЛ f(x1, x2, …, xn) (кроме тождественного нуля) может быть представлена в следующем аналитическом виде:
Представление ФАЛ в таком виде называется дизъюнктивной совершенной нормальной формой этой функции (ДСНФ).
|
