Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Методичні вказівки до лабораторних робот з компютерної логіки
Інформація про навчальний заклад
ВУЗ:
Інші
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра програмного забезпечення
Інформація про роботу
Рік:
2014
Тип роботи:
Методичні вказівки до виконання дипломних та магістерських кваліфікаційних робіт
Предмет:
Комп ютерна логіка
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
КІРОВОГРАДСЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ
КАФЕДРА ПРОГРАМНОГО ЗАБЕЗПЕЧЕННЯ
КОМП’ЮТЕРНА ЛОГІКА
( ПРИКЛАДНА ТЕОРІЯ ЦИФРОВИХ АВТОМАТІВ)
Лабораторні роботи
Затверджено
на засіданні кафедри
програмного забезпечення
Кіровоград 2014
Прикладна теорія цифрових автоматів. Лабораторні роботи.
/ Савеленко О.К., Сидоренко В.В., Якименко Н.М.
- Кіровоград: КНТУ, 2014. –20с.
Автори:
Якименко Н.М., к.ф-м.н, доцент кафедри ПЗ
Савеленко О.К., викладач кафедри ПЗ.
Для студентів денної та заочної форми навчання, які вивчають дисципліну
“Комп’ютерна логіка ”.
У стислій формі освітлені основи проектування цифрових автоматів з використанням булевої алгебри для мінімізації ФАЛ, що описують функціонування автоматів.
Представлені вирішення прикладів для кращого освоєння матеріалу, що вивчається, наведені варіанти завдань для придбання практичних навиків.
Зміст
Лабораторна робота № 1 ………………………………………………………………………………. 3
Основні поняття функції алгебри логіки (ФАЛ)
Лабораторна робота № 2 ………………………………………………………………………………. 5
Мінімізація ФАЛ методом невизначених коефіцієнтів для базису І-АБО-НЕ
Лабораторна робота № 3 ………………………………………………………………………………. 7
Мінімізація функцій алгебри логіки методом мінімізуючих карт
Лабораторна робота № 4 ………………………………………………………………………………. 9
Проектування комбінаційних автоматів
Лабораторна робота № 5 ………………………………………………………………………………. 13
Проектування кінцевого автомата
Вимоги до оформлення звітів лабораторних робіт .……………………………………………. 17
Рекомендована література ………………………………………………………………………..…. 18
Зміст …..…………………………………………………………………………………………………… 19
Лабораторна робота №1
Основні поняття функцій алгебри логіки (ФАЛ)
Теоретичні відомості
1. Способи задання комбінаційних функцій
ФАЛ можуть бути задані словесним описом, табличним, аналітичним, числовим або графічним способом.
Аналітичний спосіб задання ФАЛ полягає в тому, що логічна функція F задається у вигляді алгебраїчної рівності, у якій змінні xj зв'язані між собою символами логічних операцій І, АБО, НЕ.
Існує дві основні форми запису логічних функцій в алгебраїчному вигляді, що називаються нормальними.
Перша - диз'юнктивна нормальна форма (ДНФ), яка є логічною сумою елементарних і неелементарних логічних добутків (диз'юнкцією кон'юнкцій). При цьому в кожну з кон'юнкцій аргумент чи його заперечення входить не більше одного разу. Наприклад:
F(x1, x2, x3) = x1 2 + x2 x3 + x1 2 x3.
Друга - кон'юнктивна нормальна форма (КНФ), що являє собою логічний добуток елементарних і неелементарних логічних сум (кон'юнкція диз'юнкцій):
F(x1, x2, x3) = (x1 + x2) (x1 + 2 + x3) (x2 + x3).
Елементарними називаються такі диз'юнкції або кон'юнкції, де число змінних менше повного числа змінних, від яких залежить функція. Ті кон'юнкції і диз'юнкції, які включають повне число змінних, називаються неелементарними.
F(x1, x2, x3) = 1 x2 x3 + x1 2 x3 + x1 x2 3 + x1 x2 x3.
Дана функція складається з кон'юнкцій, що об'єднані знаками диз'юнкції і включають у свій склад повний набір змінних (або їхнє заперечення), тобто складається з диз'юнкції неелементарних кон’юнкцій.
Запис ФАЛ у вигляді суми кон'юнкцій, які складаються з повного набору змінних, на яких функція дорівнює одиниці, називається повною диз'юнктивною нормальною формою (ПДНФ).
Таким чином, аналітичний спосіб задання функцій алгебри логіки полягає в зображенні їх формулами алгебри логіки. В результаті, будь-яка функція, задана таблично, може бути представлена в аналітичній формі за допомогою використання операцій І, АБО, НЕ, тобто може бути зображена у вигляді ФАЛ.
В деяких випадках для задання ФАЛ використовується так званий числовий спосіб. При цьому ФАЛ записується у вигляді логічної суми десяткових номерів наборів, на яких функція дорівнює одиниці. Наприклад:
F(x1, x2, x3) = 3 5 6 7 = ∑ (3, 5, 6, 7).
або
F = ki3, при i=3, 5, 6, 7
де 3 - покажчик на кількість аргументів ФАЛ.
Графічний спосіб задання ФАЛ полягає в заданні функції у вигляді n-мірного одиничного куба, вершинами якого є його значення на відповідних наборах.
2. Основні базиси функцій
Серед повних систем найбільше практичне значення має булевий базис функцій І, АБО, НЕ, базис функції Шеффера І-НЕ і базис функції Вебба (Пірса) АБО-НЕ.
Властивості функцій базису І, АБО, НЕ відповідають аксіомам і законам булевої алгебри.
;
;
х+1=1;
х1=х;
х+0=х;
х0=0;
Правила двоїстості де Моргана:
Функція Шеффера має вигляд:
F(x1, x2) = = x1 / x2
Дана функція має наступні властивості.
Для кон'юнкції двох змінних справедливе співвідношення:
x1 x2 = = = (x1 / x2) / 1
Для диз'юнкції двох змінних справедливе співвідношення:
x1 x2 = = = 1 / 2 = (x1 / 1) / (x2 / 1)
У сучасній мікросхемотехніці широко застосовуються логічні елементи, які реалізують функцію Вебба.
Функція Вебба може бути записана у вигляді:
F(x1, x2) = = 1 2 = x1 x2
Для даної функції справедливі наступні співвідношення.
Зв'язок функції Вебба з кон'юнкцією двох змінних:
x1 x2 = 1 2
Зв'язок функції Вебба з диз'юнкцією двох змінних:
x1 x2 = = = (x1 x2) 0
Функції Шеффера і Вебба зв'язані між собою співвідношеннями:
x1 / x2 = = (1 2) 0
x1 x2 = = (1 / 2) / 1
Завдання
1. Функцію Y(x1, x2, x3) представлену табличним способом, подати в:
а) аналітичному вигляді;
б) числовому вигляді;
в) графічному вигляді.
№ набору
x1
x2
x3
Y(x1, x2, x3) для варіанту:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0
0
0
0
1
0
1
1
1
0
0
0
1
0
1
0
1
0
0
1
0
0
1
0
0
1
0
1
1
0
1
1
1
1
0
0
1
1
2
0
1
0
0
0
1
1
0
1
1
0
0
0
0
1
1
0
0
3
0
1
1
1
1
0
1
0
0
0
1
1
1
0
0
1
1
1
4
1
0
0
0
0
1
0
1
1
1
1
1
1
0
1
0
0
0
5
1
0
1
0
1
0
1
0
1
1
0
0
1
1
1
0
1
0
6
1
1
0
1
0
1
0
1
0
0
1
0
0
1
0
1
1
1
7
1
1
1
0
1
0
1
0
0
1
0
0
0
1
0
0
0
1
2. Функцію у(x1, x2, x3), задану аналітичним виразом, представити:
а) у базисі І-НЕ;
б) у базисі АБО-НЕ.
№ вар.
у(x1, x2, x3)
№ вар.
у(x1, x2, x3)
№ вар.
у(x1, x2, x3)
1
1 x2 + 1 x3 + x2 x3
6
x1 1 + x3 2 + x1 x3
11
1 x2 + x2 x3 + 1 3
2
x1 x2 + x2 3 + x1 3
7
x2 x1 + x3 2 + x1 x3
12
1 x2 + x2 x3 + 1 3
3
x1 3 + x3 2 + x3 1
8
x2 x1 + x3 2 + 1 x3
13
1 x3 + 2 x3 + 1 3
4
x1 2 + x3 1 + x2 x3
9
x1 x2 + x2 x3 + 1 x3
14
x1 2 + 2 x3 + 1 3
5
x2 1 + x3 2 + x1 x3
10
x1 x2 + x2 x3 + x1 3
15
x1 2 + x2 3 + 1 3
Контрольні питання:
Як можна задати комбінаційну функцію?
В чому різниця між ДНФ і ПДНФ?
Які базиси можна застосувати для запису логічних функцій?
Сформулювати аксіоми алгебри логіки.
Сформулювати правило де Моргана для трьох змінних.
Яка функція називається комбінаційною?
Лабораторна робота №2
Мінімізація ФАЛ методом невизначених коефіцієнтів
для базису І-АБО-НЕ.
Теоретичні відомості
Згідно з теоремою Жегалкіна, будь-яку логічну функцію можна представити в нормальній формі, наприклад, в диз'юнктивній нормальній формі (ДНФ):
F(x1, x2, ..., xn) = x1 + 1 + x2 + 2 + ... + xn + n + x1 x2 +
+ x1 2 + 1 x2 + 1 2 + ... + x1 xn + x1 n + 1 n + ... + x2 xn +
+ x2 n + 2 n + ...+ x1 x2 xn + x1 x2n + x1 2 n +
+ 1 2 n + ... + x1 x2 ·... ·xn + x1 x2 ·... ·n + ...
де - невизначені коефіцієнти, що приймають значення 0 чи 1 і так, щоб одержана результатом ДНФ була мінімальною. Коефіцієнти знаходяться із системи рівнянь, одержуваної шляхом підстановки значень x1, x2 ..., xn в наведену вище ДНФ.
Алгоритм пошуку невизначених коефіцієнтів наступний:
1. Вибрати черговий рядок, у якому Fi = 0, і всі коефіцієнти цього рядка визначити нулем (викреслити).
2. Якщо всі нульові рядки переглянуті, то перейти до п. 3, якщо ні, то до п. 1.
3. Переглянути рядки, в яких Fi = 1, та викреслити з них усі коефіцієнти, що зустрічаються в рядках, де Fi = 0.
4. Переписати всі модифіковані рівняння.
5. Вибрати черговий рядок Fi = 1 і викреслити максимально можливу кількість коефіцієнтів так, щоб ранг членів, що залишаються, був мінімальним.
Метод невизначених коефіцієнтів найбільш застосовний для диз'юнктивної форми і практично непридатний для кон'юнктивної форми.
Розглянемо приклад: Знайти мінімальну форму для функції F(x1, x2, x3) = ∑(0,2,4,7)
Розв’язок:
На підставі теореми Жегалкіна логічну функцію трьох змінних представимо в НДФ:
F(x1, x2, x3) = x1 + 1 + x2 + 2 + x3 + 3 + x1 x2 + x1 2 +
+ 1 x2 + 1 2 + x1 x3 + x1 3 + 1 x3 +13+ x2 x3 + x23 +
+2 x3 + 2 3 + x1 x2 x3 + x1 x23 + x1 2 3 + x1 2 x3 + 12x3 +
+ 1 x 2 3 + 1 x2 x3+ 1 2 3
Складемо систему рівнянь, і запишемо її у вигляді таблиці:
F0
1
F1
0
F2
1
F3
0
F4
1
F5
0
F6
0
F7
1
Згідно алгоритму викреслюємо коефіцієнти для Fi = 0. (\ нахил). Потім викреслюємо співпадаючі коефіцієнти для Fi = 1 (/ нахил). Отримуємо модифіковану систему рівнянь. Коефіцієнти, що задовольняють пункт 5, виділяємо, описавши їх по периметру стовщеною лінією.
Таким чином, маємо = 1 =1, = 1, а всі інші коефіцієнти рівні 0.
У результаті мінімізації знаходимо шукану функцію:
F(x1, x2, x3) = 1 3 + 2 3 + x1 x2 x3
Завдання
Згідно варіанту, мінімізувати ФАЛ F(x1, x2, x3, x4) методом невизначених коефіцієнтів для базису І-АБО-НЕ.
№ набору
x1
x2
x3
x4
F(x1, x2, x3, x4) для варіанту:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0
0
0
0
0
0
1
0
1
1
1
1
0
0
0
1
1
0
1
0
1
0
0
0
1
1
1
1
0
1
1
0
1
0
0
1
1
0
0
1
2
0
0
1
0
0
0
0
1
0
1
0
1
0
0
1
0
0
1
0
3
0
0
1
1
1
0
0
1
0
0
1
0
1
1
1
0
1
0
0
4
0
1
0
0
0
1
1
0
1
1
0
0
1
0
1
1
0
1
1
5
0
1
0
1
1
0
1
0
0
1
1
0
0
1
0
1
1
0
1
6
0
1
1
0
1
1
1
0
1
0
1
0
1
0
1
0
0
1
1
7
0
1
1
1
1
0
1
0
1
1
0
1
0
1
0
1
0
0
0
8
1
0
0
0
0
1
1
0
1
1
1
1
1
0
1
0
1
0
0
9
1
0
0
1
0
0
0
1
0
0
0
1
0
0
1
0
0
1
0
10
1
0
1
0
0
1
1
0
1
1
0
1
0
1
0
1
1
0
1
11
1
0
1
1
1
1
0
1
0
0
0
1
1
1
0
1
0
1
1
12
1
1
0
0
0
0
1
0
1
1
1
0
0
0
0
0
0
1
0
13
1
1
0
1
0
0
1
0
0
0
0
1
1
1
1
1
1
0
1
14
1
1
1
0
1
1
0
1
1
0
1
0
1
1
1
1
0
1
0
15
1
1
1
1
0
0
1
0
1
0
1
1
1
1
0
0
0
1
1
Примітка: Для функцій чотирьох змінних система рівнянь у вигляді таблиці наступна:
F0
F1
F2
F3
F4
F5
F6
F7
F8
F9
F10
F11
F12
F13
F14
F15
Контрольні питання:
Що називають базисом ?
Сформулювати означення диз’юнктивної нормальної форми логічної функції.
Що називають рангом терма?
Сформулювати теорему Жегалкіна.
Сформулювати алгоритм методу невизначених коефіцієнтів для мінімізації логічної функції.
Лабораторна робота №3
Мінімізація функцій алгебри логіки методом мінімізуючих карт.
Теоретичні відомості
Отриманий аналітичний вираз функції алгебри логіки (ФАЛ) в ПДНФ або ПКНФ є не єдино можливим, і як правило, не найкращим з погляду економічності.
Здійснення спрощення ФАЛ називається мінімізацією. Мінімізація, здійснена з використанням законів алгебри логіки (закони де Моргана, поглинання, склеювання), називається дужковою, тому що щоразу до спрощення приводимо виведенням за дужки спільних аргументів в кон'юнкціях. Даний спосіб використовується тільки при невеликій кількості змінних, а іноді, як заключний, при мінімізації ФАЛ іншими методами.
Розглянемо приклад 1: Використовуючи закони алгебри логіки мінімізувати функцію
Y(x1, x2, x3) = x1(1 + x2) + 2(x2 + x1) + x3
Рішення.
Y(x1, x2, x3) = x1(1 + x2) + 2(x2 + x1) + x3 =
= x1 1 + x1 x2 + x2 2 + x1 2 + x3
Враховуючи, що x1 1 = 0, x2 2 = 0, x1 x2 + x1 2 = = x1(x2 + 2) = x1.
Маємо Y(x1, x2, x3) = x1 + x3.
Мінімізація - це процес відшукання для заданої ФАЛ такої форми, яка мала б мінімальне число вхідних змінних. Це означає, що при інженерному проектуванні цифрових пристроїв з двох форм, які відображають задану ФАЛ, слід вибрати ту, яка реалізується за допомогою меншої кількості логічних елементів, а при однаковому числі елементів - ту, в якій менше сумарне число вхідних окремих змінних.
Широке практичне застосування завдяки своїй простоті знайшли методи мінімізації, які використовують карти Вейча.
Цими картами є таблиці відповідностей, перетворені таким чином, що у функції, яка нанесена на таку карту, сусідні кон'юнкції знаходяться поряд або на конкретних місцях.
Цифри в клітинках - це десяткові номери відповідних кон'юнкцій максимальної довжини. Клітинки карти Вейча, які не обведені дужками як по вертикалі так і по горизонталі відповідають значенням інверсій змінних.
При мінімізації ФАЛ за допомогою карт Вейча їх краще записувати в ПДНФ.
Для мінімізації перш за все необхідно відшукати сусідні кон'юнкції. Сусідніми клітинками і відповідно їм сусідніми кон'юнкціями максимальної довжини на картах необхідно вважати ті, які знаходяться безпосередньо поряд по горизонталі чи вертикалі, а також ті, що розташовані на протилежних сторонах карти.
Для відшукання сусідніх кон'юнкцій, тобто для мінімізації ФАЛ необхідно нанести її на відповідну карту, тобто на місця, які відповідають десятковим наборам кон'юнкцій, поставити одиниці, а в інших клітинках - нулі. Часто, щоб не затінювати карту, нульові значення не проставляють.
Склеювання сусідніх констант на картах Вейча виконуються їх геометричним об'єднанням в групи, які складаються з прямокутників з площею 2n (n=1, 2, ...), де під площею мається на увазі кількість клітинок, які входять в прямокутник.
Таке об'єднання називається покриттям, а прямокутник з площею 2n правильним. Результат записується у вигляді кон'юнкцій, які входять в покриття.
Чим більша площа покриття, тим менше змінних входить в результат, і чим менше число покриттів, тим менше кон'юнкцій в результаті. Тому необхідно прагнути об'єднати всі одиниці мінімальним числом покриттів максимальної площі.
На підставі вищевикладеного можна сформулювати порядок операцій мінімізації ФАЛ за допомогою карт Вейча:
1. на карту наносяться всі одиничні значення функції;
2. виконується покриття всіх одиничних значень функції мінімальним числом максимальних за площею правильних прямокутників;
3. записується результат у вигляді диз'юнкції кон'юнкцій, які охоплюють кожне окреме покриття.
Розглянемо приклад 2: Використовуючи метод мінімізуючих карт, мінімізувати функцію Y(x1, x2, x3, x4) = ∑(2,3,4,5,8,10,11).
Рішення.
Нанесемо значення ФАЛ на карту Вейча.
Виконуємо покриття всіх одиничних значень ФАЛ мінімальним
числом максимальних за площею правильних прямокутників - потовщена лінія об’єднує значення в карті. (10-й набір належить двом прямокутникам - на карті відтінений).
Прямокутник, що покриває набори 4 і 5, описується термом 1 x2 3. Прямокутник, що покрив набори 8 і 10 - x1 2 4. Прямокутник, який покрив набори 2, 3, 10 і 11 - 2 x3.
Таким чином, представимо розглянуту ФАЛ у вигляді диз'юнкції кон'юнкцій: Y(x1, x2, x3, x4) = ∑(2,3,4,5,8,10,11) = 1 x2 3 + x1 2 4 +
+ 2 x3.
Завдання:
Згідно варіанту, мінімізувати функцію:
1. Використовуючи закони алгебри логіки
№ вар.
Y(x1, x2, x3)
№ вар.
Y(x1, x2, x3)
№ вар.
Y(x1, x2, x3)
1
x1 x2 + x3 + x1
6
x1(x1 + 2) + x1 3
11
12 + x12 + x12 x3
2
x3(2 x1 + x2 x1)
7
(x1 + x2)(x1 + 2 x3)
12
12 x3 + 1 x2 x3
3
x2 + x2 x1 + x3
8
(x3 x2 x1 + 3 x1) x2
13
x1 2 + 21 + x3
4
1 2 + 2 x1 + x3
9
1 + x2 1 + 3 x2
14
1 x23 + 1 x2 x3 + x1 x23
5
x1(3 + x2) + 2(x1 + x3)
10
x1 3 + 2 x1 + x2 x1
15
x1 2 + x1 x2 + x1 x3
2. Використовуючи метод мінімізуючих карт
№ набору
x1
x2
x3
x4
F(x1, x2, x3, x4) для варіанту:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0
0
0
0
0
1
1
0
1
1
1
1
0
0
0
1
0
1
1
0
1
0
0
0
1
0
1
0
1
0
1
0
0
0
0
0
0
0
1
1
2
0
0
1
0
1
0
1
1
0
1
0
1
1
0
0
1
0
1
1
3
0
0
1
1
0
0
0
0
1
0
1
0
1
1
1
1
1
0
0
4
0
1
0
0
1
0
1
0
1
0
1
0
1
1
1
0
1
0
1
5
0
1
0
1
1
0
0
0
0
1
1
0
1
1
0
0
0
1
1
6
0
1
1
0
0
1
1
1
0
0
1
1
1
1
0
0
1
1
0
7
0
1
1
1
0
1
1
1
0
1
0
1
0
0
1
1
0
1
0
8
1
0
0
0
0
1
1
0
1
0
0
1
0
1
0
0
1
0
1
9
1
0
0
1
0
1
1
0
1
0
0
1
0
1
0
1
1
0
0
10
1
0
1
0
1
0
0
0
1
1
1
1
1
1
0
0
1
0
0
11
1
0
1
1
1
0
0
1
0
1
0
0
0
0
1
1
0
1
1
12
1
1
0
0
0
1
0
0
0
1
0
0
0
0
1
1
0
1
1
13
1
1
0
1
1
0
1
1
0
1
0
1
1
1
0
1
0
1
0
14
1
1
1
0
0
1
0
0
1
0
1
0
1
1
0
0
0
0
1
15
1
1
1
1
1
1
0
1
1
0
1
0
1
0
1
0
1
0
0
Контрольні питання:
Для чого виконувати мінімізацію ФАЛ ?
В чому суть “дужкового” методу мінімізації ФАЛ ?
Як застосувати метод карт Вейча для мінімізації ФАЛ ?
Чому потрібно намагатися об’єднати одиничні значення ФАЛ покриттями максимальної площі?
Скільки разів можна об’єднувати одну клітинку з іншими сусідніми в складі різних покриттів?
Які клітинки карти Вейча вважаються сусідніми?
Лабораторна робота №4
Проектування комбінаційних автоматів
Теоретичні відомості
Методика проектування комбінаційного автомата з одним виходом складається з наступних етапів:
1) Згідно таблиці істинності записуємо функцію алгебри логіки в ПДНФ або ПКНФ.
2) Мінімізація ПДНФ (ПКНФ) будь-яким доступним методом.
3) Побудова логічної схеми комбінаційного автомата в базисі заданої серії елементів.
4) Оцінка двоїстого (дуального) варіанту логічної схеми з урахуванням кількості вхідних і вихідних інверторів.
У чому полягає двоїстість логічних схем? Якщо логічні схеми розробляються в базисі І-НЕ і АБО-НЕ, то кожна схема може бути представлена в двох варіантах: основному і двоїстому. Останній по конфігурації схеми нічим не відрізняється від основного, тільки в ньому елементи І замінені на АБО і навпаки, а всі входи і виходи проінвертовані. Однак співвідношення числа елементів в прямому і двоїстому варіантах різне. А ще потрібно враховувати, що в більшості серій елементів входи І та АБО не еквівалентні по витратах устаткування, а кількість необхідних інверторів на входах і виходах прямого і двоїстого варіантів також різна, а отже, майже завжди варіанти відрізняються як по кількості витраченого устаткування, так і по кількості послідовно включених елементів. Тому при розробці комбінаційного автомата необхідно оцінювати обидва варіанти і вибирати
14.05.2018 22:05-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора