Cтраница 2
Что касается системы логических элементов, то к ней предъявляется требование функциональной полноты, которое предусматривает возможность реализации любой булевой функции с помощью логических элементов из данной системы. [16]
Известно [54], что существует такой способ реализации произвольной булевой функции в схеме из пороговых элементов, при котором топология схемы фиксирована и схема настраивается на вычисление любой булевой функции fn за счет выбора значений весов и порогов элементов, входящих в схему. Значит, количество информации, описывающее такую схему, равно суммарному количеству информации, задающей значение весов и порогов всех элементов схемы, без указания информации о соединении элементов в схеме. [17]
Широкий набор базисов открывает большие возможности при решении задач минимизации схем устройств дискретного действия, поскольку из базисных схем с помощью суперпозиций можно составить схему, соответствующую любой булевой функции. [18]
Таким образом, правило композиции для функций класса МНФ то же самое, что и в § 1; отличие состоит лишь в том, что вместо любых булевых функций рассматривается одна фиксированная функция: мажоритарная. Возникает вопрос - сужается ли при этом класс представимых указанным образом функций. Совпадает ли класс МНФ с множеством всех функций выбора или с одним из ранее рассмотренных классов. [19]
Пессимизм в отношении возможностей О бщих методов дискретного программирования, например, в логическом синтезе порожден в известной мере тем, что от методов требуется умение оптимизировать схему, отвечающую любой булевой функции п переменных или любому конечному автомату с заданным числом входов и внутренних состояний. Между тем, можно полагать, что класс булевых функций или автоматов, с которыми связано про-ектирование устройств, решающих ограниченные классы задач, далеко не исчерпывает множества всех операторов данной раз-мерности. [20]
Итак, для каждой булевой функции от п переменных имеется хотя бы один полином Жегалкина, который реализует эту функцию и, вместе с тем, число различных полиномов Жегалкина от п переменных равно числу всех булевых функций от п переменных. Это означает, что для любой булевой функции существует только один реализующий ее полином Жегалкина. [21]
По традиции, сложившейся в отечественной школе дискретной математики, булевы функции рассматриваются с точностью до несущественных переменных. Это означает, что наряду с любой булевой функцией / считаются одновременно заданными все функции, которые получаются из / введением или удалением несущественных переменных. Иногда такие функции называют равными, хотя, строго говоря, они различаются уже как функции, имеющие различные количества переменных. Мы в дальнейшем не будем употреблять термин равные в этом смысле. [22]
Из рассмотрения всех приведенных кортежей вытекает, кстати, что все пять определенных нами двухместных булевых функций ( произведение, дизъюнкция, сумма и две импликации) являются попарно различными. Легко понять, что кортеж для отрицания любой булевой функции получается из кортежа для самой этой функции заменой всех единиц нулями и всех нулей единицами. [23]
Основным понятием булевой алгебры является понятие переключательной, или булевой, функции. Поскольку аргументы переключательной функции могут принимать только два значения, то область определения любой булевой функции всегда конечна. Совокупность значений этих аргументов называется набором. Для любой переключательной функции от п переменных существует число Z 2 различных наборов. Z 2 21 - число наборов, на которых функция определена. [24]
Еще одним примером полезности получения окончательных оценок в ситуациях, на первый взгляд весьма далеких от практики, может служить изучение инверсионной сложности булевых функций. Грубо говоря, инверсионная сложность - это минимальное количество элементов инверсии в базисе В0, достаточных для реализации любой булевой функции п переменных. [25]
Наиболее гибким и поэтому наиболее удобным в практических применениях является набор функций типа а b, а-и и а. В этом случае большинство функций алгебры логики записывается более компактно, а наличие простых электронных элементов, моделирующих операции И, ИЛИ, НЕ, позволяет сделать вывод о целесообразности в дальнейшем рассматривать только этот функционально-полный набор функций для представления любой булевой функции. [26]
Рассмотрим булевы функции от любого конечного числа аргументов. Если число аргументов равно п, то соответствующую функцию принято называть п-местной. Благодаря тому, что каждая булева переменная может принимать лишь два значения, область определения любой булевой функции будет непременно конечной. Легко видеть, что область определения n - местной булевой функции может состоять максимум из 2 различных элементов, представляющих собой всевозможные наборы значений п ее аргументов. В таком случае набор значений аргументов отождествляется с некоторым кортежем ( конечной упорядоченной последовательностью) нулей и единиц. Термин булев применительно к кортежу ( набору) означает, что соответствующий кортеж составлен из нулей и единиц. [27]
Проблема оптимизации таких схем по существу является задачей о булевых алгебрах. Мы поясним это утверждение в § 6.3 и 6.4, где будет описана общая методика синтеза вентильных схем, реализующих любую булевую функцию, из нескольких простых элементов. [28]
Из операций любого полного набора булевых операций должны строиться какие угодно булевы операции, в частности операции отрицания, дизъюнкции и умножения. Для того чтобы выполнить требуемое построение, достаточно, очевидно, с помощью операций рассматриваемого полного набора представить булеву функцию, определяющую требуемую операцию. Наоборот, если из операций некоторого набора можно построить операции отрицания и умножения или отрицания и дизъюнкции, то, ввиду сказанного выше, этого достаточно для возможности представления любой булевой функции и, следовательно, для полноты нашего набора. В результате приходим к следующему предложению. [29]
Для бинарных изображений существует еще один метод сглаживания, который часто позволяет добиться более точного контроля, чем при регуляризации. Этот метод называется логическим усреднением или логическим сглаживанием. Он основан на том, что элементы изображения, которые находятся в пределах усредняющего окна, могут трактоваться как булевы или логические переменные, и величина сглаженной функции интенсивности в точке может быть определена любой булевой функцией этих переменных. [30]