Аналіз теорії цифрових автоматів

Аналіз теорії цифрових автоматів

(курсова робота)

Содержание

Двійкова арифметика

Системи числення з довільною основою

³³Мшан системи числення

Форма з фіксованою крапкою

Форма з плаваючою крапкою

Прямий, зворотній та доповнюючий коди чисел

Поняття про булеві функції

Аналітичне представлення булевих функцій

Мінімізація булевих функцій

Метод квайна-мак-класкі

Висновок

Висновок

Література

Теорія цифрових автоматів закладає теоретичні основи роботи комп’ютерної техніки. У даній курсові роботі проводиться аналіз математичного підгрунтя даної дисципліни.

Двійкова система числення

Двійкова позиційна система числення

Позиційна система числення з основою 2 називається двійковою. Для запису чисел в двійковій системі використовуються лише дві цифри: 0 і 1. Число два, тобто основа системи подається як 10₂.

Зручність системи - в її надзвичайній простоті.

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

Переведення числа з двійкової системи числення в десяткову та з десяткової у двійкову.

Нам уже відомо, що число N, записане в системі числення з основою p як (±a_ka_k-1…a₁a₀) _p, рівне N=a_k∙p^k+a_k-1∙p^k-1+…+a₁∙p+a₀

Тому:

1001₂=1∙2³+0∙2²+0∙2¹+1∙2⁰=8+0+0+1=9₁₀

100001₂=1∙2⁵+0∙2⁴+0∙2³+0∙2²+0∙2¹+1∙2⁰=32+0+0+0+0+1=33₁₀

Щоб перевести число із десяткової системи числення у двійкову, треба послідовно ділити десяткове число і його десяткові частки на основу двійкової системи, тобто на число 2. Ділення продовжується до тих пір, поки одержана частка не буде менша основи нової системи числення, тобто 2.

1 |40|2_

0 |20|2_

0 |10|2

0|5|2

1|2|2

0|1

Отже число 81₁₀ в двійковій системі: 1010001₂

Переведемо число 100:

100|2_

0 |50|2_

0 |25|2_

1 |12|2

0|6|2

1|3|2

1|1

Отже, (100) ₁₀= (1100100) ₂

З переводом чисел з десяткової системи одиниць у двійкову приходиться постійно мати справу при роботі на ЕОМ.

Окрему позицію в записі числа називають розрядом. Число розрядів - розрядність (довжина). Номер позиції - номер розряду. Довжина числа - це к-сть позцій (розрядів) в записі числа. В технічному розумінні це довжина розрядної сітки.

Чим менша основа системи, тим більша довжина числа. Якщо довжина розрядної сітки n, то: A_{q max}=q^n-1; A_{q min}= - (qⁿ-1);

Діапазон представлення чисел в заданій системі:

A_{q max} ≥ДП≥ A_{q min.}

Двійкова арифметика

Арифметичні дії в двійковій системі (двійковій арифметиці) виконуються за звичайними для позиційних систем правилами (алгоритмами), які нам відомі з десяткової арифметики, але при цьому, звичайно, використовуються таблиці додавання і множення двійкової системи.

Таблиця додавання

0+0=0

0+1=1

1+0=1

1+1=10₂

(додавання нуля не міняє числа, а один плюс один буде два).

Таблиця множення

0∙0=0

0∙1=0

1∙0=0

1∙1=1

(число, помножене на нуль, є нуль; множення на один не міняє числа).

Додавання. Додавання багатозначних чисел відбувається так само, як і в десятковій системі, тобто порозрядно, починаючи з молодшого.

101101₂ - 1 доданок

+ 10100₂ - 2 доданок

1000001₂ - сума

Перевіримо правильність наших обчислень:

101101₂=1∙2⁵+0∙2⁴+1∙2³+1∙2²+0∙2¹+1∙2⁰=32+0+8+4+0+1=45₁₀

10100₂=1∙2⁴+0∙2³+1∙2²+0∙2¹+0∙2⁰=16+0+4+0+0=20₁₀

45₁₀+20₁₀=65₁₀

1000001₂=1∙2⁶+0∙2⁵+0∙2⁴+0∙2³+0∙2²+0∙2¹+1∙2⁰=64+0+0+0+0+0+1=65₁₀

Віднімання

0-0=0

1-0=1

1-1=0

10₂-1=1

Знайдемо: 111010111₂-1100001₂

111010111₂

- 1100001₂

101110110₂

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

Множення

11101₂∙1101₂

11101_{2 -} множник

1101₂ - множник

11101 - множене

+11101 - множене, зсунуте на 2 розряди вліво

11101 - множене, зсунуте на 3 розряди вліво

101111001₂ - добуток

Перевірка:

11101₂=1∙2⁴+1∙2³+1∙2²+0∙2¹+1∙2⁰=16+8+4+1=29₁₀

1101₂=13₁₀; 29∙13=377₁₀

101111001₂=1∙2⁸+0∙2⁷+1∙2⁶+1∙2⁵+1∙2⁴+1∙2³+0∙2²+0∙2¹+1∙2⁰=256+0+64+32+16+8++0+1=377_10.

Отже, в двійковій арифметиці при множенні не потрібна таблиця множення. Не треба знаходити добутки першого множника на значення послідовних розрядів другого множника, так як значення цих розрядів або 1 або 0.

Достатньо записати значення першого множника одне під одним із зсувом на один розряд; у випадку рівності якого-небудь розряду другого множника нулю, його зсувають на два розряди.

1101111₂

101101₂

1101111

1101111

1101111

1101111 __

1001110000011₂

Системи числення з довільною основою

Ми розглянули алгоритм переводу чисел з двiйково¿ системи числення в десяткову i навпаки - з десятково¿ в двiйкову. Алгоритми залишаться цiлком аналогiчними, якщо замiсть двiйково¿ системи числення взяти будь-яку iншу.

Нехай, наприклад, деяке число записане в вiciмковiй системi числення. Це значить, що цифри в записі цього числа º коºфiцiєнти в його розкладi по степенях числа 8:

(a_na_n-1... a₁a₀, a_-1a_-2. .) ₈ =a_n*8ⁿ+a_n-1*8^n-1+... +a₁*8+a₀+a_-1*8^-1+...

Для того,щоб отримати зображення цього числа в десятковiй системi числення, достатньо виконати, користуючись десятковою арифметикою, всi операцi¿ в правiй частинi цього виразу. Приклад. Перевести число (276,54) ₈ з вiсiмково¿ системи числення в десяткову:

(276,54) ₈=2*8²+7*8¹+6*8⁰+5*8^-1+4*8^-2=128+56+6+5/8+4/64= (190,6875) ₁₀.

Нехай тепер потр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) ₁₀ з десятково¿ системи числення в вiсiмкову.

Переведемо цiлу частину:

190 | 8

16 | 23 | 8

30 16 | 2 | 8 (190)₁₀=(276)₈

6 7 2 | 0

Переведемо дробову частину:

0 | 6875 (0,6875)₁₀=(0,54)₈

5 | 5000

4 | 0

тобто (190,6875)₁₀ =(276,54)₈.

Цей приклад разом з попереднiм iлюструº, як можна перевiряти правильнiсть переводу з однiє¿ системи числення в iншу зворотнiм переводом.

Виконання арифметичних дій в СЧ з основою р.

Змішані СЧ. Запис чисел в змішаних СЧ. Системи з кратними основами. Теорема для СЧ з кратними основами

М³шан³ системи числення

Існує простий спос³б запису десяткових чисел за допомогою дв³йкових цифр - представлення чисел в м³шан³й дв³йково-десятков³й систем³ числення. В н³й кожна цифра десяткового зображення числа записуºться в дв³йков³й систем³ числення.

Причому для того, щоб такий запис був однозначним, для представлення будь-якої десятково¿ цифри в³дводиться одна ³ та ж к³льк³сть дв³йкових розряд³в - чотири. Якщо десяткова цифра вимагаº для свого представлення менше значущих дв³йкових цифр, то попереду цих цифр дописуються нул³ (так щоб загальна к³льк³сть дв³йкових знак³в залишалась р³вною чотирьом). Наприклад, десяткове число 834,25 в дв³йково-десятков³й систем³ запишеться так:

(834,25) ₁₀ = (1000 0011 0100,0010 0101).

Кожна четв³рка (тетрада) двійкових цифр тут в³дпов³даº одн³й десятков³й цифр³:

(8)₁₀ = (1000)_2-10 (2)₁₀ = (0010)_2-10

(3)₁₀ = (0011)_2-10 (5)₁₀ = (0101)_2-10

(4)₁₀ = (0100)_2-10

Теорема. Якщо P = Qⁿ (P, Q, n - ц³л³ додатн³ числа), то запис любого числа в м³шан³й (Q - P) - й систем³ числення тотожньо сп³впадаº з записом цього ж числа в систем³ числення з основою Q (з точн³стю до нул³в на початку запису ц³ло¿ частини числа ³ на к³нц³ дробово¿).

Якщо P=8, Q=2, n=3, то 8=2³ ³, отже, зг³дно даної теореми запис будь-якого числа в дв³йково-в³с³мков³й систем³ сп³впадаº з записом того ж числа в дв³йков³й систем³. (Зауважимо, що за т³ºю ж теоремою записи будь-якого числа в дв³йков³й ³ дв³йково-ш³стнадцятков³й системах теж сп³впадуть). Переведемо, наприклад, все теж число (405) ₁₀ з десятково¿ системи числення в ш³стнадцяткову:

405|16

32 |25|16

85 9|1 |16

80 |0

5

Збираючи залишки в³д д³лення, отримаºмо (405) ₁₀ = (195) ₁₆.

Представимо тепер число (195) ₁₆ в дв³йково - ш³стнадцятковому запис³: (195) ₁₆ = (1 1001 0101) _2-6.

Видно, що записи числа в дв³йков³й ³ дв³йково-ш³стнадцятков³й системах вuявuлuсь однаковими. Ця властив³сть дв³йково-в³с³мково¿ системи числення дозволяº дуже просто переводити числа з дв³йково¿ системи в в³с³мкову (чи ш³стнадцяткову) ³ навпаки.

Справд³, будь-який дв³йковий запис розглядаºмо як дв³йково-в³с³мковий код деякого в³с³мкового числа, розбиваºмо його на тр³йки (тр³ади) дв³йкових цифр л³воруч ³ праворуч в³д коми. Кожн³й так³й тр³йц³ ставимо у в³дпов³дн³сть одну в³с³мкову цифру ³ отримаºмо число в в³с³мков³й систем³ числення.

В³зьмемо, наприклад, код:

(10 011 110,001 1)₂ = (236,14)₈ .

2 3 6 1 4

Тут, як ³ в дв³йково-десятковому записі, в ц³л³й частин³ в³дкинут³ крайн³ зл³ва нул³, а в дробов³й частин³ - крайн³ справа. Безумовно, треба ¿х враховувати як недостатн³ у в³дпов³дних тр³адах дв³йкових цифр. Зворотн³й перев³д чисел з в³с³мково¿ системи числення в дв³йкову також простий. Кожну цифру в³с³мкового числа записуºмо тр³йкою дв³йкових символ³в, тобто записуºмо його в дв³йково-в³с³мков³й систем³, а так як цей запис сп³впадаº з дв³йковим, то ми одержимо число в дв³йков³й систем³. Переведемо, наприклад, число (3514,72) ₈ з в³с³мково¿ системи в дв³йкову:

(3514,72)₈ = (11 101 001 100,111 01)₂ .

3 5 1 4 7 2

Зв³дси сл³дуº, що в³с³мкову систему числення можна використовувати для скороченого запису любого дв³йкового коду. При цьому використовується приблизно в дв³ч³ менше символ³в, якщо розбити ¿х на тр³йки цифр ³ кожну записати одн³ºю в³с³мковою цифрою. Так само запис будь-якого числа в ш³стнадцятков³й систем³ числення можна використовувати для скороченого запису дв³йкового коду. В цьому випадку кожному ш³стнадцятковому символу взаºмно однозначно в³дпов³даº наб³р з чотирьох дв³йкових цифр:

(0)₁₆ = (0000)₂ (8)₁₆ = (1000)₂

(1)₁₆ = (0001)₂ (9)₁₆ = (1001)₂

(2)₁₆ = (0010)₂ (а)₁₆ = (1010)₂ = (10)₁₀

(3)₁₆ = (0011)₂ (b)₁₆ = (1011)₂ = (11)₁₀

(4)₁₆ = (0100)₂ (c)₁₆ = (1100)₂ = (12)₁₀

(5)₁₆ = (0101)₂ (d)₁₆ = (1101)₂ = (13)₁₀

(6)₁₆ = (0110)₂ (e)₁₆ = (1110)₂ = (14)₁₀

(7)₁₆ = (0111)₂ (f)₁₆ = (1111)₂ = (15)₁₀ .

Так як записи числа в дв³йково-ш³стнадцятков³й ³ дв³йков³й системах за сформульованою вище теоремою сп³впадають, то, зам³нивши вс³ ш³стнадцятков³ цифри деякого числа на в³дпов³дн³ четв³рки дв³йкових цифр, отримаºмо таке ж число в дв³йков³й систем³ числення. При цьому запис числа буде використовувати приблизно в чотири раза менше цифр, н³ж в дв³йков³й систем³ числення. Наприклад, число (3c2e9) ₁₆ може бути представлене в дв³йков³й систем³ числення наступним чином: (11 1100 0010 1110 1001) ₂.

3 c 2 e 9

П³д кожною четв³ркою дв³йкових цифр ми записали в³дпов³дний³ ш³стнадцятковий символ. Дві форми комп’ютерного представлення числових даних. Їх переваги і недоліки.

Форма з фіксованою крапкою

В сучасних ЕОМ застосовуються два способу представлення чисел: з ф³ксованою крапкою ³ плаваючою крапкою.

В першому випадку м³сце коми, яка в³дд³ляº ц³лу частину числа в³д дробово¿, визначаºться на етап³ конструювання ЕОМ. Зразу ж вказуºться к³льк³сть розряд³в, як³ в³дводяться для зображення ц³ло¿ ³ дробово¿ частин. Причому кожному розряду ком³рки в³дпов³даº завжди один ³ той же розряд числа, що суттºво спрощуº виконання арифметичних д³й.

Нехай, наприклад, ком³рка пам’ят³ машини маº 24 дв³йкових розряда. Як ми знаºмо, в ком³рку можна записати будь-яке машинне слово, тобто дов³льний наб³р з нулів ³ одиниць. Якщо це слово - число, то в конструкц³¿ машини може бути передбачено його представлення в форм³ з ф³ксованою комою. Наприклад, воно може бути таким: крайн³й зл³ва розряд - знаковий, пот³м наступні 9 розряд³в в³дводяться п³д ц³лу частину ³, накінець, 14 розряд³в, як³ залишилися, п³д дробову частину числа, тобто кома тут завжди на одному ³ тому ж м³сц³ - п³сля десятого розряду машинного слова (з врахуванням знакового розряду). Тод³ найб³льше число, яке можна представити, буде: (111111111,11111111111111) _2.

Видно, що воно менше, н³ж 2⁹ = (512) ₁₀. А найменше за модулем в³дм³нне в³д нуля число дор³внюº

(000000000,00000000000001) ₂ = 2^-14.

Тобто, д³апазон чисел, як³ можна записати в ком³рку пам’т³ машини, тут такий:

2^-14 < |a| < 2⁹.

Форма з плаваючою крапкою.

Для того, щоб зб³льшити д³апазон чисел, використовують другу форму запису чисел - з плаваючою комою. Будь-яке число в систем³ числення з основою Q можна записати так:

a=A*Q^p.

A називають мантисою числа, а P - порядком.

Наприклад, в десятков³й систем³ числення число 3,14 представимо у вигляд³

3,14 = 0,314*10¹.

Тут мантиса дор³внюº 0,314, а порядок 1. Очевидно, таке представлення далеко не однозначне. Число 3,14 записати так:

3,14=3,14*10⁰ = 31,4*10^-1 = 0,0314*10² =...

Порядок числа визначаº положення коми в запису мантиси. При коректуванн³ порядку в³дпов³дним чином зм³нюºться ³ положення коми - кома ніби ”плаваº".

Зв³дси ³ назва методу представлення чисел. З плаваючою комою число, як ми т³льки що бачили, представляºться неоднозначно. Одне з цих представлень називають нормал³зованим.

