Замкнутые классы и полнота в 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
| 
