Класи поста, дискретна математика

Замінюючи a0 + a1 x + a2 на 1 в 4 рівнянні системи, маємо:

Після складення перших три рівняння і враховуючи, що х + х = 0, отримаємо: а0 + 0 = 0 ⇒ а0 = 1.

Підставляючи в 1 рівняння знайдені значення а0 і а3. отримаємо: 0 + а 2 + 1 = 1 або А2 +1 = 1, звідки а 2 = 0.

Підставивши значення а0 і а3 у 2 рівняння, отримаємо:

Отже, g (x, y, z) = 0 + 1⋅х + 0⋅у + 1⋅z = x + z.

Виходячи з цієї формули, знайдемо значення функції g на тих наборах, на яких вона була не визначена: g (0,0,0) = 0 + 0 = 0; g (0,0,1) = 0 + 1 = 1; g (0,1,0) = 0 + 0 = 0; g (1,0,0) = 1 + 0 = 1.

У підсумку маємо: g (x, y, z) = (01011010).

Довизначити функцію h, використовуючи визначення самодвоїстих функції. Так як набори (0,0,0) і (1,1,1) протилежні і h (0,0,0) = 1 ⇒ h (1,1,1) = 0.

Протилежними парами наборів значень змінних є також (0,0,1) і (1,1,0), (0,1,0) і (1,0,1), (0,1,1) і (1, 0,0).

Використовуючи відомі значення функції h, отримаємо:

h (0,0,1) = h (1,1,0) = 1 = 0, h (1,0,1) = h (0,1,0) = 1 = 0.

Отже, h (x, y, z) = (10101010).

1. Чи можна з функції f (x, y, z) за допомогою суперпозиції отримати g (x, y, z)?

2. Чи вірно, що f (x, y, z) ∈ [g]. ([G] - замикання класу).

Перевіримо f (x, y, z) на приналежність до класів Посту.

(0,0,0) ⪯ (0,0,1) і f (0,0,0)> f (0,0,1) ⇒ f ∉ M;

(0,0,1) і (1,1,0) - протилежні набори,

f (0,0,1) = f (1,1,0) ⇒ f ∉ S;

f (x, y, z) = (x + 1) (y + 1) (z +1) + (x + 1) yz + x (y + 1) z =

= 1 + x + y + z + xy + xz + yz + xyz + xyz + yz + xyz + xz =

= 1 + x + y + z + xy + xyz.

Так як в поліномі функції f присутні кон'юнкції, то f ∉ L.

Отже, ми бачимо, що функція f (x, y, z) не належить жодному з класів Посту, значить, система функціонально повна, і за допомогою суперпозиції з f можна отримати будь-яку булеву функцію, зокрема, g (x, y, z).

Перевіряючи значення функції g (x, y, z) на всіх парах протилежних наборів, бачимо:

g (0,0,0) = 1 = g (1,1,1). g (0,0,1) = 0 = g (1,1,0),

g (0,1,0) = 1 = g (1,0,1). g (0,1,1) = 1 = g (1,0,0).

Так як S - функціонально замкнутий клас, то [g] ⊆ S, але f ∉ S, значить, f ∉ [g].

Для функцій f (x, y, z) і g (x, y, z) з'ясувати питання про їх належність до класів Т0. T1. L, S, М.

У разі, якщо деяка функція вдає із себе функціонально повний клас, висловити з неї за допомогою суперпозиції константи 0,1, заперечення і кон'юнкцію ху.

У разі, якщо деяка функція вдає із себе функціонально повний в слабкому сенсі клас, висловити з неї за допомогою суперпозиції і фіксування змінних заперечення і кон'юнкцію ху.

Отримані результати перевірити за допомогою побудови таблиць.

1. Досліджуємо функцію f (x, y, z). Перевіримо f (x, y, z) на приналежність до класів Посту.

Зауважимо, що це означає, що не є функціонально повним класом.

Так як набори (0,0,0) і (1,1,1) протилежні і f (0,0,0) = f (1,1,1), то f ∉ S.

Маємо, що (0,1,0) ⪯ (0,1,1), але f (0,1,0)> f (0,1,1), значить, f ∉ M.

Знайдемо поліном для f (x, y, z):

= Xyz + xy + yz + y + xyz + xy + xz + x = xz + yz + x + y.

Так як поліном функції f містить кон'юнкцію, то f ∉ L.

Як було зазначено раніше, не є функціонально повним класом, але, так як функція f нелінійна і немонотонна, - функціонально повний в слабкому сенсі клас.

Висловимо з f заперечення за допомогою фіксування змінних. На сусідніх наборах (0,1,0) і (0,1,1) порушується монотонність, розглянемо функцію р (х) = f (0,1, х).

Знайдемо всі значення функції р (х):

р (0) = f (0,1,0) = 1, p (1) = f (0,1,1) = 0 ⇒ р (х) = x.

Заперечення побудовано, x = f (0,1, х).

Для побудови кон'юнкції зафіксуємо одну змінну і переобозначив залишилися змінні так, щоб поліном прийняв вигляд

xy + αx + βy + γ, де α, β, γ ∈.

Наприклад, можна зробити так: f (1, y, x) = 1⋅х + ху + 1 + у = = ху + х + у + 1. У цьому випадку α = β = γ = 1.

Введемо функцію h (x, у) = f (1, у + α, х + β) + αβ + γ = f (1, y. X) = = f (1, f (0,1, у), f (0,1, x)).

Знайдемо значення функції h на всіх її наборах.

h (0,0) = f (1, f (0,1,0), f (0,1,0)) = f (1,1,1) = 0;

h (0,1) = f (1 f (0,1,1), f (0,1,0)) = f (1,0,1) = 0;

h (1,0) = f (1, f (0,1,0), f (0,1,1)) = f (1,1,0) = 0;

h (1,1) = f (1, f (0,1,1), f (0,1,1)) = f (1,0,0) = 1.

Як бачимо, таблиця функції h (x, y) збігається з таблицею кон'юнкції, отже, х⋅у = f (1, f (0,1, у), f (0,1, х)).

2. Досліджуємо g (x, y, z) на приналежність до класів Посту.

Набори (1,0,1) і (0,1,0) протилежні і g (1,0,1) = g (0,1,0) ⇒ g ∉ S.

Так як (0,0,0) ⪯ (0,0,1), але g (0,0,0)> g (0,0,1) ⇒ g ∉ M.

Знайдемо поліном для g (x, y, z):

g (x, y, z) = (x + 1) (y + 1) (x + 1) + (x + 1) yz + xy (z + 1) =

= Xyz + xy + xz + yz + x + y + z + 1 + xyz + yz + xyz + xy =

= 1 + x + у + z + xz + xyz.

Так як в поліномі функції g міститься кон'юнкція, то g ∉ L.

Отже, функція g не належить жодному з п'яти класів поста, значить, -функціональна повний клас.

Висловимо з g заперечення за допомогою одних лише суперпозиций. Розглянемо функцію s (x) = g (x, x, x).

Знайдемо всі значення функції s (x):

s (0) = g (0,0,0) = 1, s (1) = g (1,1,1) = 0 ⇒ s (x) = x

Заперечення побудовано, x = g (x, x, x).

Будуємо константу 0. Для цього візьмемо набір з пари проти- воположних наборів, на яких функція g дорівнює 0, наприклад, (1,0,1), і розглянемо функцію про (х): о (х) = g (x 1. x 0. x 1) = g (x, x. x) = g (x, g (x, x, x) x).

Знайдемо значення функції про (х) на її наборах.

про (0) = g (0, g (0,0,0), 0) = g (0,1,0) = 0;

