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

1.Основные понятия булевой алгебры


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

Таким аппаратом является математическая логика (алгебра логики, булева алгебра).

Логика - это наука о законах и формах мышления.

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

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

Любое высказывание можно обозначить символом х и считать, что х=1, если высказывание истинно, а х=0 - если высказывание ложно. Истинному высказыванию соответствует утверждение -“Да”, ложному высказыванию - утверждение - “Нет”.

Логическая (булева) переменная - такая величина х, которая может принимать только два значения х={0,1}.

Высказывание абсолютно истинно, если соответствующая ей логическая величина принимает значение х=1 при любых условиях.

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

Функция f, зависящая от n переменных x1,x2,...,xn, называется булевой, или переключательной, если функция f и любой из ее аргументов Булевы функции принимают значения только из множества {0,1}. Аргументы булевой функции также называются булевыми.


2.Способы задания булевых функций


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

При матричном способе булева функция f(x1,...,xn) задается таблицей истинности (табл. 1 и 2), в левой части которой представлены все возможные двоичные наборы длины n, а в правой указывается значение функции на этих наборах.

Под двоичным набором понимается совокупность значений аргументов x1,x2,...,xn булевой функции f. Двоичный набор имеет длину n, если он представлен n цифрами из множества {0,1}. В табл. 1 и 2 перечислены все двоичные наборы соответственно длины 3 и 4.


Таблица 1 Таблица 3

х1 х2 х3 f(х1,х2,,х3)

Номер

набора

f(х1,х2,,х3)
0 0 0 0
0 0
0 0 1 1
1 1
0 1 0 0
2 0
0 1 1 0
3 0
1 0 0 1
4 1
1 0 1 1
5 1
1 1 0 0
6 0
1 1 1 1
7 1

Таблица 2 Таблица 4.

x1 x2 x3 x4 f(х1..х4)
x1,x2,...,xj-1 xj,xj+1,...,xn







00..0 0...1 ... 11..1
0 0 0 0 1





0 0 0 1 0
00...0

...
0 0 1 0 0





0 0 1 1 1





0 1 0 0 1





0 1 0 1 0
00...1

...
0 1 1 0 1



f(х1...хn)
0 1 1 1 1





1 0 0 0 1





1 0 0 1 0
... ... ... ... ...
1 0 1 0 0





1 0 1 1 0





1 1 0 0 0





1 1 0 1 0
11...1



1 1 1 0 1





1 1 1 1 0






Иногда двоичные наборы в таблице истинности булевой функции удобно представлять номерами наборов. Запишем аргументы x1,x2,...,xn в порядке возрастания их индексов. Тогда любой двоичный набор можно рассматривать как целое двоичное число N, называемое номером набора. Например, двоичные наборы 0101 и 1000 имеют номера 5 и 8 соответственно. Очевидно, любая булева функция может быть задана таблицей истинности, в которой двоичные наборы заменены своими номерами (табл.3).

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

Рассмотрим способ построения такой таблицы истинности для функции n переменных. Множество из n переменных функции разбивается на два подмножества: x1,x2,...,xj-1 и хj, xj,xj+1,...,xn. Переменными x1,x2,...,xj-1 отмечают строки таблицы истинности, задавая в каждой строке значение соответствующего двоичного набора длины j-1. Переменными xj,xj+1,...,xn отмечают ее столбцы, задавая в каждом столбце значения соответствующего двоичного набора длины n-j+1. Значение функции записывается в клетке на пересечении соответствующей строки и столбца (табл.4.).

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


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

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

а) n=1 б) n=2 в) n=3

Рисунок 1- Геометрическое задание булевой функции:

а) одной переменной: б) двух переменных; в) трех переменных.


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

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

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

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

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


3.Булевы функции одной и двух переменных


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


Таблица 5

f(х) х Усл. Наименование

0 1 обозн
f0 (х) 0 0 0 тождественный ноль (константа 0);
f1 (х) 0 1 х тождественная функция
f2 (х) 1 0

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

отрицание х (инверсия);
f3 (х) 1 1 1 тождественная единица (константа 1).

Функции двух переменных представлены в табл. 6.

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

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


Таблица 6


х1 0 0 1 1 Наименование функции

х2 0 1 0 1
f0 (х1,х2) 0 0 0 0 константа 0
f1 (х1,х2) 0 0 0 1 конъюнкция
f2 (х1,х2) 0 0 1 0 запрет по х2
f3 (х1,х2) 0 0 1 1 переменная х1
f4 (х1,х2) 0 1 0 0 запрет по х1
f5 (х1,х2) 0 1 0 1 переменная х2
f6 (х1,х2) 0 1 1 0 сумма по модулю 2
f7 (х1,х2) 0 1 1 1 дизъюнкция
f8 (х1,х2) 1 0 0 0 операция Пирса (ф-ция Вебба)
f9 (х1,х2) 1 0 0 1 логическая равнозначность
f10 (х1,х2) 1 0 1 0 инверсия х2
f11 (х1,х2) 1 0 1 1 импликация от х2 к х1
f12 (х1,х2) 1 1 0 0 инверсия х1
f13 (х1,х2) 1 1 0 1 импликация от х1 к х2
f14 (х1,х2) 1 1 1 0 штрих Шеффера
f15 (х1,х2) 1 1 1 1 константа 1

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

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

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

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

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


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


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

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

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

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


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


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


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


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

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

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


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


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

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

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

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

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

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


Таблица 7.


х1х2х3 f(х1,х2,х3)
0 0 0 0 0
1 0 0 1 1
2 0 1 0 1
3 0 1 1 0
4 1 0 0 0
5 1 0 1 1
6 1 1 0 0
7 1 1 1 1

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}, а Булевы функции - операция «сумма по mod 2».

Линейными являются булевы функции из табл. 6 - f0, f3 , f5 и т. д.Булевы функции

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

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

Так, набор 1011 ≥1010. Вместе с тем наборы 1011 и 0100 несравнимы в том смысле, что для них не выполняется ни соотношение Булевы функции, ни Булевы функции.

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

Монотонными являются булевы функции f0, f1,f3 , f5 (из табл. 6) и т.д.

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

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

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

Рассмотрим примеры ФПСБФ. К таким ФПСБФ, наиболее распространенным в практике построения цифровых автоматов, следует отнести: (Булевы функции, НЕ); (Булевы функции,НЕ); (V, НЕ); (Булевы функции, НЕ), (Булевы функции,1); где символами V, Булевы функции, Булевы функции, НЕ, 1 обозначены булевы функции: «дизъюнкция», «конъюнкция», «сумма по mod 2», «отрицание», «константа 1», соответственно.


7.Минимизация булевых функций


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

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

Определение. Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция элементарных конъюнкций.

Определение. Минимальной дизъюнктивной нормальной формой булевой функции называется ДНФ, содержащая наименьшее число букв (по отношению ко всем другим ДНФ, представляющим заданную булеву функцию). Определение. Булева функция g(x1,x2,...,xn) называется импликантой булевой функции f1(x1,x2,...,xn), если для любого набора переменных, на котором g = 1, справедливо f = 1. Пример. Булева функция f задана таблицей 8. Там же приведены все ее импликанты. При записи функции и ее импликант в СДНФ имеем


f= Булевы функцииЪБулевы функцииЪБулевы функции

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

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

g3=Булевы функцииVБулевы функции=Булевы функции

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

g5=Булевы функцииvvБулевы функции=Булевы функции

g6=Булевы функцииvvБулевы функции

g7=Булевы функцииЪБулевы функцииЪБулевы функции


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

Из примера видно, что импликанты g3 и g5 являются простыми импликантами функции f. Другие импликанты не являются простыми, так как их части являются импликантами функции f, например g3 является частью g1. Приведем без доказательства два утверждения, полезные при получении минимальной ДНФ.

1. Дизъюнкция любого числа импликант булевой функции f также является импликантой этой функции.

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

Перебор всех возможных импликант для булевой функции f из рассмотренного примера дает возможность убедиться, что простых импликант всего две: g3 и g5. Следовательно, сокращенная ДНФ функции f имеет вид:


f = g3 V g5 =Булевы функцииV Булевы функции


Как видно из табл. 6.8., импликанты g3 и g5 в совокупности покрывают своими единицами все единицы функции f. Получение сокращенных ДНФ является первым этапом отыскания минимальных форм булевых функций. Как уже отмечалось, в сокращенную ДНФ входят все простые импликанты булевой функции. Иногда из сокращенной ДНФ можно убрать одну или несколько простых импликант, не нарушая эквивалентности исходной функции. Такие простые импликанты назовем лишними. Исключение лишних простых импликант из сокращенных ДНФ — второй этап минимизации.

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

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

Утверждение. Тупиковые ДНФ булевой функции f, содержащие минимальное число букв, являются минимальными. Минимальных ДНФ тоже может быть несколько.

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


7.1.Метод Квайна


Метод Квайна основывается на применении двух основных соотношений.

Соотношение склеивания


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


где А — любое элементарное произведение.

Соотношение поглощения


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


Справедливость обоих соотношений легко проверяется.

Теорема Квайна. Если в СДНФ булевой функции выполнить все возможные склеивания и поглощения, то в результате будет получена сокращенная ДНФ.

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

Для доказательства достаточно показать, что произвольная простая импликанта р = Булевы функцииможет быть получена. В самом деле, применяя к р операцию развертывания (обратную операции склеивания): Булевы функциипо всем недостающим переменным исходной функции f, получаем совокупность S конституент единицы. При склеивании всех конституент из S получим импликанту р. Последнее очевидно, поскольку операция склеивания обратна операции развертывания. Множество S конституент обязательно присутствует в совершенной ДНФ

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

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: