Р. В. Маслій алгоритмічні мови та програмування частина основи інформатики та комп’ютерної техніки icon

Р. В. Маслій алгоритмічні мови та програмування частина основи інформатики та комп’ютерної техніки




НазваР. В. Маслій алгоритмічні мови та програмування частина основи інформатики та комп’ютерної техніки
Сторінка8/9
Дата28.06.2012
Розмір1.47 Mb.
ТипДокументи
1   2   3   4   5   6   7   8   9
1. /НП_АМтаП.ч1.Довгалець.Масл_й_new.docР. В. Маслій алгоритмічні мови та програмування частина основи інформатики та комп’ютерної техніки

Приклад 4.1. Перевести десяткове дробове число 0,2812510 у двійкову систему числення.

Обчислення проводять за такою схемою:



Результат: 0,2812510=0,010012


Приклад 4.2. Перевести десяткове дробове число 0,910 у двійкову систему числення.




Очевидно, що цей процес може продовжуватись без кінця, даючи все нові і нові знаки в відображенні двійкового еквівалента числа 0,910. Так, за чотири кроки ми отримаємо число 0,11102, а за сім кроків – число 0,11100112, яке є найбільш точним поданням числа 0,910 в двійковій системі числення і т.д. Такий нескінченний процес переривають на певному кроці, коли вважають, що отримана потрібна точність подання числа.

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

  1. поділити число на 2. Зафіксувати залишок (0 чи 1) і різницю;

  2. якщо частка не дорівнює 0, то поділити її на 2 і так далі.

    Якщо частка дорівнює 0, то записати всі отримані залишки, починаючи з першого, зліва направо.


Приклад 4.3. Записати десяткове число 5810 у двійковій системі числення.

Ділення у стовпчик виконується так, як показано нижче. Цифрами шуканого числа, рівного даному, є всі залишки. Поява у частці нуля вказує на кінець процесу ділення:




Залишки, починаючи з останнього, виписані знизу вверх, утворюють шукане двійкове число: 5810 = 1110102.

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


У вісімковій системі числення використовують вісім цифр – від 0 до 7, а будь-яке число подають сумою цілих степенів основи 8, помножених на відповідні коефіці­єнти a (0, 1, ..., 7).

Наприклад, число 21510 записується у вісімковій системі числення в такий спосіб: .

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


Приклад 4.4. Записати десяткові числа 31710 і 192210 у вісімковій системі числення:




Отже, маємо: 31710=4758; 192210=36028.

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

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

Приклад 4.5. Перевести двійкові числа 10101102 та 11110100,010 111011110000112 у вісімкову систему числення.

1) 10101102=001 010 1102 = 1268




2) 11 110 100, 010 111 011 110 000 112 =

011 110 100, 010 111 011 110 000 1102 = 364,2736068




Приклад 4.6. Перевести десяткове дробове число 0,6562510 у вісімкову систему числення.




Відповідь: 0,65625 10=0,528.

При переводі змішаних десяткових чисел (наприклад, 124,2510) у вісімкову систему, окремо переводять цілі і дробові частини.


Приклад 4.7. Перевести дробове число 124,2510 у вісімкову систему.




Відповідь: 124,2510=174,28.


У шістнадцятковій системі числення алфавіт цифрових знаків складається із 16 символів, причому як перші десять символів використовують арабські цифри від 0 до 9, а додатково до них – буквені символи: 10 – А(а), 11 – В(b), 12 – С(с), 13 – D(d), 14 – E(e), 15–F(f).

Число 21510 у шістнадцятковій системі числення записують так:




Приклади 4.8

1510=F16;

3110=1*161 + F*160 =1F16;

16710=10*161+7*160=A716;

6C16= 0110 1100 2;


111110111112= 0111 1101 11112=7DF16;


11101001000,110100102= 0111 0100 1000, 1101 0010=748,D216.


Приклад 4.9. Перевести десяткове число 0,6562510 в шістнадцяткову систему числення.




Відповідь: 0,6562510=0,А816.


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


Приклад 4.10. Перевести двійково-десятковий код 010101110011,01002-10 у десяткову систему.

0101 0111 0011 0100 2-10=573,410


Приклад 4.11. Перевести десяткове число 362,8910 у двійково-десятковий код.


362,8910= 11 0110 0010, 1000 1001 2-10.




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

1) основу нової системи числення виразити цифрами вхідної системи числення і всі наступні дії проводити у вхідній системі числення;

