Лабораторная работа №6 Минимизация логических функций

Цель работы

• Освоить понятия минимизации логических функций (ЛФ).

• Научиться мимнимизировать ЛФ методом Квайна-Мак-Класски.

• Научиться мимнимизировать ЛФ с помощью карт Карно.

Теоретические сведения

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

Например, функция x₁+ x₂ может быть упрощена, если применить распределительный закон: x₁x₂+x₃=(x₁+x₃)(x₂+х₃), тогда

x₁+ x₂=( +x₁)(x₁+х₂)=x₁ +x₁x₁+ х₂+x₁x₂=

=0+x₁+х₂( +x₁)=x₁+х_2.

Упрощение сложных логических выражений может быть осуществлено на основании применения законов и аксиом алгебры логики.

6.1 Числовое и геометрическое представление ФЛ

Многие преобразования, выполняемые над булевыми функциями, удобно интерпретировать с использованием их геометрических представлений f(x).

Так функцию двух переменных можно интерпретировать как некоторую плоскость, заданную в системе координат xy=x₁x₂. При произвольно выбранных единичных значениях x₁ и х₂ получается квадрат, вершины которого соответствуют комбинациям переменных (см. рисунок 6.1).

Рис. 6.1-Геометрическое представление ФЛ при n = 2.

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

Правило склеивания распространяется и на кубическое представление ФЛ.

На рисунке 6.2 показана область определения для произвольной функции трех переменных.

Элементам куба сопоставлены конъюнкции различного ранга: вершинам куба – третий ранг, ребрам куба - второй ранг, граням куба - первый ранг.

Определение. Сумма размерности геометрического эквивалента и ранга, сопоставляемая этому геометрическому эквиваленту конъюнкции, постоянна и равна числу аргументов функции.

Определение. Каждый геометрический эквивалент меньшей размерности покрывается всеми геометрическими эквивалентами большей размерности.

Рис. 6.2-Геометрическое представление ФЛ при n=3

По аналогии будем говорить о покрытии конъюнкции большего ранга соответствующими конъюнкциями меньшего ранга.

Например, конъюнкции x₁x₂x₃ и x₁x₂ покрываются конъюнкцией x₁x₂.

В общем виде операцию покрытия можно записать АВ+А=А. Чаще употребляется термин склеивание.

В геометрическом смысле каждый набор x_1,x₂,…,х_n может рассматриваться как n -мерный вектор, определяющий точку n-мерного пространства. Исходя из этого, множество наборов, на которых определена функция n переменных, представляют в виде вершин n-мерного куба.

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

Отмечая точками вершины, в которых функция принимает значения, равные 1, получаем геометрическое представление ФЛ.

6.2 Построение комплекса кубов и его минимального покрытия

Терм максимального ранга n- куба принято называть 0-кубом (точка вершины) и обозначают К⁰. Например, для f(x₁,x₂,x₃)= (0,4,7) комплекс 0-кубов будет таким

Определение. Если два 0-куба из комплекса К⁰ различаются только по одной координате, то два таких 0-куба образуют один 1-куб. Он представляется общими элементами 0-кубов, причем на месте координаты, по которой различаются 0-кубы, указывают символ Х, обозначающий независимую координату (переменную). Различие координат определяют последовательным сравнением первого куба с остальными, затем второго с остальными и так далее. Например, два 0-куба 000 и 100 различаются только по одной координате, и они образуют 1-куб (отрезок), которому соответствует ребро трехмерного куба. Заметим, что 0-куб 111 не склеивается, так как отличается больше чем по одной координате.

Все множество 1-кубов функции называется кубическим комплексом К- один и обозначается- К¹.

K¹ = {X00}

Комплекс К¹ строится по комплексу К⁰ путем их сравнения и определяет все множество ребер, на концах которых функция принимает единичные значения. Если два 1-куба из комплекса К¹ имеют общую независимую компоненту и различаются только по одной координате, то они образуют один 2-куб. Это грань для трехмерного куба. Все множество 2-кубов, построенного из комплекса К¹, образует множество комплекса К² (множество граней). Комплекс К³ = 0 - отсутствует в трехмерном кубе (часто r-куб называют интервалом (расстоянием) r- порядка). Перед построением очередного куба необходимо отметить те кубы, которые склеились хотя бы один раз. Например, звездочкой *. Это необходимо, так как могут быть неотмеченные (не склеившиеся) кубы о которых забывать нельзя. Они являются самостоятельными импликантами, которые так же включают в общее покрытие кубов С(f). Для нашего примера, общее покрытие будет выглядеть

