Критерий полноты в P2
3.1. Показать,
что в P2 не
существует предполных классов, отличных от T0, T1,
L, S, M.
3.2. Полна
ли система A:
1)
A={ x→y, x→(z(y+1)) } (показать решение)
2)
A={ 0, 1, x(y~z)V(x+1)(y+z) }
3)
A={ (0110 1001), (1000 1101), (0001 1100) }
4)
(S \ M) U (L \ (T0 U T1))
5)
{ f1, f2 }, где
f1 ∈ S \ M, f2 ∉ L U S, f1 → f2=1 (показать решение)
6)
{ f1, f2, f3 }, где
f1 ∉ L U (T0
∩ T1), f2 ∈ M \ L, f1 →
f2=1, f1 V f3=1
3.3. Из
полной в P2 системы
выделить всевозможные базисы:
1)
A= { (x V y)( ¬x V ¬y ), xy+z, (x+y)~z, m(x,y,z) }, где m(x,y,z) = xy V xz V yz. (показать решение)
2)
A= { 1, ¬x, xy(y~z), x+y+ m(x,y,z) }
3)
A= { x V (x+y) V z, (x~y)~z, xy+zu, m(x, ¬y, ¬z) }
3.4. Привести
по 3 примера базисов в P2,
состоящих из 1, 2, 3 и 4 функций (показать ответ)
3.5. Можно
ли расширить до базиса в P2
множество A?
1)
A= { x+y, m(x,y,z) } (показать решение)
2)
A= { x~y, x V yz }
3)
A= M \ (T0 U T1)
4)
A= L ∩ M
3.6. Доказать,
что если f ∉ T0 U T1 U S, то f – шефферова. (показать решение)
3.7. При
каких n (n>1) f является
шефферовой?
f = (x1|x2)+(x2|x3)+…(xn-1|xn)+(xn|x1) (показать ответ)
3.8. Верно
ли утверждение:
1)
Если f ∉ (T0 U T1) \
S, то f ∈ L U M
2)
Если f ∉ L U S U M, то
f – шефферова
Список задач по P2
|
