Критерий полноты в P₂

3.1. Показать, что в P₂ не существует предполных классов, отличных от T₀, T₁, 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 \ (T₀ U T₁))

5) { f₁, f₂ }, где f₁ ∈ S \ M, f₂ ∉ L U S, f₁ → f₂=1 (показать решение)

6) { f₁, f₂, f₃ }, где f₁ ∉ L U (T₀ ∩ T₁), f₂ ∈ M \ L, f₁ → f₂=1, f₁ V f₃=1

3.3. Из полной в P₂ системы выделить всевозможные базисы:

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 примера базисов в P₂, состоящих из 1, 2, 3 и 4 функций (показать ответ)

3.5. Можно ли расширить до базиса в P₂ множество A?

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

2) A= { x~y, x V yz }

3) A= M \ (T₀ U T₁)

4) A= L ∩ M

3.6. Доказать, что если f ∉ T₀ U T₁ U S, то f – шефферова. (показать решение)

3.7. При каких n (n>1) f является шефферовой?

f = (x₁|x₂)+(x₂|x₃)+…(x_n-1|x_n)+(x_n|x₁) (показать ответ)

3.8. Верно ли утверждение:

1) Если f ∉ (T₀ U T₁) \ S, то f ∈ L U M

2) Если f ∉ L U S U M, то f – шефферова

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