86371 (Булевы функции), страница 2

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

Таблица 6

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

- одна и та же функция может быть представлена разными формулами;

- каждой формуле соответствует своя суперпозиция и, следовательно, своя схема соединений элементов;

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

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

1. 4.Основные законы и тождества булевой алгебры

Для булевой алгебры определены одна одноместная (унарная) операция “отрицание” и две двухместные (бинарные) операции конъюнкция и дизъюнкция (обозначаются «», «» соответственно). Приведем некоторые основные формулы.

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

Под унарной операцией на множестве А понимают выделение (фиксацию) какого-либо элемента множества А.

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

Следствия из формул де Моргана:

Формулы для системы функций:

операция поглощения (х поглощает у): хху=х; или х(ху)=х.

операция склеивания: хух =х, или (ху)(х )=х

1. 5.Аналитическое представление булевых функций

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

Конституентой единицы (коньюнктивным термом) называется функция f(x1,x2,...,xn), принимающая значение 1 только на единственном наборе.

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

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

Наборы, на которых функция f принимает значение 1, часто называются единичными, остальные — нулевыми наборами. Выписывать в СДНФ имеет смысл только конституенты единицы, соответствующие единичным наборам.

Пример. Выпишем СДНФ для функций, заданных таблицей истинности (табл. 7.).

fСДНФ(х1,х2,х3)=

fСКНФ(х1,х2,х3)=

Другая известная форма носит название совершенной конъюнктивной номальной формы (СКНФ). Она строится аналогично СДНФ.

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

Конституента нуля записывается в виде элементарной дизъюнкции всех переменных. Каждому набору соответствует своя конституента 0. Например, набору 0110 переменны х1,х2,х3,х4 соответствует конституента нуля .

СКНФ представляется как конъюнкция конституент нуля, соответствующих нулевым наборам функции.

1. 6.Функционально полные системы булевых функций

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

Определение. Функционально полной системой булевых функций (ФПСБФ) называется совокупность таких булевых функций {f1, f2,..., fk}, что произвольная булева функция f может быть записана в виде формулы через функции этой совокупности.

К ФПСБФ следует отнести системы: { , ,НЕ}, { , , НЕ}.

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