Полином Жегалкина - Zhegalkin polynomial

Жегалкина (также Žegalkin , Gégalkine или Shegalkin ) полиномы являются представление функций в булевой алгебре . Представленные русским математиком Иваном Ивановичем Жегалкиным в 1927 году, они представляют собой кольцо многочленов над целыми числами по модулю 2 . Получающиеся вырождения модулярной арифметики приводят к тому, что многочлены Жегалкина проще обычных многочленов и не требуют ни коэффициентов, ни показателей. Коэффициенты избыточны, потому что 1 - единственный ненулевой коэффициент. Показатели избыточны, потому что в арифметике по модулю 2 x ² = x . Следовательно, такой многочлен, как 3 x ² y ⁵ z , конгруэнтен и, следовательно, может быть переписан как xyz .

Логический эквивалент

До 1927 года булева алгебра считалась исчислением логических значений с логическими операциями соединения , дизъюнкции , отрицания и т. Д. Жегалкин показал, что все булевы операции могут быть записаны как обычные числовые полиномы, представляющие ложные и истинные значения как 0 и 1, целые числа по модулю 2. Логическое соединение записывается как xy , а логическое исключающее - или как арифметическое сложение по модулю 2, (записывается здесь как x ⊕ y, чтобы избежать путаницы с обычным использованием + как синонима для включающего или ∨). Тогда логическое дополнение ¬ x равно x ⊕1. Поскольку ∧ и ¬ образуют основу булевой алгебры, все остальные логические операции являются композициями этих базовых операций, и поэтому многочлены обычной алгебры могут представлять все булевы операции, позволяя проводить логические рассуждения с использованием элементарной алгебры .

Например, логический порог 2 из 3 или медианная операция записывается как полином Жегалкина xy ⊕ yz ⊕ zx .

Формальные свойства

Формально моном Жегалкина - это произведение конечного набора различных переменных (следовательно, без квадратов ), включая пустое множество, произведение которого обозначено 1. Существует 2 ⁿ возможных одночленов Жегалкина от n переменных, поскольку каждый моном полностью определяется наличие или отсутствие каждой переменной. Жегалкина полином является суммой (исключающим или) из набора Жегалкина мономов, с пустым множеством , обозначенное присутствием 0. данных мономиальным или отсутствием в полиномиальном соответствует коэффициенту этого мономиальному в равном 1 или 0 соответственно. Мономы Жегалкина, будучи линейно независимыми , покрывают 2 ⁿ -мерное векторное пространство над полем Галуа GF (2) (примечание: не GF (2 ⁿ ), умножение которого совершенно иное). 2 ^{2 n} векторов этого пространства, то есть линейные комбинации этих одночленов как единичных векторов, составляют многочлены Жегалкина. Точное совпадение с числом булевых операций над n переменными, которые исчерпывают n- мерные операции над {0,1}, дает прямой счетный аргумент в пользу полноты полиномов Жегалкина как булевого базиса.

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

Метод расчета

Существуют различные известные методы, обычно используемые для вычисления полинома Жегалкина:

• Используя метод неопределенных коэффициентов
• Построив каноническую дизъюнктивную нормальную форму
• Используя таблицы
• Метод Паскаля
• Метод суммирования
• Использование карты Карно

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

Методом неопределенных коэффициентов формируется линейная система, состоящая из всех кортежей функции и их значений. Решение линейной системы дает коэффициенты многочлена Жегалкина.

Пример

Учитывая булеву функцию , выразите ее в виде полинома Жегалкина. Эта функция может быть выражена как вектор-столбец ${\ displaystyle f (A, B, C) = {\ bar {A}} {\ bar {B}} {\ bar {C}} + {\ bar {A}} B {\ bar {C}} + A {\ bar {B}} {\ bar {C}} + ABC}$

${\ Displaystyle {\ vec {f}} = {\ begin {pmatrix} 1 \\ 0 \\ 1 \\ 0 \\ 1 \\ 0 \\ 0 \\ 1 \ end {pmatrix}}}$ .

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

${\ displaystyle {\ vec {c}} = {\ begin {pmatrix} c_ {0} \ c_ {1} \ c_ {2} \ c_ {3} \ c_ {4} \ c_ {5 } \\ c_ {6} \\ c_ {7} \ end {pmatrix}}}$

логической матрицей 8x8, которая представляет возможные значения, которые могут принимать все возможные соединения A, B, C. Эти возможные значения приведены в следующей таблице истинности:

