Аналіз теорії цифрових автоматів
(курсова робота)
Содержание
Двійкова арифметика
Системи числення з довільною основою
Мішанісистеми числення
Форма з фіксованою крапкою
Форма з плаваючою крапкою
Прямий, зворотній та доповнюючий коди чисел
Поняття про булеві функції
Аналітичне представлення булевих функцій
Мінімізація булевих функцій
Метод квайна-мак-класкі
Висновок
Висновок
Література
Теорія цифровихавтоматів закладає теоретичні основи роботи комп’ютерної техніки. У данійкурсові роботі проводиться аналіз математичного підгрунтя даної дисципліни.
Двійкова системачислення
Двійкова позиційнасистема числення
Позиційна системачислення з основою 2 називається двійковою. Для запису чисел в двійковійсистемі використовуються лише дві цифри: 0 і 1. Число два, тобто основа системиподається як 102.
Зручність системи — в її надзвичайній простоті.
Недолік — основасистеми мала, тому для запису навіть не дуже великих чисел требавикористовувати багато знаків.
Переведення числаз двійкової системи числення в десяткову та з десяткової у двійкову.
Нам уже відомо, щочисло N, записане в системі числення з основою p як (±akak-1…a1a0)p, рівне N=ak∙pk+ak-1∙pk-1+…+a1∙p+a0
Тому:
10012=1∙23+0∙22+0∙21+1∙20=8+0+0+1=910
1000012=1∙25+0∙24+0∙23+0∙22+0∙21+1∙20=32+0+0+0+0+1=3310
Щоб перевестичисло із десяткової системи числення у двійкову, треба послідовно ділитидесяткове число і його десяткові частки на основу двійкової системи, тобто начисло 2. Ділення продовжується до тих пір, поки одержана частка не буде меншаоснови нової системи числення, тобто 2.
1 |40|2_
/> 0 |20|2_
0 |10|2
0|5|2
1|2|2
0|1
Отже число 8110в двійковій системі: 10100012
Переведемо число100:
100|2_
0 |50|2_
/> 0 |25|2_
1 |12|2
0|6|2
1|3|2
1|1
Отже, (100) 10=(1100100) 2
З переводом чиселз десяткової системи одиниць у двійкову приходиться постійно мати справу прироботі на ЕОМ.
Окрему позицію взаписі числа називають розрядом. Число розрядів — розрядність (довжина). Номерпозиції — номер розряду. Довжина числа — це к-сть позцій (розрядів) в записічисла. В технічному розумінні це довжина розрядної сітки.
Чим менша основасистеми, тим більша довжина числа. Якщо довжина розрядної сітки n, то: Aqmax=qn-1; Aq min= — (qn-1);
Діапазонпредставлення чисел в заданій системі:
Aq max ≥ДП≥Aq min.
Двійкова арифметика
Арифметичні дії вдвійковій системі (двійковій арифметиці) виконуються за звичайними дляпозиційних систем правилами (алгоритмами), які нам відомі з десятковоїарифметики, але при цьому, звичайно, використовуються таблиці додавання імноження двійкової системи.
Таблиця додавання
0+0=0
0+1=1
1+0=1
1+1=102
(додавання нуля неміняє числа, а один плюс один буде два).
Таблиця множення
0∙0=0
0∙1=0
1∙0=0
1∙1=1
(число, помноженена нуль, є нуль; множення на один не міняє числа).
Додавання. Додаваннябагатозначних чисел відбувається так само, як і в десятковій системі, тобтопорозрядно, починаючи з молодшого.
1011012 — 1 доданок
+ 101002 — 2 доданок
10000012 — сума
Перевіримоправильність наших обчислень:
1011012=1∙25+0∙24+1∙23+1∙22+0∙21+1∙20=32+0+8+4+0+1=4510
101002=1∙24+0∙23+1∙22+0∙21+0∙20=16+0+4+0+0=2010
4510+2010=6510
10000012=1∙26+0∙25+0∙24+0∙23+0∙22+0∙21+1∙20=64+0+0+0+0+0+1=6510
Віднімання
0-0=0
1-0=1
1-1=0
102-1=1
Знайдемо: 1110101112-11000012
1110101112
— 11000012
1011101102
4 Крапки, поставлені над деякими розрядами, показують, що вдвійковій системі одиниця відміченого розряду роздроблюється на дві одиницівищого розряду.
Множення
111012∙11012
111012 — множник
11012 — множник
11101 — множене
+11101 — множене,зсунуте на 2 розряди вліво
11101 — множене,зсунуте на 3 розряди вліво
1011110012 — добуток
Перевірка:
111012=1∙24+1∙23+1∙22+0∙21+1∙20=16+8+4+1=2910
11012=1310;29∙13=37710
1011110012=1∙28+0∙27+1∙26+1∙25+1∙24+1∙23+0∙22+0∙21+1∙20=256+0+64+32+16+8++0+1=37710.
Отже, в двійковій арифметиці при множенні непотрібна таблиця множення. Не треба знаходити добутки першого множника назначення послідовних розрядів другого множника, так як значення цих розрядівабо 1 або 0.
Достатньо записати значення першого множникаодне під одним із зсувом на один розряд; у випадку рівності якого-небудьрозряду другого множника нулю, його зсувають на два розряди.
11011112
1011012
1101111
1101111
1101111
1101111 __
10011100000112Системи числення з довільною основою
Ми розглянулиалгоритм переводу чисел з двiйкової системи числення в десяткову i навпаки — здесяткової в двiйкову. Алгоритми залишаться цiлком аналогiчними, якщо замiстьдвiйкової системи числення взяти будь-яку iншу.
Нехай, наприклад,деяке число записане в вiciмковiй системi числення. Це значить, що цифри взаписі цього числа є коєфiцiєнти в його розкладi по степенях числа 8:
(anan-1…a1a0, a-1a-2. .) 8 =an*8n+an-1*8n-1+…+a1*8+a0+a-1*8-1+...
Для того, щоботримати зображення цього числа в десятковiй системi числення, достатньовиконати, користуючись десятковою арифметикою, всi операцiї в правiй частинiцього виразу. Приклад. Перевести число (276,54) 8 з вiсiмкової системичислення в десяткову:
(276,54) 8=2*82+7*81+6*80+5*8-1+4*8-2=128+56+6+5/8+4/64=(190,6875) 10.
Нехай теперпотрiбно перевести число з десяткової системи числення в вiсiмкову. Як i увипадку переводу в двiйкову систему числення, розглянемо окремо цiлу i дробовучастини чисел. Для цiлої частини скористаємось алгоритмом дiлення, а длядробової — множення. В першому випадку ми отримаєм шукане вiсiмкове зображенняцiлого числа, зiбравши в зворотньому порядку залишки вiд дiлення на 8, а удругому випадку отримаємо вiсiмкове зображення дробу, зiбравши в прямомупорядку цiлi частини при послiдовному множеннi на 8. Приклад. Перевести число (190,6875)10 з десяткової системи числення в вiсiмкову.
Переведемо цiлучастину:
190 |8
16 | 23 |8
30 16|2 |8 (190)10=(276)8
8 6 7 2 | 0
Переведемо дробовучастину:
0| 6875 (0,6875)10=(0,54)8
5 | 5000
4 | 0
тобто (190,6875)10=(276,54)8.
Цей приклад разомз попереднiм iлюструє, як можна перевiряти правильнiсть переводу з однiєї системичислення в iншу зворотнiм переводом.
Виконанняарифметичних дій в СЧ з основою р.
Змішані СЧ. Записчисел в змішаних СЧ. Системи з кратними основами. Теорема для СЧ з кратнимиосновамиМішані системи числення
Існує простий спосібзапису десяткових чисел за допомогою двійкових цифр — представлення чисел в мішанійдвійково-десятковій системі числення. В ній кожна цифра десяткового зображеннячисла записується в двійковій системі числення.
Причому для того,щоб такий запис був однозначним, для представлення будь-якої десяткової цифри відводитьсяодна і та ж кількість двійкових розрядів — чотири. Якщо десяткова цифра вимагаєдля свого представлення менше значущих двійкових цифр, то попереду цих цифрдописуються нулі (так щоб загальна кількість двійкових знаків залишалась рівноючотирьом). Наприклад, десяткове число 834,25 в двійково-десятковій системізапишеться так:
(834,25) 10 =(1000 0011 0100,0010 0101).
Кожна четвірка (тетрада)двійкових цифр тут відповідає одній десятковій цифрі:
(8)10 = (1000)2-10 (2)10= (0010)2-10
(3)10 = (0011)2-10 (5)10= (0101)2-10
(4)10 = (0100)2-10
11 Теорема. Якщо P = Qn (P, Q, n — цілі додатнічисла), то запис любого числа в мішаній (Q — P) — й системі числення тотожньоспівпадає з записом цього ж числа в системі числення з основою Q (з точністю донулів на початку запису цілої частини числа і на кінці дробової).
Якщо P=8, Q=2,n=3, то 8=23 і, отже, згідно даної теореми запис будь-якого числа вдвійково-вісімковій системі співпадає з записом того ж числа в двійковій системі.(Зауважимо, що за тією ж теоремою записи будь-якого числа в двійковій і двійково-шістнадцятковійсистемах теж співпадуть). Переведемо, наприклад, все теж число (405) 10з десяткової системи числення в шістнадцяткову:
405|16
32 |25|16
85 9|1 |16
80 |0
5
Збираючи залишки відділення, отримаємо (405) 10 = (195) 16.
Представимо теперчисло (195) 16 в двійково — шістнадцятковому записі: (195) 16= (1 1001 0101) 2-6.
Видно, що записичисла в двійковій і двійково-шістнадцятковій системах вuявuлuсь однаковими. Цявластивість двійково-вісімкової системи числення дозволяє дуже простопереводити числа з двійкової системи в вісімкову (чи шістнадцяткову) і навпаки.
Справді, будь-якийдвійковий запис розглядаємо як двійково-вісімковий код деякого вісімковогочисла, розбиваємо його на трійки (тріади) двійкових цифр ліворуч і праворуч відкоми. Кожній такій трійці ставимо у відповідність одну вісімкову цифру і отримаємочисло в вісімковій системі числення.
Візьмемо,наприклад, код:
(10 011 110,001 1)2= (236,14)8 .
2 3 6 1 4
12 Тут, як і в двійково-десятковому записі, в цілій частині відкинутікрайні зліва нулі, а в дробовій частині — крайні справа. Безумовно, треба їхвраховувати як недостатні у відповідних тріадах двійкових цифр. Зворотній перевідчисел з вісімкової системи числення в двійкову також простий. Кожну цифру вісімковогочисла записуємо трійкою двійкових символів, тобто записуємо його в двійково-вісімковійсистемі, а так як цей запис співпадає з двійковим, то ми одержимо число в двійковійсистемі. Переведемо, наприклад, число (3514,72) 8 з вісімковоїсистеми в двійкову:
(3514,72)8 = (11 101001 100,111 01)2 .
3 5 1 4 7 2
Звідси слідує, щовісімкову систему числення можна використовувати для скороченого запису любогодвійкового коду. При цьому використовується приблизно в двічі менше символів,якщо розбити їх на трійки цифр і кожну записати однією вісімковою цифрою. Таксамо запис будь-якого числа в шістнадцятковій системі числення можнавикористовувати для скороченого запису двійкового коду. В цьому випадку кожномушістнадцятковому символу взаємно однозначно відповідає набір з чотирьох двійковихцифр:
(0)16 =(0000)2 (8)16 = (1000)2
(1)16 =(0001)2 (9)16 = (1001)2
(2)16 =(0010)2 (а)16 = (1010)2= (10)10
(3)16 =(0011)2 (b)16 = (1011)2= (11)10
(4)16 =(0100)2 (c)16 = (1100)2= (12)10
(5)16 =(0101)2 (d)16 = (1101)2= (13)10
(6)16 =(0110)2 (e)16 = (1110)2= (14)10
(7)16 =(0111)2 (f)16 = (1111)2= (15)10 .
Так як записичисла в двійково-шістнадцятковій і двійковій системах за сформульованою вищетеоремою співпадають, то, замінивши всі шістнадцяткові цифри деякого числа на відповіднічетвірки двійкових цифр, отримаємо таке ж число в двійковій системі числення. Прицьому запис числа буде використовувати приблизно в чотири раза менше цифр, ніжв двійковій системі числення. Наприклад, число (3c2e9) 16 може бутипредставлене в двійковій системі числення наступним чином: (11 1100 0010 11101001) 2.
3 c 2 e 9
13 Під кожною четвіркою двійкових цифр ми записали відповіднийішістнадцятковий символ. Дві форми комп’ютерного представлення числових даних. Їхпереваги і недоліки.
Форма з фіксованою крапкою
В сучасних ЕОМзастосовуються два способу представлення чисел: з фіксованою крапкою іплаваючою крапкою.
В першому випадкумісце коми, яка відділяє цілу частину числа від дробової, визначається на етапіконструювання ЕОМ. Зразу ж вказується кількість розрядів, які відводяться длязображення цілої і дробової частин. Причому кожному розряду комірки відповідаєзавжди один і той же розряд числа, що суттєво спрощує виконання арифметичних дій.
Нехай, наприклад,комірка пам’яті машини має 24 двійкових розряда. Як ми знаємо, в комірку можназаписати будь-яке машинне слово, тобто довільний набір з нулів і одиниць. Якщоце слово — число, то в конструкції машини може бути передбачено йогопредставлення в формі з фіксованою комою. Наприклад, воно може бути таким: крайнійзліва розряд — знаковий, потім наступні 9 розрядів відводяться під цілу частинуі, накінець, 14 розрядів, які залишилися, під дробову частину числа, тобто коматут завжди на одному і тому ж місці — після десятого розряду машинного слова (зврахуванням знакового розряду). Тоді найбільше число, яке можна представити,буде: (111111111,11111111111111) 2.
Видно, що вономенше, ніж 29 = (512) 10. А найменше за модулем відмінневід нуля число дорівнює
(000000000,00000000000001)2 = 2-14.
Тобто, діапазончисел, які можна записати в комірку пам’ті машини, тут такий:
2-14
Форма з плаваючоюкрапкою.
Для того, щоб збільшитидіапазон чисел, використовують другу форму запису чисел — з плаваючою комою. Будь-якечисло в системі числення з основою Q можна записати так:
a=A*Qp.
A називаютьмантисою числа, а P — порядком.
14 Наприклад, в десятковій системі числення число 3,14представимо у вигляді
3,14 = 0,314*101.
Тут мантиса дорівнює0,314, а порядок 1. Очевидно, таке представлення далеко не однозначне. Число 3,14записати так:
3,14=3,14*100= 31,4*10-1 = 0,0314*102 =...
Порядок числавизначає положення коми в запису мантиси. При коректуванні порядку відповіднимчином змінюється і положення коми — кома ніби ”плаває".
Звідси і назваметоду представлення чисел. З плаваючою комою число, як ми тільки що бачили,представляється неоднозначно. Одне з цих представлень називають нормалізованим.
В цьому випадкумантиса повинна задовільняти вимозі 1/10
9. Представленнядовільного числа в формі з плаваючою крапкою. Мантиса та порядок числа. Нормалізованаформа представлення числа.
Форма з плаваючою крапкою
Для того, щоб збільшитидіапазон чисел, використовують другу форму запису чисел — з плаваючою комою. Будь-якечисло в системі числення з основою Q можна записати так:
a=A*Qp.
A називаютьмантисою числа, а P — порядком.
14 Наприклад, в десятковій системі числення число 3,14представимо у вигляді
3,14 = 0,314*101.
Тут мантиса дорівнює0,314, а порядок 1. Очевидно, таке представлення далеко не однозначне. Число 3,14записати так:
3,14=3,14*100= 31,4*10-1 = 0,0314*102 =...
Порядок числавизначає положення коми в запису мантиси. При коректуванні порядку відповіднимчином змінюється і положення коми — кома ніби ”плаває". Звідси і назваметоду представлення чисел. З плаваючою комою число, як ми тільки що бачили,представляється неоднозначно. Одне з цих представлень називають нормалізованим.В цьому випадку мантиса повинна задовільняти вимозі 1/10
3,14=0,314*101.
Запишемо кількачисел в двійковій системі числення в нормалізованій формі:
(7) 10 =(111) 2 = 111*20= 111*100= 0,111*23 =0,111*1011
(-9,5) 10 =(-1001,1) 2 = — 0,10011*24 = — 0,10011*10100.
Нехай дляпредставлення чисел з плаваючою комою в нас відведено 24 розряди. Нехай одинрозряд відведено для знаку числа, а другий для знаку порядку:
0 1 2 3 4 5 6 7 8 9 10 11 23 1 1 1 1 1 1 1
Знак числа| | ПорядокМантиса
Додатнє число,максимальне з можливих в пам’яті ЕОМ:
0 1 2 3 4 5 6 7 8 9 10 11 23 1 1 1 1 1 1 1 1 1 1 1
Знак числа| | ПорядокМантиса Знак порядку|
Мінімальне замодулем, відмінне від нуля і нормалізоване число
а= (0,1*10-1111111)2 =1/2*2-127 = 2-128:
0 1 2 3 4 5 6 7 8 9 10 11 23 1 1 1 1 1 1 1 1 1
Знак числа| | ПорядокМантиса Знак порядку|
Відмітимо, щонайменше за модулем число, не рівне нулю і не нормалізоване, яке можнапредставити в комірці:
а= (1/2) +15*2-127 = 2-142.
В цьому випадкумантиса
А= (0, 000...01) 2= 2-15, порядок Р = — (1111111) 2 = — (127) 10.Прямий, зворотній та доповнюючий кодичисел
В ЕОМ доцільнопредставляти знаки чисел з допомогою тих же символів через, через якізаписується саме число. Для цього виділяється додатковий розряд, який називаютьзнаковим і розташовують зліва від старшого розряду числа. Будемо позначатизнакові розрядні числа />як /> і відділяти їх крапкамивід цілої частини числа і комами від дробової.
Для правильностівиконання арифметичних операцій над числами, знаки яких закодовані числами,використовують спеціальні способи представлення чисел: прямий, зворотній ідодатковий.
Прямий кодвикористовується для вводу-виводу інформації і в запам’ятовуючих пристроях.
Додавання чисел впрямому коді (з одинаковими знаками) не викликає труднощів. Однак додаваннячисел з різними знаками в прямих кодах незручно, так як повинно бути спеціальнеобладнання для віднімання чисел і визначення знаку різниці.
Операціюалгебраїчного додавання чисел можна звести до операцій додавання привикористанні зворотніх і додаткових кодів.
Представленнядодатнього числа в зворотньому коді співпадавє з його прямим кодом. Дляотримання зворотнього коду від’ємного числа в двійковій системі необхідно взнаковому розряді записати 1, а в інших розрядах одиниці замінити нулями, анулі одиницями. Аналогічну заміну роблять при перетворенні зворотнього кодувід’ємного числа в прямий. На відміну від прямого коду, в зворотньому не можнавідкидати нулі після знакового розряду в цілій частині і нулі в кінці дробовоїчастини від’ємного числа.
Представленнядодатнього числа в доповнюючому коді співпадавє з його прямим кодом. Правилоформування додатнього коду від’ємного числа формулюється так: отриматизворотній код числа і додати 1 в молодший розряд числа. Перетвореннядоповнюючого коду від’ємного числа здійснюється або зворотнім шляхом (відняти 1і перетворити в зворотній код) або утворити доповнюючий код до доповнюючого. Нуль,на відміну від прямого і зворотнього кодів, в доповнюючому коді має єдинепредставлення
Байт — вісімпослідовно розміщених бітів, пронумерованих від 0 до 7, при цьому біт 0 є самиммолодшим значущим бітом.
Слово — послідовність з двох байтів, які мають послідовну адресу. Розмір слова 16 біт; бітив слові нумеруються від 0 до 15. Байт який містить нульовий біт, називаєтьсямолодшим байтом, а байт, який містить 15-й біт називають старшим байтом. МікропроцессориIntel мають важливу особливіть — молодший байт завжди зберігається за молодшоюадресою. Адресою слова рахується адреса молодшого байта. Адреса старшого байтаможе бути використана для доступа до старшої половини слова.
Подвійне слово — послідовність з чотирьох байтів (32 біта), які мають послідовну адресу. Нумераціяцих бітів проводиться від 0 до 31. Слово, яке містить нульовий біт називаєтьсямолодшим словом, а слово яке містить 31-й біт старшим словом. Молодше словозберігається за меншою адресою. Адресою подвійного слова рахується адресамолодшого слова. Адреса старшого слова може бути використана для доступа достаршої частини подвійного слова. .
Чотирьохкратнеслово — послідовність з восьми байт (64 біта). які мають послідовну адресу. Номераціяцих бітів проводиться від 0 до 63. Слово яке містить нульовий біт називаєтьсямолодшим подвійним словом словом, а слово яке містить 63-й біт старшимподвійним словом. Молодше подвійне слово зберігається за молодшою адресою. Адресоюподвійного слова рахується адреса молодшого слова. Адреса старшого подвійногослова може бути використана для доступа до старшої половини чотирьохкратногослова.Поняття про булеві функції
Ф-ція f, яказалежить від n змінних x1,x2,…,xn називаєтьсябулевою, або переключаючою, якщо ф-ція f і любий з її аргументів xi,i/>/> приймаютьзначення тільки змножини {0,1}. Аргументи булевої ф-ції також називаютьсябулевими.
Довільна булеваф-ція задається одним із трьох способів: матричним (табличним), геометричним іаналітичним.
При матричномуспособі булева ф-ція f (x1, x2, …, xn) задаєтьсятаблицею істинності (табл.1 та 2),
В лівій частиніякої представлені всі можливі двійкові набори довжини n, а в правій вказуєтьсязначення ф-ції на цих наборах.
Під двійковимнабором />= >, />{0,1} розуміють сукупністьзначень аргументів х1, х2,…, хn булевої ф-ціїf. Двійковий набір має довжину n, якщо він представлений n цифрами із множини{0,1}. В табл.1 та 4 перечислені всі двійкові набори відповідної довжини 3 і 4.
54 Іноді двійкові набори в таблиці істиності булевої ф-ціїзручно представляти номерами наборів. Запишемо аргументи x1,x2,…xnв порядку зростання їх індексів. Тоді любий двійковий набір />=>, />{0,1} можна розглядати якціле двійкове число N: N=/>2n-1+/>2n-2+…+/>, яке називають номеромнабору />. Наприклад, двійковінабори 0101 і 1000 мають номера 5 і 8 відповідно. Очевидно будь-яка булеваф-ція може бути задана таблицею істинності, в якій двійкові набори заміненісвоїми номерами (табл.2).
Булеві ф-ції,залежать від великого числа змінних, задавати таблицею істиності незручно, всилу її громіздкості. Наприклад таблиця істинності булевої функції 8 зміннихбуде містити 28=256 рядків. Тому для задання ф-ції багатьох зміннихзручно використати модифікацію таблиці істинності.
Розглянемо спосібпобудови такої таблиці істинності для ф-ції n змінних. Множина із n зміннихф-ції розбивається на дві підмножини: x1, x2, …,xj-1і хj, xj+1,…, xn. Змінні x1, x2,…,xj-1 відмічають рядки таблиці істинності, задаваючи в кожномурядку значення відповідного двійкового набору довжини j-1. Змінними хj,xj+1,…, xn відмічають її стовбці, задаваючи в кожномустовбці значення відповідного двійкового набору довжини n-j+1. Значення функціїзаписуються в клітинці на перетині відповідного рядка і стовбця (табл 3).
При геометричномуспособі булева ф-ція f (x1, x2, …, xn) задаєтьсяз допомогою n-мірного куба. В геометричному смислі кожний двійковий набір />=>, />{0,1} є n-мірний вектор,визначаючий точку n-мірного прстору. Виходячи з цього, вся множина наборів, наяких визначена ф-ція n змінних, представляється вершинами n-мірного куба. Відмічаючиточками вершини куба, в яких функція приймає одиничне значення (або нульове),одержимо геометричне представлення функції. Наприклад, булева функція, заданатабл.1, геометрично представляється 3-мірним кубом
При аналітичномуспособі булева функція задається формулами, тобто аналітичними виразами,побудованими на основі операцій булевої алгебри. Аналітичний спосіб заданнябулевих функцій займає особливе місце в проектуванні цифрових машин. Фактично,всі перетворення над булевими ф-ціями, необхідні для побудови цифрових машин,ведуться на аналітичному рівні.
Розглянемо областівизначення булевоі ф-ції. Як уже відмічалось, між двійковими наборами ідвійковими числами існує взаємнооднозначна відповідність. Отже, існує 2nрізних наборів двійкових змінних.
Таким чином,областю визначення булевої ф-ції n змінних при матричному способі заданняявляється множина всіх можливих двійкових довжин n наборів, а при геометричномуспособі задання множина всіх вершин n-мірного одиничного куба.
Булеву ф-цію,визначену на всіх своїх наборах, називають повністю визначеною. Булеву ф-цію nзмінних називають неповністю визначеною, або частинною, якщо вона визначена нена всіх двійкових наборах довжини n. Неповністю визначена булева ф-ція непопадає під визначення, дане на початку глави, але при довільному довизначенні(на всіх наборах, на яких вона не визначена) ця невідповідність знімається.
Існує не більше як2n різних булевих функцій n змінних. До цього висновку легко прийти,користуючись простими комбінаторними міркуваннями, і згадавши, що на кожному із2n наборів функції можуть приймати два значення.
Розглянемонайбільш використовувані булеви ф-ції однієї і двох змінних. Ф-ції однієїзмінної представлені таблиці 5, де
f0(x) =0- тотожній нуль (константа 0);
f1 (x) =x- тотожна ф-ція;
f2 (x) =/> - заперечення x (інверсія);
f3 (x) =1- тотожна одиниця (константа 1).
Ф-ції двох зміннихпредставлені в табл.6.
Найбільш частовикористовуються такі:
f0(x1,x2)=0 — тотожній нуль (константа 0);
f1 (x1,x2)=x1*x2 — кон’юнкція. Замість знака “*” інколивикористовують знак & або />. Цюф-цію часто називають логічним перетворенням або логічним множенням;
f3 (x1,x2)=x1 — повторення х1;
f5 (x1,x2)=x2 — повторення х2;
f6 (x1,x2)=x1/>х2 -додаванняпо модулю, або сума mod 2;
f7 (x1,x2)=x1/>x2-диз’юнкція(логічне або);
56 f8 (x1,x2) =x1/>х2 — функціяВебба (стрілка Пірса);
f9 (x1,x2)=x1~х2 — еквівалентність;
f13 (x1,x2)=x1/>х2 — імплікація;
f14 (x1,x2)=x1/x2 — штрих Шеффера;
f15 (x1,x2)=1 — тотожна одиниця (константа 1);
Розглянемонайбільш використовувані булеви ф-ції однієї і двох змінних. Ф-ції однієїзмінної представлені таблиці 5, де
f0(x) =0- тотожній нуль (константа 0);
f1 (x) =x- тотожна ф-ція;
f2 (x) =/> - заперечення x (інверсія);
f3 (x) =1- тотожна одиниця (константа 1).
Ф-ції двох зміннихпредставлені в табл.6.
Найбільш частовикористовуються такі:
f0(x1,x2)=0 — тотожній нуль (константа 0);
f1 (x1,x2)=x1*x2 — кон’юнкція. Замість знака “*” інколивикористовують знак & або />. Цюф-цію часто називають логічним перетворенням або логічним множенням;
f3 (x1,x2)=x1 — повторення х1;
f5 (x1,x2)=x2 — повторення х2;
f6 (x1,x2)=x1/>х2 -додаванняпо модулю, або сума mod 2;
f7 (x1,x2)=x1/>x2-диз’юнкція(логічне або);
56 f8 (x1,x2) =x1/>х2 — функціяВебба (стрілка Пірса);
f9 (x1,x2)=x1~х2 — еквівалентність;
f13 (x1,x2)=x1/>х2 — імплікація;
f14 (x1,x2)=x1/x2 — штрих Шеффера;
f15 (x1,x2)=1 — тотожна одиниця (константа 1);
Розглянутіпростіші булеві ф-ції дозволяють будувати нові булеви ф-ції з допомогоюузагальненої операції, що називається операцією суперпозиції. Фактично операціясуперпозиції заключається в тому, що існує підстановка замість аргументів іншихбулевих функцій (в деякій мірі аргументів).
Зауважимо, щосуперпозиція функцій одного аргументу породжує функції одного аргументу. Суперпозиціяф-цій двох аргументів дає можливість будувати функції будь-якої кількостіаргументів.
Суперпозиціябулевих ф-цій представляється у виді логічних формул. Однак слід відмітити:
одна і та жфункція може бути представлена різними формулами;
кожній формулівідповідає своя суперпозиція і своя своя схема з’єднання елементів;
між формуламипредставлення булевих ф-цій і схемами, які їх реалізують, існуєвзаємнооднозначна відповідність.
Очевидно, що середсхем, які реалізують дану функцію є найбільш проста. Пошук логічної формули, щовідповідає цій схемі, предствляє великий практичний інтерес, а перетворенняформул булевих функцій грунтується на використанні співвідношень булевоїалгебри.
Для булевоїалгебри визначена одна одномісна (унарна) операція, дві двохмісні (бінарні) операціїкон’юнкції і диз’юнкції (позначаються відповідно “*", “/>”).
В цій алгебрісправедливі три аксіоми:
закон комутативності- x/>y=y/>x, x*y=y*x;
57 закон асоціативності — (x/>y)/>z=x/> (y/>z), (x*y) *z=x*(y*z);
закондистрибутивності — x* (y/>z) = x*y/>x*z, x/>y*z= (x/>y) * (x/>z);
Перетворенняформул булевих функцій використанням тільки аксіом булевої алгебрималоефективне. Для спрощення формул використовують цілий ряд співвідношень. Приведемодеякі з них.
/>= />*/>, />*/>=/>/>/> (Теореми де Моргана)(1)
x/>x*y=x, x*(x/>y) =x; (2)
x/>x=x, x*x=x, />=x; (3)
x/>/>y=x/>y; (4)
x/>/>=1,x*/>=0; (5)
x/>1=1; x*0=0; (6)
xy/>x/>=x, (x/>y) (x/>/>) =x; (7)
В ряді випадків,перетворення над формулами булевих функцій зручно виконувати в алгебріЖегалкіна. Алгебра Жегалкіна включає дві двохмісні операції: кон’юнкцію ідодавання за модулем 2 (*,/>), атакож константу 1. Тут мають місце ті ж закони:
x/>y=y/>x, x*y=y*x
x/> (y/>z) = (x/>y) />z, x* (y*z) = (x*y) *z
x* (y/>z) =x*y/>x*z
Для спрощенняформул можуть бути використані такі співвідношення:
x/>0=x; x*1=x; x*0=0; x/>x=0; x*x=x.
Із комутативностіі асоціативності слідує, що диз’юнкція кількох змінних може виконуватисяпослідовно, причому порядок взяття дизьюнкції не впливає на результат. Тобто,диз’юнкція сукупності змінних може бути виражена співвідношенням
x1/>x2/>…/>xn=/>xi
Аналогічно длякон’юнкції
x1*x2*…*xn=/>xi
і суми по модулю 2
x1/>x2/>…/>xn=/>
Теореми де Морганадля кількох змінних мають вигляд:
/>= />
/>=/>Аналітичне представлення булевихфункцій
Вище згадувалосяпро існування аналітичних форм представлення булевих ф-цій. Тут розглянемо універсальні(канонічні) форми представлення, які дають можливість отримати аналітичну формубезпосередньо по таблиці істиності для довільної булевої ф-ції. Ця форма вдальшому може бути спрощена. Найбільш широке поширення отримала досконаланормальна форма (ДНФ). Перед тим як перейти до вивчення, приведемо визначенняконституєнти одиниці — поняття, яким будемо широко користуватися дальше.
Визначення: Конституєнтоюодиниці називається функція f (x1, x2, …, xn),яка приймає значення 1 тільки на одному наборі.
Якщо згадати, щодиз’юнкція рівна 1, коли хоча б одна з змінних приймає значення 1, то можналегко виразити, будь-яку булеву функцію як диз’юнкцію конституєнт одиниці, яківідповідають тим наборам, на яких функція рівна 1. В більш загальному виглядіце можна записати таким чином:
f (x1,x2, …, xn) =/> f (σ1,σ2, …, σn) * x1σ1,x2σ2, …, xnσn,
де σi= 0,1 і
xiσi = />
Ця форма і єдосконала диз’юнктивна форма (ДДНФ). Замітимо, що набори, де функція f приймаєзначення 1, часто називають одиничними, всі решта — нульовими наборами. Виписуватив ДДНФ є зміст тільки конституєнти одиниці, відповідні одиничним наборам.
Приклад: ВипишемоДДНФ для ф-цій, заданих таблицею істиності (табл.1).
Таблиця 1
x1 x2 x3
f1
f2
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
1
1
1
1
1
1
1
1
/>/>
Ф-ція f1нам відома як сума за модулем 2 трьох змінних х1/>х2/>х3. Ф-ціяf2 називається мажорантною (вона приймає значення, яке приймаєбільшість змінних) і позначається знаком М (х1, х2, х3)
Друга відома форманосить назву “досконалої кон’юктивної нормальної форми" (ДКНФ). Вонабудується аналогічно ДДНФ.
Визначення: Конституєнтоюнуля називається функція, яка приймає значення 0 на єдиному наборі.
Конституєнта нулязаписується у вигляді елементарної диз’юнкції всіх змінних. Кожному наборувідповідає своя конституєнта 0.
Приклад Длярозглянутих вище ф-цій х1/>х2/>х3 і М (х1,х2, х3) (табл.7) побудуємо ДКНФ:
/>;
/>.
Легко побачити, щов ДДНФ можна замінити операцію диз’юнкції операцією суми за модулем 2, причомурівність збережеться. Ця форма називається “досконалою поліноміальноюнормальною формою” (ДПНФ). Для нашого прикладу
/>
60 />
Якщо в ДПНФзамінити всі змінні з запереченням у відповідності з співвідношенням />=1/>х, то отримаєтьсяканонічний поліном Жегалкіна вигляду
f (x1,x2, …, xn)
=a0/>a1x1/>a2x2/>…/>anxn/>a12x1x2/>a13x13/>…/>a12…nx1x2…xn,
де аi/>{0,1}.
Приклад: Для тихже функцій f1 і f2 знайдемо канонічний поліном Жегалкіна:
f1= (x1/>1) (x2/>1) x3/> (x1/>1) x2 (x3/>1) />x1 (x2/>1) (x3/>1) />x1x2x3=x1x2x3/>x3/>x1x3/>x2x3/>/>x1x2x3/>x1x2/>x2x3/>x1x2x3/>x1x2/>x2x3/>x2/>x1x2x3/>x1x2/>x1x3/>x1/>x1x2x3=x1/>x2/>x3
Аналогічно для f2=x1x2/>x2x3/>x1x3.
В булевій алгебрішироко використовується розклад Шеннона- формула, яка дозволяє перейти відпредставлення функції від n-змінних до представлення функції від (n-1) — змінних:
f (x1,x2, …, xn) =x1f (1, x2, …, xn)/>/>f(0, x2, …, xn)
Співвідношеннялегко узагальнюється для будь-якої кількості змінних, якщо функції правоїчастини піддати такому ж розкладу по інших змінних. Наприклад:
f (x1,x2, …, xn) =x1 [x2f (1,1, x3,…, xn) /> />f (1,0, x3, …, xn)]/>/> [x2f(0,1, x3…xn) />/>f (0,0,x3,…xn)]=x1,x2f (1,1,x3,…xn) />x1/>f (1,0,x3,…,xn)/>/>x2f(0,1,x3,. .,xn) />/>f (0,0,x3,…,xn)
Відмітимо, що якщопровести такий же розклад по всіх змінних, получиться ДДНФ.Мінімізація булевих функцій
При проектуванніцифрових машин широко використовуються методи мінімізації булевих функцій, якідозволяють отримати рекомендації для побудови економічних схем цифрових машин. Загальназадача мінімізації булевих функцій формулюється так: знайти аналітичневираження булевої функції в формі, що містить мінімально можливе число букв. Слідвідмітити, що в загальній постановці дана задача поки що не розв’язана, аледостатньо добре досліджена в класі диз’юнктивно-кон’юктивних нормаьних форм.
61 Визначення: Елементарною кон’юнкцією називаєтьсякон’юнкція кінцевого числа різних між собою булевих змінних, кожна з яких можемати, або не мати заперечення.
Визначення: Диз’юнктивноюнормальною формою (ДНФ) називається диз’юнкція елементарних кон’юнкцій.
Визначення: Мінімальноюдиз’юнктивною нормальною формою булевої функції називається ДНФ, що міститьнайменше число букв.
Визначення: Булевафункція g (x1,x2,…,xn) називається імплікантоюбулевої функції f (x1,…,xn), якщо для будь-якого наборузмінних, на якому g=1, справедливе f=1.
Визначення: Імплікантаg булевої ф-ції f, що є елементарною кон’юнкцією, називається простою, якщоніяка частина імпліканти g не є імплікантою функції f.
Приведемо бездоведень два твердження, корисні при отриманні мінімальної ДНФ.
Дизьюнкціябудь-якої кількості імплікант булевої ф-ції f також є імплікантою цієї функції.
Будь-яка булевафункція f еквівалентна диз’юнкції всіх своїх простих імплікант. Така формапредставлення булевої ф-ції називається скороченою ДНФ.
Отримання скороченихДНФ є першим етапом відшукання мінімальних форм булевих функцій. В скороченуДНФ входять всі прості імпліканти булевої функції. Іноді з скороченої ДНФ можназабрати одну, або декілька простих імплікант, не порушуючи еквівалентностіпочаткової функції. Такі прості імпліканти називаються лишніми. Виключеннялишніх простих імплікант з скорочених ДНФ — другий етап мінімізації.
Визначення: СкороченаДНФ булевої ф-ції називається тупіковою, якщо в ній відсутні лишні простіімпліканти.
Виключення лишніхпростих імплікант в скорочених ДНФ булевої функції не є однозначним поцесом,тобто булева функція може мати декілька тупікових ДНФ.
Твердження. ТупіковіДНФ булевої функції f, що містять мінімальну кількість букв, являютьсямінімальними. Мінімальних ДНФ також може бути декілька.
Розглянемодекілька методів мінімізації. Всі вони практично відрізняються тільки напершому етапі — етапі отримання скорочених ДНФ. Слід відмітити, що, на жаль,пошук мінімальної ДНФ завжди зв’язаний з деяким перебором рішень. Існують методизменшення цього перебору, проте він завжди залишається.
Метод квайнаоснований на використанні двох основних співвідношень:
Співвідношеннясклеювання:
Ax/>A/>=A,
де А — любеелементарне походження.
Співвідношенняпоглинання:
А/>/>А=А,/>/>{x,/>}.
Справедливістьобидвох співвідношень легко перевіряється. Суть методу в послідовному виконаннівсіх можливих склеювань і потім всіх поглинань, що приводять до скороченої ДНФ.
Приклад. Нехай єбулева ф-ція, задана таблицею істиності (табл.1).
Таблиця 1
x1 x2 x3 x4 F
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
0 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1
1
1
1
1
1
1
1
Її ДДНФ має вигляд
f=/>/>/>/>/>/>/>/>/>/>/>
Для зручностіпомітимо кожну конституєнту одиниці з ДДНФ ф-ції f яким-небудь десятковимномером (довільно). Виконаємо склеювання. Конституєнта 1 склеюється тільки зконституєнтою2 (по змінній х3) і з конституєнтою 3 (по змінній х2),конституєнта 2 з конституєнтою 4. В результаті отримуємо
1-2: />; 3-4: />;
1-3: />; 4-6: />;
2-4: />; 5-6: />.
Далі проводимосклеювання отриманих елементарних перетворень. Склеюються тільки тіперетворення, які містять одинакові змінні. Має місце два випадки склеювання:
/>/> />=/>/>/>/>/>;
/>/>/>=/>/>/>/>/>,
з появою одного ітого ж />.
Подальшісклеювання неможливі. Провівши поглинання, отримаємо скорочену ДНФ
/>/>/>/>/>.
Переходимо донаступного етапу. Для отримання мінімальної ДНФ необхідно забрати з скороченоїДНФ всі лишні прості імпліканти. Це робиться за допомогою спеціальноїімплікантної матриці Квайна. Рядки такої матриці відмічаються простимиімплікантами булевої ф-ції, тобто членами скороченої ДНФ, а стовбці — конституєнтами одиниці, тобто членами ДДНФ булевої ф-ції. Приклад (продовження).Імплікантна маириця має вигляд (табл.2)
Таблиця 2. Прості імпліканти Конституенти одиниці
/>
/>
/>
/>
/>
/>
/>
/>/>/>
/>
/>
x2 x3 x4
/>
/>
x1 x2 x3
/>
Відповідна кліткаімплікантної матриці на перетині рядка (з розглядуваною простою імплікантою) істовбця (з конституєнт одиниці) відмічається хрестиком (табл.2). Мінімальні ДНФбудуються по імплікантній матриці наступним чином:
1. Шукаютьсястовбці матриці, які мають тільки один хрестик. Відповідні цим хрестикам простіімпліканти називаються базисами і складають так зване ядро булевої ф-ції. Ядрообов’язково входить в мінімальну ДНФ.
2. Розглядаютьсярізні варіанти вибору сукупності простих імплікант, які накриють хрестикамирешту стовбців матриці, і вибираються варіанти з мінімальним сумарним числомбукв в такій сукупності імплікант.
Ядром нашої ф-ціїє імпліканти x1x2x3. Імпліканта x2x3x4-лишня. Тому ф-ція має єдину тупікову і мінімальну ДНФ:
/>Метод квайна-мак-класкі
Метод представляєсобою формалізований на етапі знаходження простих імплікант метод Квайна. Формалізаціяпроводиться таким чином:
Всі конституантиодиниці з ДДНФ булевої функцію f записуються їх двійковими номерами.
Всі номерирозбиваються на групи, що не перетинаються. Ознака утворення і-ї групи: іодиниць в кожному двійковому номері конституєнти одиниці.
Склеюванняпроводять тільки між номерами сусідніх груп. Склеювані номери відмічаєтьсябудь-яким знаком (закреслюванням).
Склеюванняпроводять всеможливі, як і в методі Квайна.
Невідмічені післясклеювання номера є простими імплікантами.
Знаходженнямінімальних ДНФ дальше проводяться на імплікантній матриці, як і в методіКвайна.
Метод дозволяєшвидко отримати мінімальні ДНФ булевої функції f невеликого числа змінних. Воснові методу лежить задання булевих функцій діаграмами деякого спеціальноговиду, які дістали назву діаграм Вейча. Для булевої ф-ції двох змінних діаграмаВейча має вигляд (табл.3) Кожна клітка діаграми відповідає набору зміннихбулевої функції в її таблиці істиності. В клітці діаграми ставиться одиниця,якщо булева функція приймає одиничне значення на відповідному наборі. Нульовізначення булевої функції в діаграмі не ставляться. Для булевої функції трьохзмінних діаграма Вейча має такий вигляд (табл.4)
/>
Додаванням до неїще такої ж таблиці ми отримаємо діаграму для функції 4-х змінних (табл.5). Такимже чином можна отримати діаграму 5-ти змінних і т.д.
Таблиця 5/> /> /> /> /> /> />
/> />
/> />
/> />1100 1101 1001 1000
/> />1110 1111 1011 1010
/> 0110 0111 0011 0010
/> />0100 0101 0001 0000
70
69 Для приведених діаграм характерне наступне:
Кожній клітцідіаграми відповідає свій набір.
Сусідні наборирозміщені поряд в рядку або в стовбці.
Сусідніми набораминазивають набори, які відрізняються однією компонентою.
Ще одне важливезауваження: стовбці, розміщені по краях діаграми, також вважають сусідніми.
Загальне правилосклеювання на діаграмі Вейча можна сформолювати таким чином: склеюваннюпідлягають прямокутні конфігурації, заповнені одиницями і які містять числокліток, що являються степінню 2. Отримане повне елементарне перетвореннявизначається як перетворення змінних, які не змінюють свого значення на всіхсклеюваних наборах. Число m змінних, які залишились в елементарномуперетворенні визначається легко:
m = n — log2M,
де n — числозмінних функції; М — число склеюваних наборів. Метод широко використовується напрактиці, завдяки простоті і зручності.
Мінімізаціябулевої ф-ції полягає в знаходженні мінімального накриття всіх одиниць діаграмиВейча блоками з одиниць (вказаної конфігурації), розміщених в сусідніх кліткахдіаграми. При цьому завжди вважають, що лівий край діаграми Вейча 4-х зміннихприлягає до її правого краю, а верхній край діаграми — до її нижнього краю. Післяотримання максимального покриття всіх одиниць діаграми Вейча, мінімальна ДНФбулевої функції записується як диз’юнкція елементарних кон’юнкцій, яківідповідають виділеним блокам одиниць в діаграмі.
Приклад. Булевафункція f має наступну ДДНФ:
/>
Знайти мінімальнуДНФ з допомогою діаграми Вейча. Діаграма Вейча, що відповідає функції f,представлена в табл.18. Мінімальне накриття всіх одиниць діаграми можливетільки блокамипо дві одиниці. Кожному такому блоку відповідає своя кон’юнкція,як показано в табл.22. Отже, мінімальна ДНФ ф-ції має вигляд:
/>.
Таблиця 18
/>
/>Висновок
Отже, ключовимиматематичними поняттями теорії цифрових автоматів являється т. зв. булеваалгебра та її під-дисципліни, які і визначають її математичний базис.
Література
1. А.Я. Савельев. Арифметические и логические основы цифровых автоматов. М.:Высшая школа. 1999.
2. А.Я. Савельев. Прикладная теория цифровых автоматов. М.: Высшая школа.2007.
3. Е.Н. Вавилов, Г.П. Портной. Синтез схем электронных цифровых машин. М.:Советское радио. 2003.
4. Г.Н. Соловьев. Арифметические устройства ЭВМ. М.: Энергия. 2008.