Метод Вейча

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

На рис. 2.4 показана структура таблиці Вейча для трьох змінних.

х•у•ž	х•у•z	ӿ•у•z	ӿ•у•ž
х•ȳ•ž	х•ȳ•z	ӿ•ȳ•z	ӿ•ȳ•ž

Рис. 2.4.

Правила склеювання клітинок у таблиці Вейча:

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

2. В групу дозволяється об’єднувати кількість клітинок , n=1,2,3… При цьому група може мати лише прямокутну або квадратну форму.

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

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

5. Диз’юнкція всіх отриманих простих імплікант зображує результат мінімізації формули і є мінімальною ДНФ.

Приклад. Знайти МДНФ логічної функції

Розв’язання. Будуємо таблицю Вейча.

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

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