Как найти полином жегалкина по днф

Полином Жегалкина — многочлен над полем , то есть полином с коэффициентами вида 0 и 1, где в качестве произведения берётся конъюнкция, а в качестве сложения — исключающее или. Полином был предложен в 1927 году Иваном Жегалкиным в качестве удобного средства для представления функций булевой логики. В зарубежной литературе представление в виде полинома Жегалкина обычно называется алгебраической нормальной формой (АНФ).

Теорема Жегалкина — утверждение о существовании и единственности представления всякой булевой функции в виде полинома Жегалкина^[1].

Полином Жегалкина представляет собой сумму по модулю два попарно различных произведений неинвертированных переменных, где ни в одном произведении ни одна переменная не встречается больше одного раза, а также (если необходимо) константы 1^[1]. Формально полином Жегалкина можно представить в виде

или в более формализованном виде как

Примеры полиномов Жегалкина:

Предпосылки[править | править код]

По теореме Поста, чтобы система булевых функций была полной, надо, чтобы в ней существовали:

1. Хотя бы одна функция, не сохраняющая 0.
2. Хотя бы одна функция, не сохраняющая 1.
3. Хотя бы одна нелинейная функция.
4. Хотя бы одна немонотонная функция.
5. Хотя бы одна несамодвойственная функция.

Этому требованию отвечает, в частности, система функций (конъюнкция, сложение по модулю два, константа 1). На её основе и строятся полиномы Жегалкина.

Существование и единственность представления[править | править код]

По теореме Жегалкина каждая булева функция единственным образом представляется в виде полинома Жегалкина. Теорема доказывается следующим образом. Заметим, что различных булевых функций от n переменных штук. При этом конъюнкций вида существует ровно 2ⁿ, так как из n возможных сомножителей каждый или входит в конъюнкцию, или нет. В полиноме у каждой такой конъюнкции стоит 0 или 1, то есть существует различных полиномов Жегалкина от n переменных. Теперь достаточно лишь доказать, что различные полиномы реализуют различные функции. Предположим противное. Тогда приравняв два различных полинома и перенеся один из них в другую часть равенства, получим полином, тождественно равный нулю и имеющий ненулевые коэффициенты. Тогда рассмотрим слагаемое с единичным коэффициентом наименьшей длины, то есть с наименьшим числом переменных, входящих в него (любой один, если таких несколько). Подставив единицы на места этих переменных и нули на места остальных, получим, что на этом наборе только одно это слагаемое принимает единичное значение, то есть нулевая функция на одном из наборов принимает значение 1. Противоречие. Значит, каждая булева функция реализуется полиномом Жегалкина единственным образом.

Представление функции в виде полинома Жегалкина[править | править код]

С помощью эквивалентных преобразований ДНФ[править | править код]

По сравнению с ДНФ в полиноме Жегалкина отсутствуют операции ИЛИ и НЕ. Таким образом, полином Жегалкина можно получить из ДНФ, выразив операции ИЛИ и НЕ через операции сложение по модулю два, и константу 1. Для этого применяются следующие соотношения:

Ниже приведён пример преобразования ДНФ в полином Жегалкина:

При преобразованиях использованы соотношения

С помощью эквивалентных преобразований СДНФ[править | править код]

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

При преобразовании СДНФ в полином Жегалкина достаточно заменить все дизъюнкции на операции сложение по модулю два и избавиться от инверсий при помощи эквивалентного преобразования

С помощью карты Карно[править | править код]

Логическая функция трёх переменных , представленная в виде карты Карно, преобразуется в полином Жегалкина следующими шагами:

• Рассматриваем все ячейки карты Карно в порядке возрастания количества единиц в их кодах. Для функции трёх переменных последовательность ячеек будет 000—100 — 010—001 — 110—101 — 011—111. Каждой ячейке карты Карно сопоставляем член полинома Жегалкина в зависимости от позиций кода, в которых стоят единицы. Например, ячейке 111 соответствует член ABC, ячейке 101 — член AC, ячейке 010 — член B, ячейке 000 — член 1.
• Если в рассматриваемой ячейке находится 0, переходим к следующей ячейке.
• Если в рассматриваемой ячейке находится 1, добавляем в полином Жегалкина соответствующий член, инвертируем в карте Карно все ячейки, где этот член равен 1, и переходим к следующей ячейке. Например, если при рассмотрении ячейки 110 в ней оказывается единица, то в полином Жегалкина добавляется член AB и инвертируются все ячейки карты Карно, где A = 1 и B = 1. Если единице равна ячейка 000, то в полином Жегалкина добавляется член 1 и инвертируется вся карта Карно.
• Процесс преобразования можно считать законченным, когда после очередной инверсии все ячейки карты Карно становятся нулевыми.

Метод треугольника[править | править код]

Основной источник: ^[2], ^[3]

Метод треугольника (часто называемый методом треугольника Паскаля) позволяет преобразовать таблицу истинности в полином Жегалкина путём построения вспомогательной треугольной таблицы в соответствии со следующими правилами:

• Строится полная таблица истинности, в которой строки идут в порядке возрастания двоичных кодов от 000…00 до 111…11.
• Строится вспомогательная треугольная таблица, в которой первый столбец совпадает со столбцом значений функции в таблице истинности.
• Ячейка в каждом последующем столбце получается путём суммирования по модулю 2 двух ячеек предыдущего столбца — стоящей в той же строке и строкой ниже.
• Столбцы вспомогательной таблицы нумеруются двоичными кодами в том же порядке, что и строки таблицы истинности.
• Каждому двоичному коду ставится в соответствие один из членов полинома Жегалкина в зависимости от позиций кода, в которых стоят единицы. Например, ячейке 111 соответствует член ABC, ячейке 101 — член AC, ячейке 010 — член B, ячейке 000 — член 1 и т. д.
• Если в верхней строке какого-либо столбца стоит единица, то соответствующий член присутствует в полиноме Жегалкина.

Метод треугольника основан на теореме, предложенной В. П. Супруном, не связанной напрямую с треугольником Паскаля. В 1985 году метод двоичного треугольника было предложено использовать для преобразования вектора значений совершенной дизъюнктивной нормальной формы в вектор коэффициентов полинома Жегалкина для произвольной симметрической булевой функции. В 1987 году метод был расширен для произвольной булевой функции. Отметим, что метод треугольника позволяет строить полином Рида — Маллера^[en] с отрицательной поляризацией как для симметрических функций, так и для произвольных^{[источник не указан 1875 дней]}.

Метод БПФ[править | править код]

Наиболее экономным с точки зрения объёма вычислений и целесообразным для построения полинома Жегалкина вручную является метод быстрого преобразования Фурье (БПФ).

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

Каждую строку полученной таблицы разбиваем на блоки (чёрные линии на рисунке). В первой строке блок занимает одну клетку, во второй строке — две, в третьей — четыре, в четвёртой — восемь и т. д. Каждому блоку в некоторой строке, который мы будем называть «нижний блок», всегда соответствует ровно два блока в предыдущей строке. Будем называть их «левый верхний блок» и «правый верхний блок».

Построение начинается со второй строки. Содержимое левых верхних блоков без изменения переносится в соответствующие клетки нижнего блока (зелёные стрелки на рисунке). Затем над правым верхним и левым верхним блоками побитно производится операция «сложение по модулю два», и полученный результат переносится в соответствующие клетки правой части нижнего блока (красные стрелки на рисунке). Эта операция проводится со всеми строками сверху вниз и со всеми блоками в каждой строке. После окончания построения в нижней строке оказывается строка чисел, которая является коэффициентами полинома Жегалкина, записанными в той же последовательности, что и в описанном выше методе треугольника.

Метод суммирования[править | править код]

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

Предположим для примера, что нужно найти коэффициент при конъюнкции xz для функции трёх переменных f(x, y, z). В этой конъюнкции отсутствует переменная y. Найдём входные наборы, в которых переменная y принимает нулевое значение. Это наборы 0, 1, 4, 5 (000, 001, 100, 101). Тогда коэффициент при конъюнкции xz равен

