Бинарные операции

[boomeer]

Вот есть у нас выражение $x \oplus y$
Нам нужно разложить его через операции ($\urcorner \vee \wedge$)
Всем известно, что оно раскладывается так $\bar x y \vee x \bar y$. Здесь у нас 5 операций.
Но я могу разложить $\oplus$ и на 4 операции
$\bar {xy}(x \vee y)$

А как можно доказать что не существует разложения на 3 действия? Или быть может оно есть?

[Xaositect]

Небольшим перебором. Формула сложности 3 имеет вид ($\circ, \bullet, \star$ - либо $\vee$, либо $\wedge$):
Либо $(\cdot \circ \cdot)\star(\cdot \bullet \cdot)$, в этом случае функция монотонна, что нам не подходит.
Либо $(\cdot \circ \cdot)\star \bar{\cdot}$ или $(\bar{\cdot} \circ \cdot)\star \cdot$ или $\overline{\cdot \circ \cdot}\star \cdot$, в этом случае подставив вместо самой правой переменной одну из констант (в зависимости от операции $\star$) мы получим, что от второй не будет ничего зависеть. Тоже не подходит.
Либо $\bar{x}\circ \bar{y}$ или $\overline{\bar{x}\circ y}$, что нам тоже не подходит.
Либо содержит двойное отрицание, которое можно убрать

[boomeer]

Xaositect в сообщении #686037 писал(а):

Небольшим перебором. Формула сложности 3 имеет вид ($\circ, \bullet, \star$ - либо $\vee$, либо $\wedge$):

Извините, а какие операции обозначают $\circ, \bullet, \star$? Не встречал в учебнике таких обозначений
Или это просто "какая-то" операция?

[Xaositect]

boomeer в сообщении #688358 писал(а):

Или это просто "какая-то" операция?

Да, какая-то из двух.