Реалізація функцій формулами

Булевою називають функцію ƒ (x₁, …, x_n)область значень якої складається з 0 та 1, і яка залежить від змінних х₁,..., х_n, що прийма­ють також лише ці два значення.

Множину всіх булевих функцій позначають Р₂.Булеві функції широко застосовують у математичній і технічній кібернетиці, зокре­ма, для конструювання мікропроцесорів.

Булеву функцію відnзмінних називаютьп-місною. Областю її визначення є множина усіх можливих n-місних наборів (векто­рів) значень змінних. Ці набори називають двійковими наборами, або просто наборами. Отже, область визначення n -місної булевої функції є скінченною і складається з2^п наборів значень змінних. Для набору (а₁,..., а_п) використовують позначення або .

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

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

Віддаллю Хемінга між наборами та називають число

Це число дорівнює кількості компонент, у яких набори та відрізняються. Набори та називають сусідніми, якщо і протилежними, якщо . Отже, сусідні набори відрізняються в одній компоненті, а протилежні - в усіх n компонентах. Наприклад, набори (0100) та (1100) - сусідні, а (0100) та (1011) - протилежні.

Скінченність області визначення довільної булевої функції дає змогу задавати таку функцію таблицею. Розташуємо всі набори значень змінних у стовпчик у лексикографічному порядку і вкажемо значення функції на кожному з них Тоді одержимо таблицю булевої функції (див. табл. 8.1).

Правий стовпчик цієї таблиці (стовпчик значень функції) склада­ється з2^п нулів та одиниць. Отже, n -місних булевих функцій існує стільки, скільки існує наборів довжини2ⁿ з 0 та 1. Томуправильнішє наступне твердження.

Таблиця 8.1

Теорема 8.1. Кількість p ₂(n) всіх функцій з Р₂ які залежать від n змінних х ₁,...., x_n дорівнює . ▲

Далі завжди будемо передбачати лексикографічне розташуванні наборів. Тому функцію можна задавати век­тором , у якому компонента є значення функції на i -му наборі значень змінних, i =0, 1,..., 2ⁿ-1.

Множину наборів значень змінних, на яких булева функція приймає значення 1, позначають N_f:

Множина , очевидно, повністю визначає функцію f.

Змінну х_i функції , називають істотною, якщо існує такий набір значень решти змін­них, що

Змінну, яка істотною не є, називаютьнеістотною, або фіктив­ною. Отже, змінна х_i функції неістотна (фіктивна), якщо

для довільних значень решти змінних. Це означає, що зміна знамен­ня в довільному наборі значень не змінює значення функ­ції. У цьому випадку функція по суті залежить від (n -1) змінної, тобто є функцією . У такому разікажуть, що функція g отримана із функції f вилученням фіктивної змінної, а функція f отримана ізg уведенням фіктивної змінної.Функції f та g називають рівними, якщо функцію g можна отримати з f шляхом уведення або вилучення фіктивних змінних.

Мета вилучення фіктивних змінних полягає в тому, що вони не впливають на значення функції, і з цієї точки зору є зайвими. Проте, іноді буває корисним уводити фіктивні змінні. Завдяки цьому довільну функцію п змінних можна зробити функцією довільної більшої кількості змінних. Тому, якщо задана скінченна множина булевих функцій { f ₁,..., fs }₉ то можна вважати, що всі ці функції зале­жать від одних і тих самих змінних x ₁,..., х_п. Зокрема, твердження, що всіх и-місних булевих функцій є передбачає, що беруть до уваги всі булеві функції від n змінних, у тому числі й функції з фік­тивними змінними.

Із ростом кількості змінних швидко збільшується кількість залеж­них від них булевих функцій. Наприклад, різних булевих функцій чотирьох змінних є тис., а п'яти -- млрд. Зі збільшенням кількості змінних таблиці для булевих функцій стають громіздкими і ними незручно користуватись.

Таблиця 8.2

x			x

Таблиця 8.3

Розглянемо аналітичний метод задания булевих функцій, тобто задания функцій формулами. Спочатку за допомогою табл. 8.2 та 8.3 визначимо функції, які називаютьлементарними.

Уведені елементарні функції мають такі назви.

1. f ₁(х)=0 - константа 0.

2. f ₂(х)=1 - константа 1.

3. f₃(х)=х - тотожна функція.

4. f ₄(х) = -заперечення х, читають " не х".

5. f ₅(х ₁, х ₂)= х ₁ х ₂-- кон'юнкція, читають " х ₁ і х ₂". Іноді для кон'юнкції використовують символи ∧ та &.

6. f ₆(х ₁, х ₂=х∨ х₂ -диз'юнкція, читають " х₁ або х₂".

7. f ₇(х ₁, х ₂)= х₁→ х₂ -імплікація, читають " із х₁ випливає х₂". Для імплікації іноді використовують символ ⊃.

8. f ₈(х ₁, х ₂)=х₁∼ х₂-- еквівалентність. Для її позначення використовують також символ ≡.

9. f ₉(х ₁, х ₂)= х₁⊕ х₂ -- додавання за mod2, читають як альтернативне " або" (" або..., або")

10. f ₁₀(х ₁, х ₂)=х₁|х₂ -- штрих Шеффера.

11. f ₁₁(х ₁, х ₂)= х₁↓ х₂ - стрілка Пірса.

За допомогою елементарних функцій можна зобразити будь-яку булеву функцію в аналітичній формі, тобто у вигляді формули. Для булевих функцій f ₁,..., f_m, по-перше, можливі будь-які підстановки одних функцій замість змінних в інші функції. По-друге, можливі будь-які перейменування змінних, наприклад, перейменування x ₃ в х ₂ породжує з функції f (х_і, х ₂, х ₃, х ₄) функцію трьох змінних f (х_і, х ₂, х ₃, х ₄) (у такому разі кажуть, що змінні х ₂ та х ₃ ототож­нені). Функцію, що одержана з f ₁,..., f_m деякою підстановкою їх одна в одну й перейменуванням змінних, називають суперпозицієюf ₁,..., f_m. Вираз, який описує суперпозицію та містить функціональні символи, круглі дужки та символи змінних, називають формулою.

Приклад 8.1. Тримісна булева функція задана формулою. Вона є суперпозицією функцій

f ₇(х ₁, х ₂)= х₁→ х₂, f ₄(х) = , f ₉(х ₁, х ₂)= х₁⊕ х₂. ▲

Формулу, яка містить лише змінні, дужки й символи функцій із множини Q називаютьформулою над Q.

Приклад 8.2. НехайQ={ , ху, х∨ у}, тоді вираз є формулою над Q. ▲

З метою зменшення кількості дужок у формулах уводять пріоритет операцій, які визначені відповідними функціями: 1) заперечення; 2) кон'юнкція; 3) усі інші операції. Крім того, уводять домовленість, що символ заперечення відіграє роль дужок, якщо він є над частиною формули

Приклад 8.3. Функція задана формулою . Задамо її таблицею. Процес розв'язування цієї задачі наведено у табл. 8.4. ▲

Таблиця 8.4

x y z	xz	y⊕ xz
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

Про формулу, яка задає функцію, кажуть також, що вона реалізує або зображає цю функцію.

На відміну від табличного, зображення функції формулою не єдине. Формули називають еквівалентними або рівносильними, якщо вони реалізують рівні булеві функції. Еквівалентність формул позначають символом =.

Приклад 8.4. Формули х→ y та( ∨ у)∨ z еквівалентні: х→ y=( ∨ у)∨ z . У цьому можна переконатись, побудувавши таблиці відповідних булевих функцій. Очевидно, змінна z у другій формулі фіктивна. ▲

Крім побудови таблиць є інший метод доведення еквівалентності формул - рівносильні (еквівалентні) перетворення.