Теоретична частина. Порядок виконання роботи

Мета роботи

Порядок виконання роботи

1.3.1. Вивчити за даними методичними вказівками і літературою, що рекомендується, основні положення алгебри логіки.

1.3.2. Представити ФАЛ, вибрану з табл. 1.4 відповідно до варіанта, в диз'юнктивній і кон’юнктивній довершених нормальних формах.

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

1.3.4. Задати обрану функцію табличним, координатним, графічним і цифровим способами.

1.3.5. Використовуючи основні закони і тотожності АЛ, провести мінімізацію ФАЛ, що розглядається.

1.3.6. Побудувати схеми, що реалізують дану функцію на контактах реле і логічних елементах, використовуючи для позначення операції: «І», «АБО», «НІ», «АБО-НІ», «І-НІ».

1.3.7. Зібрати кожну з отриманих схем на лабораторному стенді і перевірити відповідність реалізованих ними ФАЛ початковій таблиці істинності.

1.4. Зміст звіту

Звіт повинен містити:

- найменування і мету роботи;

- доповнені висновками і коментарями результати виконання завдань, передбачених пунктами 1.3.2–1.3.7.

Таблиця 1.4

Варіанти ФАЛ

Аргументи

Варіанти, що визначають ФАЛ

a

b

c

f 1

f 2

f 3

f 4

f 5

f 6

f 7

f 8

f 9

f 10

f 11

f 12

f 13

f 14

f 15

f 16

f 17

Лабораторна робота № 2

МІНІМІЗАЦІЯ ФУНКЦІЙ АЛГЕБРИ ЛОГІКИ МЕТОДОМ КАРТ КАРНО

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

2.2.1. Функціонально повні системи ФАЛ, базис і його вибір

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

В АЛ існує 5 «чудових» класів функцій, які мають важливу властивість, яка полягає в тому, що будь-яка ФАЛ, отримана з функцій даного класу за допомогою операцій суперпозиції і підстановки, обов'язково буде належати до того ж класу. Це функції, які мають такі властивості: збереження константи нуль; збереження константи одиниці; монотонність; лінійність і самоподвійність.

Функціями, що зберігають константу нуль (одиницю), називаються ФАЛ завжди рівні нулю (одиниці) на нульовому (одиничному) наборі аргументів.

Лінійними є ФАЛ, які можуть бути зображені поліномом першого ступеня, вигляду

, (1)

де – константи, які дорівнюють нулю або одиниці.

Монотонними називаються ФАЛ, що не зменшуються за будь-якого зростання аргументів.

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

Приналежність кожної функції двох змінних до того або іншого класу відзначено в табл. 2.1 знаком «+».

Таблиця 2.1

Приналежність ФАЛ двох змінних до «чудових» класів функцій

Аргументи і тип ФАЛ

f 0

f 1

f 2

f 3

f 4

f 5

f 6

f 7

f 8

f 9

f 10

f 11

f 12

f 13

f 14

f 15

a

b

Зберігає «0»

+

+

+

+

+

+

+

+

Зберігає «1»

+

+

+

+

+

+

+

+

Самоподвійна

+

+

+

+

Монотонна

+

+

+

+

+

+

Лінійна

+

+

+

+

+

+

+

+

Відповідно до теореми Поста-Яблонського, для того щоб ФАЛ була функціонально повною, необхідно і достатньо, щоб вона містила хоча б одну функцію, що не зберігає константу «0», хоча б одну функцію, що не зберігає константу «1», хоча б одну несамоподвійну функцію, хоча б одну нелінійну функцію, хоча б одну немонотонну функцію. Отже, у функціонально повну систему ФАЛ двох змінних повинні входити функції, спільно перекриваючі колонки табл. 2.1 клітками, не поміченими символом «+».

Існують різні функціонально повні системи ФАЛ: заперечення диз'юнкції (АБО-НІ); заперечення кон’юнкції (І-НІ); константа нуль і імплікація; заперечення і кон’юнкція; заперечення і диз’юнкція і т.д. Функціонально повний набір ФАЛ, що використовується для реалізації логічних схем, називається базисом. Найзручнішим для зображення ФАЛ є базис, що містить кон’юнкцію, диз’юнкцію і інверсію («І», «АБО», «НІ»). Використання трьох функцій спрощує описання схем, проте, як видно з табл. 2.1, будь-яку ФАЛ можна побудувати, використовуючи і лише одну функцію «І-НІ» або функцію «АБО-НІ». Базиси «І-НІ» «АБО-НІ» також отримали широке розповсюдження завдяки можливості істотно зменшити число уніфікованих логічних елементів.

Для перетворення ФАЛ з одного базису в інший використовується закон подвійного заперечення і закон подвійності (правило де Моргана), використання яких ілюструє такий приклад:

у базисі «І», «АБО», «НІ»: ; (2)

у базисі «І-НІ»: ; (3)

у базисі «АБО-НІ»: . (4)

2.2.2. Мінімізація ФАЛ методом карт Карно

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

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

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

Рис 2.1. Приклади мінімізації ФАЛ методом карт Карно

Як видно з рис. 2.1, у разі об’єднання двох полів виключається одна змінна, під час об'єднання чотирьох – дві змінні, під час об'єднання восьми – три змінні.

Карти Карно найбільш доцільно використовувати для мінімізації ФАЛ від двох до п’яти змінних. Мінімізуючи ФАЛ п’яти змінних, доводиться оперувати з двома картами по 16 полів кожна. Одній з карт ставиться у відповідність пряме, а інший інверсне значення п'ятої змінної. У разы мінімізації ФАЛ шести змінних розглядаються чотири карти по 16 полів.

Дата добавления: 2017-01-13