Булевы функции

• х + y = y + х, х у = у х (закон коммутативности);
• х + (у + z) = (х + у) + z, х(у z) = (х у)z (закон ассоциативности);
• x (y + z) = x y + x z (закон дистрибутивности).

Для упрощения  формул могут быть использованы следующие  соотношения: 
х + 0 = х; 
х 1 = х;  
х 0 = 0;  
х + х = 0;  
х х = х. 
Из коммутативности и ассоциативности дизъюнкции следует, что дизъюнкция нескольких переменных может выполняться последовательно, причем порядок взятия дизъюнкции не влияет на результат."

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

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

Конституента 1 - функция f(x₁, x₂, ... x_n) принимающая значение 1 только на единственном наборе.

 
Конституента 1 записывается как логическое произведение n различных булевых  переменных, некоторые из них могут  быть с отрицаниями. Например, х₁/х₂/х₃х₄ - элементарное логическое произведение, являющееся конституентой еденицы переменных х₁,х₂,х₃,х₄ принимает значение 1 на единственном наборе 1001. Понятно, что на остальных 15 наборах эта конституента единицы равна нулю. 
Ели вспомнить, что дизъюнкция равна 1, когда хотя бы одна из переменных принимает значение 1, то можно легко выразить любую булеву функцию как дизъюнкцию конституент единицы, соответствующих тем наборам, на которых функция равна 1. В более общем виде это можно записать следующим образом:  
 
Эта форма и есть СДНФ. Заметим, что наборы, на которых функция f принимает значение 1, часто называются единичными, остальные - нулевыми наборами. Выписывать в СДНФ имеет смысл толькр конституенты единицы, соответствующие единичным наборам. 
ПРИМЕР :

Таблица 2.1
х1х2х3	F1	F2
000	0	0
001	1	0
010	1	0
011	0	1
100	0	0
101	0	1
110	0	1
111	1	1

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

Конституента 0 - функция f(x₁, x₂, ... x_n) принимающая значение 0 только на единственном наборе.

 
Конституента нуля записывается в  виде элементарной дизъюнкции всех переменных. Каждому набору соответствует своя конституента 0. Например, набору 0110 переменных х₁х₂х₃х₄ соответствует конституента нуля х₁ v /х₂ v /х₃ v х₄. СКНФ представляется как конъюнкция конституент нуля, соответствующих нулевым наборам функции." 
ПРИМЕР. Для рассмотренных функций в табл. 2.1 построим СКНФ: 
F₁=(x₁ v x₂ v x₃) (x₁ v /x₂ v /x₃) (/x₁ v x₂ v x₃) (/x₁ v x₂ v /x₃) (/x₁ v /x₂ v x₃) 
F₂=(x₁ v x₂ v x₃) (x₁ v x₂ v /x₃) (x₁ v /x₂ v x₃) (/x₁ v x₂ v x₃)

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

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

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

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

1. булевы функции, сохраняющие константу 0;
2. булевы функции, сохраняющие константу 1;
3. самодвойственные булевы функции;
4. линейные булевы функции;
5. монотонные булевы функции;

Табл 3.1
х1х2	f0	f1	f2	f3	f4	f5	f6	f7	f8	f9	f10	f11	f12	f13	f14	f15
00  01  10  11	0  0  0  0	0  0  0  1	0  0  1  0	0  0  1  1	0  1  0  0	0  1  0  1	0  1  1  0	0  1  1  1	1  0  0  0	1  0  0  1	1  0  1  0	1  0  1  1	1  1  0  0	1  1  0  1	1  1  1  0	1  1  1  1

 

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

 
Примерами булевых функций, сохраняющих  константу 0, являются функции f₀, f₁,..., f₇ (табл 3.1). Поскольку таблица истинности для функций, сохраняющих константу 0, в первой строке значений функций содержит 0, то имеется ровно 2^{2(^n)-1} таких функций.

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

 
Примерами булевых функций, сохраняющих  константу 1, являются функции f₁, f₃, f₅, f₇, f₉, f₁₁, f₁₃, f₁₅ (табл 3.1). Поскольку таблица истинности для функций, сохраняющих константу 1, в последней строке значений функций содержит 1, то имеется ровно 2^{2(^n)-1} таких функций. 
Прежде чем ввести понятие класса самодвойстенных функций, дадим следующее определение.

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

f₁(x₁,...,x_n)=/(f₂(/x₁,...,/x_n))

 
Двойственными являются функции f₀ и f₁₅, f₁ и f₇, f₂ и f₁₁ и т.д. (табл 3.1).

К самодвойственным булевым функциям относят такие  булеы функции, которые двойственны  по отнощению к самим себе, т.е. справедливо соотношение f(x₁,...,x_n)=/(f(/x₁,...,/x_n)). Если условия назвать противоположными наборами, набор <y₁,y₂,...,y_n> и набор </y₁,/y₂,...,/y_n>, то определение самодвойственных функций дадим следующее.

 

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

 
Самодвойственными являются функции f₃, f₅, f₁₀, f₁₂ (табл 3.1). Из определения самодвойственной функции следует, что она полностью определяется своими значениями на первой половине строк таблицы истинности. Поэтому число всех самодвойственных булевых функций f(x₁,...,x_n) равно

 

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

f(x₁,...,x_n)=с₀ + c₁x₁ + ... + c_nx_n,

где c_i E {0,1}, а + операция "сумма по mod 2".

 
Линейными являются булевы функции f₀, f₃, f₅, f₆, f₉, f₁₀, f₁₂, f₁₅, (табл 3.1), ибо 
f₀ = 0, f₃ = x₁, f₅ = x₂, f₆ = x₁ + x₂, f₉ = x₁ + x₂ + 1, f₁₀ = /x₂ = 1 + x₂, f₁₂ = /x₁ = 1 + x₁, f₁₅ = 1. 
Примечание + = . 
Поскольку линейная функция однозначно определяется заданием коэффициентов с₀,...,с_n, то число линейных функций равно 2⁽ⁿ⁺¹⁾. 
Прежде чем ввести понятие класса монотонных булевых функций, дадим следующее определение.

Двоичный набор Y = <y₁,y₂,...,y_n> не меньше двоичного набора B = <b₁,b₂,...,b_n> , если для каждой пары (Y_i,B_i) i = 1...n справедливо соотношение Y_i >= B_i.

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

Булева функция f(x₁,...,x_n) называется монотонной, если для любых двух наборов Y = <y₁,y₂,...,y_n> и B = <b₁,b₂,...,b_n> таких, что Y >= B имеет место неравенство f(y₁,...,y_n)>=f(b₁,...,b_n).

 
Монотонными являются булевы функции f₀, f₁, f₃, f₅, f₇, f₁₅ (табл. 3.1). Вместе с тем функция f₂ из табл. 3.1 не является монотонной, так как f₂(1,0) > f₂(1,1), хотя набор <1,0> меньше, чем набор <1,1>. 
Приведем без доказательства две формулировки теоремы о функциональной полноте. 
Теорема.

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

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

 
Из таблицы видно, что каждая из функций f₈ и f₁₄ являются ФПСБФ. Иными словами, используя, например, только булеву функцию f₁₄ - "штрих Шеффера", можно записать в виде формулы любую булеву функцию. f₁₄ = х₁ / х₂ = /х₁ v /х₂. Признаком функциональной полноты, очевидно, является наличие плюса в каждом столбце таблицы, хотя бы для одной из составляющих систему булевых функций. К таким ФСПБФ, наиболее распостраненным в практике построения цифровых автоматов, следует отнести:  
 
Иногда удобно строить ФПСБФ при наличии констант, т.е. булевых функций "константа 0", "константа 1". Как следует из таблицы, функция "константа 0" несамодвойственна и не сохраняет 1; функция "константа 1" несамодвойственна и не сохраняет 0. Вместе с тем константы являютя линейными и монотонными функциями. Отсюда непосредственно (на основании теоремы о функциональной полноте) вытекает следующее: система булевых функций является ослабленно функционально полной, если она содержит хотя бы одну нелинейную и хотя бы одну нелинейную и хотя бы одну немонотонную булеву функцию. 
Примерами ослабленых ФПСБФ могут служить следующие системы: 
 
Введенное понятие двойственных булевых функций позволяет сформулировать принцып двойственности, заключающийся в следующем: если формула U=c[f₁,...,f_s] реализует булеву фунуцию f(x₁,...,x_n), то формула U*=c[f*₁,...,f*_n], полученная из U заменой функций f₁,...,f_s на двойственные функции f*₁,...,f*_s, соответтвенно реализует функцию f*=f*(x₁,...,x_n), двойственную функции f. Формулу U называют двойственной U. Для формул над множеством {0, 1, /x, x₁x₂, x₁ v x₂} принцип двойственности может быть сформулирован так: для получения формулы U* двойственной формуле U достаточно в формуле U всюду заменить 0 на 1, 1 на 0, & на \/, \/ на &. "