Понятие булевой функции

Булевы функции получили свое название по имени замечательного английского математика Джорджа Буля (1815—1864), который первым начал применять математические методы в логике.

Булевы функции от одного аргумента. Определение 9.1. Булевой функцией от одного аргумента называется функция f, заданная на множестве из двух элементов и принимающая значения в том же двухэлементном множестве. Элементы двухэлементного множества будем обозначать 0 и 1. Таким образом, f:{0,1}® {0,1}. Нетрудно перечислить все булевы функции от одного аргумента:

x	f 0 (x)	f 1(x)	f 2 (x)	f 3 (x)

Составленная таблица означает, что, например, булева функция f 2 на аргументах 0 и 1 действует следующим образом: f 2 (0) =1 и f 2 (1) =1.

Булевы функции от двух аргументов. Определение 9.2. Булевой функцией от двух аргументов называется функция g, заданная на множестве {0,1}´ {0,1} и принимающая значения в двухэлементном множестве {0,1}. Другими словами, булева функция от двух аргументов сопоставляет любой упорядоченной паре, составленной из элементов 0 и 1 (а таких упорядоченных пар будет четыре), либо 0, либо 1. Перечислим все возможные булевы функции от двух аргументов в форме следующей таблицы:

	X
	Y
	g 0
·	g 1
®`	g 2
x	g 3
`	g 4
y	g 5
+	g 6
Ú	g 7
¯	g 8
«	g 9
y '	g 10
	g 11
x '	g 12
®	g 13
|	g 14
	g 15

Определение 10.1. Булевой функцией от п аргументов называется функция f, заданная на множестве {0,1} n и принимающая значения в двухэлементном множестве {0,1}. Другими словами, булева функция от п аргументов сопоставляет каждому упорядоченному набору длины п, составленному из элементов 0 и 1, либо 0, либо 1. Булева функция f от п аргументов x 1,..., xn обозначается так: f (x 1,..., xn).

Две булевы функции от п аргументов f (x 1,..., xn)и g (x 1,..., xn)называются равными, если любым одинаковым наборам значений аргументов x 1,.., xn обе эти функции сопоставляют одинаковые элементы из множества {0, 1}, т.е. f (a 1,..., an)= g (a 1,..., an)для любых элементов a 1,..., an Î{0,1}.

Определение 10.2. Суперпозицией булевых функций в булеву функцию f (x 1,..., xn) называется новая булева функция, получающаяся из функции f (x 1,..., xn) подстановкой вместо (всех или некоторых) аргументов x 1,..., xn функций g 1,..., gn соответственно Полученная функция зависит от m 1 + m 2 +... + mn аргументов.

Опишем еще одну процедуру, которую можно проделывать с булевыми функциями. Зафиксировав один из аргументов булевой функции f (x 1,..., xn)от п аргументов, т.е. придав этому аргументу какое-нибудь конкретное постоянное значение (из двухэлементного множества {0, 1}), получим функцию от n -1 аргументов. Так, фиксируя в функции f (x 1,..., xn) k- й аргумент можем получить две новые булевы функции от n -1 аргументов.

Теорема 10.3 (о числе булевых функций от п аргументов). Число различных

булевых функций от п аргументов равно 22 n.

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

Лемма 10.4 (о разложении функции по переменной). Для произвольной булевой функции f (x 1,..., xn) справедливы следующие формулы, называемые формулами разложения этой функции по переменной x 1:

Теорема 10.5 (о представлении булевых функций через конъюнкцию, дизъюнкцию и отрицание). Всякая булева функция f (x 1,..., xn) может быть представлена в виде суперпозиции конъюнкции, дизъюнкции и отрицания; причем знак отрицания стоит только непосредственно около переменной и не стоит ни перед одной из внутренних скобок. До к а з а т е л ь с т в о будем вести методом математической индукции по числу п аргументов функции f