Из полной системы функций A выделить всевозможные базисы. (Дискретная математика) A = {x ↔ y, (x → y) | z, 1, xy ⊕ (x ↓ y), x ∨ (y ⊕ (z → x)), xy ⊕ z}

Предыдущий
вопрос Следующий
вопрос

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

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

В данной системе функций A имеется следующий набор функций:

x ↔ y (эквивалентность)x → y (импликация)z (переменная)1 (истина)xy ⊕ (x ↓ y) (исключающее ИЛИ)x ∨ (y ⊕ (z → x)) (дизъюнкция)xy ⊕ z (исключающее ИЛИ)

Теперь проверим, можно ли выразить базовые логические операции из данного набора функций:

Конъюнкция (xy) можно выразить, представив исключающее ИЛИ данной системы (xy ⊕ (x ↓ y)) и отрицание (1 → (xy ⊕ (x ↓ y)))Дизъюнкция (x ∨ y) можно выразить из данной системыОтрицание (¬x) можно выразить из данной системы, представив d как xy ⊕ 1

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

Поэтому все функции из данного набора A могут быть использованы в качестве базиса.