Введем понятие логической степени, которою будем обозначать . Тогда, логическая степень будет определяться по формуле (2.1)
(2.1)
Любую функцию от n переменных можно представить в виде (см.(2.2))
(2.2)
означает, что коллективные члены формируются только для таких наборов (α1, α2,…, αn) для которых функция принимает единичное значение.
Форма (2.2) определяет алгоритм перехода от таблицы истинности к аналитическому ее виду. Для такого перехода используется следующий алгоритм:
а) Выбрать в таблице истинности все наборы, в которых функция обращается в единицу.
б) Выписать конъюнкции, соответствующие этим наборам аргументов. При этом если аргумент х i входит в данный набор как «1», то он вписывается без изменения в конъюнкцию, соответствующую данному набору. Если же входит в данный набор как «0», то в соответствующую конъюнкцию вписывается его отрицание.
в) Все полученные конъюнкции объединяют знаком дизъюнкции.
Для функции у3 СДНФ будет иметь вид:
Конъюнктивная совершенная нормальная форма
|
|
Любую функцию от n переменных можно представить в виду:
f=
означает, что коллективные члены формируются только для таких наборов, (α1, α2, …, αn) для которых функция принимает нулевое значение.
Следующий алгоритм позволяет перейти от табличной записи функции к СКНФ:
а) Выбрать в таблице истинности все наборы, в которых функция обращается в «0».
б) Выписать дизъюнкции, соответствующие этим наборам аргументов. При этом если аргумент х i входит в данный набор как «0», то он вписывается без изменения в дизъюнкцию, соответствующую данному набору. Если же входит в данный набор как «1», то в соответствующую дизъюнкцию вписывается его отрицание.
в) Все полученные дизъюнкции объединяют знаком конъюнкции
Функция У3 в виде СКНФ будет иметь вид: