Алгебри логіки

3.3.1. Мінімізація ФАЛ за допомогою матриці Карно

Матриця Карно є своєрідною таблицею істинності ФАЛ, яка розбита на клітини. Кількість клітин матриці дорівнює 2 n, де n- Число аргументів ФАЛ. Стовпці та рядки матриці позначаються наборами аргументів. Кожна клітина матриці відповідає конституенті одиниці ФАЛ (двійковому числу). Двійкове число клітин складається з набору аргументів рядка і стовпця. Матриця Карно для ФАЛ, яка від двох аргументів, представлена ​​вигляді таблиці 3.3., від трьох аргументів таблицею 3.4. та від чотирьох аргументів таблицею 3.5.

Таблиця 3.3.

Таблиця 3.5.

х 3 х 4 х 1 х 2
	0 0 0 0	0 0 0 1	0 0 1 1	0 0 1 0
	0 1 0 0	0 1 0 1	0 1 1 1	0 1 1 0
	1 1 0 0	1 1 0 1	1 1 1 1	1 1 1 0
	1 0 0 0	1 0 0 1	1 0 1 1	1 0 1 0

Клітини матриць (таблиці 3.3., 3.4. та 3.5.) пронумеровані десятковими еквівалентами двійкових чисел клітин. Поруч розташовані клітини матриць як по горизонталі, так і по вертикалі містять сусідні двійкові числа. Крім цього сусідні двійкові числа знаходяться у всіх стовпцях верхньої та нижній рядківтак само як у всіх рядках крайніх стовпців.

Процес мінімізації ФАЛ за допомогою матриці Карно заснований на законі склеювання сусідніх двійкових чисел. Можна склеювати двійкові числа розташованих клітин, але рекомендується склеювати набори аргументів, якими позначені рядки і стовпці матриць. Розглянемо склеювання двійкових чисел клітин першого стовпця матриці (табл. 3.5).

Клітини 0 та 4, відповідно двійкові числа 0000 та 0100, результат склеювання 0-00.

Клітини 8 та 12, двійкові числа 1000 та 1100, результат 1-00. Отримані імпліканти склеюються між собою, т.к. тире стоїть в тому самому розряді і двійкові числа імплікант є сусідніми, остаточний результат - - 00.

Клітини 8 та 12

Таким чином, якщо склеюються всі двійкові числа одного стовпця, пропадають ті розряди, якими позначені рядки. Аналогічно, якщо склеюватимуться всі двійкові числа одного рядка, наприклад 4, 5, 7, 6, пропадають всі розряди, якими позначені стовпці, тобто. результат буде наступний 01- -.

Якщо склеюватимуться двійкові числа тільки двох будь-яких клітин, то прочерк ставитися замість того розряду двійкових чисел рядка або стовпця, який зміниться при переході клітин з одного рядка в інший (або з одного стовпця в інший). Наприклад, склеюються числа клітин 5 і 13, отримаємо результат -101, або клітин 7 і 6 результат 011-.

При склеюванні двійкових чисел восьми поруч розташованих клітин пропадає три змінні, наприклад, для клітин 3, 7, 15, 11, 2, 6, 14, 10 пропадають змінні х 1 , х 2 , х 3 . Змінні х 1 , х 2 пропадають тому, що склеюються всі клітини стовпців, а х 3 тому, що останні два стовпці склеюються між собою.

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

Відомо, що для кожної ФАЛ має місце кількість наборів аргументів. n, де n- Число аргументів від яких залежить функція або логічний вираз.

Набори аргументів поділяються на три види

1. Набори аргументів, у яких функція дорівнює одиниці, називаються робітниками.

2. Набори аргументів, у яких функція дорівнює нулю, називаються забороненими.

3. Набори аргументів, на яких функція може дорівнювати або одиниці, або нулю, називаються байдужими.

Якщо задана ФАЛ немає байдужих наборів, вона може бути представлена ​​у буквеному вигляді як СДНФ. За наявності у заданій ФАЛ байдужих наборів, її подання може мати таку форму.

де – десяткові еквіваленти робочих наборів,

– десяткові еквіваленти заборонених наборів.

Набори аргументів, яких немає серед робітників та заборонених, будуть байдужими.

приклад 3.3. Мінімізувати задану ФАЛ у вигляді СДНФ за допомогою матриці Карно.

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

Таблиця 3.5.

х 2 х 3 х 1
	0

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

Приклад 3.4. Мінімізувати логічний вираз, заданий робочими та забороненими наборами за допомогою матриці Карно.

Будуємо матрицю Карно на чотири змінних і заповнимо клітини одиницями та нулями відповідно для робочих та заборонених наборів.

Таблиця 3.6.

х 3 х 4 х 1 х 2	00
			(1)
	(1)		(1)

При об'єднанні клітин з одиницями контури бажано, щоб у кожен контур включалося найбільше число клітин з максимально можливого. Для цього клітини деяких байдужих наборів використовуємо як клітини робочих наборів, підставивши одиниці в дужках. В результаті отримаємо три контури, що містять по 4 клітини. В узагальненому коді контуру, що включає всі клітини одного рядка, пропадають змінні х 2 х 3 (10 - -). В узагальненому коді контуру, що включає всі клітини одного стовпця, пропадають змінні х 1 х 2 (- - 11) і для контуру, що містить по дві клітинки двох рядків пропадають змінні х 2 (при переході в контурі з одного рядка в інший) та х 3 (при переході з одного стовпця до іншого). В результаті отримаємо мінімальну ДНФ у наступному вигляді

Можливі варіантиоб'єднання клітин матриці Карно в контури показано малюнку 3.4.

х 3 х 4 х 1 х 2

А = 0 - 0 -

З = - 0 - 0

Н

Б = 1 - 1 -

К = - - - 1

В = - - 0 0

Л = - 1 - -

Г = 10 - -

М = - - - 0

Д = - 0 0 1

Н = - 0 - -

Е = - 0 1 -

Ж = - 1 - 1

Мал. 3.1. Можливі варіанти поєднання клітин матриці Карно в контури

3.3.2. Мінімізація функцій логіки алгебри за допомогою матриці на п'ять змінних

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

У матриці на п'ять змінних (таблиця 3.7.) рядкам відповідають набори змінних х 1 х 2 х 3 , а стовпцям набори змінних х 4 х 5 . Кожній клітині матриці відповідає п'ятирозрядне двійкове число. У клітинах матриці (табл. 3.7) проставлені десяткові еквіваленти відповідних двійкових чисел.

Таблиця 3.7.

х 4 х 5 х 1 х 2 х 3

Мінімізація ФАЛ за допомогою матриці на п'ять змінних полягає в об'єднанні клітин з робочими наборами (включаючи при необхідності і клітини з байдужими наборами) у контури та одержання цих контурів відповідних їм узагальнених кодів.

Особливість тут полягає в тому, що в стовпцях матриці на п'ять змінних об'єднувати по чотири клітини в контури можна тільки чотири клітини зверху, або чотири клітини внизу, або чотири клітини посередині. Наприклад, для останнього стовпця матриці контури можуть складатися з клітин 2, 6, 14, 10, або 26, 30, 22, 18 або 14, 10, 26, 30.

Приклад 3.6. Мінімізувати за допомогою матриці на п'ять змінних наступний логічний вираз

Будуємо матрицю на п'ять змінних та заповнюємо клітини робочих наборів одиницями, заборонених – нулями.

Об'єднуємо в контури клітини з робочими наборами, включаючи необхідні клітини байдужих наборів. Для кожного контуру визначаємо узагальнений код.

Таблиця 3.8.

х 4 х 5 х 1 х 2 х 3
	(1)	(1)	(1)
	(1)
	(1)	(1)
		(1)	(1)
	(1)		(1)
			(1)
	(1)		(1)

Отримуємо мінімальну ДНФ

Контрольні питання

1. Дати визначення скороченої ДНФ.

2. Що таке тупикова ДНФ?

3. Як вибирається мінімальна ДНФ із тупикових ДНФ?

4. Для чого використовується імплікантна таблиця та як вона будується?

5. Пояснити аналітичний спосіб мінімізації ФАЛ Квайна-Мак-Класкі.

6. Як будується матриця Карно на три та чотири змінних?

7. Мінімізувати аналітичним способом такі логічні вирази, задані лише робочими наборами

8. Мінімізувати за допомогою матриці Карно логічні вирази, задані робочими та забороненими наборами

