Книга
← К списку книгЗагрузка разделов…
активнаАктивные записи участвуют в каталоге и синках. Неактивная книга скрыта, но не удалена из базы.
Книга
ПРЕДИСЛОВИЕ
С понятием функции сегодня знаком каждый выпускник средней школы. И это закономерно — понятие функции относится к тем немногим понятиям, которые пронизывают все разделы математики.
В математике имеется огромное число различных типов функций. Однако есть в ней такие функции, которые по праву должны быть названы самыми простыми. Речь идет о булевых функциях ) — функциях, которые определены на множестве, состоящем из двух элементов. Уменьшить это множество до одного элемента невозможно — происходит вырождение понятия функции. Поэтому булевы функции занимают первую ступень в иерархии функций, ниже которой располагаются только константы.
Как математический объект булевы функции начали интенсивно изучаться лишь около 50 лет назад. Примерно в то же время появились и первые электронные цифровые вычислительные машины. Совпадение этих двух событий неслучайно. Дело в том, что по ряду причин технического и математического характера язык, на котором “говорят” ЭВМ, есть язык двух символов: да-нет, 0-1. Поэтому описывать работу ЭВМ и программировать на ЭВМ удобно с использованием булевых функций. Булевы функции оказались также подходящим инструментом для описания функционирования широкого круга дискретных преобразователей информации, которые не относятся к универсальным вычислительным машинам: переключателей, коммутаторов, простейших сумматоров и некоторых других.
Бурное развитие вычислительной техники, а также запросы со стороны смежных разделов математики поставили перед специалистами по булевым функциям целый ряд серьезных математических проблем: анализ различных форм и возможностей представления булевых функций, оценки сложности реализации булевых функций формулами и схемами, оценки сложности построения оптимальных формул и схем и некоторые другие. Эти проблемы и направления исследований и по сей день остаются центральными в теории булевых функций.
Основные цели предлагаемой брошюры состоят в том, чтобы научить читателя языку булевых функций, познакомить его с основными фактами из теории булевых функций, показать, как решаются простейшие из перечисленных выше задач и в какой-то степени обрисовать трудности и перспективы на пути решения более сложных проблем. Мы полагаем, что потребность в подобном знакомстве с элементами теории булевых функций давно назрела, тем более, что компьютерная грамотность предполагает умение оперировать с простейшими булевыми функциями.
Книга предназначена в первую очередь для учеников старших классов средней школы. Она может быть также полезна студентам младших курсов университетов и технических вузов, изучающим дискретную математику.
Глава I
ЭЛЕМЕНТАРНЫЕ СВОЙСТВАБУЛЕВЫХ ФУНКЦИЙ
§ 1. Табличное задание булевых функций
Булевы функции определяются на множестве, состоящем из двух элементов. В качестве этих элементов обычно берутся числа 0 и 1. Будем обозначать множество, состоящее из 0 и 1, через В. Булеву функцию определим как функцию, аргументы которой принимают значения из В со значениями, также принадлежащими В.
Булеву функцию / (от) п аргументов обозначают через /(яд,... . ..,жп) и называют также булевой функцией (от) п переменных. Иногда в обозначениях булевых функций вместо переменных Ж1, Ж2,... используют переменные y^w,..., возможно, с индексами.
Булева функция /(яд,...,жп) ставит в соответствие каждому упорядоченному набору (сд,..., ап), состоящему из элементов 0 и 1, единственный элемент множества В — значение /(щ,..., ап). Как же задают функцию f(x±,..., хп)?
Чтобы ответить на этот вопрос, найдем предварительно число элементов множества Вп. состоящего из всех упорядоченных двоичных (имеются в виду элементы 0 и 1) наборов (сд,..., ап) длины п. Докажем, что это число равно 2П. Доказательство проведем с использованием принципа полной математической индукции.
Очевидно, что множество В1 состоит ровно из двух наборов. Предположим по индукции, что для данного п (n ^ 1) множество Вп состоит из 2П наборов, и рассмотрим множество Вп^г. Каждый двоичный набор (сд,..., ап) длины п порождает два различных набора (ai,..., пп, 0), (ai,..., пп, 1) из множества Вп^г. При этом если наборы (од,..., ап) и (bi,..., Ьп) из Вп различны, то при любом выборе элементов ап^\ и Ьп^\ из множества В будут различными и наборы
(бЦ, • • • , Нп, ^п+1), Д1? • • • Дп? ^п+1).
Следовательно, число наборов в множестве Bn"^T в два раза больше числа наборов в множестве Вп. Поскольку последнее число по предположению индукции есть 2П, первое число будет равно 2П • 2 = 2n+1.
Определив число наборов в множестве Вп. вернемся к вопросу о задании булевой функции f(x±,..., хп). Проще всего ее можно задать так называемым табличным способом: перечислить в некотором порядке все наборы из множества Вп и вслед за каждым набором записать значение функции / на этом наборе. Наиболее наглядно реа-
лизовать этот способ задания булевой функции можно действительно в виде таблицы (табл. 1).
В левой части этой таблицы выписаны по строкам все 2П двоичных наборов длины п. Порядок, в котором они расположены в таблице (сверху вниз), носит название лексикографический порядок.
Таблица 1
Х1
Х2 • ■
■ • Х-п,
/(яД,Ж2, .
• • , ЯД )
0
0
0
/(0,0,..
.,0)
0
0
1
/(0,0,..
.,1)
1
1
0
/(1,1,..
•, 0)
1
1
1
/(1,1,..
.,1)
Первым относительно этого порядка является нулевой набор, а каждый следующий набор получается из предыдущего прибавлением 1. При этом мы считаем, что каждый набор является записью подходящего неотрицательного целого числа в двоичной системе счисления, а имеющиеся слева нулевые разряды поставлены лишь для того, чтобы все наборы имели одну и ту же длину п.
Условимся о том, что, говоря о табличном способе задания булевой функции, мы всегда будем иметь в виду, что в левой части соответствующей таблицы двоичные наборы выписаны именно в лексикографическом порядке. В этом случае для всех булевых функций от п переменных левая часть табл. 1 будет одной и той же. Поэтому потребность в ее воспроизведении, вообще говоря, отпадает. Тогда от табл. 1 остается только столбец значений функции / высоты 2П.
Таким образом, мы приходим к выводу, что любую булеву функцию от п переменных можно задать двоичным столбцом высоты 2П. Верно, разумеется, и обратное: всякий двоичный столбец высоты 2П определяет некоторую булеву функцию от п переменных.
На практике вместо двоичных столбцов высоты 2П удобнее пользоваться двоичными строками (наборами) длины 2П. При этом первый элемент столбца становится первым элементом строки, второй элемент столбца — вторым элементом строки и т.д. В результате для булевой функции /(яд,..., жп) получаем двоичную строку вида
(/(0,0,..., 0)/(0,0,..., 1) /(1,1, - - - ,0)/(1,1, - - -, 1». (1)
Итак, каждую булеву функцию /(яд,..., жп) можно представить двоичным набором (1) ее значений длины 2П и всякий двоичный набор длины 2П определяет некоторую булеву функцию от п переменных. Нетрудно заметить, что данное соответствие, как говорят, взаимно однозначно: различным булевым функциям от п переменных (различным двоичным наборам длины п) отвечают различные двоичные
наборы длины 2П (различные булевы функции от п переменных). Это позволяет найти число всех булевых функций от п переменных. Действительно, оно равно числу всех двоичных наборов длины 2П, т.е. числу всех элементов множества В2 . Как мы установили выше, данное число равно 22 .
Множество всех булевых функций принято обозначать через Р^.
УПРАЖНЕНИЯ
Каково число булевых функций от п переменных, которые на фиксированных к двоичных наборах (к ^ 2П) принимают фиксированные к значений?
§ 2. Некоторые элементарные булевы функции
Составим таблицу для всех четырех булевых функций одной переменной.
Таблица 2
X
fl(^
/2 (ж)
/з(ж)
А(ж)
0
1
0
0
1
1
0
1
1
0
Функции /Дж) и /2 (ж) называются константами 0 и 1. Их часто так и обозначают 0 и 1, не указывая явно переменную х. Как видно из табл. 2, значения функции /з(ж) совпадают со значениями переменной х. Поэтому функцию /з(ж) называют тождественной функцией и вместо символа функции, как правило, пишут лишь символ переменной х. Функция /4 (ж) осуществляет инвертирование значений переменной х. Ее называют отрицанием и обозначают х (читается: не икс).
Обратимся далее к функциям от двух переменных. Как мы знаем, их насчитывается ровно 22 = 16. Мы могли бы поступить так же,
Таблица 3
Х1
Х2
fl
/2
/3
/4
/5
/б
/7
/8
/9
/ю
/и
0
0
0
1
0
0
1
1
0
0
0
1
1
0
1
0
1
0
1
1
0
0
1
1
1
1
1
0
0
1
1
0
0
1
0
1
1
0
1
1
1
0
1
1
1
0
0
1
1
0
1
0
как с функциями от одной переменной, и представить в одной таблице значения всех 16 функций. Однако на первых порах нам будет достаточно познакомиться с одиннадцатью функциями (по техническим причинам в табл. 3 после символов функций опущены символы переменных Ж1, Ж2).
Как видно из табл. 3, функции Д (жх, х^ и Д (^1, ^2) являются константами 0 и 1. Значения функции /з(жх, х^ совпадают со значениями переменной Ху. Поэтому функцию /3(^1,Ж2) называют функцией выбора (первого аргумента) или селекторной функцией и обозначают еДжх,x^Y Так же, как для тождественной функции одной переменной, вместо выражения е^х-^хз) часто пишут лишь жх. Аналогично обстоит дело с функцией Д(жх, #2), которая представляет собой функцию выбора (второго аргумента) и обозначается е^х^х^. Функции /5(^1, Ж2) и Д(жх,Ж2) инвертируют соответственно значения переменных жх и ^2. Поэтому их обычно заменяют функциями жх и х^.
Анализируя столбец значений функции Д(жх, x^Y нетрудно понять, что эту функцию можно определить как жх • ж 2 или как шш(ж1,Ж2). Функция /7 — одна из важнейших в логике и теории булевых функций. Она носит название конъюнкции (или логического произведения). Для функции /7(^1,Ж2) приняты обозначения: жх • Ж2 (или Ж1Ж2), жх & Ж2 и жх Л Ж2- (Так же, как в арифметике и алгебре, при написании некоторых функций от двух переменных знак функции может ставиться между символами переменных.) В дальнейшем мы будем преимущественно использовать обозначения жх-Ж2 или Ж1Ж2 (читается: жх и Ж2).
Легко проверить, что функцию /3(^1, Ж2) можно определить как шах(жх,Ж2). Функция Д также относится к числу важнейших в логике и теории булевых функций. Функцию фв(х1,Х2) называют дизъюнкцией (или логической суммой) и обозначают жх V Ж2 (читается: Ж1 или Ж2).
Функция Д(жх,Ж2) есть сложение по модулю 2 (1 + 1 = 0 по модулю 2). В отличие от обычного (арифметического) сложения жх + Ж2 она обозначается жх ф Ж2.
Функция /ю(жх,Ж2) носит название импликация и обозначается жх —> Ж2- Название “импликация” пришло из логики, где имеется соответствующая логическая связка импликация.
Наконец, функция /ц(жх,Ж2) называется штрихом Шеффера (или антиконъюнкцией) и обозначается жх | Ж2.
Для любого натурального п и любого г (1 ^ г ^ п) обозначим через
. ,xt,... ,ж„)
функцию выбора г-го аргумента (или селекторную функцию), значения которой совпадают со значениями переменной ж^. Отметим, что вместо функции еДжх,..., ж^ ..., жп) часто записывают лишь переменную Xi.
УПРАЖНЕНИЯ
Достройте табл. 3, выписав столбцы значений остальных пяти булевых функций. Используя приведенные выше названия функций от двух переменных, попытайтесь дать подходящие названия этим пяти функциям.
§ 3. Существенные и фиктивные переменные
Когда говорят, что булева функция /(яд,..., жп) зависит от переменных ад,... ,жп, имеют в виду лишь то, что функция / является функцией п переменных, которые обозначены через ад,...,жп. Однако в теории булевых функций важным является не только зависимость функции от переменных, но и так называемая существенная зависимость функции от переменной. Прежде чем дать строгое определение этому понятию, посмотрим на “степень” зависимости функции от переменных на примерах функций /Дад, яд/• • •,/и(яд, яд)-
Функция /х(яд,яд) есть константа 0. Для этой функции любое изменение значений переменных не влечет за собой изменения значения функции. В этом смысле переменные ад, ад можно было бы назвать несущественными для функции /1(яд,яд). Аналогичное замечание следует сделать и по поводу функции /2(^1, ад).
Несколько иная ситуация имеет место для функции /з(яд,яд). Поскольку значения функции /з(яд,яд) совпадают со значениями переменной яд, значения переменной ад являются существенными для функции /з(яд,яд). Напротив, значения переменной яд никак не влияют на значения функции /з(яд,яд). Таким образом, переменную яд следует считать несущественной для функции /з(яд,яд).
Аналогичные рассуждения можно провести для функций /4, /5, /б и прийти к выводу, что переменная яд является существенной для функции /5 (яд, яд) и несущественной для функций /Дад, яд), /б(яд,яд), а переменная яд — существенной для функций /Дад, яд), /б(яд,яд) и несущественной для функции fs^i^x^.
Обратимся теперь к конъюнкции /Дад, ад). Нетрудно заметить, что обе переменные яд, яд являются для нее существенными. В самом деле, из равенств /7(0,1) = 0, /7(1,1) = 1 следует, что при фиксированном значении 1 переменной яд изменение значения переменной яд влечет за собой изменение значения функции. Следовательно, переменная яд является существенной для функции /Дад,х^. Аналогичным образом, рассматривая наборы (1,0) и (1Д), убеждаемся в существенности переменной х^.
Проверьте, что оставшиеся функции /3(^1, ад),..., /и(ад, х^ также существенно зависят от обеих переменных.
Приведем теперь строгое определение существенной зависимости функции от переменной.
Функция /(яд,..., яд,...,жп) существенно зависит от переменной х^ если имеются такие значения од,..., Щ-i, o^y^... ,ап переменных ЯД, ... , Xi-Y, ЯД+1, . . . ,Хп, ЧТО
/(бЦ, . . . , Щ — 1,0, Щ-|-Х, . . . , Нп) ?^ /(^1, • • • 1 ^i — li 1, ^г+1, • • • , ^п) •
Приведенному определению существенной зависимости можно придать несколько иную форму.
Функция /(яд,...,х^...,хп) существенно зависит от переменной Xi, если имеются такие значения qy,..., щ_1, Щщ, • • • ^п переменных xi,, x^y, x^y,... ,хп, что функция одной переменной J(ai,..., Qi-i, Xi, a^Y,... ,хп) не является константой (т.е. совпадает С ОДНОЙ ИЗ функций Xi ИЛИ Xi).
Если функция /(яд,..., хп) существенно зависит от переменной Xi, то переменная Xi называется существенной переменной функции /(яд,..., хп). В противном случае переменная Xi называется несущественной или фиктивной переменной функции J(xy,...
Из определения существенной зависимости видно, что при вычислении значений функции реально используются лишь значения существенных переменных. В связи с этим возникает желание освободиться от “ненужных” фиктивных переменных. Если, например, известно, что существенными переменными булевой функции /(яд,...,хп) являются переменные яд, • • •, хт (т < п), а переменные жт+х,..., хп фиктивны, то избавиться в функции /(яд,...,хп) от фиктивных переменных жт+1,..., хп можно различными способами. Один из них состоит в том, чтобы значения функции / рассматривать только на наборах (пх,..., ап), у которых ат^ = ... = ап = 0. Это соответствует подстановке константы 0 на места переменных xm+Y,...,xn: J(xy, ... , xm,0,..., 0). При другом способе переменным жт+х,... ,хп придают значения какой-либо из переменных xy, ..., хт, например, переменной яд. Как говорят в таких случаях, переменные хт^т • • ...,хп отождествляют с переменной xy*. /(xy, ..., хт, xy, ..., xy). Возможны, разумеется, и любые комбинации подобных способов.
На практике нередко встречается обратная задача. Имеется функция p(^i,..., хт) и требуется “добавить” к ней фиктивные переменные жт+1,..., хп. В этом случае искомую функцию /(xy,..., хп) можно определить равенством
/ (зд,..., хт, xm_|-i,..., хп) = g^XYi • • •, зст), (2)
которое выполняется при любых значениях переменных XY,...,xn. Вообще, этот прием показывает, что функцию д(ач,...,хт) можно считать зависящей от любого числа дополнительных фиктивных переменных. При этом важно лишь помнить, что с функциональной
точки зрения переход от функции д к функции /, даваемый равенством (2), приводит к появлению нового объекта: функция / определена на множестве Вп. тогда как функция д — на множестве Вт.
Приведенные рассуждения показывают, что введение и удаление фиктивных переменных можно осуществить сравнительно простыми средствами, практически “даром”. Это особенно важно при введении фиктивных переменных. В связи с этим в теории булевых функций иногда для функции указывают лишь те переменные, от которых она зависит существенно. При этом предполагается, что от всех остальных переменных, которые встречаются в дальнейших построениях, данная функция зависит фиктивно.
Следует отметить, что при введении и удалении фиктивных переменных необходимо проявлять известную осторожность. Пусть, например, имеется булева функция ^(ж1,Ж2,жз) и мы хотим введением фиктивных переменных получить из нее булеву функцию, зависящую от переменных яд,... ,£5. Довольно просто сообразить, что достичь этого можно различными способами. Прежде всего, напрашивается “естественный” способ введения: добавляемые переменные яд, яд фиктивны, а искомая функция /1(я71,..., х^ определяется равенством
/1(ж1,ж2,жз,ж4,ж5) = д(ж1,ж2,ж3). (3)
Однако можно поступить иначе: к переменным функции д добавить две новые переменные так, чтобы “старые” переменные яд, яд, хз функции д для вновь определяемой функции /2(^1,... ^х^ оказались соответственно второй, четвертой и пятой переменными. Этот вариант введения фиктивных переменных дается равенством
/2(Ж1,Ж2,Ж3,Ж4,Ж5) = д(ж2,ж4,ж5). (4)
Разумеется, на этом пути введения фиктивных переменных существует еще несколько различных функций /фяд,..., яд), каждая из которых определяется выбором трех различных переменных яд, xq, хТ из множества {ад,..., ад} и использованием в равенствах (3), (4) соответствующей функции g(xpi xq, хт\
По традиции, сложившейся в отечественной школе дискретной математики, булевы функции рассматриваются с точностью до несущественных переменных. Это означает, что наряду с любой булевой функцией / считаются одновременно заданными все функции, которые получаются из / введением или удалением несущественных переменных. Иногда такие функции называют равными, хотя, строго говоря, они различаются уже как функции, имеющие различные количества переменных. Мы в дальнейшем не будем употреблять термин “равные” в этом смысле. Тем не менее равенства типа (3) или (4) будут использоваться.
Весьма распространенным способом введения фиктивных переменных является способ введения с помощью селекторных функций.
Пусть мы имеем булеву функцию д от т переменных и хотим получить из нее функцию /, удовлетворяющую тождеству (2). Тогда функцию / можно определить так:
,..., ж„) = з(е"(ж1,..., жи),..., е” (жх,...,Щ). (5) Преимущество этого способа состоит в том, что переменные хт^\,... ..., жп не появляются “ниоткуда”, как это происходит при переходе от правой к левой части равенства (2). Наряду с переменными жх,..., хт они изначально присутствуют в правой части равенства (5). Поэтому данный способ введения фиктивных переменных с математической точки зрения представляется более корректным. К недостаткам его можно отнести то, что среди “исходных” булевых функций селекторные функции присутствуют далеко не всегда.
УПРАЖНЕНИЯ
Найдите существенные и фиктивные переменные функций ^1(^1, Ж2, ж3) и ^2(^1, Ж2, жд), заданных двоичными наборами (10100101) и (00010111).
Пусть функция /(ж1,...,жп) задана двоичным набором (щ ... а2»-1 щ»-' + | .. л/^^^^ а функция д(жх,..., жп) — набором (й2и • • • а^-г^а^-г ... щ) • Как соотносятся существенные и фиктивные переменные функций / и д?
Назовем булеву функцию симметрической, если она принимает одинаковые значения на любых двух наборах, содержащих одинаковое количество единичных компонент. Докажите, что всякая симметрическая булева функция, отличная от константы, существенно зависит от всех своих переменных.
§ 4. Представление булевых функций формулами
Табличный способ является универсальным способом задания булевых функций. В нем в самой простой форме отражена функциональная зависимость значений функции от значений аргументов. Однако в математике часто возникает необходимость установить функциональные связи между значениями функции для нескольких наборов значений аргументов либо между значениями различных функций. Табличный способ для этих целей, как правило, не подходит. Обычно для этого используют формулы различных типов.
Самые простые формулы обобщают идею перехода от значений аргументов к значениям функции и допускают использование других функций в качестве аргументов. Так, например, обращаясь к элементарной алгебре, видим, что формула
(жх + ж2) • ж2 + жх • ж3, (6)
составленная из символов переменных жх,Ж2,жз и символов функций + и •, указывает на определенную последовательность при вычислении функции, представленной этой формулой: например, сначала вычисляем жх + Ж2, затем (жх + Ж2) • Ж2, далее жх • Ж3 и, наконец, (жх + Ж2) • Ж2 + Ж1 • Ж3. При этом функции + и • в формуле (6) считаем известными, “элементарными”, а формула (6) лишь организует процесс вычисления значений функции, представленной этой формулой, исходя из значений переменных жх, Ж2, жз и используя заданные функции + и •.
Переходя к булевым функциям, предположим, что имеется некоторое непустое множество F булевых функций. Мы хотим ввести понятие формулы, составленной из символов функций множества F (как говорят, формулы над множеством F). Сразу отметим, что нам не важно, какие именно функции входят в множество F и как они заданы. Нам важно лишь то, что каждая функция из F имеет собственное “имя” — индивидуальное обозначение.
С помощью индукции (по построению) определим понятие формулы над F. Пусть / есть обозначение функции от п переменных из множества F, а жх,..., хп — символы переменных. Тогда выражение /(ж1,...,жп) считаем формулой над F. Пусть, далее, g есть обозначение функции от т переменных из множества F, а Ах, • • •, Ат — либо уже определенные формулы над F, либо символы переменных (не обязательно различные). Тогда выражение g(Ai,..., Ат) считаем формулой над F.
Пусть, например, F есть множество булевых функций, состоящее из функций ” (отрицание), • (конъюнкция), V (дизъюнкция), ф (сложение по модулю 2), —> (импликация), | (штрих Шеффера). Тогда согласно приведенному выше определению следующие выражения будут являться формулами над F;
ж3,(ж2 V жх) • ж4,(ж2 • (ж3 • жх)) Ф (ж3 V (жх • ж5)),
((ж3 • Ж2) -4- (жх • Ж4)) I Жх, ((ж4 | Ж2) -4- (ж3 Ф Ж5)) ((жТ V Ж2) -4- Ж4)
(чтобы не усложнять вид формул, мы не пишем скобок при использовании отрицаний от переменных).
Понятно, что формулы предназначены для задания булевых функций. Как же определить функцию, задаваемую (или, как говорят, реализуемую) конкретной формулой? Для этого надо вновь обратиться к определению понятия формулы над F и параллельно этому определению ввести определение функции, реализуемой формулой над F.
Если / есть обозначение функции от п переменных из F, то формула /(жх,...,жп) реализует ту самую функцию от п переменных, обозначением которой служит f. (Этот пункт определения может показаться несколько туманным или даже содержащим противоречие.
Однако следует, видимо, еще раз обратить внимание на то, что функция — это отображение одного множества в другое, если угодно, алгоритм или процесс. Тогда как / есть всего лишь обозначение этой функции, ее “имя”.)
Пусть теперь д — обозначение функции от т переменных из F, а Лх,..., Ат — формулы над F либо символы переменных. И пусть каждому выражению Ai, которое представляет собой формулу над F, уже сопоставлена функция hi, реализуемая этой формулой Ai. Если же выражение Ai представляет собой символ переменной х^ то сопоставим ему тождественную функцию hi(xj\ значения которой совпадают со значениями переменной Xj. Тогда формула g(Ai,..., Ат) реализует функцию
^(^l ? • • • ?•(7)
Сделаем несколько замечаний по поводу определения функции (7). Во-первых, по понятным техническим причинам мы не выписываем переменные, от которых зависят функции hi,..., hm: у каждой функции hi могут быть свои переменные, не совпадающие, вообще говоря, с переменными других функций h^.
Во-вторых, мы оставили в стороне вопрос о том, что же представляет собой функция (7). Мы не хотели бы приводить здесь точные, но громоздкие определения. Вместо этого обратимся к примерам.
По-видимому, все читатели представляют себе, как вычисляются значения функции
если функции д, hi,..., hm предполагаются известными: для любого двоичного набора (ai,..., ап) вычисляем значения
^1 (^11 • • • 1 ^п) ? • • • 1 ^т (^11 • • • 1 ^п) 1
образуем двоичный набор
(^1 (^1 77, * * * 1 ^т (^1 77 ^п))
и, используя функцию д, вычисляем ее значение на этом наборе.
Чуть более сложной является формула
g(hi(x4,x^,x3,h2(x3,x2,xi^.
Здесь по заданному двоичному набору (ai, ^2, аз, ^4) необходимо сначала вычислить значения hi(a4,ai) и /12(^3, ^2, ^1), затем образовать двоичный набор
(Ма4, nJ, пз, ^2(^3, п2, ^1))
и найти значение функции д на этом наборе.
На этом примере уже хорошо видны те трудности, которые поджидают нас при определении функции (7): все они связаны с тем, что переменные в функциях hi,..., hm могут быть “перемешаны” каким угодно образом.
Чтобы облегчить изложение некоторых результатов, требующих для своего доказательства анализа сложных формул, нередко поступают следующим образом. Пусть, к примеру, требуется проанализировать формулу (7), в которой функции hi,...,hm зависят от различных переменных. Допустим, что ад,...,жп суть все переменные, от которых зависит хотя бы одна из функций hi,..., hm. Если функция Кг зависит от переменных жд^,..., ж^, то рассмотрим функцию Л'(ж1,..., жп), которая получается из функции h^x^ ..., Ж&.) введением недостающих фиктивных переменных из множества {яд,... ..., жп}:
/г'(жь ... ,ж„) = ht(xkl,.. .,xki\
Понятно, что формулы (7) и
■ ■ ■ ,Щ, ■ ■ ■ , h'm^Xi,. .. ,ж„))(8)
реализуют одну и ту же функцию. Вместе с тем гораздо предпочтительнее рассматривать формулу (8), нежели исходную формулу (7). Формально при совершении подобных замен мы отказываемся от функций hi,..., hm, переходя, вообще говоря, к другим функциям Ыг,..., h*m. Однако вспомним, что мы условились рассматривать функции с точностью до фиктивных переменных. В частности, наряду с функциями hi,..., hm можно считать заданными и функции Ыг,..., h*m. Собственно, именно подобные технические трудности, возникающие при анализе сложных формул, и являются одной из основных причин для принятия нами соглашения о возможности рассмотрения функций с произвольным числом фиктивных переменных.
УПРАЖНЕНИЯ
Пусть функция /(жх,Ж2,жз) задается двоичным набором (01101001), gi^xi, х^ = Ж1 -4 х2, g^xi, х^ = Xi V х2. Определите, чему равны функции
/11(Ж1,Ж2) = /(91(Ж1, х2), 92^x1, х2),х2),h2(xi,x2,x3) = Kg2(xi, ж2),ж3, gi(ж2,Ж1)).
Эквивалентность формул
Из элементарной алгебры известно, что одну и ту же функцию можно задать различными формулами. Так, например, формула (6) задает ту же функцию, что и формула
Х1 • (ж2 + Хз) + ж^ •(9)
Этот факт обычно выражают в виде высказывания “формула (6) эквивалентна формуле (9)”.
Аналогично обстоит дело и в теории булевых функций: формулы Ф и Ф называются эквивалентными, если они реализуют одну и ту же булеву функцию. Мы не вводим специального знака для обозначения эквивалентности формул. Если формулы Ф и Ф эквивалентны, то будем записывать это в виде Ф = Ф.
Для функций от одной и двух переменных, определенных в §2, можно выписать большое число связывающих их эквивалентностей. Ниже приводятся лишь наиболее употребительные из них.
1 = ж- 0 = ж- ж = жфж = 0.
О = ж V 1 = ж V.T = х Ч х = 1.
x = x- x = xVx = x- l = xVO = xBO = x.
жф1 = ж^0 = ж|ж = ж.
х о у = у о х, где о есть любая из функций •, V, ф, | (коммутативность функции о).
(х о у) о г = х о (у о г), где о есть любая из функций •, V, ф (ассоциативность функции о).
х • (у V г) = (х • у) V (х • г) (дистрибутивность конъюнкции относительно дизъюнкции).
х V (у • г) = (х V у) • (х V г) (дистрибутивность дизъюнкции относительно конъюнкции).
х • (у ф г) = (х • у) ф (х • г) (дистрибутивность конъюнкции относительно сложения по модулю 2).
х • у = х V у, х V у = х • у (правила де Моргана).
х V (х • у) = х • (х V у) = х (правила поглощения).
ж ф у = (ж • у) V (ж • у) = (ж V у) • (ж V у),
ж V у = ((ж • у) © ж) ф у = х -Ф у, ж у = ж V у = ((ж • у) ф ж) ф 1, ж I у = ЖЦ.
Справедливость эквивалентностей 1-12 можно проверить непосредственно, используя табл. 2 и табл. 3.
Чтобы несколько упростить написание формул, часть скобок обычно опускают. При этом руководствуются следующими правилами. Внешние скобки у формул не ставятся. При использовании отрицания скобки также не ставятся (читатель мог заметить, что мы уже применяли эти правила). Далее, свойства ассоциативности 6 позволяют при многократном применении одной и той же функции •, V или ф опускать внутренние скобки. Если формула содержит символы функций •, ф, V, —>, |, то при отсутствии дополнительных скобок сначала выполняют конъюнкцию, затем сложение по модулю 2, далее дизъюнкцию и, наконец, импликацию или штрих Шеффера. Например, формулу
X • у ф 2 —> у • Z V X
следует понимать так:
^x-y)®z)((rz)vz).
Применяя подходящие эквивалентности 1-12, докажем эквивалентность формул
(ху V xz) Ф ((у ^ ^) ^ ху) и xyz Ф у Ф Z.
Подформулу ху V xz первой формулы преобразуем с использованием второй из эквивалентностей 12:
ху V xz = ху • xz ф ху ф xz.
Применяя коммутативность конъюнкции и свойство х • х = 0, получаем
ху • xz Ф ху Ф xz = ху Ф xz.
Таким образом, ху V xz = ху ф xz.(10)
При рассмотрении второй части (?/ —> г) —> ху первой из исходных формул дважды применяем третью из эквивалентностей 12:
(у -4 z) -4 ху = (у V z) -4 ху = у V z V ху.
Формулу у V z упрощаем с помощью правила де Моргана и первой из эквивалентностей 3:
у У Z = yz.
Следовательно, получаем
(у 4 н- ху = yz V ху.
В правой части этой эквивалентности меняем местами х и у (коммутативность конъюнкции), “выносим за скобку” у (применяем эквивалентность 7 справа налево), меняем местами z и х (коммутативность дизъюнкции) и используем затем вторую из эквивалентностей 12:
yz\/ ху = (7 V z)y = (xz ф X ф z)y.(11)
Пользуясь дистрибутивностью конъюнкции относительно сложения по модулю 2 и складывая по модулю 2 выражения (10) и (11), получаем, что первая формула эквивалентна формуле
ху Ф xz Ф xyz Ф ху Ф yz.
Заменяя в ней ж, у, z на ж ф 1, 2/ Ф 1, г ф 1 и применяя дистрибутивность конъюнкции относительно сложения по модулю 2, приходим к формуле
ху ф XZ Ф xyz ф ху ф yz = ху ф X ф xz ф z ф xyz Ф ху ф
^yz^y^xy^y^yz^y = xyz Фху ф XZ ф X фу ф Z. (12)
Нетрудно убедиться в том, что вторая формула, xyz®y ф z, также приводится к виду (12).
2 С.С. Марченков
УПРАЖНЕНИЯ
Используя эквивалентности 1-12, докажите эквивалентность следующих формул:
(х ®yz) (х (у z)) и X н- ((у н- z) -> ж);
(х V yz) н- ((ж н- у) -> ((у V z) -> ж)) и (ж н- у) -> (у н- ж).
Выясните, при каких п (п ^ 3) эквивалентны формулы
Ж1 (ж2(ж3(ж„-1 -> ж„). . . )),
(. . . ((Ж1 Н- Ж2) Жз)Ж„-1) Хп.
Замыкание. Замкнутые классы
Одной из центральных проблем в теории булевых функций является проблема выразимости. В общем виде ее можно сформулировать следующим образом. Имеются некоторое непустое множество F булевых функций и булева функция /. Спрашивается, выразима ли функция / через функции множества F?
Чтобы дать ответ на поставленный вопрос, необходимо сначала уточнить, что понимается под выразимостью функции через другие функции. Самой распространенной формой выразимости для булевых функций является выразимость с помощью формул. Более точно, будем говорить, что булева функция / выразима через функции множсества F, если существует формула над F^ которая реализует функцию f. Совокупность всех функций, выразимых через функции множества F (т.е. реализуемых формулами над F\ обозначим через [Е].
Часто операцию порождения одних булевых функций другими с помощью формул называют операцией суперпозиции функций. Соответственно этому множество [Е] называют замыканием множества F относительно (операции) суперпозиции или просто замыканием F. Из определения легко усматриваются следующие свойства замыкания.
F содержится в [Е].
[[F]] =
Если Ei содержится в F2, то [Ei] содержится в [F2].
Если для множества булевых функций F выполняется равенство F = [Е], то F называют замкнутым множеством или замкнутым классом.
Рассмотрим некоторые примеры замкнутых классов. Прежде всего, очевидно, что замкнутым классом является множество Р^ всех булевых функций. Следующий наш пример связан с селекторными функциями. Обозначим через Uqi множество всех селекторных функ-
ций еДжх,..., жп) (1 г п, п = 1,2,...). Чтобы убедиться в том, что Uoi образует замкнутый класс, достаточно проанализировать “первый” шаг в определении формулы над Uoi, когда в селекторную функцию еДжх,..., хп) на места переменных жх,...,жп подставляются выражения Ai,...,An, которые являются либо селекторными функциями, либо символами переменных. Понятно, что значения функции еДАх,..., Ап) будут совпадать со значениями выражения At. Однако значения Ai также совпадают со значениями некоторой переменной. Следовательно, еДАх,..., Ап) — селекторная функция.
Обозначим через Со множество всех булевых функций (от любого числа переменных), тождественно равных 0. Очевидно, что суперпозициями функций, тождественно равных 0, можно получить лишь функцию, тождественно равную 0. Поэтому Со — замкнутый класс. Аналогично получаем, что замкнутым классом является множество Ci всех булевых функций, тождественно равных 1.
Пусть То есть множество всех булевых функций /Дх,..., хп), которые, как говорят, сохраняют константу 0, т.е. удовлетворяют равенству /(0,..., 0) = 0. Покажем, что То — замкнутый класс. Для этого так же, как и для класса Uoi, достаточно проверить, что функция g(yi,..., ут) принадлежит классу То, если g(yi,..., ут) реализуется формулой /(Ах,..., Ап), в которой / — функция из То, a Ai,..., Ап — либо функции из То, либо символы переменных. Поскольку переменную можно рассматривать как тождественную функцию (из класса То), то так же, как и в § 4, все выражения Ах,..., Ап можно считать функциями от переменных yi,..., ут, т.е.
/(Д1, • • • , Ап) = /(//-х (щ, . . . , Ут) 7 • • • 7 hn (t/X, . . . 7 Ут)) 7
где функции hi,... ,hn принадлежат классу Tq. Теперь легко убеждаемся в принадлежности функции д классу То: согласно определению функций hi,... ,hn имеем
ЛДО,...^) = ... = hn(C---,0) = 0,
а согласно определению функции / имеем
/(0,...,0) = 0.
Подобным образом можно показать, что замкнутым классом является множество Ti всех булевых функций, сохраняющих константу 1, т.е. функций f(xi,...,хп), удовлетворяющих равенству
Разумеется, далеко не каждое множество булевых функций представляет собой замкнутый класс. В качестве примера рассмотрим множество Uот всех “антиселекторных” функций ёДжх,..., хп), где
ё"Щ. ..,£;,...,£„) = Xi-
В самом деле, в замыкание [L7qi] по определению должна входить функция, реализуемая формулой ё}(ё}(ж)). Нетрудно видеть, что эта функция совпадает с функцией ^(ж). Однако е|(ж) не содержится в множестве Uqi. Значит, Uqi не является замкнутым классом.
С понятием замыкания тесно связано понятие полноты. Пусть R — замкнутый класс, a Q — система функций из R. Говорят, что система функций Q полна в классе R, если [Q] = R. Когда R совпадает с Р^ слова “в классе Р^ обычно опускают.
Построение нетривиальных полных систем функций мы отложим до следующего параграфа. А пока докажем простое и вместе с тем полезное утверждение.
Теорема 1. Пусть система булевых функций Q полна в замкнутом классе R, Р — некоторое множество функций из R и любая функция системы Q реализуется формулой над Р. Тогда множество Р также полно в классе R.
Доказательство. Возьмем произвольную функцию / из класса R. По условию теоремы ее можно реализовать некоторой формулой Ф над Q. В свою очередь каждая функция из Q, которая участвует в построении формулы Ф, может быть реализована формулой над Р. Заменим в формуле Ф вхождение каждого символа функции из Q соответствующей формулой над Р. Мы получим формулу Ф' над Р, которая, как легко понять, реализует ту же самую функцию /. Теорема доказана.
Если система функций Q полна в замкнутом классе Я, то говорят также, что система Q порождает класс R. а класс R порождается системой Q.
Из определения замыкания видно, что замкнутый класс потенциально может содержать бесконечное число булевых функций. Разумеется, при задании такого класса мы не можем перечислить все входящие в него функции. В связи с этим хотелось бы иметь некоторый финитный (конечный) способ описания замкнутых классов. Один из таких способов подсказывается понятием порождающей системы. Именно, назовем замкнутый класс R конечно порождаемым, если существует конечная система функций Q этого класса, которая порождает R.
Если класс R конечно порождаем, а конечная система Q порождает класс R, то путем удаления функций из системы Q можно получить наименьшую по числу функций систему Q*, которая все еще порождает класс R. Такие минимальные системы Q* называются базисами класса R. Отметим (пока без доказательства), что для одного и того же класса R, отправляясь от различных порождающих систем Q, можно прийти, вообще говоря, к различным базисам, содержащим даже различные количества функций.
УПРАЖНЕНИЯ
Покажите, что замкнутыми классами являются объединение С классов Со и Ci, объединение Со классов Cqi и Со, объединение Ci классов Cqi и Су.
Выясните, являются ли замкнутыми классами следующие множества функций:
{жх • ... -жп, п = 1,2,...};
{Ж1 Ф ... Ф жп, п = 1, 2,... };
{0, жх V ... V жп, п = 1,2,...}.
Верно ли, что объединение двух замкнутых классов всегда является замкнутым классом?
§ 7. Разложение булевой функции по переменной
Следующее утверждение имеет фундаментальное значение для всей теории булевых функций.
Теорема 2 (о разложении функции по первой переменной). Для любой булевой функции Дху,...,хД справедливо представление
7Щ -.. ,ж„) = Ж1 • /(1,ж2,... ,ж„) VS1 • /(0,ж2, ■ ■ ■ ,ЖП).(13)
Доказательство. Возьмем произвольный двоичный набор а = (ах,..., ап) и сравним значения левой и правой частей равенства (13) на этом наборе. Слева мы имеем значение ф(Д. Если щ = 0, то выражение щ • /(1, а2,..., аД из правой части обращается в 0. Поэтому правая часть будет равна
«1 • 7(0, а2,..., а„) = 0 ■ 7(«ь «2,..., а„) = 1• 7(a) = 7(a).
Аналогичным образом рассматриваем другую возможность, когда ai = 1. Теорема доказана.
Разумеется, в теореме 2 вместо первой переменной с равным успехом можно выбрать любую другую переменную.
Теорема 2 имеет целый ряд важных следствий. Во-первых, если при 77 ^ 2 ее применить далее к функциям /(1, Ж2,..., хи\ /(0, Ж2,... ... ^хД и переменной Ж2, то получим соотношение
7(^1,... ,хД = Ху • Ж2 • /(1,1,ж3, ...,хпДхгх2- /(1,0, ж3,...,жп)V
V ху • ж2 • /(0,1, ж3,..., хД V ху • ж2 • /(0, 0, ж3,..., жп).
Вообще, если ввести обозначения ж1 = ж, ж0 = ж и рассуждать далее по индукции, то получим следующее утверждение.
Следствие 1 (о разложении функции по первым т переменным). Для любой булевой функции /(жх,...,жп) и любого т (1 ^
< т < п) имеет место представление
=\/ж?1 •... • ж^ • /(<71,... ,ат,хт+1,... ,хп).
(°"1 v^m)(14)
Выражение (cri,..., сгт) под знаком дизъюнкции в формуле (14) означает, что данная формула представляет собой дизъюнкцию 2т слагаемых (по числу всех двоичных наборов длины т), каждое из которых имеет вид
Ж1 • . . . • X™ • f (<71, . . . , СГт, Хт4-1, • • • , Хп), где х^ должно быть заменено на ^, аж- — на х^.
Особенно интересным следствие 1 оказывается при т = п. В этом случае каждое дизъюнктивное слагаемое в формуле (14) имеет вид хр • ...-х^ • /((71,.. .,апу(15)
Если /(cri,..., сгп) = 0, то слагаемое (15) равно 0. Поэтому в формуле (14) его можно опустить (исключение составляет единственный случай, когда функция / тождественно равна 0; тогда формула (14) вырождается в константу 0). Если же f(ai,..., ап) = 1, то вместо формулы (15) можно написать эквивалентную формулу жД •... • яДп. Таким образом, мы приходим к следующему утверждению.
Следствие 2 (о разложении функции по всем переменным). Если булева функция f(xi,..., хп) не равна тождественно 0, то имеет место представление
= у жГ-.-.-ж^.(16)
/((П,...,(тп) = 1
Равенство f(ai,..., ап) = 1 в формуле (16) говорит о том, что в формуле (16) присутствуют лишь те дизъюнктивные слагаемые жД • ... • яДп, для которых ф(о"1,..., сгп) = 1.
Правая часть формулы (16) носит название совершенной дизъюнктивной нормальной формы (сокращенно СДНФ). Следствие 2 показывает, что любую не равную тождественно 0 булеву функцию можно представить в некоторой стандартной форме — СДНФ, которая представляет собой дизъюнкцию конъюнкций одинаковой длины, составленных из переменных яд,...,хп и их отрицаний. Для функции, тождественно равной 0, в качестве СДНФ рассматривают, например, формулу ЯД • ЯД.
СДНФ относится к более общему классу формул над множеством {х. ху, х V у^ которые носят название дизъюнктивных нормальных форм (сокращенно ДНФ). В отличие от СДНФ в произвольной ДНФ, которая также представляет собой дизъюнкцию конъюнкий, конъюнкции могут состоять из различных переменных и иметь различную
длину. Так, первая из формул
ху V ху V ху, xV у
есть СДНФ, вторая — ДНФ. Обе формулы реализуют одну и ту же функцию х —> у. На этом примере видно, что ДНФ булевой функции может быть гораздо проще, чем ее СДНФ. Этим обстоятельством, а также сравнительной простотой строения ДНФ, объясняется то внимание, которое уделяется изучению ДНФ в теории булевых функций.
Следствие 2 содержит еще одну важную информацию о классе Р> всех булевых функций. Именно, формула (16) показывает, что каждую не равную 0 булеву функцию можно представить формулой над множеством функций {ж, ху, xV у}. Поскольку, как отмечалось, О = х • х, мы получаем еще одно следствие из теоремы 2.
Следствие 3. Система функций {х, ху, х V у} полна в классе Р2.
Используя следствие 3 и теорему 1, докажем полноту следующих систем функций:
Ц,жу}, {ж,жУу}, {1,жфу,жу}, {ж I у}.
Полнота первых двух систем вытекает из полноты системы {ж, ху, х V у}, теоремы 1 и правил де Моргана (см. п. 10 в §5), согласно которым
х V у = х • у, х • у = х V у.
Полнота третьей системы следует из полноты системы {ж, ху}, теоремы 1 и соотношения х = х ф 1. Полнота четвертой системы следует из полноты системы {х, ху} и соотношений
ж = ж|ж, ху = (ж I у) I (ж I у).
УПРАЖНЕНИЯ
Разложите по переменным х, г функцию хуг В xz В у В z В 1.
Постройте СДНФ для функции ж V yz.
Докажите полноту систем функций
{х,х—>у},{0,х^у},{0, х ф у ф 1, х V у}, }l,x,xyV xz\/ yz}.
§ 8. Двойственность. Принцип двойственности
Каждому, кто знакомится с булевыми функциями, довольно быстро приходит в голову следующая мысль. Элементы 0, 1 множества В в общем-то равноправны. А что будет, если поменять их местами?
Эту мысль можно оформить вполне строгим образом и получить новое важное понятие. Именно, будем говорить, что функция g(xi,... ...,жп) является двойственной к функции /(яд,...,жп), если
дЦу,... ,хп) = /(жь ... ,хп). (17)
Это равенство следует понимать так. Чтобы найти значение функции д на наборе (сд,..., ап\ необходимо сначала образовать “противоположный” набор (ai,... ,ап), затем найти значение f(ai,... ,ап) и в заключение инвертировать его с помощью отрицания.
Функция, двойственная к функции /(яд,...,хп\ обозначается через f*(xi,..., хп\ Из определения (17) двойственной функции и тождества х = х нетрудно вывести, что
Таким образом, двойственные друг другу функции образуют пары (из приводимых далее примеров будет видно, что возможны случаи, когда /* = /). В табл. 4 приведены некоторые пары двойственных функций.
Таблица 4
/
Г
0 е7(ж1, ...,хп)
X
ху
X ® у
X ^У
Ж 1 У
1 е7(ж1,... ,хп) X
х V у хфуф!=хфу х\/у = ху = у^-х xV у = ху
Важную роль в теории булевых функций играет следующий принцип двойственности.
Если функция / реализуется формулой Ф, составленной из функций д^.-.^д^ то двойственная функция J* реализуется формулой Ф*, которая получается из формулы Ф заменой каждого вхождения функции gt (1 ^ г < т) соответствующей двойственной функцией д*.
Чтобы убедиться в справедливости принципа двойственности, достаточно рассмотреть самый простой этап в определении формул, когда
. ,жи) = g0(gi(xi,. • .,£„),... ,5ТО(Ж1,... ,хп)).(18)
Согласно исходному определению двойственной функции имеем
Лжь • ..,хп)= g0(gi(xi,... ,хп),.. .,gm(xi,.. .,$„)).
Заменим в правой части этого равенства каждую формулу ^(xi, • • • ..., жп) эквивалентной формулой gi(xi,..., жп):
Г(ЖЬ • •■,жп) = <7О(51Щ ... ,ж„),... ,5т(жь...,$„)).
Функция gi(5ц,..., хД по определению есть функция g*(xi,..., хД. Поэтому
Г^!,...,ж„) = 5О(51(Ж1,... ,ж„),.. -,g*m(xi,.. .,хпу.
Вновь по определению 9o(gi, ■ ■ ■ ,9т) есть дц(дУ ..., д^У). Окончательно получаем
/Щ1, • • •, жп) = ^(я^Щ,..., жп),...,£4(ж1,..., жп)).
Покажем на примерах, как работает принцип двойственности. При этом будем пользоваться двойственными функциями из табл. 4:
(xyz V xyz V хуД* = (ж V у У Д(х V у V Д(х V у V г),
(xyz Ф (yz V хуДД = (х V у V Д Ф (у V Д(х V у V Д Ф 1,
((ж -у у^х ®z)® (уг н- xz^y =
= (у -4- х V z —> ж) ф (х V z) —> (у V г) ф 1.
На практике принцип двойственности чаще всего применяют следующим образом. Если уже установлено некоторое утверждение о булевых функциях /, д.... и множествах булевых функций F, G,..., в котором фигурируют лишь понятия, базирующиеся на формулах, то по принципу двойственности будет справедливо аналогичное утверждение о булевых функциях /*,#*,... и множествах булевых функций F*, G*,... . При этом под F* понимается множество всех булевых функций, двойственных к функциям из F.
Так, например, доказав дистрибутивность конъюнкции относительно дизъюнкции (см. п. 7 из §5), на основании принципа двойственности мы можем заключить о справедливости свойства дистрибутивности дизъюнкции относительно конъюнкции (см. и. 8 из §5). Аналогичное утверждение имеет место для двух правил де Моргана (см. п. 10 из §5). Далее, на основе дистрибутивности конъюнкции относительно сложения по модулю 2 (см. п. 9 из § 5) можно получить новую эквивалентность
х V (у Ф z Ф 1) = (х V у) Ф (х V Д Ф 1.
С использованием принципа двойственности, теоремы 2 и ее следствий можно доказать несколько интересных утверждений. Во- первых, имеет место следующий аналог теоремы 2.
Теорема 2'. Для любой булевой функции Дх^ ... ^ хД справедливо разложение
.. ,ж„) = (Ж1 V /(0,ж2,... ,Ж„)) • (Ж1 V /(1,Ж2,... ,Ж„)).
Далее получаем разложение по п переменным.
Следствие 2'. Если булева функция f(xi,... ^хп) не равна тождественно 1, то имеет место представление
/(Ж1,... ,ж„) =&(i"1 V...V<").
Правая часть этой формулы носит название совершенной конъюнктивной нормальной формы (сокращенно СКНФ). Так же, как и в случае СДНФ и ДНФ, СКНФ относится к более широкому классу конъюнктивных нормальных форм (сокращенно КНФ), которые представляют собой конъюнкции дизъюнкций переменных и их отрицаний.
УПРАЖНЕНИЯ
Докажите, что функция /(яд,...,хп) существенно зависит от переменной х^ в том и только том случае, когда от переменной х^ существенно зависит функция /Дяд,..., хп\
Выясните, верно ли, что СКНФ для булевой функции / можно построить следующим образом: сначала построить СДНФ для функции /*, а затем в полученной СДНФ заменить V на • и • на V.
§ 9. Полиномы Жегалкина
Как установлено в § 7, система ^1, х ® у, х • у^ полна в классе Р^. Это означает, что любую булеву функцию можно представить в виде формулы над множеством функций {1, х ф у, х • yY Преобразуем эту формулу, используя следующие эквивалентности из § 5: коммутативность сложения по модулю 2 и конъюнкции (умножения), дистрибутивность конъюнкции (умножения) относительно сложения (и. 9 слева направо),
ж-ж = х-1=жф0 = х, х - 0 = х®х = 0.
Так же, как в элементарной алгебре, после выполнения этих преобразований мы получим формулу, которая имеет вид полинома: она представляет собой сумму по модулю 2 слагаемых вида х^ •... • xts и, быть может, константы 1 (в случаях, когда реализуемая полиномом функция тождественно равна 0 или 1, сумма вырождается в одно слагаемое, 0 или 1). Эта формула носит название полинома Жегалкина. Общий вид полинома Жегалкина для функции от п переменных может быть записан следующим образом:
Здесь £ означает сумму по модулю 2; суммирование распространяется по всем подмножествам {zi,...,zs} множества {1, 2,..., п},
включая пустое подмножество 0; коэффициенты пц...д принимают значения 0 или 1; при пц...д = 0 соответствующее слагаемое в полиноме (19) опускают. Наконец, если все коэффициенты пц^.д , включая коэффициент а01 равны 0, то полином (19) записывают просто как 0.
Эквивалентность х V у = х • у можно переписать в виде
х V у = (х Ф 1) • (у Ф 1) Ф 1.
Раскрывая в этом равенстве скобки и пользуясь соотношением 1 ф 1 = = 0, получаем полином Жегалкина для функции х V у:
хУу = хуфхфу.
Аналогичным способом можно построить полиномы Жегалкина для функций х —> у и х | у:
(х -4 у) = Ху ф X ф 1, (х | у) = Ху ф 1.
Интересно выглядит процесс построения полинома Жегалкина для функции ху У xz У yz:
ху V xz V yz = (ху • XZ Ф ху Ф xz) V yz = (xyz Ф ху Ф xz) V yz =
= (xyz Ф ху Ф xz) • yz Ф xyz Ф ху ф XZ Ф yz =
= xyz • yz ф ху • yz ф xz • yz ф xyz ф ху ф XZ ф yz =
= xyz Ф xyz Ф xyz Ф xyz Ф ху ф XZ Ф yz = ху ф XZ Ф yz.
На практике для построения полиномов Жегалкина чаще всего прибегают к методу неопределенных коэффициентов. Пусть нам требуется построить полином Жегалкина для функции f(x,y, г), заданной двоичным набором (10011100). Запишем функцию f(x,y,z) в виде полинома Жегалкина с неопределенными коэффициентами по,..., (27:
/(ж, у, z) = ао Ф а^х Ф а^у Ф a^z Ф а^ху Ф a^xz Ф a^yz Ф a^xyz. (20) Подставляя в функцию f(x,y,z) последовательно наборы (0,0,0), (0,0,1),...,(1,1,1) и пользуясь известными значениями функции /, из (20) получаем следующую систему уравнений для коэффициентов ао,..., ат (слева в скобках указан набор значений переменных ж, у, z, приводящий к данному соотношению):
(0,0,0)
По = 1,
(0,0,1)
а0 Ф а3 = 0,
(0,1,0)
«о Ф а2 = 0,
(0,1,1)
а0 Ф а2 Ф аз Ф а6 = 1,
(1,0,0)
П0 Ф П1 = 1,
(1,0,1)
ао Ф ai Ф аз Ф 05 = 1,
(1,1,0)
(2о Ф (21 Ф (22 Ф (24 = 0,
(1,1,1)
(2о Ф (21 Ф (22 Ф (2з Ф (24 Ф (25 Ф (2б Ф (27 = 0.
Решим ее, исключая последовательно неизвестные щ», • • • ,^7. Первое уравнение дает щ» = С второе, третье и пятое — щ = О, а^ = аз = 1. Используя далее найденные значения коэффициентов щ», ^i, П2, од, рассматриваем четвертое, шестое и седьмое уравнения. Из них находим щ = а^ = 0, ns = 1. Подставляя полученные значения в восьмое уравнение, получаем п7 = 0. Окончательно полином Жегалкина для функциии f(x,y,z) имеет вид 1 ф у ф z ф xz.
Довольно неожиданно оказывается, что для любой булевой функции имеется единственный полином Жегалкина, если только полиномы Жегалкина рассматривать с точностью до перестановок слагаемых и сомножителей в слагаемых. В самом деле, подсчитаем число коэффициентов пц^.д в общей формуле (19) полинома Жегалкина для функции от а переменных. Это число равно числу всевозможных подмножеств (включая пустое) множества {1,2,...,п}. В свою очередь подмножества множества {1, 2,..., п} взаимно однозначным образом соответствуют двоичным наборам длины п: единица, стоящая в наборе на г-м слева месте, свидетельствует о том, что в рассматриваемое подмножество входит число г, нуль — что число г в подмножество не входит.
Понятно, что число различных полиномов Жегалкина вида (19) (при условии, что мы не различаем полиномы, которые получаются друг из друга перестановкой слагаемых или перестановкой сомножителей в слагаемых) равно числу всевозможных способов, которыми мы можем придать значения 0 и 1 коэффициентам пц^.д полинома (19). Поскольку этих коэффициентов имеется 2П, мы получаем величину 22 для числа полиномов Жегалкина от п переменных.
Итак, для каждой булевой функции от п переменных имеется хотя бы один полином Жегалкина, который реализует эту функцию и, вместе с тем, число различных полиномов Жегалкина от п переменных равно числу всех булевых функций от п переменных. Это означает, что для любой булевой функции существует только один реализующий ее полином Жегалкина.
Отметим одну важную особенность полиномов Жегалкина: функция /(жх,..., хп) существенно зависит от переменной х^ тогда и только тогда, когда переменная х^, входит хотя бы в одно слагаемое полинома Жегалкина, реализующего функцию /(^1,...,хп) (еще раз напомним, что в полиноме Жегалкина присутствуют лишь слагаемые, не равные тождественно 0). В самом деле, если функция /(яд,..., хп) не зависит существенно от переменной ж^, то полином Жегалкина, реализующий функцию /(жх,..., жп), можно построить следующим образом. Сначала удалением из функции /(жх,...,жп) несущественной переменной xt образуем функцию f'(xi,..., ж^-i,ж^+i,..., жп), затем строим полином Жегалкина Ф, который реализует функцию ф*. Понятно, что ввиду несущественности переменной х^, полином Жегал-
кина Ф, рассматриваемый от всех переменных яд,..., я;п, будет также реализовать и функцию /(яд,..., жп).
Обратно, если переменная яд не входит ни в одно слагаемое полинома Жегалкина Ф, реализующего функцию /(яд,...,жп), то, очевидно, значения переменной х^ не играют никакой роли при вычислении значений функции f(xi,... ,хп) согласно формуле Ф. Поэтому переменная х^ является несущественной для функции /(яд,..., жп).
УПРАЖНЕНИЯ
Определите при любом п, какую булеву функцию реализует полином Жегалкина (19), если все коэффициенты ащ.щ (включая коэффициент а0) равны 1.
Методом неопределенных коэффициентов постройте полином Жегалкина для функции f(x, у, г, w), заданной набором
(1010101111011000).
Глава II
ЗАМКНУТЫЕ КЛАССЫ И ПОЛНОТА
Класс самодвойственных функций
Булеву функцию /(жх,...,жп) назовем самодвойственной, если /(^1,...,жп) = /*(жъ.. .,хп\(21)
Для самодвойственной функции /(xi,...,xn) равенство (21) можно записать также в виде
7(^Ь • . . ,жп) = /(жъ... Дп).
Из него следует, что самодвойственная функция / на любых двух противоположных наборах (щ,..., an), (щ,..., пп) принимает противоположные значения.
Из табл. 4 видно, что самодвойственными являются функции х и еДжх,.. .,хпу
Обозначим через S множество всех самодвойственных булевых функций. Докажем, что S образует замкнутый класс.
Поскольку селекторные функции являются самодвойственными, достаточно проверить, что из принадлежности классу S функций go, gi,..., дт вытекает принадлежность классу S функции /, заданной равенством (18). Однако это непосредственно следует из принципа двойственности.
На примере самодвойственных функций интересно еще раз проследить идею подсчета функций от н переменных с помощью таблицы. Внимательно рассмотрим табл. 1 и отметим следующий факт: противоположные наборы (ах,..., an), (ах,..., ап) располагаются в ней на равных расстояниях от середины таблицы (которая проходит между 2п-1-м набором (0,1,..., 1) и (2П-1 + 1)-м набором (1,0,..., 0)). Вспомним, что самодвойственная функция принимает противоположные значения на противоположных наборах. Таким образом, для полного задания самодвойственной функции f(xi,... ,хп) достаточно указать ее значения либо на наборах из верхней половины таблицы, либо на наборах из нижней половины. Следовательно, число самодвойственных булевых функций от п переменных равно
о п — 11 о П/ Т-у
22= 22'2 =
Иными словами, это число есть корень квадратный из числа всех булевых функций от н переменных.
Класс самодвойственных функций играет важную роль при решении проблемы полноты в классе Р^. Следующее утверждение, необ-
ходимое для ее решения, имеет также и некоторый самостоятельный интерес.
Лемма 1 (о несамодвойственной функции). Из несамодвойственной функции с помощью подстановки функций х и х на места всех ее переменных можно получить несамодвойственную функцию от одной переменной, т.е. константу 0 или 1.
Доказательство. Пусть функция f(xi,... ,хп) несамодвойственна. Тогда найдется такая пара противоположных наборов (<21,... ,ап) и (п1,...,пп), что
а„) =/(«!,...,«„).(22)
Подставим в функцию /(яд,...,хп) вместо переменной Xi (1 ^ г ^ п) функцию х, если at = 1, и функцию х, если at = 0. Полученную после подстановки функцию обозначим через д(х). Согласно определению
Щ) = /(ж®1,... ,жа"),
где, напомним, через ж1 обозначена функция ж, а через ж0 функция ж. Имеем теперь
(23)(23)01 = 1° = I = 0, ^(1) = ф(аг,... ,ап).01 = 1° = I = 0, ^(1) = ф(аг,... ,ап).g(0) =/(001,..., 0°"), Поскольку_
(23)
(23)
01 = 1° = I = 0, ^(1) = ф(аг,... ,ап).
01 = 1° = I = 0, ^(1) = ф(аг,... ,ап).
0° = 0 = I1 = 1,из равенств (23) заключаем, что^(0) = /(щ,... ,ап),
Обращение к равенству (22) завершает доказательство леммы.
Пусть функция /(ж1,Ж2,жз) определена формулой Ж1Ж2 V яджд V Х/х^хз. Из нее видно, что /(0,1,1) = /(1,0,0) = 1. Соответствующие этим противоположным наборам подстановки /(ж, ж, ж) и /(ж, ж, ж) дают константу 1.
УПРАЖНЕНИЯ
Проверьте, что самодвойственными являются функции
ж В у В г, жфуВгВ1, ху V xz V yz, xyVxzVyz, xyVxzVyz. Докажите, что не существует самодвойственных функций /(жх,Ж2), существенно зависящих от обеих переменных.
§ 2. Класс линейных функций
Булеву функцию /(жх,... ,жп) назовем линейной, если в ее полиноме Жегалкина (19) отсутствуют нелинейные слагаемые (т.е. слагаемые, содержащие не менее двух сомножителей).
Из определения следует, что всякую линейную функцию 7(жц...
..., жп) можно представить в виде
По Ф QiXi Ф ... Ф апхп,(24)
где коэффициенты по,П1,... ,ап равны 0 или 1. Представление (24) позволяет легко подсчитать число линейных функций, зависящих от п переменных. В самом деле, придавая коэффициентам а^а^ ... ^а^ различные значения 0 и 1, мы будем получать различные (проверьте!) линейные функции. Следовательно, число линейных функций, зависящих от переменных жх,... ,жп, равно числу двоичных наборов длины п + 1. Последнее число, как мы знаем, есть 2n+1.
Часто бывает полезным тот факт, что все четыре булевы функции от одной переменной 0, 1, ж, ж = ж ф 1 линейны.
Множество всех линейных булевых функций обозначим через L. Убедимся, что L является замкнутым классом. Пусть функции
9о (?Л) • • •) Ут)) 91 (яд, • • •, жп), ..., дт (жх,..., жп)
линейны, т.е.
9о(У1, • • • тУт) = 60 ® Ь1У1 Ф ... Ф ЬтУт^
Щ(Ж1, . . . ,ЖП) = До Ф йцЖ1 Ф . . . Ф П1ПЖП,
9т (ЯД , • • • , Жп) — Ото Ф «ml^l Ф • • • Ф ^тп^п ?
а функция /(жх,..., жп) представима формулой (18). Тогда
/(яд,..., жп) = Ьо ф bl (аю Ф (2цЖ1 ф ... ф щпжп) ф ...
• • • Ф Ьт(атц ф (2т1Ж1 ф ... ф птпжп) =
= (6о Ф ^1^ю Ф • • • Ф Ьтато) ф (61 (2ц ф ... ф bmami) жх ф ...
. . . Ф (biQin ф . . . ф Ьт^тп) ^п-
Если обозначить значения выражений
60 Ф 61(2ю Ф ... Ф Ьтатц. 61 (2ц ф ... ф bmami^ ..., biain ф ... ф Ьт^тп (которые являются константами 0 или 1) соответственно через (2о, (21,..., ап, то мы придем к формуле (24), определяющей функцию
Отметим, что класс L порождается системой функций {1, ж ф ?/}. В самом деле, имеем 0 = 1 ф 1. Суперпозициями функции ж ф у можно получить любую функцию вида Ж1 ф ... ф жп, где п ^ 2; а поскольку у нас в распоряжении имеются константы 0 и 1 — также и любую функцию вида Жх Ф ... Ф жп~1 и жх Ф ... Ф жп~1 Ф 1.
Булева функция, которая не является линейной, называется нелинейной. Полином Жегалкина нелинейной булевой функции включает хотя бы одно слагаемое, содержащее не менее двух сомножителей.
Для определения линейности (нелинейности) булевой функции универсальным приемом служит разложение функции в полином Жегал- кина. Однако в некоторых случаях о нелинейности функции можно судить по виду двоичного набора, задающего функцию. Так, отличная от константы булева функция будет заведомо нелинейной, если значение 1 (или значение 0) она принимает не на половине всех наборов. Это утверждение мы докажем от противного: если булева функция /(жх,... ,жп) линейна и отлична от константы, то значение 1 (и значение 0) она принимает ровно на 2П-1 наборах.
Итак, пусть функция /(ад?..., жп) линейна и отлична от константы. Тогда она существенно зависит по крайней мере от одной из переменных жх,... ,жп. Пусть это будет, например, переменная хп. Тогда функцию /(ад,..., жп) можно представить в виде
/(жх,. ...х^а^ ауХу ф ... ф пп-1Жп-1 ф хп. (25)
При n = 1 функция /(жх) совпадает с одной из функций Xi, дф1 и утверждение проверяется непосредственно. Предположим далее, что п ^ 2. Опираясь на представление (25), заключаем, что функция /(жх,..., жп) принимает значение 1 только в двух случаях: либо линейная функция
по Ф агХ1 Ф ... Ф an_ixn_i = /(жъ ... ,жп_х,0) (26) принимает значение 0 и хп = 1, либо линейная функция (26) принимает значение 1 и хп = 0. Отсюда сразу следует, что число наборов, на которых функция / принимает значение 1, равно сумме числа наборов, на которых функция (26) принимает значение 0, и числа наборов, на которых функция (26) принимает значение 1. Очевидно, что указанная сумма равна 2П-1 — числу всех двоичных наборов длины п — 1.
В дальнейшем при решении проблемы полноты в классе Р^ нам понадобится утверждение о возможности понижения числа переменных в нелинейной функции. Это утверждение носит название лемма о нелинейной функции.
Лемма 2. Из всякой нелинейной булевой функции подстановкой констант 0 и 1 вместо некоторых переменных можно получить нелинейную функцию от двух переменных.
Доказательство. Пусть f(xi,... ,хп) — нелинейная функция. Поскольку все булевы функции от одной переменной линейны, имеем п ^ 2. При п = 2 утверждение тривиально (можно применить “пустую” подстановку). Пусть п > 2. Выберем в полиноме Жегалкина функции /(ащ... ,хп) нелинейное слагаемое наименьшей степени. Чтобы не применять громоздких обозначений, будем предполагать, что это слагаемое имеет вид Xi • ... • хт (2 ^ т ^ п). Подставим в функцию /(xi,..., хп) константу 0 вместо всех переменных xm+i,...,хп (можно считать, что константа 0 зависит от пе-
3 С.С. Марченков
ременной ад). Ввиду минимальности степени слагаемого ху •... • хт полином Жегалкина функции /(ад,..., хт^ 0,..., 0) примет вид
Ху • ... • хт Ф атхт Ф ... Ф одад Ф а0-
Если т > 2, то подставим далее константу 1 вместо всех переменных хз,... ,хт. В итоге придем к функции, полином Жегалкина которой имеет вид
Ж1Ж2 Ф ^2^2 Ф ЬуХу ф Ь0.
Лемма доказана.
УПРАЖНЕНИЯ
Покажите, что функция, двойственная к линейной, также будет линейной. Покажите, что линейные функции вида а ф ад ф ... ... ф Ж2п+1 являются самодвойственными.
Докажите, что при любом п (п ^ 3) существует нелинейная функция от п переменных, которая принимает значение 1 ровно на 2П-1 наборах. Существенно ли в этом утверждении ограничение п > 3?
§ 3. Класс монотонных функций
Что такое монотонно не убывающая функция? Это функция, значения которой не убывают с ростом значений аргумента. Если вы дадите такой ответ на поставленный вопрос, то в общем-то будете правы. Трудности с монотонными функциями начинаются тогда, когда основное множество, на котором определена функция, как говорят, не является линейно упорядоченным либо когда рассматриваются функции многих переменных. Обе эти возможности нередко соседствуют друг с другом. Однако в случае булевых функций исходное множество В линейно упорядочено (0 < 1), и потому проблема остается лишь с определением монотонных функций от нескольких переменных.
Приводимое ниже определение монотонной функции по существу представляет собой определение функции, монотонной по любой из своих переменных.
Начнем с введения (частичного) порядка на множестве Вп всех двоичных наборов длины п. Говорим, что набор (щ,... ,ап) не превосходит набора (bi,..., Ьп), если для любого г (1 ^ г ^ п) выполняется неравенство щ ^ ^г- Если набор (ах,..., ап) не превосходит набора (Ь1,..., Ъп\ то этот факт записываем в виде
(бД , . . . , (1П) ^ (&1,..., 6П). (27)
Отметим, что при п ^ 2 введенное отношение определено не для любых двух наборов длины п. Так, например, наборы (0,1) и (1,0) невозможно сравнить относительно этого отношения. Именно поэтому введенное отношение является частичным.
Булева функция /(жх,...,жп) называется монотонной, если для любых двух наборов (ai,..., ап\ (bi,..., Ьп) из того, что выполняется неравенство (27), следует, что выполняется неравенство
/(«1,. • • ,аи) С /(6Ь.. -XnY
Множество всех монотонных булевых функций обозначим через М. Непосредственная проверка показывает, что множеству М принадлежат функции 0, 1, х, ху, х V у и не принадлежат функции х, х ® у, х ^у, х I у.
Для проверки монотонности булевых функций от небольшого числа переменных часто используют задание булевых функций с помощью диаграммы, на которой представлен частичный порядок на множестве Вп. Каждому набору из Вп отвечает точка на этой диаграмме, а различные точки соединяются отрезком прямой в том и только том случае, когда эти точки соответствуют наборам, различающимся ровно в одной компоненте (рис. 1). Обычно точки на диаграмме изображают “слоями”. При этом каждый “слой” диаграммы состоит из точек, которые отвечают двоичным наборам с одним и тем же числом единичных компонент. Следовательно, если число единиц в наборе а = (щ,..., ап) меньше числа единиц в наборе b = (bi,..., Ьп), то набор b расположен в диаграмме выше набора а. Если же еще для наборов а, b выполняется соотношение (27), то от набора а в диаграмме можно “подняться” до набора b по отрезкам прямых.
Значения функции помещаются на диаграмме рядом с вершинами, которые отвечают наборам соответствующих значений переменных. На рис. 1 значения 1 функций обозначены жирными точками.
На диаграмме множества В2 представлена функция х —> у, а на диаграмме множества В3 — функция х(у V г). С помощью приведенных диаграмм можно легко проверить немонотонность функции х —> у и монотонность функции х(у V г). В самом деле, переход от меньшего набора (0,0) к большему набору (1,0) сопровождается изменением функции х —> у от большего значения 1 к меньшему значению 0. Напротив, в диаграмме множества В3 на любом пути, ведущем от наименьшего набора (0, 0, 0) к наибольшему набору (1,1,1), значения функции х(у V г) не убывают.
Докажем, что множество М является замкнутым классом. Поскольку селекторные функции монотонны, нам достаточно доказать, что из монотонности функций до, д^ ..., дт следует монотонность функции У, если / определяется равенством (18). Пусть для наборов а = (щ,..., пп), b = (bi,..., ЬД выполняется соотношение (27). Тогда в силу монотонности функций gi,... ,дт будем иметь
91(a) gi(b), ..., дт^ дт(Ь).
Следовательно,
(9i(a),...,9m(a)) ^ (gi(b),...,gm(b)).
Пользуясь этим неравенством и монотонностью функции до, заключаем, что
9o(gi(a),...,gm(a))9о(91(Ц... ,gm(b^.
Согласно определяющему равенству (18) это означает, что /(ai,...,an)
и монотонность функции У установлена.
Любопытный вариант теоремы 2 о разложении имеет место для монотонных функций.
Теорема 3. Для любой монотонной булевой функции f(xi,...
... ,хД справедливо представление
f(x-L,...,Xn) = Х1 ■ /(1,ж2,...,жи) V /(0,ж2,...,жп).(28)
Доказательство. Пусть а = (ai,..., ап) — произвольный двоичный набор. Для набора а найдем значения левой и правой частей равенства (28). Слева мы имеем f(a\ Если ау = 0, то, как легко видеть, справа также образуется значение f(a\ Пусть щ = 1. Тогда справа в (28) получаем
/(1, а2,..., an) V /(0, a2,..., ап\(29)
Однако набор (0, а2,..., ап) не превосходит набора (1, а2,..., ага). Следовательно, в силу монотонности функции У будем иметь
/(0, «2,..., а„) < /(1, «2,..., а„).
Поэтому значение (29) есть /(1, а^,..., ап\ Теорема доказана.
Заметим, что в формуле (28) функции /(О, Ж2,..., жп) и /(1, х^^... ...,хп) также являются монотонными, поскольку получаются из монотонной функции / подстановкой монотонных функций 0 и 1. Поэтому при п ^ 2 так же, как и при выводе следствия 2 из теоремы 2, процесс разложения функций /(О, х^,..., хп) и /(1, х^,..., хп) можно продолжить по переменной Х2- В результате придем к разложению /Щ, ■.. ,ЖП) = Ж1 • Ж2 • /(1, 1,Ж3, . . . ,Ж„) УЖ1 • /(1,0,Жз, ... ,ж„) V
V ж2 • /(0,1,ж3, -,жп)V Д0,0,ж3,... ,ж„).
Если при /г ^ 3 проделать указанное разложение по всем оставшимся переменным жз,..., жп и воспользоваться соотношениями ж-1 = ж\/0 = ж, то получим следующее утверждение.
Следствие 1. Любую монотонную функцию, отличную от константы, можно представить в виде ДНФ, не содержащей отрицаний переменных.
Следствие 1 позволяет сделать важный вывод о системе функций, порождающей класс М.
Следствие 2. Класс М порождается системой функций {0,1, ху, х V yY
В заключение параграфа докажем лемму о немонотонной функции, которая нам понадобится в следующем параграфе при доказательстве критерия полноты.
Лемма 3. Из немонотонной функции путем подстановки констант 0 и 1 на места некоторых переменных можно получить немонотонную функцию одной переменной, т.е. функцию х.
Доказательство. Пусть функция /(ж1,...,хД немонотонна. Тогда найдутся такие два набора а = (щ,..., аД и b = (bi,..., ЬД, что выполняются соотношения (27) и /(а) = 1, f(b) = 0. Покажем, что наборы а, b можно считать соседними, т.е. различающимися ровно в одной компоненте. В самом деле, предположим, что это не так и наборы а, b различаются в t компонентах, где t > 1. Пусть, например, щ = 0, bi = 1 (вариант щ = 1, bi = 0 не может реализоваться в силу неравенства (27)). Рассмотрим набор с = (ai,..., щ_у, 1, а^1,..., аД. Он отличается от набора а в одной компоненте и от набора b в t — 1 компонентах. Кроме того, а ^ с и с ^ Ь. Если /(с) = 0, то вместо набора b можно взять набор с. Если же /(с) = 1, то набор а следует заменить на набор с и вновь повторить описанную выше процедуру. Не более чем через t — 1 шагов мы придем к паре соседних наборов с требуемыми свойствами.
Итак, считаем, что наборы а и b различаются только в одной компоненте. Пусть это будет первая компонента. Тогда щ = Ь2,... ,ап = = Ьп и, следовательно, подстановка констант щ,... ,ап на места переменных Х2,... ,хп в функцию /(ж1,... ,хД дает функцию дДД = = f(xi,O2,... ,аД такую, что ^(0) = 1 и р(1) = 0. Лемма доказана.
УПРАЖНЕНИЯ
Проверьте на монотонность функцию xyz(x —> у)(х —> г). С использованием диаграммы множества В3 найдите число монотонных функций от трех переменных.
Покажите, что из монотонности функции / следует монотонность функции /*.
Найдите все монотонные линейные функции.
Критерий полноты
Существует ли эффективный способ, который по любой системе булевых функций дает ответ на вопрос, полна ли эта система? Оказывается, такой способ существует; его предложил американский математик Э. Пост еще в 1921 г. Способ основан на проверке пяти свойств: невхождении системы булевых функций полностью ни в один из замкнутых классов
То, Тъ S, М, L.(30)
Точнее говоря, имеет место следующий критерий полноты в классе Р^.
Теорема 4. Система булевых функций Q полна в Р^ тогда и только тогда, когда Q целиком не содержится ни в одном из классов (30).
Доказательство. Необходимость. Пусть система функций Q полна в Р2. Тогда [Q] = Р^. Если бы система Q целиком содержалась в одном из классов (30) (обозначим этот класс через R), то по свойству 3 замыкания выполнялось бы равенство [Я] = Р^. Однако каждый из замкнутых классов (30) отличен от класса Р^. Поэтому система Q целиком не содержится ни в одном из классов (30).
Достаточность. Пусть система Q целиком не содержится ни в одном из классов (30). Обозначим через Д, Д, Д, Д, Д функции системы Q, которые не входят соответственно в классы То, Ту, S, М, L (некоторые из функций Д,..., Д могут совпадать). Покажем, что суперпозициями функций Д,..., Д можно получить функции X, ху, которые, как нам известно, образуют полную в Р^ систему. Тогда по теореме 1 полной будет система {Д,..., Д} и, следовательно, система Q.
Получим сначала из функций Д, Д, Д константы 0 и 1. Из того, что Д не входит в класс То, следует, что Д(0,..., 0) = 1. Значит, если положить
gi(x) = Д(ж, ...,ж),
то функция Цу (х) будет совпадать с одной из функций 1, х. Если щ(ж) — константа 1, то, пользуясь соотношением Д(1,...,1) = 0,
получаем константу 0:
Ыд^ (ж),..., 91 (ж)) = о.
Пусть gi (х) = х. Тогда, применяя лемму о несамодвойственной функции к функции Д, подстановками функций х и х получаем из нее одну из констант, 0 или 1. Другую константу образуем с помощью подстановки в функцию х.
Имея обе константы, с помощью леммы о немонотонной функции, примененной к функции Д, строим функцию Дас помощью леммы о нелинейной функции, примененной к функции Д, строим нелинейную функцию 92(х,у). Рассмотрим далее полином Жегалкина для функции 92(ж, у):
дг(ж>У) = ху® а^х ф а2у Ф аз-
Можно считать, что а^ = 0, поскольку в противном случае вместо функции д2(х,у) следует взять функцию 92^, у) = 92(х,у) ф 1 (напомним, что функция ж = жф 1 у нас уже имеется). Если ау = 02 = 0, то д2(х,у) — конъюнкция ху. Если ai = 1 и 02 = 0, то
92(х.у) = ху Ф х = х(у Ф 1) = ху.
Следовательно, в этом случае 92 (х, у) = ху. Аналогично рассматривается случай, когда ау = 0 и 02 = 1. Наконец, если ay = 02 = 1, то №(ж,у) = ху ® х ® у = XV у.
В этом случае
у2(ж,у) = ху.
Теорема доказана.
Из теоремы 4 вытекает несколько интересных следствий. Во-первых, как видно из доказательства, если система функций полна в Р2, то из нее можно выделить также полную подсистему, состоящую не более чем из пяти функций. А нельзя ли в общем случае уменьшить это число до четырех? Оказывается, можно. Действительно, пусть функции Д,..., Д выбраны так, как указано в доказательстве теоремы. Рассмотрим функцию Д. Согласно выбору этой функции имеем /1(0,..., 0) = 1. Если Д(1,..., 1) = 1, то функция Д несамодвойственна (на противоположных наборах (0,..., 0) и (1,..., 1) она принимает одно и то же значение 1). Поэтому функцию Д можно заменить функцией Д. Если же Д (1,..., 1) = 0, то функция Д немонотонна. Значит, в этом случае функцией Д можно заменить функцию Д.
Итак, мы приходим к следующему утверждению.
Если система функций полна в классе Р2, то из нее можно выделить полную подсистему, состоящую не более чем из четырех функций.
Можно ли продвинуться в этом направлении дальше, понизив оценку до трех? Следующий пример показывает, что, вообще говоря, этого сделать нельзя.
Пусть
Q = {0, 1, ху V xz V yz^ х ф у ф г}.
Пользуясь, например, теоремой 4, нетрудно убедиться, что система Q полна в Р2- Вместе с тем подсистема
{1, xy\J xz\J yz, х Ф ?/ Ф г}
целиком лежит в классе Ti, подсистема
{0, хуМ xz\/ yz, х ®у ® z}
— в классе То, подсистема
{0, 1, х Ф у Ф z}
— в классе L и подсистема
{0, 1, ху V xz\/ yz}
— в классе М. Таким образом, ни одну из функций системы Q нельзя исключить из системы, не нарушив при этом условий полноты.
УПРАЖНЕНИЯ
Постройте пример базиса в классе Р^ состоящего из трех функций.
Докажите, что булева функция /, не принадлежащая ни одному из классов То, ТА, Д является базисом класса Р^. Будет ли справедливо аналогичное утверждение, если вместо класса S взять класс LI
Замкнутые классы, содержащие константы
Как велико число замкнутых классов? Можно ли каким-либо эффективным способом перечислить все замкнутые классы?
Американский математик Э. Пост установил, что число замкнутых классов в Р2 бесконечно. Тем не менее, существует эффективная процедура перечисления всех замкнутых классов с помощью конечных порождающих систем функций. Изложение этих результатов в полном объеме хотя и не требует специальных знаний, но выходит за рамки данной брошюры). Мы решим более скромную задачу: найдем все замкнутые классы, содержащие обе константы 0 и 1.
Из всех замкнутых классов Р^, То, Ту, S, М, L, которые мы изучали в предыдущих параграфах, обе константы содержат лишь классы Р^ М и L. Дадим определение еще пяти замкнутых классов, которые также содержат обе константы (с некоторыми из этих классов мы уже начали знакомиться в § 6 гл. I).
Через С обозначим класс всех булевых функций-констант (от любого числа переменных).
Через MU обозначим класс всех функций, которые являются либо константами, либо селекторными функциями.
Через U обозначим класс всех булевых функций, которые существенно зависят не более чем от одной переменной.
Через D обозначим класс всех дизъюнкций, т.е. всех функций f^xy,... ,хп), которые представимы в виде
по V ауХу V ... V апхп,(31)
где ао, ау,..., ап — произвольные элементы из В.
Наконец, через К обозначим класс всех конъюнкций, т.е. класс всех функций f(xy,..., хп), которые представимы в виде
«о • («1 УяД • ... • (an V хпу(32)
Замкнутость классов С, MU, U легко вытекает из их определения (напомним еще раз, что наряду с любой булевой функцией / мы считаем одновременно заданными все функции, которые получаются из / добавлением или изъятием несущественных переменных).
Чтобы доказать замкнутость класса D, полезно иметь в виду, что при по = 1 дизъюнкция (31) обращается в константу 1, при ао = ау = ... = ап = 0 — в константу 0, а если из коэффициентов ао, ау,..., ап равны 1 лишь коэффициенты а^,..., щ5 , причем ао = = 0, то выражение (31) представляет собой “настоящую” дизъюнкцию жц V... V жд. Поэтому замкнутость класса D следует из свойств дизъюнкции, отмеченных в §5 гл. I.
Класс К, как несложно проверить, является двойственным к классу D. Из представлений (31) и (32) видно, что класс D порождается системой функций {0, 1, ж V у^, а класс К — системой функций {0, 1, xyY
Теорема 5. Существует всего 8 замкнутых классов, содержащих обе константы:
Р^, М, L, С, MU, U, D, К.
Доказательство. Пусть R — произвольный замкнутый класс, содержащий константы 0 и 1. Поскольку система функций {0, 1} целиком не содержится ни в одном из классов То, Ту, S, из теоремы 4 выводим, что класс R либо совпадает с классом Р^, либо целиком содержится в одном из классов М, L. Рассмотрим сначала случай, когда R состоит только из линейных функций.
Если класс R состоит из функций, существенно зависящих не более чем от одной переменной, то непосредственная проверка показывает, что R совпадает с одним из классов С, MU^ U. Пусть, далее, класс R содержит линейную функцию /(яд,...,жп), существенно зависящую не менее чем от двух переменных. Можно считать, что все переменные функции /(яд,... ,хп) существенны. Тогда функция f(xi,... ,хп) представима в виде
/(Ж1,..., ж„) = Ж1 ® ... ® ® а,
где п ^ 2 и а — элемент множества В. При п > 2 подстановкой константы 0 вместо всех переменных хз,..., хп получаем функцию яд ф яд ф а, принадлежащую классу R. Если а = 0, то в класс R входит система функций {1,яд фд}, которая, как отмечалось в § 2 гл. II, порождает класс L. Значит, в этом случае R = L. Если же а = 1, то функцию яд ф яд получаем суперпозициями функций О и яд Ф яд Ф 1:
яд Ф О Ф 1 = яд Ф 1, (яд Ф яд Ф 1) Ф 1 = яд Ф яд.
Таким образом, если замкнутый класс R содержит обе константы 0, 1 и состоит только из линейных функций, то он совпадает с одним из классов С, MU. U, L.
Пусть теперь класс R состоит только из монотонных функций. Если R содержит только функции, существенно зависящие не более чем от одной переменной, то он совпадает с одним из классов С, MU (класс U содержит немонотонную функцию ж).
Пусть в класс R входит функция, существенно зависящая не менее чем от двух переменных. Тогда согласно лемме о нелинейной функции в класс R будет входить нелинейная функция от двух переменных. Заметим, что она монотонна, поскольку получается из монотонной функции подстановкой констант 0 и 1. Легко проверить, что нелинейными монотонными функциями от двух переменных являются лишь функции
ху и х\/у = хуфхфу.
Поскольку системы функций
{О, 1, х V у^ и {0, 1, ху^
порождают соответственно классы D и К, мы приходим к выводу, что в этом случае в класс R целиком входит хотя бы один из классов D или К.
Если в класс R целиком входят оба класса D и К, то R = М , так как класс М порождается системой функций {0, 1, ху, х V т/}. Предположим поэтому, что в R целиком входит только один из классов D. К. Ввиду двойственности классов D. К можно считать, что это класс D. Мы покажем, что в этом случае R совпадает с D.
В самом деле, допустим, что R ^ D. Тогда в класс R входит функция f(xi,..., жп), которая не является дизъюнкцией. Согласно след-
ствию 1 из теоремы 3 функцию /(ж1,..., жп) можно представить в виде ДНФ Ф, которая не содержит отрицаний переменных. Поскольку функция /(ж1,...,жп) отлична от дизъюнкции, ДНФ Ф содержит хотя бы одну конъюнкцию, имеющую более одного сомножителя. Пусть жц • ...•жд — такая конъюнкция с наименьшим возможным числом сомножителей (s ^ 2). Можно считать, что в Ф в качестве дизъюнктивных слагаемых не входит ни одна из переменных жц,..., жд (иначе по свойству поглощения 11 конъюнкцию Жц • ... • Жд в Ф можно было бы опустить). Таким образом, любая конъюнкция из ДНФ Ф, отличная от жц •... • жд, содержит хотя бы одну переменную, не входящую в множество переменных {жц,..., жд }. Следовательно, если в функции /(жх,..., жп) заменить константой 0 все переменные, отличные от переменных жц,..., жд, то получится функция, реализуемая конъюнкцией жц •... • жд . Если теперь s ^ 3, то подстановка константы 1 вместо переменных ж*3,..., жд дает конъюнкцию жц • ж/2.
Итак, получаем, что в класс R входит конъюнкция ху и, тем самым, все функции класса К. Это противоречит сделанному выше предположению о невхождении класса К в R. Теорема доказана.
Довольно просто найти все замкнутые классы, которые целиком лежат в одном из классов L. D. К. Мы приведем полный перечень этих классов. Попытайтесь самостоятельно установить, что не существует других замкнутых классов, целиком лежащих в классах L. D. К.
Итак, класс L линейных функций целиком содержит замкнутые классы
Lo, Lb SL, Loi, U, MU, SU, Uo, иъ UOi, С, Со, Съ
где
Lq — класс всех линейных функций, сохраняющих константу 0;
Li — класс всех линейных функций, сохраняющих константу 1; SL — класс всех самодвойственных линейных функций;
Lqi — класс всех линейных функций, сохраняющих константы 0 и 1;
SU — класс всех самодвойственных функций, существенно зависящих от одной переменной;
По — класс всех функций, сохраняющих константу 0 и существенно зависящих не более чем от одной переменной;
Uу — класс всех функций, сохраняющих константу 1 и существенно зависящих не более чем от одной переменной;
Uо\ — класс всех функций, сохраняющих константы 0 и 1 и существенно зависящих не более чем от одной переменной;
Со — класс всех функций-констант, равных 0 (от любого числа переменных);
Ci — класс всех функций-констант, равных 1.
Класс D всех дизъюнкций целиком содержит следующие замкнутые классы:
Do — класс всех дизъюнкций, сохраняющих константу 0;
Di — класс всех дизъюнкций, сохраняющих константу 1;
Dqi — класс всех дизъюнкций, сохраняющих константы 0 и 1; а также классы
MU, Uo, Db Doi, С, Со, Су.
Класс К всех конъюнкций целиком содержит следующие замкнутые классы, двойственные к соответствующим классам из D:
Ко, Ку, Koi, MU, Do, Di, Doi, С, Со, Су.
Глава III
СЛОЖНОСТЬ РЕАЛИЗАЦИИБУЛЕВЫХ ФУНКЦИЙ
Минимизация ДНФ
Пусть Q — полная система функций. Тогда любую булеву функцию можно реализовать формулой над Q. Как мы уже не раз видели, для некоторых полных систем Q существуют функции, которые реализуются различными формулами. (Нетрудно показать, что для любой полной системы Q и любой булевой функции / существует бесконечное число формул над Q, реализующих функцию /.) Поэтому возникает желание для любой булевой функции / найти оптимальную (в каком-либо смысле) формулу над Q, которая реализует функцию /. Вопрос этот представляется в прикладном отношении очень важным. Однако пока не сформулирован критерий оптимальности, нельзя даже утверждать, что для данной булевой функции имеется хотя бы одна оптимальная формула, реализующая эту функцию.
На практике, как правило, рассматриваются такие критерии оптимальности, для которых вопрос о существовании оптимальных формул решается тривиальным образом. Обычно для формул определяется числовая характеристика (параметр), имеющая смысл некоторой сложности, и оптимальной формулой называется формула с наименьшим возможным значением этого параметра. Сам процесс поиска формул наименьшей сложности носит название минимизации формул.
Из всех полных систем функций наиболее употребительной в вопросах минимизации является система Qo = {ж, ху. х V yY В качестве меры сложности чаще всего рассматривают две взаимосвязанные меры: число символов функций, входящих в формулу, либо число символов переменных. При этом как символы функций, так и символы переменных подсчитываются с теми кратностями, с которыми они встречаются в формуле. Так, например, в формуле
Ж1(ж2 V Хз) V Ж2Ж3(Ж1Ж2 V х4)
имеется 12 символов функций и 8 символов переменных.
В этом параграфе в качестве меры сложности формул мы выбираем число символов переменных, входящих в формулу. Нетрудно понять, что для всякой булевой функции существует реализующая ее формула наименьшей сложности над системой Qo (таких формул может быть несколько). В самом деле, для заданной булевой функции /(ж1,...,жп) можно, например, последовательно перебирать в
некотором порядке все формулы над Qo сложности 1,2,..., содержащие только символы переменных яд,...,я;п, и сравнивать реализуемые ими функции с функцией f. Этот процесс не может продолжаться неограниченно долго, поскольку, во-первых, функцию /(яд,..., жп) всегда можно реализовать в виде совершенной ДНФ со сложностью, не превосходящей п • 2П. А во-вторых, количество формул над Qq заданной сложности конечно (количество формул сложности I заведомо меньше числа всех строк длины Z, составленных из символов (, ), -, &, V, яд,..., жп; это число равно (п + 5/).
Описанный выше тривиальный алгоритм поиска формулы наименьшей сложности относится к классу так называемых переборных алгоритмов. Отличительной особенностью этих алгоритмов является то, что для отыскания искомого объекта (в нашем случае — формулы) сложности I приходится перебирать все объекты сложности, меньшей или равной I. Обычно это приводит к тому, что переборный алгоритм при работе над входными данными размера I затрачивает около с1 шагов, где с — константа, превосходящая 1.
Если обратиться к формулам над системой Qo, то можно показать, что число различных формул, содержащих ровно г символов переменных из множества {яд,...,жп}, не меньше, чем (ДоД. Поэтому если функция /(яд,...,хп) задана формулой сложности Z, то непосредственный просмотр всех формул со сложностью к (к ^ I) потребует не менее с^ шагов, где ci > 1.
В настоящее время неизвестны алгоритмы непереборного типа, осуществляющие минимизацию формул над системой Qo (как, впрочем, и над любой другой полной системой). Трудности, стоящие на этом пути, носят, по-видимому, принципиальный характер. Некоторое представление об этих трудностях дает пример минимизации ДНФ — формул над системой Qo, имеющих довольно простое строение. Хотя проблема минимизации ДНФ пока также не получила окончательного удовлетворительного решения, на пути ее решения создана разветвленная система понятий и получен ряд интересных и важных результатов.
Дадим необходимые определения, используемые в теории минимизации ДНФ.
Элементарной конъюнкцией называется формула вида т/1 • ... ... • хД , где сд,..., crr Е {0,1} и все переменные ящ ,..., х^Т различны. Число г называется рангом конъюнкции.
Дизъюнктивная нормальная форма (ДНФ) есть формула вида Ку У ... У Kt, где Ку,..., Kt — различные элементарные конъюнкции (порядок сомножителей в конъюнкции роли не играет).
Минимальной ДНФ функции / называется ДНФ, которая реализует функцию / и имеет наименьшее число символов переменных среди всех ДНФ, реализующих функцию /.
Булева функция может иметь несколько минимальных ДНФ. Так, для функции /(ж, у, г), заданной двоичным набором (11100101), минимальными ДНФ являются
ху V xz V xz и xz V xz V yz. (33)
Как мы уже говорили, проблему минимизации ДНФ можно решить тривиальным переборным алгоритмом. Мы хотим уменьшить перебор за счет удаления некоторых элементарных конъюнкций, которые заведомо не входят ни в одну из минимальных ДНФ. С этой целью введем следующие понятия.
Пусть /(xi,..., жп) — булева функция и К — элементарная конъюнкция, все переменные которой принадлежат множеству {xi,... . ..,жп}. Назовем конъюнкцию К импликантом функции У, если функция
к (34)
тождественно равна 1, и -простим импликантом функции У, если К — импликант функции У, но перестает быть таковым после вычеркивания из К любого сомножителя (если ранг конъюнкции К равен 1, то импликант К по определению считается простым импликантом функции У, если / не равна тождественно 1).
Из представления (34) видно, что импликант К функции / принимает значение 1 только на тех наборах, на которых равна 1 функция У (импликант К “имплицирует” единичные значения функции /). Далее, если элементарная конъюнкция К* получается из элементарной конъюнкции К вычеркиванием некоторых сомножителей, то, очевидно, функция К К* будет тождественно равна 1, т.е. всякий двоичный набор, обращающий в 1 конъюнкцию К, будет обращать в 1 и конъюнкцию К*. Поэтому простой импликант К функции / обладает свойством максимальности: он, как говорят, покрывает наибольшее число единиц функции / (т.е. наборов, на которых функция У равна 1) среди всех импликантов функции У, которые получаются из К умножением на некоторые сомножители. Все эти соображения наводят на мысль, что простые импликанты и дизъюнкция всех простых импликантов должны играть важную роль в вопросах минимизации ДНФ.
Назовем ДНФ функции У сокращенной, если она представляет собой дизъюнкцию всех простых импликантов функции у.
Нетрудно заметить, что сокращенная ДНФ не обязана быть минимальной. Так, для рассмотренной выше функции (11100101) с минимальными ДНФ (33) сокращенной ДНФ будет формула
ху V xz V xz V yz.
Тем не менее справедливо следующее утверждение.
Теорема 6. Любая минимальная ДНФ булевой функции может быть получена из ее сокращенной ДНФ путем удаления некоторых конъюнкций.
Доказательство. Достаточно установить, что любая минимальная ДНФ булевой функции / является дизъюнкцией только простых импликантов функции ф. Последнее почти очевидно, поскольку, во-первых, в силу определения каждая входящая в ДНФ конъюнкция представляет собой импликант функции ф. А во-вторых, если бы импликант минимальной ДНФ не был простым, то из него удалением некоторых сомножителей можно было бы получить простой импликант функции ф. Как следствие, получили бы другую ДНФ с меньшим числом символов переменных. Это противоречит определению минимальной ДНФ. Теорема доказана.
Следствие. Если некоторая конъюнкция не входит в сокращенную ДНФ функции /, то она не входит ни в одну минимальную ДНФ функции ф.
Теорема 6 показывает, что при построении минимальных ДНФ нет необходимости рассматривать произвольные импликанты — достаточно ограничиться теми, которые входят в сокращенную ДНФ.
Как мы уже убедились, сокращенная ДНФ может не быть минимальной. Однако существуют достаточно широкие классы функций, для которых эти понятия совпадают. Один из них — класс монотонных функций.
Теорема 7. Сокращенная ДНФ монотонной функции, отличной от константы, не содержит отрицаний переменных и является ее единственной минимальной ДНФ.
Доказательство. Пусть фД-^.-.^хД — монотонная функция, отличная от константы, а конъюнкция
К — Жц • ... • xir • xir+1 • . . . • Жд
является импликантом функции ф, причем 8 > г. Тогда конъюнкция К, а вместе с ней и функция ф, принимает значение 1 при
Жц = . . . = Xir = 1, Ж^+1 = . . . = Жд = О
(значения остальных переменных могут быть произвольными). Ввиду монотонности функция ф будет принимать значение 1, как только жц = ... = xtT = 1. Следовательно, если положить К' = жц • ... • ж^г, то К* будет также импликантом функции ф, который получается из импликанта К вычеркиванием сомножителей 5щ+1,..., жд . Поскольку s > г, получаем, что К не есть простой импликант функции ф. Значит, сокращенная ДНФ функции ф не содержит отрицаний переменных.
Итак, любая конъюнкция К из сокращенной ДНФ функции У(жх,..., жп) имеет вид жц • ... • ж^г. Покажем, что конъюнкция К яв-
ляется единственной конъюнкцией в сокращенной ДНФ функции /, которая принимает значение 1 при
Ж41 = ... == 1, xir+1 = ... = xin = о.(35)
В самом деле, пусть имеется еще одна конъюнкция К1 из сокращенной ДНФ функции /, которая принимает значение 1 при выполнении условий (35). Тогда согласно первой части доказательства теоремы конъюнкция К1 не может содержать сомножителей ж^г+1,..., ж^, а ввиду условия xit+1 = ... = х1п = 0 из (35) — также и сомножителей ж^г+1,..., х^. Значит, в конъюнкцию К' могут входить лишь сомножители из числа жц ,..., х^т. Но тогда К* получается из К вычеркиванием некоторых сомножителей, что противоречит простоте импликанта К.
Таким образом, конъюнкцию К из сокращенной ДНФ функции / удалить нельзя. Для завершения доказательства теоремы 7 теперь остается обратиться к теореме 6.
Как же строить сокращенную ДНФ булевой функции? Существует целый ряд методов синтеза сокращенной ДНФ. Мы рассмотрим только один из них — метод Блейка. Этот метод применим к произвольной ДНФ булевой функции, отличной от константы, и состоит в многократном выполнении двух эквивалентных преобразований над конъюнкциями, входящими в ДНФ:
обобщенное склеивание
хК' V хК" = хК' V хК" V К'К";
поглощение
К' V К'К" = к'
(подразумевается, что преобразования выполняются только слева направо).
Итак, пусть D — произвольная ДНФ булевой функции /, отличной от константы. По методу Блейка сначала выполняем все возможные преобразования 1) и получаем ДНФ D*. Покажем, что при этом каждый простой импликант К функции / будет включен в ДНФ D*. Очевидно, достаточно рассмотреть случай, когда К не входит в D.
Прежде всего заметим, что в К входят только те переменные, которые содержаться в D. В самом деле, если бы это было не так, то, удалив из К переменную, не входящую в D. мы получили бы конъюнкцию К* которая, очевидно, также является импликантом функции /. Это противоречит простоте импликанта К.
Рассмотрим теперь множество конъюнкций {^}, которое удовлетворяет следующим трем условиям.
1°. Kj содержит только те переменные, которые входят в D.
2°. Kj получается из К домножением на некоторые множители (случай Kj = К не исключается).
4 С.С. Марченков
3°. Для любой конъюнкции Н из ДНФ D конъюнкции Kj удовлетворяет хотя бы один набор, не удовлетворяющий конъюнкции Н.
Множество {Kj} непусто, так как содержит, например, конъюнкцию К (условие 3° для конъюнкции К выполняется, поскольку в противном случае конъюнкция К либо входит в D. либо не является простым импликантом функции /).
Выберем в множестве {Kj} конъюнкции наибольшего ранга Ку,._КП1ь. Рассмотрим конъюнкцию Ку. Она не может содержать все переменные, входящие в D. так как в этом случае конъюнкции Ку удовлетворяет только один набор (переменные функции /, не входящие в D. здесь можно не принимать во внимание), который в силу условия 3° не удовлетворяет ни одной конъюнкции из D. То есть получаем, что Ку не является импликантом функции /, что противоречит условию 2°.
Возьмем переменную ж, которая входит в D и не входит в Ку. Рассмотрим конъюнкции хКу и хКу. Они удовлетворяют условиям 1° и 2° и имеют ранг, на 1 больший, чем ранг Ку. Следовательно, по выбору конъюнкции Ку конъюнкции хКу, хКу не удовлетворяют условию 3°. Тогда в ДНФ D имеются такие конъюнкции Ну и Н). что все сомножители конъюнкций Ну, Н> входят соответственно в конъюнкции хКу И хКу. Понятно, ЧТО В КОНЪЮНКЦИЮ Ну должен входить сомножитель ж, а в конъюнкцию Н> — сомножитель ж. Поэтому
Ну = хН^ Н^хН'^
где все сомножители конъюнкций Н^, Н^ принадлежат конъюнкции Ку. Следовательно, после выполнения преобразования 1) над конъюнкциями Ну и Н2 в ДНФ D* будет включена конъюнкция НуН^ все сомножители которой входят в конъюнкцию Ку.
Аналогичные построения и утверждения справедливы и для конъюнкций К).... ,Кт. Обозначим через Dy ДНФ, которая получается из ДНФ D добавлением конъюнкций вида Н^Н^ образованных при рассмотрении всех конъюнкций Ку^... ^Кт. Если теперь для этой ДНФ Dy определить множество конъюнкций {ЕД, удовлетворяющих условиям 1°-3°, то конъюнкция наибольшего ранга из {ЕД будет иметь ранг, меньший, чем ранг конъюнкции Ку. Понятно, что на некотором шаге этого индуктивного процесса в ДНФ D* будет включена конъюнкция К.
После того как в ДНФ D* будут включены все конъюнкции — простые импликанты функции /, — преобразование 2) удаляет из D* конъюнкции, не являющиеся простыми импликантами. В результате образуется сокращенная ДНФ функции f.
Еще раз рассмотрим функцию /(ж, у, г), заданную двоичной строкой (11100101). Ее совершенная ДНФ есть
D = xyz V xyz V xyz V xyz V xyz.
Отправляясь от ДНФ D, методом Блейка построим сокращенную ДНФ функции /. Применим четыре раза преобразование 1):
zyz V xyz = xyz V xyz V ху,
xyz V xyz = xyz V xyz V xz, xyz V xyz = xyz V xyz V yz, xyz V xyz = xyz V xyz V xz.
Таким образом, с помощью преобразования 1) к ДНФ D дизъюнктивно добавляем слагаемое
^с(/) = ху V xz V yz V xz
и образуем ДНФ D* = D V Dc(f). Затем, пользуясь преобразованием 2), из ДНФ D' удаляем все конъюнкции, входящие в совершенную ДНФ D. В результате получим сокращенную ДНФ Dc(f) функции /.
Как мы уже знаем, сокращенная ДНФ может не быть минимальной. Вместе с тем любая минимальная ДНФ получаеся из сокращенной отбрасыванием некоторого числа конъюнкций. Оказывается, в зависимости от того, какие конъюнкции и в каком порядке будут отброшены, может образоваться как минимальная ДНФ, так и неминимальная ДНФ, из которой невозможно удалить ни одну конъюнкцию, не нарушая при этом реализуемую ею функцию. В связи с этим дадим следующее определение.
ДНФ D функции / называется тупиковой, если она состоит только из простых импликантов функции / и после удаления любой конъюнкции из D полученная ДНФ уже не реализует функцию /.
Очевидно, что всякая минимальная ДНФ является тупиковой. Как показывает следующий пример, булева функция может иметь несколько тупиковых ДНФ, которые не являются минимальными. Пусть
f(x, у, z) = xyz V xyz V xyz V xyz V xyz V xyz.
Сокращенная ДНФ функции / имеет вид
ху V xz V ху V xz V yz V yz.
Тупиковыми ДНФ функции / будут
Dy = ху V xz V yz, D> = xz V ху V yz, D3 = ху V ху V yz V yz,
D4 = ху V ху V xz V xz, D5 = xz V xz V yz V yz.
Из них только Dy и D> являются минимальными.
Таким образом, если сокращенная ДНФ строится по функции однозначно, то процесс перехода от сокращенной ДНФ к тупиковой ДНФ уже неоднозначен. При этом удаление одних элементарных конъюнкций из сокращенной ДНФ приводит к минимальной ДНФ, а удаление других приводит к тупиковой, не являющейся минимальной. Поэтому для построения минимальной ДНФ приходится, вообще
говоря, строить все тупиковые ДНФ и затем проводить среди них отбор.
УПРАЖНЕНИЯ
Постройте сокращенную, тупиковые и минимальные ДНФ для функции f(x,y,z), заданной двоичной строкой (10111101).
§ 2. Схемы из функциональных элементов
В современной технике и, прежде всего, в вычислительной технике имеется целый арсенал средств и методов для реализации булевых функций, систем булевых функций и других более сложных дискретных функций. Обычно “массовым тиражом” в виде некоторых “элементов” реализуется сравнительно небольшой набор “элементарных” функций. Эти “элементы” действительно могут представлять собой простейшие вычислительные устройства (например, транзисторы или переключатели), а могут являться достаточно крупными системными блоками. Далее из этих элементов по определенным правилам собираются крупные вычислительные устройства (схемы), способные выполнять сколь угодно сложные преобразования информации.
В математической кибернетике и дискретной математике изучаются математические модели устройств, осуществляющих преобразование информации. Одной из самых простых и вместе с тем распространенных моделей являются схемы из функциональных элементов. Они предназначены в первую очередь для вычисления булевых функций либо систем булевых функций, хотя могут быть использованы и для вычисления функций более сложной природы. Содержательно схема из функциональных элементов (сокращенно СФЭ) представляет собой геометрический объект, составленный из полюсов (входы схемы), треугольников либо квадратов, изображающих функциональные ■I Iэлементы, и дуг либо отрезков прямых,
IIкоторые соединяют полюса, входы и вы-
YV у ходы функциональных элементов (“про-водники” схемы).
I Прежде чем дать точное определе- ! ние схемы из функциональных элемен- абв тов, приведем определение вспомогатель
ного объекта — сети. Сеть позволяет Рис‘ ^описать строение СФЭ безотносительно
к ее функционированию. Итак, сеть состоит из полюсов и элемен
тов, которые могут соединяться в сети дугами или отрезками прямых. Полюса будем изображать маленькими кружками (рис. 2, а). Для упрощения изложения элементы будем рассматривать только с
одним или двумя входами. Элементы изображаем в виде треугольников (рис. 2, б, в) с двуми или тремя стрелками. Стрелка, ведущая в элемент, соответствует входу элемента, ведущая из элемента — его выходу.
Еще раз подчеркнем, что на этапе определения сети нас совершен
но не интересует ни возможное техническое происхождение полюсов и элементов, ни отношение сети к булевым функциям и способам их вычисления. На этом этапе мы рассматриваем лишь способ соединения
полюсов и элементов в схеме, или, как гi
говорят, топологию схемы.|j
По индукции определим сеть и i।
множество вершин сети.J
Полюс есть сеть. Он является
единственной вершиной этой сети.Рис- 3
Пусть Ei, Е2 — две сети без общих вершин. Тогда формальное объединение сетей Ei, Е2 дает новую сеть (рис. 3). Вершинами этой сети являются все вершины сетей Ei и Е2.
Пусть Е — сеть, а Е — элемент, входы и выход которого не являются вершинами сети Е. Тогда результат присоединения (или отождествления) всех входов элемента Е к некоторым вершинам сети Е есть сеть (рис. 4, где показан элемент Е с двумя входами).
X1X1При этом в случае элемента Е с двумя входами оба входа элемента Е могут быть присоединены к одной и той же вершине сети Е, однако каждый вход должен присоединяться только к одной вершине. Вершинами новой сети являются все вершины сети Е и выход элемента Е.
X1
X1
Непосредственно из определения вытекают следующие два свойства сети.
1°. Никакой элемент сети не присоединен своим выходом ни к полюсу, ни к выходу другого элемента сети.
2°. Вершины сети можно занумеровать натуральными числами так, что выход любого элемента будет иметь номер, больший, чем номер каждого из его входов. Поэтому в сети невозможно найти последовательность вершин щ,^ • • • ^т такую, что ат = щ и при 1 ^ з < т вершина aj является входом некоторого элемента, a Hj+i — его выходом. Иными словами, сеть не содержит ориентиро-
ванных циклов, составленных из элементов.
Перейдем теперь к определению схемы из функциональных элементов. Схемой из функциональных элеметов называется сеть в которой:
каждому полюсу приписана одна из переменных Xi,...,хп,...,
причем различным полюсам приписаны различные переменные; полюса сети называются входами схемы;
каждому элементу Е с одним или двумя входами приписана некоторая функция /^, зависящая соответственно от одной или двух
переменных; функция Фе называется функцией элемента Е; элемент Е с приписанной ему функцией Фе называется функциональным элементом;
некоторым вершинам сети приписаны натуральные числа 1, 2,..., т, причем одной и той же вершине может быть приписано неколько чисел; вершины, которым приписаны числа 1,... ,ш, называются выходами схемы; l-м выходом схемы называется (единственный) выход, которому приписано число I (возможно, что этой вершине приписаны и другие числа).
Так же, как для формул, по индукции дадим определение функции, реализуемой СФЭ. При этом будем сопоставлять вершинам схемы булевы функции.
Каждому входу сопоставляется функция, равная той переменной, которая приписана этому входу.
Пусть всем вершинам, к которым присоединены входы элемента Е, уже сопоставлены функции (реализуемые в этих вершинах). Тогда выходу элемента Е сопоставляется функция фв(ф^) или ЫГМ^Ч где Фе — функция элемента Е, а ф^ — функция, сопоставленная той вершине, с которой соединен г-й вход элемента Е (рис. 5).
В результате этого процесса каждой вершине будет сопоставлена некоторая булева функция. По определению схема реализует упорядоченную систему функций (вектор-функцию)
Г(жЬ . . . ,ЖП) = (/1(Ж1,...,Жп),...,/т(Ж1,...,Ж„)),
где Л(®1, ■ ■ ■, #п) — функция, сопоставленная г-му выходу схемы.
Свойства 1°, 2° сети могут быть положены в основу более абстрактного определения схемы из функциональных элементов, которое не использует геометрических понятий. Будем рассматривать два типа переменных: входные х^х^... и рабочие у\^ у^... Схемой из функциональных элементов назовем теперь такую последовательность 2^1,..., гт+п входных и рабочих переменных, которая имеет вид Ху ... хпу\ ... ут^ причем если г^ не является входной переменной, то числу г сопоставлены либо число у (1 ^ у < г) и булева функция gi(zj) от одной переменной, либо два числа у, к (1 ^ у, к < г) и булева функция gi^Zj^Zk) от двух переменных. Так же, как и для СФЭ в исходном определении, каждой переменной z^, по индукции сопоставляется единственная булева функция /фжх,..., хп\ значения которой будут равны значениям переменной Zi в этой схеме.
Если функции всех элементов схемы Е принадлежат множеству функций Q, то говорят, что схема Е есть схема в базисе Q. Заметим, что в отличие от определения базиса, приведенного в гл. I, в этом параграфе мы не предполагаем функции базиса независимыми. В частности, в дальнейшем рассматриваем СФЭ исключительно в базисе Qo = {^, ху^ х V yY
Так же, как и для ДНФ, при изучении СФЭ основной задачей является построение для заданной булевой функции (или множества булевых функций) схемы (схем) наименьшей сложности. При этом под сложностью схемы Е понимается число всех функциональных элементов, входящих в схему Е. Сложность схемы Е будем обозначать через Е(Е). Пусть далее L(F) обозначает минимум из величин L(E), где минимум берется по всем схемам Е, реализующим систему функций F. Положим
L(n) = maxL(/), где максимум берется по всем функциям /(жх,..., хп\ зависящим от п переменных. Функция L^ носит название функции Шеннона. Она играет важнейшую роль в теории синтеза управляющих систем. Величина Ь(п), как это следует из определения, равна наименьшей сложности, с которой заведомо можно реализовать любую булеву функцию от н переменных. Как и для ДНФ, точное значение L(n) можно найти, последовательно перебирая все функции / от п переменных и находя для каждой из них величину L(f). Следует отметить, что к настоящему времени не известно никаких непереборных
алгоритмов для точного вычисления функции L(n). Более того, существует гипотеза, что перебор в этой задаче в принципе неустраним. Наша дальнейшая цель состоит в оценках сверху величин L(n) и L(F) для некоторых функций F.
Рис. 6Рис. 6
Рис. 6
Рис. 6
Используя моделирование совершенной ДНФ, оценим, прежде всего, величину Цп). Будем называть конъюнктором, дизъюнктором и инвертором элементы, которым сопоставлены соответственно функции &, V, ”.
Пусть К = жр & ... & х^г — элементарная конъюнкция. Нетрудно видеть, что ее можно реализовать СФЭ, состоящей не более чем из п инверторов и п — 1 конъюнкторов (рис. 6). Если сц = 0, то г-й вход схемы присоединен к инвертору, в противном случае инвертора, соответствующего г-у входу схемы, нет и г-й вход присоединяется к конъюнктору. Очевидно, что
(36)(36)ЦК) ^2п-1.
(36)
(36)
Пусть /(жх,..., жп) — произвольная булева функция, отличная от константы 0, и Ку V ... V Кт — ее совершенная ДНФ. СФЭ для функ
ции / строится из т схем для конъюнкций Kj и цепочки из т — 1 дизъюнкторов, которая “объединяет” выходы схем для конъюнкций (рис. 7). Таким образом, учитывая неравенство (36), приходим к следующему утверждению.
Если совершенная ДНФ функции f(xy,..., хД содержит т (т ^ 1) конъюнкций, то
L(f) < 2тп.
Так как всегда т ^ 2П, то для произвольной функ
ции Дху,...,хД, не равной тождественно 0, имеемЦЛ < п2п^.
Функция, тождественно равная 0, может быть ре
ализована схемой, изображенной на рис. 8. Поэтому
Существенно лучшую оценку для ЕД^ можно получить, если воспользоваться индуктивным процессом разложения функции по переменной. В самом деле, легко видеть (рис. 9), что L(l) = 2. Если же
Х1Х1Х1Х1Х1Х1
Х1Х1
Х1Х1
Х1
Х1
п ^ 2, то разложим произвольную функцию /(жх,..., жп) по переменной хп:
. .,Хп-1,Хп) = хп& Kxi,.. . ,Хп-1,1) V хп & Джх, . . . ,Жи-1,0), и обозначим для краткости функции f(xi,... ,xn_i, 1) и /(жх,... ■ ■ ■ ,жп-1,0) через /' и
На рис. 9 показано, как из схем, реализующих функции f* и f1^ получить схему, реализующую функцию /. Из нее видно, что
Цп) 2 • L(n — 1) + 4.
Это рекуррентное соотношение вместе с условием L(l) = 2 дает
Цп) < 3 • 2П - 4.
Отметим, что более тонкие методы синтеза схем позволяют установить, что при больших значениях п величина L(n) будет близка к величине 2п/п. Как говорят в подобных случаях, L(n) асимптотически равна 2П/п.
Общая теория синтеза СФЭ показывает, что для “почти всех” булевых функций от п переменных минимальная сложность реализующих их схем близка к величине L(n). На этом фоне представляют интерес функции, сложность реализации которых схемами существенно мень
ше, чем L(n), например, имеющие линейную (по п) сложность. К последним функциям относится двоичный сумматор — вектор-функция,
вычисляющая двоичные разряды 2у,..., zn, гп+1 суммы п-разрядных чисел ж, у, заданных в двоичной системе счисления представлениями хп ... Ху и уп .. .уу (старшие разряды этих представлений могут быть нулевыми). Сложение чисел ж, у можно осуществить “столбиком”, обозначая через щ,..., Qn+i результаты переносов из предыдущих разрядов (qy = 0):
(Qn+iQn...qi)
+ xn...Xy
Уп...У1
^n+l^n• • •^1
Очевидно, что
Zi = Xi®Ui®qi, qi+i = xtyiV XiQiV ytqt.(37)
Опираясь на тождество
Xi Ф Уг ® qi = X^i V XiQi V ^qi k (Xi VyiV Qi) V Xtytqi,
нетрудно построить СФЭ, реализующую преобразования (37) (рис. 10). Обозначим соответствующую схему через Bi (1 < г ^ п).
Хп УпХ2 У2Ху уу
Рис. 11
Тогда схема Еп для двоичного сумматора n-разрядных чисел получается путем последовательного соединения блоков Bi (рис. 11). Здесь гп+1 = Qn+i, ^ схема By осуществляет преобразование
= (Ж1 & уу) k (xy V уу), q^ = Xykyy.
Очевидно, что L(By) = 4 и L^Bi) = 9 при 1 < г ^ п. Таким образом,Ц^п) 9(п — 1) + 4 = 9п — 5.
УПРАЖНЕНИЯ
Постройте СФЭ, реализующую функцию Ху ф ... ф хп (п ^ 2) со сложностью 4 (п — 1).
Докажите, что существует такая константа С, что для любой
симметрической функции /, зависящей от п переменных, справедлива оценка Ь(/) ^ Сп (определение симметрической функции см. В упр- 5).
Выполнимость КНФ
В начале 70-х годов в ряде разделов математики (теория алгоритмов, теория булевых функций, теория графов, теория чисел, линейное программирование и др.) было обнаружено большое число задач (сейчас их насчитывается свыше 800), которые обладают следующими отличительными особенностями.
Каждая из задач представляет собой по форме массовую задачу переборного типа. Если для любой из этих задач каким-либо образом “угадано” решение, то проверка того факта, что найденное решение действительно удовлетворяет условиям задачи, требует полиномиального (от длины записи входных данных) числа шагов. Наконец, все эти задачи, как говорят, полиномиально эквивалентны. Это следует понимать так. Пусть, например, задачи А и В представляют собой поиск для заданного двоичного набора а некоторого набора Ь, который по отношению к а обладает заданным свойством. Тогда должны существовать полиномы pi (п) и р2 (п) с натуральными коэффициентами и такие алгоритмически вычислимые функции /1(ж), /2 (ж), отображающие множество всех двоичных наборов в себя, что, во-первых, функции /1(ж), /2 (ж) можно вычислить подходящими алгоритмами, которые для любого двоичного набора длины п заканчивают работу соответственно не более чем через pi(п) или P2(ti) шагов. А во-вторых, для произвольного двоичного набора ж задача А (соответственно задача В) имеет решение тогда и только тогда, когда для двоичного набора /1(ж) (для /2^)) имеет решение задача В (задача А). О функциях /1 (ж), /2 (ж) говорят, что они полиномиально сводят задачу А к задаче В и задачу В к задаче А.
Все эти многочисленные задачи из различных разделов математики в научной литературе получили название Л^Р-полных проблем (от английских слов Nondeterministic Polynomial). В теории булевых функций одной из “канонических” А^Р-полных проблем является проблема выполнимости конъюнктивных нормальных форм (сокращенно ВЫПОЛНИМОСТЬ). Содержательно эта проблема состоит в том, чтобы по произвольной конъюнктивной нормальной форме (определение КНФ см. в § 8 гл. I) выяснить, существует ли двоичный набор, обращающий эту КНФ в 1 (выполняющий КНФ). Ясно, что проблему ВЫПОЛНИМОСТЬ можно решить тривиальным алгоритмом, перебирая для заданной КНФ АГ, зависящей от п переменных, все 2П двоичных наборов длины п и вычисляя для каждого из них значение формулы К. Понятно также, что проверка выполнимости КНФ К
на заданном двоичном наборе требует сравнительно небольшого (по отношению к размеру формулы К) числа шагов: следует вместо каждой из переменных формулы К подставить соответствующее значение 0 или 1 из рассматриваемого набора и затем вычислить значение каждой дизъюнкции, входящей в К, пользуясь хорошо известными соотношениями
6 = 1, 1 = 0, 0V0 = 0, OV1 = 1VO = 1V1 = 1.
Все эти действия можно выполнить, например, за квадратичное (относительно длины записи формулы К) число шагов.
Строгое доказательство Л^Р-полноты проблемы ВЫПОЛНИМОСТЬ требует привлечения понятий недетерминированной машины Тьюринга и полиномиального вычисления на такой машине, что выходит за рамки данной брошюры. Мы ограничимся лишь рассмотрением двух важных частных случаев проблемы ВЫПОЛНИМОСТЬ: 2-ВЫПОЛНИМОСТЬ и 3-ВЫПОЛНИМОСТЬ (сокращенно 2-ВЫП и 3-ВЫП). Проблема 2-ВЫП получается из проблемы ВЫПОЛНИМОСТЬ, если в последней рассмотреть лишь такие КНФ, у которых каждый конъюнктивный сомножитель содержит не более двух переменных. Аналогичным образом определяется проблема 3-ВЫП. Далее мы докажем, что проблема 2-ВЫП полиномиально разрешима (это означает, в частности, что проблема 2-ВЫП не является проблемой переборного типа), а проблема 3-ВЫП А^Р-полна.
Начнем с проблемы 2-ВЫП. Итак, будем рассматривать лишь такие КНФ К, у которых каждый конъюнктивный сомножитель имеет вид х? или х? У х^, где ст, т G {0,1}. Алгоритм проверки выполнимости формулы К будет состоять из нескольких этапов, число которых не превосходит числа переменных, входящих в формулу К. Каждый этап характеризуется некоторой переменной из К. На каждом этапе происходит либо удаление из К некоторых конъюнктивных сомножителей, либо удаление переменной, однако в последнем случае могут появиться дополнительные конъюнктивные сомножители. Число таких дополнительных сомножителей не превосходит квадрата от числа переменных, входящих в исходную формулу К. После проведения каждого этапа образуется КНФ К', которая выполнима или невыполнима одновременно с КНФ К. На заключительном этапе будет получена формула от одной переменной, выполнимость которой определяется тривиальным образом.
Сначала рассмотрим этапы, когда в формулу К входит однобуквенный сомножитель вида х или х. Пусть для определенности это будет сомножитель х. Найдя такой сомножитель в формуле К, просмотрим формулу К и выделим в ней все остальные сомножители, содержащие переменную х. Если среди них есть сомножитель ж, то, очевидно, формула К невыполнима. Тогда завершаем работу алгоритма, давая отрицательный ответ на вопрос о выполнимости формулы К.
Пусть сомножителя х в формуле К нет. Пользуясь эквивалентностями (слева направо)
х & (х V уа) = х, х & (х V уа) = х & уа, производим сокращения в КНФ К: либо вычеркиваем сомножитель xV^, либо заменяем сомножитель хУ уа сомножителем у°. В образовавшейся после этих преобразований формуле приводим одинаковые сомножители и получаем КНФ К*. Поскольку формула К* получается из формулы К применением некоторых эквивалентных преобразований, формула К* будет эквивалентна формуле К. Однако она содержит меньше символов, чем формула К. Кроме того, весь процесс построения формулы К* из формулы К требует заведомо не более Суп2 “элементарных” действий, где Су — натуральная константа, а п — длина записи формулы К. При этом под элементарным действием мы понимаем сравнение символов в формуле, перемещение внутри формулы на один символ влево или вправо, вычеркивание одного символа и т.п.
Пусть теперь в формуле К однобуквенные сомножители отсутствуют. Возьмем произвольную переменную ж, входящую в формулу К. Пусть Ко представляет собой конъюнкцию всех сомножителей из К вида х V у (здесь у может быть как символом переменной, так и ее отрицанием):
Ко = (ж V У1) & ... & (ж V укУ
Ку представляет аналогичную конъюнкцию сомножителей вида ж\/г:
Ку = (ж V 2у) & ... & (ж V 27);
К^ представляет конъюнкцию всех остальных сомножителей из К. Тогда
К = Ко к Ку к К2.
Если, например, конъюнкция Ко пуста (соответствующих сомножителей вида х V у в формуле К нет), то конъюнкция Ку выполнима при х = 1. Следовательно, формула К будет выполнимой тогда и только тогда, когда выполнима КНФ К2. Поэтому в качестве КНФ К* можно взять КНФ К2^ которая получается из КНФ К вычеркиванием всех сомножителей, входящих в Ку. Аналогично рассуждаем, если пуста конъюнкция Ку.
Предположим, что обе конъюнкции Ко, Ку непусты. Имеем
(ж V щ) & ... & (ж V ук) = х V уу & ... & ук,
(ж V Z1) & . . . & (ж V Z/) = Ж V Zy & . . . & Z[.
Далее, формула вида (ж V У) & (ж V Z) выполнима в том и только том случае, когда выполнима формула У V Z. Следовательно, формула К будет выполнима тогда и только тогда, когда будет выполнимой формула
(уу & ... & ук V zy ^ ... & z^ & К2.
Однако
У1 & ... & yk V . & Zi = & & (yiV Zj). l^i^k l^j^l
Таким образом, вопрос о выполнимости формулы К сводится к аналогичному вопросу для формулы
К' = ( & & (№Vz,))&K2.
В формулу К* не входит переменная х и, как видно из сравнения формул К и К* в формулу К* добавляется не более 2kl новых вхождений символов у^ Zj. Поскольку kJ ^ п (напомним, что п — длина записи формулы К\ длина записи формулы К* увеличивается по сравнению с длиной записи формулы К не более, чем на 2п2. Из описания процесса построения формулы К* следует также, что формулу К можно преобразовать в формулу К* не более, чем за С^п2 “элементарных” действий, где С^ — натуральная константа.
Таким образом, последовательно применяя к исходной КНФ К описанные выше этапы преобразований, мы не далее, чем на (п — 1)-м этапе либо убедимся в невыполнимости формулы К, либо придем к формуле вида ж, ж, ж V ж, ж & ж от одной переменной. В первых трех случаях имеем, очевидно, выполнимость формулы К, в четвертом случае — невыполнимость. В целом весь процесс проверки выполнимости формулы К займет не более, чем С • п2 • п = Сп3 “элементарных” действий, где С = max(Ci, С «Jr Тем самым мы установили, что проблему 2-ВЫП можно решить, произведя примерно Сп3 элементарных действий, где п имеет смысл длины записи исходной КНФ. Иными словами, проблема 2-ВЫП является полиномиально разрешимой.
Рассмотрим теперь проблему 3-ВЫП и докажем, что она является Л^Р-полной. Наше доказательство будет относительным, поскольку мы предполагаем А^Р-полной проблему ВЫПОЛНИМОСТЬ. Очевидно, что проблема 3-ВЫП полиномиально сводится к проблеме ВЫПОЛНИМОСТЬ: соответствующая сводящая функция /(ж) по каждой КНФ, имеющей не более трех дизъюнктивных слагаемых в каждом конъюнктивном сомножителе, выдает в качестве результата эту же самую КНФ. Докажем, что проблема ВЫПОЛНИМОСТЬ также полиномиально сводится к проблеме 3-ВЫП. С этой целью продемонстрируем, как за полиномиальное число шагов преобразовать произвольную КНФ К в такую КНФ К1 с не более чем тремя слагаемыми в каждом сомножителе, что К и К' выполнимы или невыполнимы одновременно.
Очевидно, что можно ограничиться рассмотрением только таких КНФ, у которых имеются сомножители, содержащие более трех дизъюнктивных слагаемых. Пусть С = у\ V ... V ут — один из таких сомножителей в формуле К (у у,..., ут могут быть здесь как переменными, так и отрицаниями переменных). Обозначим через Ку
КНФ, которая получается из КНФ К вычеркиванием сомножителя С. Пусть и — переменная, не входящая в К. Положим
D = (У1 V у2 v и) & (уз V ... V ут V й).
Покажем, что КНФ К выполнима тогда и только тогда, когда выполнима КНФ D & Ку.
Пусть набор а = (щ,..., ап) обращает КНФ К в 1. Тогда, в частности, набор а обращает в 1 дизъюнкцию С. Если набор а обращает в 1 формулу т/1 V т/2, то набор (ах,..., ап, 0) будет обращать в 1 формулу D и, следовательно, формулу D ^Ку (последний разряд набора (щ,..., ап, 0) отвечает переменной tz). Если же набор а обращает в 1 формулу т/з V ... V т/п, то аналогичное утверждение будет справедливо для набора (щ,..., an, 1).
Обратно, пусть (ai,... , ап, Ь) — набор, обращающий в 1 КНФ D & Ку. Если b = 0, то набор а обращает в 1 формулу т/i V т/2 и, следовательно, формулу С. При b = 1 то же самое будет справедливо для формул т/з V ... V ут и С.
Описанное преобразование уменьшает на 1 число слагаемых в сомножителе т/з V ... V ут V й. полученном из С, и увеличивает на 2 общее число букв в КНФ D & Ку по сравнению с КНФ К. Если в КНФ К имеется к сомножителей соответственно с числом слагаемых тих, • • •,тп^ где Till,...,т^ > 3, то достаточно аналогичным способом добавить не более 2 (ttzi + ... + т^ — ЗА;) букв с тем, чтобы получить требуемую КНФ К* выполнимую или невыполнимую одновременно с КНФ К. То, что преобразование формулы К в формулу К* можно выполнить за полиномиальное число действий, очевидно.
5 С.С. Марченков
ОТВЕТЫ, РЕШЕНИЯ, УКАЗАНИЯ
22"-\
Набор (1011) определяет импликацию Ж2 —^ жх, набор (1001) — эквивалентность жх ~ Ж2, набор (1000) — функцию жх ^ Ж2, называемую стрелкой Пирса (или анттдиз^нткциейУ
Функция щ(жх,Ж2,жз) существенно зависит от переменных Жх, Жз, функция ^2(^1, ^2, ^з) — ОТ переменных Жх, Ж2, Ж3.
Существенные (фиктивные) переменные функций / и g совпадают. Чтобы в этом убедиться, достаточно заметить, что если а^ = = /(Ьх, • • •, ^n) (1 ^ £ ^ 2П), то at = g(bi,..., Ьп\ Поэтому из равенств йк = / (61,..., Щ1,0Д+1,... ,bn), щ = f(bi,...,bj-bl-,bj+i,...,M следуют равенства
ак = д(Ьъ... ,^-х, 1Лнъ • • -Лп^ at = g^,..., ^_х, 0, ^+1,.. . Лп\ Значит, из существенной зависимости функции /(жх,...,жп) от переменной Xj вытекает существенная зависимость функции ^(жх,..., жп) от переменной ж^-, и наоборот.
Пусть /(жх,...,жп) — симметрическая функция, отличная от константы. Тогда для некоторого т (0 ^ т < п) и некоторого а из множества В функция / принимает значение а на всех двоичных наборах, содержащих т единичных компонент, и значение а на всех двоичных наборах, содержащих т + 1 единичных компонент. Теперь для доказательства утверждения достаточно для любого г (1 ^ г ^ п) рассмотреть двоичные наборы, содержащие т и т + 1 единичных компонент и различающиеся только в г-ой компоненте.
hi(xi,x2) = 1, ^2(^1,^2,^з) = Жх Ф Жз ф 1.
Ни при одном п (п ^ 3).
а) и в) являются, б) не является.
Неверно. Например, объединение замкнутых классов То и Су не содержит функцию ж, которая получается суперпозицией функций ж ф у из класса То и 1 из класса Су.
xyz ф жг фу ф г ф 1 = жг V жг • у V xz • у У xz - у.
xyz V xyz V xyz V xyz V xyz.
Если
/(Н1, . . . , G^ — 1, О, G^-|-l 1 • • • 1 CLn^ — Ь, f (Gi, . . . , G/ —1,1, G^-j-l, . . . , Gn) — b,
TO_
/ (Gi, . . . , G^ —1,1, G/-|-l, . . . , Gn) — b,
/ (Gi, . . . , G^ —1,0, G^-j-i, . . . , Gn) — Ь.
Верно.
(xi v...v^)ei.
xyzw Ф xyw Ф xzw Ф yzw Ф xz Ф xw Ф w Ф 1.
Имеется четыре самодвойственные функции f(xi, Ж2), которые задаются двоичными наборами
(ООП), (0101), (1010), (1100).
Это суть соответственно функции Xi, Ж2, xs, Ху.
При любом и (тг ^ 3) функция f(xi,..., хп\ задаваемая полиномом Жегалкина
Ж1Ж2 Ф Ж1Ж3 Ф ж2ж3,
принимает значение 1 ровно на 2П-1 наборах. Если п ^ 2, то любая функция от п переменных, принимающая значение 1 ровно на 2П-1 наборах, является линейной.
Имеется 20 монотонных функций от трех переменных:
0, 1, х, у, z, xVy, xV z, yV z, xy, xz, yz, xV у V z, xyz,xVyz, yVxz, zV xy, x(yVz), y(xVz), z(xVy), xy V xz V yz.
Пусть функция f(xi,..., xn) монотонна и (gi ,..., Gn) ^ (bi,. . . ...,bny Тогда
(bi,. ..,bn)< (gi, ... ,Gn), f(bi,... A) < f(a,i,. ..,an)
и, следовательно,
/А,...,Gn) < / А,...,ьп(
0, 1, e^(xi,...,xn) (1 < г < n, n = 1,2,...).
Например, {1, x ф у, x V y}.
Из непринадлежности функции f(xi,... ,xn) классам 7q, Ti следует, что /(0,..., 0) = 1 и /(1,..., 1) = 0. Таким образом, / не является монотонной функцией. Если бы функция / была линейной, т.е.
/А , . . . , Хп) = Жц Ф . . . Жд Ф G,
то из условия /(0,..., 0) = 1 вытекало бы, что g = 1, а из условия /(!,...,!) = 0, что s — нечетное число. Однако тогда / была бы самодвойственной функций. Если вместо класса S взять класс L, то
утверждение становится неверным. Это видно на примере самодвойственной функции ху В ж г В yz В 1.
Сокращенная ДНФ есть
ху V ху V xz V xz V yz V yz, минимальные —
xyVxzV yz, xyVxzV yz, тупиковые неминимальные —
ху V ху V yz V yz, xz V xz V yz V yz, ху V ху V xz V xz.
Взять за основу схему, изображенную на рис. 5.
Любую симметрическую функцию /(ж1,...,жп) можно задать набором чисел (Л,..., гт) таким, что 0 ^ Л < ... < гт ^ п и /(п1,...,пп) = 1 тогда и только тогда, когда количество единиц в наборе (п1,...,пп) есть число из набора (ii,...,im). В связи с этим сначала следует построить схему линейной сложности, которая для любого двоичного набора (ai,... ,ап) вычисляет двоичные разряды bi,... ,br числа ay В ... В ап (сложение арифметическое, а не по модулю 2).
Тогда г = [log2 п\ В 1, где [d] обозначает целую часть числа d, и по набору (bi,... ,ЬТ) можно однозначным образом определить значение f(ai,.. .,ап).
Вторая схема линейной сложности осуществляет преобразование (bi,. ..,bT)^ f(ai,... ,ап).
ОГЛАВЛЕНИЕ
Предисловие 3
Глава!
ЭЛЕМЕНТАРНЫЕ СВОЙСТВА БУЛЕВЫХ ФУНКЦИЙ
Табличное задание булевых функций 5
Некоторые элементарные булевы функции 7
Существенные и фиктивные переменные 9
Представление булевых функций формулами 12
Эквивалентность формул 15
Замыкание. Замкнутые классы 18
Разложение булевой функции по переменной 21
Двойственность. Принцип двойственности 23
Полиномы Жегалкина 26
Глава II
ЗАМКНУТЫЕ КЛАССЫ И ПОЛНОТА
Класс самодвойственных функций 30
Класс линейных функций 31
Класс монотонных функций 34
Критерий полноты 38
Замкнутые классы, содержащие константы 40
Г л а в а III
СЛОЖНОСТЬ РЕАЛИЗАЦИИ БУЛЕВЫХ ФУНКЦИЙ
Минимизация ДНФ 45
Схемы из функциональных элементов 52
Выполнимость КНФ 61
Ответы, решения, указания 65
Учебное издание
МАРЧЕНКОВ Сергей Серафимович
БУЛЕВЫ ФУНКЦИИ
Редактор Е.Ю. ХоданОригинал-макет Д.В. ГорбачеваОформление обложки А.К). Алехиной
ЛР №071930 от 06.07.01. Подписано в печать 23.05.02.
Формат 60x90/16. Бумага офсетная № 1. Печать офсетная.
Усл. печ. л. 31. Уч.-изд. л. 34,1. Тираж 3000 экз. Заказ №
Издательская фирма
« Физико-математическая литература»МАИК «Наука/Интерпериодика»117864 Москва, ул. Профсоюзная, 90
Отпечатано в ФГУП«Производственно-издательский комбинат ВИНИТИ»140010, г. Люберцы, Московская обл., Октябрьский пр-т, 403
В серии «Популярные лекции по математике» в разные годы вышли следующие книги.
Маркушевич А.И. Возвратные последовательности.
Натансон Н.П. Простейшие задачи на максимум и минимум. Соминский И. С. Метод математической индукции.
Маркушевич А.И. Замечательные кривые.
Коровкин Н.П. Неравенства.
Воробьев Н.Н. Числа Фибоначчи.
Курош А.Г. Алгебраические уравнения произвольных степеней.
Гельфонд А. О. Решение уравнений в целых числах.
Маркушевич А.И. Площади и логарифмы.
Смогорснсевский А.С. Метод координат.
Дубнов Я. С. Ошибки в геометрических доказательствах.
Натансон Н.П. Суммирование бесконечно малых величин.
Маркушевич А.И. Комплексные числа и конформные отображения. Фетисов А.И. О доказательствах в геометрии.
Шафаревич ИТ. О решении уравнений высших степеней.
Шерватов ВТ. Гиперболические функции.
Болтянский ВТ. Что такое дифференцирование?
Миракьян Г.М. Прямой круговой цилиндр.
Люстерник Л.А. Кратчайшие линии.
Лопшиц А.М. Вычисление площадей ориентированных фигур.
Головина Л.И., Яглом И.М. Индукция в геометрии.
Болтянский ВТ. Равновеликие и равносоставленные фигуры. Смогорснсевский А.С. О геометрии Лобачевского.
Аргунов Б.И., Скорняков Л.А. Конфигурационные теоремы. Смогорснсевский А.С. Линейка в геометрических построениях. Трахтенброт Б.А. Алгоритмы и машинное решение задач. Успенский В.А. Некоторые приложения механики к математике. Архангельский И. А., Зайцев Б.И. Автоматические цифровые машины.
Костовский А.Н. Геометрические построения одним циркулем. Шилов Г.Е. Как строить графики.
Дорфман АТ. Оптика конических сечений.
Вентцель Е.С. Элементы теории игр.
Барсов А. С. Что такое линейное программирование.
Маргу лис В.Е. Системы линейных уравнений.
Виленкин Н.Я. Метод последовательных приближений.
Болтянский В.Г. Огибающая.
Шилов Г.Е. Простая гамма (устройство музыкальной шкалы).
Шрейдер Ю.А. Что такое расстояние?
Воробьев Н.Н. Признаки делимости.
Фомин С.В. Системы счисления.
Коган В.Ю. Приложение механики к геометрии.
Любин Ю.И., Шор Л.А. Кинематический метод в геометрических задачах.
Успенский В.А. Треугольник Паскаля.
Бакельман И.Я. Инверсия.
Яглом И.М. Необыкновенная алгебра.
Соболь И.М. Метод Монте-Карло.
Калужнин Л.А. Основная теорема арифметики.
Солодовников А.С. Системы линейных неравенств.
Шилов Г.Е. Математический анализ в области рациональных функций.
Болтянский Б. Г, Гохберг Н.Ц. Разбиение фигур на меньшие части.
Бескин П.М. Изображения пространственных фигур.
Бескин Н.М. Деление отрезка в данном отношении.
Розенфельд Б. А., Сергеева Н.Д. Стереографическая проекция.
Успенский В.А. Машина Поста.
Беран Л. Упорядоченные множества.
Абрамов С.А. Элементы программирования.
Успенский В.А. Теорема Гёделя о неполноте.
Шашкин Ю.А. Эйлерова характеристика.
Скорняков Л.А. Системы линейных уравнений.
Шашкин Ю.А. Неподвижные точки.
Петросян Л. А.. Рихсиев Б.Б. Преследование на плоскости.
ПОПУЛЯРНЫЕ ЛЕКЦИИ ПО МАТЕМАТИКЕ
ВЫПУСК
С.С. МАРЧЕНКОВ
БУЛЕВЫ ФУНКЦИИ
МОСКВА, 2002
УДК 519.7
ББК 22.176
М25
Марченков С. С. Булевы функции.— М.: ФИЗМАТ ЛИТ, 2002.— 68 с.- ISBN 5-9221-0253-2.
Брошюра знакомит читателя с булевыми функциями — одним из важнейших классов дискретных функций. В ней излагаются основные понятия теории булевых функций, доказывается критерий функциональной полноты и рассматриваются вопросы сложности реализации булевых функций.
Брошюра предназначена для школьников старших классов и студентов первых курсов.
Табл. 4. Ил. 11.
ISBN 5-9221-0253-2ISBN 5-9221-0253-2© ФИЗМАТЛИТ, 2002
ISBN 5-9221-0253-2
ISBN 5-9221-0253-2
© С.С. Марченков, 2002