Глава 9. БУЛЕВЫ ФУНКЦИИ

9.1. ОСНОВНЫЕ ПОНЯТИЯ

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

Таблица 9.1

Таблица 9.2

Таблица 9.3

Таблица 9.4

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

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

Под двоичным набором понимается совокупность значений аргументов булевой функции f. Двоичный набор имеет длину если он представлен пцифрами из множества . В табл. 9.1 и 9.2 перечислены все двоичные наборы соответственно длины 3 и 4.

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

называемое номером набора 7. Например, двоичные наборы и

Рис. 9.1

1000 имеют номера 5 и 8 соответственно. Очевидно, любая булева функция может быть задана таблицей истинности, в которой двоичные наборы заменены своими номерами (табл. 9.3).

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

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

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

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

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

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

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

Таблица 9.5

Таблица 9.6

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

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

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

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

— тождественный ноль (константа 0);

— тождественная функция;

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

— тождественная единица (константа 1).

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

Наиболее часто употребляются следующие:

тождественный ноль (константа 0);

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

— повторение

Таблица 9.7

Таблица 9.8

Рис. 9.2

— повторение

— сложение по модулю 2 или сумма

— дизъюнкция (логическое ИЛИ);

- функция Вебба (стрелка Пирса);

— эквивалентность;

— импликация;

— штрих Шеффера;

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

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

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

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

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

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

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

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

В этой алгебре справедливы три аксиомы:

закон коммутативности —

закон ассоциативности —

закон дистрибутивности —

Под бинарной операцией на множестве А, в общем случае понимают отображение декартового произведения множеств в

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

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

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

Пример. Упростить выражение

После применения соотношения (9.1) получим

Используя соотношение (9.1) к обеим квадратным скобкам, имеем!

Применяя выражения (9.3) к первой круглой скобке и (9.1) ко второй круглой скобке, получим

Последовательно применяя соотношения (9.2) и (9.4), а к выражениям с отрицаниями — (9.1). получим

После преобразования имеем

и далее, используя (9.2) и (9.4), получим

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

Алгебра Жегалкина включает две двухместные операции: конъюнкцию и сложение по модулю также константу I. Здесь имеют место те же законы:

(закон коммутативности);

(закон ассоциативности);

(закон дистрибутивности).

Для упрощения формул могут быть использованы следующие соотношения:

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

Аналогично для конъюнкции

я суммы по модулю 2

Теоремы де Моргана для нескольких переменных имеют вид: