Мінімізація функцій алгебри логіки

Мінімізація функцій алгебри логіки (ФАЛ) є одним з основних етапів аналізу і синтезу цифрових пристроїв. Основною метою мінімізації логічних функцій є отримання їх мінімальних диз'юнктивних або кон'юнктивних форм.

ДНФ (КНФ) функції f(x₁, x₂, ..., x_n) називається мінімальної, якщо вона містить найменше число змінних х_i в порівнянні з усіма іншими еквівалентними ДНФ (КНФ).

Існують різні аналітичні і табличні методи мінімізації.

1. Метод безпосередніх перетворень.
2. Метод карт Карно.

1. Метод безпосередніх перетворень. Суть методу безпосередніх перетворень полягає з тому, що мінімізація вихідної ФАЛ здійснюється шляхом застосування основних законів і тотожностей алгебри логіки.

Скороченою ДНФ називається форма подання ФАЛ, яка виходить з ДНДФ шляхом склеювання конституент одиниці між собою за всіма змінними і т. д.

Проста імпліканта - це кон'юнкція, що не склеюється ні з якою іншою кон'юнкція, що входить в дану ФАЛ. Використовуючи поняття імпліканти, скорочену ДНФ можна визначити як диз'юнкцію простих імплікант.

​

Приклад 1. Мінімізувати функцію, задану в ДНДФ.

​

​

​

​

​

1

2

3

4

5

6

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

1 і 5: (по x₂)

2 і 4: (по x₃)

4 і 6: (по x₂)

3 і 5: (по x₃)

1

2

3

4

1 і 3: (по x₁)

В результаті мінімальна ДНФ має вигляд

2. Метод карт Карно. Логічна функція, записана в ДНДФ, може бути представлена ​​у вигляді спеціальних таблиць, відомих під назвою карт Карно або діаграм Вейча.

�2 Метод карт Карно.�

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

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

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

Одиниці в клітинах карти Карно об'єднуються в групи і обводятся контуром.

Будь-яка пара одиниць, розташованих в сусідніх клітках, виражається однією змінною, тією, яка присутня в кожному з наборів, об'єднаних в групу.

Одна і та ж клітина може входити в кілька груп.

f (x₁x₂) = x₁v x₂

Карта Карно для функції трьох змінних містить вісім клітин (збігається з числом рядків таблиці істинності рівним 2³).

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

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

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

Слід пам'ятати, що кількість одиниць, що об'єднуються в групу, має бути степенем двійки, тобто може бути 1,2,... і т. д.

Контур повинен бути прямокутним або квадратним.

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

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

Карта Карно логічної функції чотирьох змінних містить 2⁴ = 16 клітин.

При мінімізації функції п'яти змінних користуються карткою з 32 клітин.

​

На цій діаграмі однієї змінної відповідає 16 одиниць, Розташованих в суміжних клітинах, твору двох змінних - вісім, одиниць, твору трьох змінних - чотири, твору чотирьох змінних - дві одиниці.

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

3 неповністю визначені логічні функції і їх мінімізація

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

Їх зазвичай довизначають так, щоб максимально спростити відповідні ФАЛ.

Для цієї мети зручно застосовувати карти Карно.