Курсова робота: Системи булевих функцій

Зміст

1. Повні системи булевих функцій

2. Скорочені й тупикові диз'юнктивні нормальні форми

3. Алгоритм Квайна й Мак-Класки мінімізації булевої функції

4. Геометричне подання логічних функцій

5. Геометричний метод мінімізації булевої функції

6. Мінімізація булевої функції за допомогою карти Карно

7. Побудова оптимальних контактно-релейних схем

Бібліографічний список

1. Повні системи булевих функцій

Нагадаємо, що булевої функцією називають функцію , у якої всі незалежні аргументи й сама функція є логічними змінними, приймаючими тільки два значення: 0 і 1. Ці функції можуть бути задані аналітично у вигляді формули (ПФ) геометрично або за допомогою таблиць істинності. Наприклад, всі елементарні булеві функції двох змінних представлені таблицею істинності 1.

Таблиця 1

№	X1= 0 X2= 0	0 1	1 0	1 1	fk (X1, X2)
	0	0	0	0	f1 = 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
	1	0	0	0
	1	0	0	1
	1	0	1	0
	1	0	1	1
	1	1	0	0
	1	1	0	1
	1	1	1	0
	1	1	1	1

Функція f₁ називається нульовою; f_{16 -} одиничною; f₂ - кон'юнкцією; f₈ - диз'юнкцією; f₁₁ і f₁₃ - запереченнями Х₁ і Х₂ відповідно; f₁₂ і f₁₄ - імплікаціями; f₃ і f₅ - коімплікаціями; f₁₀ - еквівалентцією; f₇ - додаванням по модулі дві або розділова диз'юнкції; f₉ - стрілки Пірса (функцією Вебба); f₁₅ - штрихом (функцією) Шеффера.

Функцію, отриману з елементарних шляхом перенумерації аргументів і підстановки замість аргументів у деяких інших булевих функцій, називають суперпозицією функцій. Неважко переконатися, що будь-яка булева функція від n аргументів є суперпозицією елементарних функцій, заданих табл.1. Наприклад, функція є суперпозицією елементарних функцій: заперечення, диз'юнкції, імплікації.

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

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

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

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

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

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

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

Якщо система - повна й кожна з функцій f₁, f₂,.,f_m може бути виражена за допомогою суперпозицій через функції g₁, g₂,…,g_k, те система також повна.

Приклад 1. Довести повноту системи .

Для доказу скористаємося системою , повнота якої вже доведена, ці функції можна виразити через g₁ і g₂ по формулах:

f₁=g₁, ,

отже система функцій є повною.

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

Функція f = (Х₁, Х₂,., Х_n) називається функцією, що зберігає константу 0 (1), якщо

f (0,0,.0) = 0, (f (l, 1.1) = 1).

Функція f (X₁,X₂,.,X_n) називається самодвоїстої, якщо

f (X₁,X₂,., X_n) = .

Функція f (X₁,X₂,.,X_n) називається монотонної, якщо для будь-яких двох наборів X = (X₁,X₂,…,X_n) і Y = (Y_l, Y₂,.,Y_n), таких, що X Y (для будь-якого i X_i Y_i) має місце нерівність:

f (X₁,X₂,., X_n) f (Y_l, Y₂,.,Y_n).

Функція f (X₁,X₂,., X_n) називається лінійної, якщо

f (X₁,X₂,., X_n) = ,

де .

Перші чотири властивості перевіряються за допомогою таблиці істинності, а для перевірки лінійності функції необхідно побудувати багаточлен Жегалкина. Наприклад, з табл.1 треба, що f₂ = X₁ÙX₂ і f₈ = X₁ÚX₂ - функції, що зберігають константу 0; f₁₀ = X₁↔X₂ - функція, що не зберігає константу 0, але яка збірегає константу 1; f₇ = X₁ X_{2 -} функція; f₂, f_{g -} монотонні функції; f₁₄ = X₁→X_{2 -} немонотонна функція, тому що монотонність порушується (0, 0) і (1, 0); f₃ - нелінійна функція, тому що відповідний їй багаточлен Жегалкина X₁ + X₂ + X₁X₂ - нелінійна.

Теорема Поста. Система D = {f₁, f₂,. f_m} булевих функцій є повною тоді й тільки тоді, коли серед функцій цієї системи існують: функція, що не зберігає константу 0, функція, що не зберігає константу 1, а також нелінійна, й немонотонна функції.

Приклад 2. Довести повноту системи .

Рішення. Нехай K₀ - клас функцій, що зберігають константу 0; К₁ - клас функцій, що зберігають константу 1; Кл, K_c, К_м - класи лінійних, самодвоїстих і монотонних функцій відповідно.

Складемо таблицю Поста наступного виду.

Таблиця 2

№	φi	K0	К1	Кл	Kc	Км
1	X1 X2	+	-	+	-	-
2	X1 Ú X2	+	+	-	-	+
3	1	-	+	+	-	-

Знак "+", що коштує на перетинанні i - й рядка й j-гo стовпця цієї таблиці, показує, що функція φ_i - належить відповідному класу, записаному в j-ом стовпці,

З табл.1 бачимо, що φ₁ = f₇ не зберігає константу 1 і не є монотонної, φ₂ = f₈ - нелінійна й функція, φ₃ = f₁₆ не зберігає константу 0. Отже, всі умови теореми Поста виконані, і задана система є повною.

Приклад 3. Довести, що система {|} є базисом.

