Поліном Жегалкіна

Елементарну кон'юнкцію називають монотонною, якщо вона не містить заперечень змінних. Наприклад, x₁x₂x₃, x₁, 1-монотонні кон'юнкції.

Формулу

деk₁k₂,..., k_s- попарно різні монотонні кон'юнкції змінних із мно­жиниX={x₁х₂, …, х_n }, називають поліномом Жегалкіна. Най­більший із рангів елементарних кон'юнкцій, що входять у поліном, називають степенем полінома. За окремим означенням 0 вважати­мемо поліномом Жегалкіна.

Приклад 8.17. Формули х, 1, xyz xy z 1- поліноми Жегалкіна, ахх, xyz xy z 1не є поліномами Жегалкіна. ▲

Якщо маємо будь-яку формулу алгебри Жегалкіна, то для отри­мання полінома Жегалкіна достатньо розкрити дужки (дистри­бутивний закон), скористатися, якщо можливо, законом ідемпо­тентності для кон'юнкції та звести подібні члени.

Теорема 8.5. Будь-яку булеву функцію можна єдиним способом зобразити у формі полінома Жегалкіна.

Доведення. Нехай - довільна булева функція.

Достатньо провести доведення для функцій, відмінних від конс­тант, тому що 1 та 0 є поліномами Жегалкіна. Задамо функцію f досконалою диз'юнктивною нормальною формою, тобто деякою диз'юнкцією конституент одиниціf=K₁∨ К₂∨...∨ K_s.Замінемо знак ∨ знаком ⊕ і одержимоg= K₁⊕ К₂⊕...⊕ K_s. Покажемо, що функціїfта g рівні. На жодному наборі (а₁,..., a_n) значень змінних дві різні конституенти одиниці не можуть одночасно перетворитись в 1, оскільки i -а конституента одиниці перетворюється в 1 лише на i -му наборі. Отже, під час обчислення значень функцій f та g потрібно знайти значення диз'юнкції або, відповідно, суми за mod2 членів, із яких лише один може дорівнювати одиниці, решта - обов'язково нулі. Але у такому випадку диз'юнкція та додавання за mod2 призводять до одного й того ж результату (до нуля, якщо всі члени дорівнюють нулю, і до одиниці, якщо один і лише один член дорів­нює одиниці).

Вотриманій формулі замінимо всі заперечення змінних згідно з тотожністю х = 1⨁ х. Одержимо формулу алгебри Жегалкіна. Зали­шається лише розкрити дужки, скористатись законом ідемпотент­ності для кон'юнкції та привести подібні члени. Внаслідок цього одержимо зображення булевої функції f у формі полінома Жегал­кіна.

Доведемо, що тaке зображення єдине. Для цього підрахуємо кіль­кість поліномів Жегалкіна від п змінних х₁ х₂,..., х_п. Кількість кон'юнкцій вигляду дорівнює кількості підмножин { i ₁ і₂, …, i_s) множини {1, 2,..., n }, тобто2ⁿ.Кожна з цих кон'юнкцій може входити в поліном із коефіцієнтом 0 або 1. Отже, кількість поліномів Жегалкіна від п змінних дорівнює кількості кортежів довжини 2 ⁿ елементами яких є 0 або 1, тобто , що дорівнює кількості всіх булевих функційвід змінних x₁, x₂, …, x_n. А оскільки доведено, щобудь-яку булеву функцію можна зобразити поліномом Жегалкіна, то звідси випливає єдиність цього зображення. ▲

Коротко зупинимось на методах побудови полінома Жегалкіна.

Побудова полінома Жегалкіна методом невизначених коефіці­єнтів. Для функції записують найбільш загальний вигляд полінома Жегалкіна з невизначеиими коефіцієнтами(цих коефіцієнтів є 2 ⁿ). Для кожного двійкового набору (a ₁, …, a_n) значень змінних записують рівняння .Одержують систему 2 ⁿ рівнянь. Розв'язком цієї системи є коефіцієнти полінома .

Приклад 8.18. Побудуємо поліном Жегалкіна для функції f (x, y)= x ∽ y. Загальний вигляд полінома від двох змінних з невизначеними кое­фіцієнтами такий:

Прирівняємо значення функції і полінома на всіх чотирьох набо­рах значень змінних і одержимо систему рівнянь відносно невизна­чених коефіцієнтів:

Звідси визначаємо с ₀=1, с₁=1, с₂=1, с₃=0. Отже, x∽ y= 1⨁ x ⨁ y. ▲

Побудова полінома Жегалкіна на основі тотожних перетворень. Один із способів побудови полінома Жегалкіна полягає у наступ­ному. Спочатку будують рівносильну формулу, в якій є лише операції кон'юнкції та заперечення, а потім замінюють всюди на1⨁ х. Після цього поліном одержують тривіальним шляхом.

Приклад 8.19.Побудуємо поліном Жегалкіна для функції :

. ▲

Побудова полінома Жегалкіна за досконалою ДНФ булевої функції. Цю побудову здійснюють за схемою доведення теореми 8.5. Такий спосіб доцільно застосовувати, коли функція задана доско­налою ДНФ, або якщо цю форму легко знайти.

Приклад 8.20.Побудуємо зазначеним методом поліном Жегал­кіна для функції . Спочатку перетворимо цю ДНФ у досконалу:

Повторюючи схему доведення теореми 8.5, матимемо

.▲

Поліном Жегалкіна має цікаву властивість, зручну для знаход­ження істотних змінних булевої функції.

Теорема 8.6.Булевафункція має істотними всі змінні, які входять у її поліном Жегалкіна.

Доведення. Нехай змінна х, входить у поліном Жегалкіна функції f (x₁, х₂,..., х_п). Згрупуємо члени, які містятьх₁, і винесемо х₁ за дужки:

Функція оскільки у протилежному випадку змінна х ₁ не входила б у поліном для функції f (через єдиність полінома Жегал­кіна). Нехай на наборі (а ₂,..., а_n) значення функції f ₁ дорівнює одиниці. Тоді , де . Отже, зміна значення х ₁ у разі, коли значення решти змінних задані набором (а ₂,..., а_n), змінює значення функції . Отже, змінна х₁ істотна. ▲