3. Совершенная дизъюнктивная нормальная форма и совершенная конъюнктивная нормальная форма.
Известно два способа задания логических функций: с помощью формулы и с помощью таблицы истинности. По формуле легко составляется таблица. На практике при конструировании различных электронных устройств часто возникает обратная задача – от таблицы истинности перейти к формуле, чтобы на ее основе построить функциональную схему.
Введем следующие определения:
Элементарной конъюнкцией называется конъюнкция нескольких переменных, взятых с отрицанием или без отрицания, причем среди переменных могут быть одинаковые.
Элементарной дизъюнкцией называется дизъюнкция нескольких переменных, взятых с отрицанием или без отрицания, причем среди переменных могут быть одинаковые.
Всякую дизъюнкцию элементарных конъюнкций назовем дизъюнктивной нормальной формой (ДНФ).
Всякую конъюнкцию элементарных дизъюнкций назовем конъюнктивной нормальной формой (КНФ).
Совершенной дизъюнктивной нормальной формой (СДНФ) называется ДНФ, в которой нет одинаковых элементарных конъюнкций и все конъюнкции состоят из одного и того же набора переменных, в который каждая переменная входит только один раз (возможно, с отрицанием).
Совершенной конъюнктивной нормальной формой (СКНФ) называется КНФ, в которой нет одинаковых элементарных дизъюнкций и все дизъюнкции состоят из одного и того же набора переменных, в который каждая переменная входит только один раз (возможно, с отрицанием).
Приведем примеры формул, соответствующих и не соответствующих этим определениям:
НАЗВАНИЕ ФОРМУЛЫ
В ОПРЕДЕЛЕНИИ
соответствующая определению
НЕ СООТВЕТСТВУЮЩАЯ
ОПРЕДЕЛЕНИЮ
Элементарная
Элементарная
ДНФ можно построить для всякой формулы (путем преобразования)
КНФ можно построить для всякой формулы (путем преобразования)
Любую функцию, кроме констант 0 и 1, можно представить в виде как СДНФ, так и СКНФ.
Этот факт является теоремой алгебры логики. Из него следует, что любая формула (кроме констант 0 и 1) может быть преобразован к виду как СДНФ, так и СКНФ. Константа 0 может быть представлена только СКНФ (
), а константа 1 – только СДНФ (
). Из вышесказанного следует, что если надо построить формулу некоторой функции по таблице истинности этой функции, то всегда можно получить СКНФ или СДНФ этой функции.
Алгоритм получения СДНФ по таблице истинности:
Отметить те строчки таблицы истинности, в последнем столбце которых стоят 1:
Совершенная нормальная форма — дизъюнктивная и конъюнктивная, правило построения
Нормальная форма логической формулы характеризуется тем, что для нее не свойственны эквивалентность, отрицание формул неэлементарного типа и знаки импликации.
Существует две формы нормального типа: КНФ (конъюнктивная нормальная форма) и ДНФ (дизъюнктивная нормальная форма).
СДНФ — совершенная дизъюнктивная нормальная форма формулы. СДНФ — способ написания функции алгебры логики в качестве логического выражения.
Осторожно! Если преподаватель обнаружит плагиат в работе, не избежать крупных проблем (вплоть до отчисления). Если нет возможности написать самому, закажите тут.
СДНФ формулы — это равнозначная ей формула, которая представляет собой дизъюнкцию элементарных конъюнкций, при которых функция достигает показателя «1».
ДНФ выглядит следующим образом:
СДНФ обладает некоторыми определенными свойствами:
- включает различные элементарные конъюнкции;
- все логические слагаемые формулы содержат все переменные, которые входят в функцию F;
- ни в одном логическом слагаемом не содержится переменная и её отрицание.
К СДНФ возможно привести любую формулу алгебры логики. Исключение составляет только тождественно ложная формула. СДНФ можно получить как используя таблицы истинности, так и через равносильные преобразования.
При построении таблицы истинности важно помнить, что логические переменные со значением «0» необходимо брать с отрицанием.
Что такое СКНФ
СКНФ — совершенная конъюнктивная нормальная форма. Формулу можно назвать таковой, когда она — конъюнкция неповторяющихся элементарных дизъюнкций.
Формула должна соответствовать нескольким условиям, чтобы называться СКНФ:
- в ней отсутствуют одинаковые элементарные дизъюнкции;
- дизъюнкции не содержат одинаковые переменные;
- все дизъюнкции содержат каждую переменную из входящих в конъюнктивную нормальную функцию такого типа.
Правила построения по таблице истинности
Дизъюнктивная форма
Если функция равна 1, то для всех наборов переменных, при которых это происходит, записывается произведение. Однако переменные, которые имеют значение 0, берутся с отрицанием.
Конъюнктивная форма
Когда функция равна 0, то для всех наборов переменных, при которых это происходит, записывается сумма. Однако переменные, которые имеют значение 1, берутся с отрицанием.
Алгоритм приведения к СДНФ и СКНФ
Рассмотрим логическую функцию в виде таблицы истинности.
Алгоритм построения СДНФ по таблице истинности выглядит следующим образом:
- Отметить наборы переменных, значение функции F на которых равно 1.
- Записать для всех отмеченных наборов конъюнкцию всех переменных так: если значение некоторой переменной в этом наборе равняется 1, в конъюнкцию включается сама переменная. В случае противного результата, в конъюнкцию включается ее отрицание.
- Связать полученные конъюнкции операциями дизъюнкции.
Построим совершенную ДНФ:
И как результат получим следующую СДНФ:
Алгоритм построения СКНФ по таблице истинности выглядит следующим образом:
- Отметить в таблице истинности наборы переменных, значение функции F на которых равно 0.
- Записать для всех отмеченных наборов дизъюнкцию всех переменных — в том случае, когда значение некоторой переменной в этом наборе равняется 0, в дизъюнкцию включается сама переменная, если происходит наоборот, то в дизъюнкцию включается ее отрицание.
- Связать полученные дизъюнкции операциями конъюнкции.
Построим совершенную КНФ:
И как результат получим следующую СКНФ:
Рассмотрев алгоритмы построения СДНФ и СКНФ ясно, что в случае подавляющей части наборов значений переменных функция равна 0, то значительно легче построить и СДНФ для получения ее формулы, а в обратном случае — СКНФ.
Доказательство эквивалентности
Эквивалентность — понятие, означающее, что две и более формул представляют одну и ту же функцию. Для обозначения эквивалентности могут использоваться следующие знаки: \( \equiv , = , \Leftrightarrow .\)
Доказать эквивалентность формул можно двумя способами.
- Первый заключается в построении и сравнении таблиц истинности обеих функций. В этом случае результат будет истинным только в том случае, когда оба высказывания либо ложны, либо истинны.
- Второй вариант — метод эквивалентных преобразований. Суть этого метода — построение цепи эквивалентных формул на основе ранее доказанных эквивалентностей.
Далее следуют примеры с некоторыми эквивалентными преобразованием в булевой алгебре и новыми эквивалентностями, которые возможно получить с их помощью.
Поглощение
Склеивание
Обобщенное склеивание
\(xz\;\vee\;y\overline z\;\vee\;xy\;=\;xz\;\vee y\overline z\)
\(xz\;\vee\;y\overline z\;\vee\;xy\;=\;xz\;\vee y\overline z\;\vee\;xyz\;\vee\;xy\overline z\;=\;xz\;\vee\;y\overline z\)
Расщепление
\(x\;\vee\;\overline xy\;=\;xy\;\vee\;x\overline y\;\vee\;\overline xy\;=\;xy\;\vee\;x\overline y\;\vee\;xy\;\vee\;\overline xy\;=\;x\;\cdot\;l\;\;\vee\;y\;\cdot\;l\;=\;x\;\vee\;y\)
Примеры с решением
Задача №1
Приведите к СКНФ \(((((A\rightarrow B)\rightarrow\overline A)\rightarrow\overline B)\rightarrow\overline C)\) .
Через применение закона де Моргана и правила \( x\;\rightarrow\;y\;=\;\overline x\;\vee\;y\) упростим выражения:
\(F\;=\;((((A\;\rightarrow\;B)\;\rightarrow\;\overline A)\;\rightarrow\overline B)\;\rightarrow\;\overline C)\;=\;(((\overline A\;\vee\;B)\;\rightarrow\;\overline A)\;\rightarrow\;\overline B)\;\rightarrow\overline C\;)\;=\)
\(=\;((((\overline A\;\vee\;B)\;\rightarrow\overline A)\;\rightarrow\overline B)\;\rightarrow\;\overline C)\;=\;((\overline<((\overline A\;\vee\;B)>\;\vee\;\overline A)\;\rightarrow\overline B)\;\rightarrow\overline C)\;=\)
\(=(((\overline A\;\vee\;B)\;\vee\;\overline A)\;\rightarrow\;\overline B)\;\rightarrow\;\overline C)\;=((\overline<(\overline<(\overline A\vee B)>\;\vee\;\overline A\;)>\;\vee\;\overline B)\;\rightarrow\;\overline C)\;=\)
\(=\;((\overline<(\overline A\;\vee\;B)>\;\vee\;\overline A)\;\wedge\;B)\;\vee\;\overline C\;=\;(((A\;\wedge\;\overline B)\;\vee\;\overline A)\;\wedge B)\;\vee\;\overline C\;=\)
\(=((A\overline B\;\vee\;\overline A)\;\vee\;\overline A)\;\wedge\;B)\;\vee\;\overline C\;=(((A\;\wedge\;\overline B)\;\vee\;\overline A)\;\wedge\;B)\;\vee\;\overline C\;=\)
\(=\;((A\overline B\;\vee\;\overline A)\;\wedge\;B)\;\vee\;\overline C\;=\;(A\overline BB\;\vee\;\overline AB)\;\vee\;\overline C\;=\;(0\;\vee\;\overline AB)\;\vee\;\overline C\;=\;\overline AB\;\vee\;\overline C\)
Далее приведем выражение к КНФ:
\(F\;=\;\overline AB\;\vee\;\overline C\;\;=\;(\overline A\;\vee\;\overline C)\;\wedge\;(B\;\vee\;\overline C)\)
Далее приведем выражение к СКНФ:
\(F\;=\;(\overline A\;\vee\;\overline C)\;\wedge\;(B\;\vee\;\overline C)\;=\;(\overline A\;\vee\:\overline C\;\vee\;B\overline B)\;\wedge\;(A\overline A\;\vee\;B\;v\;\overline C)\;=\)
\(=\;(\overline A\;\vee\;\overline C\;\vee\;B)\;\wedge\;(A\;\vee\;B\;\vee\;\overline C)\;\wedge\;(\overline A\;\vee\;\overline C\;\vee\;\overline B)\;\wedge\;(\overline A\;\vee\;B\;\;\overline C)\)
Задача №2
Используя эквивалентные преобразования, постройте ДНФ функции \(f(\widetilde x^n)\)
\(f(\widetilde x^3) = (\overline
\(f(\widetilde x^3) = (\overline
\(=(\overline
Что такое сднф функции
Пример ДНФ: [math]f(x,y,z) = (x \land y) \lor (y \land \neg
Пример СДНФ: [math]f(x,y,z) = (x \land \neg
Для любой булевой функции выполняется следующее соотношение, называемое разложением Шеннона:
[math]f(\vec
Данное соотношение легко проверить подстановкой возможных значений [math]x_i[/math] ( [math]0[/math] и [math]1[/math] ). Эта формула позволяет выносить [math]x_i[/math] за знак функции. Последовательно вынося [math]x_1[/math] , [math]x_2[/math] . [math]x_n[/math] за знак [math]f(\vec
[math]\neg x_1 \wedge \neg x_2 \wedge \ldots \wedge \neg x_
x_1 \wedge x_2 \wedge \ldots \wedge x_
\\ x_1 \wedge x_2 \wedge \ldots \wedge x_
Алгоритм построения СДНФ по таблице истинности
- В таблице истинности отмечаем те наборы переменных, на которых значение функции равно [math] 1 [/math] .
- Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть [math] 1 [/math] , то в конъюнкцию включаем саму переменную, иначе ее отрицание.
- Все полученные конъюнкции связываем операциями дизъюнкции.
Пример построения СДНФ для медианы
Построение СДНФ для медианы от трех аргументов
1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно [math] 1 [/math] .
| [math] x [/math] | [math] y [/math] | [math] z [/math] | [math] \langle x,y,z \rangle [/math] |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
|---|---|---|---|
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
2. Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть [math] 1 [/math] , то в конъюнкцию включаем саму переменную, иначе ее отрицание.
| [math] x [/math] | [math] y [/math] | [math] z [/math] | [math] \langle x,y,z \rangle [/math] | |
| 0 | 0 | 0 | 0 | |
| 0 | 0 | 1 | 0 | |
| 0 | 1 | 0 | 0 | |
| 0 | 1 | 1 | 1 | [math](\neg |
|---|---|---|---|---|
| 1 | 0 | 0 | 0 | |
| 1 | 0 | 1 | 1 | [math](x \land \neg |
| 1 | 1 | 0 | 1 | [math](x \land y \land \neg |
| 1 | 1 | 1 | 1 | [math](x \land y \land z)[/math] |
3. Все полученные конъюнкции связываем операциями дизъюнкции:
[math] \langle x,y,z \rangle = (x \land y \land z) \lor (\neg
Построение СДНФ для медианы от пяти аргументов
| [math] x_1 [/math] | [math] x_2 [/math] | [math] x_3 [/math] | [math]x_4[/math] | [math] x_5 [/math] | [math] \langle x_1, x_2, x_3, x_4, x_5 \rangle [/math] | |
| 0 | 0 | 0 | 0 | 0 | 0 | |
| 0 | 0 | 0 | 0 | 1 | 0 | |
| 0 | 0 | 0 | 1 | 0 | 0 | |
| 0 | 0 | 0 | 1 | 1 | 0 | |
| 0 | 0 | 1 | 0 | 0 | 0 | |
| 0 | 0 | 1 | 0 | 1 | 0 | |
| 0 | 0 | 1 | 1 | 0 | 0 | |
| 0 | 0 | 1 | 1 | 1 | 1 | [math](\neg |
|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 0 | 0 | |
| 0 | 1 | 0 | 0 | 1 | 0 | |
| 0 | 1 | 0 | 1 | 0 | 0 | |
| 0 | 1 | 0 | 1 | 1 | 1 | [math](\neg |
| 0 | 1 | 1 | 0 | 0 | 0 | |
| 0 | 1 | 1 | 0 | 1 | 1 | [math](\neg |
| 0 | 1 | 1 | 1 | 0 | 1 | [math](\neg |
| 0 | 1 | 1 | 1 | 1 | 1 | [math](\neg |
| 1 | 0 | 0 | 0 | 0 | 0 | |
| 1 | 0 | 0 | 0 | 1 | 0 | |
| 1 | 0 | 0 | 1 | 0 | 0 | |
| 1 | 0 | 0 | 1 | 1 | 1 | [math](x_1 \land \neg |
| 1 | 0 | 1 | 0 | 0 | 0 | |
| 1 | 0 | 1 | 0 | 1 | 1 | [math](x_1 \land \neg |
| 1 | 0 | 1 | 1 | 0 | 1 | [math](x_1 \land \neg |
| 1 | 0 | 1 | 1 | 1 | 1 | [math](x_1 \land \neg |
| 1 | 1 | 0 | 0 | 0 | 0 | |
| 1 | 1 | 0 | 0 | 1 | 1 | [math](x_1 \land x_2 \land \neg |
| 1 | 1 | 0 | 1 | 0 | 1 | [math](x_1 \land x_2 \land \neg |
| 1 | 1 | 0 | 1 | 1 | 1 | [math](x_1 \land x_2 \land \neg |
| 1 | 1 | 1 | 0 | 0 | 1 | [math](x_1 \land x_2 \land x_3 \land \neg |
| 1 | 1 | 1 | 0 | 1 | 1 | [math](x_1 \land x_2 \land x_3 \land \neg |
| 1 | 1 | 1 | 1 | 0 | 1 | [math](x_1 \land x_2 \land x_3 \land x_4 \land \neg |
| 1 | 1 | 1 | 1 | 1 | 1 | [math](x_1 \land x_2 \land x_3 \land x_4 \land x_5)[/math] |
[math] \langle x_1, x_2, x_3, x_4, x_5 \rangle = (\overline
Примеры СДНФ для некоторых функций
Стрелка Пирса: [math] x \downarrow y = (\neg
Исключающее или: [math] x \oplus y \oplus z = (\overline
Построение СКНФ и СДНФ по таблице истинности
Нормальная форма логической формулы не содержит знаков импликации, эквивалентности и отрицания неэлементарных формул.
Нормальная форма существует в двух видах:
конъюнктивная нормальная форма (КНФ) — конъюнкция нескольких дизъюнкций, например, $\left(A\vee \overline\vee C\right)\wedge \left(A\vee C\right)$;
дизъюнктивная нормальная форма (ДНФ) — дизъюнкция нескольких конъюнкций, например, $\left(A\wedge \overline\wedge C\right)\vee \left(B\wedge C\right)$.
Совершенная конъюнктивная нормальная форма (СКНФ) — это КНФ, удовлетворяющая трем условиям:
не содержит одинаковых элементарных дизъюнкций;
ни одна из дизъюнкций не содержит одинаковых переменных;
каждая элементарная дизъюнкция содержит каждую переменную из входящих в данную КНФ.
Любая булева формула, которая не является тождественно истинной, может быть представлена в СКНФ.
Правила построения СКНФ по таблице истинности
Для каждого набора переменных, при котором функция равна 0, записывается сумма, причем переменные, которые имеют значение 1, берутся с отрицанием.
Совершенная дизъюнктивная нормальная форма (СДНФ) — это ДНФ, удовлетворяющая трем условиям:
не содержит одинаковых элементарных конъюнкций;
ни одна из конъюнкций не содержит одинаковых переменных;
каждая элементарная конъюнкция содержит каждую переменную из входящих в данную ДНФ, к тому же в одинаковом порядке.
Любая булева формула, которая не является тождественно ложной, может быть представлена в СДНФ, к тому же единственным образом.
Правила построения СДНФ по таблице истинности
Для каждого набора переменных, при котором функция равна 1, записывается произведение, причем переменные, которые имеют значение 0 берут с отрицанием.
Примеры нахождения СКНФ и СДНФ
Записать логическую функцию по ее таблице истинности:
Решение:
Воспользуемся правилом построения СДНФ:
\[F\left(x_1,\ x_2,\ x_3\right)=\left(\overline
Воспользуемся правилом построения СКНФ:
\[F\left(x_1,\ x_2,\ x_3\right)=\left(x_1\vee \overline
Функция задана таблицей истинности:
Представить эту функцию в виде СДНФ и СКНФ.
Решение:
Запишем логическую функцию в СДНФ. Для удобства решения добавим к таблице вспомогательный столбец.
Используя правило составления СДНФ не забываем вводить знак отрицания для переменных со значением 0. Инвертировать нулевые значения переменных обязательно, т.к. иначе они превратят значения конъюнкций в нули основной функции.
Полученные во вспомогательном столбце конъюнкции соединим знаком дизъюнкции и получим искомую логическую функцию в виде СДНФ:
Запишем логическую функцию в СКНФ.
Используя правило составления СКНФ не забываем вводить знак отрицания для переменных со значением 1. Инвертировать единичные значения переменных обязательно, т.к. иначе они превратят значения дизъюнкций в единицы основной функции.
Полученные во вспомогательном столбце дизъюнкции соединим знаком конъюнкции и получим искомую логическую функцию в виде СКНФ: