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

Жегалкин (также Жегалкин , Гегалкин или Шегалкин ^[1]Полиномы являются Жегалкина нормальная алгебраическая форма , также известные как , представлением функций в булевой алгебре . Введен русским математиком Иваном Ивановичем Жегалкиным в 1927 году. ^[2] они представляют собой кольцо многочленов над целыми числами по модулю 2 . В результате вырождения модульной арифметики полиномы Жегалкина оказываются проще обычных многочленов и не требуют ни коэффициентов, ни показателей степени. Коэффициенты являются избыточными, поскольку 1 — единственный ненулевой коэффициент. Экспоненты излишни, потому что в арифметике по модулю 2 x ² = х . Следовательно, полином, такой как 3 x ²и ⁵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. Эти возможные значения приведены в следующей таблице истинности:

$А$	$Б$	$С$	1	$С$	$Б$	$до нашей эры$	$А$	$переменного тока$	$АБ$	$АВС$
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

Информация в приведенной выше таблице истинности может быть закодирована в следующей логической матрице: $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}$ .

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

Тогда линейная система $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}},$ и полином Жегалкина, соответствующий ${\vec {c}}$ является $1\oplus C\oplus AB$ .

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

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

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

Позволять $c_{0},\dots ,c_{2^{n}-1}$ быть выходными данными таблицы истинности для функции P от n переменных, такой, что индекс $c_{i}$ соответствует двоичному индексированию минтермов . ^{[номер 2]} Определите функцию ζ рекурсивно: $\zeta (c_{i}):=c_{i}$ $\zeta (c_{0},\dots ,c_{k}):=\zeta (c_{0},\dots ,c_{k-1})\oplus \zeta (c_{1},\dots ,c_{k}).$ Обратите внимание, что $\zeta (c_{0},\dots ,c_{m})=\bigoplus _{k=0}^{m}{m \choose k}_{2}c_{k}$ где ${\textstyle {m \choose k}_{2}}$ - биномиальный коэффициент, приведенный по модулю 2.

Затем $g_{i}=\zeta (c_{0},\dots ,c_{i})$ это я ^й коэффициент полинома Жегалкина, литералы которого в i ^й моном такие же, как литералы в i ^й minterm, за исключением того, что отрицательные литералы удаляются (или заменяются на 1).

ζ-преобразование является само обратным, поэтому ту же таблицу можно использовать для вычисления коэффициентов $c_{0},\dots ,c_{2^{n}-1}$ учитывая коэффициенты $g_{0},\dots ,g_{2^{n}-1}$ . Просто позволь $c_{i}=\zeta (g_{0},\dots ,g_{i}).$

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

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

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

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

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

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

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

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

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

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

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

$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 \dots \oplus f_{N-2}\oplus f_{N-1}$

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

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

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

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

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

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

Используя карту Карно

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

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

Формула обращения Мёбиуса связывает коэффициенты булевого выражения суммы минтермов и полинома Жегалкина. Это версия формулы Мёбиуса частичного порядка, а не теоретико-числовая. Формула обращения Мёбиуса для частичных порядков: ^[5] $g(x)=\sum _{y:y\leq x}f(y)\leftrightarrow f(x)=\sum _{y:y\leq x}g(y)\mu (y,x),$ где $\mu (y,x)=(-1)^{|x|-|y|}$ , | х | Поскольку расстояние Хэмминга x 0. от $-1\equiv 1$ в алгебре Жегалкина функция Мёбиуса схлопывается до постоянной 1.

Набор делителей данного числа x также является идеалом порядка, порожденным этим числом: $\langle x\rangle$ . Поскольку суммирование производится по модулю 2, формулу можно переформулировать как $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

Затем ${\begin{aligned}g(000)&=f(000)\\[1ex]g(001)&=f(000)\oplus f(001)\\[1ex]g(010)&=f(000)\oplus f(010)\\[1ex]g(011)&=f(000)\oplus f(001)\oplus f(010)\oplus f(011)\\[1ex]g(100)&=f(000)\oplus f(100)\\[1ex]g(101)&=f(000)\oplus f(001)\oplus f(100)\oplus (101)\\[1ex]g(110)&=f(000)\oplus f(010)\oplus f(100)\oplus f(110)\\[1ex]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)\end{aligned}}$

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

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