Рішення. Розглянута система складається з однієї функції f₁₅ (функції Шефера). З табл.1 бачимо, що f₁₅ - функція, що не зберігає 0 і 1, немонотонна (монотонність порушується на наборах (1, 0) і (1, 1),, тому що , a двоїста функція нелінійна, тому що багаточлен Жегалкина для цієї функції має вигляд: 1 + X₁X₂. Отже, система {f₁₅} = {|} задовольняє всім умовам теореми Поста і є базисом.

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

2. Скорочені й тупикові диз'юнктивні нормальні форми

Відомо [4], що всяку булеву функцію можна записати, причому єдиним образом, у ДНФ, тобто у вигляді диз'юнкції елементарних кон'юнкцій (суми добутків). У зв'язку із цим можна порушувати питання про відшукання для заданої функцій такий ДНФ, що була б найбільш простий у порівнянні з її іншими ДНФ.

ДНФ називається мінімальної, якщо вона містить у порівнянні з іншими еквівалентними їй формами мінімальна кількість букв (при підрахунку враховується кожне входження букви у формулу).

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

Елементарну кон'юнкцію φ_до назвемо імплікантою булевої функції f, якщо не існує такого двійкового набору змінних, при якому функція φ_до приймає значення 1, а функція f - значення 0, то ecть φ_k Ú f = f.

Для того щоб перевірити чи є задана елементарна кон'юнкція функції f, треба всім змінним, які входять у цю кон'юнкцію без знака заперечення, додати значення 1, а тим змінним, які входять із запереченням - значення 0. Тоді елементарна кон'юнкція буде мати значення 1. Після цього треба, перевірити, чи приймає функція f значення 1 при будь-яких значеннях інших змінних. Надалі для спрощення записи булевих функцій знаки кон'юнкції будемо заміняти знаками множення або просто опускати.

Приклад 4. Перевірити, чи є одночлени й імплікантами булевої функції

.

Рішення. Думаючи в першому випадку Х₁ = 1, X₂ = 1, маємо φ₁ = l і φ₂ = l і

,

отже, φ₂ - імпліканта заданої функції.

У другому випадку думаємо X₁ = 0, X₂ = l. Тоді

φ₂ = 1, а ,

отже, φ₂ не є імплікантою функції f.

Справедливі наступні твердження:

1. Якщо імпліканти булевої функції f, то й також є її імплікантами.

2. Якщо функція є імпліканта функції f, то функції також є імплікантами функції f.

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

Скороченої ДНФ даної булевої функції називається її ДНФ, складена тільки із простих імплікант.

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

.

Наприклад,

Для будь-якої заданої функції скорочена ДНФ є єдиною. Однак вонa може бути надлишкової внаслідок тогo, що деякі прості імпліканти цієї суми покриваються сукупностями інших доданків. Такі імпліканти називають зайвими, і вони можуть бути вилучені без порушення формул.

Скорочена ДНФ, з якої вилучені всі зайві імпліканти, називається тупикової ДНФ

Виключення зайвих імплікант зі скороченої ДНФ проводиться за допомогою правила поглинання: диз'юнкцію двох елементарних кон'юнкцій, з яких одна повністю втримується й інший, можна замінити кон'юнкцією, що має менший ранг, наприклад, X Ú XF = X,

.

Правила склеювання, і поглинання легко доводяться за допомогою таблиць істинності.

Приклад 5. Спростити булеву функцію .

Рішення. Ця функція містить тільки прості імпліканти, тобто є скороченою Однак вона надлишкова, тому що одночлен Х₁X₂ можна видалити. Після цього одержимо функцію:

.

Приклад 6. Знайти мінімальну ДНФ для функції

.

Рішення. Склеюючи перший і третій одночлени по змінною Х₂, одержимо Х₁X₃X₄. З першого й четвертого, а потім із друг і третього складаються після склеювання одержимо відповідно X₁X₂X₃, і т.д. Остаточний список імплікант має вигляд

У цьому списку є два одночлени X₁X₃ і Х₂Х₃Х₄, які не поглинають інших одночленів із цього списку, отже, є простими імплікантами. Тому скорочена ДНФ має вигляд , на ж є й мінімальної.

Спочатку одержують скорочену ДНФ. Далі однозначний процес переходить у процес побудови всіх тупикових ДНФ і, нарешті, з тупикових ДНФ виділяються мінімальні. Самим трудомістким етапом цього процесу є побудова тупикових ДНФ. Його можна небагато спростити, заздалегідь видаливши частину членів скороченої ДНФ, що не беруть участь у побудові тупикових ДНФ і тим самим скоротити кількість підмножин, що переглядаються

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

3. Алгоритм Квайна й Мак-Класки мінімізації булевої функції

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

1. Привести булеву функцію до СДНФ.

2. У СДНФ зробити всі можливі склеювання Отримана після цього ДНФ є скороченої, але серед простих імплікант можуть виявитися зайві.

3. Перейти від скороченої ДНФ до мінімального, тобто виключити зайві імпліканти. Для цього рекомендується скористатися імплікантою матрицею, у якій кожному рядку відповідає проста імпліканта, а кожному стовпцю - елементарна кон'юнкція, що містить всі змінні. СДНФ заданої функції Ця матриця заповнюється в такий спосіб під конституентами, у які входить дана проста імпліканта, ставиться мітка "1" Для знаходження мінімального покриття функції необхідно видалити з таблиці деякі зайві прості імпліканти Із цією метою реалізується наступний алгоритм.

1. Виділення ядра Квайна. Якщо в якому-небудь стовпці матриці є тільки одна 1, то імпліканта, що перебуває у відповідному стовпці, не є зайвою й повинна бути включена в мінімальне покриття функції. Такі імпліканти називаються істотними, а їхню сукупність називають ядром Квайна.

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

2 Стиск по стовпцях або рядкам. З матриці викреслюється той стовпець, у який повністю входить який-небудь інший стовпець і той рядок, що повністю покривається інший.

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

Приклад 7 Мінімізувати булеву функцію

.

Рішення. Функція задана в ДНФ, тому займемося відразу відшуканням простих імплікант, проводячи операцію склеювання. Для цього представимо кожну елементарну кон'юнкцію двійковим набором, ставлячи на k-ом місці 0, якщо Х_k входить із запереченням, 1 - якщо без заперечення й знак "-", якщо ця змінна не входить у кон'юнкцію Тоді функція прийме вид:

.

Розіб'ємо ці набори на класи, у кожному з яких утримуються набори з однаковим числом одиниць і розташуємо їх у порядку зростання суми всіх чисел набору (рис 2 а)

Для виключення змінних за правилом склеювання зрівняємо всі набори всіх суміжних класів. Якщо при цьому яка-небудь змінна виключається, то в розряд, що відповідає цієї змінної, записуємо прочерк. Наприклад, двійкові набори 0100 і 0101 утворять набір 010-. Всі отримані набори знову розбиваємо на класи. Поєднуємо знову набори із двох суміжних класів, причому порівнянню підлягають тільки ті, у яких прочерк перебуває в тому самому розряді, одержуємо новий набір імплікант (мал.2 в). Неважко переконатися, що подальше об'єднання наборів неможливо, отже, всі отримані імпліканти - прості.

Побудуємо матрицю (табл.3 а). Виділяючи стовпці, що містять по одній одиниці, знаходимо істотні імпліканти, що утворять ядро Квайна: 0-0 - 0-0. При цьому перша з них є істотною для 0000, 0001, 0100, 0101, а друга - для 0000, 0010, 1000, 1010. Викреслюючи стовпці із цими й рядка з істотними імплікантами, одержимо табл.3 б. У цій таблиці немає стовпців, що містять тільки одну одиницю, отже істотних імплікант у цій таблиці немає і ядро Квайна складається із двох імплікант, знайдених вище: 0-0 - і - 0-0.

Переходимо до операцій стисла по рядках і стовпцям. Другий рядок табл.3 б поглинає першу, а четверта - третю, тому першу й третю рядки можна викреслити (табл.3 в).

У табл.3 у перший стовпець повністю входить у четвертий, а другий - у третій, Після викреслювання четвертого й третього стовпців таблиця приймає вид 3 р. Із цієї таблиці видно, що імпліканта 111 - є зайвої, тому що не містить одиниць у жодному стовпці, а дві інші входять у мінімальне покриття. Таким чином, задана функція має чотири простих імпліканти: 0-0-, - 0-0, 1-і0 і - 111. Поєднуючи їхнім знаком диз'юнкції, одержуємо мінімальну ДНФ у вигляді

.

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

4. Геометричне подання логічних функцій

Позначимо через Еⁿ множину всіх наборів (α₁,., α_η), що складаються із чисел нуль і одиниця. Множина Еⁿ називається n-мірним кубом, а набір (α₁,., α_η) - вершинами куба.

Нехай σ₁,., σ_r - фіксований набір чисел з 0 і 1. Множина всіх вершин (α₁,., α_η) куба Еⁿ таких, що α_i1 = σ₁, α_i2 = σ₂,., α_ir = σ_r, 1 < i₁ < i₂ <.< i_r, називається (n - r) - мірною гранню. Очевидно, що (n - r) - мірна грань є (n - r) - підкубом куба Еⁿ.

Наприклад, у тривимірному кубі Е³ набори (0,0,1) і (0,0,0) утворять одномірну (n = 3, r = 2) грань (ребро), а набори (1,0,0), (1,0,1), (1,1,0), (1,1,1) - двомірну грань.

Нехай f (X₁,X₂,…,X_n) - довільна булева функція. Їй зіставляється у відповідність підмножина Ν_f вершин куба Еⁿ, таких що (α₁,., α_η) N_f тоді й тільки тоді, коли f (α₁,., α_η) = l Очевидно, що по підмножині N_f вихідна функція f (X₁, X₂.,., Χ_n) відновлюється однозначно. У такий спосіб геометричний спосіб завдання булевої функції полягає в завданні множини вершин n-мірного куба Еⁿ, у яких дана функція щира.

Приклад 8. Нехай функція f (X₁, X₂, Х₃) задана табл.4. Скласти для неї множина N_f.

Таблиця 4

X1	X2	X3	f (X1, X2, Х3)
0	0	0	1
0	0	1	0
0	1	0	0
1	0	0	1
0	1	1	0
1	0	1	1
1	1	0	1
1	1

1

1

Рішення. Очевидно, що N_f = { (0,0,0), (1,0,0), (1,0,1), (1,1,0), (1,1,1) }. Множина N_f зображена на мал.3.

Мал.3

Нагадаємо [1], що для будь-який булевої функції існує її подання в СДНФ. Причому в алгоритмі побудови СДНФ використовуються тільки ті набори значень, при яких функція дорівнює одиниці [3]. Це дозволяє проінтерпретувати геометричне подання функції в такий спосіб. Розглянемо тривимірний куб і занумеруємо вершини так, як показано на мал.4.

Тоді його грані (двовимірні підкуби) можна розглядати як

Ребрами даного куба (одномірними підкубами) будуть, наприклад, , і т.д.

Приклад 9. Побудувати модель куба, що відповідає функції:

.

Рішення. Першому доданку відповідає вершина 2, другому - вершина 6, третьому - вершина 3, четвертому - вершина 8, п'ятому - вершина 4 (мал.5).

Мал.5

Приклад 10. Дано модель куба з позначеними вершинами (мал.6). Скласти СДНФ для даної булевої функції

Рішення. Вершині 1 відповідає кон'юнкція , вершинам 3 і 4 кон'юнкція й відповідно; вершинам 5 і 6 - кон'юнкції й . Отже, шукана СДНФ має вигляд

.

Помітимо, що для функцій, що залежать від чотирьох і більше змінних, геометричне подання застосовується дуже рідко, тому що важко побудувати наочну модель n-мірного куба при n > 3. Тому в цьому й наступному параграфах ми будемо розглядати тільки булеві функції трьох аргументів, хоча все викладене справедливо для інших функцій, що залежать від великої кількості аргументів.

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

5. Геометричний метод мінімізації булевої функції

Розглянемо елементарну кон'юнкцію рангу r (тобто утримуючу r змінних)

де ε = 0,1; . Очевидно, що множина N_k, що відповідає кон'юнкції К, є (3 - r) - мірна грань. Число r називається рангом цієї грані.

Приклад 11.

,

,

відповідають грані (мал.7 а, б, в), N_k1={7,8}, N_k2={8,6}, N_k3={6,2,4,8}, що мають ранги 2, 2, і 1. Перші дві грані є одномірною гранню (ребром), а третя - двовимірною гранню.

Мал.7

Відзначимо очевидні властивості уведеної відповідності між булевої функцією f і підмножиною N_f.

Якщо , то

.

Зокрема, якщо f (X₁, Χ₂, X₃) володіє ДНФ, тобто , те й тобто ДНФ функції f відповідає покриття множини Ν, гранями .

Приклад 12. Розглянемо представлену в СДНФ функцію

.

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

.

ДНФ відповідають два покриття множини N_f:

,

,

де N_k1={2}, N_k2={6}, N_k3={3}, N_k4={8}, N_k5={4}, N_k10={2,6,8,4}, N_k20={4,3}. Одне із цих покриттів - крапкове, друге складається з ребра й двовимірної грані.

Нехай r_i - ранг гpани Ν_ki (він дорівнює рангу кон'юнкції k_i). Число r, певне формулою

,

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

Приведемо також визначення скороченої й тупикової ДНФ c геометричної точки зору.

Грань N_k, що втримується в N_f, називається максимальної відносно N_f, якщо не існує грані , такий, що

1)

2) розмірність грані більше розмірності грані N_k.

Приклад 13. Нехай f (X₁, Х₂, X₃) - функція, задана табл.4 і Тоді грані Ν_k1 і N_k3 є максимальними, a N_k2 не максимальна для N_f, тому що й розмірність N_k3 більше розмірності N_k2.

Кон'юнкція К, що відповідає максимальної грані N_k, називається простою імплікантою функції f.

ДНФ, що є диз'юнкцією всіх простих імплікант функції f, називається скороченої ДНФ.

Покриття множини N_f, що складає з максимальних відносно N_f граней, називається що не приводиться, якщо сукупність граней, що виходить із вихідної шляхом викидання будь-якої грані, не буде покриттям N_f.

множини N_f називається тупикової в геометричному змісті.

Теорема. Поняття тупикової ДНФ і тупикової ДНФ у геометричному змісті еквівалентні.

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

Нанести множина N_f, на тривимірний куб. Використовувати або табличне завдання функції, відзначивши вершини, у яких f (X₁, Χ₂, Χ₃₎ = 1, або СДНФ функції й тоді кожному що складається СДНФ поставити у відповідність вершину (див. розділ 5).

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

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

Щоб одержати мінімізовану форму, треба вибирати ребра, що покривають вершини, так, щоб меншим числом ребер покрити всі відзначені вершини.

Приклад 14. Мінімізувати функцію f (X₁, X₂, Х₃), задану табл.4.

Рішення. Множина N_f для зазначеної функції зображене на мал.3. Тому що вершини 2, 4, 6, 8 належать одній грані Χ₁, вершини 7 і 8 належать ребру, те мінімізована форма функції f має вигляд

.

Приклад 15. Мінімізувати записану в СДНФ функцію

.

Рішення. Відзначимо на моделі куба елементарні кон'юнкції: першої кон'юнкції відповідає вершина 6, другий - вершина 5, третьої - вершина 8, четвертої - вершина 2 (рис 8). Таким чином, множина N_{f -} побудовано. Жодна грань не відзначена повністю, тому переходимо до кроку 4 алгоритми.

Мал.8

Вершини 5 і 6 належать одному ребру , вершини 6 і 8 - ребру , отже, мінімізована форма має вигляд:

.

Приклад 16. Мінімізувати функцію f (X₁,X₂,X₃), задану табл.5.

Таблиця 5

Х1	1	1	1	0	1	0	0	0
Х2	1	1	0	1	0	1	0	0
Х3	1	0	1	1	0	0	1	0
f (X1,X2,X3)	1	1	1	1	1	1	0	0

Рішення. Побудуємо модель куба, що відповідає цієї функції (мал.9).

Мал.9

Грані (1, 2, 3,4) відповідає X₂, грані (2, 4, 6,8) - Х₁, отже, мінімізована форма має вигляд

.

Відзначимо, що при n = 3 геометричний метод мінімізації булевих функцій аналогічний мінімізації за допомогою прямокутної таблиці, названої, картою (картою Карно).

6. Мінімізація булевої функції за допомогою карти Карно

Карта Карно являє собою таблицю для завдання логічних функцій у СДНФ. Наприклад, для функції, заданої табл.5, карта Карно представлена в табл.6.

Розташування кліток у таблиці дозволяє легко визначити члени, що склеюються між собою, тому що кожній клітці карти Карно відповідає вершина куба. Помітимо, що сусідніми вважаються не тільки поруч варті осередки, але й осередку, що перебувають на протилежних кінцях будь-якого стовпця й будь-якого рядка.

Таблиця 6

Так, склеюючи констітуенти, розташовані в другому й третьому рядках табл.6, одержуємо імпліканту - X₂, а констітуентам двох останніх рядків відповідає імпліканта Х₁ - . Отже, мінімальна форма заданої булевої функції має вигляд (див. приклад 16)

.

Приклад 17. Мінімізувати за допомогою карти Карно функцію f (X₁, Х₂, Χ_3), задану табл.4.

Рішення. Побудуємо для карту (табл.7)

Таблиця 7

Об'єднаємо сусідні клітки, що відповідають одиничним значенням функції f, у максимальні інтервали, як показано в табл.7. Зіставимо кожному максимальному інтервалу імпліканти Χ₁ і . Отже, мінімальна форма має вигляд:

.

Приклад 18. Мінімізувати булеву функцію

.

Рішення. Використовуючи таблиці істинності, побудуємо для заданої функції f карту Карно (табл.8).

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

Таблиця 8

.

Якщо булева функція f залежить від чотирьох аргументів, то за допомогою карти можна знаходити скорочену ДНФ.

Приклад 19. Нехай функція f (X₁, X₂, Х₃, Х₄) задана та6л.9. Побудувати скорочену ДНФ.

Рішення. Максимальні інтервали, що з'єднують клітки, що відповідають одиничним значенням функції f, вибираються так, як показано в табл.9. Зіставляючи їм прості імпліканти, одержимо скорочену Д??.

Таблиця 9

7. Побудова оптимальних контактно-релейних схем

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

За заданою схемою скласти відповідну їй булеву функцію.

Привести цю функцію до ДНФ.

Мінімізувати записану в ДНФ булеву функцію одним з описаних вище способів

Побудувати релейно-контактну схему, що відповідає мінімальної ДНФ.

Приведемо приклади.

Приклад 20. Побудувати оптимальну релейно-контактну схему, еквівалентну схемі на мал. l0.

Рішення.

1. Складемо за цією схемою булеву функцію

.

2. Ця функція записана в ДНФ, тому попередніх її перетворень не потрібно.

3. Склеюємо перший член із третім:

.

4. Будуємо релейно-контактну схему, що відповідає отриманої функції:

У спрощеній схемі замість 9 контактів використовуються тільки 5.

Приклад 21. Побудувати оптимальну релейно-контактну схему, еквівалентну схемі на мал.12.

Рішення.

1. Заданій схемі відповідає булева функція

.

2. Представимо цю функцію в ДНФ

.

3. Склеюючи другий член із четвертим, а потім проводячи операцію поглинання, одержимо

.

4. Будуємо оптимальну релейно-контактну схему (мал.13).

Вправи

1. Мінімізувати за допомогою карт Карно наступні булеві функції:

а)

;

б) ;

в)

;

г)

;

д)

;

е)

.

2. Мінімізувати булеві функції методом Квайна:

а) ;

б)

;

в)

;

г)

.

3. Побудувати для булевої функції модель куба й мінімізувати її. Функція f задана табл.10, 11, 12.

Таблиця 10

X1

X2

X3

	f (X1,X2,X3)
0	0	0	1
0	0	1	0
0	1	0	1
1	0	0	0
0	1	1	1
1	0	1	1
1	1	0	0
1	1	1	1

Таблиця 11

X1	X2	X3	f (X1,X2,X3)
0	0	0	0
0	0	1	0
0	1	0	1
1	0	0	1
0	1	1	0
1	0	1	0
1	1	0	1
1	1	1	1

Таблиця 12

X1	X2	X3	f (X1,X2,X3)
0	0	0	1
0	0	1	0
0	1	0	1
1	0	0	1
0	1	1	1
1	0	1	0
1	1	0	1
1	1	1	0

4. Побудувати для булевої функції f (X₁,X₂,X₃), записаної в СДНФ, модель куба й мінімізувати функцію f:

a) ;

б) ;

в) .

5. Для заданої моделі куба (мал.14 а, б, в) записати булеву функцію в СДНФ і мінімізувати її.

Мал.14

6. Побудувати оптимальні контактно-релейні схеми для схем, заданих на мал.15-18.

Бібліографічний список

1. Нефедов В.М. Курс дискретної математики / В.М. Нефедов, В.О. Осипова - К., 2003

2. Яблонський С.В. Введення в дискретну математику - К., 2004

3. Леденєва Т.М. Спеціального глави математики. Дискретна математика: посібник - К., 2004

4. Кретова Л.Д. Елементи математичної логіки: методичні вказівки до практичних і індивідуальних занять. - К., 2003