Главная Обратная связь

Дисциплины:






Методы минимизации логических функций



Логические функции небольшого числа переменных (n £ 3) можно минимизировать, используя тождества алгебры логики и законы алгебры логики.

При увеличении числа переменных (n < 6) можно использовать метод карт Карно.

1) Метод карт Карно

Алгоритм метода заключается в следующем:

а) объединяются клетки, составляющие полные квадраты из 4-х или 16-ти клеток;

б) объединяются клетки, составляющие полные столбцы или ряды из 2-х, 4-х или 8-ми клеток, а также 2 рядом расположенных столбца или ряда из 4-х, 16-ти или 8-ми клеток;

в) объединяются 2 соседние клетки в столбце или ряду.

В каждое объединение должно входить максимальное число клеток, одна клетка может входить в несколько объединений.

Если объединить клетки, незанятые , можно получить минимальную ДНФ (МДНФ) для инверсии функции F. Применив к F еще инверсию и закон де Моргана, можно получить минимальную КНФ (МКНФ).

Пример:

Минимизировать функцию

Карта Карно имеет вид:

 

Получаем F1(x1,x2,x3) = .

Объединяя клетки, не занятые 1, получаем МДНФ для инверсии функции

.

Инвертируя это выражение и применяя закон де Моргана, получаем МКНФ:

.

При большом числе переменных для минимизации ЛФ можно использовать метод Квайна-Мак-Класки или метод декомпозиции.

2) Метод декомпозиции

Он заключается в выделении более простых составляющих ЛФ и минимизации их по картам Карно, при этом

,

где функции F1 и F2 получаются из F путем подстановки в нее

значений x1=0 для x1=1 для F2.

Например,

F = =

3) Минимизация ЛФ в базисе И-НЕ

Алгоритм метода состоит в следующем:

а) получить МДНФ;

б) произвести двойную инверсию над полученной МДНФ;

в) преобразовать по теореме де Моргана инверсию дизъюнкции в конъюнкцию инверсий по формуле .

В результате получается ЛФ, содержащая только операции И-НЕ.

Например, пусть имеется МДНФ:

.

Производится двойная инверсия

=

и применяется закон де Моргана

= .

4) Минимизация ЛФ в базисе ИЛИ-НЕ

Алгоритм метода состоит в следующем:

а) получить МДНФ;

б) произвести двойную инверсию конъюнкций в дизъюнкцию

инверсий;

в) преобразовать инверсию конъюнкций в дизъюнкцию инверсий:

.

В полученной ЛФ содержатся только операции ИЛИ-НЕ.

Например:

.

5) Минимизация ЛФ в базисе И - ИЛИ – НЕ

Алгоритм:

а) получить МДНФ для инверсии заданной ЛФ по картам Карно;

б) произвести инверсию полученной МДНФ:

Например,

;

.

Среди алгоритмов минимизации ЛФ от большого числа переменных, легко реализующихся на ЭВМ, наиболее распространен метод Квайна-Мак-Класки.

Задачи:

 

1. Минимизировать следующие ЛФ четырех с помощью карт Карно:



а)F = v1(0,2,5,7,8,10,15);

б)F = v1(1,3,4,5,6,7,10,11);

в)F = v1(0,2,7,8,13,15);

г)F = v1(0,2,3,4,5,7,13,15);

д)F = v1(0,3,5,7,8,11,12,15);

е)F = v1(5,6,7,9,10,11,14);

ж)F = v1(0,5,8,11,13,14,15);

з)F = v1(0,1,2,8,9,10,12,13,14,15).

 

2. Найти МДНФ методом Квайна-Мак-Класки:

а) F = v1(0,1,2,3,4,5,6,10,12,13,14);

б) F = v1(0,1,2,6,7,9,11,14,15).

 

3. Минимизировать с помощью карт Карно ЛФ:

F = (1,2,3,4,6,7,10,11,12,14).

 

4. Представить МДНФ, найденные в задаче 1, в базисах И-НЕ, ИЛИ-НЕ.

Литература

 

1) В.А. Горбатов. "Основы дискретной математики". М.: Высшая школа, 1986.

 

2) О.П. Кузнецов, Г.М. Адельсон-Вельский. "Дискретная математика для инженера", М.: Энерготомиздат, 1988.

 

3) Лекции по теории графов / Емелигев В.А. и др. - М.: Наука, 1990

 





sdamzavas.net - 2020 год. Все права принадлежат их авторам! В случае нарушение авторского права, обращайтесь по форме обратной связи...