Булевы функции: полнота и базис системы

[Sverest]

Является ли полной система функций $\{x \vee y, \overline{x} \oplus y\}$
Образует ли она базис?

С чего надо начинать?

[caxap]

Обе функции сохраняют единицу.

[cyb12]

Если взять класс $T_0$ функций, сохраняющих нуль, то любая функция в нем представима полиномом, в котором свободный член равен 0. Поэтому базис класса $T_0$ есть $\{xy, x\oplus y\}.$ А теперь можно заметить, что класс $T_1$ состоит из двойственных (к функциям из $T_0$) функций и воспользоваться принципом двойственности.

[caxap]

cyb12
Зачем так сложно?

[Legioner93]

Sverest, это задача на критерий Поста. Исходя из формулировки, нужно проверить принадлежность функций к 5 классам. Если обе функции лежат хотя бы в одном из этих пяти классов, то система не является полной.

[Sverest]

caxap в сообщении #452755 писал(а):

Обе функции сохраняют единицу.

то есть надо просто подставить единицу?

-- Чт июн 02, 2011 10:32:12 --

caxap в сообщении #452755 писал(а):

Обе функции сохраняют единицу.

то есть надо просто подставить единицу?

[caxap]

Sverest в сообщении #452888 писал(а):

то есть надо просто подставить единицу?

Надо проверить моё высказывание из 2-го сообщения. И из этого сделать вывод, что не все функции можно получить из данных функций, а значит это не полная система.

(Оффтоп)

Legioner93 в сообщении #452869 писал(а):

это задача на критерий Поста.

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

[Sverest]

$1 \vee 1=1; 1 \vee 0=1; 0 \vee 1=1; 0 \vee 0 =0$ единицу сохраняет

$\overline{1} \oplus 1=1; \overline{0} \oplus 1= 0; \overline{1} \oplus {0}=0; \overline{0} \oplus 0=1$ единицу не сохраняет

так?

[Joker_vD]

Извините, а как вы ухитрились из $f(1)=1$ сделать вывод "$f$ сохраняет единицу", а из $g(1)=1$ сделать "$g$ не сохраняет единицу"?

[Sverest]

Joker_vD в сообщении #452954 писал(а):

Извините, а как вы ухитрились из $f(1)=1$ сделать вывод "$f$ сохраняет единицу", а из $g(1)=1$ сделать "$g$ не сохраняет единицу"?

я подставил единицу, а получил ноль, вывод единица не сохранилась

[Joker_vD]

Sverest в сообщении #452964 писал(а):

я подставил единицу, а получил ноль

Это вы про $\overline 1 \oplus 1 = 1$? Подставленную единицу я вижу, а где ноль?

[Sverest]

Joker_vD в сообщении #452967 писал(а):

Sverest в сообщении #452964 писал(а):

я подставил единицу, а получил ноль

Это вы про $\overline 1 \oplus 1 = 1$? Подставленную единицу я вижу, а где ноль?

Я про $ \overline{1} \oplus {0}=0$

-- Чт июн 02, 2011 13:30:58 --

Или надо было, чтоб в и там и там еденица была

[caxap]

Sverest в сообщении #452970 писал(а):

Или надо было, чтоб в и там и там еденица была

Конечно. Повторяю свой совет.

[Joker_vD]

Говорят, что булева функция $f(x,y)$ сохраняет единицу, если $f(1,1)=1$. Берем функцию $f(x,y) = \overline x \oplus y$. $f(1,1) = \overline 1 \oplus 1 = 1$. Вывод?

[Sverest]

значит функции сохраняют единицу, какой следующий шаг. В методичке, про это не очень понятно написано