Приложение булевой алгебры к синтезу комбинационных схем

логические константы;

переменные;

операции;

выражения;

функции;

законы.

Операции
Основными операциями булевой алгебры являются:

отрицание (инверсия);

конъюнкция (логическое умножение);

дизъюнкция (логическое сложение).

Отрицание

Конъюнкция a&b, a ⋅ b, a* b, ab, a ∧ b;

Дизъюнкция a ∨ b.

Функции

Булевой (логической) функцией называется функция, аргументами которой являются булевы переменные, а сама функция принимает значение из множества {0,1}.

аналитической;

табличной;

графической;

таблично-графической;

числовой;

символической.

3. Дистрибутивные (распределительные) законы:

4. Закон двойного отрицания:

5. Законы тавтологии (идемпотентности):

6. Законы нулевого элемента:

Большинство законов задается парой соотношений (дуальность законов булевой алгебры).
Некоторые законы можно распространять на произвольное число элементов.

9. Законы двойственности (де Моргана):

Следствия:

10. Законы поглощения:

11. Правила сокращения:

12.Правила склеивания:

Разнообразие булевых функций
Булевы функции от одной переменной

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

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

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

.

Элементарной конъюнкцией (дизъюнкцией) называется конъюнкция (дизъюнкция) конечного числа попарно различимых переменных или их отрицаний.
Элементарную конъюнкцию (дизъюнкцию) называют также конъюнктивным (дизъюнктивным) термом.
В частном случае терм, как конъюнктивный, так и дизъюнктивный, может состоять из единственной буквы (литерала).

Выражения типа: термами не являются, так как в первом случае знак отрицания стоит над конъюнкцией переменных, а во втором случае переменная x1 находится в выражении с отрицанием и без него.

Рангом терма называется количество букв входя-щих в него.

Дизъюнктивной (конъюнктивной) нормальной формой булевой функции называется дизъюнкция (конъюнкция) конечного числа попарно различи-мых конъюнктивных (дизъюнктивных) термов.

Свойство конституенты. Конституента единицы (нуля) принимает значение единицы (нуля) на одном и только одном наборе аргументов.

Пример. При n = 4 конъюнктивный терм
принимает значение равное единице на наборе 1010, а дизъюнктивный терм
принимает значение равное нулю на наборе 1101.

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

2. С помощью канонических форм любую булеву функцию можно представить в булевом базисе.

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

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

Пример. Получить канонические формы для функции y = x1 ⊕ x2.
Составим таблицу истинности заданной функции:

Существует другой способ получения ККНФ:
а) составляется КДНФ, но не для самой булевой функции, а для ее отрицания;

б) берется отрицание над полученной КДНФ, которое снимается с применением закона двойственности.

Аналогично можно перейти к ККНФ:

f3(Х)=x1⊕x2⊕x3 = - символическая форма булевой функции.

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

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

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

4. Сущность конструктивного подхода при полу-чении ДНФ состоит в следующем:
а) преобразование операций небулевого базиса к операциям булевого базиса;

б) снятие отрицаний над выражениями с примене-нием законов двойственности;

г) упрощение выражения с применением законов поглощения, склеивания, сокращения и тавто-логии.

Приведенные рассуждения справедливы и для КНФ.

Пример. Привести ДНФ заданной функции к КДНФ:

Пример. Привести ДНФ заданной функции к ККНФ:

Преобразование КНФ к ККНФ реализуется путем применения правила конъюнктивного разверты-вания к каждому неполному дизъюнктивному терму

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

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

алгебра Вебба (Пирса) (↓);

алгебра Шеффера ( | ).

В каждой из этих алгебр действуют собственные законы. Естественно существуют взаимно однозначные переходы от операций одного базиса к операциям другого.

Существенные вершины образуют так называемые ноль-кубы (0-кубы). Между 0-кубами существует отношение соседства и определена операция склеивания. Два 0-куба называются соседними, если они отличаются только по одной координате и, соответственно, могут вступать в операцию склеивания, в результате которой получается 1-куб.

Заданные кубы являются соседними, так как они различаются только по одной координате. Результатом их склеивания является 1-куб (0Х01).

Координата, отмечаемая символом Х, называется свободной (независимой, несвязанной), а остальные (числовые), координаты называются зависимыми (связанными).

Аналогичное отношение соседства существует между 1-кубами, в результате склеивания которых получается 2-куб.

Заданные кубы являются соседними, так как они различаются только по одной координате. Результатом их склеивания является 2-куб (0ХХ1).

В порядке обобщения: два r-куба называются соседними, если они отличаются только по одной (естественно, зависимой) координате. Каждый r-куб содержит r независимых и (n–r) зависимых координат. В результате склеивания двух соседних r-кубов образуется (r+1)-куб содержащий (r+1) независимую координату.

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

Так, для примера 0-кубу (0101) соответствует терм
, а 0-кубу (0001) – терм . Эти термы склеиваются по переменной х2. Результат склеивания:
, в котором отсутствует переменная х2, отождествляется с 1-кубом (0Х01).

Кубическим комплексом K0(f) булевой функции f называется множество 0-кубов этой функции. В общем случае, кубическим комплексом K(f) булевой функции f называется объединение множеств кубов всех размерностей этой функции
m - максимальная размерность
кубов функции f.

K 3(f)=∅ (пустое множество).
K(f)=K0(f) U K1(f) U K2(f). Естественно, что в комплексе K2(f) останется только один куб (Х1Х).

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

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

2. При полном попарном сравнении пяти 0-кубов потре-бовалось бы выполнить 4!=24 операции сравнения, а при целенаправленном (сравниваются только кубы из двух соседних групп) – число операций сравнения равно шести.

3. Подобный принцип рационального сравнения кубов можно распространить и на кубы большей размерности. При этом добавляется еще одно условие: два r-куба могут быть соседними, если все r их независимых координат являются одноименными.

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

Множество максимальных кубов функции f обозначается Z(f). Это множество является окончательным результатом операции склеивания кубов. Из кубов этого множества (и только из них) строится минимальное покрытие булевой функции.

В примере максимальными
кубами являются кубы

При использовании графического способа задания булевой функции от n переменных каждый из 2n наборов ее аргументов отождествляется с точкой n-мерного пространства с соответствующими координатами, которые могут принимать только два значении: 0 или 1.

Геометрическим образом 3-куба можно считать весь трехмерный куб. Так как он может быть образован тремя способами как пара параллельных граней, то при склеивании он получается в трех экземплярах.

На рисунке приведены возможные графические представления функции от четырех переменных в виде гиперкуба (тессеракта).

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

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

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

При использовании многовходовых логических элементов И, ИЛИ и одновходового элемента НЕ схема может быть построена по ДНФ или КНФ функции.

При упрощенной оценке затрат оборудования на реализацию логической схемы цена схемы определяется суммарным числом входов в логические элементы и называется ценой схемы по Квайну - SQ.

Графический метод минимизации основан на использовании минимизирующих карт, назы-ваемых картами Карно (диаграммами Вейча).

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

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

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

Наиболее известные аналитические методы минимизации описаны в пособии.

Любой 1-куб покрывает два 0-куба, 2-куб - четыре 0-куба и четыре 1-куба, 3-куб покрывает восемь 0-кубов, двенадцать 1-кубов и шесть 2-кубов (см. рис.).

Замечание. Для кубов большей размерности студентам предлагается определить количество покрываемых кубов самостоятельно. Представляется целесообразным вывести общую формулу для - числа k-кубов, покрываемых одним m-кубом (m>k), используя элементы комбинаторики.

Эта ДНФ является минимальной

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

Покрытию С2(f) соответствует ДНФ вида:

Замечание: Минимальное покрытие должно сос-тоять только из максимальных кубов.

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

Рассмотрим подобный случай на примере.

По числовой форме булевой функции составим ее кубический комплекс K0(f):

Произведя всевозможные операции склеивания между 0-кубами, получим кубический комплекс K1(f).

Для рассматриваемого примера СДНФ:

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

2. Так как ядром покрытия, кроме существенных вершин (001) и (111), покрываются также существенные вершины (000) и (110), то не покрытой ядром остается только существенная вершина (100).

Таким образом, для рассматриваемого примера получены два минимальных покрытия:

;

которым соответствуют МДНФ:

и

2. В общем случае: получение минимального покрытия осуществляется в следующем порядке:

а) находится множество максимальных кубов;

б) выделяется ядро покрытия;

в) из множества максимальных кубов, не вошедших в ядро, выбирается такое минимальное подмножество, которое покрывает существенные вершины, не покрытые ядром.

Cmin(f) = Z(f). Минимальное покрытие совпадает с множеством максимальных кубов Z(f). При этом МДНФ совпадает с СДНФ;

Cmin(f) ⊂ Z(f). Минимальное покрытие представляет собой некоторое подмножество множества максимальных кубов. При этом могут иметь место следующие случаи:

а) Cmin(f) = T(f). Минимальное покрытие совпадает с ядром.

в) T(f) = ∅. Ядро покрытия отсутствует. Покрытие формируется из минимального числа максимальных кубов. Данный случай является наиболее сложным для получения минимального покрытия.

где Nr - количество r-кубов, входящих в покрытие, m - максимальная размерность кубов, входящих в покрытие. Цена Sa представляет собой сумму цен кубов, входящих в покрытие.

Цена r-куба (Sr) представляет собой количество несвязанных координат: Sr= n – r. Принято использовать два вида цены покрытия: Sa и Sb.

Можно показать, что покрытие, обладающее минимальной ценой Sa, обладает также и минимальной ценой Sb.

- цена покрытия Sa представляет собой количество букв, входящих в ДНФ;

- цена Sb представляет сумму количества букв и количества термов, образующих ДНФ.

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

В качестве системы логических элементов используем элементы булева базиса {И, ИЛИ, НЕ}. Будем строить схему с парафазными входами, в следствии чего элементы НЕ (инверторы) не понадобятся.

И(2) И(2) И(2)
ИЛИ(3)

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

Замечание. В принципе, между ценой схемы SQ и ценами покрытия Sa и Sb существует соотношение: Sa ≤ SQ ≤ Sb, которое выполняется при следующих допущениях:

1. Схема строится по нормальной форме (ДНФ или КНФ).

2. Схема строится на элементах булевого базиса (И, ИЛИ).

3. На входы схемы подаются как прямые, так и инверсные значения аргументов булевой функции (схема с парафазными входами).

Определим множество максимальных кубов нулевого покрытия. Над 0-кубами кубического комплекса выполним операцию склеивания

∅), то

Sa=5 Sb=7.

множество максимальных кубов:

2. Цена минимального нулевого покрытия оказалась меньше цены минимального единичного покрытия.

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

С использованием карт Карно находится минимальное покрытие функции, по которому строится ее минимальная ДНФ (КНФ).

1

Примеры образования 1-кубов приведены на рисунках:

с ценами Sа(f1) = 15, Sb(f1) = 20 и Sa(f2) = 24, Sb(f2)=30 определить покрытия

с ценами Sa(f1) = 6, Sb(f1) = 9, Sa(f2) = 12, Sb(f1) = 16.

Карты построены для функций f1, f2 и f3, заданных в числовой форме:

Объединение восьми клеток карты приводит к образованию 3-куба. Примеры образования 3-кубов для функций от четырех переменных f1, f2, f3, заданных в числовой форме:

Пример. Определить минимальные ДНФ и КНФ функции с использованием карт Карно.

Пример минимизации функции пяти переменных

Разделение четырехмерных карт Карно произво-дится по значению аргумента х1: для левой карты х1=0, для правой - х1=1. Каждая клетка Карно для функции от пяти переменных имеет пять соседних, четыре из которых размещаются в пределах своей четырехмерной карте, а одна расположена в

Кубы, используемые в покрытии функции, могут располагаться:
а) целиком в одной из четырехместных карт (при х1=0 - в левой, при х1=1 – в правой);

б) в обеих четырехместных картах (при этом координата х1 - независимая: х1=Х).

Рассмотрим принцип размещения карт для представления функций шести переменных

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

При минимизации частично определенных булевых функций в клетки карты Карно, соответствующие наборам аргументов, на которых функция не определена, ставится символ d (don’t care).

Введем булевы переменные: a : xk2. Построим схемы алгоритмов для вычисления r.

где FR1, FR2 и FR3 - линейные формулы, k1 и k2 - некоторые константы: k1 ≠ k2 и k1 < k2.

Для первого алгоритма сначала проверим условие а, а затем b.
Для второго – сначала условие b, а затем а.

Предполагается, что слагаемые имеют значения а1а2 ≤ 2; b1b2 ≤ 2, т.е. наборы а1а2 = 11 и b1b2 = 11 отсутствуют и рассматриваются как несущест-венные.

Для функции у1у2 составим таблицу истинности.

Булева функция g(X) называется импликантой булевой функции f(X), если для любого набора аргументов, на которых g(X)=1, f(X) также равна единице.

Свойства импликант:
1. Между импликантой и самой функцией существует отношение включения g(X)⊂ f(X).

3. Если g(X) и ϕ(X) являются импликантами функции f(X), то их дизъюнкция также является импликантой этой функции.

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

Пример. Импликантами функции
являются

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

Для функции примера простыми импликантами являются:

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

Для функции примера СДНФ имеет вид:

Для нашего примера КДНФ содержит 15 букв и 5 термов, а СДНФ - 8 букв и 4 терма.

Любой простой импликанте булевой функции соответствует максимальный куб, и, в свою очередь, множество всех простых импликант соответствует множеству Z(f) всех максимальных кубов К(f).

Таким образом, можно провести некоторую аналогию между сокращенной СДНФ и Z(f).

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

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

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

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

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

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

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

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

Для решения канонической задачи минимизации методом Квайна-Мак-Класки применяется следующая последовательность действий:

1. Нахождение множества максимальных кубов (простых импликант) булевой функции.

2. Выделение ядра покрытия (определение множества существенных импликант).

Распространение терминологии в отношении нуле-вого покрытия базируется на понятии имплиценты (как соответствие импликанте) и системы имплицент.

Нахождение множества максимальных кубов (простых импликант) булевой функции
Рассмотрим процедуру нахождения простых импликант на следующем примере.

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

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

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

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

Таблица покрытий отображает отношение покрытия между существенными вершинами булевой функции и максимальными кубами. Для этого на пересечении i-ой строки и j-го столбца таблицы делается соответ-ствующая отметка в том случае, если максимальный куб из i-ой строки покрывает существенную вершину из j-го столбца.

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

Определение множества минимальных покрытий
На этом этапе из множества максимальных кубов, не принадлежащих ядру покрытия, выделяются такие минимальные подмножества, с помощью каждого из которых покрываются оставшиеся вершины (не покрытые ядром). Реализацию этого этапа целесообразно производить с использова-нием упрощенной таблицы покрытий. В ней вычеркнуты все кубы, принадлежащие ядру, и вершины, покрываемые ядром.

На данном этапе целесообразно ввести обозначение максимальных кубов и существенных вершин. Максимальные кубы обозначены прописными буквами A, ..., F, а существенные вершины строчными буквами a, ..., e.

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

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

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

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

Это выражение представлено в конъюнктивной форме. Для его преобразования в дизъюнктивную форму выпол-няется попарное логическое умножение дизъюнктивных термов.

Замечание. В целях максимального упрощения этапа преобразования выражения Y перемножаются термы, содержащие по возможности максимальное количество букв. После логического умножения двух первых пар дизъюнктивных термов получим выражение:
Y = (AA∨AC∨AB∨ BC)(CD∨CE∨DD∨DE)(E∨F), которое, после применения законов тавтологии и поглощения, приво-дится к виду: Y = (A∨BC)(D∨CE)(E∨F).

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

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

Операции вычеркивания строк и столбцов базируются на следующих правилах:

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

Применим метод дальнейшего упрощения таблицы покрытий. С помощью операции вычеркивания “лишних” строк из нее можно удалить две строки B и F, множество меток в которых является подмножеством меток в строках A и E соответственно.

Из табл. определяем два минимальных покрытия в виде двух возможных вариантов дополнения кубов ядер покрытия нулевого T (f) и первого порядка T1(f) кубами C и D соответственно.
Таким образом, с помощью метода упрощения таблицы покрытий получено только два минимальных покрытия:

Функциональная полнота системы булевых функций
Система булевых функций S={f1 , f2,..., fm} называется функционально полной, если с помощью функций этой системы можно выразить любую булеву функцию с использованием метода суперпозиции.

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

Система S1 является избыточной, так как из нее можно удалить одну из функций (& или ∨) без нарушения функциональной полноты.

Получаемые при этом системы S2 ={⎤ , &} и S3={⎤ , ∨} обычно называют сокращенным булевым базисом.

Недостающие операции (∨ в системе S2 и & в системе S3) могут быть выражены с помощью следствий из законов де Моргана:

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

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

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

Доказательство функциональной полноты некоторой системы булевых функций можно осуществлять одним из двух способов:
1. с использованием теоремы о функциональной полноте;
2. с использованием конструктивного подхода.

хотя бы одну функцию, не cохраняющую ноль;

хотя бы одну функцию, не cохраняющую единицу;

хотя бы одну не линейную функцию;

хотя бы одну не монотонную функцию;

хотя бы одну не самодвойственную функцию.

В теореме Поста фигурируют пять классов булевых функций:
K0 – класс функций, сохраняющих ноль;
К1 – класс функций, сохраняющих единицу;
KL – класс линейных функций;
KM – класс монотонных функций;
KS – класс самодвойственных функций.

Замечательные классы булевых функций
Булева функция называется сохраняющей ноль, если на нулевом наборе аргументов она принимает значение, равное нулю, то есть f (0, 0, 0,..., 0) = 0. В противном случае функция относится к классу функций, не сохраняющих ноль.
К функциям, сохраняющим ноль, относятся
f(x1,x2)= x1 ∨ x2 и f(x1,x2)= x1 ⋅ x2.

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

Полином Жегалкина является линейным (1-ой степени), если все коэффициенты общего полинома, начиная с Kn+1, равны нулю. В отношении функции от двух переменных линейный полином Жегалкина имеет вид: f 2(Х)=K0 ⊕ K1x1 ⊕ K2x2. Примерами линейных функций являются:
y= x1⊕ x2 (K0=0, K1=K2=1),

Две булевы функции f n(Х) и gn(Х) называются двойственными, если для любых наборов аргументов выполняется равенство
то есть функции f и g на противоположных наборах аргументов Х и принимают противоположные значения.

Булева функция называется самодвойственной, если она является двойственной по отношению к самой себе, то есть принимает противоположные значения на противоположных наборах аргумен-тов. Примером самодвойственной функции явля-ется: у = .
Примеры не самодвойственных функций: у=х1⋅ х2, у=х1∨ х2, у=х1⊕ х2.

Конструктивный подход к доказательству функ-циональной полноты системы булевых функций
Подход базируется на следующей теореме булевой алгебры:

Пример. Докажем функциональную полноту системы S5={|} (универсальный базис), выразив инверсию, конъюнкцию и дизъюнкцию с помощью только функции штрих Шеффера.