Задание 6. 6.1. Требуется выделить из данного набора из 5 функций полные наборы функций и базисы:

6.1. Требуется выделить из данного набора из 5 функций полные наборы функций и базисы:

1) f₁ (x, y, z) = (x y)¯ (y ~ z), 2) f₂ (x, y) = x + y x, 3) f₃ (x, y, z) = x ~ (y z), 4) f₄ (x, y) = x + ,

5) f₅ (x, y, z) = x y Ú .

Решение. Составляем таблицу истинности для каждой из этих 5-и функций. Заметим, что для

f₂ и f₄ таблицу можно составить отдельно.

x, y, z	xy	y ~ z	f1 = (x y)¯ (y ~ z)		yz	f3 = x~ y z		f5 = x y Ú

Отсюда очевидно, что f₁ (x, y, z) Î T₀ (принадлежит классу Т₀) и f₁ Ï T₁, f₁ Ï M, S (не принадлежит Т₁ и М, S), аналогично f₃ не принадлежит T₀, T₁ и M, S. Функция f₅

принадлежит Т₁ и не принадлежит Т₀ и М, S. Осталось проверить линейность этих функций.

f₃ = x ~ (y z) = = x + x y + 1, нелинейна;

f₅ = x y = (x y + 1) z + 1 = x y z + z + 1, нелинейна.

Для f₁ требуется проверка нелинейности. Составим полином Жегалкина для f₁:

P = a₀ + a₁ x + a₂ y + a₃ z + a₄ x y + a₅ x z + a₆ y z + a₇ x y z. Находим последовательно a: a₀ = 0,

a₃ = 1, a₂ = 1, a₄ = 0, a₅ = 0, a₁ = 1, a₁ + a₃ + a₆ = 1, откуда a₆ = 1; значит,

функция f₁ нелинейна (что, впрочем, следует и из того, что f₁ в таблице истинности содержит нечетное число единиц (равное 3).

Для f₂ и f₄ составляем свои таблицы истинности.

x, y	x y	f2 = x + x y	f4 = x+

Отсюда следует, что f₂ принадлежит T₀, не принадлежит T₁, не принадлежит M, S; f₂ является полиномом Жегалкина f₂ = x + y + 1 и, значит, принадлежит L, принадлежит также T₁, но не принадлежит M, S. Все эти сведения сведём в таблицу Поста.

Таким образом, мы видим, что базисами являются: 1) f₃, 2) f₁ и f₄, 3) f₂ и f₄,

4) f₁ и f₅, 5) f₂ и f₅. Они являются полными наборами, как и любые наборы, содержащие базисы.