Системы функций алгебры логики

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

Функционально полной системой булевых функций (ФПСБФ) называется совокупность таких булевых функций (f₁, f₂, ... f_k), посредством которых можно записать произвольную булеву функцию f.

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

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

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

Теорема Жегалкина. Любая функция алгебры логики может быть представлена многочленом вида

,

где k_i – коэффициент, принимающий значения 0 или 1.

Теорема позволяет представить любую ФАЛ в виде полиномов различной степени.

Задача построения полинома Жегалкина сводится к нахождению коэффициентов k_i. Для любых конституент единицы k₁ и k₂ имеет место следующее соотношение: k₁ + k₂ = k₁  k₂. Оно позволяет выполнить переход от СДНФ к полиному Жегалкина. Для этого достаточно заменить в СДНФ символ + (дизъюнкции) на символ  и выполнить подстановку вида х=х  1 с последующими преобразованиями в алгебре Жегалкина.

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

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

.

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

Класс функций, сохраняющих ноль. К булевым функциям, сохраняющим константу 0, относят такие булевы функции f(x₁,...,x_n), для которых справедливо соотношение f(0,...,0)=0.

Класс функций, сохраняющих единицу. К булевым функциям, сохраняющим константу 1, относят такие булевы функции f(x₁,...,x_n), для которых справедливо соотношение f(1,...,1)=1.

Таблица 10

Класс монотонных функций. Функция алгебры логики называется монотонной, если при любом возрастании набора аргументов значения этой функции не убывают. Двоичный набор A=<a₁,a₂,...,a_n> не меньше двоичного набора B=<b₁,b₂,...,b_n> , если для каждой пары (a_i,b_i) i = 1...n справедливо соотношение a_i ≥ b_i.

Если у двух наборов есть и большие и меньшие аргументы f(0,1) и f(1,0), то наборы считаются несравнимыми. Таким образом, если f(0,0)≥f(0,1) ≥ f(1,1) или f(0,0) ≥f(1,0) ≥f(1,1), то функция f является монотонной.

Класс самодвойственных функций. Булевы функции f₁(x₁,...,x_n) и f₂(x₁,...,x_n) называются двойственными друг другу, если выполняется соотношение

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

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

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

Теорема Поста−Яблонского. Для того чтобы система ФАЛ была полной, необходимо и достаточно, чтобы она содержала хотя бы одну функцию:

не являющуюся линейной;

не сохраняющую ноль;

не сохраняющую единицу;

не являющуюся монотонной;

не являющуюся самодвойственной.

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

Рассмотрим примеры ФПСБФ. Для удобства изложения материала сведем элементарные булевы функции двух переменных и некоторые функции одной переменной в таблицу (табл.11), классифицируя каждую из них по признакам принадлежности к предполным классам.

Таблица 11

Из таблицы видно, что каждая из функций F₈ и F₁₄ является ФПСБФ. Иными словами, используя, например, только булеву функцию F₁₄ - "штрих Шеффера", можно записать в виде формулы любую булеву функцию. Признаком функциональной полноты, очевидно, является наличие плюса в каждом столбце таблицы, хотя бы для одной из составляющих систему булевых функций. К таким ФСПБФ, наиболее распространенным в практике построения цифровых автоматов, следует отнести:

{Λ,V,не}, { Λ,,не}, { Λ,,1}, { Λ,не}, {V,не}.

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

{ Λ,}, { Λ,~}, { V, }, {V,~}, {}

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

Базис может быть избыточным и минимальным.

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

Функционально полным базисом является базис И, ИЛИ, НЕ. В то же время он функционально избыточен. Удаление из него элемента И или ИЛИ превращает его в минимальный базис.

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

.