Изменения

Перейти к: навигация, поиск

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

1883 байта добавлено, 16:08, 13 января 2012
Метод треугольника: добавлено обоснование
# Строится полная таблица истинности, в которой строки идут в порядке возрастания двоичных кодов от 000...00 до 111...11.
# Строится вспомогательная треугольная таблица, в которой первый столбец совпадает со столбцом значений функции в таблице истинности.
# Ячейка в каждом последующем столбце получается путём суммирования сложения по модулю 2 двух ячеек предыдущего столбца — стоящей в той же строке и строкой ниже.
# Столбцы вспомогательной таблицы нумеруются двоичными кодами в том же порядке, что и строки таблицы истинности.
# Каждому двоичному коду ставится в соответствие один из членов полинома Жегалкина в зависимости от позиций кода, в которых стоят единицы. Например, ячейке 111 соответствует член ABC, ячейке 101 — член AC, ячейке 010 — член B, ячейке 000 — член 1 и т.д.
# Если в верхней строке какого-либо столбца стоит единица, то соответствующий член присутствует в полиноме Жегалкина.
 
Фактически, этот метод является модификацией метода построения по таблице истинности, описанного выше. По сравнению с ним он удобнее тем, что расчёты занимают мало места и в них сложнее ошибиться, но метод треугольника требует бо́льшего количества операций.
Пример преобразования таблицы истинности в полином Жегалкина для функции трёх переменных P(A,B,C) показан на рисунке.
[[Файл:Преобразование таблицы истинности в полином Жегалкина методом треугольника.gif]]
 
Чтобы получить формулу, по которой рассчитывается какой-либо коэффициент, нужно из клетки, в которой он записан, пройтись всеми возможными путями влево, до столбца ''P'' таблицы истинности, делая ходы влево и влево-вниз, записать значения в конечных ячейках и сложить их все между собой по модулю 2.
 
Таким образом, в первом столбце сверху записан коэффициент <tex> a_0 = P(0,0,0) </tex>,
 
во втором — <tex> a_1 = P(0,0,0) \oplus P(0,0,1) </tex>,
 
в третьем — <tex> 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) </tex>,
 
в четвёртом —
 
<tex> 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,1,0) \oplus P(0,1,1), </tex>
 
и так далее, то есть при построении вспомогательной таблицы автоматически просчитываются коэффициенты по формулам, идентичным методу построения по таблице истинности.
=== Преобразование Мёбиуса ===

Навигация