В цьому випадку мантиса повинна задов³льняти вимоз³ 1/10 <|А|< 1 (мова йде про десяткову систему числення). Iншими словами, перша цифра мантиси п³сля коми повинна бути в³дм³нною в³д нуля.

9. Представлення довільного числа в формі з плаваючою крапкою. Мантиса та порядок числа. Нормалізована форма представлення числа.

Форма з плаваючою крапкою

Для того, щоб зб³льшити д³апазон чисел, використовують другу форму запису чисел - з плаваючою комою. Будь-яке число в систем³ числення з основою Q можна записати так:

a=A*Q^p.

A називають мантисою числа, а P - порядком. Наприклад, в десятков³й систем³ числення число 3,14 представимо у вигляд³

3,14 = 0,314*10¹.

Тут мантиса дор³внюº 0,314, а порядок 1. Очевидно, таке представлення далеко не однозначне. Число 3,14 записати так:

3,14=3,14*10⁰ = 31,4*10^-1 = 0,0314*10² =...

Порядок числа визначаº положення коми в запису мантиси. При коректуванн³ порядку в³дпов³дним чином зм³нюºться ³ положення коми - кома ніби ”плаваº". Зв³дси ³ назва методу представлення чисел. З плаваючою комою число, як ми т³льки що бачили, представляºться неоднозначно. Одне з цих представлень називають нормал³зованим. В цьому випадку мантиса повинна задов³льняти вимоз³ 1/10 <|А|< 1 (мова йде про десяткову систему числення). Iншими словами, перша цифра мантиси п³сля коми повинна бути в³дм³нною в³д нуля. В нашому приклад³ десяткове число а=3,14 в нормал³зован³й форм³ маº вигляд

3,14=0,314*10¹.

Запишемо кілька чисел в двійковій системі числення в нормалізованій формі:

(7) ₁₀ = (111) ₂ = 111*2⁰ = 111*10⁰ = 0,111*2³ = 0,111*10¹¹

(-9,5) ₁₀ = (-1001,1) ₂ = - 0,10011*2⁴ = - 0,10011*10¹⁰⁰.

Нехай для представлення чисел з плаваючою комою в нас відведено 24 розряди. Нехай один розряд відведено для знаку числа, а другий для знаку порядку:

0 1 2 3 4 5 6 7 8 9 10 11 23

0

1

1

0

1

0

1

1

1

0

1

0

Знак числа| | Порядок Мантиса

Додатнº число, максимальне з можливих в пам’ят³ ЕОМ:

0 1 2 3 4 5 6 7 8 9 10 11 23

0

0

1

1

1

1

1

1

1

1

1

1

1

Знак числа| | Порядок Мантиса Знак порядку|

М³н³мальне за модулем, в³дм³нне в³д нуля ³ нормал³зоване число

а= (0,1*10^-1111111) ₂ =1/2*2^-127 = 2^-128:

0 1 2 3 4 5 6 7 8 9 10 11 23

0

1

1

1

1

1

1

1

1

1

0

0

0

Знак числа| | Порядок Мантиса Знак порядку|

В³дм³тимо, що найменше за модулем число, не р³вне нулю ³ не нормал³зоване, яке можна представити в ком³рц³:

а= (1/2) ⁺¹⁵ *2^-127 = 2^-142.

В цьому випадку мантиса

А= (0, 000...01) ₂ = 2^-15, порядок Р = - (1111111) ₂ = - (127) _10.

Прямий, зворотній та доповнюючий коди чисел

В ЕОМ доцільно представляти знаки чисел з допомогою тих же символів через, через які записується саме число. Для цього виділяється додатковий розряд, який називають знаковим і розташовують зліва від старшого розряду числа. Будемо позначати знакові розрядні числа як і відділяти їх крапками від цілої частини числа і комами від дробової.

Для правильності виконання арифметичних операцій над числами, знаки яких закодовані числами, використовують спеціальні способи представлення чисел: прямий, зворотній і додатковий.

Прямий код використовується для вводу-виводу інформації і в запам’ятовуючих пристроях.

Додавання чисел в прямому коді (з одинаковими знаками) не викликає труднощів. Однак додавання чисел з різними знаками в прямих кодах незручно, так як повинно бути спеціальне обладнання для віднімання чисел і визначення знаку різниці.

Операцію алгебраїчного додавання чисел можна звести до операцій додавання при використанні зворотніх і додаткових кодів.

Представлення додатнього числа в зворотньому коді співпадавє з його прямим кодом. Для отримання зворотнього коду від’ємного числа в двійковій системі необхідно в знаковому розряді записати 1, а в інших розрядах одиниці замінити нулями, а нулі одиницями. Аналогічну заміну роблять при перетворенні зворотнього коду від’ємного числа в прямий. На відміну від прямого коду, в зворотньому не можна відкидати нулі після знакового розряду в цілій частині і нулі в кінці дробової частини від’ємного числа.

Представлення додатнього числа в доповнюючому коді співпадавє з його прямим кодом. Правило формування додатнього коду від’ємного числа формулюється так: отримати зворотній код числа і додати 1 в молодший розряд числа. Перетворення доповнюючого коду від’ємного числа здійснюється або зворотнім шляхом (відняти 1 і перетворити в зворотній код) або утворити доповнюючий код до доповнюючого. Нуль, на відміну від прямого і зворотнього кодів, в доповнюючому коді має єдине представлення

Байт - вісім послідовно розміщених бітів, пронумерованих від 0 до 7, при цьому біт 0 є самим молодшим значущим бітом.

