Перелік літератури

План.

Лекція №7.

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

Repeat

Begin

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

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

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

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

Наприклад 1.

while I < 4 do

S:= S+ I;

I:= I +1;

end;

Наприклад 2.

S:= S+ I;

I:= I +1;

until I >= 4;

Задача 1,2,3. Знайти суму всіх натуральних чисел від 1 до N, методом вказівки повторення з передумовою, післяумовою, параметром.

Задача 4. Скласти програму знаходження факторіала числа n. n!=1*2*3*...*n

Тема: Мінімізація ФАЛ методом Квайна-Мак Класкі. Мінімізація не повністю визначених функцій.

1. Мінімізація методом Квайна-Мак Класкі.

2. Мінімізація не повністю визначених функцій.

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

Для формування простих импликант і одержання скороченої ДНФ всі конституенти минимизируемой ФАЛ п змінних записують у вигляді їхніх двійкових номерів. Останні розбивають по числу т одиниць, що втримуються в їхньому коді, на групи. Кількість одиниць т називають індексом двійкового числа. У m-ю групу ввійдуть всі номери, що мають у своєму двійковому записі рівно т одиниць.

Групи двійкових номерів з однаковим індексом рас думають у стовпець, розділяючи їхньою горизонтальною рисою в порядку зростання індексу т. Далі виконують наступні операції: попарно порівнюють двійкові номери всіх членів групи з індексом т зі членами групи, що має індекс т + 1; якщо порівнювані двійкові коди розрізняються тільки в одному розряді, у перший стовпець залишків записують код із прочерком на місці цього розряду; двійкові коди номерів, що беруть участь в операції склеювання, відрізняють умовним знаком, наприклад V- Зазначені операції повторюють для всіх груп послідовно в порядку зростання т. Всі не відзначені знаком V двійкові номери відповідають простим импликантам.

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

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

Приклад. ФАЛ заданий числовим способом:

Перейшовши до двійкових еквівалентів десяткових номерів констітуент, упорядкувавши їх у групи по числу одиниць і провівши операції порівняння й склеювання відповідно до описаного вище методикою, одержимо:

Подальший процес склеювання импликант, не відзначених знайомий диз'юнкції, неможливий. Ці імпліканти є простими, позначимо їхніми буквами А, В, З, D, Е, F. Скорочена ДНФ мінімізіруемої функції має вигляд f = A˅B˅C˅D˅E˅F. Подальше спрощення логічного вираження досягається виключенням з нього зайвих членів.

Для складання тупикових форм із простих импликант і одержання мінімальної форми використовують импликантную таблицю, що називають також таблицею покриттів. Її рядка відповідають простим импликан там, а графи - конституентам функції (членам ДЗНФ). Стовпці членів ДЗНФ, при склеюванні яких утворена дана импликанта, відзначають мітками X. Говорять, що дана импликанта покриває (поглинає) дану конституенту. Розглянутої функції відповідає імплікантная таблиця (табл. 2.7).

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

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

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

Для розглянутої функції импликанти А и D спільно покривають всі що залишилися конституенти. Таким чином, МДНФ має вигляд

Мінімальна ДНФ може бути знайдена по импликантній таблиці з використанням алгебраїчного способу. Для кожної конституенти, функції, що поглинається не ядром, записують диз'юнкцію позначень тих импликант, які її покривають. Становлять добуток цих диз'юнкцій, що називають функцією покриттів. Добуток розкривають за правилами алгебри логіки й записують у диз'юнктивній нормальній формі. Кожний член цієї форми відповідає ненадлишковому набору импликант, що покривають всі конституенты заданої функції. Диз'юнкції импликант, що відповідають кожному набору разом з ядром функції, дають тупикові форми функції.

Відповідно до табл. 2^можна написати

.

Виїшло чотири тупикових ДНФ, з яких одна мінімальна, що складається з импликант А, О и істотної импликанти F,

При застосуванні методу Квайна-Мак-Класки для одержання мінімальної кон’юнктивної нормальної форми (МКНФ) ФАЛ є наступні особливості: вихідною формою ФАЛ є КЗНФ; пари членів, що склеюються, мають вигляд a\Jх і а\/;; члени КЗНФ являють собою диз'юнкції змінних, які мають інверсні значення в порівнянні з їхніми значеннями в наборах, на яких функція дорівнює 0.

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

Скорочена КНФ

Перехід до мінімальної форми здійснюється з використанням импликантной таблиці (табл. 2.8).

Всі стовпці таблиці перекриваються істотними імпликантами, отже, член x._t у х~₃ зайвий і МКНФ функції

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

На карті Карно (мал. 2.9) умовні набори змінних відзначені знайомий —. При мінімізації функції варто задавати такі значення умовних наборів змінних, при яких клітки зі значенням 1 охоплюються мінімальним числом областей з максимальним числом кліток у кожній з них. Для розглянутої функції таке довизначення функції може бути здійснено різними способами.. Один з них показаний на мал. 2.9. При цьому виходять дві області із чотирма клітками. Тупикова НДФ / = Xj₂ V х._гх₃. Аналогічно при інших способах довизначення можуть бути отримані, наприклад, тупикові НДФ:

Всі образующиеся тупикові НДФ рівноцінні по числу вхідних у них змінних, тому кожна з них може бути прийнята в якості МДНФ. При великому числі змінних для мінімізації не повністю певних функцій застосовують метод істотних змінних. Метод істотних змінних
заснований на зіставленні дозволених наборів значень
змінних, на яких ФАЛ приймає значення 1, із забороненими наборами, на яких вона приймає значення 0. Якщо хо-
тя б на одному наборі змінних
виконується нерівність

