22
правки
Изменения
Добавил метод треугольника
<tex>P = a_0 \oplus a_1 x_1 \oplus a_2 x_2 \oplus ... \oplus a_n x_n \oplus a_{n+1} x_1 x_2 \oplus ... \oplus a_{..n + C_{n}^2} x_{n-1} x_n \oplus ... \oplus a_{2^n-1} x_1 x_2 ... x_n </tex>
== Предпосылки ==
<tex>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</tex>
=== Метод треугольника === <!-- Да, копипаста с википедии, и что? Метод же прост и удобен -->
Метод треугольника позволяет преобразовать таблицу истинности в полином Жегалкина путём построения вспомогательной треугольной таблицы в соответствии со следующими правилами:
* Строится полная таблица истинности, в которой строки идут в порядке возрастания двоичных кодов от 000...00 до 111...11.
* Строится вспомогательная треугольная таблица, в которой первый столбец совпадает со столбцом значений функции в таблице истинности.
* Ячейка в каждом последующем столбце получается путём суммирования по модулю 2 двух ячеек предыдущего столбца — стоящей в той же строке и строкой ниже.
* Столбцы вспомогательной таблицы нумеруются двоичными кодами в том же порядке, что и строки таблицы истинности.
* Каждому двоичному коду ставится в соответствие один из членов полинома Жегалкина в зависимости от позиций кода, в которых стоят единицы. Например, ячейке 111 соответствует член ABC, ячейке 101 — член AC, ячейке 010 — член B, ячейке 000 — член 1 и т.д.
* Если в верхней строке какого-либо столбца стоит единица, то соответствующий член присутствует в полиноме Жегалкина.
Пример преобразования таблицы истинности в полином Жегалкина для функции трёх переменных P(A,B,C) показан на рисунке.
[[Файл:Преобразование таблицы истинности в полином Жегалкина методом треугольника.gif]]
=== Преобразование Мёбиуса ===