Слово - послідовність з двох байтів, які мають послідовну адресу. Розмір слова 16 біт; біти в слові нумеруються від 0 до 15. Байт який містить нульовий біт, називається молодшим байтом, а байт, який містить 15-й біт називають старшим байтом. Мікропроцессори Intel мають важливу особливіть - молодший байт завжди зберігається за молодшою адресою. Адресою слова рахується адреса молодшого байта. Адреса старшого байта може бути використана для доступа до старшої половини слова.

Подвійне слово - послідовність з чотирьох байтів (32 біта), які мають послідовну адресу. Нумерація цих бітів проводиться від 0 до 31. Слово, яке містить нульовий біт називається молодшим словом, а слово яке містить 31-й біт старшим словом. Молодше слово зберігається за меншою адресою. Адресою подвійного слова рахується адреса молодшого слова. Адреса старшого слова може бути використана для доступа до старшої частини подвійного слова. .

Чотирьохкратне слово - послідовність з восьми байт (64 біта). які мають послідовну адресу. Номерація цих бітів проводиться від 0 до 63. Слово яке містить нульовий біт називається молодшим подвійним словом словом, а слово яке містить 63-й біт старшим подвійним словом. Молодше подвійне слово зберігається за молодшою адресою. Адресою подвійного слова рахується адреса молодшого слова. Адреса старшого подвійного слова може бути використана для доступа до старшої половини чотирьохкратного слова.

Поняття про булеві функції

Ф-ція f, яка залежить від n змінних x₁,x₂,…,x_n називається булевою, або переключаючою, якщо ф-ція f і любий з її аргументів x_i, i приймають значення тільки змножини {0,1}. Аргументи булевої ф-ції також називаються булевими.

Довільна булева ф-ція задається одним із трьох способів: матричним (табличним), геометричним і аналітичним.

При матричному способі булева ф-ція f (x₁, x₂, …, x_n) задається таблицею істинності (табл.1 та 2),

В лівій частині якої представлені всі можливі двійкові набори довжини n, а в правій вказується значення ф-ції на цих наборах.

Під двійковим набором = <>, {0,1} розуміють сукупність значень аргументів х₁, х₂,…, х_n булевої ф-ції f. Двійковий набір має довжину n, якщо він представлений n цифрами із множини {0,1}. В табл.1 та 4 перечислені всі двійкові набори відповідної довжини 3 і 4.

Іноді двійкові набори в таблиці істиності булевої ф-ції зручно представляти номерами наборів. Запишемо аргументи x₁,x_2,…x_n в порядку зростання їх індексів. Тоді любий двійковий набір =<>, {0,1} можна розглядати як ціле двійкове число N: N=2^n-1+2^n-2+…+, яке називають номером набору . Наприклад, двійкові набори 0101 і 1000 мають номера 5 і 8 відповідно. Очевидно будь-яка булева ф-ція може бути задана таблицею істинності, в якій двійкові набори замінені своїми номерами (табл.2).

Булеві ф-ції, залежать від великого числа змінних, задавати таблицею істиності незручно, в силу її громіздкості. Наприклад таблиця істинності булевої функції 8 змінних буде містити 2⁸=256 рядків. Тому для задання ф-ції багатьох змінних зручно використати модифікацію таблиці істинності.

Розглянемо спосіб побудови такої таблиці істинності для ф-ції n змінних. Множина із n змінних ф-ції розбивається на дві підмножини: x₁, x₂, …,x_j-1 і х_j, x_j+1,…, x_n. Змінні x₁, x₂, …,x_j-1 відмічають рядки таблиці істинності, задаваючи в кожному рядку значення відповідного двійкового набору довжини j-1. Змінними х_j, x_j+1,…, x_n відмічають її стовбці, задаваючи в кожному стовбці значення відповідного двійкового набору довжини n-j+1. Значення функції записуються в клітинці на перетині відповідного рядка і стовбця (табл 3).

При геометричному способі булева ф-ція f (x₁, x₂, …, x_n) задається з допомогою n-мірного куба. В геометричному смислі кожний двійковий набір =<>, {0,1} є n-мірний вектор, визначаючий точку n-мірного прстору. Виходячи з цього, вся множина наборів, на яких визначена ф-ція n змінних, представляється вершинами n-мірного куба. Відмічаючи точками вершини куба, в яких функція приймає одиничне значення (або нульове), одержимо геометричне представлення функції. Наприклад, булева функція, задана табл.1, геометрично представляється 3-мірним кубом

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

Розглянемо області визначення булевоі ф-ції. Як уже відмічалось, між двійковими наборами і двійковими числами існує взаємнооднозначна відповідність. Отже, існує 2ⁿ різних наборів двійкових змінних.

Таким чином, областю визначення булевої ф-ції n змінних при матричному способі задання являється множина всіх можливих двійкових довжин n наборів, а при геометричному способі задання множина всіх вершин n-мірного одиничного куба.

Булеву ф-цію, визначену на всіх своїх наборах, називають повністю визначеною. Булеву ф-цію n змінних називають неповністю визначеною, або частинною, якщо вона визначена не на всіх двійкових наборах довжини n. Неповністю визначена булева ф-ція не попадає під визначення, дане на початку глави, але при довільному довизначенні (на всіх наборах, на яких вона не визначена) ця невідповідність знімається.

Існує не більше як 2ⁿ різних булевих функцій n змінних. До цього висновку легко прийти, користуючись простими комбінаторними міркуваннями, і згадавши, що на кожному із 2ⁿ наборів функції можуть приймати два значення.

Розглянемо найбільш використовувані булеви ф-ції однієї і двох змінних. Ф-ції однієї змінної представлені таблиці 5, де

f₀ (x) =0 - тотожній нуль (константа 0);

f₁ (x) =x - тотожна ф-ція;

