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

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

Практически 100%-ая копия полюбившегося многим инстаграм, идеально подойдет для портфолио, презентации работ своим клиентам или как отклик на понравившуюся вакансию. Молодой ресурс, но администраторы оперативно реагируют на предложения и вопросы.

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

Имеем следующую логическую функцию.

$f = xy\vee \bar < y >\bar < z >$. Преобразовать функцию так, чтобы она содержала две операции.

Вспомним таблицу истинности $\oplus$ и $\wedge$:

$x$	$y$	$x\oplus y$	$xy$
$0$	$0$	$0$	$0$
$0$	$1$	$1$	$0$
$1$	$0$	$1$	$0$
$1$	$1$	$0$	$1$

Составим таблицу истинности:

$x$	$y$	$z$	$\bar < y >$	$\bar < z >$	$xy$	$\bar < y >\bar < z >$	$f$
$0$	$0$	$0$	$1$	$1$	$0$	$1$	$1$
$0$	$0$	$1$	$1$	$0$	$0$	$0$	$0$
$0$	$1$	$0$	$0$	$1$	$0$	$0$	$0$
$0$	$1$	$1$	$0$	$0$	$0$	$0$	$0$
$1$	$0$	$0$	$1$	$1$	$0$	$1$	$1$
$1$	$0$	$1$	$1$	$0$	$0$	$0$	$0$
$1$	$1$	$0$	$0$	$1$	$1$	$0$	$1$
$1$	$1$	$1$	$0$	$0$	$1$	$0$	$1$

Запишем общий вид полинома Жегалкина $f = xy\vee \bar < y >\bar < z >= \overset < 0 > < a_ < 123 >> xyz\oplus \overset < 1 > < a_ < 12 >> xy\oplus \overset < 0 > < a_ < 13 >> xz\oplus \overset < 1 > < a_ < 23 >> yz\oplus \overset < 0 > < a_ < 1 >> x\oplus \overset < 1 > < a_ < 2 >> y\oplus \overset < 1 > < a_ < 3 >> z\oplus \overset < 1 > < a_ < 0 >> = xy\oplus yz\oplus y\oplus z\oplus 1 $

$f(0,0,1) = \overset < 1 > < a_ < 3 >> \oplus \overset < 1 > < a_ < 0 >> = 0$

$f(0,1,0) = \overset < 1 > < a_ < 2 >> \oplus \overset < 1 > < a_ < 0 >> = 0$

$f(0,1,1) = \overset < 1 > < a_ < 23 >> \oplus \overset < 1 > < a_ < 2 >> \oplus \overset < 1 > < a_ < 3 >> \oplus \overset < 1 > < a_ < 0 >> = 0$

$f(1,0,0) = \overset < 0 > < a_ < 1 >> \oplus \overset < 1 > < a_ < 0 >> = 1$

$f(1,0,1) = \overset < 0 > < a_ < 13 >> \oplus \overset < 0 > < a_ < 1 >> \oplus \overset < 1 > < a_ < 3 >> \oplus \overset < 1 > < a_ < 0 >> = 0$

$f(1,1,0) = \overset < 1 > < a_ < 12 >> \oplus \overset < 0 > < a_ < 1 >> \oplus \overset < 1 > < a_ < 2 >> \oplus \overset < 1 > < a_ < 0 >> = 1$

$f(1,1,1) = \overset < 0 > < a_ < 123 >> \oplus \overset < 1 > < a_ < 12 >> \oplus \overset < 0 > < a_ < 13 >> \oplus \overset < 1 > < a_ < 23 >> \oplus \overset < 0 > < a_ < 1 >> \oplus \overset < 1 > < a_ < 2 >> \oplus \overset < 1 > < a_ < 3 >> \oplus \overset < 1 > < a_ < 0 >> = 1$

Далее:

Вычисление поверхностного интеграла первого рода

Критерий полноты

Вычисление площадей плоских областей

Класс $S$. Теорема о замкнyтости класса $S$

Механические приложения тройного интеграла

Свойства тройного интеграла

Гармонические поля

Линейный интеграл и циркуляция векторного поля

Соленоидальное векторное поле

Вычисление площади поверхности

Теорема о полныx системаx в Pk

СДНФ. Теорема о представлении в виде СДНФ. Построение СДНФ по таблице

Свойства криволинейного интеграла второго рода

Скалярное поле, производная по направлению, градиент

Огравление $\Rightarrow $

04 сентября 2016, 20:21 проектирование км, кмд, кж Алгебра логики [Г.И. Просветов, Е.А. Фоминых, Ф.Г. Кораблёв] 0 11346 0

• Полином Жегалкина. Теорема о представлении в виде полинома Жегалкина
• Замыкание. Свойства замыкания. Теорема о сведении к заведомо полной системе

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

Множество булевых функций, заданный в базисе Жегалкина S4= называется алгеброй Жегалкина.

1. коммутативность

2. ассоциативность

3. дистрибутивность

4. свойства констант

5. Утверждение. Через операции алгебры Жегалкина можно выразить все другие булевы функции:

Определение. Полиномом Жегалкина (полиномом по модулю 2) от n переменных X₁,X₂ … X_n называется выражение вида:

где постоянные C_k могут принимать значения 0 ли 1.

Если полином Жегалкина не содержит произведений отдельных переменных, то он называется линейным (линейная функция).

Например, f=X⊕YZ⊕XYZ и f1=1⊕X⊕Y⊕Z — полиномы, причем вторая является линейной функцией.

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

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

1. Метод неопределенных коэффициентов. Пусть P(X₁,X₂ … X_n) — искомый полином Жегалкина, реализующий заданную функцию f(X₁,X₂ … X_n). Запишем его в виде

Найдем коэффициенты C_k. Для этого последовательно придадим переменным X₁,X₂ … X_n значения из каждой строки таблицы истинности. В итоге получим систему из 2 n уравнений с 2 n неизвестными, имеющую единственное решение. Решив ее, находим коэффициенты полинома P(X₁,X₂ … X_n).

2. Метод, основанный на преобразовании формул над множеством связок . Строят некоторую формулу Ф над множеством связок , реализующую данную функцию f(X₁,X₂ … X_n). Затем заменяют всюду подформулы вида ¬A на A⊕1, раскрывают скобки, пользуясь дистрибутивным законом (см. свойство 3), а затем применяют свойства 4 и 5.

Пример. Построить полином Жегалкина функции f(X,Y)=X→Y

Решение.

1. (метод неопределенных коэффициентов). Запишем искомый полином в виде:

Пользуясь таблицей истинности

X	0	0	1	1
Y	0	1	0	1
X→Y	1	1	0	1

2. (Метод преобразования формул.). Имеем:

Заметим, что преимущество алгебры Жегалкина (по сравнению с другими алгебрами) состоит в арифметизации логики, что позволяет выполнять преобразования булевых функций довольно просто. Ее недостатком по сравнению с булевой алгеброй является громоздкость формул.

• Определение булевой функции
• Элементарные булевы функции
• Задание булевых функций посредством элементарных
• Существенные и несущественные переменные
• Эквивалентные функции
• Основные эквивалентности
• Функциональная полнота
• Нормальные формы
• Совершенные нормальные формы
• Минимизация ДНФ методом Квайна
• Карты Карно
• Полином Жегалкина
• Высказывания
• Предикаты
• Кванторы
• Определение формальной теории
• Исчисление высказываний
• Теорема о дедукции. Полнота ИВ
• Автоматическое доказательство теорем
• Метод резолюций в ИВ
• Определение алгоритма
• Машина Тьюринга
• Рекурсивные функции
• Алгоритмически неразрешимые задачи
• Алгоритмы и их сложности

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

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

[math]P = a_ <000\ldots000>\oplus a_ <100\ldots0>x_1 \oplus a_ <010\ldots0>x_2 \oplus \ldots \oplus a_ <00\ldots01>x_n \oplus a_ <110\ldots0>x_1 x_2 \oplus \ldots \oplus a_ <00\ldots011>x_ x_n \oplus \ldots \oplus a_ <11\ldots1>x_1 x_2 \ldots x_n [/math]

Полнота

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

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

Исходя из этого, система функций [math]\bigl\langle \wedge, \oplus, 1 \bigr\rangle[/math] является полной:

[math]x_0[/math]	[math]x_1[/math]	[math]\ldots[/math]	[math]x_n[/math]	[math]1[/math]	[math]\land[/math]	[math]\oplus[/math]
[math]0[/math]	[math]0[/math]	[math]\ldots[/math]	[math]0[/math]	[math]1[/math]	[math]0[/math]	[math]0[/math]
[math]1[/math]	[math]0[/math]	[math]\ldots[/math]	[math]0[/math]	[math]1[/math]	[math]0[/math]	[math]1[/math]
[math]\vdots[/math]	[math]\vdots[/math]	[math]\vdots[/math]	[math]\vdots[/math]	[math]\vdots[/math]	[math]\vdots[/math]	[math]\vdots[/math]
[math]1[/math]	[math]1[/math]	[math]\ldots[/math]	[math]1[/math]	[math]1[/math]	[math]1[/math]	[math]0[/math]
Сохраняет 0				[math]0[/math]	[math]1[/math]	[math]1[/math]
Сохраняет 1				[math]1[/math]	[math]1[/math]	[math]0[/math]
Самодвойственная				[math]0[/math]	[math]0[/math]	[math]0[/math]
Монотонная				[math]1[/math]	[math]1[/math]	[math]0[/math]
Линейная				[math]1[/math]	[math]0[/math]	[math]1[/math]

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

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

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

Заметим, что различных булевых функций от [math]n[/math] переменных [math]2^[/math] штук. При этом конъюнкций вида [math]x_ \ldots x_[/math] существует ровно [math]2^n[/math] , так как из [math]n[/math] возможных сомножителей каждый или входит в конъюнкцию, или нет. В полиноме у каждой такой конъюнкции стоит [math]0[/math] или [math]1[/math] , то есть существует [math]2^[/math] различных полиномов Жегалкина от [math]n[/math] переменных.

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

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

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

Пусть для функции [math]f(x_1,x_2,\ldots,x_n)[/math] задана таблица истинности. Запишем сначала данную функцию в виде полинома Жегалкина с неопределёнными коэффициентами. Затем по очереди подставляем всевозможные наборы в порядке увеличения количества единиц и находим коэффициенты с учётом того, что [math] a \oplus 1 = \bar[/math] , а [math] a \oplus 0 = a[/math] . За каждую подстановку находим только один коэффициент.

Пример: Дана функция [math]f(x_1,x_2,x_3,x_4)[/math] и её таблица истинности:

[math]x_1[/math]	[math]x_2[/math]	[math]x_3[/math]	[math]x_4[/math]	[math]f(x_1,x_2,x_3,x_4)[/math]
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

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

[math]f(x_1,x_2,x_3,x_4) = a_ \oplus a_ x_1 \oplus a_ x_2 \oplus a_ x_3 \oplus a_ x_4 \oplus a_ x_1 x_2 \oplus a_ x_1 x_3 \oplus a_ x_1 x_4 \oplus a_ x_2 x_3 \oplus a_ x_2 x_4 \oplus a_ x_3 x_4 \oplus a_ x_1 x_2 x_3 \oplus a_ x_1 x_2 x_4 \oplus a_ x_1 x_3 x_4 \oplus a_ x_2 x_3 x_4 \oplus a_ x_1 x_2 x_3 x_4[/math]

Так как [math]f(0,0,0,0) = 0[/math] , то [math]a_ = 0[/math] . Далее подставляем все остальные наборы в порядке возрастания числа единиц, подставляя вновь полученные значения в следующие формулы:

[math]f(1,0,0,0) = a_ \oplus a_ = 1,[/math] следовательно [math]a_ = 1[/math]

[math]f(0,1,0,0) = a_ \oplus a_ = 0,[/math] следовательно [math]a_ = 0[/math]

[math]f(0,0,1,0) = a_ \oplus a_ = 0,[/math] следовательно [math] a_ = 0[/math]

[math]f(0,0,0,1) = a_ \oplus a_ = 0,[/math] следовательно [math] a_ = 0[/math]

[math]f(1,1,0,0) = a_ \oplus a_ \oplus a_ \oplus a_ = 1,[/math] следовательно [math] a_ = 0[/math]

[math]f(1,0,1,0) = a_ \oplus a_ \oplus a_ \oplus a_ = 0, [/math] следовательно [math] a_ = 1[/math]

[math]f(1,0,0,1) = a_ \oplus a_ \oplus a_ \oplus a_ = 0, [/math] следовательно [math] a_ = 1[/math]

[math]f(0,1,1,0) = a_ \oplus a_ \oplus a_ \oplus a_ = 1, [/math] следовательно [math] a_ = 1[/math]

[math]f(0,1,0,1) = a_ \oplus a_ \oplus a_ \oplus a_ = 0, [/math] следовательно [math] a_ = 0[/math]

[math]f(0,0,1,1) = a_ \oplus a_ \oplus a_ \oplus a_ = 0, [/math] следовательно [math] a_ = 0[/math]

[math]f(1,1,1,0) = a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ = 1, [/math] следовательно [math] a_ = 0[/math]

[math]f(1,1,0,1) = a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ = 0, [/math] следовательно [math] a_ = 0[/math]

[math]f(1,0,1,1) = a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ = 1, [/math] следовательно [math] a_ = 0[/math]

