Критерий полноты в 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