Функціонально повні системи

Систему булевих функцій Q називають функціонально повною, якщо довільну булеву функцію можна зобразити формулою над Q

Приклад 8.21. Розглянемо деякі повні системи.

1. Як уже було зазначено, система - повна.

2. Система { x у, х⊕ у, 1} - повна. Справді, якщо функція f ≠ 0, то зобразимо її поліномом Жегалкіна; якщо f =0, то0=х⊕ х.▲

Очевидно, що не кожна система булевих функцій є повною.Наприклад, система - неповна: через неї не можна зобрази­ти функцію двох змінних.

Дослідження повноти одних систем можна звести до дослід­ження повноти інших систем.

Теорема 8.7. Нехай задано дві системи булевих функцій Q _] та Q ₂, причому система Q₁, функціонально повна і кожну її функцію можна виразити у вигляді формули через функції системи Q ₂. Тоді системаQ₂ також функціонально повна.

Доведення. Нехай f - довільна булева функція. Оскільки система Q ₁повна, то функцію f можна виразити формулою F ₁, яка містить скінченну кількість функцій системи Q ₂.Нехай це будуть функції g ₁, g ₂, …, g_k. За умовою теореми кожна з цих функцій виражається формулою через скінченну кількість функцій системи Q ₂, нехай це будуть функції h ₁, h ₂, …, h_l. Тому у формулі F можна усунути входження функцій g ₁, g ₂,.., g_k, замінюючи їх формулами, які містять функції h ₁, h ₂, …, h_l. Тоді одержимо формулу F ₂. Отже, функцію f виразили у вигляді формули F ₂ через функції h ₁, h ₂, …, h_l системи Q. Оскільки функція f довільна, то система Q ₂ функціонально повна. ▲

Приклад 8.22.Продовжимо розгляд функціонально повних систем.

3. Система {х, ху} - повна, бо повною є система 1 іх∨ у= .

4. Система - повна, тому що повною є система 1 і .

5. Система{х|у} є повною, тому що повною є система 3 і

8.4.2. Замкнені класи

Множину К булевих функцій називають замкненим класом, якщо довільна суперпозиція функцій із К знову належить К. Будь-яка системаQбулевих функцій породжує деякий замкнений клас. Цей клас складається з усіх функцій, які можна отримати суперпозиціями функцій ізQ, його називають замиканням Q.ЗамиканняQпозна­чають[Q].Очевидно, що якщо К - замкнений клас, то[К]=К, а якщоQ - функціонально повна система, то[Q]-P_r Існує п'ять найважливіших замкнених класів:

1) клас Т₀ функцій, що зберігають 0;

2) клас Т₁ функцій, що зберігають 1;

3) класSсамодвоїстих функцій;

4) клас М монотонних функцій;

5) класLлінійних функцій. Переходимо до вивчення цих класів.

Клас T₀ функцій, що зберігають 0. Булеву функцію f (x ₁, …, x_n)називають функцією, яка зберігає 0, якщо f (0,..., 0)=0.

Наприклад, функції 0, x ₁, x ₁ x ₂, x ₁∨ x ₂, x ₁⊕ x ₂ зберігають 0, тобто належать класу Т₀, а функції 1, не зберігають 0, тобто не

належать класуT₀.Таблиця значень функції ізT₀у першому рядку

завжди має 0. Отже, в Т₀ є булевих функцій, якізалежать від змінних x ₁, … x_n.

Теорема 8.8. Т₀ - замкнений клас. Іншими словами, із функцій, що зберігають 0, суперпозицією можна одержати лише функції, що зберігають 0.

Доведення. Клас Т₀ містить тотожну функцію. Отже, досить довести, що функція

зберігає 0, якщо функції f, f ₁, f ₂, …, f_m зберігають 0. Справді,
▲

Наслідок. Повна система функцій повинна містити хоча б одну функцію, яка не зберігає 0. Іншими словами, повна система функцій не повинна цілком міститись у замкненому класі Т₀. ▲

Клас Т₁ функцій, що зберігають 1. Булеву функцію називають функцією, яка зберігає 1, якщо f (1,..., 1)=1.

Наприклад, функції 1, x ₁, x ₁ x ₂, x ₁∨ x ₂, x ₁⊕ x ₂належить класуТ₁, а функції 0, не належать Т₁.

Теорема 8.9. Т₁ - замкнений клас.

Доведення. Т₁ містить тотожну функцію. Отже, достатньо довести, що функція

зберігає 1, якщофункції f, f ₁, f ₂, …, f_m зберігають 1. Справді,

Наслідок. Повна система функцій повинна містити хоча б одну функцію, яка не зберігає 1. Іншими словами, повна система функцій не повинна цілком міститись у замкненому класі Т₁▲

Легко показати, що клас Т ₁ має функцій, які залежать від n змінних х₁, …х_п. Зазначимо, що існують булеві функції, які збері­гають і 0, і 1, водночас є функції, які не зберігають ні 0, ні 1. Наприк­лад,

x ₁ x ₂, x ₁∨ x ₂, x ₁⊕ x ₂⊕ x ₃ ∈ T ₀∩ T ₁, a x ₁| x ₂, x ₁↓ x ₂∉ T ₀∪ T ₁.

Клас S самодвоїстих функцій.Нагадаємо означення самодвоїстої функції: функцію називають самодвоїстпою, якщо вона двоїста до самої себе: f *= f. Наприклад, функції x1, , x1⊕ x2⊕ x3- самодвоїсті, а функції x1x2, x1∨ x2, несамодвоїсті. Використовуючи означення двоїстої функції, можна дати інше означення самодвоїстої функції, еквівалентне до попереднього означення.

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

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

Теорема 8.10. Клас S самодвоїстих функцій замкнений.

Доведення. Оскільки тотожна функція належить класу S, достат­ньо довести, що функція

самодвоїста, якщо функції f, f ₁, f ₂, …, f_m самодвоїсті. Використовуючи принцип двоїстості, отримаємо:

.▲

Наслідок. Повна система булевих функцій повинна містити хоча б одну несамодвоїсту функцію. ▲

Теорема 8.11 (лема про несамодвоїсту функцію). Із несамодвоїстої функції f (x ₁, …, x_n)підстановкою функцій xта можна отримати несамодвоїсту функцію однієї змінної, тобто константу.

Доведення. Нехай f (x ₁, …, x_n) ∉ S. Отже, існує принаймні один такий набір значень змінних, що

За набором визначимо допоміжні функції i=1, 2, …, n:

Легко переконатись, що ці функції мають властивість , (i=1, 2, …, n).

Розглянемо функцію Ф (x)= . Ця функція отримана з функції f (x ₁, …, x_n) підстановкою xта . Функція Ф(х) - конс­танта, оскільки

Клас М монотонних функцій. На множині всіх n-місних двійкових наборів уведемо відношення часткового порядку. Нехай , - двійкові набори; набір , якщо a_n≤ b_n для всіх i=1, 2,..., n. Наприклад, (010)≤ (110), а набори (010) і (100) порівняти не можна.

Функцію f (x ₁, …, x_n) називають монотонною, якщо для будь-яких двійкових наборів із того, що випливає, що . Наприклад, 0, 1, х₁, х₁х₂, х₁∨ х₂ – монотонніфункції, а - немонотонні.

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

Теорема 8.12. Нехай - монотонна функція. Якщо не зберігає 0, то вона тотожно дорівнює 1. Якщо не зберігає 1, то вона тотожно дорівнює 0.

Доведення. Для будь-якого набору виконується . Далі, Отже, для довільного набору , тобто f є константою 1. Друге твердження теореми доводять аналогічно. ▲

Наслідок. Якщо функція f ∈ T ₀∩ T ₁ і не є константою, то вона немонотонна.▲

Отже, всі монотонні функції, окрім констант 0 та 1, належать T ₀∩ T ₁.Зауважимо, що існують функції, які належать T ₀∩ T ₁, але не є монотонними, наприклад, x ₁⊕ x ₂⊕ x ₃.

Теорема 8.13. Клас М монотонних функцій замкнений.

