Задачі до теми „Класи функцій, що зберігають константи”

Приклад 1. З’ясувати, яким із множин T₀ T₁, T₁ \ T₀ належать перелічені нижче функції:

а) f( ) = ((x₁  x₂)  (x₁ / x₂x₃))  ((x₂ ~ x₃)  x₁);

б) f( ) = (x₁x₂  x₃) / ((x₁  x₂)  (x₃  x₂));

в) f( ) = ((x₁  x₂)(x₂  x₃))  (x₃  x₂).

Розв’язування 1а). Маємо f(0, 0, 0) = ((0  0)  (0 / 0))  ((0 ~ 0)  0) = (0  1)  1 = 0, f(1, 1, 1) = ((1  1)  (1 / 1))  ((1 ~ 1)  1) = (1  0)  (1  1) = 0  1 = 0, тобто f  T₀, f  T₁. Отже, f  T₀ T₁ і f  T₁ \ T₀.

Розв’язування 1б). Маємо f(0, 0, 0) = (0  0  0) / ((0  0)  (0   0)) = 1 / (1  0) = 1 / 0 = 1, f(1, 1, 1) = (1  1  1) / ((1  1)  (1   1)) = 1 / 0 = = 1, тобто f  T₀, f  T₁. Отже, f  T₀ T₁ і f  T₁ \ T₀.

Розв’язування 1в). Маємо f(0, 0, 0) = ((0  0)(0  0))  (0  0) = 1  1  1 = 1, f(1, 1, 1) = ((1  1)(1  1))  (1  1) = (1  0)  1 = 1, тобто f  T₀, f  T₁. Отже, f  T₀ T₁ і f  T₁ \ T₀.

Приклад 2. З’ясувати, при яких n функція f( ) належить множині T₁ \ T₀:

а) f( ) = x₁  x₂  …  x_n  1;

б) f( ) = (…((x₁  x₂)  x₃)  …  x_n);

в) f( ) = 1  , де – сума за модулем 2 всіх можливих кон’юнкцій рангу 3.

Розв’язування 2а). Оскільки x  x = 0 і x  1 = , то для будь-якого n f( ) = 0  0  …  0  1 = 1, тому f  T₀. Знайдемо f( ) = 1  1  …  1  1, якщо n – парне. Враховуючи рівності 1  1 = 0 і 0  1 = 1, маємо f( ) = (1  1)  (1  1)  …  (1  1)  1 = 0  1 = 1.

Отже, f  T₁.

Якщо n – непарне, то f( ) = (1  1)  (1  1)  …  (1  1)  1  1 = 0  1  1= 1  1 = 0. Отже, f  T₁.

Якщо n – парне число, то f  T₁ \ T₀.

Розв’язування 2б). Оскільки x  x = 1 і 0  x = 1, то у випадку непарності n, маємо, наприклад, f( ) = (0  0)  0 = 0, f( ) = ((((0  0)  0)  0)  0) = 0. Отже, f( ) = 0. Тому f  T₀.

У випадку парності n, маємо f( ) = 0  0 = 1, f( ) = (((0  0)  0)  0) = 1. Отже, f( ) = 1. Тому f  T₀.

Знайдемо значення f( ) = (…((1  1)  1)  …  1). Оскільки 1  1 = 1, то f( ) = 1.

Якщо n – парне число, то f  T₁ \ T₀.

Приклад 3. Обчислити кількість функцій, залежних від змінних x₁, …, x_n, в кожній із таких множин:

а) T₀ T₁; б) T₀ T₁; в) T_0­ L; г) T₀ L; д) L \ (T₀ T₁);

е) T₁ S; ж) T₀ \ S; з) L S T₁.

Приклад 4. Знайти функцію f(x, x, …, x), якщо:

а) f(x₁, x₂, …, x_n)  T₁ \ T₀;

б) f(x₁, x₂, …, x_n)  L \ (T₁ S);

в) f(x₁, x₂, …, x_n)  S \ T₀.

Розв’язування 4а). Оскільки f  T₁ і f  T₀, то f(1, 1, …, 1) = 1, f(0, 0, …, 0) = 1. Тоді розглянемо функцію (x) = f(x, x, …, x) і (0) = f(0, …, 0) = 1, (1) = f(1, …, 1) = 1, тобто (x)  1.

Приклад 5. З’ясувати, чи можна дістати функцію f за допомогою операції суперпозиції над множиною , якщо:

а) f = x  y, Ф = {x  y};

б) f = x  y, Ф = {xy, x  y};

в) f =  , Ф = T₀ (S \ (L T₁));

г) f = x , Ф = (T₁ \ L) {x  y}.

Приклад 6. Довести, що:

а) = T₁;

б) (T₀ T₁)^* = T₀ T₁;

в) (T₀ T₁ S L)^* = T₀ T₁ S L;

г) ((T₀ T₁) S)^* = (T₀ T₁) S;

д) (T₀ \ S)^* = T₁ \ S;

е) (S \ T₀)^* = S \ T₁.

Розв’язування 6а). Якщо f  T₀, то f(0, 0, …, 0) = 0, і оскільки f^* = , то f^*(1, 1, …, 1) = = = 1, тобто f^*  T₁, або = T₁.

Розв’язування 6б). Якщо f  T₁, то f(1, 1, …, 1) = 1, і оскільки f^* = , то f^*(0, 0, …, 0) = = = 1, тобто f^*  T₀, або = T₀. Аналогічно встановлюється рівність = T₁ (дивись попередню задачу).

Отже, якщо f  T₀ T₁, то f  T₀ або f  T₁, або f  T₀ T₁, тому f  , або f  , або f належить . Тому f  (T₀ T₁)^* = T₀ T₁.