2) послідовно множити дане число і отримані дробові частини ділення на основу нової системи до тих пір, поки дробова частина ділення не стане дорівнювати нулю чи не буде отримана потрібна точність подання числа;

3) отримані цілі частини ділення, які є цифрами числа в новій системі числення, привести відповідно до алфавіту нової системи числення;

4) додати дробові частини числа в новій системі числення, починаючи з цілої частини першого ділення.

Існують різні способи переведення чисел з однієї системи числення в іншу. Розглянемо загальні правила переведення чисел з однієї позиційної системи числення в іншу.

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

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

Для переведення неправильного дробу (більшого за 1) потрібно виконати окремо пе­реведення цілої і дробової частин.

Операції ділення і множення виконуються в десятковій системі числення. Для переведення чисел із системи числення S y десяткову систему числення зручні­ше скористатися формулою (4.1). Оскільки основи вісімкової і шістнадцяткової систем числення відповідають цілим степеням числа 2 (8 = 23, 16 = 24), для них застосовують прості правила переведення в двійкову систему числення і навпаки. Кожні три цифри двійкового числа перетворяться в одну цифру вісім нового числа (якщо довжина двій­кового числа не кратна трьом, спочатку додається відповідна кількість нулів). У разі оберненого перетворення кожна цифра вісімкового числа перетвориться в три двійкові цифри.

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

Приклад 4.12

1. Переведення числа 37710 у шістнадцяткову систему числення:

377:16 = 23 (остача 9); 23:16 = 1 (остача 7); 1:16 = 0 (остача 1).

Результат: 17916.


2. Переведення дробого десяткового числа 0,687510 у вісімкову систему числення:



Результат: 0,548.


3. Переведення числа FCA116 у десяткову систему числення:



Результат: 6467310


4
1111

0111
. Переведення числа 11111112 у шістнадцяткову систему числення:

011111112 = =7F16


5
0110

1100

1000
. Переведення числа 6С816 у двійкову систему числення:

6C816 = = 011011 0010002


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

Системи числення, які використовуються в ЕОМ, наведені табл. 4.4.


Таблиця 4.4 – Системи числення

Система

числення

Основа

Алфавіт

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

Двійкова

2

1,0

А=11011; А=27

Вісімкова

8

0,1,2,3,4,5,6,7

А=23; А=19

Шістнадцяткова

16

0,1,2,3,4,5,6,7

A,B,C,D,E,F

А=2В;

A=43

Двійково-десяткова

2

1,0

А=01000101; А=45


4.3 Формати подання даних


Будь-яка інформація (числа, команди, алфавітно-цифрові записи тощо) подається в комп’ютері у вигляді двійкових кодів. Окремі елементи двійкового коду, що набува­ють значення 0 чи 1, називають розрядами чи бітами.

У старих комп’ютерах, призначених для обчислювальних задач, мінімальною одини­цею інформації, доступної для оброблення, була комірка. Кількість розрядів у комірці орієнтовано на подання чисел і вона різна у різних комп’ютерах (24 біт, 48 біт і т. д.). Однак такий великий розмір комірки був незручний для подання символів, оскільки для подання символьної інформації достатньо 5...8 біт. Це дає можливість подати від
32 до 256 символів. Мінімальною одиницею інформації, оброблюваної в сучасному комп’ютері, є байт, що складається з восьми двійкових розрядів (бітів). Кожен байт, розміщений у пам’яті комп’ютера, має свою адресу, що визначає його місцезнаходжен­ня і задається відповідним кодом. Адреси пам’яті починаються з нуля для першого бай­та і послідовно збільшуються на одиницю для кожного наступного біта.

Похідні одиниці від байта – кілобайт (210 байт) – Кбайт; мегабайт (220) байт) – Мбайт; гігабайт (230 байт) – Гбайт; терабайт (240байт) – Тбайт і петабайт (250 6aйт) – Пбайт.

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

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

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

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

У сучасних комп’ютерах застосовують дві форми подання чисел: з фіксованою точ­кою (комою) і з плаваючою точкою (комою). Ці форми, крім того, називають відповідно природною і напівлогарифмічною.

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

Для числа зі знаком крайній розряд ліворуч потрапляє під знак числа. У цьому роз­ряді записується нуль для додатних чисел і одиниця – для від’ємних. Числа без зна­ка займають усі розряди числа, тобто числа можуть бути тільки додатними. Нумерація розрядів числа зазвичай ведеться справа наліво.

У комп’ютерах числа з фіксованою точкою мають три основні формати – один байт (півсло­во), 16-розрядне слово (короткий формат) і
32-розрядне подвійне слово (довгий формат).

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




Рисунок 4.6 – Подання числа з фіксованою точкою довжиною в

півслово: а) зі знаком; б) без знака


Слід зазначити, що інтерпретацію числа з фіксованою точкою, як і числа зі знаком чи без знака, має виконувати програма оброблення цих чисел. Так, число 011100112 = 7316 буде мати десяткове значення 11510 і як число зі знаком, і як число без знака. Однак число 111011012 = ED16 буде мати десяткове значення мінус 10910 як число зі знаком і мінус 23710 – як число без знака.

Діапазон зміни чисел з фіксованою точкою зі знаком X становить:

- 2n-1X2n-1-1, а чисел без знака: 0X2n-1, де п – розрядність числа.

Так, для п = 8 діапазон зміни чисел зі знаком – від -12810 до +12710, а чисел без знака - від 010 до 25510.

Для подання чисел, що не вкладаються в діапазон подвійного слова, у сучасних комп’ютерах можна використовувати два варіанти:

  • уведення й оброблення чисел довільної довжини (наприклад, 8 чи 10 байт);

  • використання масштабних коефіцієнтів.

За обома варіантами час виконання операцій над числами істотно збільшується (за першим варіантом через велику довжину числа, за другим – через потребу вручну відслідковувати положення десяткової точки в числі).

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

Будь-яке число N, подане як число з плаваючою точкою, є добутком двох співмнож­ників:




де т – мантиса числа N(|m| < 1);

S – основа системи числення;

р – цілочисловий по­рядок.


Зі зміною порядку в той чи інший бік точка нібито «плаває» у зображенні числа.

Прикладом записування десяткового числа як числа з плаваючою точкою є експо­нентна форма запису, наприклад, чи .

Отже, для подання чисел із плаваючою точкою потрібно записати в комп’ютер зі своїми знаками мантису т і порядок р. І мантиса, і порядок записуються в двій­ковому вигляді, тобто зі значенням S=2. Знак числа при цьому збігається зі знаком мантиси.

Щоб спростити операції з порядками, їх зводять до дій над цілими додатними чис­лами використанням зміщеного порядку, що завжди додатний. Зміщений порядок р утвориться додаванням до порядку р числа 2n (де п – кількість бітів, що відводиться для значення порядку числа). Наприклад, для n-1 рт = р + 64 порядок набуватиме значення від 0 (якщо р = - 64) до 127 (якщо р = 63). У цьому разі, якщо р = -15, зміще­ний порядок = -15 + 64 = 49.

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

Тому з урахуванням різних вимог, пропонованих до точності розв’язання задач, у комп’ютерах зазвичай використовують кілька форматів. У комп’ютерах для подання значень із плаваючою точкою використовується формат IEEE (Institute of Electrical and Electronics Engineers – Інститут інженерів з електротехніки й електроніки), що визначає три формати подання чисел: звичайний, подвійної точності і довгий.

Звичайний формат займає подвійне слово (32 біт), що складається: з біта зна­ка, 7-бітового двійкового порядку і 24-бітової мантиси, що подає число в діапазоні 1,0 ... 2,0. Оскільки старший біт мантиси завжди дорівнює одиниці, він не зберігається в пам’яті. Це подання дає сім значущих цифр і діапазон значень приб­лизно 3,4 ∙ 10-38... 3,4 ∙ 10+38.

Формат подвійної точності займає подвійне слово (64 біт). Цей формат аналогіч­ний короткому формату, за винятком того, що порядок займає 11 біт, а мантиса – 52 біт (плюс неявний старший одиничний біт). Це подання містить 15 значущих цифр і діа­пазон значень чисел – близько 1,7 ∙ 10-308... 1,7 ∙ 10308.

Довгий формат займає 10 байт (80 біт). Його подання аналогічне поданню чисел з подвійною точністю, за винятком того, що мантиса займає 68 біт. Кількість значущих цифр для цього формату – 19, а діапазон значень – близько ... .