змінна х_t є істотною. Алгоритм мінімізації містить п'ять кроків.

1. Побудова таблиці существенних змінних. Таблиця містить п рядків по числу дозволених

Наборів функції, m стовпців по

числу заборонених наборів і стовбець залишків, у якій записуються істотні змінні за результатами порівняння дозволеного набору рядка із забороненим набором стовпця. Для приклада побудована таблиця істотних змінних ФАЛ семи змінних (табл. 2.9). Функція має три дозволених (8; 64; 113) і три заборонених (0; 112; 120) набори. Інші набори невикористовувані.

2. Заповнення таблиці істотних змінних. Попарно порівнюють дозволений набір рядка з кожним забороненим набором стовпця. У клітку таблиці заносять ті змінні, по яких розглянута пара наборів розрізняється між собою, і з тими значеннями, які змінні мають у дозволеному наборі.

3. Обробка таблиці істотних змінних. Її проводять построчно в наступній послідовності:

визначають клітки утримуючі по однієї змінній. Ці змінні обводять кружком і записують у стовпець залишків у вигляді кон’юнкції. Всі члени рядка, які із тримають змінні, записані в стовпець залишків, відзначають знаком V і виключають із розгляду. Такими змінними в прикладі є х₄, х₁ і х₇

серед членів рядка, не відзначених знаком ˅, виділяють змінну, що зустрічається найбільше часто. Її обводять кружком і приписують зі знаком кон’юнкції в стовпець залишків до наявним там змінного. Члени рядка, що містять дану змінну, відзначають знаком V і виключають із розгляду. Цей процес продовжують до тих нір, поки в рядку залишаться не відзначеними тільки клітини, що містять неповторюване змінне або змінне, повторюване однакове число раз;

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

змінного.

У розглянутому прикладі після виділення одиночних змінних у першому рядку залишається одна не відзначена клітка з неповторюваними змінними а,л'₂х₃, у другому рядку — дві клітки, у яких дві змінні

х₂ях₃ повторюються рівне число раз, у третину їй рядку всі клітки виявляються відзначеними. Змінні першої х_г, х₂, х₉ і другий л₂, х₃ рядків зі знаком диз'юнкції записують у стовпець залишків.

4 Побудова таблиці покриттів істотних змінних. Таблиця покриттів (табл. 2.10) аналогічна импликантной таблиці (див. табл. 2.7). Її стовпці відповідають дозволеним наборам, а рядка — кон’юнкциям существенних змінних, отриманих для кожного рядка таблиці істотних змінних. Якщо одним зі членів кон’юнкции в стовпці залишків є диз'юнкція змінних, здійснюють перетворення за розподільним законом. Для першого рядка одержимо кон’юнкции х_х x_t. х_гх₄, х₃, х₄, для другої: х_хх₂, x_tx₃.

5. Обробка таблиці покриттів. Її проводять, як і обробку импликантной таблиці: проставляють мітки А" у тих стовпцях таблиці, набори яких покриваються даною комбінацією істотних змінних, тобто ця комбінація утворена в результаті порівняння відповідного дозволеного набору із забороненими.

Комбінації х_хх₂ і х_гх₃ утворені в результаті порівняння дозволеного набору 64 із забороненими, тому на перетинаннях стовпця, що відповідає набору 64, і рядків, відзначених цими комбінаціями змінних, ставлять мітки. Ядром функції є змінна х?. Функція покриття іншої частини таблиці

.

Тупикові НДФ рівноцінні, вибравши кожну з них, наприклад АС, з урахуванням ядра одержимо МДНФ:

-

ФАЛ мінімізують окремо. Потім становлять формулу багатовихідна функції. де z1 — символ відповідного виходу. Символ z1 не є змінною ФАЛ. Однак якщо прийняти умову, що символ z₁ завжди повинен залишатися наприкінці, реалізації системи функцій і до нього не застосовувати операцію інверсії, з ним можна формально оперувати, як зі змінної ФАЛ. У цьому випадку вираження багатовихідгої функції перетвориться з використанням переміщувального, сполучного й розподільного законів алгебри логіки. Всі перетворення в межах багатовихідгої функції зводяться до послідовного винесення за дужки загальних частин різних її складових. Наприклад, Az_t V Az₂ = А (рр \J \/z₂). Запис A (z_y \J z₂) означає, що вираження А належить функції f1,мающий вихід z₁, і функції f₂, мающий вихід z₂.

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

Становимо формулу багатовихідгої функції

Цієї функції відповідає схема, наведена на рис 2.11 а

Основна

1.	Сапожников В.В. и др. Теория дискретных устройств железнодорожной автоматики и телемеханики. М.: 2001.
2.	Сапожников В.В. и др. Дискретные устройства железнодорожной автоматики, телемеханики и связи. -М.: Транспорт, 1988.-256с. Обесп. 1/3.
	Додаткова
2.	Голсуорт В.В. Проектирование цифровых логических устройств.-М.:Машиностроение, 1985.- 226 с. Обесп. 1 екз.
3.	Дискретные устройства автоматизированных систем управления /Под ред. Г.Н.Тимонькина.-Харьков, 1990.-511 с. Обесп.1 екз.
4.	Методичні вказівки Обесп.1/1

Дата добавления: 2014-01-04