Замкнутые классы булевых функций

Решение проблемы нахождения любых других базисов булевых функций, отличных от указанных в таб.1.8, было найдено Э. Постом на пути изучения замкнутых классов таких функций. Множество М булевых функций называется замкнутым классом, если [M]=M. Мы уже встречали замкнутые классы булевых функций: например, [{ИДЕНТ, НЕ}] = {ИДЕНТ, НЕ}. Другие примеры - (а) множество всех конъюнкций от различного числа аргументов, (б) множество всех дизъюнкций от различного числа аргументов. Существует множество разных замкнутых классов функций. Э. Постом было выделено пять таких классов, на основе которых им была решена проблема базисов булевых функций. Ниже для каждого такого класса вводится его определение, примеры, и формулируется теорема о том, что множество функций, обладающих указанным свойством С, составляет замкнутый класс. Доказать эти теоремы просто, доказательство основано на простой индукции по глубине суперпозиции функций. Базу индукции составляет утверждение о том, что тождественная функция обладает указанным свойством С, а шаг индукции - что если произвольная функция f(x₁,x₂,...,x_m) обладает свойством С и все функции F₁, F₂, ..., F_m обладают свойством С, то функция f(F₁,F₂,...,F_m,) тоже обладает свойством С. Более подробно о замкнутых классах можно прочитать в [КАВ88].

Определение 1.6. Функция f(x₁,x₂,...,x_m) сохраняет ноль, если f(0,0,...,0) =0.ÿ

Примером функции, сохраняющей ноль, является конъюнкция. Отрицание не сохраняет ноль. Функция f(p,q,r) = ØpÚqÅrq(pÚr) примера 1.2 не сохраняет ноль; из таб.1.6: f(0,0,0)=1. Обозначим М₀ множество всех функций, сохраняющих ноль.

Теорема 1.6. [М₀] = М₀.ÿ

Определение 1.7. Функция f(x₁,x₂,...,x_m) сохраняет единицу, если f(1,1,...,1) =1.ÿ

Примером функции, сохраняющей единицу, является конъюнкция. Отрицание не сохраняет единицу. Функция f(p,q,r) = ØpÚqÅrq(pÚr) примера 1.2 не сохраняет единицу; из таб.1.6: f(1,1,1)=0. Обозначим М₁ множество всех функций, сохраняющих единицу.

Теорема 1.7. [М₁] = М₁.ÿ

Введем отношение порядка на множестве двоичных наборов. (x₁,x₂,...,x_m)£(y₁,y₂,...,y_m) тогда и только тогда, когда для любого 1£ i £m выполняется x_i£ y_i.

Определение 1.8. Функция f(x₁,x₂,...,,x_m) называется монотонной, если для любых двух наборов <x₁,x₂,...,,x_m> и y₁,y₂,...,y_m, выполнение (x₁,x₂,...,x_m)£(y₁,y₂,...,y_m) влечет f(x₁,x₂,...,x_m)£f(y₁,y₂,...,y_m).ÿ

Обозначим М_мон множество всех монотонных функций. Примером монотонной функции является конъюнкция. Отрицание не является монотонным. Функция f(p,q,r) = ØpÚqÅrq(pÚr) примера 1.2 не является монотонной; из таб.1.6: f(0,0,0)=1, а f(0,1,1)=0.

Теорема 1.8. [М_мон] = М_мон.ÿ

Определение 1.9. Функция f(x₁,x₂,...,,x_m) называется самодвойственной, если для любого набора <x₁,x₂,...,,x_m>, f(Øx₁,Øx₂,...,Øx_m) = Øf(x₁,x₂,...,,x_m).ÿ

Примером самодвойственной функции является отрицание. Конъюнкция не является самодвойственной функцией. Функция f(p,q,r) = ØpÚqÅrq(pÚr) примера 1.2 не является самодвойственной. Действительно, из таблицы 1.6: f(0,0,1)=f(1,1,0)=1.

Обозначим М_сам множество всех самодвойственных функций.

Теорема 1.9. [М_сам] = М_сам.ÿ

Определение 1.10. Функция f(x₁,x₂,...,,x_m) называется линейной, если ее полином Жегалкина имеет вид a₀ÅSa_xix_i.ÿ

Примером линейной функции является отрицание. Дизъюнкция не является линейной функцией: ранее мы видели, что pÚq = pÅqÅpq. Функция f(p,q,r) = ØpÚqÅrq(pÚr) примера 1.2 не является линейной: ранее мы видели, что f(p,q,r)=1ÅpÅpqÅqr. Обозначим М_лин множество всех линейных функций.

Теорема 1.10. [М_лин] = М_лин.ÿ

Теорема Поста

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

Теорема 1.11 (теорема Поста).Пусть NÍВ. Для того, чтобы множество N двоичных функций было базисом, т.е. [N]=В, необходимо и достаточно, чтобы:

а) N содержало бы по крайней мере одну функцию, не сохраняющую ноль: NËМ₀, и
б) N содержало бы по крайней мере одну функцию, не сохраняющую единицу: NËМ₁, и
в) N содержало бы по крайней мере одну немонотонную функцию: NË М_мон, и
г) N содержало бы по крайней мере одну несамодвойственную функцию: NË М_сам, и
д) N содержало бы по крайней мере одну нелинейную функцию: NË М_лин.

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

Достаточность. Нужно доказать, что если все условия а) - д) выполняются, то [N]=В. Это доказательство проведем конструктивно по следующей схеме: покажем непосредственно, как из функций множества N построить функции базиса (конъюнктивного или дизъюнктивного).

Эта схема имеет следующий вид (рис.1.9):

Рис.1.9. Схема доказательства теоремы Поста

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

Шаг 1. Пусть F₀ не сохраняет 0 (т.е. F₀(0,...,0)=1), F₁ не сохраняет 1 (т.е. F₁(1,...,1)=0), а F_n несамодвойственная. Рассмотрим различные варианты.

Пусть F₀ при этом сохраняет единицу (т.е. F₀(1,...,1)=1),. Тогда при любом х, j(х) = F₀(х,...,х) = 1 и F₁(j(х),..., j(х)) = F₁(1,...,1)=0, т.е. получили искомые функции-константы.

Пусть теперь F₀ не сохраняет единицу, т.е. F₀(1,...,1)=0. Но тогда F₀(х,...,х)= Øх. Имея отрицание, с помощью несамодвойственной функции легко получить константу. Действительно, поскольку F_n - функция несамодвойственная, то найдется набор (s₁,s₂,...,s_m) такой, что F_n(s₁,s₂,...,s_m)=F_n(Øs₁,Øs₂,...,Øs_m)=Сonst, где Сonst либо 0, либо 1. Подставим вместо s_i в F_n x, если s_i=1, и Øх, если s_i=0. Выход этой функции при любом х будет Сonst. Инвертировав Сonst с помощью отрицания, получим другую константу.

Пример 1.11. Функция f, заданная таблицей 1.6, не сохраняет ноль (f(0,0,0)=1) и не сохраняет единицу (f(1,1,1)=0). Следовательно, f(х,х,х)=Øх. Она же является несамодвойственной (существуют два противоположных набора значений аргументов, на которых значения f равны: f(0,0,1)=f(1,1,0)=1). Тогда f(х,х,Øх)=1, а Øf(х,х,Øх)=0 при любом х. Использовав f(х,х,х)=Øх, получаем: f(х,х,f(х,х,х))=1, а f(f(х,х,f(х,х,х)),f(х,х,f(х,х,х)),f(х,х,f(х,х,х))=0 при любом х.

Шаг 2. Пусть F - немонотонная функция. Покажем, как с помощью констант можно построить отрицание. В немонотонной функции всегда существует “единичный интервал” немонотонности, т. е. пара соседних наборов (s₁,...,0,...,s_m) и (s₁,...,1,...,s_m), на которых F меняет значение: F(s₁,...,0,...,s_m)=1 и F(s₁,...,1,...,s_m)=0. Подставив вместо s_i - константы, получим из F инвертор.

Пример 1.12. Функция f, заданная таблицей 1.6, немонотонна. Один из ее “единичных интервалов” немонотонности - пара наборов (0,1,0) и (0,1,1), поскольку f(0,1,0)=1 и f(0,1,1)=0. Очевидно поэтому, что f(0,1,х)=Øх. Диаграмма Хассе, представляющая все пары соседних наборов и значения функции f на них, показана на рис. 1.10. Единичные интервалы немонотонности функции f выделены жирными линиями.

Рис.1.10. Диаграмма Хассе двоичных наборов

Шаг 3. Пусть F - нелинейная функция. Покажем, как с помощью констант и отрицания из нее можно построить конъюнкцию и дизъюнкцию. В нелинейной функции при разложении ее в полином Жегалкина всегда существуют термы, содержащие произведения переменных. Выберем самый короткий такой терм, содержащий не менее двух переменных. Пусть он К=х_i1x_i2...x_ik. Подставляя в F единицы вместо всех переменных, входящих в К, кроме двух из них, и нули вместо всех переменных F, не входящих в терм К, любую нелинейную функцию F можно привести к одной из следующих форм:

Легко видеть, что с помощью отрицания из всех этих функций можно получить как дизъюнкцию, так и конъюнкцию. Действительно, каждая форма справа является отрицанием соответствующей формы слева, поэтому рассмотрим только четыре левые формы. Первая из них - конъюнкция, последняя - дизъюнкция х и у. Вторая - конъюнкция хØу, третья - конъюнкция Øху.ÿ

Пример 1.13. Функция f, заданная таблицей 1.9, нелинейна: из примера 1.6 f(p,q,r)=1ÅpÅpqÅqr. Выберем один из минимальных термов - пусть это будет pq. Тогда f(p,q,0)=1ÅpÅpq. Легко видеть, что это функция Ø(pØq)= ØpÚq. Таким образом, pq=Øf(p,Øq,0), pÚq=f(Øp,q,0).ÿ

Пример 1.14. Таблица 1.11 показывает, принадлежат ли рассмотренным пяти замкнутым классам известные нам функции. Если функция не принадлежит замкнутому классу, в соответствующей позиции ставится знак Ö. Для выделения базиса, состоящего из этих функций, нужно найти строки, в совокупности покрывающие все пять столбцов знаком Ö. Кроме уже известных нам базисов, из таб.1.10 можно найти базис Фреге - {импликация, отрицание}, базис Гилберта - {импликация, дизъюнкция, константа 0} и т.д. ÿ

Таблица 1.11

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

Ф=(bÚcÚfÚhÚiÚj)&(aÚcÚgÚhÚi)&(aÚbÚdÚeÚfÚgÚhÚiÚj) )&(cÚfÚgÚhÚiÚj) )&(dÚeÚfÚhÚi).

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

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

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

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

