Дискретная математика. Задача по теме "Булевы функции&q

[Alekseeff]

Докажите независимость системы \{\vee, \wedge, 0, 1\}

[cepesh]

А на каком этапе у Вас возникают проблемы? Определение независимости системы знаете? Напишите его.

[Alekseeff]

Я не знаю как доказать, что \vee\notin[\{\wedge,0,1\}]\mbox{ и }\wedge\notin[\{\vee,0,1\}]

[Alekseeff]

Неужели никто не знает?

[juna]

Не совсем понятны Ваши затруднения. Все очень просто, доказывайте, что ни одна функция из Вашей системы не выражается через остальные.
1.система {И, Или, 1} не позволяет реализовать невыполнимую формулу (равную нулю при любых значениях аргумента);
2.система {И, Или, 0} не позволяет реализовать тавтологию;
3.если система {И, 0,1} реализует дизъюнкцию, то только так x1 И x2 И 1 И 0 И x1.., но этот конъюнкт в лучшем случае это x1 И x2, в худшем 0. ч.т.д.

[Alekseeff]

Артамонов Ю.Н., спасибо, а можно как-нибудь доказать этот факт, используя определение базиса замкнутого класса: M \mbox{ -- базис замкнутого класса } N \iff M\mbox{ независима и }[M]=N
Почему в Вашем доказательстве не рассмотрена система \{\vee,0,1\}

[juna]

Там все аналогично п.3, что следует из двойственности.