f₂ (x) = - заперечення x (інверсія);

f₃ (x) =1 - тотожна одиниця (константа 1).

Ф-ції двох змінних представлені в табл.6.

Найбільш часто використовуються такі:

f₀ (x₁,x₂) =0 - тотожній нуль (константа 0);

f₁ (x₁,x₂) =x_1*x₂ - кон’юнкція. Замість знака “_*” інколи використовують знак & або . Цю ф-цію часто називають логічним перетворенням або логічним множенням;

f₃ (x₁,x₂) =x₁ - повторення х₁;

f₅ (x₁,x₂) =x₂ - повторення х₂;

f₆ (x₁,x₂) =x₁х₂ -додавання по модулю, або сума mod 2;

f₇ (x₁,x₂) =x₁x₂-диз’юнкція (логічне або);

f₈ (x₁,x₂) =x₁х₂ - функція Вебба (стрілка Пірса);

f₉ (x₁,x₂) =x₁~х_{2 -} еквівалентність;

f₁₃ (x₁,x₂) =x₁х₂ - імплікація;

f₁₄ (x₁,x₂) =x₁/x₂ - штрих Шеффера;

f₁₅ (x₁,x₂) =1 - тотожна одиниця (константа 1);

Розглянемо найбільш використовувані булеви ф-ції однієї і двох змінних. Ф-ції однієї змінної представлені таблиці 5, де

f₀ (x) =0 - тотожній нуль (константа 0);

f₁ (x) =x - тотожна ф-ція;

f₂ (x) = - заперечення x (інверсія);

f₃ (x) =1 - тотожна одиниця (константа 1).

Ф-ції двох змінних представлені в табл.6.

Найбільш часто використовуються такі:

f₀ (x₁,x₂) =0 - тотожній нуль (константа 0);

f₁ (x₁,x₂) =x_1*x₂ - кон’юнкція. Замість знака “_*” інколи використовують знак & або . Цю ф-цію часто називають логічним перетворенням або логічним множенням;

f₃ (x₁,x₂) =x₁ - повторення х₁;

f₅ (x₁,x₂) =x₂ - повторення х₂;

f₆ (x₁,x₂) =x₁х₂ -додавання по модулю, або сума mod 2;

f₇ (x₁,x₂) =x₁x₂-диз’юнкція (логічне або);

f₈ (x₁,x₂) =x₁х₂ - функція Вебба (стрілка Пірса);

f₉ (x₁,x₂) =x₁~х_{2 -} еквівалентність;

f₁₃ (x₁,x₂) =x₁х₂ - імплікація;

f₁₄ (x₁,x₂) =x₁/x₂ - штрих Шеффера;

f₁₅ (x₁,x₂) =1 - тотожна одиниця (константа 1);

Розглянуті простіші булеві ф-ції дозволяють будувати нові булеви ф-ції з допомогою узагальненої операції, що називається операцією суперпозиції. Фактично операція суперпозиції заключається в тому, що існує підстановка замість аргументів інших булевих функцій (в деякій мірі аргументів).

Зауважимо, що суперпозиція функцій одного аргументу породжує функції одного аргументу. Суперпозиція ф-цій двох аргументів дає можливість будувати функції будь-якої кількості аргументів.

Суперпозиція булевих ф-цій представляється у виді логічних формул. Однак слід відмітити:

одна і та ж функція може бути представлена різними формулами;

кожній формулі відповідає своя суперпозиція і своя своя схема з’єднання елементів;

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

Очевидно, що серед схем, які реалізують дану функцію є найбільш проста. Пошук логічної формули, що відповідає цій схемі, предствляє великий практичний інтерес, а перетворення формул булевих функцій грунтується на використанні співвідношень булевої алгебри.

