Законы и следствия булевой алгебры

Законы булевой алгебры.

Для удобства разобьем законы на четыре группы.

Первая группа.

1.   (закон коммутативности для дизъюнкции).

2.

3.   (первый закон поглощения).

4.   (второй закон дистрибутивности).

5.  (закон идемпотентности для дизъюнкции).

Следующие пять законов получаются заменой наи наоборот.

1.  (закон коммутативности для конъюнкции).

2 .(закон ассоциативности для конъюнкции).

3 .(второй закон поглощения).

4 .(первый закон дистрибутивности)

5.  (закон идемпотентности для конъюнкции).

Каждый из законов 1- 5называется двойственным к соответствующему закону 1 – 5.

Вторая группа

1.

2

3.

4.

5.

6.

Третья группа

1.   (закон двойного отрицания).

2.

3.

Четвертая группа

1.

2.  (закон контрапозиции).

3.

Следствия

Сформулируем некоторые полезные следствия из приведенных законов.

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

С2. Если в дизъюнкции хотя бы один из элементов равен 1, то вся дизъюнкция равна 1.

С3. Выбрасывая из произвольной конъюнкции все сомножители равные 1, мы не изменим ее величины.

С4. Если в конъюнкции хотя бы один сомножитель равен 0, то все произведение равно 0.

С5. Дизъюнкция или произведение любого числа одинаковых элементов равняется А.

Эти следствия можно доказать по индукции.

С6. Если А(а1,..., ап) произвольное выражение булевой алгебры, построенное из выражений а1,..., ап с помощью операций отрицания, дизъюнкции и конъюнкции, то отрицание этого выражения равняется, где В(а1,…,ап) получается из А с помощью замены всех умножений на дизъюнкции, а всех дизъюнкций на умножения, при условии сохранения всех имевшихся в А отрицаний.

С7. Если к некоторому выражению А булевой алгебры применено более чем одно отрицание, то, не меняя значения выражения, можно исключить любое четное число отрицаний.

№ 14 Основы технического обеспечения информационных технологий.