Диана Загировна Филиппенкова
Эксперт по предмету «Информатика»
Задать вопрос автору статьи
Нормальная форма логической формулы не содержит знаков импликации, эквивалентности и отрицания неэлементарных формул.
Нормальная форма существует в двух видах:
-
конъюнктивная нормальная форма (КНФ) — конъюнкция нескольких дизъюнкций, например, $left(Avee overline{B}vee Cright)wedge left(Avee Cright)$;
-
дизъюнктивная нормальная форма (ДНФ) — дизъюнкция нескольких конъюнкций, например, $left(Awedge overline{B}wedge Cright)vee left(Bwedge Cright)$.
СКНФ
Совершенная конъюнктивная нормальная форма (СКНФ) — это КНФ, удовлетворяющая трем условиям:
-
не содержит одинаковых элементарных дизъюнкций;
-
ни одна из дизъюнкций не содержит одинаковых переменных;
-
каждая элементарная дизъюнкция содержит каждую переменную из входящих в данную КНФ.
Любая булева формула, которая не является тождественно истинной, может быть представлена в СКНФ.
Правила построения СКНФ по таблице истинности
Для каждого набора переменных, при котором функция равна 0, записывается сумма, причем переменные, которые имеют значение 1, берутся с отрицанием.
СДНФ
Совершенная дизъюнктивная нормальная форма (СДНФ) — это ДНФ, удовлетворяющая трем условиям:
-
не содержит одинаковых элементарных конъюнкций;
-
ни одна из конъюнкций не содержит одинаковых переменных;
-
каждая элементарная конъюнкция содержит каждую переменную из входящих в данную ДНФ, к тому же в одинаковом порядке.
Любая булева формула, которая не является тождественно ложной, может быть представлена в СДНФ, к тому же единственным образом.
Правила построения СДНФ по таблице истинности
Для каждого набора переменных, при котором функция равна 1, записывается произведение, причем переменные, которые имеют значение 0 берут с отрицанием.
Примеры нахождения СКНФ и СДНФ
Пример 1
Записать логическую функцию по ее таблице истинности:
Рисунок 1.
Решение:
Воспользуемся правилом построения СДНФ:
Рисунок 2.
Получим СДНФ:
[Fleft(x_1, x_2, x_3right)=left(overline{x_1}wedge overline{x_2}wedge overline{x_3}right)vee left(overline{x_1}wedge overline{x_2}wedge x_3right)vee left(x_1wedge overline{x_2}wedge overline{x_3}right)vee left(x_1wedge overline{x_2}wedge x_3right)vee left(x_1wedge x_2wedge x_3right)]
Воспользуемся правилом построения СКНФ:
Рисунок 3.
Получим СКНФ:
[Fleft(x_1, x_2, x_3right)=left(x_1vee overline{x_2}vee x_3right)wedge left(x_1vee overline{x_2}vee overline{x_3}right)wedge left(overline{x_1}vee overline{x_2}vee x_3right)]
«Построение СКНФ и СДНФ по таблице истинности» 👇
Пример 2
Функция задана таблицей истинности:
Рисунок 4.
Представить эту функцию в виде СДНФ и СКНФ.
Решение:
-
Запишем логическую функцию в СДНФ. Для удобства решения добавим к таблице вспомогательный столбец.
Используя правило составления СДНФ не забываем вводить знак отрицания для переменных со значением 0. Инвертировать нулевые значения переменных обязательно, т.к. иначе они превратят значения конъюнкций в нули основной функции.
Рисунок 5.
Полученные во вспомогательном столбце конъюнкции соединим знаком дизъюнкции и получим искомую логическую функцию в виде СДНФ:
[Fleft(x_1,x_2,x_3,x_4right)=left(overline{x}wedge overline{y}wedge zwedge fright)vee left(overline{x_1}wedge x_2wedge overline{x_3}wedge overline{x_4}right)vee left(overline{x_1}wedge x_2wedge x_3wedge x_4right)vee left(x_1wedge overline{x_2}wedge overline{x_3}wedge overline{x_4}right).]
-
Запишем логическую функцию в СКНФ.
Используя правило составления СКНФ не забываем вводить знак отрицания для переменных со значением 1. Инвертировать единичные значения переменных обязательно, т.к. иначе они превратят значения дизъюнкций в единицы основной функции.
Рисунок 6.
Полученные во вспомогательном столбце дизъюнкции соединим знаком конъюнкции и получим искомую логическую функцию в виде СКНФ:
[Fleft(x_1,x_2,x_3,x_4right)=left(x_1vee x_2vee x_3vee x_4right)wedge left(x_1vee x_2vee x_3vee overline{x_4}right)wedge left(x_1vee x_2vee overline{x_3}vee x_4right)wedge left(x_1vee overline{x_2}vee x_3vee overline{x_4}right)wedge left(x_1vee overline{x_2}vee overline{x_3}vee x_4right)wedge left(overline{x_1}vee x_2vee x_3vee overline{x_4}right)wedge left(overline{x_1}vee x_2vee overline{x_3}vee x_4right)wedge left(overline{x_1}vee x_2vee overline{x_3}vee overline{x_4}right)wedge left(overline{x_1}vee overline{x_2}vee x_3vee x_4right)wedge left(overline{x_1}vee overline{x_2}vee x_3vee overline{x_4}right)wedge left(overline{x_1}vee overline{x_2}vee overline{x_3}vee x_4right)wedge left(overline{x_1}vee overline{x_2}vee overline{x_3}vee overline{x_4}right).]
Находи статьи и создавай свой список литературы по ГОСТу
Поиск по теме
Что такое СДНФ
Нормальная форма логической формулы характеризуется тем, что для нее не свойственны эквивалентность, отрицание формул неэлементарного типа и знаки импликации.
Существует две формы нормального типа: КНФ (конъюнктивная нормальная форма) и ДНФ (дизъюнктивная нормальная форма).
Определение
СДНФ — совершенная дизъюнктивная нормальная форма формулы. СДНФ — способ написания функции алгебры логики в качестве логического выражения.
Осторожно! Если преподаватель обнаружит плагиат в работе, не избежать крупных проблем (вплоть до отчисления). Если нет возможности написать самому, закажите тут.
СДНФ формулы — это равнозначная ей формула, которая представляет собой дизъюнкцию элементарных конъюнкций, при которых функция достигает показателя «1».
ДНФ выглядит следующим образом:
((A;wedge;overline B;wedge;C);vee;(B;wedge;C))
СДНФ обладает некоторыми определенными свойствами:
- включает различные элементарные конъюнкции;
- все логические слагаемые формулы содержат все переменные, которые входят в функцию F;
- ни в одном логическом слагаемом не содержится переменная и её отрицание.
К СДНФ возможно привести любую формулу алгебры логики. Исключение составляет только тождественно ложная формула. СДНФ можно получить как используя таблицы истинности, так и через равносильные преобразования.
Примечание
При построении таблицы истинности важно помнить, что логические переменные со значением «0» необходимо брать с отрицанием.
Что такое СКНФ
Определение
СКНФ — совершенная конъюнктивная нормальная форма. Формулу можно назвать таковой, когда она — конъюнкция неповторяющихся элементарных дизъюнкций.
КНФ имеет вид:
((A;vee;overline B;vee;C);wedge;(A;vee;C))
Формула должна соответствовать нескольким условиям, чтобы называться СКНФ:
- в ней отсутствуют одинаковые элементарные дизъюнкции;
- дизъюнкции не содержат одинаковые переменные;
- все дизъюнкции содержат каждую переменную из входящих в конъюнктивную нормальную функцию такого типа.
Правила построения по таблице истинности
Дизъюнктивная форма
Если функция равна 1, то для всех наборов переменных, при которых это происходит, записывается произведение. Однако переменные, которые имеют значение 0, берутся с отрицанием.
Конъюнктивная форма
Когда функция равна 0, то для всех наборов переменных, при которых это происходит, записывается сумма. Однако переменные, которые имеют значение 1, берутся с отрицанием.
Алгоритм приведения к СДНФ и СКНФ
Рассмотрим логическую функцию в виде таблицы истинности.
Алгоритм построения СДНФ по таблице истинности выглядит следующим образом:
- Отметить наборы переменных, значение функции F на которых равно 1.
- Записать для всех отмеченных наборов конъюнкцию всех переменных так: если значение некоторой переменной в этом наборе равняется 1, в конъюнкцию включается сама переменная. В случае противного результата, в конъюнкцию включается ее отрицание.
- Связать полученные конъюнкции операциями дизъюнкции.
Построим совершенную ДНФ:
И как результат получим следующую СДНФ:
(F(x_1,;x_2,;x_3);=;(overline{x_1}wedgeoverline{x_2}wedgeoverline{x_3});vee(overline{x_1};wedge;overline{x_2};wedge;x_3);vee(x_1;wedge;overline{x_2};wedge;overline{x_3});vee;(x_1;wedge;overline{x_2};wedge;x_3);vee;(x_1;wedge;x_2;wedge;x_3))
Алгоритм построения СКНФ по таблице истинности выглядит следующим образом:
- Отметить в таблице истинности наборы переменных, значение функции F на которых равно 0.
- Записать для всех отмеченных наборов дизъюнкцию всех переменных — в том случае, когда значение некоторой переменной в этом наборе равняется 0, в дизъюнкцию включается сама переменная, если происходит наоборот, то в дизъюнкцию включается ее отрицание.
- Связать полученные дизъюнкции операциями конъюнкции.
Построим совершенную КНФ:
И как результат получим следующую СКНФ:
(F(x_1,;x_2,;x_3);=;(x_1;vee;overline{x_2};vee;x_3);wedge;(x_1;vee;overline{x_2};vee;overline{x_3});wedge;(overline{x_1};vee;overline{x_2};vee;x_3))
Рассмотрев алгоритмы построения СДНФ и СКНФ ясно, что в случае подавляющей части наборов значений переменных функция равна 0, то значительно легче построить и СДНФ для получения ее формулы, а в обратном случае — СКНФ.
Доказательство эквивалентности
Эквивалентность — понятие, означающее, что две и более формул представляют одну и ту же функцию. Для обозначения эквивалентности могут использоваться следующие знаки: ( equiv , = , Leftrightarrow .)
Доказать эквивалентность формул можно двумя способами.
- Первый заключается в построении и сравнении таблиц истинности обеих функций. В этом случае результат будет истинным только в том случае, когда оба высказывания либо ложны, либо истинны.
- Второй вариант — метод эквивалентных преобразований. Суть этого метода — построение цепи эквивалентных формул на основе ранее доказанных эквивалентностей.
Далее следуют примеры с некоторыми эквивалентными преобразованием в булевой алгебре и новыми эквивалентностями, которые возможно получить с их помощью.
Поглощение
(x;vee;xy;=;x)
(x(x;vee;y);=;x;)
Доказательство эквивалентности:
(x;vee;xy;=;x;cdot;l;vee;xy;=;x(l;vee;y);=;x)
(x(x;vee;y);=;xx;vee;xy;=;x;vee;xy;=;x)
Склеивание
(xy;vee;xoverline y;=;x)
Доказательство эквивалентности:
(xy;vee;xoverline y;=;x(y;vee;overline y);=;x;cdot;l;=;x)
Обобщенное склеивание
(xz;vee;yoverline z;vee;xy;=;xz;vee yoverline z)
Доказательство эквивалентности
(xz;vee;yoverline z;vee;xy;=;xz;vee yoverline z;vee;xyz;vee;xyoverline z;=;xz;vee;yoverline z)
Расщепление
(x;vee;overline xy;=;x;vee;y)
Доказательство эквивалентности
(x;vee;overline xy;=;xy;vee;xoverline y;vee;overline xy;=;xy;vee;xoverline y;vee;xy;vee;overline xy;=;x;cdot;l;;vee;y;cdot;l;=;x;vee;y)
Примеры с решением
Задача №1
Приведите к СКНФ (((((Arightarrow B)rightarrowoverline A)rightarrowoverline B)rightarrowoverline C)).
Через применение закона де Моргана и правила( x;rightarrow;y;=;overline x;vee;y) упростим выражения:
(F;=;((((A;rightarrow;B);rightarrow;overline A);rightarrowoverline B);rightarrow;overline C);=;(((overline A;vee;B);rightarrow;overline A);rightarrow;overline B);rightarrowoverline C;);=)
(=;((((overline A;vee;B);rightarrowoverline A);rightarrowoverline B);rightarrow;overline C);=;((overline{((overline A;vee;B)};vee;overline A);rightarrowoverline B);rightarrowoverline C);=)
(=(((overline A;vee;B);vee;overline A);rightarrow;overline B);rightarrow;overline C);=((overline{(overline{(overline Avee B)};vee;overline A;)};vee;overline B);rightarrow;overline C);=)
(=;(overline{(overline{(overline{(overline A;vee;B)};vee;overline A)};vee;overline B)};vee;overline C);=;(((A;vee;B);vee;overline A);vee;overline B);vee;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;=)
(=((Aoverline B;vee;overline A);vee;overline A);wedge;B);vee;overline C;=(((A;wedge;overline B);vee;overline A);wedge;B);vee;overline C;=)
(=;((Aoverline B;vee;overline A);wedge;B);vee;overline C;=;(Aoverline 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;Boverline B);wedge;(Aoverline 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{x_1}x_2;oplus;x_3);cdot;(x_1x_3;rightarrow;x_2))
Преобразуем функцию:
(f(widetilde x^3) = (overline{x_1}x_2;oplus;x_3);cdot;(x_1x_3;rightarrow;x_2) = ((overline{x_1}x_2;cdot;overline{x_3};);vee;(overline{overline{x_1}x_2};cdot;x_3));cdot;(overline{x_1x_3};vee;x_2);=)
(=;((overline{x_1}x_2overline{x_3});vee;((overline{overline{x_1}};vee;overline{x_2});x_3);cdot;(overline{x_1};vee;overline{x_3};vee;x_2);=;((overline{x_1}x_{2;}overline{x_3});vee;((x_1;vee;overline{x_2});x_3);cdot;(overline{x_1};vee;overline{x_3};vee;x_2);=)
(=;(overline{x_1}x_2overline{x_3};vee;x_1x_3;vee;overline{x_2}x_3);cdot;(overline{x_1};vee;overline{x_3};vee;x_2);=)
(=(overline{x_1}x_2overline{x_3};cdot(x_1vee x_3vee x_2);vee;x_1x_3;cdot;(overline{x_1};vee;overline{x_3};vee;x_2);vee;overline{x_2}x_3;cdot;(overline{x_1};vee;overline{x_3};vee;x_2));=)
(=;(overline{x_1}x_2overline{x_3};vee;(x_1;x_3overline{x_1};vee;x_1x_3overline{x_3};vee;x_1x_3x_2);vee;(overline{x_2}x_3overline{x_1};vee;overline{x_2}x_3overline{x_3};vee;overline{x_2}x_3x_2);=)
(=;(overline{x_1}x_2overline{x_3};vee;0;vee;0;vee;x_1x_2x_3;vee;overline{x_1}overline{x_2}x_3;vee;0;vee;0);=)
(=;overline{x_1}x_2overline{x_3};vee;x_1x_2x_3;vee;overline{x_1}overline{x_2}x_3)
Дизъюнктивная нормальная форма
Дизъюнкти́вная норма́льная фо́рма (ДНФ) в булевой логике — нормальная форма, в которой булева формула имеет вид дизъюнкции конъюнкций литералов. Любая булева формула может быть приведена к ДНФ.
Формулы в ДНФ:
Формулы не в ДНФ:
Алгоритм построения ДНФ
1) Избавиться от всех логических операций, содержащихся в формуле, заменив их основными: конъюнкцией, дизъюнкцией, отрицанием. Это можно сделать, используя равносильные формулы:
2) Заменить знак отрицания, относящийся ко всему выражению, знаками отрицания, относящимися к отдельным переменным высказываниям на основании формул:
3) Избавиться от знаков двойного отрицания.
4) Применить, если нужно, к операциям конъюнкции и дизъюнкции свойства дистрибутивности и формулы поглощения.
Пример построения ДНФ
Приведем к ДНФ формулу :
Выразим логические операции → и ↓ через :
В полученной формуле перенесем отрицание к переменным и сократим двойные отрицания:
Совершенная дизъюнктивная нормальная форма
Соверше́нная дизъюнкти́вная норма́льная фо́рма (СДНФ) — это такая ДНФ, которая удовлетворяет трём условиям:
- в ней нет одинаковых элементарных конъюнкций
- в каждой конъюнкции нет одинаковых пропозициональных букв
- каждая элементарная конъюнкция содержит каждую пропозициональную букву из входящих в данную ДНФ пропозициональных букв, причём в одинаковом порядке.
Для любой функции алгебры логики существует своя СДНФ, причём единственная.
Для того, чтобы получить СДНФ функции, требуется составить её таблицу истинности. К примеру, возьмём одну из таблиц истинности:
 |
 |
 |
 |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 |