Подібна інформація.

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

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

практиці для знаходження глобального мінімуму в основному використовується поєднання Монте-Карло методу та одного з методів локальної мінімізації.

Широкий клас М. ф. м. описують наступною обчислювальною схемою. Нехай мінімізована ф-ція, визначена довільно обрана початкова точка. Припустимо, що має безперервні приватні похідні до порядку включно розглядатимемо як похідну нульового порядку). Для отримання послідовних наближень до локального мінімуму будується послідовність точок по ф-лам наступного виду:

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

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

де дійсне число, яке зв. кроковим множником, вектор визначає напрямок спуску. Серед методів спуску виділяються методи монотонного спуску чи релаксаційні методи. Метод релаксаційним, якщо при Бели безперервно диференційована, то релаксаційність методу (3) забезпечується, коли напрямок спуску утворює гострий кутз напрямком градієнта та досить малий. Загальна теорія релаксаційних процесів розвинена найповніше для випадку опуклих ф-цій. Як осн. параметрів, що характеризують процес, розглядаються кути релаксації між напрямком градієнта), а також множники релаксації, що визначаються рівністю

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

Серед релаксаційних методів найвідоміші градієнтні методи. Розглянемо докладніше одноступінчасті методи градієнтного типу. Загальна схемаїх наступна:

У рамках цієї схеми можна виділити такі модифікації:

а) градієнтний спускіз постійним кроком: одинична матриця;

б) найшвидший градієнтний спуск: , де визначається за умови мінімуму

в) метод Ньютона-Рафсона: , де - гесіан у точці

г) проміжні схеми: . До найбільш поширених двоступінчастих градієнтних методів можна віднести методи сполучених градієнтів; прикладом двоступінчастої схеми є метод сполучених градієнтів Флетчера - Рівза:

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

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

Якщо градієнт розривний, перелічені вище методи не застосовуються. Тому велике значеннямають методи мінімізації опуклих (не обов'язково диференційованих) ф-цій; ці методи можна умовно розбити на 2 групи: 1) методи градієнтного типу та 2) методи «сікучих площин». До 1-ї групи належать різні модифікації узагальнених градієнтів методу, а також схеми з прискореною збіжністю, засновані на розтягуванні простір. у напрямку градієнта або різниці двох послідовних градієнтів. До методів 2 групи відноситься, напр., метод Келлі. Нехай ЗП - опукле (обмежене) мн-во, у якому визначено послідовність точок, у яких обчислюється узагальнений градієнт . Тоді перебуває як розв'язання задачі: знайти

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

Для вирішення спец. Класи багатоекстремальних завдань використовуються методи динамічного програмування.

В даний час створюються оптим. алгоритми мінімізації ф-цій різних класів. Нехай клас ф-цій, визначених у кубі , і мають приватні похідні до s-го порядку, задовольняють умові Липшица з константою L. Будь-який алгоритм мінімізації з , використовує інформацію про значення f і її похідних до порядку включно лише у N точках еквівалентний (в сенсі результату) деякому алгоритму А отримання послідовності ітерацій (1) для апроксимації шуканого значення за допомогою підсумкової операції

де - деяка обчислювана ф-ція. Введемо такі позначення:

Алгоритм, якого досягається оптимальним. Умови означають відповідно асимптотичну оптимальність і оптимальність по порядку алгоритму.

причому вибір , впливає лише на константу у зазначеній оцінці. В окремому випадку і маємо:

де мінім. мережу в.

Інший підхід до побудови оптим. алгоритмів мінімізації пов'язані з узагальненням ідей послідовних статистичних рішень. Алгоритм мінімізації сприймається як керована послідовність дослідів, кожен із яких дає той чи інший результат. На сукупності результатів визначається апріорна імовірнісна міра. Після отримання конкретного результату чергового досвіду відбувається перерозподіл ймовірностей ф-ле Байєса і вибирається наступний досвід або приймається остаточне рішення. Алгоритми відрізняються один від одного правилом, за яким вибирається наступний досвід, правилами зупинки та вибору остаточного рішення. Якість рішення визначається ф-цією втрат, яка усереднюється відповідно до отриманого на даному етапіімовірнісним розподілом. У цих термінах поставлено завдання вибору оптим. алгоритму як побудови послідовного байєсовського правила пошуку рішень Така постановка цікава тим, що в її рамках можна враховувати статистичні властивості класу розв'язуваних завдань, зіставляти «середні» втрати, пов'язані з похибкою рішення, з витратами, пов'язаними з уточненням рішення. Любич Ю. І., Майстровський Г. Д. Загальна теоріярелаксаційних процесів для опуклих функціоналів "Успіхи математичних наук", 1970, т. 25, ст. 1; Міхалевич В. С. Послідовні алгоритми оптимізації та їх застосування. "Кібернетика", 1965, N5 1-2; Іванов В. В. Про оптимальних алгоритмахмінімізації функцій деяких класів. «Кібернетика», 1972 № 4; Вайлд Д. Дк. Методи пошуку екстремуму. Пров. з англ. М., 1967.

В. В. Іванов, В. С. Михалевич, Н. 3. Шор.

Студент повинен:

Знати:

· Методи мінімізації логічних функцій.

Вміти:

· Виконувати мінімізацію функцій методом безпосередніх перетворень; Виконувати мінімізацію функцій шляхом безпосередніх перетворень;

· Виконувати мінімізацію функцій за допомогою карт Карно.

Метод безпосередніх перетворень

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

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

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

Наприклад, логічну функцію

у вигляді СДНФ, можна мінімізувати наступним чином:

1. Додамо до цієї функції доданок , яке вже є в цій функції, використовуючи правило х + х = х

2. Застосуємо метод склеювання однаково підкреслених елементарних кон'юнкцій

3. Застосуємо метод склеювання для двох останніх елементарних кон'юнкцій

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

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

Карти Карно

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

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

Карти Карно були винайдені в 1952 Едвардом В. Вейчем і вдосконалені в 1953 Морісом Карно, фізиком з Bell Labs, і були покликані допомогти спростити цифрові електронні схеми.

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

Наприклад, карта Карно для функції чотирьох змінних має 24 = 16 осередків.

Структура карти Карно для функцій двох змінних показано малюнку 2.2. 2

Малюнок 2.2

На малюнку 2.3 представлено структуру карти Карно для функції трьох змінних.

а) таблиця істинності; б) структура карти Карно

