|
| Суббота, 21.06.2025, 09:18 |
| Приветствую Вас Гость | RSS |
|
|
ПТЦА
| |
| Ellcrys | Дата: Вторник, 21.06.2011, 14:04 | Сообщение # 1 |
|
Любопытный соф
Группа: Администраторы
Сообщений: 56
Статус: Offline
| 3. Прикладна теорія цифрових автоматів. 1
a.Двійкова СЧ. Переваги і недоліки двійкової СЧ. Переведення довільного числа з десяткової СЧ в двійкову СЧ і навпаки. 2
2. Двійкова арифметика (виконання операцій додавання, віднімання, множення і ділення в 2-СЧ). 3
7. Основні властивості двійкових чисел. Правила «швидкого рахунку». 3
3. Шістнадцяткова СЧ. Шістнадцяткова арифметика. 4
4. СЧ з основою р. Переведення довільного числа з десяткової СЧ в СЧ з основою р і навпаки. 5
5. Виконання арифметичних дій в СЧ з основою р. 6
6. Змішані СЧ. Запис чисел в змішаних СЧ. Системи з кратними основами. Теорема для СЧ з кратними основами 7
8. Дві форми комп’ютерного представлення числових даних. Їх переваги і недоліки. Діапазон представлення чисел в цих випадках. 9
9. Представлення довільного числа в формі з плаваючою крапкою. Мантиса та порядок числа. Нормалізована форма представлення числа. 10
10. Прямий, зворотній та доповнюючий коди чисел. Необхідність використання доповнюючого коду. Діапазони представлення цілих додатніх та від’ємних чисел: байт, слово, подвійне слово. 11
11. Поняття про булеві функції. Три способи задання булевих функцій. Таблиця істинності. Номер двійкового набору. Повністю та неповністю визначені булеві функції. 12
12. Основні булеві функції однієї і двох зміних. Унарна і бінарні операції булевої алгебри. Суперпозиція булевих функцій. Три аксіоми булевої алгебри. Алгебра Жегалкіна. Теореми де Моргана. 14
13. Аналітичне представлення булевих функцій. Досконала диз’юнктивна нормальна форма(ЗДНФ). Досконала кон’юнктивна нормальна форма(ЗКНФ). Конституєнта нуля. Конституєнта одиниці. Розклад Шеннона. 16
14. Мінімізація булевих функцій. Постановка задачі мінімізації булевих функцій. Елементарна кон’юнкція. Диз’юнктивна нормальна форма (ДНФ). Мінімальна диз’юнктивна нормальна форма (МДНФ). Два етапи мінімізації булевих функцій. 18
15. Метод Квайна. Співвідношення склеювання та поглинання. Метод Квайна-Мак-Класкі. Метод діаграм Вейча. Сусідні набори. Загальне правило склеювання на діаграмі Вейча. 19
a.Двійкова СЧ. Переваги і недоліки двійкової СЧ. Переведення довільного числа з десяткової СЧ в двійкову СЧ і навпаки.
Двійкова позиційна система числення
Позиційна система числення з основою 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.
8110|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, то: Aq max=qn-1; Aq min= -(qn-1);
Діапазон представлення чисел в заданій системі:
Aq max ≥ДП≥ Aq min .
2. Двійкова арифметика (виконання операцій додавання, віднімання, множення і ділення в 2-СЧ).
7. Основні властивості двійкових чисел. Правила «швидкого рахунку».
Двійкова арифметика
Арифметичні дії в двійковій системі (двійковій арифметиці) виконуються за звичайними для позиційних систем правилами (алгоритмами), які нам відомі з десяткової арифметики, але при цьому, звичайно, використовуються таблиці додавання і множення двійкової системи. Таблиця додавання
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
100000 12=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
Крапки, поставлені над деякими розрядами, показують, що в двійковій системі одиниця відміченого розряду роздроблюється на дві одиниці вищого розряду.Множення
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
11011112
1011012
1101111
1101111
1101111
1101111 __
10011100000112
3. Шістнадцяткова СЧ. Шістнадцяткова арифметика.
Представим, что необходимо просмотреть содержимое некотоpых байт в
памяти (это встретится в следующей главе). Требуется oпределить содержимое
четырех последовательных байт (двух слов), которые имеют двоичные
значения. Так как четыре байта включают в себя 32 бита, то специалисты
разработали "стенографический" метод представления двоичных данных. По
этому методу каждый байт делится пополам и каждые полбайта выражаются
соответствующим значением. Рассмотрим следующие четыре байта:
Двоичное: 0101 1001 0011 0101 1011 1001 1100 1110
Десятичное: 5 9 3 5 11 9 12 14
Так как здесь для некоторых чисел требуется две цифры, расширим
систему счисления так, чтобы 10=A, 11=B, 12=C, 13=D, 14=E, 15=F. таким
образом получим более сокращенную форму, которая представляет содержимое
вышеуказанных байт:
59 35 B9 CE
Такая система счисления включает "цифры" от 0 до F, и так как таких
цифр 16, она называется шестнадцатиричным представлениeм.
Шестнадцатиричный формат нашел большое применение в языке ассемблера.
В листингах ассемблирования программ в шестнадцатеричном формате показаны
все адреса, машинные коды команд и содержимое констант. Также для отладки
при использовании программы DOS DEBUG адреса и содержимое байтов выдается
в шестнадцатиричном формате.
Если немного поработать с шестнадцатиричным форматом, то можно быстро
привыкнуть к нему. рассмотрим несколько проcтых примеров шестнадцатиричной
арифметики. Следует помнить, что после шестнадцатиричного числа F следует
шестнадцатиричное 10, что равно десятичному числу 16.
6 5 F F 10 FF
4 8 1 F 10 1
- - -- -- -- ---
A D 10 1E 20 100
Заметьте также, что шест.20 эквивалентно десятичному 32, шест.100 -
десятичному 256 и шест.100 - десятичному 4096.
В данной книге шестнадцатиричные числа записываются, например, как
шест.4B, двоичные числа как дв.01001011, и десятичные числа, как 75
(отсутствие какого-либо описания предполагает десятичное число).
Исключения возможны, когда база числа очевидна из контекста. Для индикации
шест. числа в ассемблерной программе непосредственно после числа ставится
символ "H", например, 25H (десятичное значение 37). Шест. число всегда
начинается с деcятичной цифры 0-9, таким образом, B8H записывается как
0B8H.
В прил.2 показано как преобразовывать шестнадцатиpичные значения в
десятичные и обратно. Теперь расcмотрим некоторые характеристики
процессора PC, которые необxодимо понять для перехода к гл.2.
4. СЧ з основою р. Переведення довільного числа з десяткової СЧ в СЧ з основою р і навпаки.
Системи числення з довільною основою
Ми розглянули алгоритм переводу чисел з дв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
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м переводом.
5. Виконання арифметичних дій в СЧ з основою р.
Перед тим, як розглянути формальні правила двійкової арифметики підкреслимо загальний принцип складання і віднімання чисел представлених в будь-якої позиційної системи числення.
У загальному випадку процедури складання і віднімання двох чисел
A B = C в будь-якої позиційної системи числення починаються з молодших розрядів.
Код суми каждго i-того розряду сi виходить в результаті складання
ai + bi +1, де одиниця відповідає перенесенню з молодшого (i - 1) -разряда в i-тый, якщо в молодшому розряді код суми вийшов більше або рівним підставі системи числення.
Код різниці кожного i-того розряду виходить в результаті віднімання
ai - bi -1, де одиниця відповідає заему, якщо він був, в молодші розряди величини, рівної підставі системи числення.
Отже, правила і методи складання і віднімання в будь-якої позиційної системи числення в принципі залишаються такими ж, як в десятковій системі.
Для переведення цілої частини десяткової системи числення в систему числення з основою Р, потрібно послідовно ділити на основу Р до тих пір, поки частка не стане меншою за Р. Отримана частка та остачі записують у зворотному порядку
Дробова частина 10-го числа послідовно множиться на Р до тих пір поки вона не стане рівна 0. Якщо в завданні вказується розрядна сітка, то переведення здійснюють таким чином, щоб заповнити розрядну сітку інакше буде вказано кількість розрядів після коми які потрібно представити
Ми розглянули алгоритм переводу чисел з дв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
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м переводом.
6. Змішані СЧ. Запис чисел в змішаних СЧ. Системи з кратними основами. Теорема для СЧ з кратними основами
Існує простий спосіб запису десяткових чисел за допомогою двійкових цифр - представлення чисел в мішаній двійково-десятковій системі числення. В ній кожна цифра десяткового зображення числа записується в двійковій системі числення.
Причому для того, щоб такий запис був однозначним, для представлення будь-якої десяткової цифри відводиться одна і та ж кількість двійкових розрядів - чотири. Якщо десяткова цифра вимагає для свого представлення менше значущих двійкових цифр, то попереду цих цифр дописуються нулі (так щоб загальна кількість двійкових знаків залишалась рівною чотирьом).
Наприклад, десяткове число 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
Т е о р е м а.. Якщо 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
Тут, як і в двійково-десятковому записі, в цілій частині відкинуті крайні зліва нулі, а в дробовій частині - крайні справа. Безумовно, треба їх враховувати як недостатні у відповідних тріадах двійкових цифр. Зворотній перевід чисел з вісімкової системи числення в двійкову також простий. Кожну цифру вісімкового числа записуємо трійкою двійкових символів, тобто записуємо його в двійково-вісімковій системі, а так як цей запис співпадає з двійковим, то ми одержимо число в двійковій системі. Переведемо, наприклад, число (3514,72)8 з вісімкової системи в двійкову:
(3514,72)8 = (11 101 001 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 ©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 1110 1001)2 .
3 c 2 e 9
Під кожною четвіркою двійкових цифр ми записали відповіднийі шістнадцятковий символ.
|
| |
| |
| Ellcrys | Дата: Вторник, 21.06.2011, 14:05 | Сообщение # 2 |
|
Любопытный соф
Группа: Администраторы
Сообщений: 56
Статус: Offline
| 8. Дві форми комп’ютерного представлення числових даних. Їх переваги і недоліки. Діапазон представлення чисел в цих випадках.
Представлення комп’ютерної інформації
Форма з фіксованою крапкою
В сучасних ЕОМ застосовуються два способу представдення чисел: з фіксованою крапкою і плаваючою крапкою.
В першому випадку місце коми, яка відділяє цілу частину числа від дробової, визначається на етапі конструювання ЕОМ. Зразу ж вказується кількість розрядів, які відводяться для зображення цілої і дробової частин. Причому кожному розряду комірки відповідає завжди один і той же розряд числа, що суттєво спрощує виконання арифметичних дій. Нехай, наприклад, комірка пам’яті машини має 24 двійкових розряда. Як ми знаємо, в комірку можна записати будь-яке машинне слово, тобто довільний набір з нулів і одиниць. Якщо це слово – число, то в конструкції машини може бути передбачено його представлення в формі з фіксованою комою. Наприклад, воно може бути таким: крайній зліва розряд – знаковий, потім наступні 9 розрядів відводяться під цілу частину і, накінець , 14 розрядів, які залишилися, під дробову частину числа, тобто кома тут завжди на одному і тому ж місці - після десятого розряду машинного слова (з врахуванням знакового розряду). Тоді найбільше число, яке можна представити, буде:
(111111111,11111111111111)2.
Видно, що воно менше, ніж 29 = (512)10. А найменше за модулем відмінне від нуля число дорівнює
(000000000,00000000000001)2 = 2-14 .
Тобто, діапазон чисел, які можна записати в комірку пам’ті машини, тут такий:
2-14 < |a| < 29 .
Форма з плаваючою крапкою
Для того, щоб збільшити діапазон чисел, використовують другу форму запису чисел – з плаваючою комою. Будь-яке число в системі числення з основою Q можна записати так:
a=A*Qp . A називають мантисою числа, а P – порядком.
Наприклад, в десятковій системі числення число 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 <|А|< 1 (мова йде про десяткову систему числення). Iншими словами, перша цифра мантиси після коми повинна бути відмінною від нуля.
9. Представлення довільного числа в формі з плаваючою крапкою. Мантиса та порядок числа. Нормалізована форма представлення числа.
Форма з плаваючою крапкою
Для того, щоб збільшити діапазон чисел, використовують другу форму запису чисел – з плаваючою комою. Будь-яке число в системі числення з основою Q можна записати так:
a=A*Qp .
A називають мантисою числа, а P – порядком. Наприклад, в десятковій системі числення число 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 <|А|< 1 (мова йде про десяткову систему числення). Iншими словами, перша цифра мантиси після коми повинна бути відмінною від нуля. В нашому прикладі десяткове число а=3,14 в нормалізованій формі має вигляд 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
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 )2 =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)+15 *2-127 = 2-142 .
В цьому випадку мантиса
А=(0, 000...01)2 = 2-15 , порядок Р = -(1111111)2 = -(127)10 .
10. Прямий, зворотній та доповнюючий коди чисел. Необхідність використання доповнюючого коду. Діапазони представлення цілих додатніх та від’ємних чисел: байт, слово, подвійне слово.
Прямий, зворотній і доповнюючий коди
В ЕОМ доцільно представляти знаки чисел з допомогою тих же символів через, через які записується саме число. Для цього виділяється додатковий розряд, який називають знаковим і розташовують зліва від старшого розряду числа. Будемо позначати знакові розрядні числа як і відділяти їх крапками від цілої частини числа і комами від дробової.
Для правильності виконання арифметичних операцій над числами, знаки яких закодовані числами, використовують спеціальні способи представлення чисел: прямий, зворотній і додатковий.
Прямий код використовується для вводу-виводу інформації і в запам’ятовуючих пристроях.
Додавання чисел в прямому коді (з одинаковими знаками) не викликає труднощів. Однак додавання чисел з різними знаками в прямих кодах незручно, так як повинно бути спеціальне обладнання для віднімання чисел і визначення знаку різниці.
Операцію алгебраїчного додавання чисел можна звести до операцій додавання при використанні зворотніх і додаткових кодів.
Представлення додатнього числа в зворотньому коді співпадавє з його прямим кодом. Для отримання зворотнього коду від’ємного числа в двійковій системі необхідно в знаковому розряді записати 1, а в інших розрядах одиниці замінити нулями, а нулі одиницями. Аналогічну заміну роблять при перетворенні зворотнього коду від’ємного числа в прямий. На відміну від прямого коду, в зворотньому не можна відкидати нулі після знакового розряду в цілій частині і нулі в кінці дробової частини від’ємного числа.
Представлення додатнього числа в доповнюючому коді співпадавє з його прямим кодом. Правило формування додатнього коду від’ємного числа формулюється так: отримати зворотній код числа і додати 1 в молодший розряд числа. Перетворення доповнюючого коду від’ємного числа здійснюється або зворотнім шляхом ( відняти 1 і перетворити в зворотній код) або утворити доповнюючий код до доповнюючого. Нуль, на відміну від прямого і зворотнього кодів, в доповнюючому коді має єдине представлення
Байт – вісім послідовно розміщених бітів, пронумерованих від 0 до 7, при цьому біт 0 є самим молодшим значущим бітом.
Слово – послідовність з двох байтів, які мають послідовну адресу. Розмір слова 16 біт; біти в слові нумеруються від 0 до 15. Байт який містить нульовий біт, називається молодшим байтом, а байт, який містить 15-й біт називають старшим байтом. Мікропроцессори Intel мають важливу особливіть – молодший байт завжди зберігається за молодшою адресою. Адресою слова рахується адреса молодшого байта. Адреса старшого байта може бути використана для доступа до старшої половини слова.
Подвійне слово – послідовність з чотирьох байтів (32 біта), які мають послідовну адресу. Нумерація цих бітів проводиться від 0 до 31. Слово, яке містить нульовий біт називається молодшим словом, а слово яке містить 31-й біт старшим словом. Молодше слово зберігається за меншою адресою. Адресою подвійного слова рахується адреса молодшого слова. Адреса старшого слова може бути використана для доступа до старшої частини подвійного слова..
Чотирьохкратне слово- послідовність з восьми байт (64 біта). які мають послідовну адресу. Номерація цих бітів проводиться від 0 до 63. Слово яке містить нульовий біт називається молодшим подвійним словом словом, а слово яке містить 63-й біт старшим подвійним словом. Молодше подвійне слово зберігається за молодшою адресою. Адресою подвійного слова рахується адреса молодшого слова. Адреса старшого подвійного слова може бути використана для доступа до старшої половини чотирьохкратного слова.
11. Поняття про булеві функції. Три способи задання булевих функцій. Таблиця істинності. Номер двійкового набору. Повністю та неповністю визначені булеві функції.
Основні поняття
Ф-ція 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.
Іноді двійкові набори в таблиці істиності булевої ф-ції зручно представляти номерами наборів. Запишемо аргументи 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)=x1x2-диз’юнкція (логічне або);
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);
12. Основні булеві функції однієї і двох зміних. Унарна і бінарні операції булевої алгебри. Суперпозиція булевих функцій. Три аксіоми булевої алгебри. Алгебра Жегалкіна. Теореми де Моргана.
Розглянемо найбільш використовувані булеви ф-ції однієї і двох змінних. Ф-ції однієї змінної представлені таблиці 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)=x1x2-диз’юнкція (логічне або);
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);
Розглянуті простіші булеві ф-ції дозволяють будувати нові булеви ф-ції з допомогою узагальненої операції, що називається операцією суперпозиції. Фактично операція суперпозиції заключається в тому, що існує підстановка замість аргументів інших булевих функцій (в деякій мірі аргументів).
Зауважимо, що суперпозиція функцій одного аргументу породжує функції одного аргументу. Суперпозиція ф-цій двох аргументів дає можливість будувати функції будь-якої кількості аргументів.
Суперпозиція булевих ф-цій представляється у виді логічних формул. Однак слід відмітити :
одна і та ж функція може бути представлена різними формулами;
кожній формулі відповідає своя суперпозиція і своя своя схема з’єднання елементів;
між формулами представлення булевих ф-цій і схемами, які їх реалізують, існує взаємнооднозначна відповідність.
Очевидно, що серед схем, які реалізують дану функцію є найбільш проста. Пошук логічної формули, що відповідає цій схемі, предствляє великий практичний інтерес, а перетворення формул булевих функцій грунтується на використанні співвідношень булевої алгебри.
Для булевої алгебри визначена одна одномісна (унарна) операція, дві двохмісні (бінарні) операції кон’юнкції і диз’юнкції (позначаються відповідно “*”, “”).
В цій алгебрі справедливі три аксіоми:
закон комутативності - 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.
Із комутативності і асоціативності слідує, що диз’юнкція кількох змінних може виконуватися послідовно, причому порядок взяття дизьюнкції не впливає на результат. Тобто, диз’юнкція сукупності змінних може бути виражена співвідношенням
x1x2…xn=xi
Аналогічно для кон’юнкції
x1*x2*…*xn=xi
і суми по модулю 2
x1x2…xn=
Теореми де Моргана для кількох змінних мають вигляд:
=
=
|
| |
| |
| Ellcrys | Дата: Вторник, 21.06.2011, 14:05 | Сообщение # 3 |
|
Любопытный соф
Группа: Администраторы
Сообщений: 56
Статус: Offline
| 8. Дві форми комп’ютерного представлення числових даних. Їх переваги і недоліки. Діапазон представлення чисел в цих випадках.
Представлення комп’ютерної інформації
Форма з фіксованою крапкою
В сучасних ЕОМ застосовуються два способу представдення чисел: з фіксованою крапкою і плаваючою крапкою.
В першому випадку місце коми, яка відділяє цілу частину числа від дробової, визначається на етапі конструювання ЕОМ. Зразу ж вказується кількість розрядів, які відводяться для зображення цілої і дробової частин. Причому кожному розряду комірки відповідає завжди один і той же розряд числа, що суттєво спрощує виконання арифметичних дій. Нехай, наприклад, комірка пам’яті машини має 24 двійкових розряда. Як ми знаємо, в комірку можна записати будь-яке машинне слово, тобто довільний набір з нулів і одиниць. Якщо це слово – число, то в конструкції машини може бути передбачено його представлення в формі з фіксованою комою. Наприклад, воно може бути таким: крайній зліва розряд – знаковий, потім наступні 9 розрядів відводяться під цілу частину і, накінець , 14 розрядів, які залишилися, під дробову частину числа, тобто кома тут завжди на одному і тому ж місці - після десятого розряду машинного слова (з врахуванням знакового розряду). Тоді найбільше число, яке можна представити, буде:
(111111111,11111111111111)2.
Видно, що воно менше, ніж 29 = (512)10. А найменше за модулем відмінне від нуля число дорівнює
(000000000,00000000000001)2 = 2-14 .
Тобто, діапазон чисел, які можна записати в комірку пам’ті машини, тут такий:
2-14 < |a| < 29 .
Форма з плаваючою крапкою
Для того, щоб збільшити діапазон чисел, використовують другу форму запису чисел – з плаваючою комою. Будь-яке число в системі числення з основою Q можна записати так:
a=A*Qp . A називають мантисою числа, а P – порядком.
Наприклад, в десятковій системі числення число 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 <|А|< 1 (мова йде про десяткову систему числення). Iншими словами, перша цифра мантиси після коми повинна бути відмінною від нуля.
9. Представлення довільного числа в формі з плаваючою крапкою. Мантиса та порядок числа. Нормалізована форма представлення числа.
Форма з плаваючою крапкою
Для того, щоб збільшити діапазон чисел, використовують другу форму запису чисел – з плаваючою комою. Будь-яке число в системі числення з основою Q можна записати так:
a=A*Qp .
A називають мантисою числа, а P – порядком. Наприклад, в десятковій системі числення число 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 <|А|< 1 (мова йде про десяткову систему числення). Iншими словами, перша цифра мантиси після коми повинна бути відмінною від нуля. В нашому прикладі десяткове число а=3,14 в нормалізованій формі має вигляд 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
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 )2 =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)+15 *2-127 = 2-142 .
В цьому випадку мантиса
А=(0, 000...01)2 = 2-15 , порядок Р = -(1111111)2 = -(127)10 .
10. Прямий, зворотній та доповнюючий коди чисел. Необхідність використання доповнюючого коду. Діапазони представлення цілих додатніх та від’ємних чисел: байт, слово, подвійне слово.
Прямий, зворотній і доповнюючий коди
В ЕОМ доцільно представляти знаки чисел з допомогою тих же символів через, через які записується саме число. Для цього виділяється додатковий розряд, який називають знаковим і розташовують зліва від старшого розряду числа. Будемо позначати знакові розрядні числа як і відділяти їх крапками від цілої частини числа і комами від дробової.
Для правильності виконання арифметичних операцій над числами, знаки яких закодовані числами, використовують спеціальні способи представлення чисел: прямий, зворотній і додатковий.
Прямий код використовується для вводу-виводу інформації і в запам’ятовуючих пристроях.
Додавання чисел в прямому коді (з одинаковими знаками) не викликає труднощів. Однак додавання чисел з різними знаками в прямих кодах незручно, так як повинно бути спеціальне обладнання для віднімання чисел і визначення знаку різниці.
Операцію алгебраїчного додавання чисел можна звести до операцій додавання при використанні зворотніх і додаткових кодів.
Представлення додатнього числа в зворотньому коді співпадавє з його прямим кодом. Для отримання зворотнього коду від’ємного числа в двійковій системі необхідно в знаковому розряді записати 1, а в інших розрядах одиниці замінити нулями, а нулі одиницями. Аналогічну заміну роблять при перетворенні зворотнього коду від’ємного числа в прямий. На відміну від прямого коду, в зворотньому не можна відкидати нулі після знакового розряду в цілій частині і нулі в кінці дробової частини від’ємного числа.
Представлення додатнього числа в доповнюючому коді співпадавє з його прямим кодом. Правило формування додатнього коду від’ємного числа формулюється так: отримати зворотній код числа і додати 1 в молодший розряд числа. Перетворення доповнюючого коду від’ємного числа здійснюється або зворотнім шляхом ( відняти 1 і перетворити в зворотній код) або утворити доповнюючий код до доповнюючого. Нуль, на відміну від прямого і зворотнього кодів, в доповнюючому коді має єдине представлення
Байт – вісім послідовно розміщених бітів, пронумерованих від 0 до 7, при цьому біт 0 є самим молодшим значущим бітом.
Слово – послідовність з двох байтів, які мають послідовну адресу. Розмір слова 16 біт; біти в слові нумеруються від 0 до 15. Байт який містить нульовий біт, називається молодшим байтом, а байт, який містить 15-й біт називають старшим байтом. Мікропроцессори Intel мають важливу особливіть – молодший байт завжди зберігається за молодшою адресою. Адресою слова рахується адреса молодшого байта. Адреса старшого байта може бути використана для доступа до старшої половини слова.
Подвійне слово – послідовність з чотирьох байтів (32 біта), які мають послідовну адресу. Нумерація цих бітів проводиться від 0 до 31. Слово, яке містить нульовий біт називається молодшим словом, а слово яке містить 31-й біт старшим словом. Молодше слово зберігається за меншою адресою. Адресою подвійного слова рахується адреса молодшого слова. Адреса старшого слова може бути використана для доступа до старшої частини подвійного слова..
Чотирьохкратне слово- послідовність з восьми байт (64 біта). які мають послідовну адресу. Номерація цих бітів проводиться від 0 до 63. Слово яке містить нульовий біт називається молодшим подвійним словом словом, а слово яке містить 63-й біт старшим подвійним словом. Молодше подвійне слово зберігається за молодшою адресою. Адресою подвійного слова рахується адреса молодшого слова. Адреса старшого подвійного слова може бути використана для доступа до старшої половини чотирьохкратного слова.
11. Поняття про булеві функції. Три способи задання булевих функцій. Таблиця істинності. Номер двійкового набору. Повністю та неповністю визначені булеві функції.
Основні поняття
Ф-ція 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.
Іноді двійкові набори в таблиці істиності булевої ф-ції зручно представляти номерами наборів. Запишемо аргументи 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)=x1x2-диз’юнкція (логічне або);
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);
12. Основні булеві функції однієї і двох зміних. Унарна і бінарні операції булевої алгебри. Суперпозиція булевих функцій. Три аксіоми булевої алгебри. Алгебра Жегалкіна. Теореми де Моргана.
Розглянемо найбільш використовувані булеви ф-ції однієї і двох змінних. Ф-ції однієї змінної представлені таблиці 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)=x1x2-диз’юнкція (логічне або);
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);
Розглянуті простіші булеві ф-ції дозволяють будувати нові булеви ф-ції з допомогою узагальненої операції, що називається операцією суперпозиції. Фактично операція суперпозиції заключається в тому, що існує підстановка замість аргументів інших булевих функцій (в деякій мірі аргументів).
Зауважимо, що суперпозиція функцій одного аргументу породжує функції одного аргументу. Суперпозиція ф-цій двох аргументів дає можливість будувати функції будь-якої кількості аргументів.
Суперпозиція булевих ф-цій представляється у виді логічних формул. Однак слід відмітити :
одна і та ж функція може бути представлена різними формулами;
кожній формулі відповідає своя суперпозиція і своя своя схема з’єднання елементів;
між формулами представлення булевих ф-цій і схемами, які їх реалізують, існує взаємнооднозначна відповідність.
Очевидно, що серед схем, які реалізують дану функцію є найбільш проста. Пошук логічної формули, що відповідає цій схемі, предствляє великий практичний інтерес, а перетворення формул булевих функцій грунтується на використанні співвідношень булевої алгебри.
Для булевої алгебри визначена одна одномісна (унарна) операція, дві двохмісні (бінарні) операції кон’юнкції і диз’юнкції (позначаються відповідно “*”, “”).
В цій алгебрі справедливі три аксіоми:
закон комутативності - 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.
Із комутативності і асоціативності слідує, що диз’юнкція кількох змінних може виконуватися послідовно, причому порядок взяття дизьюнкції не впливає на результат. Тобто, диз’юнкція сукупності змінних може бути виражена співвідношенням
x1x2…xn=xi
Аналогічно для кон’юнкції
x1*x2*…*xn=xi
і суми по модулю 2
x1x2…xn=
Теореми де Моргана для кількох змінних мають вигляд:
=
=
|
| |
| |
|
|
|
