Основные понятия минимизации булевых функций

Размещено на http://www.allbest.ru/

Основные понятия минимизации булевых функций

двойственность булевый карно минимизация

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

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

Мы говорили о законе склеивания, поглощения, распределительный закон, сочетательный закон, переместительный закон.

Но только для алгебры логики действует закон двойственности (правило де Моргана):

; =.

Законы двойственности обобщены К. Шенноном для любых булевых функций (ФАЛ):

.

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

Пример:

(*)

Заметим, что в первоначальную запись функции (*) можно значительно упростить. Действительно, вынесем за скобки , тогда получим:

Использование этих законов позволяет упрощать исходную запись ФАЛ.

В первой исходной записи ФАЛ, полученной по таблице 3, в каждом логическом произведении переменных (конъюнкция) присутствовали все переменные из набора x₁x₂x₃, а сами конъюнкции соединены символом логического сложения (дизъюнкции). Такая форма записи ФАЛ называется совершенной дизъюнктивной нормальной формой (СДНФ).

Если не все переменные из набора x₁x₂x₃ представлены в каждой из конъюнкций, то такая форма по-прежнему остается нормальной дизъюнктивной формой, но она не относится к классу совершенных.

ДНФ представления одной и той же ФАЛ может быть много, но совершенная ДНФ (СДНФ) одна единственная.

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

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

Анализ СДНФ и СКНФ показывает неэкономичность записи ФАЛ. Используя свойства ФАЛ можно преобразовать выражения за счет так называемой операции склеивания, т.е.

, т. к. .

,

где a - любая ФАЛ.

Упрощение записи СДНФ за счет операции склеивания называется минимизацией ФАЛ.

Существует большое число алгоритмов минимизации ФАЛ, из которых наиболее наглядным и простым является метод карт Карно.

Карта Карно представляет собой булево пространство в виде таблицы, в которой отображаются конституенты СДНФ.

Конституента - это набор переменных, соединенных знаком конъюнкции (И).

Если функция при этом наборе переменных равна 1, то в клетку матрицы записывается 1. Черточками над клетками булева пространства помечаются строки и столбцы (по горизонтали и по вертикали), в которых обозначенная переменная примет значение 1.

Например представлена ФАЛ, для которой СДНФ имеет вид:

.

Составим таблицу для этого множества:

В таблице 11 значение х₁ = 1 распространяется на столбцы 2 и 3, считая справа налево, а значение х₂ = 1 - на столбцы 1 и 2. Аналогично черточка х₃ =1 относится к нижней строке таблицы (матрицы).

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

Для минимизации все клетки, содержащие 1, объединяются в замкнутые области с числом клеток 2, 4, 8… (в зависимости от числа переменных в ФАЛ). Области могут пересекаться, и одни и те же клетки могут входить в разные области. «Соседними» являются не только клетки, расположенные рядом по горизонтали и вертикали, но и клетки, находящиеся на противоположных границах карты. При охвате клеток замкнутыми областями следует стремиться к минимальному числу областей.

Действительно, для верхней области, охватывающей две 1 при , видно, что значение x₂ несущественно, т. к. ФАЛ равна 1 как при x₂, так и при , но обе 1 в булевом пространстве при лежат в области x₁. Аналогично для значения x₃ не существенно значение x₁, но обе 1 соответствуют x₂.

Для табл. 11 получим:

.

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

Такое представление хорошо воспринимается визуально благодаря симметрии по осям. В данном случае это оси «0-0» и «1-1». Эта симметрия позволяет легче находить области склеивания конституент, для которых значения какой-либо переменной x_i не влияет на значение ФАЛ. Речь идет о «ручной» минимизации с использованием визуального восприятия, что эффективно при n?6.

Для столь простого примера нельзя сделать четкий вывод в пользу того или иного способа кодирования булева пространства, но при числе переменных, равном 4, 6 и более, преимущества кода Грея будут очевидны при визуальном методе минимизации ФАЛ.

Минимизация ФАЛ базируется на использовании свойств карт Карно. Наборы значений переменных для соседних клеток карты Карно отличаются лишь одной переменной.

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

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

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

- для каждой клетки, в которой функция имеет значение 1, записывается конъюнкция всех входных переменных (прямых или инверсных);

- составляется дизъюнкция этих конъюнкций, которая и представляет собой СДНФ данной функции.

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

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

2. Площадь любого контура должна быть симметричной относительно границ переменных, пересекаемых данным контуром. Другими словами, число клеток в контуре должно быть равно 1, 2, 4, 8, 16, 32, ….

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

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

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

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

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

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

Рассмотрим пример ФАЛ для шести переменных (табл. 12).

Все области «1», объединенные двойными линиями, представляют один интервал ФАЛ, для которого по горизонтали очевидна независимость от x₁ и x₃, а по вертикали от x₄ и x₆, т.е. весь интервал соответствует . Верхняя область, объединенная сплошным овалом в одну линию по горизонтали, соответствует x₂x₃, а по вертикали , т.е. , а нижняя соответствует , тогда получим:

.

Последняя запись в скобках для х₃ и х₆ как уже говорилось называется функцией (обозначим Ж) суммы по модулю 2 и обозначаются символом . Другое название функции Ж - функция неравнозначности, т. к. она принимает значение 1 только при различных значениях переменных.

.

Заметим, что обратная ей функция имеет вид:

.

Эта функция называется функцией тождественности, т. к. она принимает значение 1 только при одинаковых (тождественных «0» и «1») значениях переменных

.

Тогда выражение для y можно записать в виде

.

Существуют функции, значение которых неопределенно на некоторых наборах входных переменных, т.е. некая комбинация, например , не может быть реализована. Практических примеров таких булевых функций много, особенно для реальных технологических процессов. Все такие комбинации переменных также наносятся на карту Карно и отмечаются символом, отличающимся от символа «0» или «1», с целью получения минимальной формы булевых функций. Такие булевы функции называются не полностью определенными.

Размещено на Allbest.ru