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

Жегалкина (также Žegalkin , Gégalkine или Shegalkin ^[1] ) полиномы являются представление функций в булевой алгебре . Введенные русским математиком Иваном Ивановичем Жегалкиным в 1927 году ^[2], они представляют собой кольцо многочленов над целыми числами по модулю 2 . Получающиеся вырождения модулярной арифметики приводят к тому, что многочлены Жегалкина проще обычных многочленов и не требуют ни коэффициентов, ни показателей. Коэффициенты избыточны, потому что 1 - единственный ненулевой коэффициент. Показатели избыточны, потому что в арифметике по модулю 2 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- мерные операции над {0,1}, дает прямой счетный аргумент в пользу полноты полиномов Жегалкина как булевого базиса.

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

Метод расчета [ править ]

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

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

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

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

Пример [ править ]

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

{\vec {f}}={\begin{pmatrix}1\\0\\1\\0\\1\\0\\0\\1\end{pmatrix}}

.

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

{\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. Эти возможные значения приведены в следующей таблице истинности:

{\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|}A&B&C&\;\;\;\;\;\;\;\;&1&C&B&BC&A&AC&AB&ABC\\\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\end{array}}

.

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

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\end{pmatrix}}

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

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

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

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

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

{\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&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\end{pmatrix}}{\begin{pmatrix}1\\0\\1\\0\\1\\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\end{pmatrix}}

,

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

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

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

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

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

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

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

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

.

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

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

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

Затем

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

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

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

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

.

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

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

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

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

Использование метода Паскаля для вычисления полинома Жегалкина для булевой функции . В строке на русском внизу написано: - поразрядная операция «Исключающее ИЛИ»

{\bar {a}}{\bar {b}}{\bar {c}}+{\bar {a}}b{\bar {c}}+{\bar {a}}bc+ab{\bar {c}}

\oplus

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

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

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

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

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

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

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

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

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)

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

a_{0}=f_{0}

.

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

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

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

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

Теоретико-решеточная интерпретация [ править ]

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

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

Заметим, кстати, что общий рисунок таблицы представляет собой треугольник Серпинского с логической матрицей . Кроме того, шаблон соответствует элементарному клеточному автомату под названием Правило 60 , начиная с крайней левой ячейки, установленной в 1, а все остальные ячейки очищены. $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 и инвертируется вся карта Карно.
Процесс преобразования можно считать завершенным, когда после следующей инверсии все ячейки карты Карно становятся нулевыми или не учитываются.

Преобразование Мебиуса [ править ]

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

g(x)=\sum _{y:y\leq x}f(y)\leftrightarrow f(x)=\sum _{y:y\leq x}g(y)\mu (y,x)

, ^[5]

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

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

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

Пример [ править ]

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

Икс	делители x
000	000
001	000, 001
010	000, 010
011	000, 001, 010, 011
100	000, 100
101	000, 001, 100, 101
110	000, 010, 100, 110
111	000, 001, 010, 011, 100, 101, 110, 111

Затем

g(000)=f(000)

g(001)=f(000)\oplus f(001)

g(010)=f(000)\oplus f(010)

g(011)=f(000)\oplus f(001)\oplus f(010)\oplus f(011)

g(100)=f(000)\oplus f(100)

g(101)=f(000)\oplus f(001)\oplus f(100)\oplus (101)

g(110)=f(000)\oplus f(010)\oplus f(100)\oplus f(110)

g(111)=f(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	Жегалкин моном
${\bar {A}}{\bar {B}}{\bar {C}}$	000	1
${\bar {A}}{\bar {B}}C$	001	C
${\bar {A}}B{\bar {C}}$	010	B
${\bar {A}}BC$	011	до н.э
$A{\bar {B}}{\bar {C}}$	100	А
$A{\bar {B}}C$	101	AC
$AB{\bar {C}}$	110	AB
$ABC$	111	ABC

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

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

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

\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

.

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

{\begin{pmatrix}g(000)\\g(001)\\g(010)\\g(011)\\g(100)\\g(101)\\g(110)\\g(111)\end{pmatrix}}={\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\end{pmatrix}}{\begin{pmatrix}f(000)\\f(001)\\f(010)\\f(011)\\f(100)\\f(101)\\f(110)\\f(111)\end{pmatrix}}

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

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

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

Связанные работы [ править ]

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

См. Также [ править ]

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

Заметки [ править ]

^ В качестве базового случая
$S_{0}:={\begin{pmatrix}1\end{pmatrix}}$
$(S_{0})^{2}={\begin{pmatrix}1\end{pmatrix}}=I_{0}$
где здесь принято обозначать единичную матрицу размера . Индуктивное предположение $I_{n}$ $2^{n}\times 2^{n}$
$(S_{n})^{2}=I_{n}$ .
Тогда индуктивный шаг:
$S_{n+1}:={\begin{pmatrix}S_{n}&O\\S_{n}&S_{n}\end{pmatrix}}\equiv {\begin{pmatrix}1&0\\1&1\end{pmatrix}}\otimes S_{n}$ ,
где обозначает произведение Кронекера , $\otimes$
$(S_{n+1})^{2}={\begin{pmatrix}S_{n}&O\\S_{n}&S_{n}\end{pmatrix}}{\begin{pmatrix}S_{n}&O\\S_{n}&S_{n}\end{pmatrix}}={\begin{pmatrix}S_{n}S_{n}\oplus OS_{n}&S_{n}O\oplus OS_{n}\\S_{n}S_{n}\oplus S_{n}S_{n}&S_{n}O\oplus S_{n}S_{n}\end{pmatrix}}={\begin{pmatrix}I_{n}&O\\I_{n}\oplus I_{n}&I_{n}\end{pmatrix}}={\begin{pmatrix}I_{n}&O\\O&I_{n}\end{pmatrix}}=I_{n+1}$ ,
или, в терминах продукта Кронекера:
$S_{n+1}^{2}=(S_{1}\otimes S_{n})(S_{1}\otimes S_{n})=S_{1}^{2}\otimes S_{n}^{2}=I_{1}\otimes I_{n}=I_{n+1}$ . ∎
^ Minterm является булево аналогом Жегалкина одночлена . Для n -переменного контекста существуют такжемономы Жегалкина ибулевы минтермы. Минтерм для n -переменного контекста состоит из AND-произведения n литералов, каждый из которых является либо переменной в контексте, либо НЕ-отрицанием такой переменной. Более того, для каждой переменной в контексте должен появляться ровно один раз в каждом минтерме соответствующий литерал (либо утверждение, либо отрицание этой переменной). Таблица истинности для булевой функции n переменных имеет ровно $2^{n}$ $2^{n}$ $2^{n}$ rows, входные данные каждой строки естественно соответствуют minterm, контекст которого является набором независимых переменных этой логической функции. (Каждый входной 0 соответствует отрицательной переменной; каждый вход 1 соответствует утвержденной переменной.)
Любое логическое выражение может быть преобразовано в форму суммы-minterms путем многократного распределения AND относительно OR, NOT относительно AND или ИЛИ (через тождества Де Моргана), отменяющее двойное отрицание (ср. Нормальную форму отрицания ); а затем, когда получена сумма произведений, умножьте произведения с недостающими литералами на экземпляры закона исключенного среднего, которые содержат недостающие литералы; затем - наконец - снова распределите И по отношению к ИЛИ.
Обратите внимание, что для данного контекста существует формальное соответствие между мономами Жегалкина и булевыми минтермами. Однако соответствие не является логической эквивалентностью. Например, для контекста { A , B , C } существует формальное соответствие между мономом Жегалкина AB и булевым минтермом , но они не являются логически эквивалентными. (Подробнее об этом примере см . Во второй таблице в разделе « Преобразование Мёбиуса ». Один и тот же набор битовых строк используется для индексации как набора логических минтермов, так и набора мономов Жегалкина.) $AB{\bar {C}}$

Ссылки [ править ]

^ Штейнбах, Бернд ; Постхофф, Кристиан (2009). "Предисловие". Написано во Фрайберге, Германия. Логические функции и уравнения - Примеры и упражнения (1-е изд.). Дордрехт, Нидерланды: Springer Science + Business Media BV с. XV. ISBN 978-1-4020-9594-8. LCCN 2008941076 .
^ a b Жега́лкин [Жегалкин], Ива́н Ива́нович [Иван Иванович] (1927). "О Технике Вычисления Предложений в Символической Логике"О технике вычислений предложений в символической логике[О технике вычисления предложений в символической логике (Sur le Calcul des propositions dans la logique symbolique)]. Математический сборник . Москва, Россия. 34 (1): 9–28. Mi msb7433 . Архивировано 12 октября 2017 года . Проверено 12 октября 2017 .
^ Супрун [Супрун], Валерий П. [Валерий Павлович] (1987). "Табличный метод полиномиального разложения бульевых функций"Табличный метод полиномиального разложения булевых функций[Табличный метод полиномиального разложения булевых функций]. Кибернетика [Кибернетика] ( на русском языке) (1): 116–117.
^ Супрун [Супрун], Валерий П. [Валерий Павлович] (2017). "Основы теории булевых функций"Основы теории булевых функций[Основы теории булевых функций]. М .: Ленанд [Ленанд] / УРСС : 208.
^ "Мёбиуса инверсия" . Энциклопедия математики . 2021-02-17 [2011-02-07]. Архивировано 16 июля 2020 года . Проверено 27 марта 2021 .
^ Белл, Эрик Темпл (1927). «Арифметика логики» . Труды Американского математического общества . 29 (3): 597–611. DOI : 10.2307 / 1989098 . JSTOR 1989098 .
^ Стоун, Маршалл (1936). «Теория представлений булевых алгебр». Труды Американского математического общества . 40 (1): 37–111. DOI : 10.2307 / 1989664 . ISSN 0002-9947 . JSTOR 1989664 .

Дальнейшее чтение [ править ]

Гиндикин [Гиндикин], Семен Григорьевич [Семен Г.] (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 стр.)

[NB1-3] В качестве базового случая
$S_{0}:={\begin{pmatrix}1\end{pmatrix}}$
$(S_{0})^{2}={\begin{pmatrix}1\end{pmatrix}}=I_{0}$
где здесь принято обозначать единичную матрицу размера . Индуктивное предположение $I_{n}$ $2^{n}\times 2^{n}$
$(S_{n})^{2}=I_{n}$ .
Тогда индуктивный шаг:
$S_{n+1}:={\begin{pmatrix}S_{n}&O\\S_{n}&S_{n}\end{pmatrix}}\equiv {\begin{pmatrix}1&0\\1&1\end{pmatrix}}\otimes S_{n}$ ,
где обозначает произведение Кронекера , $\otimes$
$(S_{n+1})^{2}={\begin{pmatrix}S_{n}&O\\S_{n}&S_{n}\end{pmatrix}}{\begin{pmatrix}S_{n}&O\\S_{n}&S_{n}\end{pmatrix}}={\begin{pmatrix}S_{n}S_{n}\oplus OS_{n}&S_{n}O\oplus OS_{n}\\S_{n}S_{n}\oplus S_{n}S_{n}&S_{n}O\oplus S_{n}S_{n}\end{pmatrix}}={\begin{pmatrix}I_{n}&O\\I_{n}\oplus I_{n}&I_{n}\end{pmatrix}}={\begin{pmatrix}I_{n}&O\\O&I_{n}\end{pmatrix}}=I_{n+1}$ ,
или, в терминах продукта Кронекера:
$S_{n+1}^{2}=(S_{1}\otimes S_{n})(S_{1}\otimes S_{n})=S_{1}^{2}\otimes S_{n}^{2}=I_{1}\otimes I_{n}=I_{n+1}$ . ∎

[NB2-4] Minterm является булево аналогом Жегалкина одночлена . Для n -переменного контекста существуют такжемономы Жегалкина ибулевы минтермы. Минтерм для n -переменного контекста состоит из AND-произведения n литералов, каждый из которых является либо переменной в контексте, либо НЕ-отрицанием такой переменной. Более того, для каждой переменной в контексте должен появляться ровно один раз в каждом минтерме соответствующий литерал (либо утверждение, либо отрицание этой переменной). Таблица истинности для булевой функции n переменных имеет ровно $2^{n}$ $2^{n}$ $2^{n}$ rows, входные данные каждой строки естественно соответствуют minterm, контекст которого является набором независимых переменных этой логической функции. (Каждый входной 0 соответствует отрицательной переменной; каждый вход 1 соответствует утвержденной переменной.)
Любое логическое выражение может быть преобразовано в форму суммы-minterms путем многократного распределения AND относительно OR, NOT относительно AND или ИЛИ (через тождества Де Моргана), отменяющее двойное отрицание (ср. Нормальную форму отрицания ); а затем, когда получена сумма произведений, умножьте произведения с недостающими литералами на экземпляры закона исключенного среднего, которые содержат недостающие литералы; затем - наконец - снова распределите И по отношению к ИЛИ.
Обратите внимание, что для данного контекста существует формальное соответствие между мономами Жегалкина и булевыми минтермами. Однако соответствие не является логической эквивалентностью. Например, для контекста { A , B , C } существует формальное соответствие между мономом Жегалкина AB и булевым минтермом , но они не являются логически эквивалентными. (Подробнее об этом примере см . Во второй таблице в разделе « Преобразование Мёбиуса ». Один и тот же набор битовых строк используется для индексации как набора логических минтермов, так и набора мономов Жегалкина.) $AB{\bar {C}}$

[Steinbach_2009-1] Штейнбах, Бернд ; Постхофф, Кристиан (2009). "Предисловие". Написано во Фрайберге, Германия. Логические функции и уравнения - Примеры и упражнения (1-е изд.). Дордрехт, Нидерланды: Springer Science + Business Media BV с. XV. ISBN 978-1-4020-9594-8. LCCN 2008941076 .

[Zhegalkin_1927-2] Жега́лкин [Жегалкин], Ива́н Ива́нович [Иван Иванович] (1927). "О Технике Вычисления Предложений в Символической Логике"О технике вычислений предложений в символической логике[О технике вычисления предложений в символической логике (Sur le Calcul des propositions dans la logique symbolique)]. Математический сборник . Москва, Россия. 34 (1): 9–28. Mi msb7433 . Архивировано 12 октября 2017 года . Проверено 12 октября 2017 .

[Suprun_1987-5] Супрун [Супрун], Валерий П. [Валерий Павлович] (1987). "Табличный метод полиномиального разложения бульевых функций"Табличный метод полиномиального разложения булевых функций[Табличный метод полиномиального разложения булевых функций]. Кибернетика [Кибернетика] ( на русском языке) (1): 116–117.

[Suprun_2017-6] Супрун [Супрун], Валерий П. [Валерий Павлович] (2017). "Основы теории булевых функций"Основы теории булевых функций[Основы теории булевых функций]. М .: Ленанд [Ленанд] / УРСС : 208.

[Möbius_2021-7] "Мёбиуса инверсия" . Энциклопедия математики . 2021-02-17 [2011-02-07]. Архивировано 16 июля 2020 года . Проверено 27 марта 2021 .

[Bell_1927-8] Белл, Эрик Темпл (1927). «Арифметика логики» . Труды Американского математического общества . 29 (3): 597–611. DOI : 10.2307 / 1989098 . JSTOR 1989098 .

[Stone_1936-9] Стоун, Маршалл (1936). «Теория представлений булевых алгебр». Труды Американского математического общества . 40 (1): 37–111. DOI : 10.2307 / 1989664 . ISSN 0002-9947 . JSTOR 1989664 .

[1]