Можно ли выразить конъюнкцию через импликацию?

[kernel1983]

Известно, что дизъюнкцию и единицу можно выразить через импликацию: $x \vee y= (x \to y) \to y$, $1=x \to x$. А можно ли выразить конъюнкцию через импликацию? Предположу, что нет. Система, состоящая из одной импликации, не полна. Значит, есть функции, которые нельзя выразить через импликацию. Но как доказать?

[3D Homer]

Рассмотрите класс $\{f(x_1,\ldots,x_n)\mid\exists i\,\forall x_1,\ldots,x_n\;f(x_1,\ldots,x_n)\ge x_i\}$ и докажите, что он замкнут.

[iifat]

Как вариант: вы знаете, что

kernel1983 в сообщении #1385835 писал(а):

Система, состоящая из одной импликации, не полна

Вы знаете, что система из дизъюнкции, конъюнкции и единицы полна. Отсюда всё уже следует.

[kernel1983]

iifat в сообщении #1385844 писал(а):

Отсюда всё уже следует.

Я не пойму, как отсюда следует, что конъюнкцию нельзя выразить через импликацию.

[3D Homer]

iifat писал(а):

Вы знаете, что система из дизъюнкции, конъюнкции и единицы полна. Отсюда всё уже следует.

Эта система неполна, и отсюда не следует, что конъюнкцию нельзя выразить через импликацию.

[iifat]

3D Homer в сообщении #1385847 писал(а):

Эта система неполна

Тьфу, ёлки. Про отрицание-то я и забыл.

[bot]

Рассмотрим алгебру $<f, t, \to>$. Значение $f$ (ложь) достигается не более чем на одном из 4-х наборов переменных. По индукции это же верно и для термов от двух переменных. Конъюнкция этим свойством не обладает.

[3D Homer]

Из импликации можно построить функцию от $x,y$, которая будет равна $x$, то есть аргумент $y$ будет фиктивным: $(x\to y)\to x$. Эта функция принимает значение Истина на половине всех наборов аргументов. Но аналогичное утверждение, что суперпозиция импликации принимает Истину не менее, чем на половине наборов, является верным.

Ну и, конечно, класс из сообщения 2 тоже подходит.