Лекция № 12

(лек. 2 час + прак. занят 2 час + самос. 4 час)

Синтез с помощью булевых функций электронных схем (на примере сумматора)

Многочлены Жегалкина

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

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

Многочлен Жегалкина константы равен самой же константе;

мно­гочлен Жегалкина булевой функции одной переменной ;

многочлен Жегалкина булевой функции двух переменных

;

многочлен Жегалкина булевой функции трех переменных

и т.д. Коэффициенты a_1,...,i и свободный член а₀ принимают значения 0 или 1, а число слагаемых в формуле равно 2ⁿ, где п — число переменных. Знак — сумма Жегалкина или сумма по модулю два.

Теорема 3 (Жегалкина). Каждая булева функция f(х₁, х₂,..., х_п) может быть представлена в виде многочлена Жегалкина и притом единственным образом, с точностью до порядка слагаемых.

Сформулируем алгоритм построения многочлена Жегалкина. Выше было указано, что любую функцию, отличную от константы 0, можно представить в виде СДНФ. Если сравним таблицы истинности дизъюнкции и суммы по модулю два, видим, что они отличаются только последней строкой, т. е. на наборе 11. Так как в СДНФ на каждом наборе только одна конъюнкция равна 1, то все дизъюнкции можно заменить суммами по модулю два. Кроме того, известно, что . На этом и основан первый алгоритм построения многочлена Жегалкина:

1. Находим множество тех двоичных наборов, на которых функция принимает значение 1.

2. Составляем СДНФ.

3. В СДНФ каждый знак дизъюнкции меняем на знак суммы Жегал­кина.

4. Упрощаем, если можно, полученное выражение, используя тожде­ство .

5. В полученной формуле каждое отрицание заменяем на .

6. Раскрываем скобки в полученной формуле, содержащей только функции и и константу 1.

7. Приводим подобные члены, используя тождество .

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

1. Составляем систему линейных уравнений относительно 2ⁿ неиз­вестных коэффициентов, содержащую 2ⁿ уравнений, решением которой являются коэффициенты а₀, a₁,..., а_12…n многочлена Жегалкина.

Многочлен Жегалкина называется нелинейным, если он содержит конъюнкции переменных, а если он не содержит конъюнкции перемен­ных, то он называется линейным.

Функция f(х₁, х₂,..., х_п) называется линейной, если ее многочлен Же­галкина имеет вид , и нелинейной в противном случае.

Из определения многочлена Жегалкина следует, что для любой буле­вой функции коэффициенты при переменных х₁, х₂,..., х_п и свободный член вычисляются по формулам:

а₀ = f(0, 0,...,0),

,

,

…………..

.

На этом основан алгоритм определения линейности (или нелинейно­сти) булевой функции.

1. По таблицам истинности булевой функции f(х₁, х₂,..., х_п) и выше указанным формулам находим коэффициенты: (а_о, а₁,..., а_n).

2. Выписываем многочлен и про­веряем, задает ли он эту функцию. Для этого строим таблицу истинности многочлена Ф(х₁, х₂,..., х_п) и сравниваем ее с таблицей истинности функ­ции f(х₁, х₂,..., х_п).

Если таблицы истинности совпадают, то функция f(х₁, х₂,..., х_п) ли­нейная и Ф(х₁, x₂,...,x_п) — ее многочлен Жегалкина. В противном случае функция нелинейная.

Дата добавления: 2015-07-07