0 * 1 * * 01 * 0 * 1 * * 01 * ** 11 ** 11 |
Як видно з таблиць, при отриманні матриці другого рангу перший і сьомий набори третього рангу не склеїлися ні з якими іншими наборами. Їх необхідно занести в кінцеву матрицю простих импликант. У матриці ж другого рангу ми бачимо, що деякі набори однакові. Їх необхідно викреслити, так як диз'юнкція однакових наборів дорівнює цій же диз'юнкції (це випливає з закону повторення) Прості імпліканти | 1 2 3 4 5 | 0 * 1 * * 01 * ** 11 00 * 0 01 * 1 |
Перенісши всі виділені рядки в кінцевий масив, отримаємо матрицю СДНФ. Алгебраїчна запис СДНФ буде виглядати наступним чином: F (X 1 X 2 X 3 X 4) = X 1 X 3 VX 2 X 3 VX 3 X 4 VX 1 X 2 X 4 VX 1 X 2 X 4. Ця ж функція у нашому випадку є і мінімальної ДНФ. Метод Квайна-Маккласкі
В основу даного методу також покладено закон неповного склеювання. Тільки на відміну від методу Квайна тут виробляється набагато менше порівнянь, тому що, розбивши вихідну матрицю на кілька груп, ми порівнюємо тільки ті набори, які відрізняються індексом на 1 або місцем розташування міток. Розподілимо імпліканти ДСНФ по індексах. ДСНФ | Індекс i | 1 2 3 4 5 6 7 8 9 | 0000 0010 0011 0101 0110 0111 1010 1011 1111 | 0 1 2 2 2 3 2 3 4 |
Розподілені набори 4-го рангу | i = 0 | i = 1 | i = 2 | i = 3 | i = 4 | 0000 | 0010 | 0011 0101 0110 1010 | 0111 1011 | 1111 |
Порівнюючи сусідні групи і розподіляючи отримані набори по положенню символу '*' отримаємо: Набори 3-го рангу | 1 2 3 4 5 6 7 8 9 10 11 | 00 * 0 001 * 0 * 10 * 010 0 * 11 * 011 01 * 1 011 * * 111 101 * 1 * 11 |
Розподілені набори 3-го рангу | 1 | 2 | 3 | 4 | * 010 * 011 * 111 | 0 * 10 0 * 11 1 * 11 | 00 * 0 01 * 1 | 001 * 011 * 101 * |
Розподілені набори 2-го рангу | 12 | 14 | 24 | ** 11 | * 01 * | 0 * 1 * |
Примітка. У всіх вище наведених таблицях прості імпліканти відзначені жирним шрифтом з підкресленням. Аналізуючи, бачимо, що СДНФ прийме наступний вигляд: Прості імпліканти | 1 2 3 4 5 | 0 * 1 * * 01 * ** 11 00 * 0 01 * 1 |
Або в алгебраїчній формі: F (X 1 X 2 X 3 X 4) = X 1 X 3 VX 2 X 3 VX 3 X 4 VX 1 X 2 X 4 VX 1 X 2 X 4. Метод карт Карно.
Метод карт Карно - це один з графічних методів мінімізації функції. Ці методи засновані на використанні особливості зорового сприйняття, так як з його допомогою можна практично миттєво розпізнати ті чи інші прості конфігурації. Перевагами методу карт Карно над іншими методами є: А) простота відшукання склеюючих компонент; Б) простота виконання самого склеювання; В) знаходження всіх мінімальних форм функції. Побудуємо таблицю методу карт Карно.
| X 1 X 2 | X 1 X 2 | X 1 X 2 | X 1 X 2 | X 3 X 4 | ■ |
|
|
| X 3 X 4 |
| ■ |
|
| X 3 X 4 | ■ | ■ | ■ | ■ | X 3 X 4 | ■ | ■ |
| ■ |
Тепер накриємо сукупність всіх квадратів з мітками мінімальною кількістю правильних прямокутників. Таких прямокутників в нашому випадку буде 5: три четирехклеточних і два двухклеточного. Цим прямокутникам відповідають такі прості імпліканти: для першого - X 3 X 4; для другого - X 1 X 3; для третього - X 2 X 3; для четвертого - X 1 X 2 X 4; для п'ятого - X 1 X 2 X 4; Мінімальна ДНФ буде виглядати так: F (X 1 X 2 X 3 X 4) = X 1 X 3 VX 2 X 3 VX 3 X 4 VX 1 X 2 X 4 VX 1 X 2 X 4. Порівнюючи метод карт Карно з іншими методами мінімізації функції можна зробити висновок, що перший найбільше підходить для ручного виконання. Час ручної роботи значно скорочується (за рахунок наочного подання склеюючих импликант). Програмна реалізація даного методу має свої складнощі. Так, дуже складно буде реалізувати оптимальний вибір правильних прямокутників, особливо для великого числа аргументів. 1.3.5 Метод невизначених коефіцієнтів Цей метод може бути використаний для будь-якого числа аргументів. Але так як цей метод досить громіздкий, то застосовується тільки в тих випадках, коли число аргументів не більше 5-6. У методі невизначених коефіцієнтів використовуються закони універсального і нульового множин і закони повторення. На початку всі коефіцієнти невизначені (звідси і назва методу). Побудуємо матрицю невизначених коефіцієнтів для чотирьох аргументів. У цьому випадку ми будемо мати систему з 16-ти рівнянь. Система наведена на наступній сторінці. Прирівняємо всі коефіцієнти 0 в тих рядках, яким відповідає 0 у векторі стовпці. Потім прирівняємо 0 відповідає коефіцієнти в інших рядках. Після цих перетворень система прийме наступний вигляд:  V  = 1  V  V  V V  V  V  = 1 V V  V V  V  V  = 1  V  = 1 V  V V  = 1 V V V V  V  V  = 1 V  V V  = 1 V V V  V V  = 1 V V  V  = 1 Тепер у кожному рядку необхідно вибрати коефіцієнт мінімального рангу і прирівняти його одиниці, а інші коефіцієнти - 0. Після цього викреслюємо однакові рядки, залишаючи при цьому одну з них (ті рядки, в яких усі коефіцієнти рівні 0, також викреслюються). = 1 = 1 = 1 = 1 = 1 Запишемо тепер кон'юнкції, відповідну коефіцієнтам, рівним одиницям. Ми отримаємо мінімальну ДНФ. F (X 1 X 2 X 3 X 4) = X 1 X 3 VX 2 X 3 VX 3 X 4 VX 1 X 2 X 4 VX 1 X 2 X 4. Отже, ми отримали кількома способами мінімальну ДНФ, У всіх випадках вона вийшла однаковою, тобто будь-який з описаних методів може бути використаний для мінімізації функції. Однак ці методи істотно відрізняються один від одного як за принципом знаходження МДНФ, так і за часом виконання. Для ручних розрахунків дуже зручний метод карт Карно. Він наочний, не вимагає рутинних операцій, а вибрати оптимальне розташування правильних прямокутників не становить великої праці. У той час як машинна реалізація даного методу ускладнюється необхідністю знаходження оптимального розташування прямокутників. Природно застосування інших методів (метод Квайна, метод Квайна-Маккласкі, метод невизначених коефіцієнтів) для ручних розрахунків недоцільно. Вони більше підійдуть для машинної реалізації, оскільки містять велику кількість повторюваних простих операцій. Завдання 2. 2.1 Схема алгоритму для методу Квайна Початок. Введіть матрицю ДСНФ вихідної функції. Перевірити на склеиваемость i-ю (i = 1, m -1: де m - кількість рядків у ДСНФ) і j-у (j = i +1, m) рядки. Якщо рядки склеюються, то перейти до пункту 6, в іншому випадку перейти до пункту 5. Формувати масив простих импликант, попередньо позначивши символом '*' ту змінну, по якій дані рядка склеюються. Перейти до пункту 2. Рядок, який не склеїлося з жодною іншою рядком записати в кінцевий масив. Перейти до пункту 2. Висновок отриманої матриці. Кінець.
Логічна схема алгоритму в нотації Ляпунова 1 січня V H V 1 Z 1 V 2 ¯ V 3 V 4 V K V H - початок. V 1 - ввести матрицю ДСНФ вихідної функції. V 2 - формувати масив простих импликант, попередньо позначивши символом '*' ту змінну, по якій дані рядка склеюються. V 3 - рядок, який не склеїлося з жодною іншою рядком записати в кінцевий масив. V 4 - висновок отриманої матриці. Z 1 - якщо рядки склеюються, то перейти до пункту 3, в іншому випадку перейти до пункту 5. V K - кінець. Граф-схема алгоритму.  
         
