Поняття булевої функції
У дискретної математики велику роль грають кінцеві функції.Кінцевою функцією називають відображення одного кінцевого множини в інше. Важливий клас таких функцій утворюють булеві функції.
Бульова функція (від n змінних) – це довільне відображення виду
тобто. Булева функція визначена на безлічі всіх n-елементних (при n ≥ 0) послідовностей (або n-компонентих кортежів) нулів і одиниць і приймає два можливі значення: 0 і 1.
З поняттям булевої функції тісно пов'язані поняття булевої константи та булева змінного*.
* У літературі з теорії булевих функцій зазвичай використовується термін "булева змінна" (в жіночому роді). Але так як у даїйом комплексі підручників прийнятий термін "перемійне" (середнього роду), ми пишемо скрізь "булево змінне".
Булева константа - це індивідуальна константа з областю значень. Таким чином, існують дві булеві константи: 0 і 1. За визначенням приймається, що кожна булева константа є так само булева функція від 0 перемійних (що цілком аналогічно визначенню нульарної операції).
Булево змінне - це ундuвuдное змінне з областю значень, тобто. це змінне, яке може приймати лише два значення: 0 і 1 (подібно до того, як дійсне змінне приймає довільне дійсне значення, а комплексне змінне - довільне комплексне значення). Тоді з використанням поняття бульова змінного ми можемо задати булеву функцію (6.1) записом у = f(x1, . .Змінні x1, . ,xn називають при цьомузмінними булевою фунпцuu f. Фіксуючи значення αi ∈ кожного змінного xi, отримуємо кортежα ˜ = (α1, . , αn) з множини n , званийнабором значень змінних x1, . ,xn, і відповідне значення функції f(α1, . , αn), яке буде значенням змінного у, зіставленим заданим значенням змінних x1, . , Xn.
Підкреслимо, що, якщо спеціально обумовлено неприємне, у вираженні у = f(x1, . ,xn) все змінні передбачаються попарно різними, тобто. пробігають кожне незалежно від інших безліч.
Поняття булевої функції можна надати інший зміст, розуміючи елементи множини як істинні значення, а саме розуміючи одиницю як "істину", а нуль як "брехня". Такі істинні значення можуть бути, як знаємо, зіставлені кожному висловлюванню. Тоді булева функція є певне правило, що дозволяє кожному фіксованому набору істиннісних значень, тобто. набору значень булевих змінних, зіставити те чи інше істинне значення. Так можна обчислити, наприклад, істиннісне значення складного висловлювання, складеного за певними правилами з простих висловлювань. Подібні складні висловлювання складаються за допомогою логічних операцій: "або", "і", "якщо. то" і т.п. казана логічна інтерпретація булевої функції дозволяє зрозуміти, чому бульова змінна часто називають логічним змінним *, а булеву функцію - логічною функцією (або функцією алгебри логіки).
* Традиційний термін: "логічна змінна".
Крім того, згідно з визначенням, булева функція від n змінних є відображення n-го декартового ступеня множини в множину , тобто. не що інше, як n-арна операція на множині . Тим самим логічна інтерпретація булевої функції узгоджується з її алгебраїчною інтерпретацією: функція булева є операція (в алгебраїчному сенсі цього слова) на безлічі істинніснихзначень. Тоді й поняття логічної операції, яке було запроваджено раніше (див. 1.1), виявляється окремим випадком загального поняття операції (див. 2.1).
Будемо позначати черезР безліч всіх булевих функцій (для всіх можливих значень n числа змінних), а черезР 2,n - безліч всіх булевих функцій від n змінних (для фіксованого n).
З визначення випливає, що
Отже, областю визначення будь-який булевої функції від n змінних є безліч n, тобто. булев куб* раемерності n. Елементи булева куба n називають n-мірними булевими векторами (або наборами). Число всіх елементів булева куба n становить 2 n. Елементи булева куба також називатимемо його вершинами.
* Використовуються також терміни: одиничний куб розмірності n, n-мірний одиничний куб; замість слова "куб" говорять також "гіперкуб".
Булев куб n є носієм булевої алгебриB n (це ж позначення часто використовуватимемо і для відповідного булева куба). Але в будь-якій булевій алгебріА = (А, ∨, ∧,0,1 ) визначається, як відомо, природне відношення порядку ≤ так, що для довільних а, b ∈ А співвідношення а ≤ b виконується тоді й тільки тоді, коли а ∨ b = b (або, що рівносильне, а ∧ b = а). Нагадаємо (див. 3.4), що булева алгебраB n є не чим іншим, як n-й декартовим ступенем двоелементної булевої алгебриB = (, ∨, ∧, 0, 1) . Відповідно до загального принципу поширення відношення порядку на декартовий добуток множин (див. 4.5), для довільних двох наборів α ˜ = (α1, . , αn) і β ˜ = (β1, . , βn) зB n має місце α ˜ ≤ β ˜ . тоді й лише тоді, коли αi ≤ βi для кожного i = 1,n, тобто. αi ∨ βi = βi.
Іншими словами, α ˜ ≤ β ˜ тоді і тільки тоді, коли αi = βi або αi = 0, а βi = 1 длякожного i = 1, n. Якщо існує хоча б одне i, для якого виконується αi = 0, а βi = 1, то має місце сувора нерівність α ˜ ˜ . Зокрема, якщо існує одно таке i, то набір β ˜ домінує над набором α ˜ , оскільки ясно, що в цьому випадку не можна знайти такий набір γ ˜ , що α ˜ ˜ ˜ .
Приклад 6.1. У булевому кубі B 4
(0, 0, 1, 1) n називатимемобулевим порядком.
Бульовий куб як упорядковане безліч, можна зобразити у вигляді діаграми Хассе. На рис. 6.1 наведено діаграми Хассе для булевих кубів розмірності від 0 до 4.
Інший спосіб наочного зображення булева куба заснований на тому, що діаграма Хассе будь-якої кінцевої впорядкованої множини А може бути задана у вигляді орієнтованої мережі, так що дуга з вершини, зіставленої елементу х ∈ А,
веде у вершину, зіставлену елементу у ∈ А, тоді і тільки тоді, коли у домінує над х і кожен рівень мережі складається з вершин, зіставлених попарно незрівнянним елементам множини А (тобто елементам деякої антиланцюжка в А). Входи мережі зіставлені мінімальним, а виходи – максимальним елементам А.
Кожен рівень представляє булев кубB n мережі складається з усіх вершин, відповідних наборам, у яких рівно k (0 ≤ k ≤ n) компонент відмінні від нуля (множина всіх таких наборів для фіксованого k називають k шаром булева кубаB n).
Мережа, що служить зображенням булева куба розмірності n, називатимемо булевою n-мережею або просто булевою мережею, якщо згадка про розмірність опускається. Так як булев куб має найменший елемент - нульовий набір і найбільший елемент - одиничний набір, то кожна булева мережа має єдиний вхід (позначений нульовим набором) і єдиний вихід (позначений одиничним набором).
На рис.6.2 наведено зображення булева кубаB 4 у вигляді мережі.
Крім булева порядку корисно також ввести на булевому кубі інше відношення порядку, яке ми називатимемо лексикографічним порядком, використовуючи позначення ⪯. Нехай α ˜ , β ˜ ∈B n (для довільного фіксованого n). За визначенням, α ˜ ⪯ β ˜ , якщо
Кожна із сум у нерівності (6.2) є нічим іншим, як уявлення деякого натурального числа (включаючи і нуль) у двійковій системі числення (при числі розрядів, рівних фіксованої розмірності n). На кожен булев вектор можна дивитися як на таке уявлення (двійковий код) натурального числа, і лексикографічний порядок на булевому кубіB n є не що інше, як природний числовий nрядок на підмножині ℕ ∪ (за умови, що числа задані у двійковій системі числення)*.
* Суворіше: впорядковане безліч (B n , ⪯) ізоморфно підмножини ⊂ ℕ ∪ з природним числовим порядком.
Зауважимо, що ставлення лексикографічного порядку є, на відміну булева порядку, ставленням лінійного порядку.
Приклад 6.2. Набір (1, 0, 1) як двійковий код числа 5 = = 1 · 2 2 +0 · 2 1 + 1 · 2 0 лексикографічно більше набору (0, 1, 1), службовця двійковим кодом числа 3, але при цьому зазначені набори не можна порівняти по відношенню до булева порядку. #
Проте лексикографічний порядок щодо булевих кубів грає допоміжну роль. Зокрема, при зображенні булевих кубів (у вигляді діаграм Хассе або у вигляді мережі) прийнято розташовувати вершини кожного k-шару в лексикографічному порядку (за зростанням - ліворуч або зверху вниз). Скрізь надалі, розмірковуючи про булевий куб як про впорядковану множину, ми маємо на увазі булевий порядок.
Гранню булева куба розмірності n-k, де n - розмірність булева куба називають безліч наборів, що мають не менше k однакових компонентів.
Грань розмірності n - kB n буде визначена, якщо фіксувати k номерів 1 ≤ i1 ≤ . ≤ ik ≤ n і k констант σ1. σk з множини. Тоді грань, що позначається якB n,i1. ik σ1. σk є безліч всіх таких α ∈B n , що αi1 = σ1. σik = σk. У цьому кортеж номерів (i1, . ik) називають напрямом граніB n,i1. ik σ1. σk. Якщо число n -k, що визначає розмірність грані, дорівнює 1 (тобто k = n -1), то таку грань називають рубом булева кубаB n . Таким чином, ребро - це безліч, що складається з двох наборів, один із яких домінує над іншим (у сенсі булева порядку). Іншими словами, ці два набори відрізняються один від одного значенням єдиної компоненти. Для ребра булева куба використовуватимемо позначення [а, ,8], вважаючи, що другий набір домінує над першим. Будь-яка вершина булева куба вважається гранню розмірності 0.
Можна показати, що число всіх граней розмірності n - k становить 2 k · C k n.
Приклад 6.3. У чотиривимірному булевому кубіВ 4 напрям тривимірної грані задається фіксуванням одного з номерів від 1 до 4 і фіксуванням значення відповідної компоненти наборів, що належать цій грані. На рис. 6.1 виділено ребра грані 4,1 0 . Ця грань складається з восьми наборів:
(0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 1, 0), (0, 0, 1, 1),
(0, 1, 0, 0), (0, 1, 0, 1), (0, 1, 1, 0), (0, 1, 1, 1).
На рис. 6.1 виділені всі ребра булева кубаВ 3 мають напрям (1, 2). #
Грані булева куба, що мають один і той же напрямок, називаютьпаралельними. Дві паралельні граніВ n,i1. ik σ1. σk і n,i1. ik γ1. γk називаютьсусідними, якщо один із наборів (σ1, . σk) і (γ1, . γk) домінує над іншим. На рис. 6.1 граніB 4,1 0 іB 4,1 1 сусідні, так само як і грані (ребра)B 3,1,2 0,0 іB 3,1,2 0,1. Але ребраB 3,1,2 1,0 іB 3,1,2 0,1 є сусідніми.
Неважко здогадатися, що кожна грань розмірності n - k булева кубаВ n сама є булевим кубом розмірності n - k і містить, отже, 2 n-k вершин. Точніше кажучи, ця грань разом із ставленням порядку, індукованим булевим порядком наВ n , буде впорядкованим безліччю, і ізоморфним булеву кубуВ n-k (з булевим порядком на ньому). Тому часто грані булева куба називають йогопідкубами.
У той же час булев кубВ n ізоморфно вкладається (декількома способами) у булев куб більшої розмірності, а саме булев кубВ n вкладається (як грань) у булев кубВ n+k , k ≥ 1, стільки способами, скільки існує різних n-мірних граней в кубі розмірності n + k, тобто. 2 k · C k n+k способами. Так, одновимірний кубB вкладається в двовимірнийB 2 чотирма способами - як одна з його чотирьох одномірних граней (тобто як одне з чотирьох ребер, див. рис. 6.1) .
Домовимося надалі записувати конкретні набори (елементи булева куба відповідної розмірності) без дужок і ком, тобто. писатимемо не (0, 1, 0, 1), а 0101 (якщо, звичайно, це не веде до непорозумінь).
На закінчення знайдемо потужність безлічі всіх булевих функцій від змінних n для фіксованого n. Оскільки кожна булева функція відображає безліч з 2 n елементів в двоелементне безліч, а потужність безлічі всіх відображень з n-елементної множини в m-елементне дорівнює, як відомо, m n , то потужність множиниP 2,n дорівнює 2 2 n. Узокрема, при n = 0 отримуємо дві булеві константи: 0 та 1.
Зауваження 6.1. Оскільки булева функція від n змінних є в той же час і n-арною операцією на множині, то при n = 0 отримуємо нульарну операцію. Ясно, що на безлічі існують дві нульарні операції: 0 і 1, які є не що інше, як нуль та одиниця двоелементної булевої алгебри.