Третя форма подання чисел у комп’ютерах – це двійково-десяткова форма. У цій формі кожна цифра десяткового числа зберігається в чотирьох бітах, тобто дві цифри на один байт. Цифри від 0 до 9 виражені двійковими кодами від 0000 до 1001. Двійкові значення 1100 і 1101 використовують відповідно для знаків «+» і «-». Положення де­сяткової точки в цьому випадку фіксується і відслідковується програмними засобами. Наприклад: -14210=1101 0001 0100 00102-10

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

Для спрощення арифметичних операцій числа в комп’ютері подаються спеціальни­ми кодами – прямим, оберненим і додатковим.

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

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

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

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

Як відомо, комп’ютери можуть обробляти тільки ін­формацію, подану в числовій формі. Під час зчитування до­кументів, текстів програм та інших матеріалів введені букви кодуються відповідними чис­лами, а у разі виведення їх для читання людиною (на монітор, принтер і т. ін.) за кожним чис­лом будується зображення символу. Відповід­ність між набором символів і їх кодів називають кодуванням символів (symbolic coding).

Зазвичай код символу зберігається в одному байті. Код символу розглядається як число без знака і, отже, може набувати значень від 0 до 255. Такі кодування назива­ють однобайтовими; вони дозволяють використовувати до 256 різних символів. Тепер дедалі більшого поширення набуло двобайтове кодування Unicode, за якого коди сим­волів можуть набувати значень від 1 до 65535. У цьому кодуванні є номери для майже всіх застосовуваних символів (букв та ієрогліфів різних мов, математичних, декоратив­них символів тощо).

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

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


КОНТРОЛЬНІ ЗАПИТАННЯ ТА ЗАВДАННЯ


  1. Наведіть властивості нескінченної множини, яку утворюють раціональні числа.

  2. Які існують способи вираження функцій?

  3. У чому відмінність аналогових сигналів від дискретних?

  4. Яким чином аналогові сигнали перетворюють у дискретні?

  5. Що таке система числення?

  6. Наведіть приклади позиційних та непозиційних систем числення.

  7. Перетворіть десяткове число 14410 у двійкове.

  8. Перетворіть десяткове число 22110 у двійкове.

  9. Перетворіть десяткове число 51210 у двійкове.

  10. Перетворіть дробове десяткове число 123,4310 у двійкове.

  11. Перетворіть дробове десяткове число 101.2510 у двійкове.

  12. Перетворіть вісімкове число 448 у десяткове.

  13. Перетворіть вісімкове число 998 у двійкове.

  14. Перетворіть вісімкове число 1458 у двійкове.

  15. Перетворіть вісімкове число 2678 у шістнадцяткове.

  16. Перетворіть вісімкове число 3418 ушістнадцяткове.

  17. Перетворіть десяткове число 29910 у шістнадцяткове.

  18. Перетворіть десяткове число 17210 у шістнадцяткове.

  19. Перетворіть десяткове число 23610 у вісімкове.

  20. Перетворіть десяткове число 19610 у вісімкове.

  21. Перетворіть шістнадцяткове число 2F16 у десяткове.

  22. Перетвріть шістнадцяткове число 6B316 у десяткове.

  23. Перетворіть шістнадцяткове число AC16 у вісімкове.

  24. Перетворіть шістнадцяткове число D916 у двійкове.

  25. Перетворіть шістнадцяткове число F916 у двійкове.

  26. Перетворіть двійкове число 101110012 у десяткове.

  27. Перетворіть двійкове число 1111000012 у десяткове.

  28. Перетворіть двійкове число 1110012 у шістнадцяткове.

  29. Перетворіть двійкове число 1010112 у шістнадцяткове.

  30. Перетворіть двійкове число 1001001112 у вісімкове.

  31. Перетворіть двійкове число 1010001012 у вісімкове

  32. Перетворіть двійково-десяткове число 111011110,10012-10 у десяткове.

  33. Перетворіть двійково-десяткове число 110010100,11012-10 у десяткове.

  34. Перетворіть десяткове число 23410 у двійково-десяткове.

  35. Перетворіть десяткове число 16810 у двійково-десяткове.

  36. Перетворіть десяткове число 31710 у двійково-десяткове.

  37. Наведіть правила переведення правильного дробу з однієї системи в іншу.

  38. Яким чином здійснюється переведення цілого числа з десяткової системи числення в систему з основою S?

  39. Яким чином в сучасних комп’ютерах здійснюється подавання чисел з плаваючою точкою?

  40. Які існують формати подання чисел у компютері?

  41. Для чого здійснюється кодування символів у комп’ютері?

  42. Яким чином здійснюються арифметичні операції в системах числення з основою S?