Опис машинних процедур Procedure Stuck (S1, S2: Diz; IndexS1, IndexS2: byte); Дана процедура склеює два, переданих їй диз'юнктів. Диз'юнктів задаються в параметрах S 1, S 2. Індекси IndexS1, IndexS2 визначають індекси цих диз'юнктів в головному робочому масиві. Алгоритм роботи процедури наступний: спочатку шукається кількість склеюючих символів. Якщо їх 0, то вони однакові, і в кінцевий масив записується тільки один з них. Якщо 1, то визначається місце розташування символу, за яким Дані дві диз'юнкції склеюються, і замінюємо цей символ на '*'. Всі отримані результати заносяться в масив REZ. Всі інші функції і процедури програми пов'язані з діями над масивами, тобто не мають безпосереднього відношення до даного методу знаходження МДНФ. Тому немає сенсу їх описувати. 2.2 Схема алгоритму для методу Петрика Початок. Введіть матрицю ДСНФ вихідної функції і прості імпліканти, отримані в методі Квайна. Скласти таблицю міток. По таблиці міток побудувати кон'юнкцію диз'юнкцій, кожна з яких є сукупність тих импликант, які в даному стовпці мають позначки. Провести розкриття дужок в отриманому виразі з урахуванням законів поглинання. Вибрати одну з отриманих кон'юнкція і представити її як сукупність відповідних простих импликант. Якщо обрана комбінація не є мінімальною, то перейти до пункту 6, в іншому випадку перейти до пункту 8. Формувати МДНФ. Висновок отриманої матриці. Кінець.
Логічна схема алгоритму в нотації Ляпунова. 1 січня V H V 1 V 2 V 3 V 4 ¯ V 5 Z 1 V 6 V 7 V K V H - початок. V 1 - ввести матрицю ДСНФ вихідної функції і прості імпліканти, отримані в методі Квайна. V 2 - скласти таблицю міток. V 3 - за таблицею міток побудувати кон'юнкцію диз'юнкцій, кожна з яких є сукупність тих импликант, які в даному стовпці мають позначки. V 4 - зробити розкриття дужок в отриманому виразі з урахуванням законів поглинання. V 5 - вибрати одну з отриманих кон'юнкція і представити її як сукупність відповідних простих импликант. Z 1 - якщо обрана комбінація не є мінімальною, то перейти до пункту 6, в іншому випадку перейти до пункту 8. V 6 - формувати МДНФ. V 7 - висновок отриманої матриці. V K - кінець. Граф-схема алгоритму.
  
