Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

МАТ_ ЛОГИКА / МАТЕМАТИЧЕСКАЯ ЛОГИКА_ЛК6_20_02_2012_Полином Жегалкина_Минимизация булевых функций

.doc
Скачиваний:
65
Добавлен:
06.06.2015
Размер:
137.73 Кб
Скачать

Алгебра и полином Жегалкина.

Рассмотрим следующую систему функций:

,

где «  » – сложение по модулю 2, а «» – умножение по модулю 2, т.е. сложение и умножение двоичных чисел в одном разряде. .

x1

x2

x1x2

x1

х2

x1  x2

0

0

0

0

0

0

0

1

1

0

1

0

1

0

1

1

0

0

1

1

0

1

1

1

Покажем, что рассмотренная система функций  является полной.

Ранее доказано, что система ¬ , состоящая из отрицания и конъюнкции, является полной. Покажем, что функции ¬ выражаются через :

x

¬x

x1

0

1

1

1

0

0

¬х=х 1,

x1 x2 = x1x2.

Любая булева функция выражается через единицу, сложение и умножение по модулю 2, т.е. система  является полной.

Множество формул записанных с помощью операций   , называют алгеброй Жегалкина. В алгебре Жегалкина используется та же логика что и в работе ЭВМ на низком уровне, т.е. на уровне битов и байтов (ассемблеров).

В алгебре Жегалкина выполняются следующие свойства:

  1. ху=ух

  2. ху=ух

  3. (ху)z=xzyz

  4. x x=0

  5. х1=х

Представляя булеву функцию с помощью СДНФ, представляя потом дизъюнкцию через умножение и сложение по модулю 2 и раскрывая затем скобки, используя свойства 1–5, получим многочлен, который называют многочленом Жегалкина или полиномом Жегалкина.

Полином Жегалкина для отрицания

¬ х=х 1

Полином Жегалкина для конъюнкции

x1 x2 = x1x2

Построим полином Жегалкина для дизъюнкции

x1 x2=  x1 x2)=(  x1 x2)=  x1 x2=

= x1 x2= x1 x2  x1 x2= x1 x2x1 x2.

Напишем полином Жегалкина для эквиваленции:

x1x2=(x1x2)(x2x1)=( x1x2) x2x1( x1x2 x1x2)

 (x1x2 x2x1)=((х11)х2х11х2)(х121)(х21)х1)=

  1. =(x1x2x2x2x11)(х1х2x1x1х21)= x x=0=

=(x1x2x11)(x1x2x21)=x1x2x1x2x1x2x1x2x1x2x1x1x2x21=

= x1x21.

Заметим, что если  = 0, то  =. Это следует когда  либо  равно единице, следовательно, в дизъюнктивной нормальной форме мы можем заменять дизъюнкции на сложение по модулю 2.

Пример. = x1 x2x3x1=x1(x21)x3x1 = x1x2x3x1x1 полином Жегалкина.

Итак, полиномы Жегалкина для отрицания, дизъюнкции, эквиваленции:

Полиномом (многочленом) Жегалкина от п переменных называется функция

P =xx2  ... nxn n +1xx2 ...n +C2nxn-1xn  ... 2n-1xx2..xn

Всего здесь 2п слагаемых. Напомним, что + сейчас означает сложение по модулю 2, коэффициенты , n-1   являются константами (равными нулю или единице).

Теорема. Любая функция п переменных может быть представлена полиномом Жегалкина и это представление единственно (с точностью до коммутативности конъюнкции & и ).

□ Любая функция f(x1, x2, , xn) имеет свою таблицу истинности. Запишем сначала данную функцию в виде полинома Жегалкина с неопределенными коэффициентами. Затем по очереди подставляем всевозможные наборы переменных и находим коэффициенты. Легко видеть, что за каждую подстановку находим только один коэффициент. Так как число наборов равно числу коэффициентов (и равно 2п), отсюда следует утверждение теоремы. ■

Доказательство этой теоремы показывает, как по таблице истинности построить полином Жегалкина. Можно показать, что количество различных полиномов Жегалкина, содержащих n переменных равно 2(2n) , т.е. числу всех различных n-местных булевых функций, следовательно, для каждой булевой функции существует единственный полином Жегалкина.

Пример. Найти полином Жегалкина для функции f = (11111000).

Решение. Применим метод неопределенных коэффициентов.

x1x2x3

k0=1

k1=x1

k2=x2

k3=x3

k4=x1 x2

k5=x1 x3

k6=x2 x3

k7=x1 x2 x3

f

000

1

0

0

0

0

0

0

0

1

001

1

0

0

1

0

0

0

0

1

010

1

0

1

0

0

0

0

0

1

