Глава 1

функция f принимает единичные значения, называется весом || f || этой функции:

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

Таблица 1. 2. 2.

Первая и четвѐртая функции называются тождественными константами, нулем и единицей, и обозначаются, соответственно, символами 0 и 1. Вторая функция называется тождественной и обозначается так же, как и ее аргумент, символом x. Третья функция называется отрицанием или инверсией. Каждую из перечисленных функций можно задать просто

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

Таблица 1. 2. 3.

Первая функция f& называется конъюнкцией. Эта функция часто также называется умножением. Вторая функция называется дизъюнкцией. Две следующие функции называются линейными. Первая из них - функция

f , называется суммой по модулю два, иногда ее также называют

исключающим или. Вторая функция f~ называется эквивалентностью. Пятая функция называется штрихом Шеффера, шестая - стрелкой Пирса,

седьмая - импликацией.

3. Переменная xi функции f(x1, … ,xn) называется существенной, ственная если найдутся такие булевы постоянные u1, … , ui-1, ui+1, ... , un, что

f(u1, … , ui-1, 0, ui + 1, … ,un) ≠ f(u1, … , ui-1, 1, ui + 1, … ,un)

Несущественная переменная называется также фиктивной. Нетрудно показать, что если функция f имеет фиктивную переменную, то || f || - четное число. Действительно, пусть xi - фиктивная переменная f. Тогда

Пример 1.2.1. Найдем число функций принадлежащих существенно зависящих от всех своих переменных. Искомое число обозначим через N. Пусть Ai - множество всех тех функций из P2(n) для которых переменная xi не является существенной. Очевидно, что N равно

функций зависящих, не обязательно существенно, только от последних n - k переменных xk+1, … ,xn. Поэтому, легко видеть, что мощность рассматриваемого множества равна числу функций в P2(n - k), т.е.

почти все булевы функции из P2(n) существенно зависят от всех своих переменных.

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

Если для функций f(x1, … , xn) и g(xk + 1, … , xn) при всех возможных значениях переменных xk + 1, … , xn справедливо равенство

f 1,..., k , xk 1,..., xn g xk 1,..., xn .

то будем говорить, что функция g получена из функции f подстановкой констант 1,..., k вместо переменных x1, … , xk. Функцию g будем

называть

подфункцией функции f. Очевидным образом данное определение распространяется на случай подстановки констант 1,..., k вместо переменных x1, … , xk .

Пример 1.2.2. Найдем все возможные подфункции линейной функции f (x, y). Для этого подставим вместо первой переменной 0 и 1. В

подставляя константы вместо второй переменной получим функции x и f x . Очевидно, что подставляя константы одновременно вместо x и y,

получим только константы 0 и 1. Таким образом, у функции f есть ровно шесть подфункций: 0, 1, x, y, f x и f y .

Если для функций f(x1, … , xn) и g(x, xk + 1, … , xn) при всех возможных значениях переменных xk + 1, … , xn справедливы равенства

f 0,...,0, xk 1,..., xn g 0, xk 1,..., xn ,

f 1,...,1, xk 1,..., xn g 1, xk 1,..., xn ,

то будем говорить, что функция g получена из функции f отождествлением переменных x1, … , xk. Как и ранее, данное определение очевидным образом распространяется на случай отождествления произвольных переменных xi1 ,..., xik .

Пример 1.2.3. В булевой функции f(x1, x2, x3), заданной приводимой ниже таблицей, отождествим первую и третью переменные. Для этого в рассматриваемой таблице надо взять столбцы, в которых значения первой и третьей переменных совпадают. Такими столбцами будут1{Здесь полагаем, что символы x1, x2, x3 и f располагаются в нулевом столбце таблицы.} первый, третий, шестой и восьмой. После этого из этих четырех столбцов составим новую таблицу. В каждом столбце из двух одинаковых компонент, первой и третьей, оставим только первую, поставив ее в соответствие новой переменной x. Таблица значений получившейся функции g(x,x2) расположена справа внизу.

Таблица .

Легко видеть, что отождествив у функции f первую и третью переменные, получили сумму по модулю два переменной x2 и новой переменной x.

Рассмотрим булеву функцию f(x1, … , xn) с фиктивными переменными x1, … , xk и булеву функцию g(xk + 1, … , xn) получающуюся из f подстановкой констант 1,...,k вместо первых k переменных. Так как

Легко видеть, что дизъюнкция и конъюнкция являются

Среди симметрических пороговых функций особое место занимают функции n x1,..., x2n 1 , n 2 , называемые функциями голосования, или

функциями большинства.

6. Пусть D Bn. Функция f(x1, … , xn), определенная на области D и принимающая значения 0 и 1, называется частичной булевой функцией. Если набор x Bn и D, то будем говорить, что функция f не определена на этом наборе, или, что f принимает на нем неопределенное значение "*".

Как и обычную булеву функцию, частичную булеву функцию можно задать таблицей из 2n строк. Однако в таблице значений частичной функции

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

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

частичной функции, определенной на области D, есть 22n D различных доопределений.

Пример 1.2.4. Ниже приведены две частичные функции f1 и f2 и все их доопределения. Первая функция определена на двух наборах их четырех возможных, и поэтому имеет четыре доопределения, вторая функция определена на трех наборах и у нее два доопределения.

Таблицы.

7. Система булевых функций f = {f1, … , fm} называется булевым (m,n) - оператором. Функция fi называется i - й компонентой оператора f. Каждый булев (m, n) - оператор задает некоторое отображение Bn в Bm.

Задачи

1.2.1.Найти число различных булевых функций, зависящих от n аргументов и имеющих вес равный 1, 2, 3, [n/2].

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

1.2.3.Пусть булева функция f(x1, … , xn) задана вектором значений

f0 ,..., f2n 1 . Доказать, что если xi является фиктивной переменной, то

f j f2n 1 j для всех k 2n i 1 j 2k 1 2n i 1, где k = 0, 1, …, 2i- 1-1.

1.2.4. Пусть f(x1, … , xn) существенно зависит от k переменных. Показать, что || f || делится на 2n-k.

1.2.5 Найти P2 n число различных симметрических булевых функций, зависящих от n аргументов.

1.2.6.Показать, что существует ровно 2m2n булевых (m,n) -

операторов.

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

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

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

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

1.2.11.Найти число неравных полуфункций у функции, заданной вектором значений:

а) (0001011010010000); b) (1101011101010010); c) (1001011111111000).

1.2.12.Найти число булевых (m,n)-операторов таких, что f (x) 2

для каждого x Bn .

1.3. Формулы. Реализация булевых функций формулами

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

сними.

1.Пусть Xn = {x1, x2, … , xn} - множество булевых переменных, B - подмножество P2. Выражение F, составленное из символов переменных из Xn и из символов функций из B называется булевой формулой в базисе B над множеством переменных Xn, если F удовлетворяет следующему индуктивному определению:

1.Переменная xi является формулой (i {1, 2, … ,n});

2.Если f - k - местная функция из B и F1, … , Fk - формулы, то выражение

так же является формулой. Формулы F1, … , Fk называются подформулами формулы (1.3.1), а функция f - внешней функцией этой формулы. Любая подформула каждой формулы Fi так же называется подформулой формулы

F.

Индуктивно определим значение формулы F на наборе переменных x1, x2, …, xn:

1.Если F = xi, то F(x1, …, xn) = xi;

2.Пусть f B, F = f(F1, …, Fk) и значения формул F1, … , Fk на

переменных x1, …, xn определены.Тогда

F(x1, … ,xn) = f(F1(x1, …, xn), … , Fk(x1, …, xn)).

Булева формула F над множеством переменных x1, …, xn реализует булеву функцию f(x1, …, xn), если

F(x1, …, xn) = f(x1, …, xn)

при всех наборах (x1, …, xn) из Bn.

Пусть формула F, реализующая функцию f(x1, …, xn), составлена из символов переменных x1, …, xn и из символов функций f1, …, fm. Тогда говорят, что формула F и функция f являются суперпозициями функций f1, …, fm . Далее формулы и реализуемые ими булевы функции будем обозначать одними и теми же символами в тех случаях, когда это не будет приводить к неоднозначному пониманию.

Пример 1.3.1. Рассмотрим формулу F = f¬ (f& (f¬ (x1), f¬ (x2))) над множеством из двух переменных x1 и x2. В этой формуле вместо переменных x1 и x2 подставим различные булевы постоянные:

F(0, 0)=f¬(f&(f¬ (0), f¬(0))) = f¬ (f&(1, 1)) = f¬(1) = 0,

F(0, 1)=f¬(f&(f¬ (0), f¬(1))) = f¬ (f&(1, 0)) = f¬(0) = 1,

F(1, 0)=f¬(f&(f¬ (1), f¬(0))) = f¬ (f&(0, 1)) = f¬(0) = 1,

F(1, 1)=f¬(f&(f¬ (1), f¬(1))) = f¬ (f&(0, 0)) = f¬(0) = 1,

Сравнивая полученные значения со значениями функций из таблицы 1.2.3 видим, что формула f¬ (f& (f¬ (x1), f¬ (x2))) реализует дизъюнкцию переменных x1 и x2.

2. Важными характеристиками любой формулы являются ее сложность и глубина2. Сложностью l(F) формулы F в базисе B называется число символов из B входящих в F. Глубину d(F) формулы F определим индуктивно:

1.Если F = xi, то d(F) = 0;

2.Если F = f(F1, …, Fk), где f B, то

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

d F 1 max d Fi .

1i k

Пример 1.3.2. Пусть f1, f2 - двухместные булевы функции. Тогда выражения

F1 = f1 (x1, x2),

F2 = f2 (F1, x3) = f2 (f1(x1, x2), x3),

F3 = f2 (F2, F1) = f2 (f2(f1(x1, x2), x3), f1(x1, x2)),

являются формулами над множеством переменных {x1, x2, x3} в базисе {f1,

f2}.

Для сложностей и глубин этих формул справедливы следующие равенства:

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

Рис. 1.3.1

Так формулам F1, F2 и F3 из рассмотренного выше примера, соответствуют деревья, изображенные на рисунке 1.3.1. Первое из этих деревьев содержит одну внутреннюю вершину, второе - две, третье - четыре. Глубины этих деревьев равны соответственно единице, двойке и тройке.

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

Теорема 1.3.1. Пусть F - формула в базисе B = {f1, … ,fm}, k - максимальное число аргументов у функций из B. Тогда

d(F) ≥ [logk((k - 1)l(F) + 1)].

Доказательство. Теорему докажем индукцией по глубине формулы. Для формул нулевой глубины неравенство теоремы очевидно. Допустим, что теорема верна для любой формулы глубины r. Пусть F = f(