5 ЛОГІЧНІ ОСНОВИ ЕОМ


5.1 Основи булевої алгебри


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

Сукупність значень логічних змінних х1, х2 ... хn називається набором змінних. Набір логічних змінних зручно відображати у вигляді n розрядного двійкового числа, кожний розряд якого дорівнює значенню однієї із змінних. Неважко помітити, що кількість можливих наборів в n двійкових розрядах рівна 2n.

Логічною функцією від набору логічних змінних (logical values)(аргументів) f(х1, х2 ... хn ) називається функція, яка може приймати також тільки два значення: істина (true) або хибність (false). Область визначення логічної функції скінченна і залежить від числа можливих наборів аргументів. Будь-яка логічна функція може бути задана за допомогою таблиці істинності, в лівій частині якої записуються можливі набори аргументів, а в правій – відповідні їм значення функції.

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

Загальне число логічних функцій n змінних визначається за формулою . Таким чином існує 4 логічних функції однієї логічної змінної (таблиця 5.1). Дві з цих функцій є константами: f0 (x)=0, f3 (x)=1.

Функція f2 (x) називається запереченням змінної або інверсією і позначається як f2 (x) = . Функція f1 (x) повторює значення змінної, тобто f1 (x) = x.


Таблиця 5.1


x

f0(x)

f1(x)

f2(x)

f3(x)

0

0

0

1

1

1

0

1

0

1
Число логічних функцій двох змінних рівно 16 (табл. 5.2). Із них 6 функцій є виродженими:

f0 (x1, x2) = 0; f10 (x1, x2) = ;

f3 (x1, x2) = x1; f12 (x1, x2) = ;

f5 (x1, x2) = x2; f15 (x1, x2) = 1.


Таблиця 5.2 – Логічні функції двух змінних

Змінні та їх стани

Назва функції

Вираження функції через елементарні логічні операції

Позначення операції

x1

0

0

1

1

x2

0

1

0

1

f0(x1,x2)

0

0

0

0

-

0

-

f1(x1,x2)

0

0

0

1

-

x1 . x2

-

f2(x1,x2)

0

0

1

0

Заперечення за x2

x1 .

-

f3(x1,x2)

0

0

1

1

-

x1

-

f4(x1,x2)

0

1

0

0

Заперечення за x1

. x2

-

f5(x1,x2)

0

1

0

1

-

x2

-

f6(x1,x2)

0

1

1

0

Додавання за

модулем 2

(нерівнозначність)

x1 . . x2

x1 x2

f7(x1,x2)

0

1

1

1

-

x1 x2

-

f8(x1,x2)

1

0

0

0

Стрілка Пірса

(заперечення диз’юнкції)

= .

x1 x2

f9(x1,x2)

1

0

0

1

Еквівалентність (рівнозначність)

. x1 . x2

x1 x2

f10(x1,x2)

1

0

1

0

-



-

f11(x1,x2)

1

0

1

1

Імплікація

x1

x2 x1

f12(x1,x2)

1

1

0

0

-



-

f13(x1,x2)

1

1

0

1

Імплікація

x2

x1 x2

f14(x1,x2)

1

1

1

0

Штрих Шефера (заперечення кон’юнкції)

=

x1/ x2

f15(x1,x2)

1

1

1

1

-

1

-


Функції f1(x1, x2) і f7(x1, x2) разом з функцією інверсії складають функціонально–повну систему логічних функцій, які найбільш часто використовуються на практиці. В цій системі визначені 3 елементарні логічні операції: інверсія (заперечення), кон’юнкція (логічне множення), диз’юнкція (логічне додавання). Операція кон’юнкції (функція f1) позначається знаком , точкою або зовсім без знаку. Операція диз’юнкції (f7) позначається знаком або знаком +. На рисунку 5.1 наведені таблиці істинності цих логічних операцій.


Інверсія




Кон’юнкція




Диз’юнкція























0

1




0

0

0




0

0

0

1

0




0

1

0




0

1

1










1

0

0




1

0

1










1

1

1




1

1

1


Рисунок 5.1 – Таблиці істинності логічних операцій: інверсії, кон’юнкції та

диз’юнкції


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

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


5.2 Мінімізація логічних функцій


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

Найпоширеніший базис – це набір трьох функцій: кон’юнкції (& – І), диз’юнкції (V – АБО) та інверсії (НЕ). Функціонально повними є також системи, що складаються з двох логічних функцій: диз’юнкції (АБО) та інверсії (НЕ), або кон’юнкції (І) та інверсії (НЕ). Функціональну повноту мають системи, що склада­ються тільки з однієї логічної функції: інверсії кон’юнкції (І-НЕ) чи інверсії диз’юнк­ції (АБО-НЕ). Існують також інші функціонально повні системи логічних функцій. В алгебрі логіки визначено чимало законів, за допомогою яких можна перетворюва­ти логічні функції:


Аксіоми:

; ;

x + 0 = x; x · 1 = x;

x + 1 = 1; x · 0 = 0;

x + x = x; x · x = x;

; ;

;


Комутативний (переміщуваний) закон:

;

;


Асоціативний (сполучний) закон:

;




Ці закони ідентичні аналогічним законам звичайної алгебри.

Дистрибутивний (розподільний) закон:

;

;


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

;

;


Закон склеювання:

;

;


Правило де Моргана:

;

.

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

Проектування пристроїв комп’ютера передбачає виконання таких етапів:

  • визначення таблиці істинності функції для розв’язуваної цим пристроєм задачі;

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

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

  • подання отриманих виразів в обраному базисі;

  • побудова функціональної схеми пристрою – схеми, що показує зв’язок між різни­ми логічними елементами, позначеними умовними позначками.

У такий спосіб можна побудувати технічний пристрій, що має мінімальні апаратні витрати.


5.3 Геометричні методи мінімізації булевих функцій


Найбільш поширеним є метод, оснований на використанні карт Карно. Карти Карно являють собою графічне подання таблиць істинності булевих функцій. Структури карт Карно для функцій двох, трьох та чотирьох змінних показано на рис. 5.2 – 5.4. Вони являють собою таблиці, які містять по 2n прямокутні комірки, де n – кількість логічних змінних. Карта розмічається системою ко­ординат, яка відповідає значенням вхідних змінних. Комбінація цифр, якими позначається кожний стовпець, показує, для яких значень змінних обчислю­ється функція, що розміщується у клітинках цього стовпця. Якщо на наборі (1, ..., n) значення функції дорівнює „одиниці”, то її д.д.н.ф. містить елементар­ну кон’юнкцію х11.. хnn, яка набуває на цьому наборі значення 1. Тому ко­мірки карти Карно, що подають функцію, містять стільки 1, скільки елемен­тарних кон’юнкцій міститься в її д.д.н.ф., причому, кожній 1 відповідає одна з елементарних кон’юнкцій.

Координати рядків та стовпців у карті Карно слідують не у природному порядку зростання двійкових кодів, а у порядку 00,01,11,10. Модифікацію порядку слідування наборів зроблено для того, щоб сусідні набори (тобто набори, що відрізняються один від одного тільки цифрою будь-якого одного розряду), були сусідніми у геометричному розумінні.

Процес мінімізації полягає у формуванні прямокутників, які містять по 2k комірки, що заповнені одиницями (k – ціле число). У прямокутники поєдну­ються сусідні комірки, що відповідають "сусіднім" елементарним кон’юнкціям. Сукупність прямокутників, що покривають усі „одиниці”, називається покриттям. Од­на і та сама комірка може бути покритою двома чи кількома прямокутниками. Можна зробити такі висновки.

1. Формула, яку отримано в результаті мінімізації булевої функції за до­помогою карт Карно, містить стільки елементарних кон’юнкцій, скільки прямокутників є у покритті.

2. Чим більше комірок у прямокутнику, тем менше змінних у відповідній їй елементарній кон’юнкції.

На рис. 5.5, а прямокутнику, який містить чотири комірки, відповідає кон’юнкція двох змінних, а квадрату, що складається з однієї комірки, – кон’юнкція . Функція, що відповідає по­криттю, має вигляд:





Рисунок 5.2 – а) карта Карно для функції двох змінних; б) таблиця

істинності для функції двох змінних







Рисунок 5.3 – а) Карта Карно для функції трьох змінних; б) таблиця істинності

для функції трьох змінних




Рисунок 5.4 – Карта Карно для функції чотирьох змінних


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





Рисунок 5.5 – Покриття карт Карно


Послідовність дій при мінімізації булевих функцій за методом карт Карно.