По индукции можно определить, что два r-куба, содержащие r координат и различающиеся только по одной координате, могут объединяться в (r + 1)-куб, (r + 1)-я независимая координата которого соответствует координате, по которой различаются r-кубы.

Запись (r + 1)-куба состоит из общих компонент двух r-кубов, а компонента, принимающая в них различные значения, обозначается в (r + 1)-кубе как независимая компонента Х.

Число независимых координат Х в кубе определяет его размерность.

Например, куб 0Х1Х1ХХ имеет размерность r = 4.

Определение. Объединение кубов комплексов К⁰,К¹,...,Кⁿ функции f(x₁, x₂, …, х_n) называется кубическим комплексом K(f) функции f.

K(f) = K(f) = К⁰ К¹ К² К³ ...

В отличие от аналитических форм записи булевых функций, кубическое представление позволяет задавать булевы функции в виде множества кубов, компонентами которых являются только три символа 0; 1; X. Ограниченное количество символов в записи функций алгебры логики позволяет автоматизировать процесс минимизации с применением компьютерных систем.

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

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

Определение. Булева функция f(x₁, x₂, …, х_n) представляется как множество С кубов, принадлежащих комплексу К(f), и таких, что каждая вершина комплекса К⁰ включена по крайней мере в один куб множества С.

Полученное таким образом множество С называется покрытием комплекса K(f) и покрытием булевой функции. Каждому покрытию C(f) соответствует ДНФ функции.

Например, дана функция

f(х)= (3,4,5,6,7)= x₂x₃+x₁ + +x₁ x₃+x₁x₂ +x₁x₂x₃

Построим комплекс кубов К⁰,К¹,К²,К³.

К³= 0

Из комплекса кубов K(f) определяется его покрытие C(f) куда входят не отмеченная импликанта Х11 из куба К¹ и покрытие 1ХХ из куба К².

C(f) =

Это покрытие включает в себя все 5 вершин комплекса К°. В самом деле, куб x11 может включать (покрывать) 011; 111. Куб 1xx может включать вершины 100, 101, 110, 111. Таким образом, множество C(f) является покрытием комплекса K(f). Отсюда можно написать минимизированное уравнение:

f(х)= (3,4,5,6,7)=x₂x₃+x₁.

6.3. Метод Квайна-Мак-Класски

При минимизации по методу Квайна предполагается, что минимизируемая функция представленна в СДНФ.

Метод Квайна состоит из последовательного выполнения нескольких этапов.

1-й этап. Нахождение первичных импликант.

Все минтермы данной функции сравниваются попарно. Если минтермы отличаются одной координатой типа Fх_i+F=F, то выписывается конъюнкция F, являющаяся минтермом (r+l)-гo ранга. Минтермы r-го ранга, для которых произошло склеивание, отмечаются.

Другими словами, нахождение простых импликант сводится к построению комплекса кубов

K(f) = К⁰ К¹ К² … К^r.

При построении последующих кубов, образующие предыдущие кубы отмечаются, чтобы выявить неотмеченные кубы.

Этап заканчивается, когда ни один (r+1)-куб не может быть построен. При этом, все неотмеченные кубы комплекса K(f) тоже являются простыми импликантами и входят в покрытие C(f) функции f.

Пример. Пусть задана функция

F(х₁,х₂,х₃,х₄,х₅)= (0,1,2,3,4,5,14,15,16,17,18,19,21,23,31)

Для упрощения, 0-кубы упорядочивают по числу 1-ых координат (см. рисунок 6.3).

Рис. 6.3-Комплекс кубов

Простые и неотмеченные импликанты образуют покрытие С(f), которое может быть избыточным и требует последующих этапов минимизации, а именно - составления таблиц покрытия функции.

2-й этап. Составление таблиц покрытий.

Понятно, что для нахождения минимальной формы покрытия необходимо удалить из покрытия некоторые простые или неотмеченные импликанты. Для этого используют таблицу, строки которой составляют импликанты покрытия, а столбцы - 0-кубы (минтермы) исходной функции. Если импликанта отличается от 0-куба (кроме независимых координат), то на их пересечении не ставится метка + (см. таблицу 6.1).

Таблица 6.1-Таблица покрытий комплекса кубов

3-й этап. Определение существенных импликант.

Если в столбце таблицы покрытий имеется только одна метка, то первичная импликанта, стоящая в соответствующей строке, является существенной импликантой, и ее выписывают в новое минимальное покрытие C(f). Из таблицы покрытий исключаются строки, соответствующие существенным импликантам и столбцы минтермов, покрываемым этими существенными импликантами. Покрытие будет иметь вид :

C(f) = .

В результате упрощения, получим новую таблицу 6.2

Таблица 6.2-Покрытия

4-й этап. Вычеркивание лишних столбцов.

Если в таблице существенных импликант есть два столбца имеющих метки в одинаковых строках, то один из столбцов вычеркивается.

5-й этап. Вычеркивание простых лишних импликант.

Если после вычеркивания столбцов в таблице появляются строки без меток, то импликанты этих строк вычеркиваются.

6-й этап. Выбор минимального покрытия.

В таблице, полученной после выделения существенных импликант, выбирается совокупность простых импликант, обеспечивающая покрытие всех столбцов с минимальной ценой С^A.

В нашем примере выбирается импликанта Х0Х01 ( или 10ХХ1, т.к. цены С^A одинаковы).

Таким образом, покрытие функции имеет вид:

С(f) =

и определяет минимальную ДНФ

f = ++x₂x₃x₄+x₅+x₁x₃x₄x₅..

При использовании метода Квайна для СКНФ необходимо рассматривать значения функций f=0 и макстермы, соответствующие этим значениям. В результате получим

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

6.4 Метод минимизации ФЛ с помощью карт Карно

Одним из способов графического представления булевых функций от небольшого числа переменных являются карты Карно. Их разновидность - карты Вейча. Карты строят как развертки кубов на плоскости. При этом, вершины куба представляются клетками карты, координаты которых совпадают с координатами соответствующих вершин куба (минтермов). Карта заполняется так же, как таблица истинности: значение 1 указывается в клетке, соответствующей набору (минтерму), на котором функция имеет значение 1. Значение f = 0 обычно на картах не отражается. Условное размещение координат переменных и примеры минимизации ФЛ на картах для двух, трех и четырех переменных показаны на рисунке. 6.4.

Способ минимизации ФЛ с помощью карт Карно получил широкое применение среди специалистов. Этому способствовали довольно высокая формализация действий, наглядность графики и относительно простые правила. Как показано на рисунке 6.4, карты Карно представляют прямоугольником (квадратом), на котором размещают 2ⁿ клеток, где n-число переменных ФЛ. При заполнении клеток значениями функций 1, используют условные координаты размещения переменных. Координаты клеток обычно указывают с левой стороны и сверху, используя код Грея. Если нарушить места обозначения координат, то минимальная функция не будет отвечать истине. Каждой клетке соответствует свой минтерм, обозначенный пересечением переменных строк и столбцов. После заполнения клеток карт единицами, определяют соседние клетки.

6.4.1 Соседние клетки

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

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

Для минимизации функций с числом переменных больше 7 карты Карно практически не применяются.

После определения соседних клеток, их объединяют контурами объединения.

6.4.2 Правило объединения соседних клеток

Контур должен содержать только соседние клетки, при этом, число единиц включенных в контур должно быть равным одному из чисел: 2, 4, 8, 16, 32, 64,…,2ⁿ. Это условие обязательно.

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

Общее число контуров должно быть как можно меньшим, так как каждый контур объединения это новый минтерм функции и чем меньше их будет, тем она минимальна.

С другой стороны, общее число объединенных единиц должно быть по возможности большим, так как это уменьшает число переменных в минтерме, понижая его ранг. Всегда объединение в 2k клеток (соседних единиц) исключает из минтермов k переменных, где k=1,2,3,4,…. Необходимо помнить, что объединение соседних клеток это процесс требующий наличие опыта по выбору наилучшего варианта. Поэтому, каждый раз при минимизации необходимо просматривать несколько вариантов и выбирать лучший, который приводит к минимальной функции. После объединения соседних клеток, переходим к записи для них минтермов.

6.4.3 Определение простых импликант

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

Если переменная Х₁ в любой строчке(столбце), проходящей через контур, не изменяет значения своей координаты (т.е. во всех строчках контура ее значение либо 0, либо 1), то в минтерм объединения записывается ее значение (либо 0, либо1).

Если переменная Х₁ в строчках (столбцах), проходящих через контур, изменяет значение своей координаты (т.е. в одной строчке контура ее значение 0, а в другой 1, либо наоборот), то в минтерм объединения записывается, так называемая, неопределенная переменная Х на том месте, где должно записываться значение переменной Х₁ (рисунок 9.1д,е,ж). Аналогичный анализ проводится последовательно для всех переменных, в результате чего получаем минтерм объединения. На рисунке 9.1д,е,ж они расположены на выносках.