Логический минтерм	АВС	Одночлен Жегалкина
${\bar {A}}{\bar {B}}{\bar {C}}$	000	1
${\bar {A}}{\bar {B}}C$	001	С
${\bar {A}}B{\bar {C}}$	010	Б
${\bar {A}}BC$	011	до нашей эры
$A{\bar {B}}{\bar {C}}$	100	А
$A{\bar {B}}C$	101	переменного тока
$AB{\bar {C}}$	110	АБ
$ABC$	111	АВС

Мономы Жегалкина естественным образом упорядочиваются по делимости, тогда как булевы минтермы упорядочиваются не так естественно; каждый из них представляет собой исключительную восьмую часть диаграммы Венна с тремя переменными . Порядок мономов переносится на битовые строки следующим образом: $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}$ .

Тогда соответствие между булевой суммой минтермов с тремя переменными и полиномом Жегалкина будет следующим: ${\begin{aligned}&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\\[1ex]&\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.\end{aligned}}$

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

${\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] когда он заметил во время написания своей знаменитой теоремы двойственности Стоуна , что предположительно свободная аналогия между булевыми алгебрами и кольцами на самом деле может быть сформулирована как точная эквивалентность, справедливая как для конечных, так и для бесконечных алгебр, что привело его к существенной реорганизации своей статьи в течение следующих нескольких лет. .

См. также

Примечания

^ В качестве базового варианта $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}.$ КЭД
^ Минтерм — это логический аналог монома Жегалкина . Для контекста с n- переменными существуют $2^{n}$ Мономы Жегалкина и $2^{n}$ Также логические минтермы. Минтерм для контекста с n -переменными состоит из AND-произведения n литералов, каждый из которых либо является переменной в контексте, либо НЕ-отрицанием такой переменной. Более того, для каждой переменной в контексте должен встречаться ровно один раз в каждом минтерме соответствующий литерал (либо утверждение, либо отрицание этой переменной). Таблица истинности для булевой функции от n переменных имеет ровно $2^{n}$ строки, входные данные каждой строки естественным образом соответствуют минтерму, контекст которого представляет собой набор независимых переменных этой булевой функции. (Каждый 0-вход соответствует отрицательной переменной; каждый 1-вход соответствует утвержденной переменной.)
Любое логическое выражение может быть преобразовано в форму суммы минут путем многократного распределения И по отношению к ИЛИ, НЕ по отношению к И или ИЛИ (через тождества Де Моргана), исключая двойное отрицание (см. нормальную форму отрицания ); а затем, когда сумма произведений получена, умножьте произведения с отсутствующими литералами на примеры закона исключенного третьего , которые содержат недостающие литералы; затем, наконец, снова распределите И относительно ИЛИ.
Обратите внимание, что для данного контекста существует формальное соответствие между мономами Жегалкина и булевыми минтермами. Однако соответствие не является логической эквивалентностью. Например, для контекста { A , B , C } существует формальное соответствие между мономом Жегалкина AB и булевым минтермом $AB{\bar {C}}$ , но они логически не эквивалентны. (Подробнее об этом примере см. вторую таблицу в разделе « Преобразование Мёбиуса ». Один и тот же набор битовых строк используется для индексации как набора булевых минтермов, так и набора мономов Жегалкина.)

Ссылки

^ Штайнбах, Бернд [на немецком языке] ; Постхофф, Кристиан (2009). "Предисловие". Написано во Фрайберге, Германия. Логические функции и уравнения - примеры и упражнения (1-е изд.). Дордрехт, Нидерланды: Springer Science + Business Media BV с. хв. ISBN 978-1-4020-9594-8 . LCCN 2008941076 .
^ Jump up to: Перейти обратно: ^а ^б Жегалкин [Zhegalkin], Иван Иванович [Ivan Ivanovich] (1927). "О Технике Вычислении Предложенной в Symbolytscheskoy Logykye" О технике вычислений предложений в символической логике «О технике вычисления высказываний в символической логике». Математический сборник (на русском и французском языках). 34 (1). Москва, Россия: 9–28. Ми msb7433 . Архивировано из оригинала 12 октября 2017 г. Проверено 12 октября 2017 г.
^ Suprun [Супрун], Valeriy P. [Валерий Павлович] (1987). "Tablichnyy metod polinomial'nogo razlozheniya bulevykh funktsiy" Табличный метод полиномиального разложения булевых функций Табличный метод полиномиального разложения булевых функций. Кибернетика [Кибернетика] (Кибернетика) (на русском языке) (1): 116–117.
^ Suprun [Супрун], Valeriy P. [Валерий Павлович] (2017). "Osnovy teorii bulevykh funktsiy" Основы теории булевых функций [Основы теории булевых функций]. М.: Ленанд [Леанд] / УРСС : 208.
^ «Обращение Мёбиуса» . Энциклопедия математики . 17 февраля 2021 г. [07 февраля 2011 г.]. Архивировано из оригинала 16 июля 2020 г. Проверено 27 марта 2021 г.
^ Белл, Эрик Темпл (1927). «Арифметика логики» . Труды Американского математического общества . 29 (3): 597–611. дои : 10.2307/1989098 . JSTOR 1989098 .
^ Стоун, Маршалл (1936). «Теория представлений булевых алгебр». Труды Американского математического общества . 40 (1): 37–111. дои : 10.2307/1989664 . ISSN 0002-9947 . JSTOR 1989664 .

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