1. Зображується таблиця для n змінних та виконується розмітка її бічних сторін.

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

3. Вибирається найкраще покриття таблиці правильними прямокутника­ми. Найкращим вважається покриття, яке утворене мінімальною кількістю прямокутників, а якщо таких варіантів кілька, то з них вибирається той, що дає максимальну сумарну площу прямокутників. Якість мінімізації оцінюється функціоналом, який називається коефіцієнтом покриття:


, (5.1)


де m – загальна кількість прямокутників;

s – сумарна площа прямокутників.

Для рис. 5.5, a k = 2/5, рис. 5.5, б k = 2/6, а для рис. 5.5, в k = 1/4. Кращим вважається те покриття, для якого значення функціоналу k буде меншим.

1   2   3   4   5   6   7   8   9

Схожі:

Р. В. Маслій алгоритмічні мови та програмування частина основи інформатики та комп’ютерної техніки iconПрограма вступних випробувань з дисципліни «Основи програмування та алгоритмічні мови»
Програма вступних випробувань з дисципліни «Основи програмування та алгоритмічні мови» містить 100 тестових теоретичних питань, 200...
Р. В. Маслій алгоритмічні мови та програмування частина основи інформатики та комп’ютерної техніки iconМетодичні вказівки до виконання лабораторних робіт із дисципліни «Основи програмування та алгоритмічні мови» для студентів спеціальності
Методичні вказівки до виконання лабораторних робіт з дисципліни «Основи програмування та алгоритмічні мови» / укладач С. М. Ващенко....
Р. В. Маслій алгоритмічні мови та програмування частина основи інформатики та комп’ютерної техніки iconОпис модуля назва модуля: Обчислювальна техніка та алгоритмічні мови, частина 3 Код модуля
Обчислювальна техніка та алгоритмічні мови. Вища математика. Теоретичні основи електротехніки, частина 1
Р. В. Маслій алгоритмічні мови та програмування частина основи інформатики та комп’ютерної техніки iconМіністерство фінансів україни буковинський державний фінансово-економічний університет
Для студентів комп’ютерних спеціальностей вивчення дисципліни «Основи програмування та алгоритмічні мови» є однією з найважливіших...
Р. В. Маслій алгоритмічні мови та програмування частина основи інформатики та комп’ютерної техніки iconАнотація навчальної дисципліни «Основи комп’ютерної інженерії»
Основна мета засвоєння курсу полягає в ознайомленні студентів спеціальності 04030201 з основними етапами конструювання сучасних інформаційних...
Р. В. Маслій алгоритмічні мови та програмування частина основи інформатики та комп’ютерної техніки iconАнотація навчальної дисципліни «Основи комп’ютерної інженерії»
Основна мета засвоєння курсу полягає в ознайомленні студентів спеціальності 04030201 з основними етапами конструювання сучасних інформаційних...
Р. В. Маслій алгоритмічні мови та програмування частина основи інформатики та комп’ютерної техніки iconАнотація навчальної дисципліни «Основи комп’ютерної інженерії»
Основна мета засвоєння курсу полягає в ознайомленні студентів спеціальності 04030201 з основними етапами конструювання сучасних інформаційних...
Р. В. Маслій алгоритмічні мови та програмування частина основи інформатики та комп’ютерної техніки iconАнотація навчальної дисципліни «Основи комп’ютерної інженерії»
Основна мета засвоєння курсу полягає в ознайомленні студентів спеціальності 04030201 з основними етапами конструювання сучасних інформаційних...
Р. В. Маслій алгоритмічні мови та програмування частина основи інформатики та комп’ютерної техніки iconОпис модуля назва модуля: Обчислювальна техніка та алгоритмічні мови, частина 2 Код модуля
Обчислювальна техніка та алгоритмічні мови, частина Вища математика, частини 1, 2
Р. В. Маслій алгоритмічні мови та програмування частина основи інформатики та комп’ютерної техніки iconПрограма Предмет: моделювання в електроніці
Курс спирається на дисципліни „Вища математика”, „Загальна фізика”, „Основи програмування та алгоритмічні мови”
Р. В. Маслій алгоритмічні мови та програмування частина основи інформатики та комп’ютерної техніки icon«Спецкурс з комп’ютерної інженерії»
Системні науки та кібернетика ” з основними етапами конструювання сучасних інформаційних систем, технологіями виготовлення комп’ютерних...
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи