Минимизация логических функций с помощью диаграмм Вейча

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

Минимизацию логических функций можно провести, используя диаграммы Вейча (или аналогичный метод карт Карно). Диаграмма Вейча для функции F четырех переменных А, В, С, D представлена на рис. 3. Каждая из переменных принимает два значения, т.е, воз­можны 2⁴= 16 комбинаций входных функций.

Диаграмма Вейча содер­жит 16 клеток, каждая из которых соответствует одной из 16 возмож­ных комбинаций входных переменных. На полях диаграммы обозначе­ны значения каждой переменной. Диаграмма состоит из четырех строк и четырех столбцов.

Рисунок 3 – Диаграмма Вейча для функции четырёх переменных

При минимизации с помощью диаграмма Вейча нужно логическое выражение привести к сумме произведений переменных, прямых или с их инверсиями – чтобы они совпадали с конъюнкциями в клетках диаграммы – частично или полностью. Общие инверсии суммы или произведения переменных нужно исключить с помощью правил де Моргана.

Рассмотрим минимизацию логической функции на примере.

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

+ ()+ A CD+ BCD+ ABC + + B D.

Решение состоит из четырёх операций.

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

При преобразовании нужно раскрыть скобки и исключить инверсии над комбинациями переменных (с помощью формул де Мограна). В примере нужно избавиться от комбинации , заменив её на одиночные инверсии . Получим:

+ + A CD+ BCD+ ABC + + B D.      (14)

2. Заполнение диаграммы Вейча производится следующим образом:

¨ Клетки диаграммы, содержащие комбинации выражения (14) обозначаются знаком 1 (рис. 4).

¨ Если слагаемое не содержит одного или нескольких аргументов (члены BCD и ), то заполняются клетки, соответствующие и прямому, и инверсному значениям отсутствующих аргументов. Таким образом, для члена BCD единицами обозначаются клетки ABCD и , а для члена  - клетки .

в)

Рисунок 4 – а) заполненная диаграмма Вейча; б) схема на элементах И-НЕ; в) схема на элемента И-НЕ, И, ИЛИ.

3. "Склейка", т.е. объединение клеток. Склеиваются только рядом стоящие клетки. Можно склеивать целую заполненную строку, столбец, полстроки или полстолбца. Можно склеить соседние строки, столбцы, полустроки и полустолбцы.

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

Одна склейка может накладываться на другую. Склейка содержит 2, 4, 8 клеток.

Содержание клетки реализуется в схемах функцией конъюнкции "И", а их склейки – функцией дизъюнкции "ИЛИ".