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

 

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

1) {0,1}

2) {0,x1 V x2, x1 V x2 V x3, …, x1 V x2 V … V xn, …}

3) {x1 + x2, x1 + x2 + x3, …, x1 + x2 + … + xn, …}

 

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

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=(x1x2 V x1(x2+1)) + x3

2) f=(x1->x2)(x2->x1) ~ x3

 

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

1) f=(1010 1010 0110 1000)

2) f=(1001 0110 1001 0110)

 

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

 

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

1) f=x1 + x2 + … + xn+ 1

2) f= (…((x1->x2)-> x3)->…-> xn)

 

2.11. Найти функцию f(x,x,…x), если f(x1, …, xn) принадлежит множеству S\T0

 

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

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

2) f=xy+yz+zx+z

3) (0001 0101 0101 0111)

 

2.13. Перечислить все монотонные функции f(x1,x2,x3,x4), удовлетворяющие следующим условиям:

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. Найти число функций, зависящих от переменных x1, …, xn и принадлежащих множеству M\(T1UT0).

 

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

 

 

 

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