Бинарные диаграммы решений (Binary Decision Diagrams, BDD).Это графы, являющиеся модификацией семантического дерева, в котором узлы с уже известным значением функции объединены [B86].

На рис. 1.11 показаны все четыре формы представления функции f примера 1.2.

Рис. 1.11. Четыре формы представления двоичной функции

Бинарные диаграммы решений в последнее время часто используются как форма представления булевой функции, когда нужно многократно вычислять ее значения при различных наборах значений ее аргументов. Для того, чтобы получить значение функции f примера 1.2, например, на языке Си, вместо хранения громоздкой таблицы истинности можно вычислить оператор: f=q? (r?0:1): (p?0:1), который построен на основании БДР

Булевы алгебры

Алгеброй называется множество с определенными на нем операциями. Обозначается алгебра обычно парой: (М, W), где М-множество, а W - множество операций над его элементами (часто называющееся сигнатурой). Результаты операций всегда принадлежат М.

Булевой алгеброй называется алгебра со следующими свойствами. Сигнатура операций в булевой алгебре содержит две бинарные операции “+” и “×”, одну унарную операцию “ ’ ” и две нульарных операции (константы) 0 и I. Для любых x,y,zÎM справедливы законы:

Идемпотентность: х+х=х, х×х=х;

Коммутативность: х+у=у+х, х×у=у×х;

Ассоциативность: х+(у+z)=(х+у)+z,

x×(y×z)=(x×y) ×z;

Поглощение: х×(х+у)=х, х+(х×у)=х;

Дистрибутивность: х+(у×z)=(x+y)×(x+z),

x×(y+z)=(x×y)+(x×z);

Дополнение: x×0=0; x+0=x, x×I=x, x+I=I;

Обратный элемент: Для любого х из М существует такой х’ в М, что: х×х’=0, x+x’=I.

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

Очевидна связь булевых алгебр и двоичных функций. Множество М составляют все двоичные функции, множество операций W - дизъюнкция, конъюнкция и отрицание, а нульарные операции - тождественные функции 0 и 1. Но интересно, что и многие другие модели являются булевыми алгебрами, и для них можно интерпретировать многие свойства двоичных функций. Например, булеву алгебру представляет собой любое множество всех подмножеств произвольного множества А, с операциями объединения, пересечения и дополнения множеств, а нульарные операции - это пустое подмножество и полное множество А. Интерес к изучению булевых алгебр состоит в том, что как только для некоторой математической структуры - множества и определенных на нем операций - доказано выполнение только семи указанных выше законов, можно быть уверенным, что огромное количество свойств булевых алгебр также справедливы для этой структуры. Например, на множестве всех подмножеств выполняется закон (де Моргана): “Дополнение к пересечению двух множеств равно объединению дополнений этих множеств” (доказать).

Задачи к главе 1.

1.1 Существует теорема геометрии о трех перпендикулярах: “Прямая, проведенная на плоскости перпендикулярно к проекции наклонной, перпендикулярна к самой наклонной”. Если эта теорема доказана, то нужно ли доказывать утверждения (А): “Прямая, проведенная на плоскости не перпендикулярно к наклонной, не перпендикулярна к ее проекции” и (В): “Прямая, проведенная на плоскости перпендикулярно к наклонной, перпендикулярна к ее проекции”?

1.2 Используя следующую лемму о разложении булевой функции: f(x₁,...,х_i,...,х_m)=(1Åх_i)f(x₁,...,0,...,х_m)Åх_if(x₁,...,1,...,х_m),
доказать, что множество { &, Å, 1} - базис. Построить на основе этой леммы представление функции, заданной таблично, в виде полинома Жегалкина.

1.3 Проверить свойство дистрибутивности:
(а) импликации и конъюнкции;
(б) импликации и дизъюнкции.

Указание. Использовать таблицы истинности.

1.4 Выразить функцию xy ÞzÚu с помощью стрелки Пирса.

1.5 Преобразовать равносильно формулы так, чтобы они содержали только указанные операции:
а) (хÞØу)Þ(уÚz); операции: конъюнкция и отрицание.
б) (хÚу)&(ØхÚØy)Þ (xÛy)(ØxÛØy); операции: дизъюнкция и отрицание.
в) Ø(хÞØу)Þ(ØхÚz); операции: импликация и отрицание.

1.6 Проверить аналитически эквивалентность формул: (АÚВ)(ØАÚС) и (АÚВ)(ØАÚС)(ВÚС).

Указание. В СДНФ, СКНФ и в форме полинома Жегалкина булевы функции имеют единственное представление. Поэтому приведя каким-либо способом обе формулы к любой из этих форм, получим решение задачи.

1.7 Является ли набор функций {Û, Ú, 0} функционально полным? Реализовать в нем функцию Å.

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

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

1.10 Построить функциональную схему двоично-десятичного счетчика по модулю 10.

1.11 Семисегментная структура светодиодов используется для отображения следующих букв русского алфавита: Б, Г, Е, О, П, Р, С, Ь, Н. Построить схему отображения.

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

1.13 В 1943 г. У. Мак-Каллок и У. Питтс предложили формальную модель нейрона в виде логической схемы, имеющей конечное число двоичных входов и один двоичный выход. Входы могут быть возбуждающими или тормозящими (в последнем случае со входа вводится отрицательная единица возбуждения). Нейрон возбуждается, если суммарное возбуждение не меньше некоторого порога срабатывания q.

Рассмотрим формальный нейрон с двумя входами {x1,x2}, изображенный на рис.1.12 ([ГП87]). Вход х1 здесь тормозящий, он изображается петлей на теле формального нейрона; вход х2 - возбуждающий. Суммарное возбуждение S для этой схемы рассчитывается так: S = (-х1) + 2*х2.

Рис.1.12. Пример формального нейрона

С изменением порога логические функции, реализуемые этим нейроном, изменяются. Например, при пороге q=0 выход у=Øх1Ùх2, при пороге q=1 выход у=х2 и т.д. Можно ли имея только один такой двухвходовой нейрон строить все возможные конечные функциональные преобразователи, задавая различные значения порога?

1.14 Двоичная логика представляет мир “в черно-белом свете” - элементы ее могут принимать значения только 1 и 0, что соответствует “ДА” и “НЕТ”, или “ИСТИНА” и “ЛОЖЬ”. Обобщением двоичной логики является многозначная логика, в которой высказывания могут принимать значения, отражающие некоторую долю уверенности, например, в трехзначной логике значения 1, 1/2 и 0 могут соответствовать “ДА”, “НАВЕРНОЕ” и “НЕТ”, а в четырехзначной значения 1, 2/3, 1/3 и 0 могут соответствовать “ДА”, “ВЕРОЯТНО, ЧТО ДА” “ВЕРОЯТНО, ЧТО НЕТ” и “НЕТ”. Построить в этих логиках унарную функцию, соответствующую отрицанию и бинарные функции, соответствующие дизъюнкции и конъюнкции. Выполняются ли в этих логиках законы булевой алгебры?

ЛИТЕРАТУРА к Главе 1.

[КАВ88] O.П. Кузнецов, Г.М. Адельсон-Вельский. Дискретная математика для инженера // Энергоатомиздат, М. - 1988.

[ГП87] М.А. Гаазе-Рапопорт, Д.А. Поспелов. От амебы до робота: модели поведения // “Наука”, М., 1987

[TS92] J. Turek, D. Sasha. The Many Faces of Consensus in Distributed Systems // IEEE Computer, July, 1992

[B86] R. E. Bryant. Graph-Based Algorithms for Boolean Function Manipulation // IEEE Transaction on Computers, vol. C-35, No 8, August 1986, pp. 677-691.

[П74] Д. А. Поспелов. Логические методы анализа и синтеза схем // “Энергия”, М., 1974

[БП96] Б. Н. Попов. Анализ и синтез законов управления системой “Импульсный усилитель мощности - электродвигатель” // Известия АН РАН. Теория и системы управления. - 1996, N 3, c.94-102.

[ФК84] Т. Фудзисава, Т. Касами. Математика для радиоинженеров. Теория дискретных структур // М., “Радио и связь”, 1984