ПОПУЛЯРНЫЕ ЛЕКЦИИ ПО МАТЕМАТИКЕ
ВЫПУСК
С.С. МАРЧЕНКОВ
БУЛЕВЫ ФУНКЦИИ
МОСКВА, 2002

УДК 519.7
ББК 22.176
М25
Марченков С. С. Булевы функции.— М.: ФИЗМАТ ЛИТ, 2002.—
68 с— ISBN 5-9221-0253-2.
Брошюра знакомит читателя с булевыми функциями — одним из важ-
важнейших классов дискретных функций. В ней излагаются основные понятия
теории булевых функций, доказывается критерий функциональной полно-
полноты и рассматриваются вопросы сложности реализации булевых функций.
Брошюра предназначена для школьников старших классов и студентов
первых курсов.
Табл. 4. Ил. 11.
ISBN 5-9221-0253-2	© ФИЗМАТЛИТ, 2002
© С.С. Марченков, 2002

ПРЕДИСЛОВИЕ
С понятием функции сегодня знаком каждый выпускник средней
школы. И это закономерно — понятие функции относится к тем немно-
немногим понятиям, которые пронизывают все разделы математики.
В математике имеется огромное число различных типов функ-
функций. Однако есть в ней такие функции, которые по праву должны
быть названы самыми простыми. Речь идет о булевых функциях 1) —
функциях, которые определены на множестве, состоящем из двух эле-
элементов. Уменьшить это множество до одного элемента невозможно —
происходит вырождение понятия функции. Поэтому булевы функции
занимают первую ступень в иерархии функций, ниже которой распо-
располагаются только константы.
Как математический объект булевы функции начали интенсив-
интенсивно изучаться лишь около 50 лет назад. Примерно в то же время
появились и первые электронные цифровые вычислительные маши-
машины. Совпадение этих двух событий неслучайно. Дело в том, что
по ряду причин технического и математического характера язык,
на котором "говорят" ЭВМ, есть язык двух символов: да-нет, 0-1.
Поэтому описывать работу ЭВМ и программировать на ЭВМ удоб-
удобно с использованием булевых функций. Булевы функции оказались
также подходящим инструментом для описания функционирования
широкого круга дискретных преобразователей информации, кото-
которые не относятся к универсальным вычислительным машинам: пе-
переключателей, коммутаторов, простейших сумматоров и некоторых
других.
Бурное развитие вычислительной техники, а также запросы со
стороны смежных разделов математики поставили перед специали-
специалистами по булевым функциям целый ряд серьезных математических
проблем: анализ различных форм и возможностей представления
булевых функций, оценки сложности реализации булевых функций
формулами и схемами, оценки сложности построения оптимальных
формул и схем и некоторые другие. Эти проблемы и направления ис-
исследований и по сей день остаются центральными в теории булевых
функций.
) Свое название булевы функции получили по имени английского ма-
математика Дж. Буля (G. Boole, 1815-1864).

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

Глава I
ЭЛЕМЕНТАРНЫЕ СВОЙСТВА
БУЛЕВЫХ ФУНКЦИЙ
§ 1. Табличное задание булевых функций
Булевы функции определяются на множестве, состоящем из двух
элементов. В качестве этих элементов обычно берутся числа 0 и 1.
Будем обозначать множество, состоящее из 0 и 1, через В. Булеву
функцию определим как функцию, аргументы которой принимают
значения из В со значениями, также принадлежащими В.
Булеву функцию / (от) п аргументов обозначают через /(xi, ...
...,жп) и называют также булевой функцией (от) п переменных.
Иногда в обозначениях булевых функций вместо переменных
х\, Ж2,... используют переменные y,z,w,..., возможно, с индексами.
Булева функция f(xi,... ,хп) ставит в соответствие каждому
упорядоченному набору (ai,... ,an), состоящему из элементов 0 и 1,
единственный элемент множества В — значение /(ai,... ,an). Как
же задают функцию /(xi,..., хп)?
Чтобы ответить на этот вопрос, найдем предварительно число эле-
элементов множества Вп, состоящего из всех упорядоченных двоичных
(имеются в виду элементы 0 и 1) наборов (ai,... ,an) длины п. До-
Докажем, что это число равно 2П. Доказательство проведем с использо-
использованием принципа полной математической индукции.
Очевидно, что множество В1 состоит ровно из двух наборов. Пред-
Предположим по индукции, что для данного п (п ^ 1) множество Вп со-
состоит из 2П наборов, и рассмотрим множество Вп+1. Каждый дво-
двоичный набор (ai,..., ап) длины п порождает два различных набора
(ai,..., an, 0), (ai,..., an, 1) из множества Bn+1. При этом если набо-
наборы (ai,..., ап) и (Ь]_,..., Ьп) из Вп различны, то при любом выборе
элементов an+i и 6n+i из множества В будут различными и наборы
(ai,... ,an,an+i), (Ьь ... ,6n,6n+i).
Следовательно, число наборов в множестве Вп+1 в два раза больше
числа наборов в множестве Вп. Поскольку последнее число по пред-
предположению индукции есть 2П, первое число будет равно 2П • 2 = 2n+1.
Определив число наборов в множестве Вп, вернемся к вопросу о
задании булевой функции f(xi,...,xn). Проще всего ее можно за-
задать так называемым табличным способом: перечислить в некотором
порядке все наборы из множества Вп и вслед за каждым набором за-
записать значение функции / на этом наборе. Наиболее наглядно реа-

6	Гл. I. Элементарные свойства булевых функций
лизовать этот способ задания булевой функции можно действительно
в виде таблицы (табл. 1).
В левой части этой таблицы выписаны по строкам все 2П дво-
двоичных наборов длины п. Порядок, в котором они расположены в
таблице (сверху вниз), носит название лексикографический порядок.
Таблица 1
XI
0
0
1
1
0 .
0 .
1
1 .
. хп
. 0
1
. 0
. 1
f(xi,
/@
/@
/A
/A
Х2,.
,0,..
,0,..
,1,..
..,хп)
.,0)
•,1)
.,0)
-,1)
Первым относительно этого порядка является нулевой набор, а каж-
каждый следующий набор получается из предыдущего прибавлением 1.
При этом мы считаем, что каждый набор является записью подходя-
подходящего неотрицательного целого числа в двоичной системе счисления,
а имеющиеся слева нулевые разряды поставлены лишь для того, что-
чтобы все наборы имели одну и ту же длину п.
Условимся о том, что, говоря о табличном способе задания бу-
булевой функции, мы всегда будем иметь в виду, что в левой части
соответствующей таблицы двоичные наборы выписаны именно в лек-
лексикографическом порядке. В этом случае для всех булевых функций
от п переменных левая часть табл. 1 будет одной и той же. Поэтому
потребность в ее воспроизведении, вообще говоря, отпадает. Тогда от
табл. 1 остается только столбец значений функции / высоты 2П.
Таким образом, мы приходим к выводу, что любую булеву функ-
функцию от п переменных можно задать двоичным столбцом высоты 2П.
Верно, разумеется, и обратное: всякий двоичный столбец высоты 2П
определяет некоторую булеву функцию от п переменных.
На практике вместо двоичных столбцов высоты 2П удобнее пользо-
пользоваться двоичными строками (наборами) длины 2П. При этом первый
элемент столбца становится первым элементом строки, второй эле-
элемент столбца — вторым элементом строки и т.д. В результате для
булевой функции /(xi,... ,жп) получаем двоичную строку вида
(/@,0,...,0)/@,0,..., 1) ... /A,1,..., 0) /A,1,..., 1)). A)
Итак, каждую булеву функцию /(xi,... ,хп) можно представить
двоичным набором A) ее значений длины 2П и всякий двоичный набор
длины 2П определяет некоторую булеву функцию от п переменных.
Нетрудно заметить, что данное соответствие, как говорят, взаимно
однозначно: различным булевым функциям от п переменных (раз-
(различным двоичным наборам длины п) отвечают различные двоичные

§2. Некоторые элементарные булевы функции
наборы длины 2П (различные булевы функции от п переменных). Это
позволяет найти число всех булевых функций от п переменных. Дей-
Действительно, оно равно числу всех двоичных наборов длины 2П, т.е.
числу всех элементов множества В2™. Как мы установили выше, дан-
данное число равно 22 .
Множество всех булевых функций принято обозначать через Р^.
УПРАЖНЕНИЯ
1. Каково число булевых функций от п переменных, которые на
фиксированных к двоичных наборах {к ^ 2П) принимают фиксиро-
фиксированные к значений?
§ 2. Некоторые элементарные булевы функции
Составим таблицу для всех четырех булевых функций одной пе-
переменной.
Таблица 2
X
0
1
0
0
1
1
/з(я)
0
1
/4 (*)
1
0
Функции fi(x) и /2(х) называются константами 0 и 1. Их часто
так и обозначают 0 и 1, не указывая явно переменную х. Как видно
из табл. 2, значения функции /з(ж) совпадают со значениями пере-
переменной х. Поэтому функцию /з(х) называют тождественной функ-
функцией и вместо символа функции, как правило, пишут лишь символ
переменной х. Функция /4 (х) осуществляет инвертирование значений
переменной х. Ее называют отрицанием и обозначают х (читается:
не икс).
Обратимся далее к функциям от двух переменных. Как мы знаем,
их насчитывается ровно 22 =16. Мы могли бы поступить так же,
Таблица 3
XI Х2
0 0
0 1
1 0
1 1
h
0
0
0
0
/2
1
1
1
1
/3
0
0
1
1
/4
0
1
0
1
/5
1
1
0
0
/б
1
0
1
0
/7
0
0
0
1
/8
0
1
1
1
/9
0
1
1
0
/ю
1
1
0
1
/11
1
1
1
0

8	Гл. I. Элементарные свойства булевых функций
как с функциями от одной переменной, и представить в одной таб-
таблице значения всех 16 функций. Однако на первых порах нам будет
достаточно познакомиться с одиннадцатью функциями (по техниче-
техническим причинам в табл. 3 после символов функций опущены символы
переменных xi, X2).
Как видно из табл. 3, функции Д (х\, жг) и /2(х±, жг) являются кон-
константами 0 и 1. Значения функции /3(^1,^2) совпадают со значения-
значениями переменной х\. Поэтому функцию /з(ж1,Ж2) называют функцией
выбора (первого аргумента) или селекторной функцией и обозначают
е^(ж1,Ж2). Так же, как для тождественной функции одной перемен-
переменной, вместо выражения е\{х\,Х2) часто пишут лишь х\. Аналогично
обстоит дело с функцией f±{x\, Ж2), которая представляет собой функ-
функцию выбора (второго аргумента) и обозначается е\{х\,Х2)* Функции
/5(^1,^2) и /б(^1,Ж2) инвертируют соответственно значения перемен-
переменных х\ и Ж2- Поэтому их обычно заменяют функциями х\ и х^-
Анализируя столбец значений функции /7(^1,^2), нетрудно по-
понять, что эту функцию можно определить как х\ • х<± или как
mm(xi,X2). Функция /7 — одна из важнейших в логике и теории бу-
булевых функций. Она носит название конъюнкции (или логического
произведения). Для функции /7(^1,^2) приняты обозначения: х\ • х<±
(или Ж1Ж2), х\ & Х2 и х\ Л Х2- (Так же, как в арифметике и алгебре,
при написании некоторых функций от двух переменных знак функ-
функции может ставиться между символами переменных.) В дальнейшем
мы будем преимущественно использовать обозначения х\ -Х2 или х±Х2
(читается: х\ и жг).
Легко проверить, что функцию fs(%i,%2) можно определить
как тах(ж1,Ж2). Функция /§ также относится к числу важнейших
в логике и теории булевых функций. Функцию fs(xi,X2) называют
дизъюнкцией (или логической суммой) и обозначают х\ V Х2 (читает-
(читается: х\ или жг).
Функция /э(ж1,Ж2) есть сложение по модулю 2 A + 1 = 0 по мо-
модулю 2). В отличие от обычного (арифметического) сложения х\ + Х2
она обозначается х\ 0 Х2-
Функция fio(xi,X2) носит название импликация и обозначается
х\ —У Ж2- Название "импликация" пришло из логики, где имеется со-
соответствующая логическая связка импликация.
Наконец, функция /ц(ж1,Ж2) называется штрихом Шеффера (или
антиконъюнкцией) и обозначается х\ | Ж2-
Для любого натурального п и любого г A ^ г ^ п) обозначим
через
е^ \Х\,..., Xij..., хп)
функцию выбора г-го аргумента (или селекторную функцию), значе-
значения которой совпадают со значениями переменной Х{. Отметим, что
вместо функции ef(xi,..., ж«,..., хп) часто записывают лишь пере-
переменную Xi.

§3. Существенные и фиктивные переменные
УПРАЖНЕНИЯ
2. Достройте табл. 3, выписав столбцы значений остальных пяти
булевых функций. Используя приведенные выше названия функций
от двух переменных, попытайтесь дать подходящие названия этим
пяти функциям.
3. Существенные и фиктивные переменные
Когда говорят, что булева функция /(xi,..., хп) зависит от пере-
переменных Ж].,... ,жп, имеют в виду лишь то, что функция / является
функцией п переменных, которые обозначены через Ж1,...,жп. Од-
Однако в теории булевых функций важным является не только зависи-
зависимость функции от переменных, но и так называемая существенная
зависимость функции от переменной. Прежде чем дать строгое опре-
определение этому понятию, посмотрим на "степень" зависимости функ-
функции от переменных на примерах функций /i(xi,X2),..., fu(xi,X2).
Функция fi(xi,X2) есть константа 0. Для этой функции любое
изменение значений переменных не влечет за собой изменения зна-
значения функции. В этом смысле переменные х\,Х2 можно было бы
назвать несущественными для функции fi(xi,X2). Аналогичное за-
замечание следует сделать и по поводу функции /2ОЕ1, жг).
Несколько иная ситуация имеет место для функции /3(^1,^2)-
Поскольку значения функции /3(^1,^2) совпадают со значениями
переменной Ж1, значения переменной х\ являются существенными
для функции /з(^1,Ж2). Напротив, значения переменной х<± никак не
влияют на значения функции /з(жъЖ2). Таким образом, перемен-
переменную Х2 следует считать несущественной для функции /з(жъЖ2).
Аналогичные рассуждения можно провести для функций /4, /б,
/б и прийти к выводу, что переменная х\ является существенной
для функции /5(^1,^2) и несущественной для функций /4(^1,^2),
/б(ж1,Ж2), а переменная х<± — существенной для функций /4(^1,^2),
fe(xi,X2) и несущественной для функции /б(жъХ2)-
Обратимся теперь к конъюнкции /7(^1,жг). Нетрудно заметить,
что обе переменные Ж1, х^ являются для нее существенными. В са-
самом деле, из равенств /7@,1) = 0, /7A,1) = 1 следует, что при фик-
фиксированном значении 1 переменной х<± изменение значения перемен-
переменной х\ влечет за собой изменение значения функции. Следовательно,
переменная х\ является существенной для функции /7(^1^2). Ана-
Аналогичным образом, рассматривая наборы A,0) и A,1), убеждаемся в
существенности переменной х^-
Проверьте, что оставшиеся функции fs(xi,X2), • • • ? /11(^1, Ж2) так"
же существенно зависят от обеих переменных.

10	Гл. I. Элементарные свойства булевых функций
Приведем теперь строгое определение существенной зависимости
функции от переменной.
Функция /(xi,..., Xi,..., хп) существенно зависит от перемен-
переменной Xi, если имеются такие значения ai,..., a^-i, сц+i,... ,ап пере-
переменных Ж]_, . . . ,Xi_i,Xi+i, . . . ,ЖП, ЧТО
/(ab.. .,ai_i,0,ai+b... , ап) 7^ /(ai,..., а;_ь 1, а;+ь ... ,ап).
Приведенному определению существенной зависимости можно
придать несколько иную форму.
Функция f(xi,..., Xi,..., хп) существенно зависит от перемен-
переменной Xi, если имеются такие значения ai,..., a^-i, ^i+i, • • • •> &п пе-
переменных x\,..., Xi_i, Xf+i,..., xn, что функция одной переменной
/(ai,..., a,i-i,Xi, a^+i,..., жп) не является константой (т.е. совпадает
С ОДНОЙ ИЗ фуНКЦИЙ Xi ИЛИ Xi) .
Если функция f(xi,... ,хп) существенно зависит от перемен-
переменной Xi, то переменная xi называется существенной переменной функ-
функции /(xi,... , жп). В противном случае переменная xi называет-
называется несущественной или фиктивной переменной функции f(xi,...
...,жп).
Из определения существенной зависимости видно, что при вычис-
вычислении значений функции реально используются лишь значения суще-
существенных переменных. В связи с этим возникает желание освободить-
освободиться от "ненужных" фиктивных переменных. Если, например, известно,
что существенными переменными булевой функции /(xi,... ,хп) яв-
являются переменные xi,...,хш {т < п), а переменные xm+i,...,хп
фиктивны, то избавиться в функции /(xi,... ,хп) от фиктивных пе-
переменных жт+1,...,жп можно различными способами. Один из них
состоит в том, чтобы значения функции / рассматривать только на
наборах (ai,..., an), у которых am+i = ... = ап = 0. Это соответст-
соответствует подстановке константы 0 на места переменных жт+1,...,жп:
f(xi,... ,жт,0,... ,0). При другом способе переменным жт+1,... ,хп
придают значения какой-либо из переменных xi,... ,хт, например,
переменной х\. Как говорят в таких случаях, переменные xm+i,...
...,жп отождествляют с переменной х\\ /(xi,... ,xm,xi,... ,xi).
Возмож:ны, разумеется, и любые комбинации подобных способов.
На практике нередко встречается обратная задача. Имеется функ-
функция g(xi,... ,хт) и требуется "добавить" к ней фиктивные перемен-
переменные жт+1,...,жп. В этом случае искомую функцию f(xi,... ,хп)
можно определить равенством
/Ol, . . . , Хт, Хт+1, . . . , Хп) = д(хг, . . . , Хт),	B)
которое выполняется при любых значениях переменных xi,...,xn.
Вообще, этот прием показывает, что функцию #(жъ...,жш) можно
считать зависящей от любого числа дополнительных фиктивных пе-
переменных. При этом важно лишь помнить, что с функциональной