Малюнок 2.3

Карта розмічується системою координат, що відповідають значенням вхідних змінних. Наприклад, верхній рядоккарти для функції трьох змінних (рисунок 2.3) відповідає нульовому значенню змінної x1, а нижня – її одиничному значенню.

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

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

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

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

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

а) таблиця істинності; б) карта Карно

Малюнок 2.4

Спочатку формуємо прямокутники, що містять по 2k осередків, де k - ціле число.

У прямокутники поєднуються сусідні осередки, які відповідають сусіднім елементарним творам.

Наприклад, малюнку 2.4,б об'єднані осередки з координатами 001 і 101. При об'єднанні цих осередків утворився прямокутник, у якому змінна x1 змінює своє значення. Отже, вона зникне при склеюванні відповідних елементарних творів і залишаться лише х2 та х3, причому змінну х2 беремо в інверсному вигляді, т.к. вона дорівнює 0.

Осередки, розташовані у першому рядку (рисунок 2.4 б), містять одиниці і є сусідніми. Тому всі вони об'єднуються у прямокутник, що містить 2 2 = 4 комірки.

Змінні х2 та х3 у межах прямокутника змінюють своє значення; отже, вони зникнуть із результуючого елементарного твору. Змінна х1 залишається незмінною та рівної нулю. Таким чином, елементарний твір, отриманий в результаті об'єднання осередків першого рядка малюнка 2.4 б, містить лише один х1, який беремо в інверсному вигляді, т.к. він дорівнює 0.

Це, зокрема, випливає з того, що чотирьом осередкам першого рядка відповідає сума чотирьох елементарних творів:

Двом осередкам старого стовпця відповідає сума двох творів

Функція, що відповідає малюнку 2.4 має вигляд:

Сукупність прямокутників, що покривають усі одиниці, називають покриттям. Зауважимо, що один і той самий осередок (наприклад, осередок з координатами 001) може покриватися два або кілька разів.

Отже, можна зробити наступні висновки:

1. Формула, що у результаті мінімізації логічної функції з допомогою карт Карно, містить суму стільки елементарних творів, скільки прямокутників в покритті.

2. Чим більше осередків у прямокутнику, тим менше змінних міститься у відповідному елементарному творі.

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

а Б В)

Малюнок 2.5

Функція, що відповідає покриттю, показаному на малюнку 2.5 а, має вигляд:

Незважаючи на те, що карти Карно зображуються на площині, сусідство квадратів встановлюється на поверхні тора. Верхня і нижня межі карти Карно як би «склеюються», утворюючи поверхню циліндра. При склеюванні бічних кордонів виходить тороїдальна поверхня. Дотримуючись викладених міркувань, встановлюємо, що комірки з координатами 1011 і 0011, зображені малюнку 2.5 б, є сусідніми і об'єднуються в прямокутник. Справді, зазначеним осередкам відповідає сума елементарних творів

Аналогічно об'єднуються та інші чотири поодинокі осередки. В результаті їх об'єднання отримуємо елементарний твір.

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

Карта Карно, показана малюнку 2.5 в, містить одиничні осередки, розташовані по кутах. Усі чотири осередки є сусідніми, і після об'єднання дадуть елементарний твір

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

1. Зображується таблиця для n змінних і розмітка її сторін.

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

3. Вибирається найкраще покриття таблиці правильними прямокутниками, які обводимо контурами. У кожному прямокутнику має бути 2 n осередків.

4. Одні й самі клітинки з одиницями можуть входити у різні контури.

5. Кількість прямокутників має бути мінімальною, а площа прямокутників максимальна.

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

7. Отримані твори з'єднуємо знаком логічного додавання.

Контрольні питання:

1. Що називають мінтермами та мінтермами?

2.Записати функції, задані таблицями 2.9 та 2.10 у СДНФ та СКНФ.

Таблиця 2.9

3. Спростіть логічні функції, використовуючи аксіоми тотожності та закони алгебри логіки:

a)

c)

Логічні елементи

Студент повинен

Знати:

· Таблиці логічних станів для основних функціональних логічних схем;

· Основні базиси побудови логічних схем.

Вміти:

· Визначати логічні стани на виходах цифрових схемза відомими станами на входах;

· Виконувати логічне проектуванняу базисах мікросхем;

· Вибирати мікросхему за довідником, виходячи з заданих параметрівта умов використання.

Принцип логічного устрою базується в ІМС на роботі біполярних транзисторіву режимі ключа (або замкнуті, або розімкнуті).

Логічне дію здійснюється як із одного (одновходовий логічний елемент) і з безліччю (многовходовый логічний елемент) вхідних змінних.

p align="justify"> При роботі логічних пристроїв використовуються три основних дії згідно алгебри Буля - "І", "АБО", "НЕ".

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

Розрізняють комбінаційні та послідовні логічні пристрої.

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

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

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

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

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

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

Історично першими пристроями, для опису дій яких використовували логічні функції, були пристрої, виконані релейно-контактних елементах. Для проектування таких пристроїв було розроблено теорію релейно-контактних схем (ТРКС). Потім з'явилися безконтактні пристрої, призначені тільки для логічних перетворень сигналів і конструктивно оформлені вироби.

Пристрої автоматики, дія яких описується елементарними логічними функціями, зазвичай називають відповідно до реалізованої ними логічної операцією елементами НЕ, І, АБО, І-НЕ, АБО-HE (див. табл. 4.1).

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

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

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

Сполучний закон.Результат послідовного складання змінних чи множення їх залежить від порядку цих действий:

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

розподільчий закон.Загальний множник можна виносити за дужки, як у звичайній алгебрі:

Закон склеювання.Сума творів першої та другої змінних та другої змінної та інверсії першої змінної дорівнює другій змінній. Добуток суми двох змінних та суми інверсії першої змінної з другою змінною дорівнює другій змінній:

Закон інверсії (Закон Моргана - Шеннона).Заперечення логічного складання рівносильне твору заперечень доданків, і, навпаки, заперечення логічного множення рівносильне сумі заперечень співмножників:

Інверсія довільної комбінації двійкових змінних, з'єднаних знаком «плюс» або «множення», еквівалентна заміні в ній значень змін-