Доведення. Оскільки тотожна функція належить класуМ, то для доведення замкненості М досить показати, що функція

монотонна, якщо функції f, f ₁, f ₂, …, f_m монотонні. Нехай , тоді для всіх i =1, 2,..., п. Звідси

Отже, ,

Наслідок. Повна система булевих функцій повинна містити хоча б одну немонотонну функцію. ▲

Теорема 8.14 (лема про немонотонну функцію). Ізнемонотонної функції підстановкою констант 0, 1 та функції х можна отримати функцію .

Доведення. Нехай f (x ₁,..., х_n)∉ М, отже, існує два набори , значень змінних х₁,..., х_n такі, що , але , тобто , .

Якщо та відрізняються у k компонентах, то в цих компо­нентах у наборі є нулі, а в наборі -одиниці (оскільки ).

Підставимо у функцій)/^,..., xjзамість змінних, яким у наборах а" та В" відповідають однакові значення, просто ці значення, а на місце решти £ змінних - функціюх. Тоді отримаємо функцію однієї

змінноїg(x).Враховуючи, що , , одержимо g (0) = , . Отже, g(x)= . ▲

Клас Lлінійних функцій.Булеву функцію f (x ₁, …, x_n)називають лінійною, якщо їїполіном Жегалкіна має вигляд

Це поліном першого степеня, або лінійний поліном. Він не має багатомісних кон'юнкцій вигляду х_i.х_j, х_iх_jх_k тощо.

Коефіцієнтиc₀, с₁,..., с_плінійного полінома утворюють довіль­ний набір значень із n +1 нулів та одиниць. Через єдиність полінома Жегалкіна різним наборам коефіцієнтів відповідають різні булеві функції. Отже, є точно 2 ^{n+ 1} лінійних булевих функцій від n змінних. Прикладами лінійних булевих функцій є 0, 1, х, , х₁~х_2> а функції x ₁→ x ₂, x ₁∨ x ₂ - нелінійні.

Неважко переконатись, що серед лінійних функцій самодвоїсгими є ті, у яких поліном Жегалкіна містить непарну кількість змінних, а несамодвоїстими ті, у яких поліном Жегалкіна містить парну кількість змінних. Наприклад, функціїx, x⊕ 1, x₁⊕ x₂⊕ x₃- самодвоїсті, а функції x₁⊕ x₂, x₁⊕ x₂⊕ 1 -- несамодвоїсті.

Серед лінійних функцій монотонними є лише 0, 1, x.

Теорема 8.15.Класі L лінійних функцій замкнений.

Доведення. МножинаLусіх лінійних функцій є замкненим класом, оскільки підстановка формул вигляду у формулу такого ж вигляду знову дає формулу того самого вигляду. ▲

Наслідок. Повна система булевих функцій повинна містити хоча б одну нелінійну функцію. ▲

Теорема 8.16(лема про нелінійну функцію). Якщо функція нелінійна, то існує зображення кон'юнкції двох змінних у вигляді суперпозиції констант 0 il, заперечення та функції

Доведення. Нехайf∉ L.Тоді її поліном Жегалкіна містить кон'юнкції змінних. Виберемо серед них кон'юнкцію найменшого рангу, нехай це буде

Надамо значення , а для всіх x_j, які не входять в k, надамо значення x_j =0. Підстановка цих констант у поліном перетво­рить.решту кон'юнкцій - в 0. При цьому функція/набере вигляду, , деα, β, γ - коефіцієнти, що дорівнюють 0 або 1 і залежать від конкретної функції f (x ₁,..., х_n).

Розглянемо функцію

Отже, .

Цю функцію отримано суперпозицією констант 0 il, заперечен­ня та функції f (x ₁,..., х_n)∉ L.Якщо , то . Якщо , то .▲

8.4.3. Критерій функціональної повноти системи булевих функцій

Перейдемо безпосередньо до критерію функціональної повноти, який дає теорема про функціональну повноту, доведена Е. Постом (Е. Post) 1921 p.