§3. Существенные и фиктивные переменные	11
точки зрения переход от функции д к функции /, даваемый равенст-
равенством B), приводит к появлению нового объекта: функция / опреде-
определена на множестве Вп, тогда как функция д — на множестве Вт.
Приведенные рассуждения показывают, что введение и удаление
фиктивных переменных можно осуществить сравнительно простыми
средствами, практически "даром". Это особенно важно при введении
фиктивных переменных. В связи с этим в теории булевых функций
иногда для функции указывают лишь те переменные, от которых она
зависит существенно. При этом предполагается, что от всех остальных
переменных, которые встречаются в дальнейших построениях, данная
функция зависит фиктивно.
Следует отметить, что при введении и удалении фиктивных пе-
переменных необходимо проявлять известную осторожность. Пусть, на-
например, имеется булева функция #(жъЖ2,жз) и мы хотим ввеДением
фиктивных переменных получить из нее булеву функцию, зависящую
от переменных xi,... ,х&. Довольно просто сообразить, что достичь
этого можно различными способами. Прежде всего, напрашивается
"естественный" способ введения: добавляемые переменные х±, х§ фик-
фиктивны, а искомая функция /i(xi,..., Ж5) определяется равенством
/i(xi,x2,X3,X4,x5) = д(х1,х2,х3).	C)
Однако можно поступить иначе: к переменным функции д доба-
добавить две новые переменные так, чтобы "старые" переменные xi, X2, %з
функции д для вновь определяемой функции /2(^1,..., х^) оказались
соответственно второй, четвертой и пятой переменными. Этот вари-
вариант введения фиктивных переменных дается равенством
/2(ж1,ж2,жз,ж4,ж5) =#О2,ж4,ж5).	D)
Разумеется, на этом пути введения фиктивных переменных существу-
существует еще несколько различных функций /г(жь..., Ж5), каждая из кото-
которых определяется выбором трех различных переменных хр, xq, xr из
множества {xi,... ,х$} и использованием в равенствах C), D) соот-
соответствующей функции g(xpjxqjxr).
По традиции, сложившейся в отечественной школе дискретной ма-
математики, булевы функции рассматриваются с точностью до несу-
несущественных переменных. Это означает, что наряду с любой булевой
функцией / считаются одновременно заданными все функции, ко-
которые получаются из / введением или удалением несущественных
переменных. Иногда такие функции называют равными, хотя, стро-
строго говоря, они различаются уже как функции, имеющие различные
количества переменных. Мы в дальнейшем не будем употреблять тер-
термин "равные" в этом смысле. Тем не менее равенства типа C) или D)
будут использоваться.
Весьма распространенным способом введения фиктивных пере-
переменных является способ введения с помощью селекторных функций.

12	Гл. I. Элементарные свойства булевых функций
Пусть мы имеем булеву функцию д от т переменных и хотим по-
получить из нее функцию /, удовлетворяющую тождеству B). Тогда
функцию / можно определить так:
/Oi,..., хп) = g(e1l(x1,..., хп),..., e^(xi,..., хп)).	E)
Преимущество этого способа состоит в том, что переменные xm+i,...
..., хп не появляются "ниоткуда", как это происходит при переходе от
правой к левой части равенства B). Наряду с переменными х\,..., хт
они изначально присутствуют в правой части равенства E). Поэтому
данный способ введения фиктивных переменных с математической
точки зрения представляется более корректным. К недостаткам его
можно отнести то, что среди "исходных" булевых функций селектор-
селекторные функции присутствуют далеко не всегда.
УПРАЖНЕНИЯ
3.	Найдите существенные и фиктивные переменные функций
#1(^1,^2,^3) и #2(^1,^2,^3), заданных двоичными наборами
A0100101) и @0010111).
4.	Пусть функция f(xi,...,xn) задана двоичным набором
(ai ... a2n-ia2n-i+1 ... а2^), а функция g(xi,... ,жп) — набором
(а2™ ... a2n-i+1a2n-i ... а\). Как соотносятся существенные и фиктив-
фиктивные переменные функций / и д?
5.	Назовем булеву функцию симметрической, если она принима-
принимает одинаковые значения на любых двух наборах, содержащих одина-
одинаковое количество единичных компонент. Докажите, что всякая сим-
симметрическая булева функция, отличная от константы, существенно
зависит от всех своих переменных.
§ 4. Представление булевых функций формулами
Табличный способ является универсальным способом задания бу-
булевых функций. В нем в самой простой форме отражена функци-
функциональная зависимость значений функции от значений аргументов.
Однако в математике часто возникает необходимость установить
функциональные связи между значениями функции для нескольких
наборов значений аргументов либо между значениями различных
функций. Табличный способ для этих целей, как правило, не под-
подходит. Обычно для этого используют формулы различных типов.
Самые простые формулы обобщают идею перехода от значений
аргументов к значениям функции и допускают использование других
функций в качестве аргументов. Так, например, обращаясь к элемен-
элементарной алгебре, видим, что формула
(xi +ж2) • х2 +xi -ж3,	F)

§4- Представление булевых функций формулами	13
составленная из символов переменных х\,Х2,х% и символов функ-
функций + и •, указывает на определенную последовательность при вы-
вычислении функции, представленной этой формулой: например, снача-
сначала вычисляем х\ + Х2, затем (х\ + Х2) • Х2, далее х\ • жз и, наконец,
[х\ + Х2) • Х2 + х\ • жз- При этом функции + и • в формуле F) счи-
считаем известными, "элементарными", а формула F) лишь организует
процесс вычисления значений функции, представленной этой форму-
формулой, исходя из значений переменных х\, Х2, х% и используя заданные
функции + и •.
Переходя к булевым функциям, предположим, что имеется некото-
некоторое непустое множество F булевых функций. Мы хотим ввести поня-
понятие формулы, составленной из символов функций множества F (как
говорят, формулы над множеством F). Сразу отметим, что нам не
важно, какие именно функции входят в множество F и как они зада-
заданы. Нам важно лишь то, что каждая функция из F имеет собственное
"имя" — индивидуальное обозначение.
С помощью индукции (по построению) определим понятие форму-
формулы над F. Пусть / есть обозначение функции от п переменных из
множества F, а х\,..., хп — символы переменных. Тогда выражение
/(ж1,...,жп) считаем формулой над F. Пусть, далее, g есть обозна-
обозначение функции от т переменных из множества F, а А\,..., Аш —
либо уже определенные формулы над F, либо символы переменных
(не обязательно различные). Тогда выражение g(Ai,..., Ат) считаем
формулой над F.
Пусть, например, F есть множество булевых функций, состоящее
из функций ~ (отрицание), • (конъюнкция), V (дизъюнкция), 0 (сло-
(сложение по модулю 2), —У (импликация), | (штрих Шеффера). Тогда
согласно приведенному выше определению следующие выражения бу-
будут являться формулами над F:
хз,
х2)^
(Х2 V X!
(xi • хЛ)
) -х±,
XI,
(х2 • (х3 • х
((ж4 х2) —У (
i)) e (хз
хз 6ж5)
V(a
) -».
((xi Vx2)
(чтобы не усложнять вид формул, мы не пишем скобок при исполь-
использовании отрицаний от переменных).
Понятно, что формулы предназначены для задания булевых функ-
функций. Как же определить функцию, задаваемую (или, как говорят, ре-
реализуемую) конкретной формулой? Для этого надо вновь обратиться
к определению понятия формулы над F и параллельно этому опре-
определению ввести определение функции, реализуемой формулой над F.
Если / есть обозначение функции от п переменных из F, то фор-
формула /(ж1,...,жп) реализует ту самую функцию от п переменных,
обозначением которой служит /. (Этот пункт определения может по-
показаться несколько туманным или даже содержащим противоречие.

14	Гл. I. Элементарные свойства булевых функций
Однако следует, видимо, еще раз обратить внимание на то, что функ-
функция — это отображение одного множества в другое, если угодно, ал-
алгоритм или процесс. Тогда как / есть всего лишь обозначение этой
функции, ее "имя".)
Пусть теперь д — обозначение функции от т переменных из F,
а А\,..., Аш — формулы над F либо символы переменных. И пусть
каждому выражению Ai, которое представляет собой формулу над F,
уже сопоставлена функция hi, реализуемая этой формулой Ai. Если
же выражение Ai представляет собой символ переменной Xj, то со-
сопоставим ему тождественную функцию hi(xj), значения которой сов-
совпадают со значениями переменной Xj. Тогда формула g(Ai,... ,Ат)
реализует функцию
g(hu...,hm).	G)
Сделаем несколько замечаний по поводу определения функции G).
Во-первых, по понятным техническим причинам мы не выписываем
переменные, от которых зависят функции hi,..., hm: у каждой функ-
функции hi могут быть свои переменные, не совпадающие, вообще говоря,
с переменными других функций /ц..
Во-вторых, мы оставили в стороне вопрос о том, что же представ-
представляет собой функция G). Мы не хотели бы приводить здесь точные,
но громоздкие определения. Вместо этого обратимся к примерам.
По-видимому, все читатели представляют себе, как вычисляются
значения функции
g(h1(x1,...,хп),..., hm(x1,...,хп)),
если функции д, hi,..., hm предполагаются известными: для любого
двоичного набора (ai,..., ап) вычисляем значения
hi(ai,...,an), ..., hm(ai,... ,ап),
образуем двоичный набор
(/ii(ab... ,ап),... ,hm(ai,.. .,an))
и, используя функцию д, вычисляем ее значение на этом наборе.
Чуть более сложной является формула
Здесь по заданному двоичному набору (ai, a2, а%, а^) необходимо сна-
сначала вычислить значения hi{a^ai) и /12(^3,^2,^1), затем образовать
двоичный набор
(/ii(a4, ai), a3, h2(a3, a2, ai))
и найти значение функции д на этом наборе.
На этом примере уже хорошо видны те трудности, которые под-
поджидают нас при определении функции G): все они связаны с тем, что
переменные в функциях hi,..., hm могут быть "перемешаны" каким
угодно образом.

§5. Эквивалентность формул	15
Чтобы облегчить изложение некоторых результатов, требующих
для своего доказательства анализа сложных формул, нередко посту-
поступают следующим образом. Пусть, к примеру, требуется проанализи-
проанализировать формулу G), в которой функции hi,...,hm зависят от раз-
различных переменных. Допустим, что xi,...,xn суть все переменные,
от которых зависит хотя бы одна из функций /ii,..., hm. Если функ-
функция hi зависит от переменных xkl,..., xki, то рассмотрим функцию
h[(xi,...,хп), которая получается из функции hi(xkl,...,xki) вве-
введением недостающих фиктивных переменных из множества {х\,...
..., хпу.
hi(x1,...,xn) = hi(xkl,...,xki).
Понятно, что формулы G) и
g(h[ (хг,..., хп),..., Ыт(хг,..., хп))	(8)
реализуют одну и ту же функцию. Вместе с тем гораздо предпочти-
предпочтительнее рассматривать формулу (8), нежели исходную формулу G).
Формально при совершении подобных замен мы отказываемся
от функций hi,..., hm, переходя, вообще говоря, к другим функци-
функциям h[,..., h'm. Однако вспомним, что мы условились рассматривать
функции с точностью до фиктивных переменных. В частности, на-
наряду с функциями hi,..., hm можно считать заданными и функции
/&!,..., h'm. Собственно, именно подобные технические трудности, воз-
возникающие при анализе сложных формул, и являются одной из основ-
основных причин для принятия нами соглашения о возможности рассмот-
рассмотрения функций с произвольным числом фиктивных переменных.
УПРАЖНЕНИЯ
6. Пусть функция f{xi,X2,xs) задается двоичным набором
@1101001), gi(xi,X2) = xi —У Х2, 92(xi,X2) = xi V Х2- Определите,
чему равны функции
§ 5. Эквивалентность формул
Из элементарной алгебры известно, что одну и ту же функцию
можно задать различными формулами. Так, например, формула F)
задает ту же функцию, что и формула
Xl • (Х2 + Хз) + х\.	(9)
Этот факт обычно выражают в виде высказывания "формула F) эк-
эквивалентна формуле (9)".

16	Гл. I. Элементарные свойства булевых функций
Аналогично обстоит дело и в теории булевых функций: формулы Ф
и Ф называются эквивалентными, если они реализуют одну и ту же
булеву функцию. Мы не вводим специального знака для обозначения
эквивалентности формул. Если формулы Ф и Ф эквивалентны, то
будем записывать это в виде Ф = Ф.
Для функций от одной и двух переменных, определенных в § 2,
можно выписать большое число связывающих их эквивалентностей.
Ниже приводятся лишь наиболее употребительные из них.
3.	ж = ж-ж = ж\/ж
4.	ж©1 = ж—)-0 =
5.	х о у = у о ж, где о есть любая из функций •, V, ©, | (коммута-
(коммутативность функции о).
6.	(х о у) о z = х о (у о z), где о есть любая из функций •, V, ©
(ассоциативность функции о).
7.	х • (у V z) = (х • у) V (х • z) (дистрибутивность конъюнкции
относительно дизъюнкции).
8.	ж V (у • z) = (х V у) • (х V z) (дистрибутивность дизъюнкции
относительно конъюнкции).
9.	х • (у © z) — (х • у) ф (х • z) (дистрибутивность конъюнкции
относительно сложения по модулю 2).
10.	х • у = х V у, х V у = х • у (правила де Моргана).
11.	х V (х • у) = х • (х V у) = х (правила поглощения).
12.	х 0 у = (х • у) V (х • у) = (х V у) • (х V у),
х V у = ((ж • у) © ж) © у = ж -»> 2/,
х ->• 2/ = ж V у = ((ж • у) © ж) © 1,
х\у = W^y.
Справедливость эквивалентностей 1—12 можно проверить непос-
непосредственно, используя табл. 2 и табл. 3.
Чтобы несколько упростить написание формул, часть скобок обыч-
обычно опускают. При этом руководствуются следующими правилами.
Внешние скобки у формул не ставятся. При использовании отрица-
отрицания скобки также не ставятся (читатель мог заметить, что мы уже
применяли эти правила). Далее, свойства ассоциативности б позволя-
позволяют при многократном применении одной и той же функции •, V или ©
опускать внутренние скобки. Если формула содержит символы функ-
функций •, ф, V, —>, |, то при отсутствии дополнительных скобок сначала
выполняют конъюнкцию, затем сложение по модулю 2, далее дизъ-
дизъюнкцию и, наконец, импликацию или штрих Шеффера. Например,
формулу
х • у (В z —> у - z\l х

§5. Эквивалентность формул	17
следует понимать так:
((х-у)фг) -+ ((y-z)Vx).
Применяя подходящие эквивалентности 1-12, докажем эквива-
эквивалентность формул
(ху V xz) 0 ((у —У z) —у ху) и xyz 0 у 0 z.
Подформулу ху V xz первой формулы преобразуем с использова-
использованием второй из эквивалентностей 12:
ху V xz = ху • xz 0 ху 0 xz.
Применяя коммутативность конъюнкции и свойство х • х = 0, полу-
получаем
Ху • XZ 0 Ху 0 XZ = Ж?/ 0 Ж2.
Таким образом,
ху V xz = ху (В xz.	A0)
При рассмотрении второй части (у —у z) —У ху первой из исходных
формул дважды применяем третью из эквивалентностей 12:
(у -У z) -у ху = (у V z) -У ху = у V z V ху.
Формулу у V z упрощаем с помощью правила де Моргана и первой из
эквивалентностей 3:
у\/ z = yz.
Следовательно, получаем
(у -У z) -^xy = yz\/ ху.
В правой части этой эквивалентности меняем местами х и у (комму-
(коммутативность конъюнкции), "выносим за скобку" у (применяем эквива-
эквивалентность 7 справа налево), меняем местами z и х (коммутативность
дизъюнкции) и используем затем вторую из эквивалентностей 12:
yz\/ ху = (ж V z)y = (xz 0 ж 0 z)y.	A1)
Пользуясь дистрибутивностью конъюнкции относительно сложения
по модулю 2 и складывая по модулю 2 выражения A0) и A1), полу-
получаем, что первая формула эквивалентна формуле
ху 0 xz 0 xyz 0 ху 0 з/?.
Заменяя в ней х, у, z наж01,?/01,2:01 и применяя дистрибутив-
дистрибутивность конъюнкции относительно сложения по модулю 2, приходим к
формуле
ху 0 xz 0 x^/z 0 Ж2/ 0 2/? = ху 0 ж 0 xz 0 2 0 ж^/2: 0 ху 0
®yz®y®xy®y®yz®y = xyz ®xy®xz®x®y®z. A2)
Нетрудно убедиться в том, что вторая формула, xyz(By(Bz, также
приводится к виду A2).
2 С.С.Марченков

18	Гл. I. Элементарные свойства булевых функций
УПРАЖНЕНИЯ
7.	Используя эквивалентности 1-12, докажите эквивалентность
следующих формул:
(х 0 yz) -> (х-> (у -> z)) и х -> ((у -> z) -> ж);
(х V yz) -> ((x ->у)-> ((у V z) -> х)) и (х -> у) -> (у -> х).
8.	Выясните, при каких п (n ^ 3) эквивалентны формулы
XI "^ (Ж2 ->" (Ж3 ~+ • • • ->" (Жп_1 ->> Жп) . . . )),
§ 6. Замыкание. Замкнутые классы
Одной из центральных проблем в теории булевых функций яв-
является проблема выразимости. В общем виде ее можно сформулиро-
сформулировать следующим образом. Имеются некоторое непустое множество F
булевых функций и булева функция /. Спрашивается, выразима ли
функция / через функции множества F?
Чтобы дать ответ на поставленный вопрос, необходимо сначала
уточнить, что понимается под выразимостью функции через другие
функции. Самой распространенной формой выразимости для буле-
булевых функций является выразимость с помощью формул. Более точ-
точно, будем говорить, что булева функция / выразима через функции
множества F, если существует формула над F, которая реализует
функцию /. Совокупность всех функций, выразимых через функции
множества F (т.е. реализуемых формулами над F), обозначим че-
рез [F].
Часто операцию порождения одних булевых функций другими с
помощью формул называют операцией суперпозиции функций. Соот-
Соответственно этому множество [F] называют замыканием множества F
относительно (операции) суперпозиции или просто замыканием F. Из
определения легко усматриваются следующие свойства замы-
замыкания.
1.	F содержится в [F].
2.	[[F]} = [F].
3.	Если F\ содержится в F2, то \F\\ содержится в [i^].
Если для множества булевых функций F выполняется равен-
равенство F = [F], то F называют замкнутым множеством или замкну-
замкнутым классом.
Рассмотрим некоторые примеры замкнутых классов. Прежде все-
всего, очевидно, что замкнутым классом является множество Р2 всех
булевых функций. Следующий наш пример связан с селекторными
функциями. Обозначим через C/qi множество всех селекторных функ-

§ 6. Замыкание. Замкнутые классы	19
ций ef(xi,... , жп) A ^ г ^ п, п = 1,2,...). Чтобы убедиться в том,
что Uoi образует замкнутый класс, достаточно проанализировать
"первый" шаг в определении формулы над ZToi, когда в селектор-
селекторную функцию ef(xi,...,xn) на места переменных xi,...,xn под-
подставляются выражения Ai,... ,Ап, которые являются либо селек-
селекторными функциями, либо символами переменных. Понятно, что
значения функции ef(Ai,..., Ап) будут совпадать со значениями вы-
выражения Ai. Однако значения Ai также совпадают со значениями
некоторой переменной. Следовательно, ef(Ai,..., Ап) — селекторная
функция.
Обозначим через Со множество всех булевых функций (от лю-
любого числа переменных), тождественно равных 0. Очевидно, что су-
суперпозициями функций, тождественно равных 0, можно получить
лишь функцию, тождественно равную 0. Поэтому Со — замкнутый
класс. Аналогично получаем, что замкнутым классом является мно-
множество С\ всех булевых функций, тождественно равных 1.
Пусть То есть множество всех булевых функций f(xi,..., хп), ко-
которые, как говорят, сохраняют константу 0, т.е. удовлетворяют ра-
равенству /@,..., 0) = 0. Покажем, что То — замкнутый класс. Для это-
этого так же, как и для класса С/оъ достаточно проверить, что функция
9{Уъ • • •»Ут) принадлежит классу То, если д(уъ ... ,ут) реализуется
формулой f(Ai,..., Ап), в которой / — функция из То, а А±,..., Ап
— либо функции из То, либо символы переменных. Поскольку пере-
переменную можно рассматривать как тождественную функцию (из клас-
класса То), то так же, как и в § 4, все выражения А\,..., Ап можно считать
функциями от переменных 2/ъ ..., 2/ш, т*е-
f(AU . . . , Ап) =
где функции /ii,..., hn принадлежат классу Tq. Теперь легко убежда-
убеждаемся в принадлежности функции д классу Tq: согласно определению
функций hi,...,hn имеем
/ц@,...,0) = ... = /in@,...,0) =0,
а согласно определению функции / имеем
Подобным образом можно показать, что замкнутым классом явля-
является множество Xi всех булевых функций, сохраняющих константу 1,
т.е. функций f(xi,... ,жп), удовлетворяющих равенству
Разумеется, далеко не каждое множество булевых функций пред-
представляет собой замкнутый класс. В качестве примера рассмотрим
множество Uoi всех "антиселекторных" функций ef(xi,... ,жп), где
в^ \Xi, . . . , Xi, . . . , Хп) — Xi.

20	Гл. I. Элементарные свойства булевых функций
В самом деле, в замыкание \Uq\\ по определению должна входить
функция, реализуемая формулой ё\(ё\(х)). Нетрудно видеть, что эта
функция совпадает с функцией е\(х). Однако е\(х) не содержится в
множестве Uq\. Значит, C/oi не является замкнутым классом.
С понятием замыкания тесно связано понятие полноты. Пусть R —
замкнутый класс, a Q — система функций из R. Говорят, что система
функций Q полна в классе R, если [Q] = R. Когда R совпадает с i^?
слова "в классе iV' обычно опускают.
Построение нетривиальных полных систем функций мы отложим
до следующего параграфа. А пока докажем простое и вместе с тем
полезное утверждение.
Теорема 1. Пусть система булевых функций Q полна в замк-
замкнутом классе R, Р — некоторое множество функций из R и лю-
любая функция системы Q реализуется формулой над Р. Тогда мно-
множество Р таксисе полно в классе R.
Доказательство. Возьмем произвольную функцию / из
класса R. По условию теоремы ее можно реализовать некоторой фор-
формулой Ф над Q. В свою очередь каждая функция из Q, которая участ-
участвует в построении формулы Ф, может быть реализована формулой
над Р. Заменим в формуле Ф вхождение каждого символа функции
из Q соответствующей формулой над Р. Мы получим формулу Ф'
над Р, которая, как легко понять, реализует ту же самую функцию /.
Теорема доказана.
Если система функций Q полна в замкнутом классе R, то говорят
также, что система Q порождает класс R, а класс R порождается
системой Q.
Из определения замыкания видно, что замкнутый класс потен-
потенциально может содержать бесконечное число булевых функций. Ра-
Разумеется, при задании такого класса мы не можем перечислить все
входящие в него функции. В связи с этим хотелось бы иметь некото-
некоторый финитный (конечный) способ описания замкнутых классов. Один
из таких способов подсказывается понятием порождающей системы.
Именно, назовем замкнутый класс R конечно порождаемым, если су-
существует конечная система функций Q этого класса, которая порож-
порождает R.
Если класс R конечно порождаем, а конечная система Q порож-
порождает класс R, то путем удаления функций из системы Q можно по-
получить наименьшую по числу функций систему Q'\ которая все еще
порождает класс R. Такие минимальные системы Q' называются ба-
базисами класса R. Отметим (пока без доказательства), что для од-
одного и того же класса R, отправляясь от различных порождающих
систем Q, можно прийти, вообще говоря, к различным базисам, со-
содержащим даже различные количества функций.

§7. Разложение булевой функции по переменной	21
УПРАЖНЕНИЯ
9.	Покажите, что замкнутыми классами являются объединение С
классов Со и Ci, объединение Uo классов C/oi и Со, объединение JJ\
классов Uoi и С\.
10.	Выясните, являются ли замкнутыми классами следующие
множества функций:
а)	{хг • ... -жп, п = 1,2,...};
б)	{xi 0 ...0жп, п = 1,2,...};
в)	{0,xi V... Vxn, n = 1,2,...}.
11.	Верно ли, что объединение двух замкнутых классов всегда
является замкнутым классом?
§ 7. Разложение булевой функции по переменной
Следующее утверждение имеет фундаментальное значение для
всей теории булевых функций.
Теорема 2 (о разложении функции по первой переменной). Для
любой булевой функции /(xi,... , жп) справедливо представление
/(жь...,жп) = хх -/A,ж2,...,жп) Vxi -/@,ж2,...,жп).	A3)
Доказательство. Возьмем произвольный двоичный набор
а = (ai,..., ап) и сравним значения левой и правой частей равен-
равенства A3) на этом наборе. Слева мы имеем значение /(а). Если а\ — О,
то выражение а\ • /A, а2,..., ап) из правой части обращается в 0. По-
Поэтому правая часть будет равна
Si '/@,a2,...,an) = 0-/(aba2,...,an) = 1 -/(a) = /(a).
Аналогичным образом рассматриваем другую возможность, когда
а\ — 1. Теорема доказана.
Разумеется, в теореме 2 вместо первой переменной с равным успе-
успехом можно выбрать любую другую переменную.
Теорема 2 имеет целый ряд важных следствий. Во-первых, если
при п ^ 2 ее применить далее к функциям /A, ж2,..., жп), /@, ж2,...
... ,жп) и переменной ж2, то получим соотношение
/(жь...,жп) =Х!-х2 -/A,1,ж3,...,жп) Vxi -ж2 -/A,0,ж3,...,жп) V
V X! • Х2 • /@, 1, Ж3, . . . , Хп) V X! • Х2 • /@, 0, Ж3, . . . , Хп).
Вообще, если ввести обозначения х1 = ж, ж0 = ж и рассуждать да-
далее по индукции, то получим следующее утверждение.
Следствие 1 (о разложении функции по первым т перемен-
переменным). Для любой булевой функции /(ж1,...,жп) и любого т A ^

22	Гл. I. Элементарные свойства булевых функций
^ т ^ п) имеет место представление
(жЬ...,Жп) =	\J X*1 • ... 'Х°^ •/(сГ1,...,СГт,Жт+Ь...,Жп).
(сГ1,...,СГт)
Выражение (с^,..., о~т) под знаком дизъюнкции в формуле A4)
означает, что данная формула представляет собой дизъюнкцию 2т
слагаемых (по числу всех двоичных наборов длины т), каждое из
которых имеет вид
х\х • ...-<Г •/(сгь...,сгт,жт+1,...,жп),
где х\ должно быть заменено на Xi, aij — на Xi.
Особенно интересным следствие 1 оказывается при т = п. В этом
случае каждое дизъюнктивное слагаемое в формуле A4) имеет вид
х? -..•¦<" ¦f(au...,an).	A5)
Если /(cri,..., ап) = 0, то слагаемое A5) равно 0. Поэтому в фор-
формуле A4) его можно опустить (исключение составляет единственный
случай, когда функция / тождественно равна 0; тогда формула A4)
вырождается в константу 0). Если же /(cri,..., сгп) = 1, то вместо
формулы A5) можно написать эквивалентную формулу х*1 •... • ж^п.
Таким образом, мы приходим к следующему утверждению.
Следствие 2 (о разложении функции по всем переменным). Ес-
Если булева функция f(xi,..., хп) не равна тождественно 0, то имеет
место представление
/(хь...,хп)= \/ х^.....^.	A6)
/(<71,...,<7„) = 1
Равенство /(cri,..., сгп) = 1 в формуле A6) говорит о том, что
в формуле A6) присутствуют лишь те дизъюнктивные слагаемые
х*1 • ... • x^n, для которых /(cri,..., о~п) = 1.
Правая часть формулы A6) носит название совершенной дизъюнк-
дизъюнктивной нормальной формы (сокращенно СДНФ). Следствие 2 пока-
показывает, что любую не равную тождественно 0 булеву функцию мож-
можно представить в некоторой стандартной форме — СДНФ, которая
представляет собой дизъюнкцию конъюнкций одинаковой длины, со-
составленных из переменных xi,...,хп и их отрицаний. Для функции,
тождественно равной 0, в качестве СДНФ рассматривают, например,
формулу х\ -х\.
СДНФ относится к более общему классу формул над множеством
{ж, ху, х V у}, которые носят название дизъюнктивных нормальных
форм (сокращенно ДНФ). В отличие от СДНФ в произвольной ДНФ,
которая также представляет собой дизъюнкцию конъюнкий, конъ-
конъюнкции могут состоять из различных переменных и иметь различную

§8. Двойственность. Принцип двойственности	23
длину. Так, первая из формул
хуУхуУ ху, х V у
есть СДНФ, вторая — ДНФ. Обе формулы реализуют одну и ту же
функцию х —у у. На этом примере видно, что ДНФ булевой функции
может быть гораздо проще, чем ее СДНФ. Этим обстоятельством, а
также сравнительной простотой строения ДНФ, объясняется то вни-
внимание, которое уделяется изучению ДНФ в теории булевых функций.
Следствие 2 содержит еще одну важную информацию о клас-
классе Р<± всех булевых функций. Именно, формула A6) показывает, что
каждую не равную 0 булеву функцию можно представить формулой
над множеством функций {ж, ху, х V у}. Поскольку, как отмечалось,
О = х • ж, мы получаем еще одно следствие из теоремы 2.
Следствие 3. Система функций {ж, ху, х V у} полна в клас-
классе Р2.
Используя следствие 3 и теорему 1, докажем полноту следующих
систем функций:
{х,ху}, {х,х\/у}, {1,х®у,ху}, {х\у}.
Полнота первых двух систем вытекает из полноты системы {ж, ху,
х V у}, теоремы 1 и правил де Моргана (см. п. 10 в §5), согласно
которым
х\1 у — х -у, х -у = ж Vу.
Полнота третьей системы следует из полноты системы {ж, ж?/}, теоре-
теоремы 1 и соотношения ж = ж 0 1. Полнота четвертой системы следует
из полноты системы {ж, ху} и соотношений
ж = ж |ж, ху = (х\у)\(х\у).
УПРАЖНЕНИЯ
12.	Разложите по переменным ж, z функцию xyz (В xz (В у (В z (В 1.
13.	Постройте СДНФ для функции ж V yz.
14.	Докажите полноту систем функций
{ж,ж—)>?/}, {0,ж—)>?/}, {0,ж © у © 1,ж V у}, {1,ж,ж^/ V xz V yz}.
§ 8. Двойственность. Принцип двойственности
Каждому, кто знакомится с булевыми функциями, довольно
быстро приходит в голову следующая мысль. Элементы 0, 1 множе-
множества В в общем-то равноправны. А что будет, если поменять их ме-
местами?

24
Гл. I. Элементарные свойства булевых функций
Эту мысль можно оформить вполне строгим образом и получить
новое важное понятие. Именно, будем говорить, что функция g(xi,...
..., хп) является двойственной к функции /(xi,..., жп), если
#(жь...,жп) = /(жь...,жп).	A7)
Это равенство следует понимать так. Чтобы найти значение функ-
функции g на наборе (ai,..., an), необходимо сначала образовать "проти-
"противоположный" набор (ai,..., an), затем найти значение /(ai,..., ап) и
в заключение инвертировать его с помощью отрицания.
Функция, двойственная к функции /(xi,..., жп), обозначается че-
через /*(жь • • • •> хп)- Из определения A7) двойственной функции и тож-
тождества х = х нетрудно вывести, что
Таким образом, двойственные друг другу функции образуют пары
(из приводимых далее примеров будет видно, что возможны случаи,
когда /* = /). В табл. 4 приведены некоторые пары двойственных
функций.
Таблица 4
/
0
X
ху
х (В у
х ->> у
х\у
г
1
X
х У у
х(Ву(В1 = х(Ву
х У у = ху
Важ:ную роль в теории булевых функций играет следующий
принцип двойственности.
Если функция f реализуется формулой Ф, составленной из
функций #i,... ,дт, то двойственная функция /* реализуется
формулой Ф*, которая получается из формулы Ф заменой каж-
каждого вхождения функции gi A ^ г ^ т) соответствующей двойст-
двойственной функцией д*.
Чтобы убедиться в справедливости принципа двойственности, до-
достаточно рассмотреть самый простой этап в определении формул,
когда
f(x!,..., хп) = go(gi(xi,..., хп),..., gm(xi,..., хп)). A8)
Согласно исходному определению двойственной функции имеем
ь ... ,хп) =
xi,... ,хп

§8. Двойственность. Принцип двойственности	25
Заменим в правой части этого равенства каждую формулу gi(x\,...
..., хп) эквивалентной формулой <^(xi,..., жп):
/*(жЬ . . . , Хп) = gO(ei(xi,. • • , Жп), . . . ,§т(жЬ . . . , Хп)).
Функция gi(xi,..., хп) по определению есть функция g*(xi,..., хп).
Поэтому
/*(жЬ . . . ,ЖП) = <?0(#l0b • • -,Хп), • • • ,<40ь • • • ,ЖП)).
Вновь по определению po(pj,... ,р^) есть ^(^,...,^). Оконча-
Окончательно получаем
/* Oi,..., хп) = #о (р* (xi , • • • , хп), • • •, д*ш (xi,..., хп)) •
Покажем на примерах, как работает принцип двойственности. При
этом будем пользоваться двойственными функциями из табл. 4:
(xyz V xyz V xyz)* = (х V у V г)(ж V 2/ V z)(x VyV z),
(xyz 0 (yz V ж^))* = (ж V у V z) 0 (у V 2:)(ж V 2/ V z) 0 1,
((ж -+ y)(x -> z) 0 B/2 -)> xz))* =
= (y ->• ж V 2 ->• ж) 0 (ж V z) ->• (^ V z) 0 1.
На практике принцип двойственности чаще всего применяют сле-
следующим образом. Если уже установлено некоторое утверждение о бу-
булевых функциях /, д,... и множествах булевых функций F, G,..., в
котором фигурируют лишь понятия, базирующиеся на формулах, то
по принципу двойственности будет справедливо аналогичное утвер-
утверждение о булевых функциях /*,#*,... и множествах булевых функ-
функций F*, G*,... . При этом под F* понимается множество всех булевых
функций, двойственных к функциям из F.
Так, например, доказав дистрибутивность конъюнкции относи-
относительно дизъюнкции (см. п. 7 из §5), на основании принципа двой-
двойственности мы можем заключить о справедливости свойства дистри-
дистрибутивности дизъюнкции относительно конъюнкции (см. п. 8 из §5).
Аналогичное утверждение имеет место для двух правил де Моргана
(см. п. 10 из § 5). Далее, на основе дистрибутивности конъюнкции от-
относительно сложения по модулю 2 (см. п. 9 из § 5) можно получить
новую эквивалентность
ж V (у 0 z 0 1) = (ж V у) 0 (ж V z) 0 1.
С использованием принципа двойственности, теоремы 2 и ее
следствий можно доказать несколько интересных утверждений. Во-
первых, имеет место следующий аналог теоремы 2.
Теорема 2'. Для любой булевой функции f(x\,...,хп) справед-
справедливо разложение
/(жь...,жп) = (ж! У/@,ж2,...,жп)) • (ж! У/A,ж2,...,жп)).
Далее получаем разложение по п переменным.

26	Гл. I. Элементарные свойства булевых функций
Следствие 2'. Если булева функция /(жь... ,жп) не равна
тождественно 1, то имеет место представление
f(xu...,xn)= & (x^V.-.Vx^).
f((T1,...,(rn)=O
Правая часть этой формулы носит название совершенной конъ-
конъюнктивной нормальной формы (сокращенно СКНФ). Так же, как и
в случае СДНФ и ДНФ, СКНФ относится к более широкому клас-
классу конъюнктивных нормальных форм (сокращенно КНФ), которые
представляют собой конъюнкции дизъюнкций переменных и их отри-
отрицаний.
УПРАЖНЕНИЯ
15.	Докажите, что функция /(xi,..., хп) существенно зависит от
переменной Х{ в том и только том случае, когда от переменной Х{
существенно зависит функция /*(xi, ..., хп).
16.	Выясните, верно ли, что СКНФ для булевой функции / можно
построить следующим образом: сначала построить СДНФ для функ-
функции /*, а затем в полученной СДНФ заменить V на • и • на V.
§ 9. Полиномы Жегалкина
Как установлено в § 7, система {1, х (В у, х • у} полна в классе Р^.
Это означает, что любую булеву функцию можно представить в виде
формулы над множеством функций {1, ж © ?/, х • у}. Преобразуем эту
формулу, используя следующие эквивалентности из § 5: коммутатив-
коммутативность сложения по модулю 2 и конъюнкции (умножения), дистрибу-
дистрибутивность конъюнкции (умножения) относительно сложения (п. 9 сле-
слева направо),
Так же, как в элементарной алгебре, после выполнения этих пре-
преобразований мы получим формулу, которая имеет вид полинома: она
представляет собой сумму по модулю 2 слагаемых вида Хгг •... • xis и,
быть может, константы 1 (в случаях, когда реализуемая полиномом
функция тождественно равна 0 или 1, сумма вырождается в одно сла-
слагаемое, 0 или 1). Эта формула носит название полинома Жегалкина.
Общий вид полинома Жегалкина для функции от п переменных мо-
может быть записан следующим образом:
Здесь ? означает сумму по модулю 2; суммирование распростра-
распространяется по всем подмножествам {ii,..., is} множества {1, 2,..., п},

§ 9. Полиномы Жегалкина	27
включая пустое подмножество 0; коэффициенты а^...^ принимают
значения 0 или 1; при а^...^ = О соответствующее слагаемое в поли-
полиноме A9) опускают. Наконец, если все коэффициенты а^...^, включая
коэффициент п0, равны 0, то полином A9) записывают просто как 0.
Эквивалентность ж Vу = ж • у можно переписать в виде
xV у = (ж 0 1) • (у Ф1) 0 1.
Раскрывая в этом равенстве скобки и пользуясь соотношением 101 =
= 0, получаем полином Жегалкина для функции ж V у:
х\/у = ху(Вх(Ву.
Аналогичным способом можно построить полиномы Жегалкина для
функций х —у у и х | у:
(х -у у) = ху 0 х 0 1, (х | у) = ху 0 1.
Интересно выглядит процесс построения полинома Жегалкина для
функции ху V xz V yz:
хуМ xzM yz — (ху • xz 0 ху 0 жг) Vyz = (ж^/г 0ж^0 ж г) \l yz —
— (xyz (В ху (В xz) • yz 0 :п/2: 0 ху 0 xz 0 yz =
= ж^/2: • yz (В ху • yz (В xz • yz (В xyz (В ху (В xz (В yz =
= :п/2: 0 :п/2: 0 ж^/2: 0 ж^/2: (В ху (В xz (В yz = ху (В xz (В yz.
На практике для построения полиномов Жегалкина чаще все-
всего прибегают к методу неопределенных коэффициентов. Пусть нам
требуется построить полином Жегалкина для функции f(x,y,z), за-
заданной двоичным набором A0011100). Запишем функцию f(x,y,z)
в виде полинома Жегалкина с неопределенными коэффициен-
коэффициентами ао,..., а*?:
/(ж, у, z) = ао 0 а\х 0 а^у 0 a^z 0 а^ху 0 a$xz 0 a^yz 0 a^xyz. B0)
Подставляя в функцию f(x,y,z) последовательно наборы @,0,0),
@,0,1),...,A,1,1) и пользуясь известными значениями функции /,
из B0) получаем следующую систему уравнений для коэффициентов
ао,..., <27 (слева в скобках указан набор значений переменных ж, у, z,
приводящий к данному соотношению):
@,0,0)	а0 = 1,
@,0,1)	ао0а3=О,
@,1,0)	ао0а2=О,
@,1,1)	а0фа2Фа3фа6 = 1,
A,0,0)	а0 0ai = 1,
A, 0,1)	а0 0 ai 0 а3 0 а5 = 1,
A,1, 0)	а0 0 ai 0 а2 0 а4 = 0,
A,1,1)	аоФа1фа2Фа3фа4Фа5фа6фа7 = 0.

28	Гл. I. Элементарные свойства булевых функций
Решим ее, исключая последовательно неизвестные ао,... ,&7- Первое
уравнение дает ао = 1, второе, третье и пятое — а\ — 0, а^ — аз = 1-
Используя далее найденные значения коэффициентов ао, ai, a2, аз,
рассматриваем четвертое, шестое и седьмое уравнения. Из них нахо-
находим CL4 = a,Q = 0, as = 1. Подставляя полученные значения в восьмое
уравнение, получаем a 7 = 0. Окончательно полином Жегалкина для
функциии f(x,y,z) имеет вид 1 0 у 0 z 0 xz.
Довольно неожиданно оказывается, что для любой булевой функ-
функции имеется единственный полином Жегалкина, если только полино-
полиномы Жегалкина рассматривать с точностью до перестановок слагае-
слагаемых и сомножителей в слагаемых. В самом деле, подсчитаем число
коэффициентов а^...^ в общей формуле A9) полинома Жегалкина
для функции от п переменных. Это число равно числу всевозмож-
всевозможных подмножеств (включая пустое) множества {1,2,...,п}. В свою
очередь подмножества множества {1, 2,..., п} взаимно однозначным
образом соответствуют двоичным наборам длины п: единица, стоя-
стоящая в наборе на г-м слева месте, свидетельствует о том, что в рас-
рассматриваемое подмножество входит число г, нуль — что число г в
подмножество не входит.
Понятно, что число различных полиномов Жегалкина вида A9)
(при условии, что мы не различаем полиномы, которые получаются
друг из друга перестановкой слагаемых или перестановкой сомножи-
сомножителей в слагаемых) равно числу всевозможных способов, которыми
мы можем придать значения 0 и 1 коэффициентам а^...^ полино-
полинома A9). Поскольку этих коэффициентов имеется 2П, мы получаем
величину 22™ для числа полиномов Жегалкина от п переменных.
Итак, для каждой булевой функции от п переменных имеется хо-
хотя бы один полином Жегалкина, который реализует эту функцию и,
вместе с тем, число различных полиномов Жегалкина от п перемен-
переменных равно числу всех булевых функций от п переменных. Это озна-
означает, что для любой булевой функции существует только один реали-
реализующий ее полином Жегалкина.
Отметим одну важную особенность полиномов Жегалкина: функ-
функция f(xi,..., хп) существенно зависит от переменной х\ тогда и толь-
только тогда, когда переменная Х{ входит хотя бы в одно слагаемое
полинома Жегалкина, реализующего функцию /(xi, ..., хп) (еще раз
напомним, что в полиноме Жегалкина присутствуют лишь слагаемые,
не равные тождественно 0). В самом деле, если функция /(xi,..., хп)
не зависит существенно от переменной Хг, то полином Жегалкина,
реализующий функцию f(xi,...,xn), можно построить следующим
образом. Сначала удалением из функции f(xi,...,xn) несуществен-
несущественной переменной xi образуем функцию /'(жъ • • • 5жг-ъ^г+ъ ¦¦¦,жп), за-
затем строим полином Жегалкина Ф, который реализует функцию /;.
Понятно, что ввиду несущественности переменной xi полином Жегал-

§ 9. Полиномы Жегалкина	29
кина Ф, рассматриваемый от всех переменных xi,...,жп, будет также
реализовать и функцию /(xi, ..., хп).
Обратно, если переменная xi не входит ни в одно слагаемое по-
полинома Жегалкина Ф, реализующего функцию /(xi,... ,хп), то, оче-
очевидно, значения переменной х\ не играют никакой роли при вычис-
вычислении значений функции /(xi,... ,хп) согласно формуле Ф. Поэтому
переменная xi является несущественной для функции /(xi,... ,жп).
УПРАЖНЕНИЯ
17.	Определите при любом п, какую булеву функцию реализует
полином Жегалкина A9), если все коэффициенты a«i...ia (включая
коэффициент а0) равны 1.
18.	Методом неопределенных коэффициентов постройте полином
Жегалкина для функции f(x,y,z,w), заданной набором
A010101111011000).

Глава II
ЗАМКНУТЫЕ КЛАССЫ И ПОЛНОТА
§ 1. Класс самодвойственных функций
Булеву функцию /(ж1,... ,жп) назовем самодвойственной, если
/(жь...,жп) = /*(жь...,жп).	B1)
Для самодвойственной функции /(ж1,... ,жп) равенство B1) можно
записать также в виде
7(жь...,жп) = /(жь...,жп).
Из него следует, что самодвойственная функция / на любых двух
противоположных наборах (ai,..., an), (ai,..., ап) принимает про-
противоположные значения.
Из табл. 4 видно, что самодвойственными являются функции х и
е^(жь...,жп).
Обозначим через S множество всех самодвойственных булевых
функций. Докажем, что S образует замкнутый класс.
Поскольку селекторные функции являются самодвойственными,
достаточно проверить, что из принадлежности классу S функций
до, д\,..., дш вытекает принадлежность классу S функции /, задан-
заданной равенством A8). Однако это непосредственно следует из принципа
двойственности.
На примере самодвойственных функций интересно еще раз просле-
проследить идею подсчета функций от п переменных с помощью таблицы.
Внимательно рассмотрим табл. 1 и отметим следующий факт: про-
противоположные наборы (ai,..., an), (ai,..., ап) располагаются в ней
на равных расстояниях от середины таблицы (которая проходит меж-
между 2п-1-м набором @,1,...,1) и BП~1 + 1)-м набором A, 0,..., 0)).
Вспомним, что самодвойственная функция принимает противополож-
противоположные значения на противоположных наборах. Таким образом, для
полного задания самодвойственной функции /(ж1,... ,жп) достаточ-
достаточно указать ее значения либо на наборах из верхней половины таб-
таблицы, либо на наборах из нижней половины. Следовательно, число
самодвойственных булевых функций от п переменных равно
Иными словами, это число есть корень квадратный из числа всех бу-
булевых функций от п переменных.
Класс самодвойственных функций играет важную роль при реше-
решении проблемы полноты в классе Р^. Следующее утверждение, необ-

§2. Класс линейных функций	31
ходимое для ее решения, имеет также и некоторый самостоятельный
интерес.
Лемма 1 (о несамодвойственной функции). Из несамодвойст-
несамодвойственной функции с помощью подстановки функций х и х на места
всех ее переменных можно получить несамодвойственную функцию
от одной переменной, т.е. константу 0 или 1.
Доказательство. Пусть функция /(ж1,...,жп) несамо-
несамодвойственна. Тогда найдется такая пара противоположных наборов
(аь...,ап) и (аь...,ап), что
/(аь...,ап) = /(аь...,ап).	B2)
Подставим в функцию /(xi,..., хп) вместо переменной Xi (I ^ i ^ п)
функцию ж, если ai — 1, и функцию ж, если (ц = 0. Полученную после
подстановки функцию обозначим через д(х). Согласно определению
g(x)=f(xa\...,xa'),
где, напомним, через х1 обозначена функция ж, а через х° функция ж.
Имеем теперь
5@) = /@а\...,0а"), g(l) = f(la\...Xn)-	B3)
Поскольку
0° = 0 = I1 = 1, О1 = 1° = 1 = 0,
из равенств B3) заключаем, что
#@) = /(аь...,ап), дA) = /(аь ..., ап).
Обращение к равенству B2) завершает доказательство леммы.
Пусть функция /(ж1,Ж2,жз) определена формулой х±Х2 V х\Хз V
Vx2^3- Из нее видно, что /@,1,1) = /A,0,0) = 1. Соответствующие
этим противоположным наборам подстановки /(ж, ж, х) и /(ж, ж, ж) да-
дают константу 1.
УПРАЖНЕНИЯ
19. Проверьте, что самодвойственными являются функции
x(By(Bz, Ж0 2/020 1, xyVxzVyz, xyVxzVyz, xy V xz\l yz.
Докажите, что не существует самодвойственных функций /(ж1,Ж2),
существенно зависящих от обеих переменных.
§ 2. Класс линейных функций
Булеву функцию /(ж1,... ,жп) назовем линейной, если в ее поли-
полиноме Жегалкина A9) отсутствуют нелинейные слагаемые (т.е. сла-
слагаемые, содержащие не менее двух сомножителей).

32	Гл. П. Замкнутые классы и полнота
Из определения следует, что всякую линейную функцию /(#1,...
..., хп) можно представить в виде
а0 Ф а\Х\ © ... © апхп,	B4)
где коэффициенты ao,ai,...,an равны 0 или 1. Представление B4)
позволяет легко подсчитать число линейных функций, зависящих от п
переменных. В самом деле, придавая коэффициентам ao,ai,...,an
различные значения 0 и 1, мы будем получать различные (проверь-
(проверьте!) линейные функции. Следовательно, число линейных функций,
зависящих от переменных xi,... ,жп, равно числу двоичных наборов
длины п + 1. Последнее число, как мы знаем, есть 2n+1.
Часто бывает полезным тот факт, что все четыре булевы функции
от одной переменной 0, 1, ж, ж = ж © 1 линейны.
Множество всех линейных булевых функций обозначим через L.
Убедимся, что L является замкнутым классом. Пусть функции
линейны, т.е.
9о(У1,-..,Ут) = 6о
..,xn) = а10 ©anxi © ...
дт(хи... ,хп) = ат0 ©amixi © ... Фатпжп,
а функция /(xi,... ,жп) представима формулой A8). Тогда
f(x!,..., хп) = bo © bi (аю Ф anxi © ... © ainxn) © ...
. . . Ф 0m(Bmo Ф Q"mlxl © • • • © Q"mnxn) zz
= (Ьо © biaio Ф ... © frmamo) Ф (bian Ф ... Ф bmaml) xi Ф ...
. . . ф @iBin ф . . . ф 0mBmnJ Жп.
Если обозначить значения выражений
fro © fri^io Ф ... © bmamo, bian © ... © frmami, ..., biain © ... © bmamn
(которые являются константами 0 или 1) соответственно через ао,
ai,...,an, то мы придем к формуле B4), определяющей функцию
Отметим, что класс L порождается системой функций {1, х ф у}.
В самом деле, имеем 0 = 1 ф 1. Суперпозициями функции х ф у мож-
можно получить любую функцию вида Х\ ф ... ф хп, где п ^ 2; а посколь-
поскольку у нас в распоряжении имеются константы 0 и 1 — также и любую
функцию вида х\ Ф ... Ф хп-\ и х\ Ф ... Ф хп-\ © 1.
Булева функция, которая не является линейной, называется нели-
нелинейной. Полином Жегалкина нелинейной булевой функции включает
хотя бы одно слагаемое, содержащее не менее двух сомножителей.

§2. Класс линейных функций	33
Для определения линейности (нелинейности) булевой функции уни-
универсальным приемом служит разложение функции в полином Жегал-
кина. Однако в некоторых случаях о нелинейности функции можно
судить по виду двоичного набора, задающего функцию. Так, отличная
от константы булева функция будет заведомо нелинейной, если зна-
значение 1 (или значение 0) она принимает не на половине всех наборов.
Это утверждение мы докажем от противного: если булева функция
/(xi,... ,жп) линейна и отлична от константы, то значение 1 (и зна-
значение 0) она принимает ровно на 2п~1 наборах.
Итак, пусть функция /(xi,..., хп) линейна и отлична от констан-
константы. Тогда она существенно зависит по крайней мере от одной из пере-
переменных xi,... ,жп. Пусть это будет, например, переменная хп. Тогда
функцию /(xi,..., хп) можно представить в виде
/(жь. . .,жп) = а0 0aixi 0 ... 0 an_ixn_i 0жп.	B5)
При п = 1 функция f{x\) совпадает с одной из функций xi, x\ 0 1
и утверждение проверяется непосредственно. Предположим далее,
что п ^ 2. Опираясь на представление B5), заключаем, что функ-
функция /(xi,... ,жп) принимает значение 1 только в двух случаях: либо
линейная функция
а0 0ai^i 0 ... 0an_ixn_i = /(жь... ,жп_ь0)	B6)
принимает значение 0 и хп = 1, либо линейная функция B6) прини-
принимает значение 1 и хп = 0. Отсюда сразу следует, что число наборов,
на которых функция / принимает значение 1, равно сумме числа
наборов, на которых функция B6) принимает значение 0, и числа
наборов, на которых функция B6) принимает значение 1. Очевид-
Очевидно, что указанная сумма равна 2п~1 — числу всех двоичных наборов
длины п — 1.
В дальнейшем при решении проблемы полноты в классе Р<± нам
понадобится утверждение о возможности понижения числа перемен-
переменных в нелинейной функции. Это утверждение носит название лемма
о нелинейной функции.
Лемма 2. Из всякой нелинейной булевой функции подстановкой
констант 0 и 1 вместо некоторых переменных можно получить
нелинейную функцию от двух переменных.
Доказательство. Пусть /(жь ... ,жп) — нелинейная функ-
функция. Поскольку все булевы функции от одной переменной линей-
линейны, имеем п ^ 2. При п = 2 утверждение тривиально (можно при-
применить "пустую" подстановку). Пусть п > 2. Выберем в полиноме
Жегалкина функции f(xi,...,xn) нелинейное слагаемое наимень-
наименьшей степени. Чтобы не применять громоздких обозначений, будем
предполагать, что это слагаемое имеет вид х\ • ... • хш B ^ та ^ п).
Подставим в функцию f(xi,... ,хп) константу 0 вместо всех пере-
переменных xm+i,..., хп (можно считать, что константа 0 зависит от пе-
3 С.С.Марченков

34	Гл. П. Замкнутые классы и полнота
ременной х\). Ввиду минимальности степени слагаемого х\ • ... • хт
полином Жегалкина функции f(x\,..., жт, 0,..., 0) примет вид
Если т > 2, то подставим далее константу 1 вместо всех перемен-
переменных Жз,... ,хт. В итоге придем к функции, полином Жегалкина ко-
которой имеет вид
Х\Х2 © &2^2 © biXi © Ьо.
Лемма доказана.
УПРАЖНЕНИЯ
20.	Покажите, что функция, двойственная к линейной, также бу-
будет линейной. Покажите, что линейные функции вида а © х\ © ...
... © Х2п+\ являются самодвойственными.
21.	Докажите, что при любом п (п ^ 3) существует нелиней-
нелинейная функция от п переменных, которая принимает значение 1 ров-
ровно на 2п~1 наборах. Существенно ли в этом утверждении ограниче-
ограничение п > 3?
§ 3. Класс монотонных функций
Что такое монотонно не убывающая функция? Это функция, зна-
значения которой не убывают с ростом значений аргумента. Если вы
дадите такой ответ на поставленный вопрос, то в общем-то буде-
будете правы. Трудности с монотонными функциями начинаются тогда,
когда основное множество, на котором определена функция, как го-
говорят, не является линейно упорядоченным либо когда рассматри-
рассматриваются функции многих переменных. Обе эти возможности нередко
соседствуют друг с другом. Однако в случае булевых функций исход-
исходное множество В линейно упорядочено @ < 1), и потому проблема
остается лишь с определением монотонных функций от нескольких
переменных.
Приводимое ниже определение монотонной функции по существу
представляет собой определение функции, монотонной по любой из
своих переменных.
Начнем с введения (частичного) порядка на множестве Вп всех
двоичных наборов длины п. Говорим, что набор (ai,... ,an) не пре-
превосходит набора (&i,..., Ьп), если для любого i (I ^ i ^ п) выполняет-
выполняется неравенство а^ ^ hi. Если набор (ai,..., ап) не превосходит набора
(&i,..., Ьп), то этот факт записываем в виде
(ab...,an) ^ (&1,...,6П).	B7)

§3. Класс монотонных функций
35
Отметим, что при п ^ 2 введенное отношение определено не для лю-
любых двух наборов длины п. Так, например, наборы @,1) и A,0) невоз-
невозможно сравнить относительно этого отношения. Именно поэтому вве-
введенное отношение является частичным.
Булева функция f(xi,...,xn) называется монотонной, если для
любых двух наборов (ai,..., an), (&i,..., Ъп) из того, что выполняется
неравенство B7), следует, что выполняется неравенство
/(ab...,an) ^ /(&!,..., Ъп).
Множество всех монотонных булевых функций обозначим через М.
Непосредственная проверка показывает, что множеству М принадле-
принадлежат функции 0, 1, ж, ху, ж V у и не принадлежат функции ж, х 0 у,
х -> у, х\у.
Для проверки монотонности булевых функций от небольшого чис-
числа переменных часто используют задание булевых функций с по-
помощью диаграммы, на которой представлен частичный порядок на
множестве Вп. Каждому набору из Вп отвечает точка на этой диа-
диаграмме, а различные точки соединяются отрезком прямой в том и
только том случае, когда эти точки соответствуют наборам, разли-
различающимся ровно в одной компоненте (рис. 1). Обычно точки на диа-
диаграмме изображают "слоями". При этом каждый "слой" диаграммы
состоит из точек, которые отвечают двоичным наборам с одним и тем
же числом единичных компонент. Следовательно, если число единиц в
наборе а = (ai,..., ап) меньше числа единиц в наборе Ъ = (&i,..., 6П),
то набор Ъ расположен в диаграмме выше набора а. Если же еще для
наборов а, Ъ выполняется соотношение B7), то от набора а в диаграм-
диаграмме можно "подняться" до набора Ъ по отрезкам прямых.
001
100
Рис. 1
Значения функции помещаются на диаграмме рядом с вершина-
вершинами, которые отвечают наборам соответствующих значений перемен-
переменных. На рис. 1 значения 1 функций обозначены жирными точками.

36	Гл. П. Замкнутые классы и полнота
На диаграмме множества В2 представлена функция х —У у, а на диа-
диаграмме множества В3 — функция х(у V z). С помощью приведенных
диаграмм можно легко проверить немонотонность функции х —У у и
монотонность функции х(у V z). В самом деле, переход от меньше-
меньшего набора @,0) к большему набору A,0) сопровождается изменени-
изменением функции х —У у от большего значения 1 к меньшему значению 0.
Напротив, в диаграмме множества В3 на любом пути, ведущем от
наименьшего набора @, 0, 0) к наибольшему набору A,1,1), значения
функции х(у V z) не убывают.
Докажем, что множество М является замкнутым классом. По-
Поскольку селекторные функции монотонны, нам достаточно доказать,
что из монотонности функций до, д\,..., дш следует монотонность
функции /, если / определяется равенством A8). Пусть для набо-
наборов а = (ai,..., an), b = (&i,..., bn) выполняется соотношение B7).
Тогда в силу монотонности функций д\,..., дш будем иметь
9i{o) ^ 9i(b), • • •, 9т{р) ^ 9т(Ъ).
Следовательно,
(gi(a),...,gm(a)) ^ (gi(b),... ,дт(Ъ)).
Пользуясь этим неравенством и монотонностью функции до, заклю-
заключаем, что
go(gi(a),.. .,дт(а)) ^ go(gi(b), • • .,дт{Ъ)).
Согласно определяющему равенству A8) это означает, что
/(ab...,an) ^ /FЬ..., Ьп),
и монотонность функции / установлена.
Любопытный вариант теоремы 2 о разложении имеет место для
монотонных функций.
Теорема 3. Для любой монотонной булевой функции f{x\,...
..., хп) справедливо представление
/(жь...,жп) = хх -/A,ж2,...,жп) V/@,x2,...,xn).	B8)
Доказательство. Пусть а = (ai,..., ап) — произвольный
двоичный набор. Для набора а найдем значения левой и правой
частей равенства B8). Слева мы имеем /(а). Если а± = 0, то, как
легко видеть, справа также образуется значение /(а). Пусть а± = 1.
Тогда справа в B8) получаем
/(l,a2,...,an)V/@,a2,...,an).	B9)
Однако набор @, а2,..., ап) не превосходит набора A, а2,..., ап).
Следовательно, в силу монотонности функции / будем иметь
/@,a2,...,an) ^ /(I,a2,...,an).
Поэтому значение B9) есть /A, а2,..., ап). Теорема доказана.

§3. Класс монотонных функций	37
Заметим, что в формуле B8) функции /(О, ж2,..., хп) и /A, ж2,...
...,жп) также являются монотонными, поскольку получаются из мо-
монотонной функции / подстановкой монотонных функций 0 и 1. По-
Поэтому при п ^ 2 так же, как и при выводе следствия 2 из теоремы 2,
процесс разложения функций /@, ж2,..., хп) и /A, ж2,..., хп) можно
продолжить по переменной ж2. В результате придем к разложению
/Oi,...,xn) = Xl-x2 -/A,1,ж3,...,жп) Vxi -/A,0,ж3,...,жп) V
V х2 • /@,1, х3, • • •, хп) V /@, 0, ж3,..., жп).
Если при п ^ 3 проделать указанное разложение по всем остав-
оставшимся переменным х%,..., хп и воспользоваться соотношениями
х-1 = х\/0 = х, то получим следующее утверждение.
Следствие 1. Любую монотонную функцию, отличную от
константы, можно представить в виде ДНФ, не содержащей от-
отрицаний переменных.
Следствие 1 позволяет сделать важный вывод о системе функций,
порождающей класс М.
Следствие 2. Класс М порождается системой функций {0,1,
ху,х Vy}.
В заключение параграфа докажем лемму о немонотонной функ-
функции, которая нам понадобится в следующем параграфе при доказа-
доказательстве критерия полноты.
Лемма 3. Из немонотонной функции путем подстановки
констант 0 и 1 на места некоторых переменных можно полу-
получить немонотонную функцию одной переменной, т.е. функцию х.
Доказательство. Пусть функция f{x\,...,хп) немонотонна.
Тогда найдутся такие два набора а = (ai,..., ап) и Ъ = [Ъ\,..., Ьп),
что выполняются соотношения B7) и /(а) = 1, f(b) = 0. Покажем,
что наборы а, Ъ можно считать соседними, т.е. различающимися ров-
ровно в одной компоненте. В самом деле, предположим, что это не так и
наборы а, Ъ различаются в t компонентах, где t > 1. Пусть, например,
^ = 0, bi = 1 (вариант а^ = 1, bi = 0 не может реализоваться в силу
неравенства B7)). Рассмотрим набор с = (ai,..., a^-i, 1,а«+1,... ,ап).
Он отличается от набора а в одной компоненте и от набора b
в ? — 1 компонентах. Кроме того, а ^ с и с ^ Ь. Если /(с) = 0, то
вместо набора b можно взять набор с. Если же /(с) = 1, то набор
а следует заменить на набор с и вновь повторить описанную выше
процедуру. Не более чем через t — 1 шагов мы придем к паре сосед-
соседних наборов с требуемыми свойствами.
Итак, считаем, что наборы а и b различаются только в одной ком-
компоненте. Пусть это будет первая компонента. Тогда а2 = 62,..., ап =
= Ьп и, следовательно, подстановка констант а2,..., ап на места пе-
переменных ж2,..., хп в функцию /(xi,..., хп) дает функцию д(х\) =
= f(xi, a2,..., ап) такую, что д@) = 1 и д{1) = 0. Лемма доказана.

38	Гл. П. Замкнутые классы и полнота
УПРАЖНЕНИЯ
22.	Проверьте на монотонность функцию xyz(x —>¦ у)(х —>¦ z).
С использованием диаграммы множества В3 найдите число монотон-
монотонных функций от трех переменных.
23.	Покажите, что из монотонности функции / следует монотон-
монотонность функции /*.
24.	Найдите все монотонные линейные функции.
§ 4. Критерий полноты
Существует ли эффективный способ, который по любой системе
булевых функций дает ответ на вопрос, полна ли эта система? Оказы-
Оказывается, такой способ существует; его предложил американский мате-
математик Э. Пост еще в 1921 г. Способ основан на проверке пяти свойств:
невхождении системы булевых функций полностью ни в один из
замкнутых классов
Го, Тъ S, M, L.	C0)
Точнее говоря, имеет место следующий критерий полноты в классе Р^.
Теорема 4. Система булевых функций Q полна в Р<± тогда и
только тогда, когда Q целиком не содержится ни в одном из клас-
классов C0).
Доказательство. Необходимость. Пусть система функ-
функций Q полна в Р<±. Тогда [Q] = Р<±. Если бы система Q целиком содер-
содержалась в одном из классов C0) (обозначим этот класс через R), то по
свойству 3 замыкания выполнялось бы равенство [R] = Р^. Однако
каждый из замкнутых классов C0) отличен от класса Р^. Поэтому
система Q целиком не содержится ни в одном из классов C0).
Достаточность. Пусть система Q целиком не содержится ни
в одном из классов C0). Обозначим через Д, /2, /з, /4, /б функции
системы Q, которые не входят соответственно в классы То, Т\, 5,
М, L (некоторые из функций /i,..., /б могут совпадать). Покажем,
что суперпозициями функций /i,..., /б можно получить функции ж,
ху, которые, как нам известно, образуют полную в Р<± систему. Тогда
по теореме 1 полной будет система {/i,..., /б} и, следовательно, си-
система Q.
Получим сначала из функций Д, /2, /з константы 0 и 1. Из того,
что /i не входит в класс То, следует, что /i@,..., 0) = 1. Значит, если
положить
01 (ж) = /l (Ж, ...,Ж),
то функция gi(x) будет совпадать с одной из функций 1, х. Если
gi(x) — константа 1, то, пользуясь соотношением /2A,...,!) = 0,

Критерий полноты	39
получаем константу 0:
f2(gi(x),...,gi(x)) = 0.
Пусть gi(x) = х. Тогда, применяя лемму о несамодвойственной функ-
функции к функции /з, подстановками функций жиж получаем из нее
одну из констант, 0 или 1. Другую константу образуем с помощью
подстановки в функцию х.
Имея обе константы, с помощью леммы о немонотонной функции,
примененной к функции /4, строим функцию ж, а с помощью леммы
о нелинейной функции, примененной к функции /5, строим нелиней-
нелинейную функцию д2(х,у). Рассмотрим далее полином Жегалкина для
функции д2(х,у):
д2(х, у) = ху® ахх 0 а2у 0 а3.
Можно считать, что аз = 0, поскольку в противном случае вместо
функции д2(х,у) следует взять функцию д2(х,у) — 92(х,у) 0 1 (на-
(напомним, что функция х = ж0 1 у нас уже имеется). Если а± = а2 =0,
то д2(х,у) — конъюнкция ху. Если а\ — 1 и а2 = 0, то
д2(х,у) = хуфх = х(у® 1) =ху.
Следовательно, в этом случае д2(х,у) = ху. Аналогично рассматри-
рассматривается случай, когда а± = 0 и а2 = 1. Наконец, если а± = а2 = 1, то
д2(х,у) = хуфхфу = х\/у.
В этом случае
д2(х,у) = ху.
Теорема доказана.
Из теоремы 4 вытекает несколько интересных следствий. Во-пер-
Во-первых, как видно из доказательства, если система функций полна в Р2,
то из нее можно выделить также полную подсистему, состоящую не
более чем из пяти функций. А нельзя ли в общем случае уменьшить
это число до четырех? Оказывается, можно. Действительно, пусть
функции /i,..., /5 выбраны так, как указано в доказательстве тео-
теоремы. Рассмотрим функцию Д. Согласно выбору этой функции име-
имеем Д@,..., 0) = 1. Если ДA,..., 1) = 1, то функция Д несамодвой-
несамодвойственна (на противоположных наборах @,..., 0) и A,..., 1) она при-
принимает одно и то же значение 1). Поэтому функцию /з можно заме-
заменить функцией Д. Если же Д A,..., 1) = 0, то функция Д немонотон-
немонотонна. Значит, в этом случае функцией Д можно заменить функцию /4.
Итак, мы приходим к следующему утверждению.
Если система функций полна в классе Р2, то из нее можно выде-
выделить полную подсистему, состоящую не более чем из четырех функ-
функций.
Можно ли продвинуться в этом направлении дальше, понизив
оценку до трех? Следующий пример показывает, что, вообще гово-
говоря, этого сделать нельзя.

40	Гл. П. Замкнутые классы и полнота
Пусть
Q = {0, 1, ху V xz V yz, х 0 у 0 z}.
Пользуясь, например, теоремой 4, нетрудно убедиться, что система Q
полна в Ръ. Вместе с тем подсистема
{1, ху V xz V yz, х 0 у 0 z}
целиком лежит в классе Т\, подсистема
{0, ху V xz V yz, х 0 ^/ 0 z}
—	в классе То, подсистема
{0, 1, х Фу 0z}
—	в классе L и подсистема
{0, l,xyVxzVyz}
—	в классе М. Таким образом, ни одну из функций системы Q нельзя
исключить из системы, не нарушив при этом условий полноты.
УПРАЖНЕНИЯ
25.	Постройте пример базиса в классе Р^, состоящего из трех
функций.
26.	Докажите, что булева функция /, не принадлежащая ни од-
одному из классов То, Xi, 5, является базисом класса Р^. Будет ли
справедливо аналогичное утверждение, если вместо класса S взять
класс L?
§ 5. Замкнутые классы, содержащие константы
Как велико число замкнутых классов? Можно ли каким-либо эф-
эффективным способом перечислить все замкнутые классы?
Американский математик Э. Пост установил, что число замкну-
замкнутых классов в Р<± бесконечно. Тем не менее, существует эффективная
процедура перечисления всех замкнутых классов с помощью конеч-
конечных порождающих систем функций. Изложение этих результатов в
полном объеме хотя и не требует специальных знаний, но выходит за
рамки данной брошюры2). Мы решим более скромную задачу: най-
найдем все замкнутые классы, содержащие обе константы 0 и 1.
2) Заинтересованному читателю можно посоветовать обратиться к кни-
книгам: Яблонский СВ., Гаврилов Г.П., Кудрявцев В.Б. Функции алгебры ло-
логики и классы Поста.— М.: Наука, 1966; Марченков С. С. Замкнутые классы
булевых функций.— М.: Наука, 2000. В них приведены подробные доказа-
доказательства упомянутых результатов.

§ 5. Замкнутые классы, содержащие константы	41
Из всех замкнутых классов Р<±, То, Т\, S, М, L, которые мы изуча-
изучали в предыдущих параграфах, обе константы содержат лишь классы
Р2? М и L. Дадим определение еще пяти замкнутых классов, которые
также содержат обе константы (с некоторыми из этих классов мы уже
начали знакомиться в § б гл. I).
Через С обозначим класс всех булевых функций-констант (от лю-
любого числа переменных).
Через MU обозначим класс всех функций, которые являются либо
константами, либо селекторными функциями.
Через U обозначим класс всех булевых функций, которые су-
существенно зависят не более чем от одной переменной.
Через D обозначим класс всех дизъюнкций, т.е. всех функций
,..., хп), которые представимы в виде
а0 V aixi V ... V апжп,	C1)
где ао, ai,..., ап — произвольные элементы из В.
Наконец, через К обозначим класс всех конъюнкций, т.е. класс
всех функций f(xi,..., хп), которые представимы в виде
а0 • (ах V xi) • ... • (ап V хп).	C2)
Замкнутость классов С, MU, U легко вытекает из их определе-
определения (напомним еще раз, что наряду с любой булевой функцией / мы
считаем одновременно заданными все функции, которые получаются
из / добавлением или изъятием несущественных переменных).
Чтобы доказать замкнутость класса D, полезно иметь в виду,
что при ао = 1 дизъюнкция C1) обращается в константу 1, при
ао = а\ — ... = ап = 0 — в константу 0, а если из коэффициентов
ао, ai,..., ап равны 1 лишь коэффициенты а^,..., ais, причем ао =
= 0, то выражение C1) представляет собой "настоящую" дизъюнк-
дизъюнкцию Хгг V ... V Xis. Поэтому замкнутость класса D следует из свойств
дизъюнкции, отмеченных в § 5 гл. I.
Класс К, как несложно проверить, является двойственным к клас-
классу D. Из представлений C1) и C2) видно, что класс D порожда-
порождается системой функций {0, 1, х V у}, а класс К — системой функ-
функций {0, 1, ху}.
Теорема 5. Существует всего 8 замкнутых классов, содержа-
содержащих обе константы:
Р2, М, L, С, MU, U, Д К.
Доказательство. Пусть R — произвольный замкнутый класс,
содержащий константы 0 и 1. Поскольку система функций {0, 1} це-
целиком не содержится ни в одном из классов То, Т\, 5, из теоремы 4
выводим, что класс R либо совпадает с классом Р<±, либо целиком
содержится в одном из классов М, L. Рассмотрим сначала случай,
когда R состоит только из линейных функций.

42	Гл. П. Замкнутые классы и полнота
Если класс R состоит из функций, существенно зависящих не бо-
более чем от одной переменной, то непосредственная проверка показы-
показывает, что R совпадает с одним из классов С, MU, U. Пусть, далее,
класс R содержит линейную функцию /(xi,... ,хп), существенно за-
зависящую не менее чем от двух переменных. Можно считать, что
все переменные функции f(xi,...,xn) существенны. Тогда функ-
функция /(xi,..., хп) представима в виде
/ \%11 • • • 1 Хп) — Х\ 0 ... 0 Хп ф B,
где п ^ 2 и а — элемент множества В. При п > 2 подстановкой
константы 0 вместо всех переменных жз,..., хп получаем функ-
функцию х\ © Х2 © а, принадлежащую классу R. Если а = 0, то в
класс R входит система функций {l,?i © Ж2}, которая, как отмеча-
отмечалось в § 2 гл. II, порождает класс L. Значит, в этом случае R = L. Если
же а = 1, то функцию х\ ф х2 получаем суперпозициями функций О
и х\ © ж2 © 1:
xi Ф О Ф 1 = xi Ф 1, (xi Ф х2 Ф 1) Ф 1 = xi Ф х2.
Таким образом, если замкнутый класс R содержит обе констан-
константы 0, 1 и состоит только из линейных функций, то он совпадает с
одним из классов С, MU, U, L.
Пусть теперь класс R состоит только из монотонных функций.
Если R содержит только функции, существенно зависящие не более
чем от одной переменной, то он совпадает с одним из классов С, MU
(класс U содержит немонотонную функцию х).
Пусть в класс R входит функция, существенно зависящая не менее
чем от двух переменных. Тогда согласно лемме о нелинейной функции
в класс R будет входить нелинейная функция от двух переменных.
Заметим, что она монотонна, поскольку получается из монотонной
функции подстановкой констант 0 и 1. Легко проверить, что нелиней-
нелинейными монотонными функциями от двух переменных являются лишь
функции
ху и х\/у = ху(Вх(Ву.
Поскольку системы функций
{0,1, xV у} и {0,1, ху}
порождают соответственно классы D и К, мы приходим к выводу, что
в этом случае в класс R целиком входит хотя бы один из классов D
или К.
Если в класс R целиком входят оба класса D и К, то R = М,
так как класс М порождается системой функций {0, 1, ху, х V у}.
Предположим поэтому, что в R целиком входит только один из клас-
классов D, К. Ввиду двойственности классов D, К можно считать, что
это класс D. Мы покажем, что в этом случае R совпадает с D.
В самом деле, допустим, что R ф D. Тогда в класс R входит функ-
функция /(xi,... ,жп), которая не является дизъюнкцией. Согласно след-

§ 5. Замкнутые классы, содержащие константы	43
ствию 1 из теоремы 3 функцию /(#1,..., хп) можно представить в ви-
виде ДНФ Ф, которая не содержит отрицаний переменных. Поскольку
функция /(xi,..., хп) отлична от дизъюнкции, ДНФ Ф содержит хо-
хотя бы одну конъюнкцию, имеющую более одного сомножителя. Пусть
Хгг ' • • • ' Хгз — такая конъюнкция с наименьшим возможным числом
сомножителей (s ^ 2). Можно считать, что в Ф в качестве дизъюнк-
дизъюнктивных слагаемых не входит ни одна из переменных Х{х,..., xis (ина-
(иначе по свойству поглощения 11 конъюнкцию Хгг • ... • Xis в Ф можно
было бы опустить). Таким образом, любая конъюнкция из ДНФ Ф,
отличная от Хгг •... • Xis, содержит хотя бы одну переменную, не вхо-
входящую в множество переменных {х^,..., xis}. Следовательно, если в
функции /(xi,..., хп) заменить константой 0 все переменные, отлич-
отличные от переменных х^,..., xis, то получится функция, реализуемая
конъюнкцией х^ •... • Xis. Если теперь s ^ 3, то подстановка констан-
константы 1 вместо переменных Xi3,..., Xis дает конъюнкцию х^ • Xi2.
Итак, получаем, что в класс R входит конъюнкция ху и, тем са-
самым, все функции класса К. Это противоречит сделанному выше
предположению о невхождении класса К в R. Теорема доказана.
Довольно просто найти все замкнутые классы, которые целиком
лежат в одном из классов L, D, К. Мы приведем полный пере-
перечень этих классов. Попытайтесь самостоятельно установить, что не
существует других замкнутых классов, целиком лежащих в клас-
классах L, D, К.
Итак, класс L линейных функций целиком содержит замкнутые
классы
Lq, Li, SX, Lqi, U, MU, SU, Uq, U\, С/оъ С? Со? Ci?
где
Lq — класс всех линейных функций, сохраняющих константу 0;
L\ — класс всех линейных функций, сохраняющих константу 1;
SL — класс всех самодвойственных линейных функций;
Loi — класс всех линейных функций, сохраняющих констан-
константы 0 и 1;
SU — класс всех самодвойственных функций, существенно зави-
зависящих от одной переменной;
Uo — класс всех функций, сохраняющих константу 0 и существен-
существенно зависящих не более чем от одной переменной;
U\ — класс всех функций, сохраняющих константу 1 и существен-
существенно зависящих не более чем от одной переменной;
C/oi — класс всех функций, сохраняющих константы 0 и 1 и суще-
существенно зависящих не более чем от одной переменной;
Со — класс всех функций-констант, равных 0 (от любого числа
переменных);
С\ — класс всех функций-констант, равных 1.

44	Гл. П. Замкнутые классы и полнота
Класс D всех дизъюнкций целиком содержит следующие замкну-
замкнутые классы:
Do — класс всех дизъюнкций, сохраняющих константу 0;
D\ — класс всех дизъюнкций, сохраняющих константу 1;
Doi — класс всех дизъюнкций, сохраняющих константы 0 и 1;
а также классы
MU, Uo, Uu Uoi, С, Со, Ci.
Класс К всех конъюнкций целиком содержит следующие замкну-
замкнутые классы, двойственные к соответствующим классам из D:
Ко, Кг, Koi, MU, Uo, Uu U01, С, Со, Су.

Глава III
СЛОЖНОСТЬ РЕАЛИЗАЦИИ
БУЛЕВЫХ ФУНКЦИЙ
§ 1. Минимизация ДНФ
Пусть Q — полная система функций. Тогда любую булеву функ-
функцию можно реализовать формулой над Q. Как мы уже не раз видели,
для некоторых полных систем Q существуют функции, которые реа-
реализуются различными формулами. (Нетрудно показать, что для лю-
любой полной системы Q и любой булевой функции / существует бес-
бесконечное число формул над Q, реализующих функцию /.) Поэтому
возникает желание для любой булевой функции / найти оптималь-
оптимальную (в каком-либо смысле) формулу над Q, которая реализует функ-
функцию /. Вопрос этот представляется в прикладном отношении очень
важным. Однако пока не сформулирован критерий оптимальности,
нельзя даже утверждать, что для данной булевой функции имеет-
имеется хотя бы одна оптимальная формула, реализующая эту функцию.
На практике, как правило, рассматриваются такие критерии оп-
оптимальности, для которых вопрос о существовании оптимальных
формул решается тривиальным образом. Обычно для формул опре-
определяется числовая характеристика (параметр), имеющая смысл неко-
некоторой сложности, и оптимальной формулой называется формула с
наименьшим возможным значением этого параметра. Сам процесс по-
поиска формул наименьшей сложности носит название минимизации
формул.
Из всех полных систем функций наиболее употребительной в во-
вопросах минимизации является система Qo = {х, ху, хУ у}. В каче-
качестве меры сложности чаще всего рассматривают две взаимосвязан-
взаимосвязанные меры: число символов функций, входящих в формулу, либо число
символов переменных. При этом как символы функций, так и симво-
символы переменных подсчитываются с теми кратностями, с которыми они
встречаются в формуле. Так, например, в формуле
Х\{х<2 V Жз) V Х<2Хъ{х\Х<1 V
имеется 12 символов функций и 8 символов переменных.
В этом параграфе в качестве меры сложности формул мы выби-
выбираем число символов переменных, входящих в формулу. Нетрудно
понять, что для всякой булевой функции существует реализующая
ее формула наименьшей сложности над системой Qq (таких формул
может быть несколько). В самом деле, для заданной булевой функ-
функции /(ж1,...,жп) можно, например, последовательно перебирать в

46	Гл. III. Сложность реализации булевых функций
некотором порядке все формулы над Qo сложности 1,2,..., содер-
содержащие только символы переменных xi,..., жп, и сравнивать реализу-
реализуемые ими функции с функцией /. Этот процесс не может продолжать-
продолжаться неограниченно долго, поскольку, во-первых, функцию /(xi,..., хп)
всегда можно реализовать в виде совершенной ДНФ со сложностью,
не превосходящей п • 2п. А во-вторых, количество формул над Qo
заданной сложности конечно (количество формул сложности I за-
заведомо меньше числа всех строк длины I, составленных из симво-
символов (, ), ~, &, V, xi,... ,жп; это число равно (п + 5)').
Описанный выше тривиальный алгоритм поиска формулы наи-
наименьшей сложности относится к классу так называемых переборных
алгоритмов. Отличительной особенностью этих алгоритмов является
то, что для отыскания искомого объекта (в нашем случае — формулы)
сложности I приходится перебирать все объекты сложности, меньшей
или равной I. Обычно это приводит к тому, что переборный алгоритм
при работе над входными данными размера I затрачивает около с1
шагов, где с — константа, превосходящая 1.
Если обратиться к формулам над системой Qo, то можно показать,
что число различных формул, содержащих ровно г символов перемен-
переменных из множества {xi,... ,жп}, не меньше, чем Dп)г. Поэтому если
функция /(ж1,...,жп) задана формулой сложности I, то непосред-
непосредственный просмотр всех формул со сложностью к (к ^ I) потребует
не менее с[ шагов, где с\ > 1.
В настоящее время неизвестны алгоритмы непереборного типа,
осуществляющие минимизацию формул над системой Qo (как, впро-
впрочем, и над любой другой полной системой). Трудности, стоящие на
этом пути, носят, по-видимому, принципиальный характер. Некоторое
представление об этих трудностях дает пример минимизации ДНФ —
формул над системой Qo, имеющих довольно простое строение. Хотя
проблема минимизации ДНФ пока также не получила окончательного
удовлетворительного решения, на пути ее решения создана разветв-
разветвленная система понятий и получен ряд интересных и важных резуль-
результатов.
Дадим необходимые определения, используемые в теории миними-
минимизации ДНФ.
Элементарной конъюнкцией называется формула вида ж^1 • ...
... • х°г, где а\,..., ar Е {0,1} и все переменные Хгг,..., Xir различ-
различны. Число г называется рангом конъюнкции.
Дизъюнктивная нормальная форма (ДНФ) есть формула вида
К\ V ... V Kt, где К\,..., Kt — различные элементарные конъюнк-
конъюнкции (порядок сомножителей в конъюнкции роли не играет).
Минимальной ДНФ функции / называется ДНФ, которая реа-
реализует функцию / и имеет наименьшее число символов переменных
среди всех ДНФ, реализующих функцию /.

§1. Минимизация ДНФ	47
Булева функция может иметь несколько минимальных ДНФ. Так,
для функции f(x,y,z), заданной двоичным набором A1100101), ми-
минимальными ДНФ являются
xyV xzV xz и xzV xzV yz.	C3)
Как мы уже говорили, проблему минимизации ДНФ можно ре-
решить тривиальным переборным алгоритмом. Мы хотим уменьшить
перебор за счет удаления некоторых элементарных конъюнкций, ко-
которые заведомо не входят ни в одну из минимальных ДНФ. С этой
целью введем следующие понятия.
Пусть /(xi,..., хп) — булева функция и К — элементарная конъ-
конъюнкция, все переменные которой принадлежат множеству {xi,...
...,жп}. Назовем конъюнкцию К импликантом функции /, если
функция
K->f(Xl,...,xn)	C4)
тождественно равна 1, и простым импликантом функции /, ес-
если К — импликант функции /, но перестает быть таковым после
вычеркивания из К любого сомножителя (если ранг конъюнкции К
равен 1, то импликант К по определению считается простым импли-
импликантом функции /, если / не равна тождественно 1).
Из представления C4) видно, что импликант К функции / при-
принимает значение 1 только на тех наборах, на которых равна 1 функ-
функция / (импликант К "имплицирует" единичные значения функции /).
Далее, если элементарная конъюнкция К' получается из элементар-
элементарной конъюнкции К вычеркиванием некоторых сомножителей, то, оче-
очевидно, функция К —>¦ К' будет тождественно равна 1, т.е. всякий
двоичный набор, обращающий в 1 конъюнкцию К, будет обращать
в 1 и конъюнкцию К'. Поэтому простой импликант К функции /
обладает свойством максимальности: он, как говорят, покрывает
наибольшее число единиц функции / (т.е. наборов, на которых функ-
функция / равна 1) среди всех импликантов функции /, которые получа-
получаются из К умножением на некоторые сомножители. Все эти соображе-
соображения наводят на мысль, что простые импликанты и дизъюнкция всех
простых импликантов должны играть важную роль в вопросах мини-
минимизации ДНФ.
Назовем ДНФ функции / сокращенной, если она представляет со-
собой дизъюнкцию всех простых импликантов функции /.
Нетрудно заметить, что сокращенная ДНФ не обязана быть мини-
минимальной. Так, для рассмотренной выше функции A1100101) с мини-
минимальными ДНФ C3) сокращенной ДНФ будет формула
xy\l xz'M xz\l yz.
Тем не менее справедливо следующее утверждение.

48	Гл. III. Сложность реализации булевых функций
Теорема 6. Любая минимальная ДНФ булевой функции мо-
может быть получена из ее сокращенной ДНФ путем удаления неко-
некоторых конъюнкций.
Доказательство. Достаточно установить, что любая мини-
минимальная ДНФ булевой функции / является дизъюнкцией только
простых импликантов функции /. Последнее почти очевидно, по-
поскольку, во-первых, в силу определения каждая входящая в ДНФ
конъюнкция представляет собой импликант функции /. А во-вторых,
если бы импликант минимальной ДНФ не был простым, то из него
удалением некоторых сомножителей можно было бы получить про-
простой импликант функции /. Как следствие, получили бы другую ДНФ
с меньшим числом символов переменных. Это противоречит опреде-
определению минимальной ДНФ. Теорема доказана.
Следствие. Если некоторая конъюнкция не входит в сокра-
сокращенную ДНФ функции /, то она не входит ни в одну минимальную
ДНФ функции /.
Теорема б показывает, что при построении минимальных ДНФ
нет необходимости рассматривать произвольные импликанты — до-
достаточно ограничиться теми, которые входят в сокращенную ДНФ.
Как мы уже убедились, сокращенная ДНФ может не быть мини-
минимальной. Однако существуют достаточно широкие классы функций,
для которых эти понятия совпадают. Один из них — класс монотон-
монотонных функций.
Теорема 7. Сокращенная ДНФ монотонной функции, отлич-
отличной от константы, не содержит отрицаний переменных и являет-
является ее единственной минимальной ДНФ.
Доказательство. Пусть /(xi,...,xn) — монотонная функ-
функция, отличная от константы, а конъюнкция
-*»¦ — %i\ • • • %ir ' %ir-\-i • • • *^is
является импликантом функции /, причем s > г. Тогда конъюнк-
конъюнкция К, а вместе с ней и функция /, принимает значение 1 при
*&i\ — • • • — %ir — -l-j %ir-\-\ — • • • — *^is —
(значения остальных переменных могут быть произвольными). Вви-
Ввиду монотонности функция / будет принимать значение 1, как только
Хгг = ... = Xir = 1. Следовательно, если положить К' = х^ • ... • ж^,
то К' будет также импликантом функции /, который получается из
импликанта К вычеркиванием сомножителей Xir+1,..., Xis. Посколь-
Поскольку s > г, получаем, что К не есть простой импликант функции /.
Значит, сокращенная ДНФ функции / не содержит отрицаний пере-
переменных.
Итак, любая конъюнкция К из сокращенной ДНФ функции
f(xi,..., хп) имеет вид Хгг • ... • Xir. Покажем, что конъюнкция К яв-

§1. Минимизация ДНФ	49
ляется единственной конъюнкцией в сокращенной ДНФ функции /,
которая принимает значение 1 при
xix = ... = xir = 1, xir+1 = ... = xin = 0.	C5)
В самом деле, пусть имеется еще одна конъюнкция К' из сокращен-
сокращенной ДНФ функции /, которая принимает значение 1 при выполне-
выполнении условий C5). Тогда согласно первой части доказательства теоре-
теоремы конъюнкция К' не может содержать сомножителей Xir+1,..., Х{п,
а ввиду условия Xir+1 = ... = Xin = 0 из C5) — также и сомножите-
сомножителей Xir+1,..., Xin. Значит, в конъюнкцию К' могут входить лишь со-
сомножители из числа Хгг,..., Xir. Но тогда К' получается из К вы-
вычеркиванием некоторых сомножителей, что противоречит простоте
импликанта К.
Таким образом, конъюнкцию К из сокращенной ДНФ функции /
удалить нельзя. Для завершения доказательства теоремы 7 теперь
остается обратиться к теореме 6.
Как же строить сокращенную ДНФ булевой функции? Существу-
Существует целый ряд методов синтеза сокращенной ДНФ. Мы рассмотрим
только один из них — метод Блейка. Этот метод применим к произ-
произвольной ДНФ булевой функции, отличной от константы, и состоит в
многократном выполнении двух эквивалентных преобразований над
конъюнкциями, входящими в ДНФ:
1)	обобщенное склеивание
хК' V хК" = хК' V хК" V К'К";
2)	поглощение
К' V К'К" = К'
(подразумевается, что преобразования выполняются только слева на-
направо).
Итак, пусть D — произвольная ДНФ булевой функции /, отлич-
отличной от константы. По методу Блейка сначала выполняем все возмож-
возможные преобразования 1) и получаем ДНФ D'. Покажем, что при этом
каждый простой импликант К функции / будет включен в ДНФ D'.
Очевидно, достаточно рассмотреть случай, когда К не входит в D.
Прежде всего заметим, что в К входят только те переменные, ко-
которые содержаться в D. В самом деле, если бы это было не так, то,
удалив из К переменную, не входящую в D, мы получили бы конъ-
конъюнкцию К', которая, очевидно, также является импликантом функ-
функции /. Это противоречит простоте импликанта К.
Рассмотрим теперь множество конъюнкций {i^/}, которое удов-
удовлетворяет следующим трем условиям.
1°. Kj содержит только те переменные, которые входят в D.
2°. Kj получается из К домножением на некоторые множители
(случай Kj = К не исключается).
4 С.С.Марченков

50	Гл. III. Сложность реализации булевых функций
3°. Для любой конъюнкции Н из ДНФ D конъюнкции Kj удов-
удовлетворяет хотя бы один набор, не удовлетворяющий конъюнкции Н.
Множество {Kj} непусто, так как содержит, например, конъюнк-
конъюнкцию К (условие 3° для конъюнкции К выполняется, поскольку в
противном случае конъюнкция К либо входит в D, либо не является
простым импликантом функции /).
Выберем в множестве {Kj} конъюнкции наибольшего ранга
Ki,... ,Кт. Рассмотрим конъюнкцию К\. Она не может содержать
все переменные, входящие в D, так как в этом случае конъюнкции
К\ удовлетворяет только один набор (переменные функции /, не вхо-
входящие в D, здесь можно не принимать во внимание), который в силу
условия 3° не удовлетворяет ни одной конъюнкции из D. То есть полу-
получаем, что К\ не является импликантом функции /, что противоречит
условию 2°.
Возьмем переменную ж, которая входит в D и не входит в К\.
Рассмотрим конъюнкции хК\ и хК\. Они удовлетворяют условиям 1°
и 2° и имеют ранг, на 1 больший, чем ранг К\. Следовательно, по вы-
выбору конъюнкции К\ конъюнкции xKi, xK\ не удовлетворяют усло-
условию 3°. Тогда в ДНФ D имеются такие конъюнкции Н\ и Я2, что
все сомножители конъюнкций Н\, Н2 входят соответственно в конъ-
конъюнкции хК\ и хК\. Понятно, что в конъюнкцию И\ должен вхо-
входить сомножитель ж, а в конъюнкцию Н2 — сомножитель х. Поэтому
Н1=хН[, Н2=хЩ,
где все сомножители конъюнкций Н[, Н'2 принадлежат конъюнк-
конъюнкции К\. Следовательно, после выполнения преобразования 1) над
конъюнкциями Н\ и Н.2 в ДНФ D' будет включена конъюнк-
конъюнкция Н[Н'2, все сомножители которой входят в конъюнкцию К\.
Аналогичные построения и утверждения справедливы и для конъ-
конъюнкций if2,... ,Кт. Обозначим через D\ ДНФ, которая получается
из ДНФ D добавлением конъюнкций вида Н[Н^ образованных при
рассмотрении всех конъюнкций Ki,... ,Кт. Если теперь для этой
ДНФ D\ определить множество конъюнкций {I/j}, удовлетворяющих
условиям 1°—3°, то конъюнкция наибольшего ранга из {Lj} будет
иметь ранг, меньший, чем ранг конъюнкции К\. Понятно, что на неко-
некотором шаге этого индуктивного процесса в ДНФ D' будет включена
конъюнкция К.
После того как в ДНФ D' будут включены все конъюнкции —
простые импликанты функции /, — преобразование 2) удаляет из D'
конъюнкции, не являющиеся простыми импликантами. В результате
образуется сокращенная ДНФ функции /.
Еще раз рассмотрим функцию f(x,y,z), заданную двоичной стро-
строкой A1100101). Ее совершенная ДНФ есть
D = xyz V xyz V xyz V xyz V xyz.

§1. Минимизация ДНФ	51
Отправляясь от ДНФ D, методом Блейка построим сокращенную
ДНФ функции /. Применим четыре раза преобразование 1):
zyz V xyz = xyz V xyz V xy,
xyz V xyz = xyz V xyz V xz,
xyz V x^z = xyz V x^z V yz,
xyz V x?/z = xyz V Ж?/;г V жг.
Таким образом, с помощью преобразования 1) к ДНФ D дизъюнктив-
дизъюнктивно добавляем слагаемое
Dc(f) =xyV xzVyzVxz
и образуем ДНФ D' = D V Dc(f). Затем, пользуясь преобразовани-
преобразованием 2), из ДНФ D' удаляем все конъюнкции, входящие в совершенную
ДНФ D. В результате получим сокращенную ДНФ Dc(f) функции /.
Как мы уже знаем, сокращенная ДНФ может не быть минималь-
минимальной. Вместе с тем любая минимальная ДНФ получаеся из сокра-
сокращенной отбрасыванием некоторого числа конъюнкций. Оказывается,
в зависимости от того, какие конъюнкции и в каком порядке будут
отброшены, может образоваться как минимальная ДНФ, так и неми-
неминимальная ДНФ, из которой невозможно удалить ни одну конъюнк-
конъюнкцию, не нарушая при этом реализуемую ею функцию. В связи с этим
дадим следующее определение.
ДНФ D функции / называется тупиковой, если она состоит толь-
только из простых импликантов функции / и после удаления любой конъ-
конъюнкции из D полученная ДНФ уже не реализует функцию /.
Очевидно, что всякая минимальная ДНФ является тупиковой.
Как показывает следующий пример, булева функция может иметь
несколько тупиковых ДНФ, которые не являются минимальными.
Пусть
/(ж, у, z) = xyz V xyz V xyz V xyz V xyz V xyz.
Сокращенная ДНФ функции / имеет вид
xy\l xz~\l xy\l xz\l yz\l yz.
Тупиковыми ДНФ функции / будут
D\ —xy\lxz\l yz, D2 —xz\lxy\l yz, D3 —xy\lxy\lyz\l yz,
D4 = xy V xy V xz V xz, D5 = xzV xz V yz\J yz.
Из них только D\ и D^ являются минимальными.
Таким образом, если сокращенная ДНФ строится по функции од-
однозначно, то процесс перехода от сокращенной ДНФ к тупиковой
ДНФ уже неоднозначен. При этом удаление одних элементарных
конъюнкций из сокращенной ДНФ приводит к минимальной ДНФ,
а удаление других приводит к тупиковой, не являющейся минималь-
минимальной. Поэтому для построения минимальной ДНФ приходится, вообще

52	Гл. III. Сложность реализации булевых функций
говоря, строить все тупиковые ДНФ и затем проводить среди них
отбор.
УПРАЖНЕНИЯ
27. Постройте сокращенную, тупиковые и минимальные ДНФ для
функции f(x,y,z), заданной двоичной строкой A0111101).
§ 2. Схемы из функциональных элементов
В современной технике и, прежде всего, в вычислительной техни-
технике имеется целый арсенал средств и методов для реализации булевых
функций, систем булевых функций и других более сложных дискрет-
дискретных функций. Обычно "массовым тиражом" в виде некоторых "эле-
"элементов" реализуется сравнительно небольшой набор "элементарных"
функций. Эти "элементы" действительно могут представлять собой
простейшие вычислительные устройства (например, транзисторы или
переключатели), а могут являться достаточно крупными системными
блоками. Далее из этих элементов по определенным правилам соби-
собираются крупные вычислительные устройства (схемы), способные вы-
выполнять сколь угодно сложные преобразования информации.
В математической кибернетике и дискретной математике изучают-
изучаются математические модели устройств, осуществляющих преобразова-
преобразование информации. Одной из самых простых и вместе с тем распростра-
распространенных моделей являются схемы из функциональных элементов. Они
предназначены в первую очередь для вычисления булевых функций
либо систем булевых функций, хотя могут быть использованы и для
вычисления функций более сложной природы. Содержательно схе-
схема из функциональных элементов (сокращенно СФЭ) представляет
собой геометрический объект, составленный из полюсов (входы схе-
схемы), треугольников либо квадратов, изображающих функциональные
элементы, и дуг либо отрезков прямых,
которые соединяют полюса, входы и вы-
выходы функциональных элементов ("про-
("проводники" схемы).
Прежде чем дать точное определе-
о	т	? ние схемы из функциональных элемен-
а	б	в тов, приведем определение вспомогатель-
вспомогательного объекта — сети. Сеть позволяет
с*	описать строение СФЭ безотносительно
к ее функционированию. Итак, сеть состоит из полюсов и элемен-
элементов, которые могут соединяться в сети дугами или отрезками пря-
прямых. Полюса будем изображать маленькими кружками (рис. 2, а).
Для упрощения изложения элементы будем рассматривать только с

§2. Схемы из функциональных элементов	53
одним или двумя входами. Элементы изображаем в виде треуголь-
треугольников (рис. 2, б, в) с двуми или тремя стрелками. Стрелка, ведущая
в элемент, соответствует входу элемента, ведущая из элемента — его
выходу.
Еще раз подчеркнем, что на этапе определения сети нас совершен-
совершенно не интересует ни возможное техническое происхождение полюсов и
элементов, ни отношение сети к булевым функциям и способам их вы-
вычисления. На этом этапе мы рассматриваем лишь способ соединения
полюсов и элементов в схеме, или, как г	1
говорят, топологию схемы.	j
По индукции определим сеть и i
множество вершин сети.	[
1.	Полюс есть сеть. Он является
единственной вершиной этой сети.
2.	Пусть Ei, ?2 — две сети без общих вершин. Тогда формальное
объединение сетей Ei, ?2 дает новую сеть (рис. 3). Вершинами этой
сети являются все вершины сетей Ei и ?2.
3.	Пусть Е — сеть, а Е — элемент, входы и выход которого не явля-
являются вершинами сети ?. Тогда результат присоединения (или отож-
отождествления) всех входов элемента Е к некоторым вершинам сети Е
есть сеть (рис. 4, где показан элемент Е с двумя входами).
При этом в случае элемента Е с двумя входами оба входа
элемента Е могут быть присоединены к одной и той же
вершине сети ?, однако каждый вход должен присоеди-
присоединяться только к одной вершине. Вершинами новой сети
являются все вершины сети Е и выход элемента Е.
Непосредственно из определения вытекают следующие
два свойства сети.
1°. Никакой элемент сети не присоединен своим выхо-
выходом ни к полюсу, ни к выходу другого элемента сети.
2°. Вершины сети можно занумеровать натуральными
числами так, что выход любого элемента будет иметь номер, боль-
больший, чем номер каждого из его входов. Поэтому в сети невозможно
найти последовательность вершин ai,a2,..., аш такую, что аш = а\
и при 1 ^ j < m вершина ctj является входом некоторого элемента,
а CLj+i — его выходом. Иными словами, сеть не содержит ориентиро-
ориентированных циклов, составленных из элементов.
Перейдем теперь к определению схемы из функциональных эле-
элементов. Схемой из функциональных элеметов называется сеть в ко-
которой:
1)	каждому полюсу приписана одна из переменных xi,..., хп,...,
причем различным полюсам приписаны различные переменные; по-
полюса сети называются входами схемы;
2)	каждому элементу Е с одним или двумя входами приписана
некоторая функция /#, зависящая соответственно от одной или двух

54
Гл. III. Сложность реализации булевых функций
переменных; функция /# называется функцией элемента Е\ эле-
элемент Е с приписанной ему функцией Je называется функциональным
элементом;
3) некоторым вершинам сети приписаны натуральные числа 1,
2,...,т, причем одной и той же вершине может быть приписано
неколько чисел; вершины, которым приписаны числа 1,... , т, назы-
называются выходами схемы; 1-м выходом схемы называется (единствен-
(единственный) выход, которому приписано число I (возможно, что этой вер-
вершине приписаны и другие числа).
Так же, как для формул, по индукции дадим определение функ-
функции, реализуемой СФЭ. При этом будем сопоставлять вершинам схе-
схемы булевы функции.
1) Каждому входу сопоставляется функция, равная той перемен-
переменной, которая приписана этому входу.
XI к Х2
k X2
Х\ V Х2
(х1кх2)к(х1 У х2)
Рис. 5
2) Пусть всем вершинам, к которым присоединены входы эле-
элемента Е, уже сопоставлены функции (реализуемые в этих верши-
вершинах). Тогда выходу элемента Е сопоставляется функция /еA^) или
/еЦ^,/^), где /е — функция элемента Е, a /W — функция, со-
сопоставленная той вершине, с которой соединен г-й вход элемента Е
(рис. 5).

§2. Схемы из функциональных элементов	55
В результате этого процесса каждой вершине будет сопоставлена
некоторая булева функция. По определению схема реализует упоря-
упорядоченную систему функций (вектор-функцию)
F(X! , . . . , Хп) = (/l Oi, . . . , Хп), . . . , fm Ol, . . . , Хп)),
где /^(xi,... , жп) — функция, сопоставленная г-му выходу схемы.
Свойства 1°, 2° сети могут быть положены в основу более аб-
абстрактного определения схемы из функциональных элементов, ко-
которое не использует геометрических понятий. Будем рассматривать
два типа переменных: входные xi, х?,,... и рабочие 2/i, 2/2 ? • • • Схемой
из функциональных элементов назовем теперь такую последователь-
последовательность z\,..., zm+n входных и рабочих переменных, которая имеет вид
х\ ... хпу\ ... ут, причем если z\ не является входной переменной, то
числу i сопоставлены либо число j (I ^ j < г) и булева функция
gi(zj) от одной переменной, либо два числа j, k (I ^ j, к < г) и буле-
булева функция gi(zj,Zk) от двух переменных. Так же, как и для СФЭ в
исходном определении, каждой переменной zi по индукции сопостав-
сопоставляется единственная булева функция fi(xi,..., жп), значения которой
будут равны значениям переменной z\ в этой схеме.
Если функции всех элементов схемы Е принадлежат множеству
функций Q, то говорят, что схема Е есть схема в базисе Q. Заме-
Заметим, что в отличие от определения базиса, приведенного в гл. I, в
этом параграфе мы не предполагаем функции базиса независимыми.
В частности, в дальнейшем рассматриваем СФЭ исключительно в ба-
базисе Qo = {x, ху, х V у}.
Так же, как и для ДНФ, при изучении СФЭ основной задачей
является построение для заданной булевой функции (или множества
булевых функций) схемы (схем) наименьшей сложности. При этом
под сложностью схемы Е понимается число всех функциональных
элементов, входящих в схему Е. Сложность схемы Е будем обозна-
обозначать через 1/(Е). Пусть далее L(F) обозначает минимум из величин
L(E), где минимум берется по всем схемам Е, реализующим систему
функций F. Положим
L(n) = maxL(/),
где максимум берется по всем функциям /(xi,... ,жп), зависящим
от п переменных. Функция L(n) носит название функции Шенно-
Шеннона. Она играет важнейшую роль в теории синтеза управляющих си-
систем. Величина L(n), как это следует из определения, равна наимень-
наименьшей сложности, с которой заведомо можно реализовать любую булеву
функцию от п переменных. Как и для ДНФ, точное значение L(n)
можно найти, последовательно перебирая все функции / от п пере-
переменных и находя для каждой из них величину L(f). Следует отме-
отметить, что к настоящему времени не известно никаких непереборных

56
Гл. III. Сложность реализации булевых функций
алгоритмов для точного вычисления функции L(n). Более того, су-
существует гипотеза, что перебор в этой задаче в принципе неустраним.
Наша дальнейшая цель состоит в оценках сверху величин L(n)
и L(F) для некоторых функций F.
Рис. 6
Используя моделирование совершенной ДНФ, оценим, прежде все-
всего, величину L(n). Будем называть конъюнктором, дизъюнктором и
инвертором элементы, которым сопоставлены соответственно функ-
функции &, V, ~.
Пусть К = х^1 & ... & х^п — элементарная конъюнкция. Нетруд-
Нетрудно видеть, что ее можно реализовать СФЭ, состоящей не более чем
из п инверторов и п — 1 конъюнкторов (рис. 6). Если o~i = 0, то г-й
вход схемы присоединен к инвертору, в противном случае инвертора,
соответствующего г-у входу схемы, нет и г-й вход присоединяется к
конъюнктору. Очевидно, что
L(K) ^ 2п- 1.
C6)

§2. Схемы из функциональных элементов
57
Пусть /(xi,..., хп) — произвольная булева функция, отличная от
константы 0, и К\ V ... V Кт — ее совершенная ДНФ. СФЭ для функ-
К!
к2
Кг
Кт
Рис. 7
ции / строится из т схем для конъюнкций Kj и цепочки из т — 1
дизъюнкторов, которая "объединяет" выходы схем для конъюнкций
(рис. 7). Таким образом, учитывая неравенство C6),
приходим к следующему утверждению.
L,...,xn) содер-
Если совершенная ДНФ функции
жит т (т ^ 1) конъюнкций, то
L(f) ^ 2тп.
Так как всегда т ^ 2П, то для произвольной функ-
функции /(xi,... ,жп), не равной тождественно 0, имеем
Функция, тождественно равная 0, может быть ре-
реализована схемой, изображенной на рис. 8. Поэтому
L(n) ^ п2п .	Рис g
Существенно лучшую оценку для L(n) можно получить, если вос-
воспользоваться индуктивным процессом разложения функции по пере-
переменной. В самом деле, легко видеть (рис. 9), что L(l) = 2. Если же

58
Гл. III. Сложность реализации булевых функций
Рис. 9
п ^ 2, то разложим произвольную функцию f(x\,..., хп) по перемен-
переменной хп:
, Хп-!, Xn)=Xnkf(x1,..., Хп-!, 1) V Хп & /Oi, . . . , Хп-и °) j
и обозначим для краткости функции f{x\,...,xn-i,l) и f(x\,...
...,жп_ь0) через /; и //;.

§2. Схемы из функциональных элементов
59
На рис. 9 показано, как из схем, реализующих функции /' и /",
получить схему, реализующую функцию /. Из нее видно, что
L(n) ^2-1,G1-1)+4.
Это рекуррентное соотношение вместе с условием L(l) = 2 дает
L{n) ^ 3 • 2П - 4.
Отметим, что более тонкие методы синтеза схем позволяют уста-
установить, что при больших значениях п величина L(n) будет близка к
величине 2п/п. Как говорят в подобных случаях, L(n) асимптотиче-
асимптотически равна 2п/п.
Общая теория синтеза СФЭ показывает, что для "почти всех" буле-
булевых функций от п переменных минимальная сложность реализующих
их схем близка к величине L(n). На этом фоне представляют интерес
функции, сложность реализации которых схемами существенно мень-
Рис. 10
ше, чем L(n), например, имеющие линейную (по п) сложность. К по-
последним функциям относится двоичный сумматор — вектор-функция,

60
Гл. III. Сложность реализации булевых функций
вычисляющая двоичные разряды z\,..., zn, zn+i суммы n-разрядных
чисел ж, у, заданных в двоичной системе счисления представления-
представлениями хп ...х\ и Уп .. .у\ (старшие разряды этих представлений могут
быть нулевыми). Сложение чисел ж, у можно осуществить "столби-
"столбиком", обозначая через gi,..., qn+i результаты переносов из предыду-
предыдущих разрядов (qi = 0):
(яп+i qn ... qi)
Хп . . . Х\
Уп ... У\
Zn+1
Очевидно, что
Zi = Xi®yi
Опираясь на тождество
Xi 0 Уг 0 qi = Xi
qi+1 =
C7)
i V
qi &
V yi V
нетрудно построить СФЭ, реализующую преобразования C7)
(рис. 10). Обозначим соответствующую схему через Bi A < г ^ п).
ХпУп
Х2 У2
I
вп
II
в2
1
В!
Рис. 11
Тогда схема Еп для двоичного сумматора п-разрядных чисел получа-
получается путем последовательного соединения блоков Bi (рис. 11). Здесь
?n+1 = gn+i, а схема В\ осуществляет преобразование
2i = [хх & 2/i) & (xi V 2/i), q2=x1by1.
Очевидно, что Ь(В\) = 4 и L(Bi) = 9 при 1 < г ^ п. Таким образом,
УПРАЖНЕНИЯ
28.	Постройте СФЭ, реализующую функцию х\ © ... © хп (п ^ 2)
со сложностью 4 (п — 1).
29.	Докажите, что существует такая константа С, что для любой

§3. Выполнимость КНФ	61
симметрической функции /, зависящей от п переменных, справед-
справедлива оценка L(f) ^ Сп (определение симметрической функции см.
в упр. 5).
§ 3. Выполнимость КНФ
В начале 70-х годов в ряде разделов математики (теория алгорит-
алгоритмов, теория булевых функций, теория графов, теория чисел, линей-
линейное программирование и др.) было обнаружено большое число задач
(сейчас их насчитывается свыше 800), которые обладают следующими
отличительными особенностями.
Каждая из задач представляет собой по форме массовую задачу
переборного типа. Если для любой из этих задач каким-либо образом
"угадано" решение, то проверка того факта, что найденное решение
действительно удовлетворяет условиям задачи, требует полиномиаль-
полиномиального (от длины записи входных данных) числа шагов. Наконец, все
эти задачи, как говорят, полиномиально эквивалентны. Это следует
понимать так. Пусть, например, задачи А и В представляют собой по-
поиск для заданного двоичного набора а некоторого набора Ь, который
по отношению к а обладает заданным свойством. Тогда должны суще-
существовать полиномы pi (n) и р2 (п) с натуральными коэффициентами и
такие алгоритмически вычислимые функции Д(ж), /2(ж), отобража-
отображающие множество всех двоичных наборов в себя, что, во-первых, функ-
функции Д(ж), /2 (х) можно вычислить подходящими алгоритмами, кото-
которые для любого двоичного набора длины п заканчивают работу соот-
соответственно не более чем через р\(п) или Р2(п) шагов. А во-вторых, для
произвольного двоичного набора х задача А (соответственно задача
В) имеет решение тогда и только тогда, когда для двоичного набора
fi(x) (для /2(ж)) имеет решение задача В (задача А). О функциях
Л (х), /2 (х) говорят, что они полиномиально сводят задачу А к задаче
В и задачу В к задаче А.
Все эти многочисленные задачи из различных разделов матема-
математики в научной литературе получили название TVP-полных проблем
(от английских слов Nondeterministic Polynomial). В теории булевых
функций одной из "канонических" TVP-полных проблем является про-
проблема выполнимости конъюнктивных нормальных форм (сокращен-
(сокращенно ВЫПОЛНИМОСТЬ). Содержательно эта проблема состоит в том,
чтобы по произвольной конъюнктивной нормальной форме (опреде-
(определение КНФ см. в § 8 гл. I) выяснить, существует ли двоичный набор,
обращающий эту КНФ в 1 (выполняющий КНФ). Ясно, что пробле-
проблему ВЫПОЛНИМОСТЬ можно решить тривиальным алгоритмом, пе-
перебирая для заданной КНФ К, зависящей от п переменных, все 2П
двоичных наборов длины п и вычисляя для каждого из них значение
формулы К. Понятно также, что проверка выполнимости КНФ К

62	Гл. III. Сложность реализации булевых функций
на заданном двоичном наборе требует сравнительно небольшого (по
отношению к размеру формулы К) числа шагов: следует вместо каж-
каждой из переменных формулы К подставить соответствующее значе-
значение 0 или 1 из рассматриваемого набора и затем вычислить значение
каждой дизъюнкции, входящей в К, пользуясь хорошо известными
соотношениями
0 = 1, 1 = 0, 0V0 = 0, OV1 = 1VO = 1V1 = 1.
Все эти действия можно выполнить, например, за квадратичное
(относительно длины записи формулы К) число шагов.
Строгое доказательство TVP-полноты проблемы ВЫПОЛ-
ВЫПОЛНИМОСТЬ требует привлечения понятий недетерминированной ма-
машины Тьюринга и полиномиального вычисления на такой машине,
что выходит за рамки данной брошюры. Мы ограничимся лишь рас-
рассмотрением двух важных частных случаев проблемы ВЫПОЛНИ-
ВЫПОЛНИМОСТЬ: 2-ВЫПОЛНИМОСТЬ и 3-ВЫПОЛНИМОСТЬ (сокращенно
2-ВЫП и 3-ВЫП). Проблема 2-ВЫП получается из проблемы ВЫ-
ВЫПОЛНИМОСТЬ, если в последней рассмотреть лишь такие КНФ,
у которых каждый конъюнктивный сомножитель содержит не бо-
более двух переменных. Аналогичным образом определяется проблема
3-ВЫП. Далее мы докажем, что проблема 2-ВЫП полиномиально раз-
разрешима (это означает, в частности, что проблема 2-ВЫП не является
проблемой переборного типа), а проблема 3-ВЫП TVP-полна.
Начнем с проблемы 2-ВЫП. Итак, будем рассматривать лишь та-
такие КНФ К, у которых каждый конъюнктивный сомножитель име-
имеет вид х\ или х\ VxJ, где о,т Е {0,1}. Алгоритм проверки выпол-
выполнимости формулы К будет состоять из нескольких этапов, число ко-
которых не превосходит числа переменных, входящих в формулу К.
Каждый этап характеризуется некоторой переменной из К. На каж-
каждом этапе происходит либо удаление из К некоторых конъюнктивных
сомножителей, либо удаление переменной, однако в последнем случае
могут появиться дополнительные конъюнктивные сомножители. Чис-
Число таких дополнительных сомножителей не превосходит квадрата от
числа переменных, входящих в исходную формулу К. После прове-
проведения каждого этапа образуется КНФ К1, которая выполнима или
невыполнима одновременно с КНФ К. На заключительном этапе бу-
будет получена формула от одной переменной, выполнимость которой
определяется тривиальным образом.
Сначала рассмотрим этапы, когда в формулу К входит однобук-
венный сомножитель вида х или х. Пусть для определенности это
будет сомножитель х. Найдя такой сомножитель в формуле К, про-
просмотрим формулу К и выделим в ней все остальные сомножители,
содержащие переменную х. Если среди них есть сомножитель ж, то,
очевидно, формула К невыполнима. Тогда завершаем работу алго-
алгоритма, давая отрицательный ответ на вопрос о выполнимости фор-
формулы К.

§3. Выполнимость КНФ	63
Пусть сомножителя ж в формуле К нет. Пользуясь эквивалентно-
стями (слева направо)
ж & (ж V уа) = ж, ж & (ж V з/*7) = ^ & ?Д
производим сокращения в КНФ К: либо вычеркиваем сомножи-
сомножитель х V уа, либо заменяем сомножитель xV уа сомножителем уа. В
образовавшейся после этих преобразований формуле приводим оди-
одинаковые сомножители и получаем КНФ К'. Поскольку формула К'
получается из формулы К применением некоторых эквивалентных
преобразований, формула К' будет эквивалентна формуле К. Одна-
Однако она содержит меньше символов, чем формула К. Кроме того, весь
процесс построения формулы К' из формулы К требует заведомо
не более С\ш? "элементарных" действий, где С\ — натуральная кон-
константа, an— длина записи формулы К. При этом под элементарным
действием мы понимаем сравнение символов в формуле, перемещение
внутри формулы на один символ влево или вправо, вычеркивание од-
одного символа и т.п.
Пусть теперь в формуле К однобуквенные сомножители от-
отсутствуют. Возьмем произвольную переменную ж, входящую в фор-
формулу К. Пусть Kq представляет собой конъюнкцию всех сомножите-
сомножителей из К вида х V у (здесь у может быть как символом переменной,
так и ее отрицанием):
K0 = (xVyi)&...&(xVyk);
К\ представляет аналогичную конъюнкцию сомножителей вида х\1'z:
Кх = (х V zx) & ... & (х V zi);
К2 представляет конъюнкцию всех остальных сомножителей из К.
Тогда
К = К0&К1&К2.
Если, например, конъюнкция Kq пуста (соответствующих сомножите-
сомножителей вида х V у в формуле К нет), то конъюнкция К\ выполнима при
х — 1. Следовательно, формула К будет выполнимой тогда и только
тогда, когда выполнима КНФ К2. Поэтому в качестве КНФ К' можно
взять КНФ i^2, которая получается из КНФ К вычеркиванием всех
сомножителей, входящих в К\. Аналогично рассуждаем, если пуста
конъюнкция К\.
Предположим, что обе конъюнкции Kq,Ki непусты. Имеем
(х V 2/i) & ... & (х V ук) = х V У1 & ... & ук,
(х V zx) & ... & (х V zi) = х V 2i & ... & z\.
Далее, формула вида (х V Y) & (ж V Z) выполнима в том и только
том случае, когда выполнима формула Y \l Z. Следовательно, форму-
формула К будет выполнима тогда и только тогда, когда будет выполнимой
формула
(y1k...kyk\/z1k...kzl)kK2.

64	Гл. III. Сложность реализации булевых функций
Однако
Таким образом, вопрос о выполнимости формулы К сводится к
аналогичному вопросу для формулы
К'=
В формулу К' не входит переменная х и, как видно из сравнения
формул К и К', в формулу К' добавляется не более 2Ы новых
вхождений символов у^ Zj. Поскольку k,l ^ п (напомним, что п —
длина записи формулы К), длина записи формулы К' увеличивается
по сравнению с длиной записи формулы К не более, чем на 2п2. Из
описания процесса построения формулы К' следует также, что фор-
формулу К можно преобразовать в формулу К' не более, чем за С2П2
"элементарных" действий, где С2 — натуральная константа.
Таким образом, последовательно применяя к исходной КНФ К
описанные выше этапы преобразований, мы не далее, чем на (п — 1)-м
этапе либо убедимся в невыполнимости формулы К, либо придем к
формуле вида ж, ж, ж V ж, ж&ж от одной переменной. В первых трех
случаях имеем, очевидно, выполнимость формулы К, в четвертом
случае — невыполнимость. В целом весь процесс проверки выполни-
выполнимости формулы К займет не более, чем С • п2 • п = Сп3 "элементар-
"элементарных" действий, где С = max(Ci, C2). Тем самым мы установили, что
проблему 2-ВЫП можно решить, произведя примерно Сп3 элементар-
элементарных действий, где п имеет смысл длины записи исходной КНФ. Ины-
Иными словами, проблема 2-ВЫП является полиномиально разрешимой.
Рассмотрим теперь проблему 3-ВЫП и докажем, что она явля-
является TVP-полной. Наше доказательство будет относительным, по-
поскольку мы предполагаем TVP-полной проблему ВЫПОЛНИМОСТЬ.
Очевидно, что проблема 3-ВЫП полиномиально сводится к пробле-
проблеме ВЫПОЛНИМОСТЬ: соответствующая сводящая функция f(x) по
каждой КНФ, имеющей не более трех дизъюнктивных слагаемых в
каждом конъюнктивном сомножителе, выдает в качестве результата
эту же самую КНФ. Докажем, что проблема ВЫПОЛНИМОСТЬ так-
также полиномиально сводится к проблеме 3-ВЫП. С этой целью проде-
продемонстрируем, как за полиномиальное число шагов преобразовать про-
произвольную КНФ К в такую КНФ К' с не более чем тремя слагаемы-
слагаемыми в каждом сомножителе, что К и К' выполнимы или невыполнимы
одновременно.
Очевидно, что можно ограничиться рассмотрением только та-
таких КНФ, у которых имеются сомножители, содержащие более трех
дизъюнктивных слагаемых. Пусть С = у± V ... V ут — один из та-
таких сомножителей в формуле К (у±,..., ут могут быть здесь как
переменными, так и отрицаниями переменных). Обозначим через К\

§3. Выполнимость КНФ	65
КНФ, которая получается из КНФ К вычеркиванием сомножителя С.
Пусть и — переменная, не входящая в К. Положим
D = B/i V у2 V и) & (?/з V ... V уш V и).
Покажем, что КНФ К выполнима тогда и только тогда, когда выпол-
выполнима КНФ DkKi.
Пусть набор а = (аь ..., ап) обращает КНФ К в 1. Тогда, в част-
частности, набор а обращает в 1 дизъюнкцию С. Если набор а обращает
в 1 формулу 2/1 V 2/2, то набор (ai,..., an, 0) будет обращать в 1 фор-
формулу D и, следовательно, формулу D &iK\ (последний разряд набора
(ai,..., an, 0) отвечает переменной и). Если же набор а обращает в 1
формулу 2/з V ... V уп, то аналогичное утверждение будет справедливо
для набора (ai,..., an, 1).
Обратно, пусть (ai,..., an, 6) — набор, обращающий в 1 КНФ
D & К\. Если 6 = 0, то набор а обращает в 1 формулу 2/1 V 2/2 и,
следовательно, формулу С. При 6 = 1 то же самое будет справедливо
для формул 2/з V ... V ут и С.
Описанное преобразование уменьшает на 1 число слагаемых в со-
сомножителе 2/з V ... V 2/ш V й, полученном из G, и увеличивает на 2
общее число букв в КНФ D & К\ по сравнению с КНФ К. Если в
КНФ К имеется к сомножителей соответственно с числом слагаемых
?7ii, • • • ? wifc, где TTii,..., т/. > 3, то достаточно аналогичным способом
добавить не более 2 (т\ + ... + га/. — Зк) букв с тем, чтобы получить
требуемую КНФ К', выполнимую или невыполнимую одновременно
с КНФ К. То, что преобразование формулы К в формулу К' можно
выполнить за полиномиальное число действий, очевидно.
5 С.С.Марченков

ОТВЕТЫ, РЕШЕНИЯ, УКАЗАНИЯ
1.	22""fc.
2.	Набор A011) определяет импликацию х<± —У х\, набор A001) —
эквивалентность х\ ~ Ж2, набор A000) — функцию х\ \, Ж2, называе-
называемую стрелкой Пирса (или антидизъюнкцией).
3.	Функция #1(жъЖ2,жз) сУЩественн0 зависит от переменных
xi, жз, функция #2(^1,^2,^3) — от переменных xi, Ж2, х%.
4.	Существенные (фиктивные) переменные функций / и g совпа-
совпадают. Чтобы в этом убедиться, достаточно заметить, что если а^ =
= /(&i,..., Ьп) A ^ г ^ 2П), то cti = #(bi,..., Ьп). Поэтому из равенств
dk = /(bi,... ,&j_i,0,6J+b... ,bn), сц = /(bi,.. .,^_1,1,^+ь.. .,bn)
следуют равенства
dk = g(bi,... ,5^-1,1, bj+i,... ,5п)? a/ = 0(bi,. • • ,bj-i,Q,bj+i,... ,bn).
Значит, из существенной зависимости функции /(xi,... ,жп) от пере-
переменной Xj вытекает существенная зависимость функции g(xi,..., хп)
от переменной Xj, и наоборот.
5.	Пусть /(ж1,...,жп) — симметрическая функция, отличная от
константы. Тогда для некоторого т @ ^ т < п) и некоторого а из
множества В функция / принимает значение а на всех двоичных
наборах, содержащих т единичных компонент, и значение а на всех
двоичных наборах, содержащих т + 1 единичных компонент. Теперь
для доказательства утверждения достаточно для любого i (I ^ i ^ п)
рассмотреть двоичные наборы, содержащие т и т + 1 единичных
компонент и различающиеся только в г-ой компоненте.
6.	/ii(xi,x2) = 1, /^2(^1,^2,^3) = xi Ф х3 © 1.
8. Ни при одном п (п ^ 3).
10.	а) и в) являются, б) не является.
11.	Неверно. Например, объединение замкнутых классов То и С\
не содержит функцию ж, которая получается суперпозицией функ-
функций х 0 у из класса То и 1 из класса Ci.
12.	xyz (В xz (В у (В z (В 1 = xz V xz • у V xz • у V xz • у.
13.	ж^/z V xyz V ж^/z V x^z V xyz.

Ответы, решения, указания	67
15.	Если
/(аь.. .,а;_1,0,а;+ь. ..,ап) = Ь, /(аь..., а;_ь 1, а;+ь ... ,ап) = Ь,
то
/*(аь... ,ai_i,l,ai+i,... , ап) = Ъ,
/* (ai,..., a;_i, 0, ai+i,..., ап) = Ъ.
16.	Верно.
17.	Oi v...vxn)ei.
18.	xyzw 0 жгуш 0 xzw 0 2/2:?/; 0 xz 0 жги 0 ги 0 1.
19.	Имеется четыре самодвойственные функции /(xi, Ж2), которые
задаются двоичными наборами
(ООП), @101), A010), A100).
Это суть соответственно функции xi, Ж2, #2, #i.
21. При любом п (п ^ 3) функция /(xi,... ,жп), задаваемая по-
полиномом Жегалкина
Х\Х2 0
принимает значение 1 ровно на 2п~1 наборах. Если п ^ 2, то любая
функция от п переменных, принимающая значение 1 ровно на 2п~1
наборах, является линейной.
22.	Имеется 20 монотонных функций от трех переменных:
0, 1, ж, у, z, xV у, x\l z, y\lz, xy, xz, yz, x\ly\l z, xyz,
хМyz, yM xz, z\lxy, x(y\/z), y(xVz), z(xVy), xyM xzM yz.
23.	Пусть функция j[x\,..., xn) монотонна и (ai,..., an) ^ (Ъ\,...
...,6n). Тогда
(bi,... ,bn) ^ (ab.. .,an), /Ei,... ,&n) ^ /(Si,... ,an)
и, следовательно,
/(ab...,an) ^ 7Fb...,6n).
24.	0, 1, e^(xb...,xn) (l^i^n, n = l,2,...).
25.	Например, {1, x 0 t/, ж V у}.
26.	Из непринадлежности функции /(жь ... ,жп) классам Tq, Ti
следует, что /@,..., 0) = 1 и /A,..., 1) = 0. Таким образом, / не яв-
является монотонной функцией. Если бы функция / была линейной, т.е.
/(xi,..., хп) = xh 0 ... xis 0 a,
то из условия /@,..., 0) = 1 вытекало бы, что а = 1, а из условия
/A,...,1) = 0, что s — нечетное число. Однако тогда / была бы
самодвойственной функций. Если вместо класса S взять класс L, то

Ответы, решения, указания
утверждение становится неверным. Это видно на примере самодвой-
самодвойственной функции ху 0 xz 0 yz 0 1.
27.	Сокращенная ДНФ есть
ху V ху V xz V xz V yz V f/z,
минимальные —
хуМ xzM yz, xyM xzM yz,
тупиковые неминимальные —
ху У ху У y'z У yz, xzV xz\J yzV yz, ху V ху V xz V xz.
28.	Взять за основу схему, изображенную на рис. 5.
29.	Любую симметрическую функцию f(x\,... ,хп) можно за-
задать набором чисел (i\,..., im) таким, что 0^ii<...<im^n и
/(ai,...,an) = 1 тогда и только тогда, когда количество единиц
в наборе (ai,...,an) есть число из набора (H,...,zm). В связи с
этим сначала следует построить схему линейной сложности, которая
для любого двоичного набора (а\,..., ап) вычисляет двоичные разря-
разряды Ъ\,..., Ъг числа а\ + ... + ап (сложение арифметическое, а не по
модулю 2).
Тогда г = [log2 п] + 1, где [d] обозначает целую часть числа d, и
по набору (Ъ\,..., Ъг) можно однозначным образом определить значе-
значение /(аь... ,ап).
Вторая схема линейной сложности осуществляет преобразование
(bi,-• • А) ->•

ОГЛАВЛЕНИЕ
Предисловие	 3
Глава I
ЭЛЕМЕНТАРНЫЕ СВОЙСТВА БУЛЕВЫХ ФУНКЦИЙ
§ 1. Табличное задание булевых функций	 5
§ 2. Некоторые элементарные булевы функции	 7
§ 3. Существенные и фиктивные переменные 	 9
§ 4. Представление булевых функций формулами	 12
§ 5. Эквивалентность формул	 15
§ 6. Замыкание. Замкнутые классы 	 18
§ 7. Разложение булевой функции по переменной	 21
§ 8. Двойственность. Принцип двойственности	 23
§ 9. Полиномы Жегалкина	 26
Глава II
ЗАМКНУТЫЕ КЛАССЫ И ПОЛНОТА
§ 1. Класс самодвойственных функций		30
§ 2. Класс линейных функций		31
§ 3. Класс монотонных функций		34
§ 4. Критерий полноты		38
§ 5. Замкнутые классы, содержащие константы		40
Г л а в а III
СЛОЖНОСТЬ РЕАЛИЗАЦИИ БУЛЕВЫХ ФУНКЦИЙ
§ 1. Минимизация ДНФ	 45
§ 2. Схемы из функциональных элементов	 52
§ 3. Выполнимость КНФ	 61
Ответы, решения, указания	 65

Учебное издание
МАРЧЕНКОВ Сергей Серафимович
БУЛЕВЫ ФУНКЦИИ
Редактор Е.Ю. Ходан
Оригинал-макет Д. В. Горбачева
Оформление обложки А.Ю. Алехиной
ЛР №071930 от 06.07.01. Подписано в печать 23.05.02.
Формат 60x90/16. Бумага офсетная № 1. Печать офсетная.
Усл. печ. л. 31. Уч.-изд. л. 34,1. Тираж 3000 экз. Заказ №
Издательская фирма
« Физико-математическая литература»
МАИК «Наука/Интерпериодика»
117864 Москва, ул. Профсоюзная, 90
Отпечатано в ФГУП
«Производственно-издательский комбинат ВИНИТИ»
140010, г. Люберцы, Московская обл., Октябрьский пр-т, 403

В серии «Популярные лекции по математике» в разные
годы вышли следующие книги.
Маркушевич А. И. Возвратные последовательности.
Натансон И. П. Простейшие задачи на максимум и минимум.
Соминский И. С. Метод математической индукции.
Маркушевич А. И. Замечательные кривые.
Коровкин П. П. Неравенства.
Воробьев Н.Н. Числа Фибоначчи.
Курош А.Г. Алгебраические уравнения произвольных степеней.
Гельфонд А.О. Решение уравнений в целых числах.
Маркушевич А.И. Площади и логарифмы.
Смогоржевский А.С. Метод координат.
Дубнов Я. С. Ошибки в геометрических доказательствах.
Натансон И.П. Суммирование бесконечно малых величин.
Маркушевич А.И. Комплексные числа и конформные отображения.
Фетисов А.И. О доказательствах в геометрии.
Шафаревич И.Р. О решении уравнений высших степеней.
Шерватов В. Г. Гиперболические функции.
Болтянский В. Г. Что такое дифференцирование?
Миракьян Г.М. Прямой круговой цилиндр.
Люстерник Л.А. Кратчайшие линии.
Лопшиц A.M. Вычисление площадей ориентированных фигур.
Головина Л.И., Яглом И.М. Индукция в геометрии.
Болтянский В.Г. Равновеликие и равносоставленные фигуры.
Смогоржевский А.С. О геометрии Лобачевского.
Аргунов Б.И., Скорняков Л.А. Конфигурационные теоремы.
Смогоржевскнй А.С. Линейка в геометрических построениях.
Трахтенброт Б.А. Алгоритмы и машинное решение задач.
Успенский В.А. Некоторые приложения механики к математике.
Архангельский И.А., Зайцев Б.И. Автоматические цифровые маши-
машины.
Костовский А.Н. Геометрические построения одним циркулем.
Шилов Т.Е. Как строить графики.
Дорфман А.Г. Оптика конических сечений.

Вентцелъ Е.С Элементы теории игр.
Барсов А.С. Что такое линейное программирование.
Маргулис В.Е. Системы линейных уравнений.
Виленкин Н.Я. Метод последовательных приближений.
Болтянский В.Г. Огибающая.
Шилов Т.Е. Простая гамма (устройство музыкальной шкалы).
Шрейдер Ю.А. Что такое расстояние?
Воробьев Н.Н. Признаки делимости.
Фомин СВ. Системы счисления.
Коган В.Ю. Приложение механики к геометрии.
Любич Ю.И., Шор Л.А. Кинематический метод в геометрических за-
задачах.
Успенский В.А. Треугольник Паскаля.
Бакельман И. Я. Инверсия.
Яглом И.М. Необыкновенная алгебра.
Соболь И.М. Метод Монте-Карло.
Калужнин Л.А. Основная теорема арифметики.
Солодовников А.С. Системы линейных неравенств.
Шилов Т.Е. Математический анализ в области рациональных функ-
функций.
Болтянский Б.Г., Гохберг Н.Ц. Разбиение фигур на меньшие части.
Бескин И.М. Изображения пространственных фигур.
Бескин Н.М. Деление отрезка в данном отношении.
Розенфельд Б.А., Сергеева И. Д. Стереографическая проекция.
Успенский В.А. Машина Поста.
Беран Л. Упорядоченные множества.
Абрамов С.А. Элементы программирования.
Успенский В.А. Теорема Гёделя о неполноте.
Шашкин Ю.А. Эйлерова характеристика.
Скорняков Л.А. Системы линейных уравнений.
Шашкин Ю.А. Неподвижные точки.
Петросян Л.А., Рихсиев Б.Б. Преследование на плоскости.