них інверсіями при одночасному зміні знака «плюс» на знак «множення» і навпаки. Наприклад, x t x 2 +x 3 x 4 =(x l x 2)(x 3 x 4) = (x l +х 2)(х 3 +х 4).Закон інверсії зустрічається лише у алгебрі логіки.

Таким чином, закон інверсії дозволяє замінити операцію АБО операцією І, а за необхідності – навпаки. Це особливо важливо, оскільки при широкому використанніІнтегральних логічних елементів у побудові логічних пристроїв найчастіше використовують елементи базисів І-НЕ, АБО-НЕ.

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

Виконуючи мінімізацію, користуються також наслідками законів логіки алгебри, основні з яких такі:

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

Друга інверсія дає

Для переходу з базису І, АБО, НЕ в базис АБО-HE, а також базис І-НЕ також виконується перетворення логічної формули з використанням подвійного заперечення. Розглянемо приклад переходу для релейної схеми на рис. 4.5, а, Реалізованої в базисі І, АБО, НЕ (рис. 4.5, б), в базис АБО-HE (рис. 4.5, в):

та в базис І-НЕ (рис. 4.5, г):

Кількість рисок зверху формул дорівнює кількості елементів заперечення, тобто. елементів АБО-HE та І-НЕ. У першій формулі шість заперечень і відповідно схема на рис. 4.5, вмістить шість елементів АБО-HE. У другій формулі п'ять заперечень і відповідно схема на рис. 4.5, гмістить п'ять елементів І-НЕ.

Мал. 45.

а -на релейних елементах; б -на елементах АБО, І, НЕ; в -на елементах

АБО-HE; пана на елементах І-НЕ

Приклад 4.1

Спростіть вираз / = (х + у) (х + z)та накресліть релейний еквівалент до спрощення та після нього. Тут/ - вихідний сигнал (стан замикаючого контакту) релейного елемента F.

Рішення

Спростимо заданий виразвідповідно до законів алгебри логіки: Враховуючи, що х х = х,запишемо

Враховуючи, що 1 + у + z= 1, остаточно запишемо /= х + у z.Після спрощення релейний еквівалент виглядає так:

Спростіть вираз f = х-у + х y-z + y-zта накресліть релейний еквівалент до спрощення та після нього.

Рішення

До спрощення релейний еквівалент відповідно до заданого виразу виглядає наступним чином:

Спростимо заданий вираз відповідно до законів алгебри логіки, виносячи загальний множникза дужки:

Релейно-контактна схема цього виразу набуде вигляду

Тут враховано, що x-z = x + z і а + а = 1, або x+z+x+z= 1, де a = x + z; а = x+z.Тому після перетворення спрощений вираз набуде вигляду

Після спрощення вираження релейний еквівалент виглядає так:

Перевіримо правильність перетворення за допомогою таблиці стану (табл. 4.2), в якій показані всі можливі комбінації двох змінних хі 2, і переконаємося, що вираз х+г+х-гзавжди одно одиниці.

Таблиця 4.2

Таблиця стану

		X+Z+X-Z

Розглянемо приклад застосування алгебри логіки до створення системи автоматичного регулюваннярівня води у резервуарі Р (рис. 4.6). Виконавчий механізм ІМ здійснює подачу води в резервуар шляхом повного відкриттяабо закриття вентиля, що подає А. У резервуарі є два датчики рівня води: датчик верхнього рівняВ і датчик нижнього рівня Н. Коли рівень води досягне або перевищить положення датчика, сигнал стає рівним одиниці. Якщо рівень води опуститься нижче за рівень датчика, сигнал на його виході стає рівним нулю.

Мал. 4.6.

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

Мал. 4.7.

на рис. 4.6

умови роботи, тобто. всі комбінації вхідних сигналів та сигналу управління, перекладені на мову алгебри логіки та представлені на рис. 4.7 у верхній таблиціу вигляді одиниць та нулів. У таблиці вказано, за яких співвідношеннях вхідних сигналів є або відсутній сигнал Qна виході релейної САР. Сигнал на виході є результатом логічних операційнад вхідними сигналами.

