Как найти сднф на наборах

Что такое СДНФ 

Нормальная форма логической формулы характеризуется тем, что для нее не свойственны эквивалентность, отрицание формул неэлементарного типа и знаки импликации.

Существует две формы нормального типа: КНФ (конъюнктивная нормальная форма) и ДНФ (дизъюнктивная нормальная форма).

ДНФ выглядит следующим образом:

((A;wedge;overline B;wedge;C);vee;(B;wedge;C))

СДНФ обладает некоторыми определенными свойствами:

• включает различные элементарные конъюнкции;
• все логические слагаемые формулы содержат все переменные, которые входят в функцию F;
• ни в одном логическом слагаемом не содержится переменная и её отрицание.

К СДНФ возможно привести любую формулу алгебры логики. Исключение составляет только тождественно ложная формула. СДНФ можно получить как используя таблицы истинности, так и через равносильные преобразования.

Что такое СКНФ

КНФ имеет вид:

((A;vee;overline B;vee;C);wedge;(A;vee;C))

Формула должна соответствовать нескольким условиям, чтобы называться СКНФ:

• в ней отсутствуют одинаковые элементарные дизъюнкции;
• дизъюнкции не содержат одинаковые переменные;
• все дизъюнкции содержат каждую переменную из входящих в конъюнктивную нормальную функцию такого типа.

Правила построения по таблице истинности

Дизъюнктивная форма

Если функция равна 1, то для всех наборов переменных, при которых это происходит, записывается произведение. Однако переменные, которые имеют значение 0, берутся с отрицанием.

Конъюнктивная форма

Когда функция равна 0, то для всех наборов переменных, при которых это происходит, записывается сумма. Однако переменные, которые имеют значение 1, берутся с отрицанием.

Алгоритм приведения к СДНФ и СКНФ

Рассмотрим логическую функцию в виде таблицы истинности.

Алгоритм построения СДНФ по таблице истинности выглядит следующим образом:

1. Отметить наборы переменных, значение функции F на которых равно 1.
2. Записать для всех отмеченных наборов конъюнкцию всех переменных так: если значение некоторой переменной в этом наборе равняется 1, в конъюнкцию включается сама переменная. В случае противного результата, в конъюнкцию включается ее отрицание.
3. Связать полученные конъюнкции операциями дизъюнкции.

Построим совершенную ДНФ:

И как результат получим следующую СДНФ:

(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))

Алгоритм построения СКНФ по таблице истинности выглядит следующим образом:

1. Отметить в таблице истинности наборы переменных, значение функции F на которых равно 0.
2. Записать для всех отмеченных наборов дизъюнкцию всех переменных — в том случае, когда значение некоторой переменной в этом наборе равняется 0, в дизъюнкцию включается сама переменная, если происходит наоборот, то в дизъюнкцию включается ее отрицание.
3. Связать полученные дизъюнкции операциями конъюнкции.

Построим совершенную КНФ:

И как результат получим следующую СКНФ:

(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 .)

Доказать эквивалентность формул можно двумя способами.

1. Первый заключается в построении и сравнении таблиц истинности обеих функций. В этом случае результат будет истинным только в том случае, когда оба высказывания либо ложны, либо истинны.
2. Второй вариант — метод эквивалентных преобразований. Суть этого метода —  построение цепи эквивалентных формул на основе ранее доказанных эквивалентностей. 

Далее следуют примеры с некоторыми эквивалентными преобразованием в булевой алгебре и новыми эквивалентностями, которые возможно получить с их помощью. 

Поглощение

(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. конъюнктивная нормальная форма (КНФ) — конъюнкция нескольких дизъюнкций, например, $left(Avee overline{B}vee Cright)wedge left(Avee Cright)$;

2. дизъюнктивная нормальная форма (ДНФ) — дизъюнкция нескольких конъюнкций, например, $left(Awedge overline{B}wedge Cright)vee left(Bwedge Cright)$.

СКНФ

Совершенная конъюнктивная нормальная форма (СКНФ) — это КНФ, удовлетворяющая трем условиям:

• не содержит одинаковых элементарных дизъюнкций;

• ни одна из дизъюнкций не содержит одинаковых переменных;

• каждая элементарная дизъюнкция содержит каждую переменную из входящих в данную КНФ.

Любая булева формула, которая не является тождественно истинной, может быть представлена в СКНФ.

Правила построения СКНФ по таблице истинности

Для каждого набора переменных, при котором функция равна 0, записывается сумма, причем переменные, которые имеют значение 1, берутся с отрицанием.

СДНФ

Совершенная дизъюнктивная нормальная форма (СДНФ) — это ДНФ, удовлетворяющая трем условиям:

• не содержит одинаковых элементарных конъюнкций;

• ни одна из конъюнкций не содержит одинаковых переменных;

• каждая элементарная конъюнкция содержит каждую переменную из входящих в данную ДНФ, к тому же в одинаковом порядке.

Любая булева формула, которая не является тождественно ложной, может быть представлена в СДНФ, к тому же единственным образом.

Правила построения СДНФ по таблице истинности

Для каждого набора переменных, при котором функция равна 1, записывается произведение, причем переменные, которые имеют значение 0 берут с отрицанием.

Примеры нахождения СКНФ и СДНФ

«Построение СКНФ и СДНФ по таблице истинности» 👇

Для любой логической формулы можно построить бесконечное количество равносильных ей формул. Для этого потребуется произвести некоторое количество тождественных преобразований. Одной из главных задач в алгебре логики является нахождение канонических форм формул. Проще говоря таких, которые построены по одному канону (правилу).

Форма представления какой-либо логической функции будет считаться нормальной, если она выражена через конъюнкцию, дизъюнкцию, а также отрицание переменных. Среди всех нормальных форм можно выделить совершенно нормальные. Это тот случай, когда функция может быть записана только одним единственным способом.

Классы СКНФ и СДНФ

В при решении задач в алгебре логики особая роль отводится классам конъюнктивных и дизъюнктивных совершенно нормальных форм. Они основаны на стандартных понятиях элементарной конъюнкции и дизъюнкции.

СКНФ

Форма любой логической формулы нормального типа не может содержать знаки эквивалентности, импликации, а также отрицания неэлементарных формул. Она может существовать только в двух видах:

• КНФ – конъюнктивная нормальная форма, представляющая собой конъюнкцию нескольких дизъюнкций. К примеру, [(A vee bar{B} vee C) wedge(A vee C)];
• ДНФ – дизъюнктивная нормальная форма, которая является дизъюнкцией нескольких конъюнкций. К примеру, [(A wedge bar{B} wedge C) vee(A wedge C)].

Правила построения СКНФ

В алгебре логики для любого набора переменных, при котором конечное значение функции становится нулевым, можно записать сумму. При этом переменные, имеющие числовые значение больше единицы, должны браться с отрицательным знаком.

Построение должно осуществляться по следующему алгоритму:

1. В таблице нужно отметить такие наборы переменных, при которых [f=1].
2. Для каждого выбранного набора переменных записываем КНФ, при этом если значение какой-либо из них равно 1, то она включается в неизменном виде, иначе – ее отрицание.
3. На последнем этапе все полученные конъюнкции следует связать операциями дизъюнкции.

СНДФ

Любую булеву формулу в алгебре логики, не являющуюся тождественно ложной, можно представить в виде СНДФ, но только в одном единственном виде.

Правила построения СДНФ

Если существует определённый набор переменных, при котором значение функции равно единице, то можно записать произведения, учитывая, что переменные, значение которых больше нуля, нужно брать с отрицанием.

Алгоритм построения будет следующим:

1. В таблице отмечаются все те наборы переменных, при которых [f=0]
2. Для каждого отмеченного набора всех переменных записывается ДНФ, при этом если значение какой-либо из них равно нулю, то включается сама переменная, в любом другом случае ее нужно инвертировать.
3. В конце все полученные дизъюнкции связываются друг с другом операциями конъюнкции.

Примеры нахождения СКНФ и СДНФ

Рассмотрим несколько примеров нахождения СКНФ и СДНФ с помощью данных таблицы истинности.

ДНФ, КНФ, СДНФ, СКНФ, полином Жегалкина

На этой странице вы найдете готовые примеры задач, связанных с упрощением и преобразованием булевых функций к нормальным формам (ДНФ, КНФ), совершенным нормальным формам (СДНФ, СКНФ) и к каноническому многочлену Жегалкина.

Самый простой метод построения совершенной дизъюнктивной и конъюнктивной нормальных форм — с помощью таблиц истинности. Для перехода к ДНФ и КНФ используют методы эквивалентных преобразований, правила де Моргана, свойства поглощения, правило Блейка и т.п.

Полином Жегалкина может быть построен как с помощью последовательных преобразований, так и по таблице истинности (метод неопределенных коэффициентов).

Все эти примеры разобраны ниже. Типовые задачи снабжены подробным решением, формулами, пояснениями. Используйте их, чтобы научиться решать подобные задачи или закажите решение своей работы нам.

Другие примеры решений о булевых функциях:

Задачи и решения о представлении булевых функций

Нормальные формы (КНФ, СКНФ, ДНФ и СДНФ): примеры решений

Задача 1. Привести к КНФ и СКНФ.

$$((((Ato B)to bar A) to bar B) to bar C).$$

Задача 2. С помощью эквивалентных преобразований построить д.н.ф. функции:

$$f(x)=(overline{x_1}x_2 oplus x_3) cdot (x_1 x_3 to x_2) $$

Задача 3. Используя СКНФ, найдите наиболее простую формулу алгебры высказываний от четырех переменных, принимающую значение 0 на следующих наборах значений переменных, и только на них:

$$F(1,1,1,0)=F(1,1,0,1)=F(1,0,1,1)=F(0,1,1,1)=F(1,0,0,1)=0.$$

Задача 4. Привести данные выражения к ДНФ, пользуясь правилами де Моргана. Если возможно, сократить ДНФ, используя свойство поглощения и правило Блейка.

Многочлен Жегалкина: примеры решений

Задача 5. Представив функцию формулой над множеством связок ${&, -}$, преобразовать затем полученную формулу в полином Жегалкина функции $f(x)$ (используя эквивалентности):

$$f(x) = (x_1 vee x_2) cdot (x_2 | x_3)$$

Задача 6. Задана булева функция:
$$ f(x_1, x_2, x_3) = overline {x_2} vee ((x_1 wedge overline {x_3} ) | overline{(x_2 | overline {x_3})}$$
А) Построить таблицу истинности, найти двоичную форму булевой функции и привести ее к СДНФ и СКНФ.
Б) Найти многочлен Жегалкина.

Задача 7. Для заданной логической функции перейти к полиному Жегалкина.

$$ F=(y vee overline{xcdot z})cdot (overline{ycdot zdownarrow x}) $$

Решение задач на заказ

Выполняем для студентов очников и заочников решение заданий, контрольных и практических работ по любым разделам булевой алгебры, в том числе задачи по построению СДНФ, СКНФ, полинома Жегалкина на заказ. Также оказываем помощь в сдаче тестов. Подробное оформление, таблицы, графики, пояснение, использование специальных программ при необходимости. Стоимость примера от 100 рублей, оформление производится в Word, срок от 2 дней.