Гиндикин [гидикин], Семен Григорьевич [Семен г.] (1972). алгебраическая логика алгебра логики в задачах [ Алгебраическая логика ] (на русском языке) (1-е изд.). Москва, Россия: Наука [Наука] . ISBN 0-387-96179-8 . (288 страниц) (Примечание. Перевод: Springer-Verlag , 1985. [1] )
Перковский, Марек А.; Грыгель, Станислав (20 ноября 1995 г.). «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] Минтерм — это логический аналог монома Жегалкина . Для контекста с n- переменными существуют $2^{n}$ Мономы Жегалкина и $2^{n}$ Также логические минтермы. Минтерм для контекста с n -переменными состоит из AND-произведения n литералов, каждый из которых либо является переменной в контексте, либо НЕ-отрицанием такой переменной. Более того, для каждой переменной в контексте должен встречаться ровно один раз в каждом минтерме соответствующий литерал (либо утверждение, либо отрицание этой переменной). Таблица истинности для булевой функции от n переменных имеет ровно $2^{n}$ строки, входные данные каждой строки естественным образом соответствуют минтерму, контекст которого представляет собой набор независимых переменных этой булевой функции. (Каждый 0-вход соответствует отрицательной переменной; каждый 1-вход соответствует утвержденной переменной.)
Любое логическое выражение может быть преобразовано в форму суммы минут путем многократного распределения И по отношению к ИЛИ, НЕ по отношению к И или ИЛИ (через тождества Де Моргана), исключая двойное отрицание (см. нормальную форму отрицания ); а затем, когда сумма произведений получена, умножьте произведения с отсутствующими литералами на примеры закона исключенного третьего , которые содержат недостающие литералы; затем, наконец, снова распределите И относительно ИЛИ.
Обратите внимание, что для данного контекста существует формальное соответствие между мономами Жегалкина и булевыми минтермами. Однако соответствие не является логической эквивалентностью. Например, для контекста { A , B , C } существует формальное соответствие между мономом Жегалкина AB и булевым минтермом $AB{\bar {C}}$ , но они логически не эквивалентны. (Подробнее об этом примере см. вторую таблицу в разделе « Преобразование Мёбиуса ». Один и тот же набор битовых строк используется для индексации как набора булевых минтермов, так и набора мономов Жегалкина.)

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

[Zhegalkin_1927-2] Jump up to: Перейти обратно: ^а ^б Жегалкин [Zhegalkin], Иван Иванович [Ivan Ivanovich] (1927). "О Технике Вычислении Предложенной в Symbolytscheskoy Logykye" О технике вычислений предложений в символической логике «О технике вычисления высказываний в символической логике». Математический сборник (на русском и французском языках). 34 (1). Москва, Россия: 9–28. Ми msb7433 . Архивировано из оригинала 12 октября 2017 г. Проверено 12 октября 2017 г.

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

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

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

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

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

[1]

[2]

[номер 1]

[номер 2]

[3]

[4]

[5]

[6]

[7]

v т и Нормальные формы в логике
Пропозициональная логика	Нормальная форма отрицания Конъюнктивная нормальная форма Дизъюнктивная нормальная форма Алгебраическая нормальная форма ( полином Жегалкина ) Каноническая форма Блейка Каноническая нормальная форма Оговорка о роге
Логика предикатов	Шолем нормальная форма Гербрандизация Пренекс нормальная форма
Другой	Бета-нормальная форма Модальная клаузальная форма Нормальная форма (естественная дедукция)