Поскольку в свободном члене отсутствуют все переменные, то

Для члена, куда входят все переменные, в сумму входят все значения функции:

Представим графически коэффициенты полинома Жегалкина как суммы по модулю 2 значений функций в некоторых точках. Для этого построим квадратную таблицу, где каждый столбец представляет собой значение функции в одной из точек, а строка — коэффициент полинома Жегалкина. Точка на пересечении некоторого столбца и строки означает, что значение функции в данной точке входит в сумму для данного коэффициента полинома (см. рисунок). Назовём эту таблицу T_N, где N — число переменных функции.

Существует закономерность, которая позволяет получить таблицу для функции N переменных, имея таблицу для функции N − 1 переменных. Новая таблица T_N+1 компонуется как матрица 2 × 2 таблиц T_N, причём правый верхний блок матрицы очищается.

См. также[править | править код]

• Алгебра Жегалкина

Примечания[править | править код]

Литература[править | править код]

• Яблонский С. В. Введение в дискретную математику. — М.: Наука. — 1986
• Марченков С. С. Замкнутые классы булевых функций. — М.: Физматлит. — 2000
• Супрун В. П. Основы теории булевых функций. — М.: Ленанд / URSS. — 2017.

Полином Жегалкина (англ. Zhegalkin polynomial) — полином с коэффициентами вида и , где в качестве произведения берётся конъюнкция, а в качестве сложения исключающее или. Полином был предложен в 1927 году И. И. Жегалкиным в качестве средства для представления функций булевой логики. Полином Жегалкина имеет следующий вид:

Полнота

По теореме Поста, чтобы система булевых функций была полной, надо, чтобы в ней существовали

1. Хотя бы одна функция, не сохраняющая ;
2. Хотя бы одна функция, не сохраняющая ;
3. Хотя бы одна нелинейная функция;
4. Хотя бы одна немонотонная функция;
5. Хотя бы одна несамодвойственная функция.

Исходя из этого, система функций является полной:

Сохраняет 0
Сохраняет 1
Самодвойственная
Монотонная
Линейная

На основе этой системы и строятся полиномы Жегалкина.

Существование и единственность представления (теорема Жегалкина)

Теорема (Жегалкина):

Каждая булева функция единственным образом представляется в виде полинома Жегалкина.

Доказательство:

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

Построение полинома Жегалкина

Существует несколько способов построения полинома Жегалкина.

По таблице истинности

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

Пример:
Дана функция и её таблица истинности:

0	0	0	0	0
0	0	0	1	0
0	0	1	0	0
0	0	1	1	0
0	1	0	0	0
0	1	0	1	0
0	1	1	0	1
0	1	1	1	0
1	0	0	0	1
1	0	0	1	0
1	0	1	0	0
1	0	1	1	1
1	1	0	0	1
1	1	0	1	0
1	1	1	0	1
1	1	1	1	0

Построим для неё полином Жегалкина:

Так как , то .
Далее подставляем все остальные наборы в порядке возрастания числа единиц, подставляя вновь полученные значения в следующие формулы:

следовательно

следовательно

следовательно

следовательно

следовательно

следовательно

следовательно

следовательно

следовательно

следовательно

следовательно

следовательно

следовательно

следовательно

следовательно

Таким образом, полином Жегалкина выглядит так:

Преобразование дизъюнктивной нормальной формы

Этот способ основан на том, что . Если функция задана в виде ДНФ, то можно сначала убрать дизъюнкцию, используя правило де Моргана, а все отрицания заменить прибавлением единицы по модулю два, после чего раскрыть скобки по обычным правилам, при этом учитывая, что четное число одинаковых слагаемых равно нулю (так как ), а нечетное число одинаковых слагаемых равно одному такому слагаемому. Либо же можно заменить дизъюнкцию по следующему правилу:
  .

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

Пример:
Дана функция в ДНФ , построим полином Жегалкина.

Запишем функцию так:

;

Сгруппируем слагаемые и воспользуемся преобразованием (1):

Воспользуемся свойствами конъюнкции и , а также тем, что , и упростим выражение:

Ещё раз воспользуемся преобразованием (1):

