4.Основные законы и тождества булевой алгебры
Для булевой алгебры определены одна одноместная (унарная) операция “отрицание” и две двухместные (бинарные) операции конъюнкция и дизъюнкция (обозначаются «Ù», «Ú» соответственно). Приведем некоторые основные формулы.
Под бинарной операцией на множестве А, в общем случае понимают отображение декартового произведения множеств (А х А) в множество А. Иными словами, результат применения бинарной операции к любой упорядоченной паре элементов из А есть также элемент из множества А.
Под унарной операцией на множестве А понимают выделение (фиксацию) какого-либо элемента множества А.
Преобразование формул булевых функций применением только аксиом булевой алгебры малоэффективно. Для упрощения формул используется целый ряд соотношений. Из коммутативности и ассоциативности дизъюнкции следует, что дизъюнкция нескольких переменных может выполняться последовательно, причем порядок взятия дизъюнкции не влияет на результат. Формулы де Моргана:
Следствия из формул де Моргана:
Формулы для системы функций:
операция поглощения (х поглощает у): хÚху=х; или х(хÚу)=х.
операция склеивания: хуÚх
=х, или (хÚу)Ù(хÚ
)=х
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 соответствует конституента нуля
.СКНФ представляется как конъюнкция конституент нуля, соответствующих нулевым наборам функции.
6.Функционально полные системы булевых функций
Любая булева функция может быть представлена аналитически одной из нормальных форм (СДНФ, СКНФ). Последние используют ограниченное число элементарных булевых функций. Например, для СДНФ такими функциями являются «конъюнкция», «дизъюнкция» и «отрицание». Существуют системы булевых функций, с помощью которых можно аналитически представить любую сколь угодно сложную булеву функцию. Проектирование цифровых автоматов основано на знании таких систем булевых функций. Последнее особенно важно для разработки комплектов интегральных микросхем, из которых можно построить произвольный цифровой автомат. Проблема функциональной полноты является центральной проблемой функциональных построений в алгебре логики.
Определение. Функционально полной системой булевых функций (ФПСБФ) называется совокупность таких булевых функций {f1, f2,..., fk}, что произвольная булева функция fможет быть записана в виде формулы через функции этой совокупности.
К ФПСБФ следует отнести системы: {
, 
,НЕ}, { , 
, НЕ}.Определение свойств ФПСБФ основано на понятии замкнутого относительно операции суперпозиции класса функций. Класс булевых функций, функционально замкнутый по операции суперпозиции, есть множество функций, любая суперпозиция которых дает функцию, также принадлежащую этому множеству. Среди функционально замкнутых классов выделяют классы особого типа, называемые предполными, которые обладают следующим свойством. Предполный класс Sне совпадает с множеством P2 всех возможных булевых функций, однако, если в него включить любую, не входящую в S, булеву функцию, то новый функционально замкнутый класс будет совпадать с множеством P2. Проведенные исследования показали, что предполных классов пять, а для построения ФПСБФ необходимо и достаточно, чтобы ее функции не содержались полностью ни в одном из пяти предполных классов. Перечислим предполные классы булевых функций:
1) булевы функции, сохраняющие константу 0;
2) булевы функции, сохраняющие константу 1;
3) самодвойственные булевы функции;
4) линейные булевы функции;
5) монотонные булевы функции.
Определение. К булевым функциям, сохраняющим константу 0, относят такие булевы функции f(x1,x2,...,xn), для которых справедливо соотношение
f(0,..., 0)=0.
Примерами булевых функций, сохраняющих константу 0, являются функции f0 – f7 (табл. 6.).
Определение. К булевым функциям, сохраняющим константу 1, относят такие булевы функции f(x1,x2,...,xn), для которых справедливо соотношение f(1,1, ..., 1)=1.
Примерами булевых функций, сохраняющих константу 1, являются функции f1, f3, f5, f7 (табл. 6).
Прежде чем ввести понятие класса самодвойственных функций, дадим следующее определение.
Определение. Булевы функции f1(x1,x2,...,xn) и f2(x1,x2,...,xn), называются двойственными друг другу, если выполняется соотношение f1(x1,x2,...,xn) =
Двойственными являются функции из табл. 6 - f0 и f15 , f1 и f7 и т. д.
Определение. К самодвойственным булевым функциям относят такие булевы функции, которые двойственны по отношению к самим себе, т. е. справедливо соотношение f1(x1,x2,...,xn) =
.Если условиться называть противоположными наборами набор
и набор 
, то определение самодвойственных функций дадим следующее.Определение. Булева функция называется самодвойственной, если на любых двух противоположных наборах она принимает противоположные значения.
Самодвойственными являются функции f3, f5, f10, f12 из табл. 6.. Из определения самодвойственной функции следует, что она полностью определяется своими значениями на первой половине строк таблицы истинности.
Определение. К линейным булевым функциям относят такие булевы функции, которые представимы в виде
f(x1,x2,...,xn)=с0
с1х1 ... сnхn,где сі
{0, 1}, а - операция «сумма по mod2».