3.03 Булева алгебра

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

На основании определения основных операций нетрудно убедиться в справедливости следующих свойств булевой алгебры:

· коммутативность (перестановочный)

ХУ = УХ; ХУ = УХ;

· ассоциативность (сочетательный)

Х (УZ) = (ХУ) Z;

· дистрибутивность (распределительный)

Х (УZ) = (ХУ) (ХZ);

· свойство констант

Х0 = Х;

Х 1 = Х;

· свойство отрицания

Х = 1; Х = 0.

Приведенные свойства позволяют получить ряд важных законов и тождеств.

1. Законы де Моргана

= ; = .

2. Законы поглощения

Х(Х У) = Х; Х (Х У) = Х.

Доказательство:

Х(ХУ) = (Х1) (ХУ) = (дистрибутивный) = Х(1У) = Х1 = Х;

Х(ХУ) = (Х0) (ХУ) = (дистрибутивный) = Х(0У) = Х0 = Х.

3. Законы идемпотентности

ХХ = х; х х = х.

Доказательство:

ХХ = (хХ)1 = (хХ)(х) = (дистрибутивность) =
= х(х) = (х0) = х;

ХХ = (хХ)0 = (хХ) (х) = (дистрибутивность) =
= х(х) = (х1) = х.

4. Х( У) = Х У.

5. (Х У) (Х Z) (Y ) = (Х Z) (Y ).

6. = C.

7. Х 1 = 1; Х 0 = 0.

< Предыдущая		Следующая >