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

БУЛЕВА АЛГЕБРА

Логические функции, приведенные в табл. 2.1, можно рассматривать, как элементарные операции над одной или двумя двоичными переменными. Функционально полная система таких операций образует на множестве двузначных переменных алгебру логики. Таких алгебр можно представить столько же, сколько наберется подходящих функционально полных систем. Но наиболее распространена булева алгебра, в которой в качестве основных операций приняты конъюнкция х₁х₂ (И), дизъюнкция х₁+х₂ (ИЛИ) и отрицание `х (НЕ). Часто конъюнкцию и дизъюнкцию называют соответственно логическим произведением и суммой, а отрицание – инверсией. Используются также и другие варианты обозначений: для конъюнкции х₁Ùх₂, для дизъюнкции х₁Úх₂ и для отрицания х^/. Чтобы избежать в сложных формулах лишних скобок, которые появляются при суперпозиции функций, установлен жесткий порядок выполнения операций – конъюнкция предшествует дизъюнкции. Свойства булевых операций И, ИЛИ, НЕ определяются таблицами соответствующих функций (см. табл. 2.1) и могут быть представлены в виде

X1	X2	ù X1	X1 v X2	X1&X2
0	0	1	0	0
0	1	1	1	0
1	0	0	1	0
1	1	0	1	1

 

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

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

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

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

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

С принципом дуальности непосредственно связано обобщение законов де Моргана на любое число переменных. Если функция j^*(х₁, х₂,…, х_n) дуальная функции j (х₁, х₂,…, х_n), то

`j (х<sub>1</sub>, х<sub>2</sub>,…, х<sub>n</sub>) = j<sup>*</sup>(`х₁, `х<sub>2</sub>,…, `х_n),                            (2.1)

откуда следует, что отрицание некоторой функции можно определить заменой в дуальной функции каждой переменной ее отрицанием. Пусть, например, задана функция y = x +`vz. Дуальная ей у<sup>*</sup> = х (v+`z) и, следовательно, `у =`х (`v + z).

Из выражения (2.1) также следует, что дуальная функция выражается как отрицание исходной функции, в которой каждая переменная замещена ее отрицанием:

j^*(х₁, х₂,…, х_n) =`j (`х₁, `х<sub>2</sub>,…, `х_n).                                 (2.2)

                                                                                   Таблица 2.2

Свойство	Первая форма	Вторая форма
1. Коммутативность	Х+у=у+х	ху=ух
2. Ассоциативность	х+(y+z)=(x+y)+z	x(yz)=(xy)z
3. Дистрибутивность	x(y+z)=xy+xz	x+yz=(x+y)(x+z)
4. Дополнение	x+x=1	xx=0
5. Повтор переменной	x+0=x	x1=x
6. Повтор константы	x+1=1	x0=0
7. Двойное отрицание	X=x	x=x
8. Идемпотентность	x+x=x	xx=x
9. Законы де Моргана	x+y=xy	xy=x+y
10. Склеивание	xy+xy=x	(x+y)(x+y)=x
11. Поглошение	x+xy=x	x(x+y)=x
12. Замещение	x+xy=x+y	x(x+y)=xy
13. Выявление	xy+xz=xy+xz+yz	(x+y)(x+z)= =(x+y)(x+z)(y+z)

 

СТАНДАРТНЫЕ ФОРМЫ

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

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

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

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

Х1 0 0 0 0 1 1 1 1 Х2 0 0 1 1 0 0 1 1 Х3 0 1 0 1 0 1 0 1   У 0 1 1 0 1 1 0 1

             

 

 

 

У = `х<sub>1</sub>`х₂ х₃ + `х<sub>1</sub> х<sub>2</sub>`х₃ + х₁`х<sub>2</sub>`х₃ + х₁`х₂ х₃+ х₁х₂х₃=

 = (х₁ + х₂ + х₃) (х₁ +`х<sub>2</sub> +`х₃)(`х<sub>1</sub> +`х₂ + х₃).

 

Если булева функция задана логической формулой, то ее можно привести к стандартной форме последовательностью эквивалентных преобразований, основанных на свойствах булевой алгебры. Сначала с помощью теорем де Моргана исходное выражение приводится к такому виду, чтобы знаки отрицания относились только к отдельным переменным. Затем на основе свойств дистрибутивности осуществляется преобразование к одной из форм – сумме произведений или произведению сумм. На заключительном этапе используются свойства х +`х=1 и х`х=0 для введения недостающих переменных в минтермы и макстермы, а также свойства идемпотентности х+х=х и хх=х для исключения повторяющихся слагаемых и сомножителей.

 

          ПРЕОБРАЗОВАНИЕ И УПРОЩЕНИЕ ФОРМУЛ

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

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

Склеивание х у + х`у = х (под х можно понимать любое выражение) позволяет заменить два минтерма, отличающихся вхождением только одной переменной (с отрицанием и без него), одним минтермом более низкого ранга. Пусть, например, функция задана в виде канонической суммы минтермов: у=`х₁ х₂`х<sub>3</sub> + `х₁ х₂ х₃ + х₁`х<sub>2</sub>`х₃ + х₁`х<sub>2</sub> х<sub>3</sub> + х<sub>1</sub>х<sub>2</sub>х<sub>3</sub>. Группируя члены и применяя операцию склеивания, имеем у= (`х₁ х₂`х<sub>3</sub> +`х₁х₂х₃ )+ (х₁`х<sub>2</sub>`х₃ + х₁`х<sub>2</sub> х<sub>3</sub>)+ х<sub>1</sub>х<sub>2</sub>х<sub>3</sub>=`х₁ х₂ + х₁`х<sub>2</sub> + х<sub>1</sub>х<sub>2</sub>х<sub>3</sub>. При другом варианте группирования получим у=`х₁ х₂`х<sub>3</sub> + (х<sub>1</sub>х<sub>2</sub>х<sub>3</sub> + х<sub>1</sub>х<sub>2</sub>х<sub>3</sub> )+ (х<sub>1</sub>`х₂`х<sub>3</sub> + х<sub>1</sub>`х₂ х₃)= `х<sub>1</sub> х<sub>2</sub>`х₃ + х₁ х₂+х₁`х₂.

Последующие упрощения основаны на свойствах поглощения и выявления. Поглощение х+ху=х, если под х и у понимать не только переменные, но и любые булевы выражения, позволяет исключить все минтермы, в которые в качестве сомножителя входит некоторый другой минтерм более низкого ранга. Наряду с этим дополнительный член, можно использовать для поглощения и/или замещения других членов (минтермов). Эта операция, называемая обобщенным склеиванием, всегда возможна, если исходная формула наряду с порождающими членами содержит минтермы, в которые в качстве сомножителя входит дополнительный член, например:

 

xy+xz+yzv=xy+xz+yzv+yz=xy+xz+yz=xy+xz

            yz – дополнительный член поглощение выявление

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

Например:

                     х +`xy + yz = x +`xy + yz + y = x +`xy + y = x + y

у-дополнительный член поглощение замещение

 

     Здесь дополнительный член поглощает минтерм yz и замещает породивший его минтерм `ху. Заметим, что это выражение можно было бы упростить и без введения дополнительного члена с помощью поглощения и замещения: х +`ху + yz = х + у + yz = х + у.

Применяя изложенную процедуру к рассматриваемому примеру для первого варианта группирования `х<sub>1</sub> х<sub>2</sub> + х<sub>1</sub>`х₂ + х₁ х₂ х₃, получаем `х<sub>1</sub> х<sub>2</sub> + х<sub>1</sub>`х₂ + х₂ х₃ или `х<sub>1</sub> х<sub>2</sub> + х<sub>1</sub>`х₂ + х₁ х₃. Аналогично второй вариант `х<sub>1</sub> х<sub>2</sub>`х₃ + х₂ х₃ + х₁`х<sub>2</sub> упрощается к виду  `х₁ х₂ + х₂ х₃ + х₁`х<sub>2</sub>, что повторяет уже полученный результат для первого варианта. Таким образом, исходная формула преобразуется к двум формам, которые в данном случае являются и минимальными. К такому же результату можно было бы прийти, применяя только простое склеивание, если в исходном выражении повторить минтерм `х₁х₂х₃ и х₁`х<sub>2</sub> х<sub>3</sub>, о чем, конечно, не так просто догадаться в самом начале преобразования. Следует заметить, что с применением обобщенного склеивания можно упрощать формулы, заданные в любой форме, а не обязательно в канонической. В то же время эта операция не подходит, если порождающие члены содержат различное вхождение (с отрицание и без него) не одной, а двух или больше переменных. Например, х(yz) +`х(`yz), так как при этом дополнительный член (yz) (`yz) обращается в тождественный нуль.

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

 

 

МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ С ПОМОЩЬЮ ПОЗИЦИОННЫХ КАРТ

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

     На рис. 2.1 приведены примера позиционных карт для трех переменных (а), для четырех переменных (б) и для пяти переменных (в).

 

Рис.2.1.

     Операции склеивания двух минтермов n-го ранга исходной формулы соответствует на карте Карно объединение двух соседних ячеек, отмеченных единицами, и эта объединенная пара ячеек представляет собой результат (n-1)-го ранга. Аналогич­но склеивание двух минтермов (n-1)-го ранга в минтерм (n-2)-го ранга представляется объединением соответствующих пар ячеек и т.д.  

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

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

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

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

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

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

Модифицированные позиционные карты представляют собой правильный прямоугольник (с соотношением сторон 1:1 при четном количестве переменных или 1:2 - при нечетном). Главным отличием рассматривае­мых карт является обозначение переменных в виде разрывных линий.

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

 

 

Рис. 2.2

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

                                               S = 2^{(n - r)},

где n - количество переменных,

r - ранг конъюнкции, т.е. количество переменных, входящих в конъюнкции.

На рис.2.3 приведены примеры правильных конфигураций.

 

 

 

Рис.2.3

 

Алгоритм минимизации логических функций состоит из следующих этапов.

1. Рассматриваются правильные конфигурации r=1.

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

3. Проверяют все ли ячейки склеены, если да, то процесс минимизации окончен.

4. Повторяют п.п. 1, 2, 3 для r=2, …, n.