Опис машинних процедур Procedure FormMatrix; Дана процедура формує матрицю міток шляхом попарного аналізу диз'юнктів з ДСНФ і матриці простих импликант. Якщо стравненію пройшло успішно, то відповідному елементу матриці міток присвоюється значення 1, у противному випадку - значення 0. Function Pokritie (var S: string16): boolean; Ця функція перевіряє, чи є дана комбінація простих импликант повної, тобто накриває вона все диз'юнктів матриці ДСНФ. Це порівняння відбувається наступним чином: вводиться новий масив - масив соостветсвія стовпцях. Кожному елементу нового масиву спочатку присвоюється значення 0. Далі, пробігаючи всі задані рядки матриці, визначаємо в яких стовпцях коштує 1 і в новому масиві ставимо на відповідне місце 1. Таким чином, якщо у векторі є нулі, значить ця комбінація диз'юнктів не накриває повністю всі стовпці матриці. У цьому випадку функція повертає значніє False, інакше функція повертає значення True. Завдання 3. Синтез схеми логічного пристрою. 1. Подання МДНФ в базисі Буля. У базисі Буля використовується 3 логічні схеми: НЕ, АБО, І. Ось їх графічне зображення:    X1 X1
 __
 XX X1VX2 X1 * X2
X2 X2
Для апаратної реалізації мінімальної ДНФ нам потрібно 3 ІМС серії К155: одна ІМС К155ЛН1 (елементи НЕ), одна ІМС К155ЛЛ1 (елементи АБО) і одна ІМС К155ЛІ1 (елементи І). Але в них все елементи не використовуються. Так в ІМС К155ЛН1 не використовуються 3 елементи НЕ Це можна використовувати в тому випадку, коли один з елементів вийде з ладу і його нічим буде замінити. Треба буде тільки перепаяти контакти на незадіяний елемент. Всього в базисі Буля використовується 11 логічних елементів. 2. Подання МДНФ в базисі Шеффера. Для того, щоб реалізувати мінімальну ДНФ в базисі Шеффера, необхідно перевести базис Буля в базис Шеффера, в якому використовується тільки один логічний елемент: І-НЕ. Формули перекладу з базису Буля в базис Шеффера записуються наступним чином:   
НЕ: X = X * X АБО: X 1 VX 2 = X 1 * X 1 * X 2 * X 2
І: X 1 * X 2 = X 1 * X 2 * X 1 * X 2 Мінімальна ДНФ виглядає так:  f (X 1, X 2, X 3, X 4) = X 3 X 4 VX 2 X 3 VX 1 X 3 VX 1 X 2 X 4 VX 1 X 2 X 4;
Переведемо її в базис Шеффера за допомогою зазначених вище формул.   
 Позначимо A = X 3 X 4 VX 2 X 3 VX 1 X 3 = X 3 · (X 4 VX 2 VX 1) = X 3 · X 4 · X 4 · X 2 · X 1 =
