Замкнутые классы и полнота в P₂

2.1. Является ли множество замкнутым классом?

1) {0,1}

2) {0,x₁ V x₂, x₁ V x₂ V x₃, :, x₁ V x₂ V : V x_n, :}

3) {x₁ + x₂, x₁ + x₂ + x₃, :, x₁ + x₂ + : + x_n, :}

2.2. Сведением к заведомо полным системам показать, что множество является полной системой в P₂

1) {x&y+z, (x~y)+z} (показать решение)

2) {x->y, (1100 0011 0011 1100)}

3) {(1011), (1111 1100 1100 0000)}

2.3. Из системы A, полной для замкнутого класса M=[A], выделить базис в M

1) A={ 0, 1, x, ¬x } (показать решение)

2) A={x V y, x & y & z, x V y & z, (x V y) & z} (показать ответ)

3) A={(x->y)->(y->z), x V y V (y+z)}

2.4. Перечислить все предполные классы в замкнутом классе M

1) M=[{ 0, ¬x }] (показать решение)

2) M=[{0, x V y}]

3) M=[{0, x & y & z}]

2.5. Самодвойственна ли функция f?

1) f=( ¬ ((x->y)->xz) )->(y->z) (показать решение)

2) f=(0001 0010 0110 0111)

2.6. Из функции f с помощью подстановки на места переменных функций x и ^┐x получить константу

1) f=(00111001) (показать ответ)

2) f=xy V xz V yt V zt

2.7. Разложив функцию f в полином Жегалкина, выяснить, является ли она линейной

1) f=(x₁x₂ V x₁(x₂+1)) + x₃

2) f=(x₁->x₂)(x₂->x₁) ~ x₃

2.8. Является ли линейной функция f?

1) f=(1010 1010 0110 1000)

2) f=(1001 0110 1001 0110)

2.9. Найти число функций, зависящих от переменных x₁, :, x_n и принадлежащих одновременно классам L и S.

2.10. Выяснить, при каких n функция f принадлежит множеству T₁\T₀

1) f=x₁ + x₂ + : + x_n+ 1

2) f= (:((x₁->x₂)-> x₃)->:-> x_n)

2.11. Найти функцию f(x,x,:x), если f(x₁, :, x_n) принадлежит множеству S\T₀

2.12. Является ли функция f монотонной?

1) f=x->(y->x)

2) f=xy+yz+zx+z

3) (0001 0101 0101 0111)

2.13. Перечислить все монотонные функции f(x₁,x₂,x₃,x₄), удовлетворяющие следующим условиям:

1) f(1,0,0,0)=1, f(0,1,1,1)=0 (показать ответ)

2) f(1,0,0,0)=1, f - линейная

3) f(1,0,0,1)=0, f - самодвойственная

2.14. Найти число функций, зависящих от переменных x₁, :, x_n и принадлежащих множеству M\(T₁UT₀).

2.15. Показать, что [[M]]=[M].

Список задач по P₂