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

Упрощение формул в булевой алгебре (как и в любой другой алгебре) производится на основе эквивалентных преобразований, опирающихся на основные законы (эквивалентные соотношения), которые в каждой алгебре - свои.

1. Ассоциативность дизъюнкции и конъюнкции:

х₁ Ú (х ₂ Ú х₃) = (х₁ Ú х ₂) Ú х₃ = х₁ Ú х ₂ Ú х₃

х₁ Ù (х ₂ Ù х₃) = (х₁ Ù х ₂) Ù х₃ = х₁ Ù х ₂ Ù х₃

2. Коммутативность дизъюнкции и конъюнкции:

х ₁ Ú х ₂ = х ₁ Ú х ₂; х ₁ Ù х ₂ = х ₂ Ù х ₁

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

х₁ Ù (х ₂ Ú х₃) = (х₁ Ù х ₂) Ú (х ₁ Ù х₃)

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

х₁ Ú (х ₂ Ù х₃) = (х₁ Ú х ₂) Ù (х₁ Ú х₃)

5. Идемпотентность (отсутствие степеней и коэффициентов):

х Ù х = х; х Ú х = х

6. Закон двойного отрицания:

ù ù х = х

7. Свойства констант 0 и 1:

х Ù 1 = х; х Ù 0 = 0

х Ú 1 = 1; х Ú 0 = х

ù 0 = 1; ù 1 = 0

8. Правило де Моргана:

ù (х₁ Ù х ₂) = ù х₁ Ú ù х ₂

ù (х₁ Ú х ₂) = ù х₁ Ù ù х ₂

9. Закон противоречия:

х Ù ù х = 0

10. Закон исключения третьего:

х Ú ù х = 1

Кроме того, часто используются формулы, позволяющие перейти от импликации и эквивалентности к формулам булевой алгебры:

х «у = (х ® у) Ù (у ® х)

(у ® х) = ù х Ú у;

х «у = (х Ù у) Ú (ù х Ù у)

Пример 2. Доказать равносильность ù (х → y) ≡ x & ù у.

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

ù (х → y) ≡ ù (ù х Ú y) ≡ ù ù x & ù y ≡ х & ù у.

Пример 3. Упростить формулу А = (ù (х Ú у) → ù х Ú y)) & у.

Решение. Подвергнем формулу А равносильным преобразованиям:

A ≡ (ù (х Ú у) → ù х Ú y)) & у ≡ (ù ù (х Ú у)Ú ù х Ú y)) & у ≡ (х Ú у Ú ù х Ú y) & у ≡ ((х Ú ù х) Ú (у Ú y)) & у ≡ (1Ú y) & y ≡ 1 & y ≡ y.

Пример 4. Доказать, что формула А ≡ х → (у → х)тождественно истинная.

Решение. Подвергнем формулу А равносильным преобразованиям

А ≡ х → (у → х) ≡ ù х Ú(ù у Ú х) ≡ (ù х Ú х)Ú ù у ≡ 1 Ú ù y ≡ 1.

Под релейно-контактной схемой мы понимаем устройство из проводников и двухпозиционных контактов, через которые полюсы источника тока связаны с некоторым потребителем. Контакты могут быть замыкающими и размыкающими. Каждый контакт подключен к некоторому реле (переключателю). Когда реле срабатывает (находится под током), все подключенные к нему замыкающие контакты замкнуты, а размыкающие контакты разомкнуты; в противном случае наоборот. Каждому реле ставится в соответствие своя булева переменная х, которая принимает значение 1, если реле срабатывает, и 0 в противном случае.

На чертежах обозначается: х – замыкающий контакт; ù х – размыкающий контакт; Ù - последовательное соединение; Ú - параллельное соединение.

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

Пример 8. Постройте релейно-контактную схему с заданной функцией проводимости:

(х ® (у ® ù z)) Ú ((x Ù y) «z).

Решение. Выразим сначала данную функцию через функции булевой алгебры: ù (инверсия – отрицание), Ú (дизъюнкция), Ù (конъюнкция), причем так, чтобы знак ù стоял бы лишь перед переменными:

(х ® (у ® ù z)) Ú ((x Ù y) «z) = (ù х Ú (y ® ù z)) Ú ((ù (x Ù y) Ú z)) Ù

Ù ((x Ù y) Ú ù z) = ù x Ú ù y Ú ù z Ú [(ù x Ú ù y Ú ù z) Ù ((x Ù y) Ú ù z)].