Эквивалентные преобразования формул

Из § 3.2: Свойства логических операций ∨, &, ¬ («Исходные соотношения»)

2) Полезные соотношения для булевских формул

Доказательство - на примере (3.3.1а)

* Порядок замены – возможны варианты

Удалили повторяющиеся подформулы и переменные

Завершили преобразования

4) Анализ схем из двухпозиционных переключательных элементов
x
y
x & y
x
y
x ∨ y

((x & y) ∨ ¬x ∨ (x & ¬y)) & ( (¬x & y) ∨ ¬x) & x =
= (¬x ∨ y ∨ (x & ¬y)) & (¬x & x) =
= (¬x ∨ y ∨ x) & (¬x & x) =
= 1 & (¬x & x) = ¬x & x = 0

¬x & ((¬x & ¬y) ∨ (x & ¬y) ∨ ¬x) & y =
= ¬x & ((¬x & ¬y) ∨ ¬x ∨ ¬y) & y =
= ¬x & (¬x ∨ ¬y) & y =
= (¬x & (¬x & y)) ∨ (¬x & ¬y & y) =
= (¬x & y) ∨ 0 = ¬x & y

Интересный другой вариант той же задачи:
Составить схему, позволяющую включать и выключать свет в вашей комнате любым из трёх различных выключателей. Выключатели расположены у входа в комнату, над постелью и у письменного стола
(Медведева Я.С. Применение булевых функций к релейно-контактным схемам // Молодой учёный. — 2016. — № 3. — С. 8-11)

Отправная точка: 000 – свет в подъезде выключен

¬x1
¬x1
x1
x1
¬x2
¬x2
x2
x2
¬x3
¬x3
x3
x3
⊗
⊗
⊗
1 этаж
2 этаж
3 этаж

Задача

(Было 24, осталось 16 неизвестных)

Контрольная работа: 18 - 23 декабря
Подведение итогов: 25 - 30 декабря

x
x
x
¬x
¬x
¬x
¬x
¬x
¬x
x
y
y
y
¬y
¬y
¬y

Можно видеть, что формулы A и B представляют одну и ту же функцию ψ15(x, y) – константу 1, то есть формулы эквивалентны.

Можно видеть, что формула A представляет функцию η31(x, y, z), а формула B - функцию η127(x, y, z), то есть формулы не эквивалентны.

2a) ((x ≡ y) │ x) ⇒ y =
= (((x ∨ ¬y) & (¬x ∨ y))│ x) ⇒ y =
= (¬((x ∨ ¬y) & (¬x ∨ y)) ∨ ¬x) ⇒ y =
= ¬(¬((x ∨ ¬y) & (¬x ∨ y)) ∨ ¬x) ∨ y =
= ¬(¬(x ∨ ¬y) ∨ ¬ (¬x ∨ y) ∨ ¬x) ∨ y =
= (¬¬(x ∨ ¬y) & ¬¬ (¬x ∨ y) & ¬¬x) ∨ y =
= ((x ∨ ¬y) & (¬x ∨ y) & x) ∨ y =
= (((x&¬x) ∨ (x&y) ∨ (¬x&¬y) ∨ (y&¬y)) & x) ∨ y =
= (x&x&¬x) ∨ (x&x&y) ∨ (x&¬x&¬y) ∨ (x&y&¬y) ∨ y =
= 0 ∨ (x&y) ∨ 0 ∨ 0 ∨ y =
= (x&y) ∨ y =
= y

2b) ((x ∨ ¬y) & (z ∨ ¬x)) ∨ ((y ∨ z) & (x ∨ y ∨ ¬z)) =
= ((x & z) ∨ (x & ¬x)∨ (¬y & z) ∨ (¬x & ¬y)) ∨
∨ ((x & y) ∨ (y & y) ∨ (y & ¬z) ∨ (x & z) ∨ (y & z) ∨ (z & ¬z)) =
= ((x&z) ∨ 0 ∨ (¬y&z) ∨ (¬x&¬y)) ∨ ((x&y) ∨ y ∨ (y&¬z) ∨ (x&z) ∨ (y&z) ∨ 0) =
= (x&z) ∨ (¬y&z) ∨ (¬x&¬y) ∨ (x&y) ∨ y ∨ (y&¬z) ∨ (x&z) ∨ (y&z) =
= (x&z) ∨ (¬y&z) ∨ (¬x&¬y) ∨ (x&y) ∨ y ∨ (x&z) ∨ (y&z) =
= (x&z) ∨ (¬y&z) ∨ (¬x&¬y) ∨ y ∨ (x&z) ∨ (y&z) =
= (x&z) ∨ (¬y&z) ∨ (¬x&¬y ∨ y) ∨ (x&z) =
= (x&z) ∨ (¬y&z) ∨ ¬x ∨ y ∨ (x&z) =
= (x&z) ∨ z ∨ ¬x ∨ y ∨ (x&z) =
= z ∨ ¬x ∨ y ∨ (x&z) =
= ¬x ∨ y ∨ z