Якщо за даними таблиці ми спробуємо записати умови роботи у вигляді логічних функцій, то виявимо, що увімкненому сигналу управління відповідають два різні співвідношення вхідних сигналів. Те саме стосується і вимкненого сигналу управління. Виходить неоднозначність вихідного сигналу, залежно від поєднання вхідних сигналів. При В = 0 і Н = 1 є положення, коли Q = 0 і є положення коли Q=l. Це означає, що в схемі повинен бути елемент пам'яті, як який можна використовувати вже знайомий нам RS-тригер Т. Для включення тригера використовуємо появу нульового сигналу на виході 11 (II = 0). Цей сигнал інвертується і подається на встановлюючий вхід S тригера Т. Оскільки сигнал не змінюється, його не будемо враховувати і запишемо умову включення S = Н. Умови скидання тригера і зняття сигналу управління записуємо як R = У.

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

Розглянемо ще один приклад застосування алгебри логіки для створення логічних релейних захистів електротехнічних об'єктів на прикладі релейного захисту силового трансформатора, наведеною на рис. 4.8.

Правила влаштування електроустановок передбачають для відповідальних об'єктів основний та резервний захист. Основний захист повинен відключати об'єкт без витримки часу, а резервний – з витримкою часу.

Мал. 4.8.

а -силова схема;б -схема ланцюгів захисту

Основним захистом трансформатора Т1 при короткому замиканні в трансформаторі (КЗ у точці К1) служить диференціальний релейний захист (на схемі вона не показана). Резервним захистом при короткому замиканні на шинах, що відходять, підстанції за вимикачем Q2 (КЗ в точці К2) служить максимальний струмовий захист, що діє при спрацьовуванні струмових реле КЛ1-К АЗ. Коротке замиканняу трансформаторі Т1 має відключатися вимикачем Q1 від дії резервного захисту без витримки часу, тобто. "миттєво". Коротке замикання в точці К2 має без витримки часу відключатися вимикачем Q2 (захист вимикача Q2 на схемі не показаний). Якщо з будь-яких причин захист, що впливає на вимикач Q2 або сам вимикач Q2, не спрацює, то від резервного захисту з витримкою часу повинен відключитись вимикач Q1.

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

Визначення місця КЗ виконується в такий спосіб. При КЗ Т1 (точка К1) трансформатори струму ТА 1-ТАЗ обтікаються струмом КЗ, і спрацьовують реле струму КА1-КАЗ. Трансформатори струму ТА4-ТА5 на виході Т1 трансформатора не обтікаються струмом КЗ. Реле струму КА4 і КА5 не спрацьовують, їх контакти, що розмикають, замкнуті. У такій ситуації захист має спрацювати без витримки часу. Проміжне реле KL подає сигнал відключення вимикача Q1.

Умови роботи проміжного реле KL для відключення без витримки часу словесно можна сформулювати так: реле KL спрацює, якщо спрацює реле КЛ1, АБО спрацює реле КА2 АБО, спрацює реле КАЗ І НЕ спрацюють реле КА4 І реле КА5.

У символах математичної логіки умова спрацьовування реле KL записується так:

При КЗ на ділянці зовнішньої мережі (точка К2) трансформатори струму ТА4 і ТА5 обтікаються струмом КЗ, що призводить до спрацьовування реле струму КА4 і КА5 і розмикання їх контактів, що розмикають, в ланцюгу релейного захисту без витримки часу. Таким чином робота захисту без витримки часу блокується. Резервний захист при КЗ у точці К2 працює з витримкою часу.

Умова спрацьовування реле часу резервного захисту формулюється словесно так: реле часу КТ спрацює, якщо спрацює реле КА1, АБО спрацює реле КА2, АБО спрацює реле КАЗ.

У символах математичної логіки умова спрацьовування реле часу записується як

Повністю умова спрацьовування проміжного реле KL, що вимикає вимикач Q1 без витримки часу та з витримкою часу, записується так:

Схема на рис. 4.8, бпобудована відповідно до рівнянь (4.13) та (4.14). Спрацювання захисту без витримки часу (логічного захисту) фіксується вказівним реле КН1. Спрацювання захисту з витримкою часу фіксується вказівним реле КН2.

Найбільш уживана операція при мінімізації функцій - це операція склеювання.

AB + BB = B (A + В) = B.

Розглянемо три найпоширеніші методи мінімізації.

1. Нехай будуть задані номери наборів чотирьох змінних, на яких логічна функція набуває одиничного значення: f (2,5,6,7,10,12,13,14)=1.

