Тождественные преобразования

Геометрическое представление.Область определения булевых функций от п переменных у = f(х₁, x₂, ...,x_n) можно рассматривать как совокупность n-мерных векторов (слов длины n), компонентами которых являются буквы 0 и 1 двоичного алфавита. При п = 3 каждый вектор представляется вершиной единичного куба в трехмерном пространстве (рис. 20). В общем случае совокупность векторов (х₁, x₂, ...,x_n) отображается на множество вершин n-мерного куба.Всетакие вершины образуют логическое пространство.

Булева функция отображается на n-мерном кубе путем выделения вершин, соответствующих векторам (х₁, x₂, ...,x_n) на которых булева функция у = f(х₁, x₂, ...,x_n) принимает значения 1. Обычно такие вершины отмечают жирными точками. Так, на рис. 20 отображена функция в соответствии с таблицей из (8).

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

Данная формула приводится к нормальной форме следующими путем: 1) с помощью законов де Моргана формула преобразуется! к такому виду, чтобы знаки отрицания относились только к отдельным переменным; 2) на основе первого (второго) дистрибутивного закона формула сводится к дизъюнкции конъюнкций (конъюнкции дизъюнкций); 3) полученное выражение упрощается в соответствии с тождествамихх = хи =0 и ).

Пример: (дизъюнктивная нормальная форма); (конъюнктивная нормальная форма).

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

Если исходная формула содержит другие операции, то они предварительно выражаются через дизъюнкцию, конъюнкцию и отрицание, например:

Совершенные нормальные формы. Если в каждом члене нормальной формы представлены все переменные (либо в прямом, либо в инверсном виде), то она называется совершенной нормальной формой.

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

Продолжая второй пример из (2), приведем данную функцию к совершенной дизъюнктивной нормальной форме: . Приведение к совершенной конъюнктивной нормальной форме иллюстрируется следующим примером:

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

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

При большом количестве переменных такой способ практически неосуществим из-за огромного числа возможных наборов значений переменных. Более удобный путь - приведение формулы к нормальной форме. Если в процессе такого приведения формула не обращается в тождественный 0 или 1, то это свидетельствует о ее выполнимости.

Конституенты и представление функций. Для совокупности переменных х₁, х₂, ..., х_n выражение называют конституентой единицы, а выражение - конституентой нуля ( означает либо x_i, либо ). Данная конституента единицы (нуля) обращается в единицу (нуль) только при одном соответствующем ей наборе значений переменных, который получается, если все переменные принять равными единице (нулю), а их отрицания - нулю (единице). Например, конституенте единицы соответствует набор (1011), а конституенте нуля - набор (1001).

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

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

соответствуют совершенные нормальные формы:

.

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

Упрощение формул

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

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

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

Например, функция из (3) упрощается следующим образом:

.

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

Каноническая задача синтеза логических схем в булевом базисе сводится к минимизации булевых функций, т. е. к представлению их в дизъюнктивной нормальной форме, которая содержит наименьшее число букв (переменных и их отрицаний). Такие формы называют минимальными. При каноническом синтезе предполагается, что на входы схемы подаются как сигналы х_i, так и их инверсии `x_i. Формула, представленная в дизъюнктивной нормальной форме, упрощается многократным применением операции склеивания и операций поглощения и (дуальные тождества для конъюнктивной нормальной формы имеют вид: ; ). Здесь под a и b можно понимать любую формулу булевой алгебры. В результате приходим к такому аналитическому выражению, когда дальнейшие преобразования оказываются уже невозможными, т. е. получаем тупиковую форму. Среди тупиковых форм находится и минимальная дизъюнктивная форма, причем она может быть неединственной. Чтобы убедиться в том, что данная тупиковая форма является минимальной, необходимо найти все тупиковые формы и сравнить их по числу входящих в них букв.

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

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

Многомерный куб. Каждой вершине n-мерного куба (1. 9), можно поставить в соответствие конституенту единицы (2, 5). Следовательно, подмножество отмеченных вершин является отображением на n-мерном кубе булевой функции от п переменных в совершенной дизъюнктивной нормальной форме. На рис. 21 показано такое отображение для функции из (5).

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

Минитерм (n - 1)-го ранга можно рассматривать как результат склеивания двух минитермовn-го ранга (конституент единицы), т. е. .На n-мерном кубе это соответствует замене двух вершин, которые отличаются только значениями координаты x_i, соединяющим эти вершины ребром (говорят, что ребро покрывает инцидентные ему вершины). Таким образом, минитермам (n - 1)-го порядка соответствуют ребра n-мерного куба. Аналогично устанавливается соответствие минитермов (п - 2)-го порядка граням n-мерного куба, каждая из которых покрывает четыре вершины (и четыре ребра).

Элементы n-мерного куба, характеризующиеся s измерениями, называют s-кубами. Так, вершины являются 0-кубами, ребра - 1-кубами, грани - 2-кубами и т. д. Обобщая приведенные рассуждения, можно считать, что Минитерм (п - s)-го ранга в дизъюнктивной нормальной форме для функции п переменных отображается s-кубом, причем каждый s-куб покрывает все те s-кубы низшей размерности, которые связаны только с его вершинами. В качестве

примера на рис. 22 дано отображение функции трех переменных .Здесь минитермы и соответствуют 1-кубам (s = 3 – 2 = 1), а минитерм отображается 2-кубом (s = 3 - 1 = 2).

Итак, любая дизъюнктивная нормальная форма отображается на n-мерном кубе совокупностью s-кубов, которые покрывают все вершины, соответствующие конституентам единицы (0-кубы). Справедливо и обратное утверждение: если некоторая совокупность s-кубов покрывает множество всех вершин, соответствующих единичным значениям функции, то дизъюнкция соответствующих этим s-кубам минитермов является выражением данной функции в дизъюнктивной нормальной форме. Говорят, что такая совокупность s-кубов (или соответствующих им минитермов) образует покрытие функции.

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

Отображение функции на n-мерном кубе наглядно и просто при п3. Четырехмерный куб можно изобразить, как показано на

а б в

Рис. 23. Покрытие функции :

а – неминимальное; б, в – минимальное.

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

Рис. 24. Отображение функции на

четырехмерном кубе

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

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

Между отображениями функции на n-мерном кубе и на карте Карно имеет место взаимно-однозначное соответствие. На карте Карно s-кубу соответствует совокупность 2 соседних клеток, размещенных в строке, столбце, квадрате или прямоугольнике (с учетом соседства противоположных краев карты). Поэтому все положения, изложенные в (6), справедливы и для карт Карно.

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

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

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

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

Комплекс кубов K(у) функции у = f(х₁, х₂, ..., х_n) определяется как объединение множеств K^s(у) всех ее s-кубов (s = 0, 1, .... n), т. е. , причем некоторые из K^s(у) могут быть пустыми. Для записи s-кубов и минитермов функции от п переменных используются слова длины п, буквы которых соответствуют всем n переменным. Входящие в минитерм переменные называются связанными и представляются значениями, при которых минитерм равен единице (1 для x_i и 0 для ). Не входящие в минитерм переменные являются свободными и обозначаются через х. Например, 2-куб функции пяти переменных, соответствующий минитерму , запишется как (x10x1). 0-кубы, соответствующие конституентам единицы, представляются наборами значений переменных, на которых функция равна единице. Очевидно, в записи s-куба всегда имеется s свободных переменных. Если все п переменных свободны, что соответствует n-кубу, то это означает тождественность единице рассматриваемой функции. Таким образом, для функций, не равных тождественно единице, .

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

; ;

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

которое соответствует . В данном случае это покрытие являетcя и минимальным.

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

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

Реализация в различных формах. Реализация функции в дизъюнктивной нормальной форме представляет собой логическую схему И-ИЛИ. Например, функция реализуется логической схемой. Более экономичная реализация получается, если общий множитель вынести за скобки: . При использовании элементов со многими входами получаем двухуровневую логическую схему И—ИЛИ.

В соответствии с принципом двойственности (2.1), заменяя в дизъюнктивной нормальной форме операции конъюнкции на дизъюнкции, операции дизъюнкции на конъюнкции и беря отрицание каждой переменной, получаем конъюнктивную нормальную форму, которая выражает функцию , обратную к у. Ее реализация с помощью многовходовых элементов представляет собой двухуровневую логическую схему ИЛИ—И. Для рассматриваемой функции соответствующая реализация показана на рис. 26, г. Если требуется получить схему для данной функции у, то используется инвертор или элемент, реализующей операцию НЕ—И.

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

; ,

а их покрытия

; .

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

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

Задача сводится к выбору для каждой функции такого покрытия, которое включало бы возможно большее число s-кубов, содержащихся в покрытиях других функций. Этому требованию удовлетворяют, например, покрытия для трех функций, которому соответствует трехвыходная схема. Если бы для функции y₃ было выбрано другое покрытие, то схема получилась бы менее экономичной.

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

Постановка задачи. Минимизация схемы в булевом базисе сводится к поиску минимальной дизъюнктивной формы, которой соответствует минимальное покрытие. Общее число букв, входящих в нормальную форму, выражается ценой покрытия - число s-кубов, образующих покрытие даннойфункции от п переменных. Используются и другие определения цены покрытия, например с’ = с + q, где q - общее число всех кубов покрытия. Во всех случаях минимальное покрытие характеризуется наименьшим значением его цены.

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

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

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

Сокращенное покрытие Z, и минимальные покрытия С’_min и C”_min выражаются следующим образом:

; ; .

Сокращенная форма представляет собой дизъюнкцию четырех простых импликант, т. е. . Экстремалями являются простые импликанты и , которым соответствуют 1-кубы (10x) и (01x), а отмеченные вершины - и или соответственно (100) и (010).

Метод Квайна - Мак-Класки. Этот метод используется в случаях, когда функция задана в дизъюнктивной совершенной нормальной форме (или таблицей соответствия). Приведение к сокращенной форме осуществляется последовательным применением операции склеивания , где a - конъюнкции переменных, отличных от x_i. Множеству конституент единицы, представленных в исходной форме, соответствует совокупность 0-кубов K⁰, а операции склеивания - объединение двух 0-кубов, которые отличаются только одной координатой. Результатом такого объединения является 1-куб, в котором различные координаты исходных 0-кубов замещены символом х. Сравнивая попарно все 0-кубы, получаем множество 1-кубов K¹. Применяя к K¹ операцию склеивания, находим множество 2-кубов K² и т. д. Этот процесс продолжается до тех пор, пока получаемое из K^s очередное K^s+1 не окажется пустым множеством. В результате множество K⁰ преобразуется в комплекс кубов К = { K⁰, K¹, K², …, K^s], причем .

Для выделения из К множества простых импликантпри каждой операции склеивания необходимо отмечать каким-либо знаком (например, меткой ) те кубы, которые объединяются в кубы высшей размерности. Очевидно, неотмеченные кубы и образуют множество простых импликант Z. Чтобы уменьшить число сравниваемых пар при операции объединения целесообразно разбить множество K^s на классы, в каждом из которых содержатся s-кубы с одинаковым числом единиц (или нулей), и упорядочить эти классы по возрастающему числу единиц. Так как объединяться могут только такие два s-куба, число единиц в которых точнонаодну больше или меньше, то достаточно ограничиться попарным сравнением s-кубов одного класса с s-кубами соседнего класса.

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

Пример минимизации функции. Рассмотрим в качестве примера функцию четырех переменных у = f(х₁, х₂, х₃, х₄), заданную таблицей соответствия

Ей соответствует дизъюнктивная совершенная нормальная форма . Множество 0-кубов после разбиения и упорядочения записывается следующим образом:

.

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

; .

Простым импликантам соответствуют неотмеченные кубы.Составляем таблицу покрытия Z, которому соответствует сокращенная форма .

K0     Z									Обозначения импликант
0 x 1 1									A
0 1 x 1									B
x 0 1 1									C
1 0 x 1									D
1 x 0 1									E
x 1 0 x									F

Извлекаем единственную экстремаль (х10х), которой соответствует минитерм и упрощаем таблицу к виду:

K0 Z
0 x 1 1
0 1 x 1
x 0 1 1
1 0 x 1
1 x 0 1

В качестве дополнительных целесообразно выбрать кубы (0x11) и (10x1), так как они совместно с экстремалью (x10x) образуют покрытие функции, минимальная форма которой имеет вид: . Соответствующее этой функции минимальное покрытие иллюстрируется на четырехмерном кубе и на карте Карно.