Теорема 8.17. Для того, щоб система булевих функційQбула функціонально повною, необхідно й достатньо, щоб вона містила 1) функцію, яка не зберігає 0; 2) функцію, яка не зберігає 1; 3) несамодвоїсту функцію; 4) немонотонну функцію; 5) нелінійну функцію.

Іншими словами, для повноти системиQнеобхідно й достатньо, щоб для можного з п'яти замкнених класівT₀, T₁S, М, Lвона містила функцію, яка цьому класу не належить..

Доведення. Необхідність. Вона випливає із замкненості кож­ного з п'яти розглянутих класів (наслідки з теорем 8.8, 8.9, 8.10, 8.13, 8.15).

Достатність. Уведемо позначення для функцій із системиQ:

f_i - функція, яка не зберігає 0;

f_j-функція, яка не зберігає 1;

f_k - несамодвоїста функція;

f_m - немонотонна функція;

f_l - нелінійна функція.

Доведення виконаємо в 2 етапи.

Перший етап. На цьому етапі одержимо константи 0 та 1. Роз­глянемо функцію f_i (не зберігає 0): f_i (0,..., 0)=1. Можливі два випадки.

1) f_i (1,..., 1)=1, тоді функція тотожно дорівнює 1, бо =1, .

Із функції f_i (не зберігає 1) у цьому випадку можна одержати константу 0, тому що .

2) . Тоді функція є запереченням: , оскільки .

Із несамодвоїстої функції f_k і побудованої функції за лемою про несамодвоїсту функцію (теорема 8.11) одержимо константу. Другу константу одержимо, використовуючи , оскільки , . Отже, у випадках 1) та 2) одержимо функції 0 та 1.

Другий етап. Використовуючи константи 0, 1 і немонотонну функцію f_m за лемою про немонотонну функцію (теорема 8.14) одержимо. Далі, використовуючи константи 0, 1 і функції та f_l ∉ L за лемою про нелінійну функцію (теорема 8.16) одержимо кон'юнкцію двох зміннихху.

Отже, через функції системи Q виразили таху. Але система { , ху} - повна. Отже, за теоремою 8.7 і система Q повна. ▲

Для перевірки виконання для деякої скінченної системи функцій { f ₁, …, f_q } умов теореми Поста складають таблицю, яку називають таблицею Поста. Рядки цієї таблиці позначено функціями системи, а стовпці - назвами п'яти основних замкнених класів.

У клітках таблиці Поста ставлять знак " +" або " -" залежно від того, належить чи не належить функція замкненому класу. Для повноти системи функцій необхідно й достатньо, щоб у кожному стовпчику таблиці Поста був хоча б один " -" (мінус).

Приклад 8, 23.Дослідимо, чи є функціонально повною система {х→ у, 0}. Побудувавши таблицю Поста (табл. 8.6), переконуємося, що ця система є функціонально повною. ▲

Таблиця 8.6

Мінімальну повну систему функцій (тобто таку повну систему функцій, вилучення із якої довільної функції робить систему непов­ною) називають базисом. Із теореми Поста випливає, що базис не може містити більше п'яти функцій. Насправді, відомий точніший результат.

Теорема 8.18. Максимальна кількість функцій базису дорівнює 4.

Доведення. Функція f_i ∉ Т₀або несамодвоїста: f_i (0,..., 0)= f_i (1,..1)=1 (випадок 1 доведення теореми 8.17), або не зберігає 1 і немонотонна (випадок 2 доведення теореми 8.17).

Отже, повною буде або система { f_i, f_j, f_m, f_l }, або система { f_i, f_k, f_l }. Константу 4 у цій теоремі не можна понизити. Система з чотирьох функ­цій { f ₁, f ₂, f ₃, f ₄}, де f ₁=0, f ₂=2, f ₃ =x₁x₂, повна. Із цієї системи не можна вилучити жодної функції без порушення повноти. Справді, функція f ₁ є єдиною із функцій цієї системи, що не зберігає 1, f ₂- єдиною функцією, що не зберігає 0, f ₃- єдиною нелінійною функцією, f ₄- єдиною немонотонною функцією. Несамодвоїстих тут три функції: f ₁, f ₂, f ₃.▲