МІНІСТЕРСТВО ТРАНСПОРТУ ТА ЗВ’ЯЗКУ
Державний департамент з питань зв’язку та інформатизації України
ДЗ «Київський коледж зв’язку»
ПОГОДЖЕНО ЗАТВЕРДЖЕНО
Цикловою комісією КСМ Заступник директора з НР
Голова комісії ______ А.Ю. Лойкова ___________ В.С. Шматко
„___” ____________ 20__р. „___” ___________ 20__р.
ПЕРЕТВОРЕННЯ ЛОГІЧНИХ ВИРАЗІВ
Опис практичної роботи №1
з предмету: «Обчислювальна техніка та мікропроцесори»
(Методичні вказівки)
Розробив викладач
___________ Лойкова А.Ю.
„___” ___________ 20___р.
Київ
1. МЕТА РОБОТИ :
1.1. Вивчити і практично закріпити основні теоретичні положення лекційного матеріалу:
- вивчити правила і закони алгебри логіки;
- закріпити знання про перетворення логічних виразів методами Квайна і діаграм Вейча.
2. ОCHOBHI ТЕОРЕТИЧНІ ВІДОМОСТІ
2.1. Цифрові (логічні) схеми працюють в режимі двійкового рахунку, де кожна вхідна і вихідна напруги представлені логічним 0 або 1, символи 0 і 1 представляють наказані їм рівні напруги 0-низький, 1-високий рівень напруги. Ця особливість логічних схем дозволяє скористатись бульовою алгеброю для аналізу і проектування цифрових систем. Бульова алгебра – це математичний апарат, що дозволяє описати зв'язки між виходами і входами логічних схем за допомогою алгебраїчних рівнянь (бульовими виразами).
Бульову функцію можна задати трьома способами:
змістовно ( словесний опис);
таблично (таблиця істинності);
алгебраїчно.
Алгебраїчний спосіб задання бульової функції представляє собою формулу зв'язану простішими логічними операціями І, АБО, НЕ, І-НЕ, АБО-НЕ (табл. 1).
Способи задания бульового виразу.
Таблиця 1
Логічна операція (назва функції) |
Задання функції формулою |
Таблиця істинності |
||
входи |
виходи |
|||
Х2 |
Х1 |
f(х1,х2) |
||
І (кон’юнкція, логічне множення) |
f(х1,х2)= х1*х2; f(х1,х2)= х1х2 f(х1,х2)= х1х2 f(х1,х2...хn)= х1х2... хn |
0 0 1 1 |
0 1 0 1 |
0 0 0 1 |
АБО (диз’юнкція, логічне додавання) |
f(х1,х2)= х1+х2 f(х1,х2)= х1х2 f(х1,х2...хn)= х1х2...хn |
0 0 1 1 |
0 1 0 1 |
0 1 1 1 |
НЕ (інверсія, заперечення) |
|
|
0 1 |
1 0 |
І-НЕ (функція Шеффера) |
f(х1,х2)= х1|х2
|
0 0 1 1 |
0 1 0 1 |
1 1 1 0 |
АБО-НЕ (функція Пирса) |
f(х1,х2)= х1+х2
|
0 0 1 1 |
0 1 0 1 |
1 0 0 0 |
Алгебраїчний запис логічного виразу може бути громіздким, і побудова логічної схеми за даним виразом буде неекономною. Тому перш за все необхідно спростити логічний вираз, використовуючи метод тотожних перетворень, які базуються на послідовному використанні відповідно до формули законів і правил тотожних перетворень алгебри логіки, таблиця 2.
Основні співвідношення алгебри Буля Таблиця 2
№ п/п |
Логічне додавання (а) |
Логічне множення (b) |
Співвідношення алгебри Буля |
|
|
|
|
закон |
правило |
1 |
х1х2= х2 х1 |
х1х2= х2х1 |
переставний |
|
2 |
(х1х2)х3= х1(х2х3) |
(х1х2)х3= х1(х2х3) |
сполучний |
|
3 |
(х1х2)х3=х1х3 х2х3 |
х1(х2х3)=(х1х2)(х1х3) |
розподільний |
|
4 |
|
|
|
де Моргана |
5 |
х0= х |
х*1=х |
|
повторення |
6 |
х1= х |
х*0=0 |
||
7 |
хх= х |
х*х=х |
||
8 |
хх= 1 |
х*х=0 |
||
9 |
х1х2 х1х2= х1(х2х2)=х1 |
(х1х2)(х1х2)=х1 |
|
склеювання |
10 |
х1 х1х2= х1 |
х1(х1х2)= х1 |
|
поглинання |
11 |
|
|
інверсія
|
|
12 |
|
подвійне заперечення |
||
13 |
f(x)=x |
повторення |
|
Розглянемо процес спрощення виразів на прикладах.
Приклад 1. Логічна функція від трьох змінних f(х1,х2,х3)=х1х2 х1х2 х2х3х1х2
спрощується наступним способом:
за правилом 7а
за правилом 9а
У результаті перетворення логічна функція має вид
Приклад 2. Відома логічна функція
Спрощуємо;
по закону 3а
за правилом 7b
за правилом 13
по закону 6а
У результаті одержуємо
Процес спрощення логічного виразу, який оснований на тотожних перетвореннях носить назву мінімізація.
Розрізняють алітичні і табличні методи мінімізації. Для запису однієї і тієї ж функції алгебри логіки можна використовувати канонічні форми представлення функцій:
- доскональна диз'юнктивна нормальна форма(ДДНФ);
- доскональна кон'юнктивна нормальна форма(ДКНФ).
ДДНФ визначається як сума елементарних добутків, в яких кожна зміна зустрічається рівно один раз або з запереченням, або без нього, наприклад:
ДКНФ визначається як добуток елементарних сум, в яких кожна змінна зустрічається рівно один раз або з запереченням, або без нього, наприклад:
2.2. Мінімізація методом Квайна.
Мінімізацію по Квайну потрібно починати із ДДНФ функції. Якщо функція задається в довільній формі, то її необхідно перетворити до ДДНФ.
Для цього член в записі функції, який не містить якого-небудь аргумента, множимо на логічну одиницю , і таким чином одержуємо два члена, які містять весь набір аргументів, а потім до функції застосовуємо операції склеювання і поглинання, щоб одержати скорочену ДНФ функцію.
Розглянемо етапи мінімізації логічної функції , заданій в ДДНФ.
В даній функції - об'єднуємо елементарні добути, отримаємо - , маємо .
У результаті застосування правила склеювання у виразі логічної функції зменшується число підсумовуваних добутків і число змінних.
Таким чином, мінімізація функцій Буля проводиться за допомогою законів і теорем алгебри логіки, теореми де Моргана, закона подвійного заперечення і правил поглинання і склеювання.
2.3. Мінімізація функцій Буля за допомогою карт Карно (табличний метод).
Карта Карно — це прямокутник, розбитий на квадрати (комірки), число яких дорівнює 2n , де n- число логічних змінних. Структура карт Карно для 2-х, 3-х, 4-х змінних показана на мал. 3.
Карти Карно
Мал.З а) для функції 2-х аргументів;
б) для функції 3-х аргументів;
в) для функції 4-х аргументів;
Комірки карти відповідають значенням вхідних змінних. Наприклад, верхній рядок карти для функції 3-х змінних відповідає "1", тобто значення х1=1, а нижній рядок - нульовому значенню х1=0 кожний стовпчик характеризується значенням двух змінних х2 і х3.
Для табличної заданої функції у комірки карта Карно проставляють значення функції для відповідних наборів аргументів, мал.4.
Пошуки мінімальної форми функції зводяться до визначення областей, які містять по 2k комірок, де 2- число, k-ціле число (0, 1, 2...). В області об'єднуються сусідні комірки, які відповідають сусіднім елементарним добуткам мал. 4.
Мал. 4
Такій мінімізації відповідає вираз: . Карти Карно можна уявно звертати, що дасть змогу побачити найбільш короткі імплеканти результуючі кон'юнкції, мал.5.
Карти Карно і мінімальний запис логічних функцій:
Мал. 5 а- для 3-х змінних, б,в- для 4-х змінних
Аналізуючи карти Карно, мал. 5, бачимо, що одна і таж комірка ( наприклад, комірка з координатами х2х3) може покриватися два або декілька разів. Таким чином, формула, одержана в результаті мінімізації логічної функції за допомогою карт Карно, містить суму стількох елементарних добутків, скільки областей є в карті. Чим більше комірок в області, тим меньше змінних міститься у відповідному йому симентарному добутку.
3. ДОМАШНЕ ЗАВДАННЯ:
Вивчити відповідний теоретичний матеріал по підручнику п.1ст. 101,102,123,126
Підготувати відповіді на наступні запитання:
3.2.1. Записати довільну кон'юнкцію для логічної функції 5-ти змінних.
3.2.2. Довести тотожність, відмічаючи закон і правила алгебри логіки застосовувані на кожному кроці перетворення: .
3.2.3.Проаналізувати відповідні таблиці, вибрати правильну відповідь і записати її.
Таблиця 3
Питання |
Відповідь |
||||||||||||||||
1.Зробити мінімізацію логічних функцій
|
1. 2. 3. 4. 5. |
||||||||||||||||
2.
|
1. 2. 3. 4. 5. |
3.3. Заготовити звіт по даній роботі, для чого записати:
номер практичної роботи,
- назву практичної роботи,
мету;
письмово відповісти yа запитання домашнього завдання п.п. 3, 4, 5.
4. ПОРЯДОК ВИКОНАННЯ РОБОТИ:
4.1. По заданому варіанту таблиці 4,5 перетворити логічний вираз:
методом Квайна;
методом Карно.
Порівняти отримані результати.
Відповісти на контрольні запитання.
Зробити висновки по роботі.
5 КОНТРОЛЬНІ ЗАПИТАННЯ:
Які основні розпізнавальні особливості логічних змінних?
Назвіть основні закони алгебри логіки.
Які існують способи задания логічних функцій?
Використовуючи основні закони алгебри (Бульової), спростити наступні вирази:
a).
б).
в)
5.5.Отримайте заперечення наступних виразів:
a).
б).
в).
Таблиця 4
|
f(x1x2x3) |
|||||||||||||
х1 |
х2 |
х3 |
f1 |
f2 |
f3 |
f4 |
f5 |
f6 |
f7 |
f8 |
f9 |
f10 |
f11 |
f12 |
0 0 0 0 1 1 1 1 |
0 0 1 1 0 0 1 1 |
0 1 0 1 0 1 0 1 |
1 0 0 1 0 0 1 1 |
0 1 1 1 0 1 0 1 |
1 0 1 0 0 0 1 0 |
0 1 1 1 1 1 0 0 |
0 1 1 0 0 1 1 1 |
0 1 0 1 0 0 1 0 |
1 1 0 0 1 1 1 0 |
0 0 1 0 1 1 1 1 |
1 0 1 1 0 1 1 0 |
1 1 1 0 1 0 0 1 |
0 1 1 0 1 0 1 1 |
1 1 0 1 1 1 0 0 |
Таблиця 5
|
f(x1x2x3) |
||||||||||||
х1 |
х2 |
х3 |
f13 |
f14 |
f15 |
f16 |
f17 |
f18 |
f19 |
f20 |
f21 |
f22 |
f23 |
0 0 0 0 1 1 1 1 |
0 0 1 1 0 0 1 1 |
0 1 0 1 0 1 0 1 |
0 0 1 1 0 1 0 1 |
0 1 1 0 0 1 1 1 |
1 0 0 0 1 1 1 0 |
1 1 1 0 0 1 0 0 |
1 1 0 0 1 1 0 1 |
0 0 0 1 1 1 0 1 |
0 1 0 1 0 1 1 0 |
1 0 1 1 1 0 0 1 |
0 0 1 0 0 1 1 1 |
1 1 1 0 1 0 1 0 |
1 0 1 1 1 0 1 0 |
6. ЛІТЕРАТУРА
6.1. Калабеков Б.А., Мамзелев Н.А. "Цифрові пристрої та мікропроцесорні системи" М. Радіо і звязок, 1987р.
6.2. Скаржева В.А., Луценко А.Н. "Електроніка та мікросхемотехніка"(2ч.) Київ, Вища школа, 1978р.