[math]f(0,1,1,1) = a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ = 0, [/math] следовательно [math] a_ = 1[/math]

[math]f(1,1,1,1) = a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ \oplus a_ = 0, [/math] следовательно [math] a_ = 1[/math]

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

[math]f(x_1,x_2,x_3,x_4) = x_1 \oplus x_1 x_3 \oplus x_1 x_4 \oplus x_2 x_3 \oplus x_2 x_3 x_4 \oplus x_1 x_2 x_3 x_4[/math]

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

Этот способ основан на том, что [math] X \oplus 1 = \bar [/math] . Если функция задана в виде ДНФ, то можно сначала убрать дизъюнкцию, используя правило де Моргана, а все отрицания заменить прибавлением единицы по модулю два, после чего раскрыть скобки по обычным правилам, при этом учитывая, что четное число одинаковых слагаемых равно нулю (так как [math] X \oplus X = 0 [/math] ), а нечетное число одинаковых слагаемых равно одному такому слагаемому. Либо же можно заменить дизъюнкцию по следующему правилу: [math] A \lor B = AB \oplus A \oplus B [/math] [math] (1) [/math] .

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

Пример: Дана функция в ДНФ [math] f(x_1,x_2,x_3,x_4) = (x_1 \land x_2 \land \neg x_3 \land x_4) \lor (\neg x_1 \land \neg x_4) \lor (x_1 \land x_2) \lor x_2 [/math] , построим полином Жегалкина.

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

[math]f(x_1,x_2,x_3,x_4) = x_1 x_2 \neg x_3 x_4 + \neg x_1 \neg x_4 + x_1 x_2 + x_2[/math] ;

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

[math]f(x_1,x_2,x_3,x_4) = (x_1 x_2 \neg x_3 x_4 \oplus \neg x_1 \neg x_4 \oplus x_1 x_2 \neg x_3 x_4 \neg x_1 \neg x_4) + (x_1 x_2 \oplus x_2 \oplus \oplus x_1 x_2 x_2)[/math]

Воспользуемся свойствами конъюнкции [math]A \land A = A[/math] и [math]\neg A \land A = 0[/math] , а также тем, что [math]A \oplus A = 0[/math] , и упростим выражение:

[math]f(x_1,x_2,x_3,x_4) = (x_1 x_2 \neg x_3 x_4 \oplus \neg x_1 \neg x_4) + x_2[/math]

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

[math]f(x_1,x_2,x_3,x_4) = x_1 x_2 \neg x_3 x_4 \oplus \neg x_1 \neg x_4 \oplus x_2 \oplus (x_1 x_2 \neg x_3 x_4 \oplus \neg x_1 \neg x_4) x_2[/math]

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

[math]f(x_1,x_2,x_3,x_4) = x_1 x_2 \neg x_3 x_4 \oplus \neg x_1 \neg x_4 \oplus x_2 \oplus x_1 x_2 x_2 \neg x_3 x_4 \oplus \neg x_1 x_2 \neg x_4[/math]

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

[math]f(x_1,x_2,x_3,x_4) = \neg x_1 \neg x_4 \oplus x_2 \oplus \neg x_1 x_2 \neg x_4[/math]

Заменим отрицание на прибавление [math]1[/math] :

[math]f(x_1,x_2,x_3,x_4) = (x_1 \oplus 1) (x_4 \oplus 1) \oplus x_2 \oplus (x_1 \oplus 1) x_2 (x_4 \oplus 1)[/math]

[math]f(x_1,x_2,x_3,x_4) = x_1 x_4 \oplus x_1 \oplus x_4 \oplus 1 \oplus x_2 \oplus x_1 x_2 x_4 \oplus x_1 x_2 \oplus x_2 x_4 \oplus x_2[/math]

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

[math]f(x_1,x_2,x_3,x_4) = x_1 x_2 x_4 \oplus x_1 x_2 \oplus x_1 x_4 \oplus x_2 x_4 \oplus x_1 \oplus x_4 \oplus 1[/math]

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

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

1. Строится полная таблица истинности, в которой строки идут в порядке возрастания двоичных кодов от [math]000\ldots00[/math] до [math]111\ldots11[/math] .
2. Строится вспомогательная треугольная таблица, в которой первый столбец совпадает со столбцом значений функции в таблице истинности.
3. Ячейка в каждом последующем столбце получается путём сложения по модулю 2 двух ячеек предыдущего столбца — стоящей в той же строке и строкой ниже.
4. Столбцы вспомогательной таблицы нумеруются двоичными кодами в том же порядке, что и строки таблицы истинности.
5. Каждому двоичному коду ставится в соответствие один из членов полинома Жегалкина в зависимости от позиций кода, в которых стоят единицы. Например, ячейке [math]111[/math] соответствует член [math]ABC[/math] , ячейке [math]101[/math] — член [math]AC[/math] , ячейке [math]010[/math] — член [math]B[/math] , ячейке [math]000[/math] — член [math]1[/math] и т.д.
6. Если в верхней строке какого-либо столбца стоит единица, то соответствующий член присутствует в полиноме Жегалкина.

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

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

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

Таким образом, в первом столбце сверху записан коэффициент [math] a_0 = P(0,0,0) [/math] ,

во втором — [math] a_1 = P(0,0,0) \oplus P(0,0,1) [/math] ,

в третьем — [math] a_2 = P(0,0,0) \oplus P(0,0,1) \oplus P(0,0,1) \oplus P(0,1,0) = P(0,0,0) \oplus P(0,1,0) [/math] ,

[math] a_3 = P(0,0,0) \oplus P(0,0,1) \oplus P(0,0,1) \oplus P(0,0,1) \oplus P(0,1,0) \oplus P(0,1,0) \oplus P(0,1,0) \oplus P(0,1,1) = P(0,0,0) \oplus P(0,1,0) \oplus P(0,0,1) \oplus P(0,1,1), [/math]

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

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

Пусть задана булева функция [math]f: B^n \rightarrow B, \;\; B=\< 0; 1 \>[/math] . Любая булева функция представима в виде полинома Жегалкина, притом единственным образом.

Пусть [math] i = (i_1, i_2, \ldots i_n), \;\; i_k \in \[/math] , и введем обозначение [math] x ^ \sim \left\ x, \;\; i_k=1 \\ 1, \;\; i_k=0 \end\right. [/math]

Тогда полином Жегалкина можно записать как: [math] f(x) = \bigoplus\limits_i \alpha_i \cdot x_1^ \cdot x_2^ \cdot[/math] [math]\ldots[/math] [math]\cdot x_n^[/math] , где [math]\alpha_i \in \< 0; 1 \>[/math] .

Множество коэффициентов [math]\[/math] можно рассматривать как функцию [math]\alpha[/math] , заданной на множестве индексов [math] i = (i_1, i_2, \ldots i_n)[/math] , то есть [math]\alpha: i \mapsto \alpha_i[/math] .

Очевидно, функцию [math] f [/math] можно записать и следующим образом: [math] f(x) = \bigoplus \limits_i \alpha_i \cdot [x_1 , \; [/math] если [math] \;\; i_1] \cdot [x_2 , \; [/math] если [math] \;\; i_2] \cdot[/math] [math]\ldots[/math] [math]\cdot [x_n , \; [/math] если [math] \;\; i_n][/math] .

Тут запись [math][x_k , \; [/math] если [math] \; i_k][/math] означает, что элелемент [math] x_k [/math] присутствует в соответствующем члене полинома только если [math] i_k = 1 [/math] . Тогда если для какого-то [math]x[/math] , [math]i \succ x*[/math] ,то в слагаемом будет существовать хотя бы один множитель, равный нулю, и такое слагаемое на сумму не повлияет. Отсюда ясно, что [math] f(x) = \bigoplus \limits_ \alpha_i [/math] [math] (2) [/math] Найдем отображение [math] f \mapsto \alpha[/math] (То есть такое, которое по заданной функции вычисляет значения всех коэффициентов).

[math]*[/math] [math]i \succ x[/math] обозначает, что [math]x[/math] «меньше» [math]i[/math] как последовательность бит

Пусть задана функция [math] f [/math] . Тогда функцию [math] \alpha_x [/math] можно найти по формуле: [math]\alpha_x = \bigoplus \limits_ f(j)[/math] [math] (3) [/math] .

Докажем при помощи индукции по количеству единиц в векторе [math] x [/math] ( иначе говоря, по сумме [math]x_1+x_2+[/math] [math]\ldots[/math] [math]+x_n[/math] ) и для удобства обозначим это количество единиц(сумму) [math] wt(x) [/math] .

1) База: если [math] x = 0 [/math] , то, очевидно [math] f(0) = \alpha_0 [/math]

2) Пускай теорема справедлива для всех сумм [math]wt(x) \lt k[/math] . Покажем, что в таком случае она верна и для [math]wt(x) = k[/math] . По [math] (2) [/math] , а далее по предположению индукции видим: [math] f(x) = \bigoplus \limits_ \alpha_i = \left [ \bigoplus \limits_ \bigoplus \limits_ f(j) \right ] \oplus \alpha_x[/math] .

Рассмотрим сумму [math] \left [ \bigoplus \limits_ \bigoplus \limits_ f(j) \right ] [/math] . Каждый элемент [math] f(j) [/math] содержится в ней, только если [math] j \prec x [/math] , и для фиксированных [math] j[/math] и [math] x [/math] элемент [math] f(j)[/math] встречается ровно столько раз, сколько существует [math] i [/math] , таких, что [math] j \preceq i \prec x[/math] . Несложно увидеть, что таких [math] i [/math] существует ровно [math] 2^-1 [/math] , то есть нечетное количество раз. Тогда [math] \left [ \bigoplus \limits_ \bigoplus \limits_ f(j) \right ] = \bigoplus \limits_ f(j) [/math] . Но тогда [math] f(x) = \left [ \bigoplus \limits_ f(j) \right ] \oplus \alpha_x \Leftrightarrow f(x) \oplus \bigoplus \limits_ f(j) = \alpha_x \Leftrightarrow \alpha_x = \bigoplus \limits_ f(j)[/math] .

Отображение [math] f \rightarrow \alpha[/math] также называется преобразованием Мёбиуса.

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

См. также

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

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

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

Построение таблицы истинности. СДНФ. СКНФ. Полином Жегалкина.

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

Калькулятор таблицы истинности, СКНФ, СДНФ, полинома Жегалкина

введите функцию или её вектор

Скрыть клавиатуру
Показать настройки
Опускать знак конъюнкции
Таблица истинности
Полином Жегалкина
Классификация Поста
Минимизация, карта Карно
Фиктивные переменные
С решением

Построено таблиц, форм:

Как пользоваться калькулятором

1. Введите в поле логическую функцию (например, x1 ∨ x2) или её вектор (например, 10110101)
2. Укажите действия, которые необходимо выполнить с помощью переключателей
3. Укажите, требуется ли вывод решения переключателем «С решением»
4. Нажмите на кнопку «Построить»

Видеоинструкция к калькулятору

Используемые символы

В качестве переменных используются буквы латинского и русского алфавитов (большие и маленькие), а также цифры, написанные после буквы (индекс переменной). Таким образом, именами переменных будут: a , x , a1 , B , X , X1 , Y1 , A123 и так далее.

Для записи логических операций можно использовать как обычные символы клавиатуры ( * , + , ! , ^ , -> , = ), так и символы, устоявшиеся в литературе ( ∧ , ∨ , ¬ , ⊕ , → , ≡ ). Если на вашей клавиатуре отсутствует нужный символ операции, то используйте клавиатуру калькулятора (если она не видна, нажмите «Показать клавиатуру»), в которой доступны как все логические операции, так и набор наиболее часто используемых переменных.

Для смены порядка выполнения операций используются круглые скобки ().

Обозначения логических операций

• И (AND): & • ∧ *
• ИЛИ (OR): ∨ +
• НЕ (NOT): ¬ !
• Исключающее ИЛИ (XOR): ⊕ ^
• Импликация: -> → =>
• Эквивалентность: = ~ ≡
• Штрих Шеффера: ↑ |
• Стрелка Пирса: ↓

Что умеет калькулятор

• Строить таблицу истинности по функции
• Строить таблицу истинности по двоичному вектору
• Строить совершенную конъюнктивную нормальную форму (СКНФ)
• Строить совершенную дизъюнктивную нормальную форму (СДНФ)
• Строить полином Жегалкина (методами Паскаля, треугольника, неопределённых коэффициентов)
• Определять принадлежность функции к каждому из пяти классов Поста
• Строить карту Карно
• Минимизировать ДНФ и КНФ
• Искать фиктивные переменные

Что такое булева функция

Булева функция f(x₁, x₂, . x_n) — это любая функция от n переменных x₁, x₂, . x_n, в которой её аргументы принимают одно из двух значений: либо 0, либо 1, и сама функция принимает значения 0 или 1. То есть это правило, по которому произвольному набору нулей и единиц ставится в соответствие значение 0 или 1. Подробнее про булевы функции можно посмотреть на Википедии.

Что такое таблица истинности?

Таблица истинности — это таблица, описывающая логическую функцию, а именно отражающую все значения функции при всех возможных значениях её аргументов. Таблица состоит из n+1 столбцов и 2 n строк, где n — число используемых переменных. В первых n столбцах записываются всевозможные значения аргументов (переменных) функции, а в n+1-ом столбце записываются значения функции, которые она принимает на данном наборе аргументов.

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