В ячейках результата отмечаются лишь те комбинации, которые приводят логическое выражение в состояние единицы. Далее рассматриваются значения переменных при которых функция равна 1. Если значение переменной равно 0, то она записывается с инверсией. Если значение переменной равно 1, то без инверсии.
Первая строка содержит 1 в указанном поле. Отмечаются значения всех трёх переменных, это:
Нулевые значения — тут все переменные представлены нулями — записываются в конечном выражении инверсией этой переменной. Первый член СДНФ рассматриваемой функции выглядит так: 
Переменные второго члена:
в этом случае будет представлен без инверсии: 
Таким образом анализируются все ячейки . Совершенная ДНФ этой функции будет дизъюнкцией всех полученных членов (элементарных конъюнкций).
Совершенная ДНФ этой функции:
Переход от ДНФ к СДНФ
Если в какой-то простой конъюнкции недостаёт переменной, например, Z, вставляем в неё выражение
- ,
,
после чего раскрываем скобки (при этом повторяющиеся дизъюнктные слагаемые не пишем, так как 
по закону идемпотентности). Например:
Таким образом, из ДНФ получили СДНФ.
Известно два способа задания логических
функций: с помощью формулы и с помощью
таблицы истинности. По формуле легко
составляется таблица. На практике при
конструировании различных электронных
устройств часто возникает обратная
задача – от таблицы истинности перейти
к формуле, чтобы на ее основе построить
функциональную схему.
Введем следующие определения:
Элементарной
конъюнкцией называется конъюнкция
нескольких переменных, взятых с отрицанием
или без отрицания, причем среди переменных
могут быть одинаковые.
Элементарной
дизъюнкцией называется дизъюнкция
нескольких переменных, взятых с отрицанием
или без отрицания, причем среди переменных
могут быть одинаковые.
Всякую дизъюнкцию
элементарных конъюнкций назовем
дизъюнктивной нормальной формой (ДНФ).
Всякую конъюнкцию
элементарных дизъюнкций назовем
конъюнктивной нормальной формой (КНФ).
Совершенной
дизъюнктивной нормальной формой (СДНФ)
называется ДНФ, в которой нет одинаковых
элементарных конъюнкций и все конъюнкции
состоят из одного и того же набора
переменных, в который каждая переменная
входит только один раз (возможно, с
отрицанием).
Совершенной
конъюнктивной нормальной формой (СКНФ)
называется КНФ, в которой нет одинаковых
элементарных дизъюнкций и все дизъюнкции
состоят из одного и того же набора
переменных, в который каждая переменная
входит только один раз (возможно, с
отрицанием).
Приведем примеры формул, соответствующих
и не соответствующих этим определениям:
|
НАЗВАНИЕ
В |
Формула,
соответствующая |
ФОРМУЛА,
НЕ ОПРЕДЕЛЕНИЮ |
|
Элементарная дизъюнкция |
|
|
|
Элементарная конъюнкция |
|
|
|
ДНФ |
|
ДНФ |
|
КНФ |
|
КНФ |
|
СДНФ |
|
|
|
СКНФ |
|
|
Любую функцию,
кроме констант 0 и 1, можно представить
в виде как СДНФ, так и СКНФ.
Этот факт является теоремой алгебры
логики. Из него следует, что любая формула
(кроме констант 0 и 1) может быть преобразован
к виду как СДНФ, так и СКНФ. Константа 0
может быть представлена только СКНФ
(
),
а константа 1 – только СДНФ (
).
Из вышесказанного следует, что если
надо построить формулу некоторой функции
по таблице истинности этой функции, то
всегда можно получить СКНФ или СДНФ
этой функции.
Алгоритм получения
СДНФ по таблице истинности:
-
Отметить те строчки таблицы истинности,
в последнем столбце которых стоят 1:
-
X
Y
F(X,Y)
0
0
0
0
1
1*
1
0
1*
1
1
0
-
Выписать для каждой отмеченной строки
конъюнкциювсех переменных следующим
образом: если значение некоторой
переменной в данной строкеравно 1,
то в конъюнкцию включатьсаму эту
переменную, еслиравно 0, то ееотрицание:
– для 2-й строки;
– для 3-й строки.
-
Все полученные конъюнкции связать в
дизъюнкцию:
.
.
Алгоритм получения
СКНФ по таблице истинности:
-
Отметить те строки таблицы истинности,
в последнем столбце которых стоит 0:
-
X
Y
F(X,Y)
0
0
0*
0
1
1
1
0
1
1
1
0*
-
Выписать для каждой отмеченной строки
дизъюнкциювсех переменных следующим
образом: если значение некоторой
переменной в данной строкеравно 0,
то в дизъюнкцию включатьсаму эту
переменную, еслиравно 1, то ееотрицание:
– для 1-й строки;
– для 4-й строки.
-
Все полученные дизъюнкции связать в
конъюнкцию:
.
.
Покажем, что полученные по двум алгоритмам
СДНФ и СКНФ эквивалентны. Преобразуем
СКНФ по правилам алгебры логики:
.
Примечание: для нахождения
формулы по таблице истинности рекомендуется
использовать тот из двух алгоритмов, в
котором в таблице помечается меньше
строк.
-
ТИПОВЫЕ ЛОГИЧЕСКИЕ
УСТРОЙСТВА ЭВМ.
К типовым логическим устройствам ЭВМ
относятся сумматоры, полусумматоры,
триггеры, счетчики, регистры, шифраторы,
дешифраторы.
-
СУММАТОРЫ.
Сумматор является
основным узлом арифметико-логического
устройства ЭВМ и служит для суммирования
чисел посредством поразрядного сложения.
Сумматор выполняет сложение многозначных
двоичных чисел. Он представляет собой
последовательное соединение одноразрядных
двоичных сумматоров, каждый из которых
осуществляет сложение в одном разряде.
При этом если сумма двух цифр в данном
разряде больше или равна основанию
используемой системы счисления, то
возникает перенос старшего разряда в
соседний сумматор.
Одноразрядный сумматор должен иметь
два выхода: для суммы и для переносимого
значения. У него может быть два или три
(для складываемых значений и значения
переноса) входа.
Одноразрядный
двоичный сумматор на два входа и два
выхода называется одноразрядным
полусумматором.
Одноразрядный
двоичный сумматор на три входа и два
выхода называется одноразрядным
сумматором на три входа.
Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]
- #
- #
- #
- #
- #
- #
- #
- #
- #
- #
- #
Для любой логической формулы можно построить бесконечное количество равносильных ей формул. Для этого потребуется произвести некоторое количество тождественных преобразований. Одной из главных задач в алгебре логики является нахождение канонических форм формул. Проще говоря таких, которые построены по одному канону (правилу).
Форма представления какой-либо логической функции будет считаться нормальной, если она выражена через конъюнкцию, дизъюнкцию, а также отрицание переменных. Среди всех нормальных форм можно выделить совершенно нормальные. Это тот случай, когда функция может быть записана только одним единственным способом.
Классы СКНФ и СДНФ
В при решении задач в алгебре логики особая роль отводится классам конъюнктивных и дизъюнктивных совершенно нормальных форм. Они основаны на стандартных понятиях элементарной конъюнкции и дизъюнкции.
Определение 1 — 2
Элементарной конъюнкцией принято называть формулу в том случае, когда она представляет собой конъюнкцию любого количества переменных, которые берутся без отрицания либо с отрицанием. При этом одночленной элементарной конъюнкцией считается только одна единственная переменная либо ее отрицание.
Элементарной дизъюнкцией называют формулу при условии, что она будет являться дизъюнкцией некоторого любого количества переменных и отрицаний, при этом она может быть и одночленной.
СКНФ
Форма любой логической формулы нормального типа не может содержать знаки эквивалентности, импликации, а также отрицания неэлементарных формул. Она может существовать только в двух видах:
- КНФ – конъюнктивная нормальная форма, представляющая собой конъюнкцию нескольких дизъюнкций. К примеру, [(A vee bar{B} vee C) wedge(A vee C)];
- ДНФ – дизъюнктивная нормальная форма, которая является дизъюнкцией нескольких конъюнкций. К примеру, [(A wedge bar{B} wedge C) vee(A wedge C)].
Определение 3
Совершенной конъюнктивной нормальной формой (СКНФ) называют КНФ, удовлетворяющую нескольким условиям:
- В ней не содержится двух и более элементарных дизъюнкций;
- Во всех дизъюнкциях отсутствуют одинаковые переменные;
- Каждая ДНФ содержит в себе все переменные из входящих в нее КНФ.
Любую булеву формулу, не являющуюся тождественной истиной, можно представить в виде СКНФ.
Правила построения СКНФ
В алгебре логики для любого набора переменных, при котором конечное значение функции становится нулевым, можно записать сумму. При этом переменные, имеющие числовые значение больше единицы, должны браться с отрицательным знаком.
Построение должно осуществляться по следующему алгоритму:
- В таблице нужно отметить такие наборы переменных, при которых [f=1].
- Для каждого выбранного набора переменных записываем КНФ, при этом если значение какой-либо из них равно 1, то она включается в неизменном виде, иначе – ее отрицание.
- На последнем этапе все полученные конъюнкции следует связать операциями дизъюнкции.
СНДФ
Определение 4
Совершенной дизъюнктивной нормальной формой (СНДФ) называют удовлетворяющую нескольким условиям ДНФ. Всего должно выполняться три условия:
- В ДНФ не должно содержаться двух и более одинаковых СКНФ.
- Ни в одной из конъюнкций не должно содержаться одинаковых переменных.
- В каждой элементарной КНФ должны содержаться все переменные, входящих в нее ДНФ, при этом их порядок должен полностью совпадать.
Любую булеву формулу в алгебре логики, не являющуюся тождественно ложной, можно представить в виде СНДФ, но только в одном единственном виде.
Правила построения СДНФ
Если существует определённый набор переменных, при котором значение функции равно единице, то можно записать произведения, учитывая, что переменные, значение которых больше нуля, нужно брать с отрицанием.
Алгоритм построения будет следующим:
- В таблице отмечаются все те наборы переменных, при которых [f=0]
- Для каждого отмеченного набора всех переменных записывается ДНФ, при этом если значение какой-либо из них равно нулю, то включается сама переменная, в любом другом случае ее нужно инвертировать.
- В конце все полученные дизъюнкции связываются друг с другом операциями конъюнкции.
Нет времени решать самому?
Наши эксперты помогут!
Примеры нахождения СКНФ и СДНФ
Рассмотрим несколько примеров нахождения СКНФ и СДНФ с помощью данных таблицы истинности.
Примеры 1 — 2
Необходимо по таблице истинности записать логическую функцию.
Решение. Для того чтобы выполнить задачу будем использовать правило построения СДНФ.
Получим СДНФ, которая имеет следующий вид:
[Fleft(x_{1}, x_{2}, x_{3}right)=left(overline{x_{1}} wedge overline{x_{2}} wedge overline{x_{3}}right) veeleft(overline{x_{1}} wedge overline{x_{2}} wedge x_{3}right) veeleft(x_{1} wedge overline{x_{2}} wedge overline{x_{3}}right) veeleft(x_{1} wedgeright.left.overline{x_{2}} wedge x_{3}right) veeleft(x_{1} wedge x_{2} wedge x_{3}right)]
Далее будем действовать согласно правилу построения СКНФ:
В результате получим:
[Fleft(x_{1}, x_{2}, x_{3}right)=left(x_{1} wedge overline{x_{2}} wedge x_{3}right) wedgeleft(x_{1} wedge overline{x_{2}} wedge overline{x_{3}}right) wedgeleft(overline{x_{1}} wedge overline{x_{2}} wedge x_{3}right)]
Требуется представить функцию, которая задана в таблице в виде СДНФ и СКНФ.
Решение: Для начала запишем в СНДФ заданную логическую функцию. Чтобы было проще, добавим еще один вспомогательный столбец. Руководствуемся правилом составления СДНФ и учитываем, что требуется ввести знак отрицания, если значение переменной будет нулевым. Это нужно для того, чтобы они не превратили в нули основной функции значение конъюнкции.
Значения, которые получились во вспомогательном столбце соединяем знаком дизъюнкции, в результате чего получаем искомую логическую функцию, которая примет следующий вид:
[Fleft(x_{1}, x_{2}, x_{3}, x_{4}right)=(bar{x} wedge bar{y} wedge z wedge f) veeleft(overline{x_{1}} wedge overline{x_{2}} wedge overline{x_{3}} wedge overline{x_{4}}right) veeleft(overline{x_{1}} wedge x_{2} wedge x_{3} wedgeright.left.x_{4}right) veeleft(x_{1} wedge overline{x_{2}} wedge overline{x_{3}} wedge overline{x_{4}}right)]
После этого потребуется записать логическую функцию в СКНФ. Для этого используем правило ее составления и вводим знаки отрицания для тех переменных, значение которых равно 1. Если пренебречь инвертированием единичных значений, то они могут превратить ДНФ в единицы основных функций.
Все полученные нами значения во вспомогательном столбце соединяем знаком конъюнкции и в итоге получаем логическую функцию в следующем виде.
[Fleft(x_{1}, x_{2}, x_{3}, x_{4}right)=left(x_{1} vee x_{2} vee x_{3} vee x_{4}right) wedgeleft(x_{1} vee x_{2} vee x_{3} vee overline{x_{4}}right) wedgeleft(x_{1} vee x_{2} veeright.\left.overline{x_{3}} vee x_{4}right) wedgeleft(x_{1} vee overline{x_{2}} vee x_{3} vee overline{x_{4}}right) wedgeleft(x_{1} vee overline{x_{2}} vee overline{x_{3}} vee x_{4}right) wedgeleft(overline{x_{1}} vee x_{2} vee x_{3} veeright.\left.overline{x_{4}}right) wedgeleft(overline{x_{1}} vee x_{2} vee overline{x_{3}} vee x_{4}right) wedgeleft(overline{x_{1}} vee x_{2} vee overline{x_{3}} vee overline{x_{4}}right) wedgeleft(overline{x_{1}} vee overline{x_{2}} vee x_{3} vee x_{4}right) wedge\left(overline{x_{1}} vee overline{x_{2}} vee x_{3} vee overline{x_{4}}right) wedgeleft(overline{x_{1}} vee overline{x_{2}} vee overline{x_{3}} vee x_{4}right) wedgeleft(overline{x_{1}} wedge overline{x_{2}} wedge overline{x_{3}} wedge overline{x_{4}}right)]
После рассмотрения примеров построения СДНФ и СКНФ с использованием таблицы истинности, стал понятен принцип построения логических функций.