МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
ЛЬВІВСЬКИЙ ДЕРЖАВНИЙ ІНСТИТУТ НОВІТНІХ ТЕХНОЛОГІЙ ТА УПРАВЛІННЯ ІМ. В. ЧОРНОВОЛА
Логічні основи
цифрової схемотехніки
Методичні вказівки
до практичних занять № 2 з дисципліни
“Комп’ютерна схемотехніка ”
Затверджено
на засіданні кафедри КСМ
Протокол № 1 від 29.08. 2008 р.
ЛЬВІВ 2008
Арифметико-логічні основи цифрової схемотехніки. Методичні вказівки до практичних занять № 2 з дисципліни "Комп’ютерна схемотехніка”.
Упорядники: Сергій Сергійович Івчук, ст. Викладач каф. Ксм Логічні основи комп’ютерної схемотехніки
1. Теоретичні основи алгебри логіки
Можливість опису цифрових схем за допомогою є зручною за двох причин. Перша – за допомогою формул зручно перевіряти роботу схеми. Друга – формування умов роботи довільної цифрової схеми у вигляді формул алгебри логіки не тільки спрощує процес розробки цифрових схем, так і в багатьох випадках автоматизованого створення даних схем.
В даний час основна задача алгебри логіки – аналіз, синтез та структурне моделювання довільних дискретних систем. Апарат булевої алгебри поширюється на об’єкти різноманітної природи інваріантне до їх природи, тільки б вони характеризувалися двома значеннями або двома станами: контакт увімкнений або вимкнений. В нашому випадку наявність високого або низького рівня напруги, виконання або невиконання деякої умовної роботи та ін.
Основне поняття алгебри логіки – висловлювання. Висловлювання – деяке твердження, про яке можемо говорити, що воно істинне (позначимо символом 1), або воно фальшиве (позначимо символом 0). Позначивши, власне висловлювання символом х можемо застосувати визначення булевої змінної.
Логічна (булева) змінна – така величина х, яка може приймати тільки два значення: х = {0, 1}.
Висловлювання абсолютно істинне, якщо відповідна їй логічна змінна приймає значення 1 при довільних умовах.
Висловлювання абсолютно фальшиве, якщо відповідна їй логічна змінна приймає значення 0 при довільних умовах.
За допомогою логічних зв'язок НЕ, АБО, І, ЯКЩО…ТО… формують складні висловлювання, які називають логічними (булевими) функціями. Звідки, логічна функція – функція f(x1, x2, …, xn), яка приймає значення, рівне нулю або рівне 1 на наборі логічних змінних x1, x2, …, xn.
Операція – чітко визначена дія над одним або декількома операндами, яка створює новий об’єкт (результат).
Основними булевими операціями є заперечення (операція НЕ, інверсія), диз’юнкція (операція АБО, логічне додавання, об’єднання) та кон’юнкція (операція І, логічне множення).
Заперечення – це одномісна булева операція f = (читається «не х»), результатом якої є значення, протилежне значенню операнди.
Диз’юнкція – це булева операція f = х1 х2 (читається «х1 або х2»), результатом якої є значення 0 тоді і тільки тоді, коли обидва операнди мають значення 0.
Кон’юнкція – це булева операція f = х1 х2 (читається «х1 і х2»), результатом якої є значення одиниці тоді і тільки тоді, коли значення кожного операнди рівне 1. В даній булевій операції допускається і наступні записи «х1 х2» або «х1 х2».
Операції заперечення, диз’юнкції та кон’юнкції зручно подавати таблицею істинності табл.1, 2.
Таблиця 1 Таблиця 2
х |
f = |
|
х1 |
х2 |
f = х1 х |
f = х1 х2 |
0 |
1 |
|
0 |
0 |
0 |
0 |
1 |
0 |
|
0 |
1 |
1 |
0 |
|
|
|
1 |
0 |
1 |
0 |
|
|
|
1 |
1 |
1 |
1 |
З табл. 3 видно, що елементарні функції заперечення, кон’юнкції, диз’юнкції, Шиффера, Пірса, імплікації та інші знаходяться в певному зв’язку один з другим.
Використовуючи положення алгебри логіки, не складно переконатися в справедливості наступних аксіом. Нехай х – довільна логічна змінна. Тоді:
-
х = , що означає можливість виключення з логічного виразу всіх членів, які мають подвійне заперечення, замінивши їх вихідною величиною;
-
х + х = х; х х = х – правила таких перетворень, дозволяють скоротити довжину логічних виразів;
х + 0 = х; |
х 0 = 0; |
х = 0; |
х + 1 = 1; |
х 1 = 1; |
х = 1. |
Логічні функції від двох змінних подано в табл. 3.
Таблиця 3.
х1 0011 х2 0101 |
Вираз |
Назва операції |
|
f0 |
0000 |
f0 = 0 |
Константа 0 |
f1 |
0001 |
f1 = х1х2 f1 = х1 х2 |
Кон’юнкція |
f2 |
0010 |
f2 = f2 = |
Заборона по х2 |
f3 |
0011 |
f3 = х1 f3 = х1х2 = х1 |
Повторення х1 |
f4 |
0100 |
f4 = f4 = |
Заборона по х1 |
f5 |
0101 |
f5 = х2 f5 = х1х2 = х2 |
Повторення х2 |
f6 |
0110 |
f6 = х1х2 |
Сума за модулем 2 |
f7 |
0111 |
f7 = х1 х2 |
Диз’юнкція |
f8 |
1000 |
f8 = х1 х2 (функція Пірса) |
Заперечення диз’юнкції |
f9 |
1001 |
f9 = х1 х2 (рівнозначність) |
Еквівалентність |
f10 |
1010 |
f10 = f10 = |
Заперечення х2 |
f11 |
1011 |
f11 = х1 х2 |
Імплікація від х2 до х1 |
f12 |
1100 |
f12 = f10 = |
Заперечення х1 |
f13 |
1101 |
f13 = х1 х2 |
Імплікація від х1 до х2 |
f14 |
1110 |
f14 = х1 х2 (функція Шеффера) |
Заперечення кон’юнкції |
f15 |
1110 |
f15 = 1 |
Константа 0 |
Диз’юнкція та кон’юнкція володіють властивостями, аналогічними властивостям звичайних арифметичних операцій додавання та множення:
-
властивість асоціативності (сполучний закон):
х1 (х2 х3) = (х1 х2) х3; х1 (х2 х3) = (х1 х2) х3;
-
властивість комутативності (переміщувальний закон):
х1 х2 = х2 х1; х1 х2 = х2 х1;
-
властивість дистрибутивності (розподільчий закон):
-
для кон’юнкції відносно диз’юнкції
х1 (х2 х3) = (х1 х2) (х1 х3);
-
для диз’юнкції відносно кон’юнкції
х1 х2 х3 = (х1 х2) (х1 х3).
Згідно табл. 3, визначено ще перелік нових функцій (операцій):
Виключення (заборона) – двомісна булева операція, результатом якої є значення одиниці тоді і тільки тоді, коли значення одного опе6ранда рівне одиниці, а іншого – нулю. Записується у вигляді:
або .
Сума за модулем два (виключне або, заперечення еквівалентності) – двомісна булева операція, результатом якої є значення одиниці тоді і тільки тоді, коли операнди мають різні значення. Записується у вигляді:
.
Заперечення диз’юнкції (операція НЕ-АБО, інакше стрілка Пірса) – булева операція, результатом якої є значення одиниці тоді і тільки тоді, коли обидва операнди рівні нулю. Позначається наступним чином:
.
Узагальнюючи для n змінних, отримаємо:
.
Еквівалентність (рівнозначність) – двомісна булева операція, результатом якої є значення одиниці тоді і тільки тоді, коли операнди набувають однакових значень. Записується у вигляді:
.
Імплікація (включення) – двомісна булева операція, результатом якої є значення нуль тоді і тільки тоді, коли значення одного з операндів дорівнює нулю, а іншого одиниця. Позначаємо наступним чином:
.
Заперечення кон’юнкції (операція НЕ-І, інакше штрих Шефера, інакше заперечення перетину) – булева операція, результатом якої є значення нуль тоді і тільки тоді, коли обидва операнди дорівнюють одиниці. Позначаємо у вигляді:
Узагальнюючи для n змінних, отримаємо:
.
Приклад: проведемо доведення виразу х1 х2 х3 = (х1 х2) (х1 х3):
-
за допомогою вище викладених аксіом
(х1 + х2) (х1 + х3) = х1 х1 + х1 х3 + х2 х1 + х2 х3 = х1 + х1 х3 + х2 х1 + х2 х3 =
х1(1 + х3 + х2) + х2 х3 = х1 1+ х2 х3 = х1 + х2 х3.
-
за допомогою таблиці істинності
х1 |
х2 |
х3 |
х2 х3 |
х1 + х2 х3 |
х1 + х2 |
х1 + х3 |
(х1 + х2) (х1 + х3) |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Порівнюючи стовпці правої та лівої частини бачимо, що вони ідентичні, тобто права частина, тотожна лівій частині виразу який аналізуємо.
Аналогічно можемо довести інші закони.
Нескладно визначити правильність співвідношень, відомих як закони де Моргана:
=
=
Із законів де Моргана можемо отримати вирази алгебри логіки за допомогою яких можливо подавати кон’юнкцію через диз’юнкцію та заперечення, або диз’юнкцію через кон’юнкцію на заперечення
х1х2 =
х1 + х2 =
Для логічних функцій встановлюються співвідношення, відомі як закони поглинання:
х1 + х1х2 = х1,
х1(х1 + х1) = х1.
Областю визначення булевої функції f(x1, x2, …, xn) є скінчена множина різних двійкових наборів довжиною n, на кожному з яких вказується значення функції 0 або 1. Кількість двійкових наборів дорівнює множині n-розрядних двійкових чисел m = 2n.
Довільну булеву функцію можемо задавати різними способами: за допомогою логічних виразів та таблиці істинності, як подано вище, словесним описом, геометричними фігурами та графами.
Н априклад функцію f(x1, x2) можемо подати як f = 1 при x1 x2 = 1 та f = 0, якщо x1 x2 = 0. Дану функцію можемо зобразити діаграмою (рис.1, а) або геометрично за допомогою двовимірного куба (рис.1, б), а також графом де вершини відображають значення 0 та 1, а на орієнтованих дугах змінні вказують на умови переходів.
Булеві функції одного або двох аргументів називають елементарними. Схема, яка здійснює елементарну логічну операцію, називають логічним елементом (вентилем). Сукупність взаємозалежних логічних елементів з формалізованими методами опису називається логічною схемою.
Назви та умовні графічні позначення основних елементів, які застосовуються в комп’ютерній схемотехніці подано на рис. 2. Значення змінних (операндів) відображаються електричними сигналами (напругою) з двома чітко вираженими рівнями значень.