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

ЗМІСТ

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

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

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

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

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

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

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

Вправи

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

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

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

Таблиця 1

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

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

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

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

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

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

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

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

Згідно з цим визначенням система булевих функцій не є базисом. Дійсно, застосовуючи закони де - Моргана

, ,

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

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

Якщо система - Повна і будь-яка з функцій f _1, f ₂ ,..., f _m може бути виражена за допомогою суперпозицій через функції g _1, g _2, ..., g _k, то система також повна.

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

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

f ₁ = g _1, ,

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

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

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

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

Функція f (X _1, X ₂ ,..., X _n) називається самодвойственной, якщо

f (X _1, X ₂ ,..., X _n) = .

Функція f (X _1, X ₂ ,..., X _n) називається монотонною, якщо для будь-яких двох наборів X = (X _1, X _2, ..., X _n) і Y = (Y _l, Y _2, .. ., Y _n), таких, що X Y (для будь-якого _i X i Y _i) має місце нерівність:

f (X _1, X ₂ ,..., X _n) f (Y _l, Y ₂ ,..., Y _n).

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

f (X _1, X ₂ ,..., X _n) = ,

де .

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

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

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

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

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

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

Таблиця 2

№	φ i	K 0	До 1	К л	K c	До м
1	X 1 X 2	+	-	+	-	-
2	X 1 Ú X 2	+	+	-	-	+
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 _2. Отже, система {f _15} = {|} задовольняє всім умовам теореми Посту і є базисом.

Досліджуючи різні набори функцій, можна показати, що для різних булевих функцій двох змінних існують 17 різних базисів, в кожному з яких не можна викреслити ні одну функцію без втрати повноти. Найбільш поширеними з них є кон'юнктивний базис Буля , Диз'юнктивний базис Буля . імплікатівниі базис . баз ис Шеффера {|}, базис Жегалкина .

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

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. Знайти мінімальну ДНФ для функції

.

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

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

,

ο на ж є і мінімальної

У загальному випадку процес побудови мінімальних ДНФ може бути охарактеризований наступною схемою.

Рис. 1

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

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

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-мірним кубом, а набір (α _1, ..., α _η) - вершинами куба.

Нехай σ _1, ..., σ _r - фіксований набір чисел з 0 і 1. Безліч всіх вершин (α ₁ ,..., α _η) куба Е ⁿ таких, що α _{i 1} = σ _1, α _{i 2} = σ _2, ... , Α _ir   = Σ _r, 1 <i ₁ <i ₂ <... <i _r, називається (n - r) - Мірної гранню. Очевидно, що (n - r)-мірна грань є (n - r) - подкубом куба Е ^n.

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

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

Приклад 8. Нехай функція f (X _1, X _2, Х ₃₎ задана табл. 4. Скласти для неї безліч N _f.

Таблиця 4

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

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

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

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

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

.

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

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

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

.

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

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

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

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

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

Приклад 11. Кон'юнкція

,

,

відповідають межі (рис. 7 а, б, в), N _{k 1} = {7,8}, N _{k 2} = {8,6}, N _{k 3} = {6,2,4,8}, які мають ранг 2 , 2, і 1. Перші дві грані є одномірної гранню (ребром), а третя - двовимірної гранню.

Зазначимо очевидні властивості введеного відповідності між булевой функцією f і підмножиною N _f.

Якщо , То

.

Зокрема, якщо f (X _1, Χ _2, 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 _1, Х _2, X ₃₎ - функція, задана табл. 4 і Тоді межі Ν _{k 1} і N _{k 3} є максимальними, a N _{k 2} не максимальна для N _f, т. к. і розмірність N _{k 3} більше розмірності N _{k 2.}

Кон'юнкція К, відповідна максимальної межі N _k, називається простий импликантой функції f.

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

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

ДНФ, відповідна неприводимого покриттю безлічі N _f називається тупиковою в геометричному сенсі.

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

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

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

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

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

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

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

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

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

.

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

.

Рішення. Зазначимо на моделі куба елементарні кон'юнкції: першої кон'юнкції відповідає вершина 6, другий - вершина 5, третій - вершина 8, четвертого - вершина 2 (рис 8). Таким чином, безліч N _f -Побудовано. Ні одна грань не відзначена повністю, тому переходимо до кроку 4 алгоритму.

Рис. 8

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

.

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

Таблиця 5

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

Рис. 9

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

.

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

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

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

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

Таблиця 6

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

.

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

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

Таблиця 7

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

.

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

.

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

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

Таблиця 8

.

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

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

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

Таблиця 9

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

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

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

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

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

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

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

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

Рішення.

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

.

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

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

.

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

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

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

Рішення.

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

.

2. Уявімо цю функцію в ДНФ

.

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

.

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

Вправи

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

а)

;

б) ;

в)

;

г) ;

д) ;

е) .

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

а) ;

б)

;

в)

;

г)

.

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

Таблиця 10

Таблиця 11

Таблиця 12

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

a) ;

б) ;

в) .

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

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

СПИСОК

1. Нефедов В.М. Курс дискретної математики / В.М. Нефедов, В.А. Осипова: Изд-во МАІ, 1992. 262 с.

2. Яблонський С.В. Введення в дискретну математику / С.В. Яблонський. Μ.: Наука, 1979. 272 с.

3. Леденьовим Т.М. Спеціальні глави математики. Дискретна математика: навч. посібник / Т.М. Леденьовим. Воронеж: ВДТУ, 1997. 130 с.

4. Кретова Л.Д. Елементи математичної логіки: методичні вказівки до практичних та індивідуальних занять / Л.Д. Кретова, Н.Б. Ускова, В.В. Посметь. Воронеж: ВДТУ, 2005. 21 с.