o (1) = g (1, g (1, g (1,1,1) 1) = g (1,0,1) = 0.

Константа 0 побудована, g (x, g (x, x, x), x) = 0.

Для побудови константи 1 візьмемо заперечення від функції про (х) і позначимо отриману функцію через е (х).

Отже, койстанта 1 отримана,

Для побудови кон'юнкції зафіксуємо змінну z, надавши їй значення 1.

Отримаємо: g (x, у, 1) = 1 + x + y + 1 + x⋅1 + xy⋅1 = xy + y + 1, т. Е. Ми отримали вираз виду ху + αх +? У + γ, де α = γ = 0, β = 1.

Розглянемо функцію k (х, у) = g (x + β, y + α, 1) + αβ + γ =

= G (x + 1, y, 1) + 0⋅l + 0 = g (g (x, x, x), y, 1) =

Знайдемо значення функції до на всіх її наборах.

k (0,0) = g (g (0,0,0), 0, g (g0, g (0,0,0), 0x g (0, g (0,0,0), 0), g (0, g (0,0,0), 0))) =

= G (1,0, g (g (0,1,0), g (0,1,0), g (0,1,0)) = g (1,0,0) = 0;

Як бачимо, таблиця функції до (х, у) збігається з таблицею кон'юнкції, отже,

Підрахувати число різних булевих функцій від п змінних, що належать даній безлічі A.

Приклад 1. Підрахувати число различ них булевих функцій від n змінних, що належать безлічі L \ (T0 ∩S).

Позначимо через L (n). T (n) 0. S (n) відповідно безлічі лінійних, які зберігали нуль і самодвоїстих функцій від n змінних.

Заштрихованная область відповідає функціям шуканого класу. Очевидно, виконано рівність:

| L (n) \ (T (n) 0 ∩S (n)) | = | L (n) | - | L (n) ∩T (n) 0 ∩S (n) |

Поставимо у відповідність кожній такій функції вектор її довічних коефіцієнтів (а 0. А1. А0. А0). Очевидно, що це відповідність - біекція, значить, кількість різних лінійних функцій від п змінних дорівнює кількості різних двійкових наборів розмірності n + 1, тобто 2 n + 1 отже, | L (n) | = 2 n + 1.

Якщо лінійна функція зберігає константу 0, то а0 + а1 ⋅ 0 + а0 ⋅ 0 +. + Аn ⋅ 0 = 0 ⇒ а0 = 0, і вона має вигляд а1 х1 + А2 х2 +. + Аn хn. Для самодвоїстих функції виконується властивість f (х 1. х n) = f (х1. Хn). З огляду на, що х = х + 1, подивимося, як буде виглядати ця рівність в разі лінійної, зберігає нуль функції:

Додамо по модулю 2 до обох частин отриманого рівності вираз а1 х1 + А2 х2 +. + Аn хn. врахуємо, що х + х = 0. Тоді після спрощень матимемо: а1 + а1 +. + А1 = 1. (*)

З коефіцієнтів а1. а1. аn довільним чином можна призначати n-1 коефіцієнт, а значення n-го коефіцієнта однозначно визначається з рівності (*). Отже, між безліччю булевих функцій класу L (n) ∩T (n) 0 ∩S (n) і безліччю двійкових векторів розмірності n-1 існує біекція, значить, вірно рівність | L (n) ∩T (n) 0 ∩S (n) | = 2 n-1.

В результаті отримуємо:

| L (n) \ T (n) 0 ∩ S (n)) | = | L (n) | - | L (n) ∩ T (n) 0 ∩ S (n) | = 2 n + 1 - 2 n-1 = 2 n-1 (4-1) = 3⋅2 n-1.

Приклад 2. Підрахувати число різних булевих функцій від n змінних, що належать безлічі S ∪ T 1.

Позначимо через S (n) і T (n) 1 відповідно безлічі самодвоїстих і зберігають одиницю функцій від n змінних.

Зобразимо безлічі S (n) і T (n) 1 (рис. 2.4.4, б).

| S (n) ∪ T (n) 1 | = | S (n) | + | T (n) 1 | - | S (n) ∩ T (n) 1 |.

Нехай f ∈ S (n). g ∈ T (n) 1. h ∈ S (n) ∩T (n) 1. зобразимо таблиці цих функцій.