1.3. Булева алгебра

Определение. Булева алгебра – алгебра с произвольным множеством элемен-тов M, сигнатура которой содержит две бинарные операции < & >, < >, одну унарную операцию < – > и две нульарных операции – константы 0 и 1 и для любых x, y, z M в ней справедливы следующие законы ( аксиомы ):

1. Ассоциативность: а) х & ( y & z) = ( x & y ) & z, b) x ( y z ) = ( x y ) z.

2. Коммутативность: а) x y = y x₁, b) x & y = y & x.

3. Идемпотентность: а) x & x = x, b) x x = x.

4. Поглощение: a) x ( x y ) = x, b) x ( x & y ) = x.

5. Дистрибутивность конъюнкции относительно дизъюнкции:

a) x & ( y z ) = x & y x & z, b) x ( y & z ) = ( x y ) & ( x z ).

6. Свойство констант: a) x & 1 = x, b) x & 0 = 0, c) x 1 = 1, d) x 0 = x

7. Дополнение: a) x & = 0, b) x = 1.

8. Законы де Моргана: a) = , b) = & .

9. Инволютивность: = x

В дальнейшем, под операциями «&», « »и «–» мы будем понимать операции конъюнкцию, дизъюнкцию и отрицание, соответственно, а под множеством M – множество всех логических функций и логических переменных.

Все эти свойства можно легко проверить. Например, для проверки правила де Моргана составим следующую таблицу.

Таблица 1.13

Из данной таблицы видно, что столбцы 6 и 7 равны, что подтверждает спра-ведливость закона 8а). Равенство столбцов 9 и 10 подтверждает справедливость закона 8 в).

Справедливость закона 4а) x xy = x и 4b) x ( x y ) = x,

можно доказать следующим образом:

x xy = x∙1 xy = x ( 1 y ) = x∙1 = x;

x ( x y ) = x x x y = x x y = x.

Формула в булевой алгебре называется булевой формулой.

Замечания:

1. С целью упрощения записи формул принимается, что операция & сильнее операции , т.е. если нет скобок, то сначала выполняется &.

Например, запись

x & y z означает ( x & y ) z.

2. В силу закона ассоциативности можно вместо формулы ( x y ) z писать эквивалентное выражение x y z, которое не является формулой, но может быть превращено в нее путем расстановки скобок, причем функциональные свойства не меняются, как бы мы ни расставляли скобки.

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

Если в логическом произведении один из множителей равен 0, то и логическое произведение равно 0. Например, x ( y · ) z = 0.

Если в логическом произведении, содержащем не менее двух множителей, имеется множитель, равный 1, то этот множитель можно зачеркнуть. Например,

x ( y ) z = x z.

Если в логической сумме, содержащей не менее двух слагаемых, имеется слагаемое, равное 0, то это слагаемое можно зачеркнуть. Например,

x ( y ) z = x z.

Если в логической сумме одно из слагаемых равно 1, то и логическая сумма равна 1. Например, x ( y ) z = 1.

В дальнейшем, согласно замечаниям 1 и 2, мы будем употреблять не формулы, а выражения, отличающиеся от формул тем, что в них кое-где опущены скобки. Эти выражения мы также будем называть формулами.

Перечисленные свойства булевых операций можно использовать в любых формулах алгебры логики. Это делается по следующему правилу замены: если в формуле вместо x подставляем f, то эту замену нужно сделать для всех x и дан-

ной формулы.

Например, закон дополнения при данной замене будет записан так:

f = 1.

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

Рассмотрим некоторые эквивалентные соотношения, применяемые в эквивалентных преобразованиях для упрощения булевых формул т.е. для получения эквивалентных формул, содержащих меньше символов. Для упрощения записи вместо x & y будем использовать эквивалентную запись x y.

1. Склеивание: x y x = x.

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

2. Обобщенное склеивание: x z y x y = x z y .

Справедливость этого соотношения можно доказать табличным способом.

.

3. x y = x y.

Доказательство: заменим x на x x y. Тогда:

x x y y = x y ( x ) = = x y.

4. x₁ f( x₁, x₂, … , x_n ) = x₁ f( 0, x₂, … , x_n ).

Пример. Показать справедливость соотношения 4 для функции

f( x ,x ,x ) = x x x x .

Левуя часть равенства 4 для данной функции будет иметь вид

x ( x x x x ) = x x x .

Правая часть равенства 4 для данной функции будет иметь вид

x ( 0 x x x ) = x x x .

Полученые выражения для правой и левой частей соотношения 4 совпадают.

Приведем примеры эквивалентных преобразований булевых формул.

В следующем примере используются законы 2, 3, 5 и 7.

Пример. ( x y) ( x z ) = x x y x x z y z = x x y x z y z =

= x ·1 x y x z y z = x ( 1 y ) x z y z = x x z y z =

= x ( 1 z ) y z = x y z.

Пример. xy ( y x z ) =

= y ( y x z )( ( ) ) = x y y ( )( ) =

= x y y ( y )( ) = x y y ( y ) = = x y y ( y ) = x y y y y y =

= x y y y = x y y = y ( x ) = y ( x )( x ) =

= y ( x ) = y z y .

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

Пример. ( y z )( x ) =

= x y x y y z x z z =

= x y y x z z = ( y ) x y x z z =

= y x y x z z = ( z x z ) y x y =

= z x y x y = ( z x y x y ) = z x y =

= y x z.