Логические операции

Логическая операция — операция над высказываниями, позволяющая составлять новые высказывания путём соединения более простых. В качестве основных операций обычно называют конъюнкцию (∧ или &), дизъюнкцию (∨ или |), импликацию (→), отрицание (¬), эквивалентность (=), исключающее ИЛИ (⊕).

Таблица истинности логических операций

a	b	a ∧ b	a ∨ b	¬a	¬b	a → b	a = b	a ⊕ b
0	0	0	0	1	1	1	1	0
0	1	0	1	1	0	1	0	1
1	0	0	1	0	1	0	0	1
1	1	1	1	0	0	1	1	0

Как задать логическую функцию

Есть множество способов задать булеву функцию:

• таблица истинности
• характеристические множества
• вектор значений
• матрица Грея
• формулы

Рассмотрим некоторые из них:

Чтобы задать функцию через вектор значений необходимо записать вектор из 2 n нулей и единиц, где n — число аргументов, от которых зависит функция. Например, функцию двух аргументов можно задать так: 0001 (операция И), 0111 (операция ИЛИ).

Чтобы задать функцию в виде формулы, необходимо записать математическое выражение, состоящее из аргументов функции и логических операций. Например, можно задать такую функцию: a∧b ∨ b∧c ∨ a∧c

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

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

• Совершенная дизъюнктивная нормальная форма (СДНФ)
• Совершенная конъюнктивная нормальная форма (СКНФ)
• Алгебраическая нормальная форма (АНФ, полином Жегалкина)

Совершенная дизъюнктивная нормальная форма (ДНФ)

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

Например, ДНФ является функция ¬a bc ∨ ¬a ¬b c ∨ ac, но не является СДНФ, так как в последней конъюнкции отсутствует переменная b.

Совершенная конъюнктивная нормальная форма (КНФ)

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

Например, КНФ является функция (a ∨ b) ∧ (a ∨ b ∨ c), но не является СДНФ, так как в первой дизъюнкции отсутствует переменная с.

Алгебраическая нормальная форма (АНФ, полином Жегалкина)

Алгебраическая нормальная форма, полином Жегалкина — это форма представления логической функции в виде полинома с коэффициентами вида 0 и 1, в котором в качестве произведения используется операция конъюнкции, а в качестве сложения — исключающее ИЛИ.

Примеры полиномов Жегалкина: 1, a, a⊕b, ab⊕a⊕b⊕1

Алгоритм построения СДНФ для булевой функции

1. Построить таблицу истинности для функции
2. Найти все наборы аргументов, на которых функция принимает значение 1
3. Выписать простые конъюнкции для каждого из наборов по следующему правилу: если в наборе переменная принимает значение 0, то она входит в конъюнкцию с отрицанием, а иначе без отрицания
4. Объединить все простые конъюнкции с помощью дизъюнкции

Алгоритм построения СКНФ для булевой функции

1. Построить таблицу истинности для функции
2. Найти все наборы аргументов, на которых функция принимает значение 0
3. Выписать простые дизъюнкции для каждого из наборов по следующему правилу: если в наборе переменная принимает значение 1, то она входит в дизъюнкцию с отрицанием, а иначе без отрицания
4. Объединить все простые дизъюнкции с помощью конъюнкции

Алгоритм построения полинома Жегалкина булевой функции

Есть несколько методов построения полинома Жегалкина, в данной статье рассмотрим наиболее удобный и простой из всех.

1. Построить таблицу истинности для функции
2. Добавить новый столбец к таблице истинности и записать в 1, 3, 5. ячейки значения из тех же строк предыдущего столбца таблицы истинности, а к значениям в строках 2, 4, 6. прибавить по модулю два значения из соответственно 1, 3, 5. строк.
3. Добавить новый столбец к таблице истинности и переписать в новый столбец значения 1, 2, 5, 6, 9, 10. строк, а к 3, 4, 7, 8, 11, 12. строкам аналогично предыдущему пункту прибавить переписанные значения.
4. Повторить действия каждый раз увеличивая в два раза количество переносимых и складываемых элементов до тех пор, пока длина не станет равна числу строк таблицы.
5. Выписать булевы наборы, на которых значение последнего столбца равно единице
6. Записать вместо единиц в наборах имена переменных, соответствующие набору (для нулевого набора записать единицу) и объединить их с помощью операции исключающего ИЛИ.

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