Раскроем скобку по алгебраическим правилам:

Снова воспользуемся свойствами конъюнкции и исключающего ИЛИ:

Заменим отрицание на прибавление :

Раскроем скобки:

Выкинем парные слагаемые и получим окончательную формулу:

Метод треугольника

Метод треугольника позволяет преобразовать таблицу истинности в полином Жегалкина путём построения вспомогательной треугольной таблицы в соответствии со следующими правилами:

1. Строится полная таблица истинности, в которой строки идут в порядке возрастания двоичных кодов от до .
2. Строится вспомогательная треугольная таблица, в которой первый столбец совпадает со столбцом значений функции в таблице истинности.
3. Ячейка в каждом последующем столбце получается путём сложения по модулю 2 двух ячеек предыдущего столбца — стоящей в той же строке и строкой ниже.
4. Столбцы вспомогательной таблицы нумеруются двоичными кодами в том же порядке, что и строки таблицы истинности.
5. Каждому двоичному коду ставится в соответствие один из членов полинома Жегалкина в зависимости от позиций кода, в которых стоят единицы. Например, ячейке соответствует член , ячейке — член , ячейке — член , ячейке — член и т.д.
6. Если в верхней строке какого-либо столбца стоит единица, то соответствующий член присутствует в полиноме Жегалкина.

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

Пример преобразования таблицы истинности в полином Жегалкина для функции трёх переменных показан на рисунке.

Чтобы получить формулу, по которой рассчитывается какой-либо коэффициент, нужно из клетки, в которой он записан, пройтись всеми возможными путями влево, до столбца таблицы истинности, делая ходы влево и влево-вниз, записать значения в конечных ячейках и сложить их все между собой по модулю 2.

Таким образом, в первом столбце сверху записан коэффициент ,

во втором — ,

в третьем — ,

в четвёртом —

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

Преобразование Мёбиуса

Пусть задана булева функция .
Любая булева функция представима в виде полинома Жегалкина, притом единственным образом.

Пусть , и введем обозначение

Тогда полином Жегалкина можно записать как:
, где .

Множество коэффициентов можно рассматривать как функцию , заданной на множестве индексов , то есть .

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

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

обозначает, что “меньше” как последовательность бит

Теорема:

Пусть задана функция . Тогда функцию можно найти по формуле:     .

Доказательство:

Докажем при помощи индукции по количеству единиц в векторе ( иначе говоря, по сумме ) и для удобства обозначим это количество единиц(сумму) . 1) База: если , то, очевидно 2) Пускай теорема справедлива для всех сумм . Покажем, что в таком случае она верна и для . По , а далее по предположению индукции видим: . Рассмотрим сумму . Каждый элемент содержится в ней, только если , и для фиксированных и элемент встречается ровно столько раз, сколько существует , таких, что . Несложно увидеть, что таких существует ровно , то есть нечетное количество раз. Тогда . Но тогда . То есть при формула также выполняется, значит при любых выполняется .

Отображение также называется преобразованием Мёбиуса.

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

См. также

• Булевы функции
• Полные системы функций, теорема Поста
• ДНФ
• КНФ

Источники информации

• Cтатистика | Математика НГУ
• Википедия — Полином Жегалкина
• Е.Л Рабкин, Ю.Б. Фарфоровская, дискретная математика
• Логачёв О.А, Сальников А.А., Ященко В.В. Булевы фунции в теории кодирования и криптологии — МЦНМО, 2004. – 470с. — ISBN 5-94057-117-4.

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

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

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

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

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

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

• Булевы формулы
• Таблицы истинности
• Минимизация ДНФ булевых функций
• Полнота системы функций

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

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

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

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

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

$$f(x)=(overlinex_2 oplus x_3) cdot (x_1 x_3 to x_2) $$

Задача 3. Используя СКНФ, найдите наиболее простую формулу алгебры высказываний от четырех переменных, принимающую значение 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 vee ((x_1 wedge overline ) | overline)>$$ А) Построить таблицу истинности, найти двоичную форму булевой функции и привести ее к СДНФ и СКНФ.
Б) Найти многочлен Жегалкина.

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

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

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

