Основы булевой алгебры

В XIX веке английский математик Джордж Буль разработал основные положения алгебры логики, которую называют булевой алгеброй. Только в XX веке соответствующий уровень развития промышленности привел к тому, что этот раздел математики оказался востребованным. Его удобно использовать для описания законов работы цифровых дискретных устройств.

Булевой переменной х называется переменная, которая может принимать только одно из двух значений: 0 или 1. Этот факт закреплен в аксиоме

т. е. никаких других значений переменная принимать не может.

Булеву переменную называют двоичной, или логической, переменной. Операции над этими переменными называют логическими. Определим следующие операции над булевыми переменными:

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

и подчиняется следующим правилам (табл. 1.1):

Таблица 1.1

Таблица истинности операции логического произведения

X1	X2	X1&X2

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

и подчиняется следующим правилам (табл. 1.2):

Таблица 1.2

Таблица истинности операции логического сложения

Y1	Y2	Y1+Y2

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

и подчиняется следующим правилам (табл. 1.3):

Таблица 1.3

Таблица истинности операции логического отрицания

А	Ā

Булевы переменные подчиняются следующим аксиомам:

0&0=0, 0&1=0, 0+0=0, 1+1=1, 0+1=1, 1&1=1,

причем они справедливы и для произвольного числа переменных:

0&0&0&…&0=0, 1+1+1+…+1=1.

Для операции инверсии справедливы следующее отношения:

,

т. е. четное число инверсий дает саму переменную, а нечетное – инверсную.

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

1) переместительный для дизъюнкции x₁+x₂=x₂+x₁,

для конъюнкции x₁x₂=x₂x₁;

2) сочетательный для дизъюнкции x₁+(x₂+x₃)=(x₁+x₂)+x₃,

для конъюнкции x₁(x₂x₃)=(x₁x₂)x₃;

3) распределительный для дизъюнкции x₁+x₂x₃=(x₁+x₂)(x₁+x₃),

для конъюнкции x₁(x₂+x₃)=x₁x₂+x₁x₃.

Из аксиом и законов алгебры логики следует ряд важных теорем, свойств и правил, которые полезны при выполнении эквивалентных преобразований:

1) x+x+x+…+x = x,

x x x…x = x;

2) x+1=1

(для произвольного числа булевых переменных 1+x+y+z+…+p=1);

3) 0&х=0

(для произвольного числа булевых переменных 0&x&y&z&…&p=0);

4)

5) законы склеивания

6) законы поглощения

7) теоремы де Моргана

Здесь надо уяснить, что все вышеизложенные положения действуют для любого количества переменных. Например: