Схемы из функциональных элементов

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

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

Будем изображать такие элементы в виде:

&

Здесь стрелки, ведущие в ф.э. (входы элементов), представляют каналы, по которым в такие ф.э. поступают значения переменных.

По стрелкам, выходящим из ф.э. (выходам элемента), выдаются значения функций, вычисляемых элементами.

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

Из отдельных элементов строятся схемы из функциональных элементов (с.ф.э.), которые удовлетворяют следующим требованиям:

1) схема имеет конечное число входов, помеченных символами переменных;

2) выходы всякого входа схемы или элемента схемы могут разветвляться;

3) на всякий вход каждого функционального элемента в схеме подается ровно один выход входа схемы или выход другого функционального элемента;

4) ориентированные дуги, соединяющие функциональные элементы, не могут образовывать циклы.

Примером с.ф.э. может служить схема, приведенная на рис. 4.1.

x₁ x₂ x₃

&

&

Рис. 4.1

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

Например, нетрудно проверить, что приведенная ранее с.ф.э. вычисляет функцию, представляемую формулой:

В дальнейшем будем рассматривать только такие с.ф.э., которые имеют ровно один выход.

Поскольку всякая б.ф. может быть представлена с помощью формулы над множеством функций {&, Ú,` }, то с помощью схем, составленных из функциональных элементов, можно вычислять любую б.ф.

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

Сложностью произвольной с.ф.э. S называется число входящих в нее элементов & и Ú. Сложность схемы S обозначается как L(S).

Пусть f(x₁, . . . , x_n) - некоторая б.ф. Предположим, что f отлична от тождественного нуля. Возьмем СДНФ для f, по которой построим с.ф.э., вычисляющую f, и определим сложность такой схемы.

f(x₁, . . . , x_n) = .

Представим СДНФ для f в виде K₁ . . . K_r, где r - число наборов, на которых f принимает значение 1, а K₁, . . . , K_r - все различные конъюнкции ранга n, принимающие значение 1 на таких наборах.

Для каждой конъюнкции K_i= построим с.ф.э. S_k, вычисляющую эту конъюнкцию (рис. 4.2):

x₁ x₂ . . . x_n

_{1 2 n}

&

. . .

&

Рис.4.2

В приведенной схеме использовано специальное обозначение s , представляющее фрагмент схемы, имеющий вид:

, если s = 0

Здесь s =

, в противном случае.

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

Схема, реализующая конъюнкцию S_k, имеет сложность, равную n - 1 .

Пусть построены схемы S₁, . . ., S_k, вычисляющие все конъюнкции из СДНФ для f. Тогда f реализуется схемой S_f, представленной на рис.4.3:

x₁ x₂ x_n

. . .

. . . . . . . . .

S₁ S₂. . .S_r

Ú

. . .

Ú

f

Рис 4.3

Определим число функциональных элементов & иÚ, входящих в S_f.

Понятно, что L(S_f) = + r - 1 = (n - 1) r + r - 1.

В общем случае значение r может изменяться в пределах
от 1 до 2ⁿ. Если остановиться на “среднем“ случае, когда f принимает значение 1 на половине наборов значений переменных, то r = 2^{n - 1} .

Полученное значение сложности с.ф.э. оказывается слишком большим для того, чтобы схему для практически важных булевских функций можно было считать реализуемой. Например, уже для n = 16 значение L(S_f) имеет величину, близкую к 16 2¹⁵ = 2¹⁹. Последнее значение превосходит 500000.

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

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

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

МИНИМАЛЬНЫЕ ДНФ

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

ОПРЕДЕЛЕНИЕ

Дизъюнктивной нормальной формой (ДНФ) называется всякая формула вида D = K₁ . . . K_r , где K₁, . . . , K_r - это произвольные элементарные конъюнкции.

ОПРЕДЕЛЕНИЕ

Сложностью ДНФ D называется число вхождений в D функций & и . Для обозначения сложности ДНФ используется выражение L(D).

Например, следующая формула является ДНФ:

.

Сложность этой ДНФ равна 8.

Одна и та же булевская функция может представляться различными ДНФ.

Например, две ДНФ:

U = и

W = представляют одну и ту же б.ф.

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

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

ОПРЕДЕЛЕНИЕ

ДНФ D, представляющая функцию f, называется минимальной ДНФ для этой функции, если L(D) = min(L(D*)), где минимум берется по всем ДНФ D* , представляющим функцию f.

То есть сложность минимальной ДНФ для f является наименьшей среди сложностей всех ДНФ, представляющих функцию f.

ТЕОРЕМА 4.2. Для каждой б.ф. f, отличной от тождественного нуля, существует минимальная ДНФ.

Доказательство

1. Заметим, что всякая f, отличная от тождественного нуля, представляется хотя бы одной ДНФ (например, это может быть СДНФ).

2. Если задана б.ф. f(x₁, . . . , x_n), то нетрудно проверить, что существует ровно3ⁿ -1 конъюнкций разных рангов, составленных только на основе переменных функции f.

Действительно, каждая из переменных f может либо не входить в элементарную конъюнкцию, либо входить в неё без отрицания, либо входить в такую конъюнкцию с отрицанием. Всего таких вариантов для n переменных ровно 3ⁿ. Их них невозможен случай, когда ни одна переменная не входит в элементарную конъюнкцию.

Из 3ⁿ - 1 различных конъюнкций с точностью до порядка вхождения элементарных конъюнкций можно составить ровно - 1 разных ДНФ.

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

3. Последовательно просматривая все - 1 ДНФ, составленные из переменных функции f, можно найти такую из них, которая представляет f и имеет минимальную сложность среди всех ДНФ, представляющих f.

Доказательство окончено.

Замечание. Метод нахождения минимальной ДНФ, предложенный в доказательстве теоремы, неприменим на практике, поскольку количество ДНФ, которое требуется проверить для нахождения минимальной ДНФ функции с n переменными, слишком велико. Например, для n =2 число ДНФ равно255, а n = 3число вариантов принимает значение свыше 10⁶. То есть функция числа вариантов, проверяемых ДНФ, слишком быстро растет и для булевских функций, используемых в таких приложениях, как электроника и информатика, оказывается необозримой.

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

Рассмотрим следующее семейство соотношений эквивалентности.

1. Правила поглощения:

и .

2. Правило склеивания: .

3. Правило обобщенного склеивания:

.

Здесь K, K¹, K² - произвольные конъюнкции, или тождественная единица.

Справедливость приведенных эквивалентностей проверяется непосредственно построением таблиц значений формул слева и справа в тождествах 1 - 3 для различных значений x, K, K¹, K².

В качестве примера применения приведенных правил рассмотрим процесс построения минимальной ДНФ для функции: f = x₁ ® (x₂ ® x₃).

Выпишем СДНФ для f:

Применяя правило склеивания к первым трем парам конъюнкций в СДНФ, последнюю формулу можно переписать в виде:

.

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

Теперь воспользуемся правилом обобщенного склеивания к первой и второй конъюнкциям последней формулы. При этом в качестве K¹ используется пустая конъюнкция - 1, а в качестве
K² - .

В результате получается формула: .

К конъюнкциям и применяем правило поглощения. В результате получим формулу: .

Еще два раза последовательно применим правила обобщенного склеивания и поглощения. Сначала для первой и третьей конъюнкций, а затем к тому, что получится, для второй и третьей.

Окончательная формула имеет вид: .

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