Для булевої алгебри визначена одна одномісна (унарна) операція, дві двохмісні (бінарні) операції кон’юнкції і диз’юнкції (позначаються відповідно “_*", “”).

В цій алгебрі справедливі три аксіоми:

закон комутативності - xy=yx, x_*y=y_*x;

закон асоціативності - (xy) z=x (yz), (x_*y) _*z=x_* (y_*z);

закон дистрибутивності - x_* (yz) = x_*yx_*z, xy_*z= (xy) _* (xz);

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

= _*, _*= (Теореми де Моргана) (1)

xx_*y=x, x_* (xy) =x; (2)

xx=x, x_*x=x, =x; (3)

xy =xy; (4)

x=1, x_*=0; (5)

x1=1; x_*0=0; (6)

xyx=x, (xy) (x) =x; (7)

В ряді випадків, перетворення над формулами булевих функцій зручно виконувати в алгебрі Жегалкіна. Алгебра Жегалкіна включає дві двохмісні операції: кон’юнкцію і додавання за модулем 2 (*,), а також константу 1. Тут мають місце ті ж закони:

xy=yx, x*y=y*x

x (yz) = (xy) z, x* (y*z) = (x*y) *z

x* (yz) =x*yx*z

Для спрощення формул можуть бути використані такі співвідношення:

x0=x; x*1=x; x*0=0; xx=0; x*x=x.

Із комутативності і асоціативності слідує, що диз’юнкція кількох змінних може виконуватися послідовно, причому порядок взяття дизьюнкції не впливає на результат. Тобто, диз’юнкція сукупності змінних може бути виражена співвідношенням

x₁x₂…x_n=x_i

Аналогічно для кон’юнкції

x_1*x_2*…_*x_n=x_i

і суми по модулю 2

x₁x₂…x_n=

Теореми де Моргана для кількох змінних мають вигляд:

=

=

Аналітичне представлення булевих функцій

Вище згадувалося про існування аналітичних форм представлення булевих ф-цій. Тут розглянемо універсальні (канонічні) форми представлення, які дають можливість отримати аналітичну форму безпосередньо по таблиці істиності для довільної булевої ф-ції. Ця форма в дальшому може бути спрощена. Найбільш широке поширення отримала досконала нормальна форма (ДНФ). Перед тим як перейти до вивчення, приведемо визначення конституєнти одиниці - поняття, яким будемо широко користуватися дальше.

Визначення: Конституєнтою одиниці називається функція f (x₁, x₂, …, x_n), яка приймає значення 1 тільки на одному наборі.

Якщо згадати, що диз’юнкція рівна 1, коли хоча б одна з змінних приймає значення 1, то можна легко виразити, будь-яку булеву функцію як диз’юнкцію конституєнт одиниці, які відповідають тим наборам, на яких функція рівна 1. В більш загальному вигляді це можна записати таким чином:

f (x₁, x₂, …, x_n) = f (σ₁, σ₂, …, σ_n) * x₁ ^σ1, x₂ ^σ2, …, x_n ^σn,

де σ_i = 0,1 і

x_i ^σ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	0 1 1 0 1 0 0 1	0 0 0 1 0 1 1 1

Ф-ція f₁ нам відома як сума за модулем 2 трьох змінних х₁х₂х₃. Ф-ція f₂ називається мажорантною (вона приймає значення, яке приймає більшість змінних) і позначається знаком М (х₁, х₂, х₃)

Друга відома форма носить назву “досконалої кон’юктивної нормальної форми" (ДКНФ). Вона будується аналогічно ДДНФ.

Визначення: Конституєнтою нуля називається функція, яка приймає значення 0 на єдиному наборі.

Конституєнта нуля записується у вигляді елементарної диз’юнкції всіх змінних. Кожному набору відповідає своя конституєнта 0.

Приклад Для розглянутих вище ф-цій х₁х₂х₃ і М (х₁, х₂, х₃) (табл.7) побудуємо ДКНФ:

;

.

Легко побачити, що в ДДНФ можна замінити операцію диз’юнкції операцією суми за модулем 2, причому рівність збережеться. Ця форма називається “досконалою поліноміальною нормальною формою” (ДПНФ). Для нашого прикладу

Якщо в ДПНФ замінити всі змінні з запереченням у відповідності з співвідношенням =1х, то отримається канонічний поліном Жегалкіна вигляду

f (x₁, x₂, …, x_n)

=a₀a₁x₁a₂x₂…a_nx_na₁₂x₁x₂a₁₃x₁₃…a_12…nx₁x₂…x_n,

де а_i {0,1}.

Приклад: Для тих же функцій f₁ і f₂ знайдемо канонічний поліном Жегалкіна:

f₁= (x₁1) (x₂1) x₃ (x₁1) x₂ (x₃1) x₁ (x₂1) (x₃1) x₁x₂x₃= x₁x₂x₃x₃x₁x₃x₂x₃x₁x₂x₃x₁x₂x₂x₃x₁x₂x₃x₁x₂x₂x₃x₂x₁x₂x₃x₁x₂x₁x₃x₁x₁x₂x₃=x₁x₂x₃

Аналогічно для f₂= x₁x₂x₂x₃x₁x₃.

В булевій алгебрі широко використовується розклад Шеннона- формула, яка дозволяє перейти від представлення функції від n-змінних до представлення функції від (n-1) - змінних:

f (x₁, x₂, …, x_n) =x₁f (1, x₂, …, x_n) f (0, x₂, …, x_n)

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

f (x₁, x₂, …, x_n) =x₁ [x₂f (1,1, x₃, …, x_n) f (1,0, x₃, …, x_n)] [x₂f (0,1, x₃…x_n) f (0,0,x₃,…x_n)] =x₁,x₂f (1,1,x₃,…x_n) x₁f (1,0,x₃,…,x_n) x₂f (0,1,x₃,. .,x_n) f (0,0,x₃,…,x_n)

Відмітимо, що якщо провести такий же розклад по всіх змінних, получиться ДДНФ.

Мінімізація булевих функцій

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

Визначення: Елементарною кон’юнкцією називається кон’юнкція кінцевого числа різних між собою булевих змінних, кожна з яких може мати, або не мати заперечення.

Визначення: Диз’юнктивною нормальною формою (ДНФ) називається диз’юнкція елементарних кон’юнкцій.

Визначення: Мінімальною диз’юнктивною нормальною формою булевої функції називається ДНФ, що містить найменше число букв.

Визначення: Булева функція g (x₁,x₂,…,x_n) називається імплікантою булевої функції f (x₁,…,x_n), якщо для будь-якого набору змінних, на якому g=1, справедливе f=1.

Визначення: Імпліканта g булевої ф-ції f, що є елементарною кон’юнкцією, називається простою, якщо ніяка частина імпліканти g не є імплікантою функції f.

Приведемо без доведень два твердження, корисні при отриманні мінімальної ДНФ.

Дизьюнкція будь-якої кількості імплікант булевої ф-ції f також є імплікантою цієї функції.

Будь-яка булева функція f еквівалентна диз’юнкції всіх своїх простих імплікант. Така форма представлення булевої ф-ції називається скороченою ДНФ.

Отримання скорочених ДНФ є першим етапом відшукання мінімальних форм булевих функцій. В скорочену ДНФ входять всі прості імпліканти булевої функції. Іноді з скороченої ДНФ можна забрати одну, або декілька простих імплікант, не порушуючи еквівалентності початкової функції. Такі прості імпліканти називаються лишніми. Виключення лишніх простих імплікант з скорочених ДНФ - другий етап мінімізації.

Визначення: Скорочена ДНФ булевої ф-ції називається тупіковою, якщо в ній відсутні лишні прості імпліканти.

Виключення лишніх простих імплікант в скорочених ДНФ булевої функції не є однозначним поцесом, тобто булева функція може мати декілька тупікових ДНФ.

Твердження. Тупікові ДНФ булевої функції f, що містять мінімальну кількість букв, являються мінімальними. Мінімальних ДНФ також може бути декілька.

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

Метод квайна оснований на використанні двох основних співвідношень:

Співвідношення склеювання:

AxA=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 0 0 1 1 0 1 1 1 0 0 0 0 0 1 0

Її ДДНФ має вигляд

f=

Для зручності помітимо кожну конституєнту одиниці з ДДНФ ф-ції f яким-небудь десятковим номером (довільно). Виконаємо склеювання. Конституєнта 1 склеюється тільки з конституєнтою2 (по змінній х₃) і з конституєнтою 3 (по змінній х₂), конституєнта 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. Розглядаються різні варіанти вибору сукупності простих імплікант, які накриють хрестиками решту стовбців матриці, і вибираються варіанти з мінімальним сумарним числом букв в такій сукупності імплікант.

Ядром нашої ф-ції є імпліканти x₁x₂x₃. Імпліканта x₂x₃x₄ -лишня. Тому ф-ція має єдину тупікову і мінімальну ДНФ:

Метод квайна-мак-класкі

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

Всі конституанти одиниці з ДДНФ булевої функцію f записуються їх двійковими номерами.

Всі номери розбиваються на групи, що не перетинаються. Ознака утворення і-ї групи: і одиниць в кожному двійковому номері конституєнти одиниці.

Склеювання проводять тільки між номерами сусідніх груп. Склеювані номери відмічається будь-яким знаком (закреслюванням).

Склеювання проводять всеможливі, як і в методі Квайна.

Невідмічені після склеювання номера є простими імплікантами.

Знаходження мінімальних ДНФ дальше проводяться на імплікантній матриці, як і в методі Квайна.

Метод дозволяє швидко отримати мінімальні ДНФ булевої функції f невеликого числа змінних. В основі методу лежить задання булевих функцій діаграмами деякого спеціального виду, які дістали назву діаграм Вейча. Для булевої ф-ції двох змінних діаграма Вейча має вигляд (табл.3) Кожна клітка діаграми відповідає набору змінних булевої функції в її таблиці істиності. В клітці діаграми ставиться одиниця, якщо булева функція приймає одиничне значення на відповідному наборі. Нульові значення булевої функції в діаграмі не ставляться. Для булевої функції трьох змінних діаграма Вейча має такий вигляд (табл.4)

Додаванням до неї ще такої ж таблиці ми отримаємо діаграму для функції 4-х змінних (табл.5). Таким же чином можна отримати діаграму 5-ти змінних і т.д.

Таблиця 5

1100	1101	1001	1000
1110	1111	1011	1010
0110	0111	0011	0010
0100	0101	0001	0000

Для приведених діаграм характерне наступне:

Кожній клітці діаграми відповідає свій набір.

Сусідні набори розміщені поряд в рядку або в стовбці.

Сусідніми наборами називають набори, які відрізняються однією компонентою.

Ще одне важливе зауваження: стовбці, розміщені по краях діаграми, також вважають сусідніми.

Загальне правило склеювання на діаграмі Вейча можна сформолювати таким чином: склеюванню підлягають прямокутні конфігурації, заповнені одиницями і які містять число кліток, що являються степінню 2. Отримане повне елементарне перетворення визначається як перетворення змінних, які не змінюють свого значення на всіх склеюваних наборах. Число m змінних, які залишились в елементарному перетворенні визначається легко:

m = n - log₂M,

де n - число змінних функції; М - число склеюваних наборів. Метод широко використовується на практиці, завдяки простоті і зручності.

Мінімізація булевої ф-ції полягає в знаходженні мінімального накриття всіх одиниць діаграми Вейча блоками з одиниць (вказаної конфігурації), розміщених в сусідніх клітках діаграми. При цьому завжди вважають, що лівий край діаграми Вейча 4-х змінних прилягає до її правого краю, а верхній край діаграми - до її нижнього краю. Після отримання максимального покриття всіх одиниць діаграми Вейча, мінімальна ДНФ булевої функції записується як диз’юнкція елементарних кон’юнкцій, які відповідають виділеним блокам одиниць в діаграмі.

Приклад. Булева функція f має наступну ДДНФ:

Знайти мінімальну ДНФ з допомогою діаграми Вейча. Діаграма Вейча, що відповідає функції f, представлена в табл.18. Мінімальне накриття всіх одиниць діаграми можливе тільки блокамипо дві одиниці. Кожному такому блоку відповідає своя кон’юнкція, як показано в табл.22. Отже, мінімальна ДНФ ф-ції має вигляд:

.

Таблиця 18

Висновок

Отже, ключовими математичними поняттями теорії цифрових автоматів являється т. зв. булева алгебра та її під-дисципліни, які і визначають її математичний базис.

Література

1. А.Я. Савельев. Арифметические и логические основы цифровых автоматов. М.: Высшая школа. 1999.

2. А.Я. Савельев. Прикладная теория цифровых автоматов. М.: Высшая школа. 2007.

3. Е.Н. Вавилов, Г.П. Портной. Синтез схем электронных цифровых машин. М.: Советское радио. 2003.

4. Г.Н. Соловьев. Арифметические устройства ЭВМ. М.: Энергия. 2008.