БАЗИС БУЛЯ

Инф 💻

Честно. Понятно. С душой.

👨‍💻 Буль — по имени первого исследователя математической Джорджа Буля.

			~ Базис Буля — это набор операций, который позволяет выразить любую другую операцию через них.		

В базисе всего 3 операции: {∧, v, ¬} — И, ИЛИ, НЕ.

Например:
Импликация — логическое “если — то» или следствие.
Обозначается : x —> y и имеет следующую таблицу истинности:

X Y F
0 0 1
0 1 1
1 0 0
1 1 1

Импликация ложна(=0), когда Х = 1, а Y = 0 (в реальной жизни эта операция заменяет логическую связку, когда невозможно, чтобы при наличии условия не произошло следствие).

Выразим это с помощью Базиса Буля:
X —> Y = ¬X v Y

Это можно доказать, если построить таблицы истинности для левой и правой части.

🙆‍♀️ Правда, остается тонкость связанная с порядком операций, смотри картинку.
~ Например:
перевести в Базис Буля выражение: X ∧ Z —> Y

что делать с X ∧ Z: брать общее отрицание или только Z?

Зная приоритет операций, мы понимаем, что импликация будет выполняться после конъюнкции:
X ∧ Z —> Y = ¬(X ∧ Z) v Y = (по закону Де Моргана) = ¬X v ¬Z v Y