= X 3 · X 4 · X 4 · X 2 · X 1 · X 2 · X 1.   
   B = X 1 X 2 X 4 VX 1 X 2 X 4 = X 1 · (X 2 · X 4 VX 2 · X 4) = X 1 · X 1 · X 2 · X 2 · X 4 · X 4 · X 2 · X 4.
Остаточно отримаємо Y = A · B. Звідси видно, що для реалізації мінімальної ДНФ в базисі Шеффера потрібно 12 елементів І-НЕ. Відповідно для апаратної реалізації нам потрібно 3 інтегральні мікросхеми К155ЛА3. 3. Подання МДНФ в базисі Пірса. Для того, щоб реалізувати мінімальну ДНФ в базисі Пірса, необхідно як і в попередньому пункті перевести МДНФ з базису Буля в базис Пірса, в якому використовується тільки один елемент АБО-НЕ. Формули перекладу записуються наступним чином:
НЕ: X = XVX АБО: X 1 VX 2 = X 1 V X 2 V X 1 V X 2 
І: X 1 * X 2 = X 1 V X 1 V X 2 V X 2 Переведемо МДНФ в базис Пірса. Введемо позначення:    
A = X 3 X 4 VX 2 X 3 VX 1 X 3 = X 3 · X 4 · X 2 · X 3 · X 1 · X 3 = X 3 VX 4 VX 2 VX 3 VX 1 VX 3.
B = X 1 · (X 2 X 4 VX 2 X 4) = X 1 · (X 2 · X 4 · X 2 · X 4) = X 1 · X 2 VX 4 VX 2 VX 4 =  
= X 1 VX 2 VX 4 VX 2 VX 4. Y = AV B. Щоб реалізувати кожну окрему логічну суму нам потрібно 2 елемента АБО-НЕ, тобто для 4-х логічних сум, які становлять функцію, нам потрібно 6 логічних елементів. Усього на реалізацію МДНФ в базисі Пірса знадобиться 16 логічних елементів ИЛИ-НЕ, а для апаратної реалізації 4 ІМС серії К155 (К155ЛЕ1). Отже, можна підбити підсумки: на реалізацію МДНФ в різних базисах потрібна різна кількість логічних елементів, але доцільно вибрати той базис, який буде більш універсальним і на реалізацію якого буде потрібно менше кількість логічних елементів. У нашому випадку це базис Буля (11 логічних елементів). Висновок У цій роботі були розглянуті методи мінімізації ФАЛ від 4 х змінних: методи Квайна, Квайна-Маккласкі, карт Карно, невизначених коефіцієнтів, а також розглянуто пряме алгебраїчне перетворення. Для двох із них (методу невизначених коефіцієнтів і методу Квайна) були розроблені програми. При цьому особливо важко було реалізувати процедури, що відповідають за логічні операції. Причому проглядалася наступна закономірність: чим легше був метод для ручного виконання, тим важче було написати для нього програму. Взяти хоча б метод карт Карно. З його допомогою вручну дуже легко отримати МДНФ, скласти таблицю і вибравши правильні прямокутники. Але якщо взятися за реалізацію цього методу програмно, то відразу виникають труднощі, особливо при написанні процедури вибору правильних прямокутників. Це буде дуже складна логічна процедура, здається, що все просто. Інакше виглядає метод невизначених коефіцієнтів. Для машинної реалізації він підходить більше за інших, оскільки в ньому ми маємо справу з масивами, для роботи з якими не треба особливо складної логіки. І звичайно ручне виконання цього методу вкрай нераціонально, оскільки доводиться вирішувати систему з 16-ти рівнянь. Це для чотирьох змінних, а для п'яти це буде 32 рівняння. Такий метод для ручного виконання не підходить. У задачі курсової роботи також входив синтез логічної схеми. Отримана схема МДНФ була реалізована в трьох базисах: Буля, Пірса, Шеффера. Аналіз та оцінка апаратурних витрат також приведена в даній записці. Список літератури Гаджієв А.А. Методичні вказівки до виконання курсової роботи з дисципліни "Дискретна математика" для студентів спеціальності 22.01 (ВМКСіС). Махачкала, 1998 р. Гаджієв А.А. Методичні вказівки до виконання лабораторного практикуму з дисципліни "Дискретна математика" (частина 2. Математична логіка). Махачкала, 1998 р.
Додаток Програма для методу Квайна Uses Crt; Const R = 4; SR = 16; Type Diz = string [R]; Var S: array [1 .. SR * 2] of Diz; Rez: array [1 .. SR * 2] of Diz; Flag: array [1 .. SR * 2] of byte; Y: array [1 .. SR] of byte; IndexS: byte; IndexRez: byte; i, j, k: byte; FData: Text; FRez: Text; FDSNF: file of Diz; FSImp: file of Diz; {Функція формування диз'юнктів} Function MakeDiz (Number: byte): Diz; Var i: byte; S: Diz; C: char; Begin S :=''; for i: = 0 to R-1 do begin C: = chr (((Number shr i) and $ 01) + 48); Insert (C, S, 1); end; MakeDiz: = S; End; {Функція склеювання} Procedure Stuck (S1, S2: Diz; IndexS1, IndexS2: byte); Var i, k, n: byte; Begin k: = 0; {к-ть різних} for i: = 1 to R do if S1 [i] <> S2 [i] then begin k: = k +1; n: = i; end; case k of 0: begin Inc (IndexRez); Rez [IndexRez]: = S1; Flag [IndexS1]: = 1; Flag [IndexS2]: = 1; end; 1: if (S1 [n ]<>'*') and (S2 [n ]<>'*') then begin S1 [n ]:='*'; Inc (IndexRez); Rez [IndexRez]: = S1; Flag [IndexS1]: = 1; Flag [IndexS2]: = 1; end; end; End; {Функція перевірки на видалення порожнього диз'юнктів} Function Del (S: Diz): Boolean; Var i, k: byte; Begin Del: = False; k: = 0; for i: = 1 to R do if S [i ]='*' then k: = k +1; if k = R then Del: = True; End; Procedure Clear; Var i, j: byte; Begin IndexS: = 0; for i: = 1 to SR * 2 do begin Flag [i]: = 0; S [i ]:=''; end; for i: = 1 to IndexRez-1 do if Flag [i] = 0 then for j: = i +1 to IndexRez do if Rez [i] = Rez [j] then Flag [j]: = 1; for i: = 1 to IndexRez do if Flag [i] = 0 then begin Inc (IndexS); S [IndexS]: = Rez [i]; end; End; {Виведення на екран масиву Rez} Procedure PrintRezult (Step: Byte); Var i: byte; Begin WriteLn ('{---------------------------------------------- --}'); WriteLn (FRez,'{-----------------------------------------}') ; if Step = 0 then begin Write ('Вихідна ДНФ. '); Write (FRez, 'Вихідна ДНФ.'); end else begin Write ('Крок номер: ', Step: 2,'.'); Write (FRez, 'Крок номер: ', Step: 2,'.'); end; WriteLn ('Кількість диз'юнктів:', IndexS: 2); WriteLn (FRez, 'Кількість диз'юнктів:', IndexS: 2); for i: = 1 to IndexS do begin WriteLn (S [i]); WriteLn (FRez, S [i]); end; ReadKey; End; {Основна програма} Begin ClrScr; Assign (FDSNF, 'dsnf.dat'); Rewrite (FDSNF); Assign (FSImp, 'simplimp.dat'); Rewrite (FSImp); Assign (FRez, 'rezult.dat'); ReWrite (FRez); {Вважати масив Y з файлу} Assign (FData, 'func.dat'); Reset (FData); for i: = 1 to SR do Read (FData, Y [i]); Close (FData); {Отримати масив S} for i: = 1 to SR do S [i]: = MakeDiz (i-1); {Преоразовать S: залишивши тільки ті елементи, для яких Y = 1. Результату в Rez} IndexRez: = 0; for i: = 1 to SR do if Y [i] = 1 then begin Inc (IndexRez); Rez [IndexRez]: = S [i]; end; for i: = 1 to SR * 2 do S [i]: = Rez [i]; IndexS: = IndexRez; for i: = 1 to IndexS do Write (FDSNF, S [i]); PrintRezult (0); {Склеювання} for i: = 1 to R do begin IndexRez: = 0; {------------------------------------------------- -----------} for j: = 1 to SR * 2 do {підготовка масиву Flag під склеювання} Flag [j]: = 0; {------------------------------------------------- -----------} for j: = 1 to SR * 2 do {склеювання} Rez [j ]:=''; for j: = 1 to IndexS-1 do for k: = j +1 to IndexS do Stuck (S [j], S [k], j, k); {------------------------------------------------- -----------} for j: = 1 to IndexS do {копіювання несклеівшіхся компонент} if Flag [j] = 0 then begin Inc (IndexRez); Rez [IndexRez]: = S [j]; end; {------------------------------------------------- -----------} Clear; {видалення однакових диз'юнктів} {------------------------------------------------- -----------} PrintRezult (i); {висновок результату на екран} end; {Видалити все диз'юнктів виду'****'} IndexRez: = 0; for i: = 1 to IndexS do if not Del (S [i]) then begin Inc (IndexRez); Rez [IndexRez]: = S [i]; end; for i: = 1 to IndexS do Write (FSImp, S [i]); PrintRezult (R +1); Close (FSImp); Close (FDSNF); Close (FRez); End. Результати роботи програми (файл rezult. Dat). {------------------------------------------------- ---------------} Вихідна ДНФ. Кількість диз'юнктів: 9 0000 0010 0011 0101 0110 0111 1010 1011 1111 {------------------------------------------------- ---------------} Крок номер: 1. Кількість диз'юнктів: 11 00 * 0 001 * 0 * 10 * 010 0 * 11 * 011 01 * 1 011 * * 111 101 * 1 * 11 {------------------------------------------------- ---------------} Крок номер: 2. Кількість диз'юнктів: 5 0 * 1 * * 01 * ** 11 00 * 0 01 * 1 {------------------------------------------------- ---------------} Крок номер: 3. Кількість диз'юнктів: 5 0 * 1 * * 01 * ** 11 00 * 0 01 * 1 {------------------------------------------------- ---------------} Крок номер: 4. Кількість диз'юнктів: 5 0 * 1 * * 01 * ** 11 00 * 0 01 * 1 {------------------------------------------------- ---------------} Крок номер: 5. Кількість диз'юнктів: 5 0 * 1 * * 01 * ** 11 00 * 0 01 * 1 Програма для методу Петрика. Uses Crt; Type string4 = String [4]; string16 = String [16]; TImpArray = array [1 .. 16] of string4; Var DSNF: TImpArray; {ДСНФ} SimpleImp: TImpArray; {Прості імпліканти} IndexDSNF: Integer; IndexSImp: Integer; QM: array [1 .. 16, 1 .. 16] of integer; {матриця покриття} S16Min: string16; Procedure Input; Var FData: file of string4; i: integer; Begin {Введення матриці ДСНФ} Assign (FData, 'dsnf.dat'); Reset (FData); i: = 0; while not eof (FData) do begin Inc (i); Read (FData, DSNF [i]); end; IndexDSNF: = i; Close (FData); {Введення простих импликант} Assign (FData, 'simplimp.dat'); Reset (FData); i: = 0; while not eof (FData) do begin Inc (i); Read (FData, SimpleImp [i]); end; IndexSImp: = i; Close (FData); {Кінець введення} End; Function Metka (n, m: integer): boolean; Var i, S: integer; Begin Metka: = False; S: = 0; for i: = 1 to 4 do if SimpleImp [n, i ]='*' then S: = S +1 else if SimpleImp [n, i] = DSNF [m, i] then S: = S +1; if S = 4 then Metka: = True; End; Procedure FormMatrix; Var i, j: integer; Begin for i: = 1 to IndexSImp do for j: = 1 to IndexDSNF do if Metka (i, j) then QM [i, j]: = 1 else QM [i, j]: = 0; End; Procedure PrintMatrix; Var i, j: integer; Begin TextColor (LIGHTGREEN); Write (''); for i: = 1 to IndexDSNF do Write (DSNF [i]: 6); WriteLn; for i: = 1 to IndexSImp do begin TextColor (LIGHTGREEN); Write (SimpleImp [i]: 6); for j: = 1 to IndexDSNF do case QM [i, j] of 1: begin TextColor (LIGHTRED); Write ('1'); end; 0: begin TextColor (RED); Write ('-'); end; end; WriteLn; end; End; Function Bin (N: integer): string16; Var i: integer; S: string16; Begin S: = '0000000000000000 '; i: = 0; while N> 0 do begin Inc (i); Insert (Chr ((N mod 2) +48), S, i); N: = N div 2; end; Bin: = S; End; Function Pokritie (var S: string16): boolean; Var V: array [1 .. 16] of integer; i, j, Sum: integer; Begin Pokritie: = False; for i: = 1 to 16 do V [i]: = 0; for i: = 1 to IndexSImp do if S [i] = '1 'then for j: = 1 to IndexDSNF do if QM [i, j] = 1 then V [j]: = 1; Sum: = 0; for i: = 1 to IndexDSNF do if V [i] = 1 then Sum: = Sum +1; if Sum = IndexDSNF then Pokritie: = True; End; Function Count (S: string16): integer; Var i, j, C: integer; Begin C: = 0; for i: = 1 to IndexSImp do if S [i] = '1 'then for j: = 1 to 4 do if SimpleImp [i, j ]<>'*' then C: = C +1; Count: = C; End; Procedure ActionsPetrik; Var i, j, Index: integer; S16: string16; Begin Index: = (1 shl IndexSImp) -1; S16Min: = '1111111111111111 '; for i: = 1 to Index do begin S16: = Bin (i); if Pokritie (S16) then if Count (S16) <Count (S16Min) then S16Min: = S16; end; End; Procedure PrintRezult; Var i: integer; Begin WriteLn; WriteLn; TextColor (LIGHTGREEN); WriteLn ('Мінімальна діз'юнктівная нормальна форма. '); WriteLn; TextColor (LIGHTRED); for i: = 1 to IndexSImp do if S16Min [i] = '1 'then WriteLn (SimpleImp [i]: 8); End; Begin ClrScr; Input; {введення даних} FormMatrix; {формування матриці покриття для її подальшої обробки} PrintMatrix; {висновок матриці} ActionsPetrik; {формування кон'юнкції диз'юнкцій за методом Петрика і вибір мінімальної з них} PrintRezult; {друк МДНФ} ReadKey; End. Результати роботи програми. 0000 0010 0011 0101 0110 0111 1010 1011 1111 0 * 1 * - 1 1 - 1 1 - - - * 01 * - 1 1 - - - 1 1 - ** 11 - - 1 - - 1 - 1 1 00 * 0 1 1 - - - - - - - 01 * 1 - - - 1 - 1 - - - Мінімальна діз'юнктівная нормальна форма. 0 * 1 * * 01 * ** 11 00 * 0 01 * 1
Додати в блог або на сайт
Цей текст може містити помилки.
Математика | Курсова
181.2кб. | скачати
Схожі роботи:
Функціонально повні системи логічних функцій Алгебраїчний підхід
Представлення логічних функцій від великого числа змінних
Валютні ризики і методи їх мінімізації
Методи рішення логічних задач
Аналіз мінімізації банківських ризиків
Аутсорсинг як спосіб мінімізації витрат
Небезпеки і засоби їх мінімізації Надзвичайна ситуація
Ризики у зовнішньоекономічній діяльності та механізм їх мінімізації
Характеристика фінансових ризиків на та заходи щодо їх мінімізації
| 