011

1

0

1

1

0

0

1

0

1

100

1

1

0

0

0

0

0

0

1

101

1

1

0

1

0

1

0

0

0

110

1

1

1

0

1

1

0

0

0

111

1

1

1

1

1

1

1

1

0

Если , то получим систему уравнений

a0 = 1 a0 = 1

a0  a3 = 1 a3 = 0

a0  a2 = 1 a2 = 0

a0  a1 = 1 a6 = 0

a0  a2  a3  a6 = 1 a1 = 0

a0  a1  a3  a5 = 0 a5 = 1

a0  a1  a2  a4 = 0 a4 = 1

a0  a1  a2  a3  a4  a5  a6  a7 = 0 a7 = 1

Отсюда f = K0  K4  K5  K7 = 1  x1x2  x2x3  x1x2 x3.

Функция называется линейной, если ее полином Жегалкина имеет вид:

n

αixi, где αi и  – это число 0 или 1.

i=1

Так, любая булева функция от одной переменной является линейной.

Как показали ранее, отрицание, эквиваленция - линейные функции.

Минимизация булевых функций.

Сущность минимизации состоит в том, чтобы представить булеву функцию с помощью минимального количества операций дизъюнкции, конъюнкции и отрицания. Важность минимизации: при этом минимизируется количество оборудования с помощью которого реализуется булева функция.

Пусть  и  – булевы функции. Если =1, то говорят, что функция  имплицирует . Если при этом  является элементарной конъюнкцией, то  называют импликантом . В дизъюнктивной нормальной форме все элементарные конъюнкции - импликанты. Импликант называется простым, если удаление любой переменной из этого импликанта приводит к тому, что он перестает быть импликантом.

Пример. =(хz)( у z)(ху).

Покажем, что первый импликант хz является простым.

Решение. Удалим переменную х и получим z. Покажем, что функция z не имплицирует функцию .

z ; при z=1, х=0, у=0  =0, z – не является импликантом.

х ; при z=0, х=1, у=0  =0, первый импликант xz является простым.

Аналогично можно показать, что два остальных элемента конъюнкции также являются простыми импликантами. Рассмотрим, какие значения принимают элементарные конъюнкции функции =(хz)( у z)(ху)..

х

у

z

xz

y z

x y

0

0

0

0

0

0

0

0

1

0

0

0

0

1

0

0

1

0

0

1

1

0

0

0

1

0

0

0

0

0

1

0

1

1

0

0

1

1

0

0

1

1

1

1

1

1

0

1

Из таблицы видно, что конъюнкция ху обладает свойствами: в той строке, где есть 1, есть соседние конъюнкции, принимающие значения 1 (говорят, что элемент конъюнкции покрывается остальными элементарными конъюнкциями). Построенная таблица называется таблицей покрытия для функции . Если элементарная конъюнкция покрывается другой конъюнкцией, то ее можно исключить из дизъюнктивной формы, т.е. =(хz)( у z)

Минимизация булевых функций сводится к трем операциям:

1) для булевых функций строится СДНФ;

2) используя законы склеивания, получаем ДНФ, в которую входят только простые импликанты;

3) составляя таблицу покрытия, удаляем из ДНФ те импликанты, которые покрываются остальными импликантами. В некоторых случаях применение законов склеивания может быть облегчено с помощью матриц Карно.

х1  х1

х2

1

 х3

х3

х1х2 х3х4.

 х2

 х3

 х4 х4  х4

Матрица Карно составлена так, что для любой элементарной конъюнкции, которая содержит все четыре переменные, в этой матрице соответствует определенная клеточка. Если дана СДНФ, то каждой элементарной конъюнкции соответствует 1 в матрице Карно. Таких единичек столько, сколько элементарных конъюнкций в СДНФ. Пусть две единицы в матрице Карно, значит в СДНФ входят две элементарные конъюнкции

х1  х1

х2

1

1

 х3

х1х2 х3х4 х1х2 х3х4= х2 х3х4

х3

 х2

 х3

 х4 х4  х4

Рассмотрим три единички:

х1  х1

х2

 х3

х1х2 х3х4 х1х2 х3х4

х3

 х1х2 х3х4=х2 х3х4х1х2 х3

 х2

1

1

1

 х3

 х4 х4  х4

Рассмотрим четыре единицы:

х1  х1

х2

 х3

х1х3х4 х1х3х4= х3х4

1

1

х3

 х2

1

1

 х3

 х4 х4  х4

х1  х1

х2

 х3

х3

х1х2 х3х1х2х3=х2х3

 х2

1

1

1

1

 х3

 х4 х4  х4

Упражнение

Привести к виду полинома Жегалкина h = xy  xz  yz.