Исследование систем функций k-значной логики на полноту

3.1 Выяснить, полны ли в P_к следующие системы:

1) { 1, J₀(x), J₂(x), min(x,y), max(x,y) }, k=3 (показать решение)

2) { 1, 2, J₂(x), min(x,y), max(x,y) }, k=3

3) { 1, 2, J₀(x), J₁(x), min(x,y), max(x,y) }, k=4

3.2 Используя метод сведения к заведомо полным системам, доказать полноту:

1) { 1, x²-y, min(x,y) } (показать решение)

2) { k-1, x y, x+y }

3) { 1, 2x+y, x² y }

3.3 Используя критерий Слупецкого, доказать полноту:

1) { k-1, j₀(x), x+y }

2) { j₂(x), x+y², x∙y+1 } (показать решение)

3.4 Исследовать на полноту следующие системы:

1) { k-2, x+y, min(x,y) } (показать решение)

2) { 1, 2, x y +1 }

3) { 2 x, max(x,y), x∙y } (показать решение)

4) { ~x, 2j₀(x), J₁(x), x y }

3.5 Подсчитать число существенных функций в P_к, зависящих от переменных x₁,... x_n.

3.6 Доказать, что каждый замкнутый класс в P_к имеет не более чем счетное множество предполных в нем классов.

Список задач по P_k