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

 

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

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

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

3) { 1, 2, J0(x), J1(x), min(x,y), max(x,y) }, k=4

 

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

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

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

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

 

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

1) { k-1, j0(x), x+y }

2) { j2(x), x+y2, 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, 2j0(x), J1(x), x y }

 

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

 

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

 

 

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