Построим совершенные дизъюнктивную и дизъюнктивную нормальные формы, а также полином Жегалкина для функции трёх переменных F = ¬a b∨ ¬b c∨ca

1. Построим таблицу истинности для функции

a	b	c	¬a	¬a ∧b	¬b	¬b ∧c	¬a ∧b∨ ¬b ∧c	c∧a	¬a ∧b∨ ¬b ∧c∨c∧a
0	0	0	1	0	1	0	0	0	0
0	0	1	1	0	1	1	1	0	1
0	1	0	1	1	0	0	1	0	1
0	1	1	1	1	0	0	1	0	1
1	0	0	0	0	1	0	0	0	0
1	0	1	0	0	1	1	1	1	1
1	1	0	0	0	0	0	0	0	0
1	1	1	0	0	0	0	0	1	1

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

Найдём наборы, на которых функция принимает истинное значение: < 0, 0, 1 > < 0, 1, 0 > < 0, 1, 1 > < 1, 0, 1 >

В соответствие найденным наборам поставим элементарные конъюнкции по всем переменным, причём если переменная в наборе принимает значение 0, то она будет записана с отрицанием:

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

K₁ ∨ K₂ ∨ K₃ ∨ K₄ ∨ K₅ = ¬a ¬b c ∨ ¬a b ¬c ∨ ¬a bc ∨ a ¬b c ∨ abc

Построение совершенной конъюнктивной нормальной формы:

Найдём наборы, на которых функция принимает ложное значение: < 0, 0, 0 > < 1, 0, 0 >

В соответствие найденным наборам поставим элементарные дизъюнкции по всем переменным, причём если переменная в наборе принимает значение 1, то она будет записана с отрицанием:

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

D₁ ∧ D₂ ∧ D₃ = (a∨b∨c) ∧ ( ¬a ∨b∨c) ∧ ( ¬a ∨ ¬b ∨c)

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

Добавим новый столбец к таблице истинности и запишем в 1, 3, 5 и 7 строки значения из тех же строк предыдущего столбца таблицы истинности, а значения в строках 2, 4, 6 и 8 сложим по модулю два со значениями из соответственно 1, 3, 5 и 7 строк:

a	b	c	F	1
0	0	0	0	→	0
0	0	1	1	⊕ 0	1
0	1	0	1	→	1
0	1	1	1	⊕ 1	0
1	0	0	0	→	0
1	0	1	1	⊕ 0	1
1	1	0	0	→	0
1	1	1	1	⊕ 0	1

Добавим новый столбец к таблице истинности и запишем в 1 и 2, 5 и 6 строки значения из тех же строк предыдущего столбца таблицы истинности, а значения в строках 3 и 4, 7 и 8 сложим по модулю два со значениями из соответственно 1 и 2, 5 и 6 строк:

a	b	c	F	1	2
0	0	0	0	0	→	0
0	0	1	1	1	→	1
0	1	0	1	1	⊕ 0	1
0	1	1	1	0	⊕ 1	1
1	0	0	0	0	→	0
1	0	1	1	1	→	1
1	1	0	0	0	⊕ 0	0
1	1	1	1	1	⊕ 1	0

Добавим новый столбец к таблице истинности и запишем в 1 2, 3 и 4 строки значения из тех же строк предыдущего столбца таблицы истинности, а значения в строках 5, 6, 7 и 8 сложим по модулю два со значениями из соответственно 1, 2, 3 и 4 строк:

a	b	c	F	1	2	3
0	0	0	0	0	0	→	0
0	0	1	1	1	1	→	1
0	1	0	1	1	1	→	1
0	1	1	1	0	1	→	1
1	0	0	0	0	0	⊕ 0	0
1	0	1	1	1	1	⊕ 1	0
1	1	0	0	0	0	⊕ 1	1
1	1	1	1	1	0	⊕ 1	1

Окончательно получим такую таблицу:

a	b	c	F	1	2	3
0	0	0	0	0	0	0
0	0	1	1	1	1	1
0	1	0	1	1	1	1
0	1	1	1	0	1	1
1	0	0	0	0	0	0
1	0	1	1	1	1	0
1	1	0	0	0	0	1
1	1	1	1	1	0	1

Выпишем наборы, на которых получившийся вектор принимает единичное значение и запишем вместо единиц в наборах имена переменных, соответствующие набору (для нулевого набора следует записать единицу):

Объединяя полученные конъюнкции с помощью операции исключающего или, получим полином Жегалкина: c⊕b⊕bc⊕ab⊕abc

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

Copyright © 2017 — 2023 Programforyou — помощь с программированием | programforyou.ru