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

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

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

Конъюнкция двух бинарных величин и обозначается и определяется таблицей истинности

Операцию конъюнкция называют логическим умножением (логическое ).

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

Таблица истинности для операции эквивалентности имеет вид

Можно строить сложные конструкции из величин типа

или ,

если договориться о следующем выполнении порядка действий

1. Конъюнкция выполняется раньше, чем все остальные операции.

2. Дизъюнкция выполняется раньше, чем импликация и эквиваленция.

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

определяется посредством следующей таблицы истинности.

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

Выпишем основные равносильности

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

Здесь и    равны единице и нулю соответственно.

Выпишем также равносильности, выражающие одни операции через другие

1.

2.

3.

4.

5.

6.

Определим еще одну операцию которую называют «Штрих Шеффера», эта операция определяется следующей таблицей истинности

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

1. коммутативность конъюнкции

2. коммутативность дизъюнкции

3. ассоциативность конъюнкции

4. ассоциативность дизъюнкции

5. дистрибутивность конъюнкции относительно дизъюнкции

6. дистрибутивность дизъюнкции относительно конъюнкции

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

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

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

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

Приведем таблицу для булевых функций двух переменных

Нетрудно видеть, что выполняются следующие равенства

.

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

Любую булеву функцию можно представить следующим образом

Определение.

Элементарной конъюнкцией переменных назовем следующую конструкцию

здесь

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

(1)

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

Приведем пример такого представления.

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

Следуя формуле (1) эта булева функция представима следующей формулой

(2)

Определение.

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

Как следует из приведенного определения, формула (2) является дизъюнктивной нормальной формой представления булевой функции.

Пусть - множество значений , на котором булева функция равна 1, а - множество значений , на котором булева функция равна 0.

Очевидно, что справедливо равенство

(3)

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

(4)

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

Рассмотрим функцию, определяемую формулой (2) и построим для нее (КНФ). Согласно приведенным рассуждениям имеем

Напомним определение операции - сложение по модулю 2. таблица истинности для этой операции следующая.

В алгебре логики эта операция называется XOR, употребляется также название – исключающее или.

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

, .

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

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

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

Рассмотрим еще один пример построения полиномиальной формы для следующей функции

Для произвольной функции функция называется двойственной и обозначается f*. Кратко приведенное определение записывается так

следующий пример позволяет более подробно понять определение двойственной функции

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

здесь - наименьшее целое большее или равное . Наборы первого множества сопоставляются столбцам матрицы. Наборы второго множества строкам матрицы.

На этой диаграмме единичное значение переменной изображается чертой, нулевое значение отсутствием черты.

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

Код Грея 0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 1 1 0 0 1 1 1 0 1 0 1 0 1 0 0 1 1 0 0 1 1 0 1 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 1 1 0 0 1 1 0 0 0

Позиционных код 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

Построение кода Грея происходит по следующей схеме:

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

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

1 свойство

(7)

это свойство мы можем доказать с помощью таблиц истинности.

2 свойство

(8)

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

(9)

Дальнейшие упрощения этого соотношения возможны с использованием соотношения которое называется теоремой поглощения

(10)

Доказательство этого утверждения очень простое, читателю предлагается провести его самостоятельно. С использованием этого свойства перепишем (9).

Выпишем еще несколько полезных теорем.

Теорема склеивания.

(11)

Доказательство этого свойства просто, если заменить следующее

Теорема неполного склеивания.

(12)

Эту равносильность легко доказать, используя таблицу истинности.

Теорема обобщенного склеивания.

(13)

Эту равносильность также легко доказать используя таблицу истинности.

Сформулируем теперь правила, посредством которых можно упрощать ДНФ.

Операция поглощения.

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

Рассмотрим пример

Операция неполного склеивания.

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

Пример

.

Операция обобщенного склеивания.

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

Пример.

.

Пример. Упростим ДНФ

Мы выполнили операцию склеивания.

Задание. С использованием операций склеивания и обобщенного склеивания провести упрощение ДНФ.

Рассмотрим класс булевых функций, называемых симметрическими.

Определение: Булева функция симметрична по переменным и , если выполняется равенство

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

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

1. Выпишем множество наборов переменных , на которых функция равна единице.

2. Разбиваем множество на классы . К такому классу отнесем множество наборов переменных, в которых ровно переменных принимают значение равное единице.

3. Проверяем соотношение

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

Выпишем наборы, на которых функция обращается в нуль

0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 1 1 0 1 1 0 1 1 0 1 1 0 1 1 1

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

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

Пример

1 0 0 0 1 1 1 0 1 1 0 0 1 0 1 1 0 0 0 1 0 0 1 0 0 1 0 0     0 0 0 0   0 1 1 0 0 1 0 1 0 0 1 1 1 0 0 1 1 0 1 0 1 1 0 0

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

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

Для нашего примера имеем.

Из рассмотрения этого примера получаем, что инвертировать нужно

1 0 0 0 1 1 1 0 1 1 0 1 1 0 1 1 0 0 0 1 0 0 1 0 0 1 0 0 4 3 3 3 3 4 4

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

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

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

Теорема. Существует различных симметрических булевых функций и переменных.

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

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

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

Пример.

Преобразованная ДНФ позволяет заключить, что функция монотонна.

Булева функция называется самодвойственной, если выполняется соотношение

.