0v
V001111v010010v010011v010111v011001v100000v100010v100101v110110
Для подальшої роботи необхідно мінімізувати отримані вихідні функції автомата.
В
мінімізує картки
Одним з видів представлення ФАЛ від невеликого числа змінних (як правило, не більше 5) є діаграми Карно або Вейча, які будуються на розгортках багатовимірних кубів на площину. При цьому вершини куба представляються клітинами карти, координати яких збігаються з координатами відповідних вершин куба. Карта заповнюється шляхом позначки кодів вершин, відповідних наборам, на яких ФАЛ дорівнює одиниці. Іншими символами позначаються коди наборів, на яких ФАЛ не визначена. Таким чином, діаграма на карті Карно або Вейча відповідає уявленню ФАЛ в СДНФ. Якщо будується карта Карно для непарної кількості змінних в наборі, то на відстані одиниці ліворуч від вихідної карти для парного кількості змінних зображується повернена на 180 В° навколо осі, що проходить між вихідною і новою картами, нова карта тієї ж розмірності. Після цього в старшому розряді двійкових кодів наборів вихідної карти додаються незначущі нулі, а в старшому розряді нової картки додаються одиниці. Ці дві карти об'єднуються в одну більшої розмірності.
Якщо будується карта Карно для парного кількості змінних в наборі, те на відстані одиниці знизу від вихідної карти для непарної кількості змінних зображується повернена на 180 В° навколо осі, що проходить між вихідною і новою картами, нова карта тієї ж розмірності. Після цього в старшому розряді двійкових кодів наборів вихідної карти додаються незначущі нулі, а в старшому розряді нової картки додаються одиниці. Ці дві карти об'єднуються в одну більшої розмірності.
У картах набори змінних, на яких функція приймає одиничні значення, позначаються нечисловими символами. Карта з нанесеними на ній значеннями ФАЛ називається діаграмою. p> Карти, на яких коди наборів зображуються у вісімковій системі числення, називаються картами Вейча.
В
Мінімізація функцій за методом Квайна
При мінімізації за методом Квайна в базисі І, АБО, НЕ вихідна ФАЛ задається в СДНФ Метою мінімізації є знаходження всіх первинних імплікант і вибір деяких з них для мінімальної запису функції.
импликантами функції - деяка логічна функція, звертається в нуль при наборі змінних, на якому сама функція також дорівнює нулю.
Тому будь кон'юнктивний терм, входить до складу СДНФ, або група термів, з'єднаних знаками диз'юнкції є импликантами вихідної ФАЛ. Імпліканти мають поодинокі значення тільки на підмножині наборів з безлічі наборів, на яких вихідна ФАЛ дорівнює одиниці.
Первинна импликанта функції - импликанта типу елементарної кон'юнкції деяких змінних, ніяка частина якої вже не є импликантой.
Задача мінімізації за методом Квайна вирішується шляхом попарного порівняння всіх імплікант, що входять до ФАЛ, з метою виявлення можливості їх неповного склеювання з якоїсь змінної на проміжних етапах. При склеюванні знижується ранг термів. Склеювання проводиться до тих пір, поки не залишиться жодного терма, що допускає склеювання з яким-небудь іншим термом. Терми, що піддалися склеюванню, відзначаються. Невідмічені терми представляють собою первинні імпліканти. Після отримання безлічі всіх первинних імплікант досліджується можливість знаходження найпростішої записи ФАЛ. Для цього складається таблиця, в першому рядку якій записані минтермов вихідної ФАЛ, а в першому стовпці записані всі знайдені первинні імпліканти. Клітини цієї таблиці позначаються в тому випадку, якщо первинна импликанта входить до складу якого-небудь минтермов вихідної ФАЛ. Після цього завдання спрощення зводиться до того, щоб знайти таке мінімальне кількість первинних імплікант, які покривають всі стовпці минтермов вихідної ФАЛ.
В
Мінімізація функцій за методом Мак-Класкі
Недоліком методу Квайна є - необхідність вичерпного попарного порівняння або зіставлення всіх минтермов на етапі знаходження первинних імплікант. З ростом числа минтермов збільшується кількість попарних порівнянь.
Числове подання ФАЛ дозволяє спростити самий трудомісткий перший етап. Всі минтермов СДНФ ФАЛ записуються у вигляді їх двійкових кодів, а всі коди розбиваються за кількістю одиниць на непересічні групи.
минтермов, підлягають склеюванню, розрізняються тільки по одній змінній, а їх коди - тільки в одному розряді. З цієї причини порівнянні підлягають тільки двійкові коди минтермов сусідніх груп.
Розглянувши кілька методів мінімізації ФАЛ, можна зробити висновок про те, що для вирішення нашого завдання найбільш відповідним є метод Мак-Класкі.
Мінімізуємо < b> Y:
i
x
Вісімкове число
...
