![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Основні положення методу квайна
Нехай вихідна функція зображена у ДДНФ. Визначення 15.1. Імпліканта функції – це деяка логічна функція, що обертається на нуль на тому же наборі змінних, на якому дорівнює нулю сама функція. Будь-який кон’юнктивний терм або група термів, з’єднаних знаками диз’юнкції, що входять у ДДНФ, є імплікантами вихідної функції. Визначення 15.2. Первинна імпліканта функції – це імпліканта типу елементарної кон’юнкції, ніяка частина якої вже не є імплікантою. Завдання мінімізації за методом Квайна полягає у попарному порівнянні всіх імплікант, що входять у ДДНФ, з метою виявлення можливості поглинання якоїсь змінної на основі закону склеювання Якщо отриманий логічний вираз не виявився мінімальним, то досліджується можливість подальшого спрощення. Для цього складається таблиця, у рядках якої вказуються знайдені первинні імпліканти, а в стовпцях – терми вихідного виразу. Комірки таблиці відзначаються, якщо первинна імпліканта входить до складу якого-небудь терму. Таким чином, завдання спрощення зводиться до того, щоб знайти таку мінімальну кількість первинних імплікант, які покривають всі стовпці. Метод Квайна включає такі етапи: – визначення первинних імплікант; – розміщення міток; – знаходження істотних імплікант; – визначення й видалення зайвих стовпців; – визначення й видалення зайвих первинних імплікант; – вибір мінімального покриття; – складання мінімальної форми вихідної функції.
|