${\ Displaystyle {\ begin {array} {| c | c | c | c | c | c | c | c | c | c | c | c |} A & B & C & \; \; \; \; \; \; \ ; \; & 1 & C & B & БК & & AC & AB & АВС \\\ HLine 0 & 0 & 0 && 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 && 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 && 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 && 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 && 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 && 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 && 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 && 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \ конец {массив}}}$ .

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

${\ Displaystyle S_ {3} = {\ BEGIN {pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \ конец {pmatrix}}}$

где «S» здесь означает «Серпинского», как в треугольнике Серпинского , а индекс 3 дает экспонентам его размера: . ${\ displaystyle 2 ^ {3} \ times 2 ^ {3}}$

С помощью математической индукции и блочного умножения матриц можно доказать, что любая такая «матрица Серпинского» является своей собственной обратной. ${\ displaystyle S_ {n}}$

Тогда линейная система есть

${\ Displaystyle S_ {3} {\ vec {c}} = {\ vec {f}}}$

который может быть решен для : ${\ displaystyle {\ vec {c}}}$

${\ displaystyle {\ vec {c}} = S_ {3} ^ {- 1} {\ vec {f}} = S_ {3} {\ vec {f}} = {\ begin {pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \= \ 1 \ end {pmatrix}} = {\ begin {pmatrix} 1 \\ 1 \\ 1 \ oplus 1 \\ 1 \ oplus 1 \\ 1 \ oplus 1 \\ 1 \ oplus 1 \\ 1 \ oplus 1 \ oplus 1 \\ 1 \ oplus 1 \ oplus 1 \ oplus 1 \ end {pmatrix}} = {\ begin {pmatrix} 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 1 \\ 0 \ конец {pmatrix}}}$ ,

и полином Жегалкина, соответствующий is . ${\ displaystyle {\ vec {c}}}$${\ displaystyle 1 \ oplus C \ oplus AB}$

Использование канонической дизъюнктивной нормальной формы

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

Использование таблиц

Вычисление полинома Жегалкина для примерной функции P табличным методом

Позвольте быть выходными данными таблицы истинности для функции P от n переменных, так что индекс 's соответствует двоичной индексации minterms . Рекурсивно определить функцию ζ следующим образом: ${\ displaystyle c_ {0}, ..., c_ {2 ^ {n} -1}}$${\ displaystyle c_ {i}}$

${\ displaystyle \ zeta (c_ {i}): = c_ {i}}$

${\ displaystyle \ zeta (c_ {0}, ..., c_ {k}): = \ zeta (c_ {0}, ..., c_ {k-1}) \ oplus \ zeta (c_ {1} , ..., c_ {k})}$ .

Обратите внимание, что

${\ displaystyle \ zeta (c_ {0}, ..., c_ {m}) = \ bigoplus _ {k = 0} ^ {m} {m \ choose k} _ {2} c_ {k}}$

где - биномиальный коэффициент, приведенный по модулю 2. ${\ displaystyle {m \ choose k} _ {2}}$

Затем

${\ displaystyle g_ {i} = \ zeta (c_ {0}, ..., c_ {i})}$

это я ^й коэффициент Жегалкин полинома, литер в я - ^е мономиальных такое же , как литералы в я - ^е minterm, за исключением того, что отрицательные литералов удаляются (или заменены на 1).

Ζ-преобразование является само по себе обратным, поэтому такую ​​же таблицу можно использовать для вычисления коэффициентов с учетом коэффициентов . Просто позволь ${\ displaystyle c_ {0}, ..., c_ {2 ^ {n} -1}}$${\ displaystyle g_ {0}, ..., g_ {2 ^ {n} -1}}$

${\ displaystyle c_ {i} = \ zeta (g_ {0}, ..., g_ {i})}$ .

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

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

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

Метод Паскаля

Использование метода Паскаля для вычисления полинома Жегалкина для булевой функции . В строке на русском внизу написано: - поразрядная операция «Исключающее ИЛИ». ${\ displaystyle {\ bar {a}} {\ bar {b}} {\ bar {c}} + {\ bar {a}} b {\ bar {c}} + {\ bar {a}} bc + ab {\ bar {c}}}$
${\ displaystyle \ oplus}$

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

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

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

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

Метод суммирования

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

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

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

${\ displaystyle a_ {5} = f_ {0} \ oplus f_ {1} \ oplus f_ {4} \ oplus f_ {5} = f (0,0,0) \ oplus f (0,0,1) \ oplus f (1,0,0) \ oplus f (1,0,1)}$

Поскольку нет переменных с постоянным членом,

${\ displaystyle a_ {0} = f_ {0}}$ .

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

${\ displaystyle a_ {N-1} = f_ {0} \ oplus f_ {1} \ oplus f_ {2} \ oplus ... \ oplus f_ {N-2} \ oplus f_ {N-1}}$

Представим графически коэффициенты полинома Жегалкина в виде сумм по модулю 2 значений функций в определенных точках. Для этого строим квадратную таблицу, в которой каждый столбец представляет значение функции в одной из точек, а строка - коэффициент полинома Жегалкина. Точка на пересечении некоторого столбца и строки означает, что значение функции в этой точке входит в сумму для данного коэффициента многочлена (см. Рисунок). Мы называем эту таблицу , где N - количество переменных функции. ${\ displaystyle T_ {N}}$

Существует шаблон, который позволяет получить таблицу для функции от N переменных, имея таблицу для функции от переменных. Новая таблица организована как матрица таблиц 2 × 2 , и правый верхний блок матрицы очищается. ${\ displaystyle N-1}$${\ displaystyle T_ {N} +1}$${\ displaystyle T_ {N}}$

Теоретико-решеточная интерпретация

Считайте столбцы таблицы соответствующими элементами логической решетки размера . Для каждого столбца выразите число M как двоичное число , тогда и только тогда , когда , где обозначает побитовое ИЛИ. ${\ displaystyle T_ {N}}$${\ displaystyle 2 ^ {N}}$${\ displaystyle f_ {M}}$${\ displaystyle M_ {2}}$${\ displaystyle f_ {M} \ leq f_ {K}}$${\ Displaystyle M_ {2} \ vee K_ {2} = K_ {2}}$${\ displaystyle \ vee}$

Если строки таблицы пронумерованы сверху вниз числами от 0 до , то табличное содержимое строки с номером R является идеальным, порожденным элементом решетки. ${\ displaystyle T_ {N}}$${\ displaystyle 2 ^ {N} -1}$${\ displaystyle f_ {R}}$

Заметим кстати, что общий рисунок таблицы представляет собой треугольник Серпинского с логической матрицей . Кроме того, шаблон соответствует элементарному клеточному автомату под названием Правило 60 , начиная с крайней левой ячейки, установленной в 1, а все остальные ячейки очищены. ${\ displaystyle T_ {N}}$

Использование карты Карно

Преобразование отображения Карно в полином Жегалкина.

На рисунке показана функция трех переменных P ( A , B , C ), представленная в виде карты Карно , которую читатель может рассматривать как пример того, как преобразовать такие карты в полиномы Жегалкина; общая процедура состоит из следующих шагов:

• Мы рассматриваем все ячейки карты Карно в порядке возрастания количества единиц в их кодах. Для функции трех переменных последовательность ячеек будет 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 и инвертируется вся карта Карно.
• Процесс преобразования можно считать завершенным, когда после следующей инверсии все ячейки карты Карно становятся нулевыми или не учитываются.

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

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

${\ displaystyle g (x) = \ sum _ {y: y \ leq x} f (y) \ leftrightarrow f (x) = \ sum _ {y: y \ leq x} g (y) \ mu (y, Икс)}$ ,

где , | х | является расстоянием Хэмминга по й от 0. Так как в алгебре Жегалкина, функция Мёбиуса разрушается , чтобы быть постоянными 1. ${\ Displaystyle \ му (у, х) = (- 1) ^ {| х | - | у |}}$${\ Displaystyle -1 \ эквив 1}$

Множество делителей заданного числа х также порядковый идеал , порожденный этим номером: . Поскольку суммирование ведется по модулю 2, формулу можно переформулировать как ${\ Displaystyle \ langle х \ rangle}$

${\ displaystyle g (x) = \ bigoplus _ {y: y \ in \ langle x \ rangle} f (y) \ leftrightarrow f (x) = \ bigoplus _ {y: y \ in \ langle x \ rangle} g (y)}$

Пример

В качестве примера рассмотрим случай с тремя переменными. В следующей таблице показано отношение делимости:

Затем

${\ displaystyle g (000) = f (000)}$

${\ Displaystyle г (001) = е (000) \ oplus f (001)}$

${\ Displaystyle г (010) = е (000) \ oplus f (010)}$

${\ displaystyle g (011) = f (000) \ oplus f (001) \ oplus f (010) \ oplus f (011)}$

${\ Displaystyle г (100) = е (000) \ oplus f (100)}$

${\ Displaystyle г (101) = е (000) \ oplus f (001) \ oplus f (100) \ oplus (101)}$

${\ Displaystyle г (110) = е (000) \ oplus f (010) \ oplus f (100) \ oplus f (110)}$

${\ Displaystyle г (111) знак равно е (000) \ oplus f (001) \ oplus f (010) \ oplus f (011) \ oplus f (100) \ oplus f (101) \ oplus f (110) \ oplus f (111)}$

Вышеупомянутая система уравнений может быть решена относительно f , и результат можно резюмировать как полученный заменой g и f во всей вышеупомянутой системе.

В таблице ниже показаны двоичные числа вместе с соответствующими одночленами Жегалкина и булевыми минтермами:

Логический минтерм	ABC	Жегалкин моном
${\ displaystyle {\ bar {A}} {\ bar {B}} {\ bar {C}}}$	000	1
${\ displaystyle {\ bar {A}} {\ bar {B}} C}$	001	C
${\ displaystyle {\ bar {A}} B {\ bar {C}}}$	010	B
${\ displaystyle {\ bar {A}} до н.э.}$	011	до н.э
${\ displaystyle A {\ bar {B}} {\ bar {C}}}$	100	А
${\ displaystyle A {\ bar {B}} C}$	101	AC
${\ displaystyle AB {\ bar {C}}}$	110	AB
${\ displaystyle ABC}$	111	ABC

Мономы Жегалкина естественным образом упорядочены по делимости, тогда как булевы минтермы сами себя упорядочивают не так естественно; каждая из них представляет собой исключительную восьмую из трех переменных диаграммы Венна . Порядок мономов переносится на битовые строки следующим образом: даны и , пара троек битов, затем . ${\ displaystyle a_ {1} a_ {2} a_ {3}}$${\ displaystyle b_ {1} b_ {2} b_ {3}}$${\ displaystyle a_ {1} a_ {2} a_ {3} \ leq b_ {1} b_ {2} b_ {3} \ leftrightarrow a_ {1} \ leq b_ {1} \ клин a_ {2} \ leq b_ {2} \ wedge a_ {3} \ leq b_ {3}}$

Тогда соответствие между булевой суммой терминов с тремя переменными и полиномом Жегалкина будет следующим:

${\ displaystyle f (000) {\ bar {A}} {\ bar {B}} {\ bar {C}} \ vee f (001) {\ bar {A}} {\ bar {B}} C \ vee f (010) {\ bar {A}} B {\ bar {C}} \ vee f (011) {\ bar {A}} BC \ vee f (100) A {\ bar {B}} {\ bar {C}} \ vee f (101) A {\ bar {B}} C \ vee f (110) AB {\ bar {C}} \ vee f (111) ABC}$

${\ Displaystyle \ qquad \ qquad \ Equiv g (000) \ oplus g (001) C \ oplus g (010) B \ oplus g (011) BC \ oplus g (100) A \ oplus g (101) AC \ oplus g (110) AB \ oplus g (111) ABC}$ .

Приведенная выше система уравнений может быть представлена ​​в виде логического матричного уравнения:

${\ displaystyle {\ begin {pmatrix} g (000) \ g (001) \ g (010) \ g (011) \ g (100) \ g (101) \ g (110) \ \ г (111) \ конец {pmatrix}} = {\ начинаются {pmatrix} 1 && 0 && 0 && 0 && 0 && 0 && 0 && 0 \\ 1 && 1 && 0 && 0 && 0 && 0 && 0 && 0 \\ 1 && 0 && 1 && 0 && 0 && 0 && 0 && 0 \\ 1 && 1 && 1 && 1 && 0 && 0 && 0 && 0 \\ 1 && 0 && 0 && 0 && 1 && 0 && 0 && 0 \\ 1 && 1 && 0 && 0 && 1 && 1 && 0 && 0 \\ 1 && 0 && 1 && 0 && 1 && 0 && 1 && 0 \\ 1 && 1 && 1 && 1 && 1 && 1 && 1 && 1 \ конец {pmatrix}} {\ начать { pmatrix} f (000) \\ f (001) \\ f (010) \\ f (011) \\ f (100) \\ f (101) \\ f (110) \\ f (111) \ end {pmatrix}}}$

который Н. Дж. Вильдбергер называет преобразованием Буля – Мёбиуса.

Ниже показана форма « электронной таблицы XOR » преобразования, идущего в направлении от g к f :

${\ displaystyle f_ {000}}$	${\ displaystyle f_ {001}}$	${\ displaystyle f_ {010}}$	${\ displaystyle f_ {011}}$	${\ displaystyle f_ {100}}$	${\ displaystyle f_ {101}}$	${\ displaystyle f_ {110}}$	${\ displaystyle f_ {111}}$
${\ displaystyle g_ {000}}$	${\ displaystyle g_ {000} \ oplus g_ {001}}$	${\ displaystyle g_ {000} \ oplus g_ {010}}$	${\ displaystyle g_ {000} \ oplus g_ {010} \ oplus g_ {001} \ oplus g_ {011}}$	${\ displaystyle g_ {000} \ oplus g_ {100}}$	${\ displaystyle g_ {000} \ oplus g_ {100} \ oplus g_ {001} \ oplus g_ {101}}$	${\ displaystyle g_ {000} \ oplus g_ {100} \ oplus g_ {010} \ oplus g_ {110}}$	${\ displaystyle g_ {000} \ oplus g_ {100} \ oplus g_ {010} \ oplus g_ {110} \ oplus g_ {001} \ oplus g_ {101} \ oplus g_ {011} \ oplus g_ {111}}$
${\ displaystyle g_ {001}}$	${\ displaystyle g_ {001} \ oplus g_ {010}}$	${\ displaystyle g_ {001} \ oplus g_ {011}}$	${\ displaystyle g_ {001} \ oplus g_ {011} \ oplus g_ {010} \ oplus g_ {100}}$	${\ displaystyle g_ {001} \ oplus g_ {101}}$	${\ displaystyle g_ {001} \ oplus g_ {101} \ oplus g_ {010} \ oplus g_ {110}}$	${\ displaystyle g_ {001} \ oplus g_ {101} \ oplus g_ {011} \ oplus g_ {111}}$
${\ displaystyle g_ {010}}$	${\ displaystyle g_ {010} \ oplus g_ {011}}$	${\ displaystyle g_ {010} \ oplus g_ {100}}$	${\ displaystyle g_ {010} \ oplus g_ {100} \ oplus g_ {011} \ oplus g_ {101}}$	${\ displaystyle g_ {010} \ oplus g_ {110}}$	${\ displaystyle g_ {010} \ oplus g_ {110} \ oplus g_ {011} \ oplus g_ {111}}$
${\ displaystyle g_ {011}}$	${\ displaystyle g_ {011} \ oplus g_ {100}}$	${\ displaystyle g_ {011} \ oplus g_ {101}}$	${\ displaystyle g_ {011} \ oplus g_ {101} \ oplus g_ {100} \ oplus g_ {110}}$	${\ displaystyle g_ {011} \ oplus g_ {111}}$
${\ displaystyle g_ {100}}$	${\ displaystyle g_ {100} \ oplus g_ {101}}$	${\ displaystyle g_ {100} \ oplus g_ {110}}$	${\ displaystyle g_ {100} \ oplus g_ {110} \ oplus g_ {101} \ oplus g_ {111}}$
${\ displaystyle g_ {101}}$	${\ displaystyle g_ {101} \ oplus g_ {110}}$	${\ displaystyle g_ {101} \ oplus g_ {111}}$
${\ displaystyle g_ {110}}$	${\ displaystyle g_ {110} \ oplus g_ {111}}$
${\ displaystyle g_ {111}}$

Связанных с работой

В 1927 году, в том же году, что и работа Жегалкина, американский математик Эрик Темпл Белл опубликовал сложную арифметизацию булевой алгебры, основанную на идеальной теории Ричарда Дедекинда и общей модульной арифметике (в отличие от арифметического модуля 2). Гораздо более простой арифметический характер многочленов Жегалкина был впервые замечен на Западе (независимо, общение между советскими и западными математиками в ту эпоху было очень ограниченным) американским математиком Маршаллом Стоуном в 1936 году, когда он заметил при написании своей знаменитой теоремы двойственности Стоуна, что якобы слабая аналогия между булевыми алгебрами и кольцами могла быть фактически сформулирована как точная эквивалентность, выполняемая как для конечных, так и для бесконечных алгебр, что привело его к существенной реорганизации своей работы в течение следующих нескольких лет.

Смотрите также

• Алгебраическая нормальная форма (АНФ)
• Нормальная форма кольцевой суммы (RSNF)
• Расширение Рида-Мюллера
• Логический домен
• Булевозначная функция

Ноты

использованная литература

дальнейшее чтение

• Гиндикин [Гиндикин], Семен Григорьевич [Семен Г.] (1972). алгебра логики в задачах [ Алгебраическая логика ] (1-е изд.). Москва, Россия: Наука [Наука] . ISBN   0-387-96179-8 . (288 страниц) (Примечание. Перевод: Springer-Verlag , 1985. [1] )
• Perkowski, Marek A .; Григель, Станислав (1995-11-20). «6. Исторический обзор исследований разложения». Обзор литературы по разложению функций . Версия IV. Группа функциональной декомпозиции, Департамент электротехники, Портлендский университет, Портленд, Орегон, США. С. 21–22. CiteSeerX   10.1.1.64.1129 . (188 стр.)