9.3. ФУНКЦИОНАЛЬНО ПОЛНЫЕ СИСТЕМЫ БУЛЕВЫХ ФУНКЦИЙ

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

Определение. Функционально полной системой булевых функций (ФПСБФ) называется совокупность таких булевых функций

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

Исходя из определения к следует отнести системы:

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

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

Перечислим предполные классы булевых функций]

1) булевы функции, сохраняющие константу 0;

2) булевы функции, сохраняющие константу 1;

3) самодвойственные булевы функции;

4) линейные булевы функции;

5) монотонные булевы функции.

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

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

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

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

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

Определение. Булевы функции называются двойственными друг другу, если выполняется соотношение

Двойственными являются функции (табл. 9.8).

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

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

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

Определение. К линейным булевым функциям относят такие булевы функции, которые представимы в виде

где — операция «сумма по

Линейными являются булевы функции (табл. 9.8), ибо

Поскольку линейная функция однозначно определяется заданием коэффициентов си то число линейных функций равно

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

Определение. Двоичный набор а не меньше двоичного набора (т. е. ), если для каждой пары справедливо соотношение

Так, набор 1011 1010. Вместе с тем наборы 1011 и несравнимы и том смысле, что для них не выполняется ни соотношение а ,

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

Моионжмымн являются булевы функции (табл. 9.8). Имеете с тем функция из табл. 9.8 не является монотонной, чек как , хотя набор меньше, чем набор

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

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

Таблица 9.10

содержала хотя бы одну булеву функцию, сохраняющую константу I, хотя бы одну булеву функцию, не сохраняющую константу 1, хотя бы одну несамодиойственную булеву функцию, хотя бы одну нелинейную булеву функцию и хотя бы одну немонотонную булеву функцию.

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

Рассмотрим примеры Для удобства изложения материала сведем элементарные булевы функции двух переменных и некоторые функции одной переменной в табл. 9.10, классифицируя каждую из них по признакам принадлежности к предполным классам. Из табл. 9.10 видно, что каждая из функций являются Иными словами, используя, например, только булеву функцию — «штрих Шеффера», можно записать в виде формулы любую булеву функцию. Табл. 9.10 позволяет получить и другие Признаком функциональной полноты является, очевидно, наличие плюса в каждом столбце табл. 9.10, хотя бы для одной из составляющих систему булевых функций. К таким наиболее распространенным в прак тике построения цифровых автоматов, следует отнести: где символами обозначены булевы функции; «дизъюнкция», «конъюнкция», «сумма по «отрицание», «константа 1», соответственно.

Иногда удобно строить при наличии констант, т. е. булевых функций «константа 0» и «константа I». Как следует из табл. 9.10, функция «константа 0» несамодвойственна и не сохраняет 1; функция «константа 1» несамодвойственна и не сохраняет 0. Вместе с тем константы являются линейными и монотонными функциями. Отсюда непосредственно (на основании теоремы о функциональной полноте) вытекает следующее: система булевых функций является ослаблснно функционально полной, если она содержит хотя бы одну нелинейную и хотя бы одну немонотонную булеву функции.

Примерами ослабленных могут служить следующие системы:

где символами обозначены булевы функции «эквивалентность» и «импликация», соответственно.

Введенное понятие двойственных булевых функций позволяет сформулировать принцип двойственности, заключающийся в следующем: если формула реализует булеву функцию то формула полученная из заменой функций на двойственные функции соответственно реализует функцию двойственную функции Формулу называют двойственной Для формул над множеством принцип двойственности может быть сформулирован так: для получения формулы двойственной формуле достаточно в формуле всюду заменить 0 на

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