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

 

Для реализации метода зададим исходную функцию набором значений f(x,y,z)=(00001101). На строке значений функции построим треугольник Паскаля, представленный на рисунке 1.1, складывая попарно по модулю 2 соседние значения функции.

 

 

Рисунок 1.1 – Треугольник Паскаля

 

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

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

 

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

 

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

Пусть с помощью карты Карно задана логическая функция , необходимо найти ее тупиковую ДНФ. Тогда задача минимизации решается следующим образом: среди единичных значений логической функции , предварительно нанесенных на карту Карно, отыскиваются прямоугольники и/или квадраты с числом клеток , где k=(n-1),…,0. Выделяемые прямоугольники и/или квадраты могут пересекаться между собой.

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

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

Импликанты– это элементарные конъюнкции ранга меньше максимального, которые не могут быть склеены (т.е. объединены) между собой.

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

Если необходимо найти тупиковую КНФ логической функции , то задача минимизации решается следующим образом: среди нулевых значений логической функции , предварительно нанесенных на карту Карно, отыскиваются прямоугольники и/или квадраты с числом клеток , где k=(n-1),…,0. Выделяемые прямоугольники и/или квадраты могут пересекаться между собой.

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

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

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

Минимизируем с помощью данного метода логическую функцию , СДНФ которой определяется соотношением:

(1.1)

Построим для функции карту Карно (рисунок 1.2).

 

ab c

 

Рисунок 1.2 - Карта Карно функции

 

Определим максимальный размер прямоугольника, которым можно покрыть клетки карты. Величина прямоугольников вычисляется как , где k=(n-1),(n-2),…,0, а n – число аргументов, от которых зависит логическая функция. В нашем случае n=3, следовательно, максимальный размер прямоугольника равен = =4. В карте Карно нет прямоугольника, состоящего из четырех единиц, стоящих рядом, поэтому объединять клетки карты можно только по две, например так, как показано на рис. 1.3.

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

+ = = ,

то есть переменная из этой группы может быть исключена.

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

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

 

 

Рисунок 1.3 - Карта Карно функции

 

Объединяя знаком дизъюнкции найденные из каждого прямоугольника импликанты, получаем тупиковую ДНФ функции :

 

(1.2)

 

Объединить клетки карты Карно можно и другим образом (рисунок 1.3),

 

 

Рисунок 1.4 - Карта Карно функции

 

тогда получим еще одну тупиковую ДНФ, реализующую функцию (1.3):

 

(1.3)

 

 

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

 

Пусть не полностью определенная логическая функция R(a,b,c,d) задана с помощью карты Карно (рисунок 1.5).

 

 

Рисунок 1.5 - Карта Карно логической функции R(a,b,c,d)

 

Для представления функции R(a,b,c,d) в виде минимальной ДНФ целесообразно следующее доопределение логической функции (рисунок 1.6):

 

Рисунок 1.6 - Доопределенная карта Карно логической функции R(a,b,c,d)

 

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

 

 

Рисунок 1.7 - Карта Карно логической функции R(a,b,c,d)

 

В результате минимизации получим минимальную ДНФ логической функции R(a,b, c,d):

 

(1.4)

 

Сравнение эффективности минимизированных форм часто проводят по способу Шеннона. Этот способ базируется на введении такого понятия как цена схемы – Ц. Цену схемы можно рассчитать по следующей формуле:

 

, (1.5)

 

где - количество входов у j-ого элемента, i-количество элементов.

Пусть логическая функция R(a,b,c,d) задана в виде СДНФ (1.6):

 

(1.6)

 

Оценим минимальную ДНФ логической функции R(a,b, c,d) (1.5):

 

Элементов “И” в выражении присутствует 5 (два элемента “И” по 2 входа, три элемента “И” по 3 входа), элементов “ИЛИ”- 1 (один элемент на 5 входов), элементов “НЕ”- 4 (4 элемента по 1 входу), следовательно:

 

Ц=2*2+3*3+1*5+4*1=22 входа

 

Тем же способом оценим СДНФ логической функции R(a,b,c,d) – выражение (1.6):

 

Элементов “И” - 11 (одиннадцать элементов по 4 входа), элементов “ИЛИ”- 1 (один элемент на 11 входов), элементов “НЕ”- 4 (4 элемента по 1 входу), следовательно:

Ц=11*4+1*11+4*1=59 входов.

 

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

 

 

1.3 Полиномы Жегалкина для частично определенных булевых функций

 

Как уже было сказано, частичной называется булева функция, значения которой заданы лишь на некоторых наборах, образующих в совокупности область определения функции. Предположим, что на всех остальных наборах значения рассматриваемой функции могут быть любыми – их можно определить произвольно. Если число таких наборов равно k, то существует 2^k различных доопределений функции и каждому из них соответствует свой полином Жегалкина. Из практических соображений возникает задача выбора среди них, самого простого, с минимальным числом конъюктивных термов.

Эту задачу можно решить «в лоб», перебирая все 2^k доопределения, находя для каждого их них полином Жегалкина и выбирая среди них наилучший. Суть метода заключается в следующем.

Совокупность значений функции, определяемых на k безразличных наборах, представляется булевым k – вектором. Значения этого вектора перебираются по коду Грея, введенному первоначально для представления натуральных чисел. При этом, как и в случае двоичного позиционного кода, представляются числа меньшие, чем 2^k, начиная с 0.

В соответствии с кодом Грея, значения вектора, кодирующие число 0, составляется из нулей, а каждое последующее получается из предыдущего изменения значения в одном разряде – самом младшем (правом) из тех, которые обеспечивают получение еще не использованной комбинации [2].

 

1.4 Обзор программных средств решения задачи