Задача на полноту системы функций

[mastedm]

Задача.
Выяснить полноту системы функций

$$ f = !x_1 \lor x_2 \lor x_3 , \quad w = !x_1x_2!x_3 \lor !x_2x_3 \lor x_1x_3 $$

Если система не полна, то дополнить её ф-цией $g$ до полной. (Запрещается дополнять системы константами и базовыми функциями, а также ф-цией, образующей полную систему с одной из ф-ций f или w)

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

$$ f(x,x,x) = 1, \quad f(1,x_2,x_3) = x_2 \lor x_3 $$

Для полного счастья осталось только получить отрицание. Понятно, что нужно заюзать w. Вот что я получил из w:

$$ w(x_1, x_2, x_3) = (!x_1x_2)!x_3 \lor !(!x_1x_2)x_3 $$

На этом стопор. Может кто поможет.

[Профессор Снэйп]

Ну конечно отрицание не выражается.

Заметьте, что для любой функции $u(x_1, \ldots, x_k)$, которую можно выразить через $f$ и $w$, справедливо $u(1, \ldots, 1) = 1$. Действительно, $f$ и $w$ этим свойством обладают. Ну а если какие-то функции $u_1, u_2, u_3$ обладают этим свойством, то функции $f(u_1,u_2,u_3)$ и $w(u_1,u_2,u_3)$ тоже обладают им. Отрицание же данным свойством не обладает.

[mastedm]

Тогда нужно вводить новую функцию, которая бы дополнила эту систему до полной. У меня была идея в качестве оной взять $g(x_1,x_2)=!x_1x_2$, но она вместе с f уже образует полную систему, т.е. w остаётся не при чём. По заданию запрещается дополнять ф-цией, образующей с f или w полную подсистему, кроме случаев, когда иное невозможно. Вот эта приписка "иное невозможно" меня смущает: что же я сначала должен показать, что иное невозможно?

[Профессор Снэйп]

mastedm писал(а):

Вот эта приписка "иное невозможно" меня смущает: что же я сначала должен показать, что иное невозможно?

О какой приписке идёт речь? Я в Вашем первом сообщении этого сочетания слов нигде не заметил.

А, всё, заметил. Имелась в виду фраза из второго сообщения "кроме случаев, когда иное невозможно".

А Вы таблички истинности (aka таблицы значений) для функций $f$ и $w$ порисовать не пробовали? Иногда при взгляде на них многое становится понятно.

[mastedm]

Таблички перед глазами. Собственно через них и функции задавались:

          f  w
0 0 0  1 0
0 0 1  1 1
0 1 0  1 1
0 1 1  1 0
1 0 0  0 0
1 0 1  1 1
1 1 0  1 0
1 1 1  1 1

[Профессор Снэйп]

Н-да... И после некоторого среднепродолжительного размышления становится ясно, что "иное действительно невозможно"!!!

Если мы дополняем систему $\{ f, w \}$ какой-то функцией $g(x_1,\ldots, x_k)$, то должно выполняться равенство $g(1,\ldots,1)=0$ (иначе система $\{ f,w,g \}$ не будет полна по тем же соображениям, что и ранее). Теперь берём систему $\{ f,g \}$. Единицу мы при помощи $f$ выражать умеем, значит, при помощи $f$ и $g$ можем выразить ноль. Однако $f(x,0,0) = !x$ и $f(1,x,y) = x \vee y$. То есть при помощи $f$ и $g$ мы можем выразить как дизъюнкцию, так и отрицание. Вывод: система $\{ f,g \}$ полна.