Как построить полином жегалкина по таблице истинности

Полином Жегалкина — полином с коэффициентами вида 0 и 1, в котором конъюнкция используется как произведение, сумма по модулю 2 используется как сложение. Полином был предложен в 1927 году Иваном Жегалкиным в качестве удобного средства для представления функций булевой логики. В зарубежной литературе представление в виде полинома Жегалкина обычно называется алгебраической нормальной формой (АНФ).
Полином Жегалкина имеет вид:

где C0, C1, …, C1…n – коэффициенты при переменных 1, x1, x2,…xn, x1x2,…, x1…xn соответственно.
Теорема. Любая функция п переменных может быть представлена полиномом Жегалкина и это представление единственно.
Доказательство. Любая функция f(x1, x2, …, xn) имеет свою таблицу истинности. Запишем сначала данную функцию в виде полинома Жегалкина с неопределенными коэффициентами. Затем по очереди подставляем всевозможные наборы переменных и находим коэффициенты. Легко видеть, что за каждую подстановку находим только один коэффициент. Так как число наборов равно числу коэффициентов (и равно 2п), отсюда следует утверждение теоремы.
Доказательство этой теоремы показывает, как по таблице истинности построить полином Жегалкина.
Для булевых функций двух переменных полином Жегалкина имеет вид:

Определим булевы функции двух переменных через операции алгебры Жегалкина (т. е. через конъюнкцию и сумму по модулю 2).
Предварительно дадим решение простейших уравнений, вытекающих из определения суммы по модулю 2:
Если a ⊕ 1 = 1, то a = 0
Если a ⊕ 0 = 1, то a = 1
Если a ⊕ 1 = 0, то a = 1
Если a ⊕ 0 = 0, то a = 0.
Функция f0(x1,x2)= есть тождественный ноль.
Функция f1(x1,x2)= есть конъюнкция.
Для функции f2(x1,x2)= определим значения коэффициентов полинома Жегалкина:
f2(0,0) = C0=0
f2(0,1) = C0⊕ C2=0
f2(1,0) = C0⊕ C1=1
f2(1,1) = C0⊕ C1⊕ C2⊕ C12=0

Метод треугольника
Метод треугольника позволяет преобразовать таблицу истинности в полином Жегалкина путём построения вспомогательной треугольной таблицы в соответствии со следующими правилами:

• Строится полная таблица истинности, в которой строки идут в порядке возрастания двоичных кодов от 000. 00 до 111. 11.
• Строится вспомогательная треугольная таблица, в которой первый столбец совпадает со столбцом значений функции в таблице истинности.
• Ячейка в каждом последующем столбце получается путём сложения по модулю 2 двух ячеек предыдущего столбца — стоящей в той же строке и строкой ниже.
• Столбцы вспомогательной таблицы нумеруются двоичными кодами в том же порядке, что и строки таблицы истинности.
• Каждому двоичному коду ставится в соответствие один из членов полинома Жегалкина в зависимости от позиций кода, в которых стоят единицы. Например, ячейке 111 соответствует член ABC, ячейке 101 — член AC, ячейке 010 — член B, ячейке 000 — член 1 и т.д.
• Если в верхней строке какого-либо столбца стоит единица, то соответствующий член присутствует в полиноме Жегалкина.

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

Пример преобразования таблицы истинности в полином Жегалкина для функции трёх переменных P(A,B,C) показан на рисунке.

ЛЕКЦИЯ 9

Пополним список уже известных логических операций, а именно, познакомимся со штрихом Шеффера, стрелкой Пирса и операцией двоичного сложения. На последней остановимся более подробно.

Штрих Шеффера – это новое высказывание , обозначаемое х|y, ложное тогда и только тогда, когда оба высказывания х и у истинны. Приведем таблицу истинности:

Легко заметить, что штрих Шеффера – это отрицание конъюнкции или дизъюнкция отрицаний х и у: Следовательно, штрих Шеффера можно прочесть следующим образом: не х или не у.

Используя основные равносильности, можно эту операцию выразить и через другие, например:

Отрицание высказывания можно представить в виде :

Стрелка Пирса – это новое высказывание, обозначаемое х¯ у, истинное тогда и только тогда, когда оба высказывания ложны. Приведем таблицу истинности:

Стрелка Пирса – это отрицание дизъюнкции или конъюнкция отрицаний х и у:

Стрелку Пирса можно прочесть так: не х и не у.

Отрицание высказывания выражается через стрелку Пирса:

Пример: составить КНФ и ДНФ для формулы

Используя новые равносильности и основные равносильности , преобразуем формулу:

Полученная формула является одновременно ДНФ и КНФ.

Двоичное сложение – это новое высказывание, обозначаемое х+у, ложное тогда и только тогда. Когда оба высказывания имеют одинаковые логические значения. Приведем таблицу истинности:

Двоичное сложение – это отрицание эквиваленции:

Познакомимся с законами для двоичного сложения:

1. коммутативность: х+у º у+х;

2. ассоциативность: х+у+z º x+(y+z);

3. дистрибутивность: x(y+z) º xy +xz;

Рассмотрим использование данной операции в вопросе представления булевой функции единственным образом, наряду с совершенными формулами.

2. Полином Жегалкина.

Познакомимся с определением полинома:

Любую булеву функцию можно представить в виде двоичной суммы различных одночленов (конъюнкций), в которые все переменные входят не выше, чем в первой степени и константы 1 или 0, т.е. булева функция представима в виде:

Причем, такое представление единственное.

Эта сумма называется многочленом Жегалкина.

Существует два способа представления булевой функции в виде полинома: метод неопределенных коэффициентов и метод построения полином по формуле. Опишем каждый метод подробно.

Метод неопределенных коэффициентов.

Перепишем полином в виде :

где K_i – конъюнкции, число которых равно 2 n – 1, — вектор коэффициентов, где b_I Î.

Коэффициент b_I указывает на присутствие или отсутствие соответствующей конъюнкции в полиноме.

Алгоритм поиска вектора коэффициентов и составления полинома.

1. по таблице истинности составить систему уравнений ,где (a₁ , a₂ , …, a_n) — все наборы значений переменных таблицы истинности для данной булевой функции (вместо переменных в полином подставить их соответствующие значения, в левой части уравнения – соответствующее этому набору значение функции).

3. пользуясь таблицей истинности для двоичного сложения и конъюнкции, вычислить коэффициенты b_I ;

4. подставить в полином значения коэффициентов и составить полином.

Представление булевой функции в виде полинома называется разложением функции в многочлен или в полином.

Разложить функцию f(x, y, z) = (01101000).

Cоставляя уравнения, нулевые конъюнкции будем исключать:

Решая систему , получим вектор коэффициентов: (0,0,1,0,1,1,0,1), тогда функция раскладывается в полином:

P(x,y,z) = 0 + y +xy + xz +xyz.

Проверку можно выполнить, составив таблицу истинности для полинома.

Построение полинома по формуле.

Данный метод основан на применении равносильных преобразований данной булевой функции, представленной в виде формулы, к виду полинома.

Алгоритм построения полинома по формул:

1. заменить формулу равносильной, содержащей только операции конъюнкцию и отрицание;

2. снять отрицания, пользуясь равносильностью:

3. раскрыть скобки:

4. упростить, используя идемпотентность : х+х =0, равносильность х+0=х.

Задачи для самостоятельного решения.

1. Построить таблицу истинности для формулы Составить для данной формулы КНФ и ДНФ.

2. Методом неопределенных коэффициентов разложить функции в полиномы: а) f(x,y,z)= (01001110); б) f(x,y,z) = (11000101); в) f(x,y)= (0101); г) f(x,y)=(1011)

3. Методом неопределенных коэффициентов и путем равносильных преобразований построить полиномы для формул: а) х®у; б) (х|y)¯z; в) (x®y)(y¯z); г) ((x®y)v)|x.

1. Привести таблицу истинности для штриха Шеффера. Выразить штрих Шеффера через отрицание и конъюнкцию. Выразить отрицание через штрих Шеффера.

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 дней.