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

Упрощение логических выражений с помощью законов алгебры логики основывается на интуитивных решениях и представляет большие трудности, особенно при большом числе переменных. При этом бывает трудно оценить, является ли полученное выражение простейшим или возможны дальнейшие упрощения.

Минимизировать логические функции можно с помощью так называемых карт Карно. Представление функций с помощью карт Карно очень удобно, когда число переменных невелико. По сути карта Карно — это таблица, которая содержит 2п клеток, где п — число переменных. К каждой клетке содержится логическое произведение переменных или их инверсий. Одни переменные располагаются по горизонтали, другие — по вертикали. Изображаться карты Карно могут по-разному. На рис. 11.1 приведен пример изображения карты Карно для функции четырех переменных:

Карта Карно содержит 24 = 16 клеток. Комбинации значений аргументов одной группы хгх2 приписываются столбцам таблицы, а комбинации значений аргументов другой группы х3х4 — строкам таблицы. Столбцы и строки обозначаются комбинациями, соответствующими последовательности чисел в коде Грея 00, 01, 11, 10. Это сделано для того, чтобы склеивающиеся клетки находились рядом. Обозначения столбца и строки, на пересечении которых находится клетка таблицы, образуют набор, при котором значение заданной логической функции записывается в клетку (рис. 11.1).

Для получения минимальной дизъюнктивной нормальной формы (МДНФ) функции в таблице охватываются областями (выделено пунктиром) группы клеток, содержащие единицы. Число одновременно объединяемых клеток может быть 2, 4, 8, 16 и т.д. Для заданной логической функции выделяем две такие области I и II.

Карта Карно для функции четырех переменных

Рис. 11.1. Карта Карно для функции четырех переменных

Анализ карты Карно (рис. 11.1), показывает, что группа / из четырех ячеек у = х1х2х3х4 vXiX2x3x4 vx1x2x3x4 vx1x2x3x4 может быть описана одним логическим произведением х3х4, в которое переменные х3 и х4 не входят. Группа II из двух ячеек у = х1х2х3х4 vx3x2x3x4 описывается в виде логического произведения у = х1х2х3, в которое переменная х4 не входит.

В результате минимизированная логическая функция представляет собой сумму двух произведений, соответствующих отдельным группам:

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

Для минимизации логических функций, заданных в том или ином виде, можно использовать компьютерные программы, например, Electronics Work-bench.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >