Полином Жегалкина
Полином Жегалкина (англ. 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]
Полнота
По теореме Поста, чтобы система булевых функций была полной, надо, чтобы в ней существовали
- Хотя бы одна функция, не сохраняющая [math]0[/math] ;
- Хотя бы одна функция, не сохраняющая [math]1[/math] ;
- Хотя бы одна нелинейная функция;
- Хотя бы одна немонотонная функция;
- Хотя бы одна несамодвойственная функция.
Исходя из этого, система функций [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]
Метод треугольника
Метод треугольника позволяет преобразовать таблицу истинности в полином Жегалкина путём построения вспомогательной треугольной таблицы в соответствии со следующими правилами:
- Строится полная таблица истинности, в которой строки идут в порядке возрастания двоичных кодов от [math]000\ldots00[/math] до [math]111\ldots11[/math] .
- Строится вспомогательная треугольная таблица, в которой первый столбец совпадает со столбцом значений функции в таблице истинности.
- Ячейка в каждом последующем столбце получается путём сложения по модулю 2 двух ячеек предыдущего столбца — стоящей в той же строке и строкой ниже.
- Столбцы вспомогательной таблицы нумеруются двоичными кодами в том же порядке, что и строки таблицы истинности.
- Каждому двоичному коду ставится в соответствие один из членов полинома Жегалкина в зависимости от позиций кода, в которых стоят единицы. Например, ячейке [math]111[/math] соответствует член [math]ABC[/math] , ячейке [math]101[/math] — член [math]AC[/math] , ячейке [math]010[/math] — член [math]B[/math] , ячейке [math]000[/math] — член [math]1[/math] и т.д.
- Если в верхней строке какого-либо столбца стоит единица, то соответствующий член присутствует в полиноме Жегалкина.
Фактически, этот метод является модификацией метода построения по таблице истинности, описанного выше. По сравнению с ним он удобнее тем, что расчёты занимают мало места и в них сложнее ошибиться, но метод треугольника требует бо́льшего количества операций.
Пример преобразования таблицы истинности в полином Жегалкина для функции трёх переменных [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_
Докажем при помощи индукции по количеству единиц в векторе [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_
Рассмотрим сумму [math] \left [ \bigoplus \limits_ \bigoplus \limits_
Отображение [math] f \rightarrow \alpha[/math] также называется преобразованием Мёбиуса.
Видно, что [math] (2) [/math] и [math] (3) [/math] — это одно и тоже преобразование. Значит, если применить преобразование Мёбиуса к функции, а затем вновь применить то же преобразование к получившейся функции, тогда вновь получим исходную функцию [math]f[/math] . То есть преобразование Мёбиуса обратно самому себе, иными словами, является инволюцией.
См. также
- Булевы функции
- Полные системы функций, теорема Поста
- ДНФ
- КНФ
Источники информации
- Cтатистика | Математика НГУ
- Википедия — Полином Жегалкина
- Е.Л Рабкин, Ю.Б. Фарфоровская, дискретная математика
- Логачёв О.А, Сальников А.А., Ященко В.В. Булевы фунции в теории кодирования и криптологии — МЦНМО, 2004. — 470с. — ISBN 5-94057-117-4.
Что нам стоит полином Жегалкина построить…
Думаю, каждый, кто изучал или изучает в университете дискретную математику, знаком с понятием многочлена Жегалкина.
Главная особенность этих многочленов состоит в том, что любую булеву функцию можно представить полиномом Жегалкина, причем единственным образом.
Чаще всего для построения полиномов Жегалкина студентам предлагаются два метода построения таких полиномов: метод неопределенных коэффициентов и метод эквивалентных преобразований.
Расчеты с использованием данных методов часто оказываются громоздкими. По невнимательности допустить ошибку не составляет труда.
Под катом приведен один удобный алгоритм, для построения полиномов Жегалкина, который студенты воспринимают «на ура», т.к. требует только выполнение «механических действий» без применения каких-либо умственных усилий. Краткое описание метода можно найти в Википедии, но на мой взгляд по нему не совсем понятно, как быстро проводить вычисления. Мне метод известен под названием «метод треугольника Паскаля».
Порядок проведения вычислений проще показать на примере. Далее я буду по шагам показывать, как должен выглядеть расчет на бумаге (или как его удобно проводить).
Метод треугольника Паскаля
Требуется построить полином Жегалкина для функции f. Для примера, в качестве функции f возьмем функцию голосования .
Шаг 1. Строим таблицу значений функции (строки в таблице идут в порядке возрастания двоичных кодов). Таблицу лучше разместить в левой части листа.
Шаг 2. Построение треугольника.
Для этого берем вектор значения функции и выписываем его напротив первой строки таблицы:
Далее заполняем треугольник, складывая попарно соседние значения по модулю 2, результат сложения выписываем ниже.
Продолжаем вычисления, пока в строке не останется лишь одна цифра.
Шаг 3. Построение полинома Жегалкина.
Нас интересует левая сторона треугольника (значения выделены жирным):
Числа на левой стороне (выделены жирным шрифтом) треугольника есть коэффициенты полинома при монотонных конъюнкциях, соответствующих наборам значений переменных.
Теперь выпишем для наглядности эти конъюнкции. Конъюнкции выписываем по двоичным наборам в левой части таблицы по следующему принципу: если напротив переменной xi стоит 1, то переменная входит в конъюнкцию; в противном случае переменная отсутствует в конъюнкции. Набору (0,0,0) соответствует константа 1.
Если принцип получения конъюнкций понятен, то столбец с ними можно (даже лучше) не выписывать, а сразу переходить к построению полинома.
Для построения полинома нужны только конъюнкции из строк с единицами на левой стороне треугольника.
Это и есть конъюнкции, входящие в состав полинома Жегалкина. Осталось лишь выписать сам полином:
Если переменных в функции не 3, а 4 или больше, то метод работает без изменений, только увеличатся размеры таблиц. Тем не менее, в отличие от метода неопределенных коэффициентов, расчеты можно без особых усилий выполнить на листе бумаги.
Литература
К сожалению, мне не удалось найти и посмотреть источник, указанный в Википедии:
В.П. Супрун Табличный метод полиномиального разложения булевых функций // Кибернетика. — 1987. — № 1. — С. 116-117.
ДНФ, КНФ, СДНФ, СКНФ, полином Жегалкина
На этой странице вы найдете готовые примеры задач, связанных с упрощением и преобразованием булевых функций к нормальным формам (ДНФ, КНФ), совершенным нормальным формам (СДНФ, СКНФ) и к каноническому многочлену Жегалкина.
Самый простой метод построения совершенной дизъюнктивной и конъюнктивной нормальных форм — с помощью таблиц истинности. Для перехода к ДНФ и КНФ используют методы эквивалентных преобразований, правила де Моргана, свойства поглощения, правило Блейка и т.п.
Полином Жегалкина может быть построен как с помощью последовательных преобразований, так и по таблице истинности (метод неопределенных коэффициентов).
Все эти примеры разобраны ниже. Типовые задачи снабжены подробным решением, формулами, пояснениями. Используйте их, чтобы научиться решать подобные задачи или закажите решение своей работы нам.
Другие примеры решений о булевых функциях:
- Булевы формулы
- Таблицы истинности
- Минимизация ДНФ булевых функций
- Полнота системы функций
Лучшее спасибо — порекомендовать эту страницу
Задачи и решения о представлении булевых функций
Нормальные формы (КНФ, СКНФ, ДНФ и СДНФ): примеры решений
Задача 1. Привести к КНФ и СКНФ.
$$((((A\to 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<(x_2 | \overline )>$$ А) Построить таблицу истинности, найти двоичную форму булевой функции и привести ее к СДНФ и СКНФ.
Б) Найти многочлен Жегалкина.
Задача 7. Для заданной логической функции перейти к полиному Жегалкина.
Решение задач на заказ
Выполняем для студентов очников и заочников решение заданий, контрольных и практических работ по любым разделам булевой алгебры, в том числе задачи по построению СДНФ, СКНФ, полинома Жегалкина на заказ. Также оказываем помощь в сдаче тестов. Подробное оформление, таблицы, графики, пояснение, использование специальных программ при необходимости. Стоимость примера от 100 рублей , оформление производится в Word, срок от 2 дней.
Полином Жегалкина. Пример.
Практически 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$
Далее:
Логические следствия
Соленоидальное векторное поле
Введение
Класс M. Теорема о замкнутости класса M
Решение задач с помощью алгебры высказываний
Вычисление двойного интеграла. Двукратный интеграл
Теорема Остроградского
Упрощение логических функций
Механические и физические приложения поверхностного интеграла первого рода
Вычисление криволинейного интеграла второго рода. Примеры.
Несобственные интегралы от неограниченной функции
Свойства тройного интеграла
Поток жидкости через поверхность
Поверхностный интеграл первого рода и его свойства
Вычисление криволинейного интеграла первого рода. Примеры
Огравление $\Rightarrow $
04 сентября 2016, 20:21 проектирование км, кмд, кж Алгебра логики [Г.И. Просветов, Е.А. Фоминых, Ф.Г. Кораблёв] 0 11463 0
- Полином Жегалкина. Теорема о представлении в виде полинома Жегалкина
- Замыкание. Свойства замыкания. Теорема о сведении к заведомо полной системе