Нормальная форма логической формулы не содержит знаков импликации, эквивалентности и отрицания неэлементарных формул.
Нормальная форма существует в двух видах:
-
конъюнктивная нормальная форма (КНФ) -- конъюнкция нескольких дизъюнкций, например, (A∨¯B∨C)∧(A∨C);
-
дизъюнктивная нормальная форма (ДНФ) -- дизъюнкция нескольких конъюнкций, например, (A∧¯B∧C)∨(B∧C).
СКНФ
Совершенная конъюнктивная нормальная форма (СКНФ) -- это КНФ, удовлетворяющая трем условиям:
-
не содержит одинаковых элементарных дизъюнкций;
-
ни одна из дизъюнкций не содержит одинаковых переменных;
-
каждая элементарная дизъюнкция содержит каждую переменную из входящих в данную КНФ.
Любая булева формула, которая не является тождественно истинной, может быть представлена в СКНФ.
Правила построения СКНФ по таблице истинности
Для каждого набора переменных, при котором функция равна 0, записывается сумма, причем переменные, которые имеют значение 1, берутся с отрицанием.
СДНФ
Совершенная дизъюнктивная нормальная форма (СДНФ) -- это ДНФ, удовлетворяющая трем условиям:
-
не содержит одинаковых элементарных конъюнкций;
-
ни одна из конъюнкций не содержит одинаковых переменных;
-
каждая элементарная конъюнкция содержит каждую переменную из входящих в данную ДНФ, к тому же в одинаковом порядке.
Любая булева формула, которая не является тождественно ложной, может быть представлена в СДНФ, к тому же единственным образом.
Правила построения СДНФ по таблице истинности
Для каждого набора переменных, при котором функция равна 1, записывается произведение, причем переменные, которые имеют значение 0 берут с отрицанием.
Примеры нахождения СКНФ и СДНФ
Записать логическую функцию по ее таблице истинности:
Рисунок 1.
Решение:
Воспользуемся правилом построения СДНФ:
Рисунок 2.
Получим СДНФ:
F(x1, x2, x3)=(¯x1∧¯x2∧¯x3)∨(¯x1∧¯x2∧x3)∨(x1∧¯x2∧¯x3)∨(x1∧¯x2∧x3)∨(x1∧x2∧x3)Воспользуемся правилом построения СКНФ:
Рисунок 3.
Получим СКНФ:
F(x1, x2, x3)=(x1∨¯x2∨x3)∧(x1∨¯x2∨¯x3)∧(¯x1∨¯x2∨x3)Функция задана таблицей истинности:
Рисунок 4.
Представить эту функцию в виде СДНФ и СКНФ.
Решение:
-
Запишем логическую функцию в СДНФ. Для удобства решения добавим к таблице вспомогательный столбец.
Используя правило составления СДНФ не забываем вводить знак отрицания для переменных со значением 0. Инвертировать нулевые значения переменных обязательно, т.к. иначе они превратят значения конъюнкций в нули основной функции.
Рисунок 5.Полученные во вспомогательном столбце конъюнкции соединим знаком дизъюнкции и получим искомую логическую функцию в виде СДНФ:
F(x1,x2,x3,x4)=(¯x∧¯y∧z∧f)∨(¯x1∧x2∧¯x3∧¯x4)∨(¯x1∧x2∧x3∧x4)∨(x1∧¯x2∧¯x3∧¯x4). -
Запишем логическую функцию в СКНФ.
Используя правило составления СКНФ не забываем вводить знак отрицания для переменных со значением 1. Инвертировать единичные значения переменных обязательно, т.к. иначе они превратят значения дизъюнкций в единицы основной функции.
Рисунок 6.Полученные во вспомогательном столбце дизъюнкции соединим знаком конъюнкции и получим искомую логическую функцию в виде СКНФ:
F(x1,x2,x3,x4)=(x1∨x2∨x3∨x4)∧(x1∨x2∨x3∨¯x4)∧(x1∨x2∨¯x3∨x4)∧(x1∨¯x2∨x3∨¯x4)∧(x1∨¯x2∨¯x3∨x4)∧(¯x1∨x2∨x3∨¯x4)∧(¯x1∨x2∨¯x3∨x4)∧(¯x1∨x2∨¯x3∨¯x4)∧(¯x1∨¯x2∨x3∨x4)∧(¯x1∨¯x2∨x3∨¯x4)∧(¯x1∨¯x2∨¯x3∨x4)∧(¯x1∨¯x2∨¯x3∨¯x4).
