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

Существует не более чем  различных булевых функций п переменных. К этому выводу легко прийти, пользуясь простыми комбинаторными рассуждениями, и вспомнив, что на каждом из 2n наборов функции могут принимать два значения.
Рассмотрим наиболее употребляемые булевы функции одной и двух переменных. Функции одной переменной представлены в табл. 1.3, где
f0 (x) = 0 — тождественный ноль (константа 0);
f1 (х) = х — тождественная функция;
f2 (х) =  — отрицание х (инверсия);
f3 (х) = 1 — тождественная единица (константа 1).
Функции двух переменных представлены в табл. 1.4.
Наиболее часто употребляются следующие:
f0 (x1, x2) = 0 — тождественный ноль (константа 0);
f1 (x1, x2) = — конъюнкция.
f3 (x1, x2)=x1 — повторение х1;
f5 (x1, x2) = x2 — повторение х2,

Вместо знака “•” иногда упо­требляется знак & или . Эту функцию часто называют логическим произведением или логическим умножением;

Таблица 1.3 – Функции одной  переменной

Таблица 1.4 – Функции двух переменных

f0 (x1, x2) = 0 — тождественный ноль (константа 0);
f1 (x1, x2) = — конъюнкция.
f2 (x1, x2)=x1 — повторение х1;
f4 (x1, x2)=x1 —запрет  х2= x1, x2 ;
f3 (x1, x2) = x2 — повторение х1,
f5 (x1, x2) = x2 — повторение х2,
f6 (x1, x2) =  — сложение по модулю 2 или сумма mod 2;
f7 (x1, x2 )=  — дизъюнкция (логическое ИЛИ);
f8 (x1, x2) =  — функция Вебба (стрелка Пирса);
f9 (x1, x2) = x1 ~ x2 — эквивалентность;
f13 (x1, x2 )= — импликация;
f14 (x1, x2) = x1 / x2 — штрих Шеффера;
f15 (x1, x2) = 1 — тождественная единица (константа 1).
Рассмотренные простейшие булевы функции позволяют строить новые булевы функции с помощью обобщенной операции, называемой операцией суперпозиции. Фактически операция суперпозиции заключается в подстановке вместо аргументов других булевых функций (в частности аргументов). Например, из функции f1 (x1, x2) c помощью подстановки x1=f3 (x4, x8), х2 = x3 вместо аргументов х1 и x2 соответственно получаем функцию f1 (f3 (х3, x4), x3). Последняя от переменных x1иx2 уже не зависит.
Операция суперпозиции позволяет увидеть качественный переход от п = 1 к п = 2. Действительно, суперпозиция функций одного аргумента порождает функции одного аргумента. Суперпозиция функций двух аргументов дает возможность строить функции любого числа аргументов (в приведенном примере построена функция трех переменных).
Суперпозиция булевых функций представляется в виде логических формул. Однако следует отметить:

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

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

Вернуться в оглавление:Цифровые автоматы