Висловимо цю логічну функцію в СДНФ (символ кон'юнкції писати не будемо):

f(0010,0101, 0110, 0111, 1010, 1100, 1101, 1110) =

На першому етапі мінімізації вихідну СДНФ можна спростити за рахунок використання закону склеювання, тоді отримаємо:

Звертаємо увагу на те, що ту саму конституенту (імпліканту) можна склеювати з іншими конституентами (імплікантами) багаторазово, тому що в логіці Буля діє закон ідемпотентності:

тому будь-яку конституенту можна розмножити.

На другому етапі скористаємося таблицею Куайна (табл. 8), відповідно до якої даний методмінімізації отримав своє найменування – метод Куайна. У таблиці по вертикалі перераховані всі отримані першому етапі спрощення імпліканти, а, по горизонталі - вихідні конституенти. Одиниця у табл. 8 стоїть там, де імпліканта «накриває» конституенту. Справа в тому, що конституент завжди може бути замінена імплікантою або навіть окремим термом за законом поглинання:

Таблиця 8

Після заповнення таблиці Куайна в нас вийшло так, що майже в кожній графі було по дві одиниці; тим часом достатньо мати одну одиницю у графі. Тому, наскільки можна, треба виключити надлишкові одиниці. Вибір одиниць проводиться з міркувань мінімності числа термів (вибрані одиниці затемнені). У результаті виявилося, що можна обійтися лише трьома імплікантами замість шести.

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

2. Не менше ефективним способомМінімізація логічних функцій є метод поєднання індексів. Для його викладу складемо табл. 9, у графах якої записані можливі поєднання індексів. В останній графі виписано значення функції. Аналіз таблиці починається ліворуч по шпальтах. Принцип виключення i, j_коду наступний. На перетині i_стовпця, наприклад, з поєднанням індексів 23, і j_рядки, наприклад, 3-ї, знаходиться код 10, що відповідає імпліканті. Отже, у цьому стовпці скрізь, де зустрічається код 10, тобто у рядках 2, 3, 10 і 11, ці коди виключаються, оскільки значення функції в 3-му рядку дорівнює нулю. Тепер візьмемо стовпець з поєднанням індексів 124. Тут у 2-му і 6-му рядках залишені коди 010, а в 10-му і 14-му рядках - код 011. Зроблено це тому, що ці коди зустрічаються тільки на рядках зі значенням функції, що дорівнює одиниці. Навпаки, код 110 цього стовпця зустрічається як при одиничних значеннях функції, так і при нульових.

Таблиця 9

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

Далі керуються наступним правилом. Для того щоб функція прийняла значення, що дорівнює одиниці, достатньо того, щоб тільки якась одна імпліканта на рядку прийняла одиничне значення. Насамперед, залишаємо мінімальну імпліканту, яка перекриває одиниці у рядках 2, 6, 10 та 14. Потім, природно, звертаємося до 12-го рядка. Тут залишаємо єдиний на рядку код 011, що відповідає імпліканту. Ця ж імпліканта відповідальна за 13_у рядок, що закінчується теж одиницею. Залишилося розглянути 5-ий і 7-ий рядки. Спільною їм є импликанта: . Таким чином, трьома імплікантами ми перекрили всі поодинокі значення функції, що збігаються з результатом, отриманим на основі таблиць Куайна.

3. Існує графічний спосібсклеювання, який отримав назву метод карти Карно (представлений у табл. 10). Виділяємо суміжні одиниці, це будуть складові нашої функції.

Таблиця 10

Отримали два доданки

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

Таблиця 11

Таблиця 12

Карту Карно для чотирьох змінних представлено у вигляді табл. 11. Кожна клітинка картки відповідає конституенту. Заповнена карта представлена ​​в табл. 12 (функція взята та сама, що у перших двох методах). Відповідно до закону склеювання, дві суміжні конституенти з одиничними значеннями завжди можна поєднати для отримання відповідної імпліканти. Причому суміжними вважаються й ті, що лежать на межах карти. Які саме одиниці потрібно об'єднати для отримання відповідної імпліканти легко визначити візуально. Слід також пам'ятати, що відповідно до закону ідемпотентності та сама одиниця табл. 12 може склеюватися з двома або трьома суміжними одиницями.