Учебное пособие 800647

Метод неопределенных коэффициентов

Метод неопределенных коэффициентов состоит в следующем [2]: записываем булеву функцию в виде полинома Жегалкина с неопределенными коэффициентами. Приравниваем значения функции к значениям полинома на соответствующих наборах переменных и находим неизвестные коэффициенты.

Теперь воспользуемся методом неопределенных коэффициентов. Для этого запишем исходную функцию (16) в общем виде в соответствии с (15), то есть в виде многочлена с неопределенными коэффициентами, получим:

f (x, y,z) H Ex Fy Gz Dyz Cxz Bxy Axyz, (17)

где A, B, C, D, E, F, G, H {0,1}.

Таблица истинности нашей функции выглядит следующим образом:

Таблица 2

Таблица истинности функции

Чтобы определить неизвестные коэффициенты, подставим соответствующие значения переменных в правую и левую части формулы (17) и получим систему:

9

C E G H 1

B E F H 0

A B C D E F G H 1

Решая систему, получим коэффициенты равные: H=0, G=0, F=0, D=0, E=1, C=0, B=1, A=1. Подставляя найденные значения A, B, C, D, E, F, G, H в формулу (17), получим полином Жегалкина:

f (x, y,z) 0 1*x 0* y 0*z 0*yz 0*xz

,

1*xy 1*xyz x xy xyz

Этот полином имеет тот же вид, что и полином, полученный методом аналитического преобразования произвольной формулы алгебры логики:

P(x, y,z) xyz xy x.

Метод треугольника Паскаля

Метод треугольника Паскаля заключается в следующем: выписываем упорядоченные значения исходной булевой функции; складываем по модулю 2 пары рядом стоящих значений БФ и выписываем результат сложения каждой пары; далее продолжаем сложение по модулю 2 рядом стоящих результатов предшествующих сложений до тех пор, пока не будет получен единственный результат сложения. В результате, числа на левой стороне полученного треугольника определяют коэффициенты полинома Жегалкина при соответствующих

10

монотонных конъюнкциях. Напомним, что элементарная конъюнкция называется монотонной, если она не содержит отрицаний переменных. Константа 1 (то есть элементарная конъюнкция нулевого ранга) считается по определению монотонной конъюнкцией.

Для реализации метода зададим исходную функцию набором значений f(x,y,z)=(00001101). На строке значений функции построим треугольник Паскаля, представленный на рис. 1, складывая попарно по модулю 2 соседние значения функции.

Рис. 1 Треугольник Паскаля

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

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

Следовательно, полученный методом треугольника Паскаля полином Жегалкина имеет вид:

P(x, y,z) xyz xy x .

11

Таблица 3

Интерпретация значений, полученных с помощью метода треугольника Паскаля

100x

101xz

110xy

111xyz

ЗАДАНИЕ: Получить ПНФ булевой функции F(a,b,c),

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

12

Таблица 4

Номер ваАналитический вид функции F(a,b,c) рианта

1F1(a,b,c) (a c)(ab c)

2F2(a,b,c) (a cb)(ab c)

4F4(a,b,c) (a c)(ab c)(a c)

5F5(a,b,c) (b c)(ab c)

6F6 (a,b,c) (a c)(ab c)(с b)

7F7 (a, b,c) (a b)(ab c)

8F8 (a,b,c) cb(a c)(a b)

9F9 (a, b,c) (c ab)(cb a)

10F10 (a,b,c) (c b)(a c)(ac b)

2.Записать аналитический метод получения полиномиальной нормальной формы булевой функции – метод неопределенных коэффициентов – в общем виде для булевых функций, зависящих от n-переменных.

Лабораторная работа №2

ПОЛИНОМИАЛЬНОЕ РАЗЛОЖЕНИЕ БУЛЕВЫХ ФУНКЦИЙ НА ОСНОВЕ МЕТОДА НЕОПРЕДЕЛЕННЫХ КОЭФФИЦИЕНТОВ

ЦЕЛЬ: изучение метода неопределённых коэффициентов и алгоритмов автоматического полиномиального разло-

13

жения n – аргументных булевых функций, базирующихся на его основе.

Известно несколько методов автоматического полиномиального разложения булевых функций [2], каждый из которых имеет свои преимущества и недостатки. Рассмотрим три модификации одного и того же метода преобразования n – аргументных булевых функций к полиному Жегалкина [8]. Предлагаемые подходы базируются на методе неопределенных коэффициентов и требуют для реализации упорядоченного вектора F (f0 ,f1,...,fi ,...,f2n 1 ) значений булевой функции на

всех возможных наборах значений аргументов [9].

Суть предлагаемого подхода состоит в том, что исходная булева функция n аргументов представляется в виде 2n – компонентного вектора F (f0 ,f1,..., fi ,...,f2n 1), каждый компо-

нент которого может быть равен 0 или 1 и однозначно соответствует значению булевой функции на i-ом наборе значений входных переменных.

Так, например, для функции F(a, b, c) булев 23 – вектор F(a, b, c)=(1 0 1 0 0 1 1 0), интерпретируется как множество

значений булевой функции на i-ом входном наборе значений переменных a, b, c. При этом сами наборы переменных интерпретируются как позиционные двоичные коды целых неотрицательных чисел, следующих друг за другом в лексиграфическом порядке, чаще всего в порядке возрастания своих значе-

ний, например, 000, 001, 010, 011, 100, 101, 110, 111 (при n=3).

За каждым разрядом позиционного кода закрепляется какаялибо одна входная переменная. При этом разряд позиционного кода одновременно характеризует имя переменной и ее значение на i-ом входном наборе. Поясним сказанное с помо-

щью табл. 5 для функции F(a, b, c)=(10100110).

14

Таблица 5

В самой левой колонке табл. 5 указаны элементарные конъюнкции максимального ранга Ki, соответствующие i – му набору входных переменных.

СДНФ функции F(a, b, c) может быть записана в следующем виде:

F(a, b,c) Vi2n0 1 fiKi ,

(18)

где V – знак дизъюнкции.

Для представления булевой функции n аргументов в виде полинома Жегалкина так же используется 2n – компонентный вектор G (g0 ,g1,...,gi ,...,g2n 1), каждый компо-

нент которого может быть равен 0 или 1 и однозначно соответствует некоторой монотонной конъюнкции Kiм, являющейся членом полинома Жегалкина общего вида.

Тогда булева функция F(a, b, c) может быть представлена в виде полинома Жегалкина как

15

i 0

где – знак суммы по модулю 2; Kiм – монотонная

конъюнкция, то есть логическое произведение только тех логических переменных, которые в i - ом входном наборе равны

1.Конъюнкция K0м всегда принимается равной 1.

Втабл. 6 представлены все монотонные конъюнкции,

входящие в полином Жегалкина общего вида для булевой функции от аргументов a, b, c и соответствующие Kiм компо-

ненты вектора G (g0 ,g1,...,gi ,...,g2n 1).

Таблица 6

С учетом данных табл. 5 и 6, а также соотношения (19) имеем следующий общий вид полинома Жегалкина для функ-

ции F(a, b, c):

P(a,b,c) g01 g1c g2b g3bc g4a g5ac g6ab g7abc, (20)

где – знак суммы по модулю 2.

Метод неопределенных коэффициентов заключается в последовательном нахождении компонент вектора G как сумм

16

по модулю 2 некоторой совокупности компонент вектора F и уже определенных компонент вектора G. Поясним это на при-

мере функции F(a, b, c)=(10100110).

В левую часть соотношения (20) будем последовательно подставлять значения fi , а в правую часть – соответствующие значения переменных на i-ом входном наборе. В результате такой последовательной подстановки получим следующую систему уравнений:

g7 g0 g1 g2 g3 g4 g5 g6 f7

Как видно из системы уравнений (21) – (28) компоненты вектора F могут быть однозначно определены на основании компонент вектора G, что позволяет получить СДНФ булевой функции непосредственно по соответствующему полиному Жегалкина.

Преобразуем систему уравнений (21) – (28) к следующему виду:

17

Система уравнений (29) – (36) позволяет однозначно определять компоненты вектора G на основании компонент вектора F, что широко известно. Найдем формальное правило, которое бы позволяло для произвольного gi автоматически формировать и решать соответствующее уравнение (29) – (36) для булевой функции произвольного числа аргументов.

Рассмотрим алгоритмическую возможность формирования компонент вектора G по их индексу, представленному в двоичном позиционном коде, для чего представим систему уравнений (29) – (36) для функции F(a, b, c) = (10100110) в

виде табл. 7.

Таблица 7

На основании табл. 7 легко осуществляется переход от СДНФ булевой функции к её полиномиальному представлению в виде полинома Жегалкина. Для этого необходимо в

18