Алгебра Жегалкина. Основные свойства операций алгебры Жегалкина.



Мы поможем в написании ваших работ!


Мы поможем в написании ваших работ!



Мы поможем в написании ваших работ!


ЗНАЕТЕ ЛИ ВЫ?

Алгебра Жегалкина. Основные свойства операций алгебры Жегалкина.



Определение. Алгеброй Жегалкина называется алгебра над множеством логических функций и переменных, сигнатура которой содержит две бинарные операции & и , и две нульарные операции – константы 0 и 1.

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

1. x y = y x;

2. x ( y z ) = x y x z;

3. x x = 0;

4. x = 1;

5. x 0 = x.

Эти соотношения легко проверить табличным способом. Кроме перечисленных соотношений в алгебре Жегалкина выполняются соотношения булевой алгебры относительно конъюнкции и констант.

Функцию Шеффера, функцию стрелка Пирса и можно представить следующими эквивалентными формулами:

х1 / x2 = = , x1 “ x2 = & =

 

Найдем выражения для основных элементарных функций алгебры логики в алгебре Жегалкина.

1. = x 1.

Это соотношение проверяется непосредственной подстановкой 0 и 1 в обе части равенства.

2. x y = x y x y.

Доказательство: x y = = 1 = ( x 1 )( y 1 ) 1 =

= x y x y 1 1 = x y x y.

3. x ’ y = x y x 1.

Доказательство: Используем выражение для импликсации в . Тогда:

x ’ y = y = y y = ( x 1 ) y ( x 1 ) y =

= x y y x 1 y = x y x 1.

4. x / y = x y 1.

Доказательство: Используем выражение для x / y. Тогда:

x / y = = xy 1.

5. x “ y = x y x y 1.

Доказательство: Используем выражение для x “ y. Тогда:

x “ y = = ( x 1 )( y 1) = x y x y 1.

6. x ~ y = 1 x y.

Доказательство: Легко проверить, что x ~ y = x y . Тогда :

x ~ y = x y ( x 1 )( y 1 ) = x y x y x y 1 = 1 x y.


29. Алгебра Жегалкина. Представление логических функций полиномом Жегалкина.

 

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

a x x … x , ( 1 d k d n )

причем в каждом наборе ( i , , i ) все i различны, а суммирование по mod 2 ведется по некоторому множеству таких не совпадающих наборов.

Например, 1 x x x , x x x x x x - некоторые полиномы Жегалкина для двух и трех переменных соответственно.

От формулы алгебры логики всегда можно перейти к формуле алгебры Жегалкина. Для этого нужно заменить основные элементарные функции алгебры логики на соответствующие эквивалентные выражения алгебры Жегалкина (1) - (5), представленные выше.

В полученной формуле нужно раскрыть скобки и произвести упрощения, используя соотношения (1.4), а также следующие соотношения: x & x = x и x·1 = x. Полученное выражение и будет полиномом Жегалкина для данной формулы.

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

Полученное выражение и есть полином Жегалкина.

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

f1 f2 = f1 f2, (1.5)

справедливое при f1f2 = 0. Используем соотношение (1.5) для нахождения полинома Жегалкина в следующих примерах.

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

Сделаем следующие преобразования:

f( x,y ) = x y = x y = x y ( x 1 )( y 1 ) =

= x y x y x y 1 = 1 x y - полиномом Жегалкина.

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

Сделаем следующие преобразования:

f( x,y ) = x z = x z = x ( y 1 ) ( x 1 ) z =

= x y x x z z = x z x y x z. - полиномом Жегалкина.

Теорема. Для любой логической функции существует полином Жегалкина и притом единственный.

Доказательство: Существование полинома доказано вышеприведенным алгоритмом получения полинома из логической формулы. Для доказательства единственности надо показать, что между множеством всех логических функций от n переменных и множеством всех полиномов Жегалкина от n переменных существует взаимно однозначное соответствие.

Полином Жегалкина можно найти методом неопределенных коэффициентов. Рассмотрим этот метод на следующим примере.

Пример. Найти полином Жегалкина для функции заданной векторно:

f( x,y ) = ( 0, 1, 1, 0 ).

Составим таблицу 1.14 задания данной функции.

Таблица 1.14

x y f

Полином Жегалкина для функции двух переменных ищем в следующем виде:

f( x, y ) = a0 a1·x a2·y a3·xy (1.6)

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

Подставляя набор переменных(0,0) в (1.6) получим:

. a = 0.

Аналогично для набора (0,1) получим: . a = 1.

Для набора (1,0) получим: a = 1.

Для набора (1,1) получим: a = 0.

Подставляя в (1.6) найденные значения коэффициентов получим искомый полином для данной функции:

f( x, y ) = x y.

Замечание. Можно показать, что переменная x будет фиктивной для некоторой функции тогда и только тогда, когда полином Жегалкина для нее не содержит переменной x

 


 



Последнее изменение этой страницы: 2016-08-14; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 44.192.112.123 (0.011 с.)