Дискретная математика

3.5Различные алгоритмы построения многочлена Жегалкина

3.5.1Алгоритм 1 (посредством СДНФ)

1.Строим СДНФ функции, отличной от нуля (функция f(xe) ≡ 0 уже представлена в виде многочлена Жегалкина).

2.Заменяем все символы " " на " ".

3.Выносим за скобки одинаковые сомножители и упрощаем полученную формулу, применяя тождество

xy xy = x(y y) = x · 1 = x.

4.Все отрицания переменных xi заменяем на выражение xi 1 (в силу равенства xi = xi 1).

5.Раскрываем скобки, учитывая сочетательный и распределительный законы функций алгебры логики.

6.Приводим подобные члены, вычеркивая пары одинаковых слагаемых (согласно тождеству x x = 0).

7.В результате проведенных преобразований получаем многочлен Жегалкина заданной функции.

Пример 3.11. Представить функцию fe = (01001101) в виде многочлена Жегалкина.

Решение.

Представим функцию в виде СДНФ

fсднф = x · y · z x · y · z x · y · z x · y · z

Упростим представление данной функции , используя приведенный выше алгоритм:

f(xe) = x·y·z x·y·z x·y·z x·y·z = x·y·z x·y·z x·y·z x·y·z =

=x · y · z x · y · z xz(y y) = x · y · z x · y · z x · z =

=(x 1)(y 1)z x(y 1)(z 1) xz =

=xyz yz xz z xyz xz xy x xz = yz xz z xy x.

41

Итак, f(xe) = yz xz z xy x- представление заданной функции многочленом Жегалкина.

3.5.2Алгоритм 2 (метод неопределенных коэффициентов)

1.Выписываем в общем виде многочлен Жегалкина функции n переменных

P (xe) =

= a0 a1x1 a2x2 . . . anxn a12x1x2 a13x1x3 . . .

. . . a12:::nx1x2 · · · xn.

2.Для каждого набора αe Bn составляем уравнение P (αe) = f(αe), где P (αe)- выражение, получаемое из многочлена Жегалкина P (xe) при подстановке вместо xe двоичного набора αe. Получаем систему из 2n линейных уравнений (количество уравнений равно количеству двоичных наборов) с 2n неизвестными (неизвестными являются коэффициенты a0, a1, a2 . . . a12:::n). Определитель системы равен 1, система имеет единственное решение.

3.Решая систему, находим все коэффициенты.

4.Подставляя найденные коэффициенты в P (xe), получаем искомый многочлен Жегалкина.

Пример 3.12. Представить функцию fe= (01001101) из примера 3.11 в виде многочлена Жегалкина методом неопределенных коэффициентов.

Решение.

1.Многочлен Жегалкина функции 3 переменных в общем виде задаётся формулой

P (x, y, z) =

= a0 a1x1 a2x2 a3x3 a12x1x2 a13x1x3 a23x2x3 a123x1x2x3.

42

2.Для наглядности зададим функцию таблично. x y z f

Последовательно подставляя наборы в стандартном (лек-

Заметим: если строго придерживаться стандартного порядка, каждое последующее уравнение содержит ровно один новый неизвестный коэффициент. Решаем полученную систему уравнений, учитывая, что 0 0 = 0 и 1 1 = 0.

43

3.Подставляя найденные коэффициенты в P (xe), получаем многочлен Жегалкина заданной функции

f(xe) = x z xy xz yz.

С точностью до слагаемых, многочлен совпал с формулой, полученной в примере 3.11.

3.5.3Алгоритм 3 (метод треугольника)

1.Выписываем левую часть таблицы истинности. Напомним, что она одинакова для всех булевых функций n переменных.

2.Вектор значений функции размещаем в правой части, но не вертикально, а в той же строке, что и набор, состоящий из всех нулей. Эта строка в таблице истинности первая.

3.Попарно складываем по модулю 2 пары соседних значений в стро-

0 0 = 0

0 1 = 1

ке, учитывая, что 1 0 = 1 .

1 1 = 0

44

Результат записываем на 1 строку ниже. Получаем строку, содержащую на 1 элемент меньше, чем в векторе значений.

4.Складываем соседние значения в полученной строке, каждый раз записывая результат в нижней строке и уменьшая на 1 число элементов. Последняя строка, расположенная соответственно набору из всех единиц, содержит только одну цифру.

5.Левые значения полученных строк равны коэффициентам многочлена Жегалкина n переменных P (xe). Подставляя вычисленные коэффициенты в P (xe), получаем многочлен Жегалкина исходной функции.

Пример 3.13. Представить функцию fe= (01001101) из предыдущих примеров в виде многочлена Жегалкина, используя метод треугольника.

Выделенные в правой части числа равны значениям коэффициентов при соответствующих конъюнкциях в многочлене Жегалкина. Индекс многочлена равен номеру ненулевой переменной в левой части. Например,(000) α0, (010) α2, (110) α12 (переменные нумеруются слева направо). И значения коэффициентов

45

3.6Задачи для самостоятельного решения

1.Найти СДНФ, СКНФ и многочлен Жегалкина булевых функций, заданных вектором значений:

1.fe1 = ( 1100 1100 );

2.fe2 = ( 1101 1010 );

3.fe3 = ( 1001 0001 );

4.fe4 = ( 0110 1111 ).

2.Построить таблицу истинности, найти носитель функции, СДНФ, СКНФ и многочлен Жегалкина булевой функции, заданной формулой

1.2.fсднф2 = x · y · z x · y · z x · y · z x · y · z x · y · z;

rсднф2 = 15; fскнф2 = (x y z)&(x y z)&(x y z); rскнф2 = 9; fмн.Жег.2 = 1 y yz xz xy xyz.

46

1.4.fсднф4 = x · y · z x · y · z x · y · z x · y · z x · y · z x · y · z;

rсднф4 = 18; fскнф4 = (x y z)&(x y z); rскнф4 = 6; fмн.Жег.4 = z y x xz xy.

2. fe5 = ( 1111 0111 );

fсднф5 = x·y ·z x·y ·z x·y ·z x·y ·z x·y ·z x·y ·z x·y ·z; rсднф5 = 21; fскнф5 = x y z; rскнф5 = 3; fмн.Жег.5 = 1 x xz xy xyz.

47

Глава 4

Геометрический метод минимизации булевых функций

4.1Постановка задачи минимизации

4.1.1Основные определения

Ранее (см. главу 3) мы уже показывали, что любую двоичную функцию, не являющуюся константой, можно представить в виде ДНФ (например, СДНФ). Кроме того, представление функции в виде ДНФ не является однозначным для данной функции. Различные ДНФ, реализующие одну и ту же булеву функцию, могут иметь различный ранг (см. замечание 3.3 на стр. 29). Совершенная ДНФ имеет максимальный ранг среди ДНФ данной функции.

Попытаемся представить любую функцию алгебры логики в виде ДНФ, имеющей как можно меньший ранг.

Определение 4.1. Элементарная конъюнкция

48

Из определения следует, что на всех двоичных наборах, на которых импликанта обращается в единицу, функция f также обращается в единицу. На тех наборах, на которых функция обращается в нуль, импликанта также обращается в нуль, значит, нулей у импликанты функции не меньше, чем у самой функции.

Все элементарные конъюнкции, входящие в СДНФ функции f, являются импликантами данной функции.

Пример 4.1. Дана двоичная функция f(x, y, z) = (0101 0001).