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

 

Самостоятельная работа на Тему:

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

 

 

 

 

 

 

 

 

 

2013 г.

Содержание:

 

1. Цели и задачи минимизации. 3
2. Метод карт Карно (Вейча). 4 (9)
3. Метод Квайна.  10
4. Метод Квайна – Мак – Класки.  16
5. Метод Петрика.  17
6. Минимизация функции всеми перечисленными методами.  18

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Цели и задачи минимизации.

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

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

Существуют два направления  минимизации:

1. Кратчайшая форма записи (при этом получаются кратчайшие формы КДНФ, ККНФ, КПНФ);

2.   Получение минимальной формы записи (получение   минимального числа символов для записи всей функции сразу).  

Но следует учесть, что  ни один из способов минимизации не универсален.

 

 

 

 

 

 

 

 

 

Метод Карт Карно (Вейча).

Карта Карно или карта (диаграмма) Вейча – графический  способ минимизации функций алгебры  логики.

Карты Карно удобны при  небольшом числе переменных.

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

На рис. 1 представлены карты Вейча  для двух, трех и четырех переменных соответственно [12].

 

 

 

рис. 1

Расположение групп переменных x не имеет значения, необходимо лишь, чтобы каждая клетка отличалась от любой соседней лишь на одну переменную. Согласно принятой форме построения карт соседними также считаются клетки первой и последней строк, клетки первого и последнего столбцов. Число клеток карты равно числу возможных комбинаций значений переменных (термов) и в каждую клетку записывается значение логической функции, соответствующее данному набору переменных. Если какая-то из возможных комбинаций присутствует в совершенной дизъюнктивной нормальной форме (СДНФ) записи функции, то в соответствующей клетке карты Карно ставится «1». Если какого-то терма в полученной функции нет, то в соответствующей клетке карты Карно ставится «0» [12].

Например, рассмотренная в предыдущем примере функция 

 

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

 

 

 

 

рис. 2

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

Так в первой строке карты Карно (см. рис. 2 б) переменная х, встречается в комбинации с х₁ и х₂, которые дополняют друг друга:

 

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

Аналогично, группируя две  соседние клетки в левом столбце (контур на рис. 2 б) и исключая отличающиеся переменные, получим упрощенное выражение  – х₂.

Полученные упрощенные выражения  объединяют с помощью операции ИЛИ.

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

 

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

Допускается также иметь  несколько групп перекрывающихся  клеток, как в только что рассмотренном  примере.

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

Для исключения n переменных общее число группируемых клеток должно быть равно 2ⁿ. Так, для исключения одной переменной требуется объединить две соседние клетки, а для исключения трех переменных уже требуется объединить восемь соседних клеток [12].

Таким образом, для того чтобы  получить минимизированную логическую функцию, необходимо сгруппировать  все соседние клетки карты Карно, содержащие 1, а затем объединить полученные группы с помощью операции ИЛИ. Клетки, содержащие 1, которые не удалось объединить с другими  клетками, образуют в минимизированной логической функции самостоятельные  члены, каждый из которых содержит все  переменные [12].

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

Так, карта Вейча для логической функции

 

приведена на рисунке 3.

 

 

рис. 3

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

Упрощенное выражение логической функции имеет вид

 

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

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

Карта Карно для этой функции  представлена на рисунке 4:

рис. 4

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

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

 

Диаграмма Вейча

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

которой представлена на рис. 5.

рис. 5

Булево выражение этой функции имеет вид

Четыре угловые клетки можно объединить в одну группу. Это объединение позволяет исключить  две переменные (х₁ и х₂) и получить член .

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

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

Таким образом, мы получим  минимизированную логическую функцию

 

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

 

Метод Куайна.

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

Преобразование функции  можно разделить на два этапа:

на первом этапе осуществляется переход от канонической формы (СДНФ или СКНФ) к так называемой сокращённой  форме;

на втором этапе — переход  от сокращённой формы к минимальной  форме.

Первый этап (получение  сокращённой формы)

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

1. Операция склеивания;
2. Операция поглощения.

Операция склеивания сводится к нахождению пар членов, соответствующих  виду   или  , и преобразованию их в следующие выражения:  . Результаты склеивания   теперь играют роль дополнительных членов.

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

0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	1

СДНФ выглядит так:

Результат операции склеивания нужен для преобразования функции  на втором этапе (поглощения)

Членами результата склеивания являются

Член   поглощает те члены исходного выражения, которые содержат  , то есть первый и четвёртый. Эти члены вычёркиваются. Член   поглощает второй и третий, а член   — пятый член исходного выражения.

Повторение обеих операций приводит к следующему выражению:

Здесь склеивается пара членов   и   (склеивание пары членов   и   приводит к тому же результату), результат склеивания   поглощает 2-, 3-, 4-, 5-й члены выражения. Дальнейшее проведение операций склеивания и поглощения оказывается невозможным, сокращённая форма выражения заданной функции (в данном случае она совпадает с минимальной формой)

Структурная схема функции

Члены сокращённой формы (в нашем случае это   и  ) называются простыми импликантами функции. В итоге, мы получили наиболее простое выражение, если сравнивать его с начальной версией — СДНФ. Структурная схема такого элемента показана на рисунке справа.

Второй этап (табличный) (получение  минимальной формы)

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

0	0	0	0	1
0	0	0	1	1
0	0	1	0	1
0	0	1	1	0
0	1	0	0	0
0	1	0	1	0
0	1	1	0	1
0	1	1	1	0
1	0	0	0	0
1	0	0	1	0
1	0	1	0	0
1	0	1	1	0
1	1	0	0	0
1	1	0	1	0
1	1	1	0	1
1	1	1	1	1