Булевы функции от n переменных

⇐ ПредыдущаяСтр 2 из 3Следующая ⇒

Булевы функции ¹ названы в честь английского математика ХIХ века Дж. Буля, который впервые применил алгебраические методы для решения логических задач. Они образуют самый простой нетривиальный класс дискретных функций - их аргументы и значения могут принимать всего два значения (если мощность множества значений функции равна 1, то это тривиальная функция - константа! ). С другой стороны, этот класс достаточно богат и его функции имеют много интересных свойств. Булевы функции находят применение в логике, электротехнике, многих разделах информатики.

Обозначим через B двухэлементное множество {0, 1}. Тогда

это множество всех двоичных последовательностей (наборов, векторов) длины n. Булевой функцией от n переменных (аргументов) называется любая функция f(x₁, x_n): Bⁿ -> B. Каждый из ее аргументов x_i, 1 < = i < = n, может принимать одно из двух значений 0 или 1 и значением функции на любом наборе из B_n также может быть 0 или 1. Обозначим через множество всех булевых функций от n переменных. Нетрудно подсчитать их число.

Теорема 3.1. .

Доказательство. Действительно, по теореме 1.1 число функций из k -элементного множества A в m -элементное множество Bравно m^k. В нашем случае B={0, 1}, а A = Bⁿ. Тогда m=2 и k= |Bⁿ| = 2ⁿ. Отсюда следует утверждение теоремы.

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

Геометрическое представление

B_n можно рассматривать как единичный n-мерный куб. Каждый набор из нулей и единиц длины n задает вершину этого куба. На рис. 3.1 представлены единичные кубы B_n при n=3, 4.

Рис. 3.1.

При этом существует естественное взаимно однозначное соответствие между подмножествами вершин n-мерных единичных кубов и булевыми функциями от n переменных: подмножеству соответствует его характеристическая функция

Например, верхней грани куба B³ (ее вершины выделены на рисунке) соответствует функция f: f(0, 0, 1)=f(0, 1, 1)=f(1, 0, 1)=f(1, 1, 1) =1 и f(0, 0, 0)=f(0, 1, 0)=f(1, 0, 0)=f(1, 1, 0) =0. Очевидно, что указанное соответствие действительно взаимнооднозначное: каждая булевая функция f от n переменных задает подмножество A_f={(x₁, ..., x_n)|f(x₁, ..., x_n)=1} вершин Bⁿ. Например, функция, тождественно равная 0, задает пустое множество , а функция, тождественно равная 1, задает множество всех вершин Bⁿ.

Табличное представление

Булевы функции от небольшого числа аргументов удобно представлять с помощью таблиц. Таблица для функции f(x₁, ..., x_n)имеет n+1 столбец. В первых n столбцах указываются значения аргументов x₁, ..., x_n, а в (n+1) -ом столбце значение функции на этих аргументах - f(x₁, ..., x_n).

Таблица 3.1. Табличное представление функции f(x₁, ..., x_n)
x₁	.	.	.	x_n-1	x_n	f(x₁, ..., x_n)
	.	.	.			f(0, ..., 0, 0)
	.	.	.			f(0, ..., 0, 1)
	.	.	.			f(0, ..., 1, 0)
.	.	.	.	.	.
	.	.	.			f(1, ..., 1, 1)

Наборы аргументов в строках обычно располагаются в лексикографическом порядке:

существует такое , что при , а .

Если эти наборы рассматривать как записи чисел в двоичной системе счисления, то 1-ая строка представляет число 0, 2-ая - 1, 3-я - 2, а последняя - 2ⁿ-1.

При больших n табличное представление становится громоздким, например, для функции от 10 переменных потребуется таблицас 1024 строками. Но для малых n оно достаточно наглядно.

Формулы

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

Пусть - некоторое (конечное или бесконечное) множество булевых функций. Зафиксируем некоторое счетное множество переменных V={X₁, X₂, ...}. Определим по индукции множество формул над с переменными из V. Одновременно будем определять числовую характеристику формулы называемую ее глубиной, и множество ее подформул.

Определение 3.2.

1. Базис индукции. Каждая переменная и каждая константа является формулой глубины 0, т.е. dep(X_i)=dep(c)=0. Множество ее подформул состоит из нее самой.

2. Шаг индукции. Пусть и A₁, ..., A_m - формулы, и max {dep(A_i) | i = 1,..., m} = k. Тогда выражение является формулой, ее глубина равна k+1, а множество подформул включает саму формулу и все подформулы формул A₁, ..., A_m.

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

Базис индукции. Пусть . Тогда или . В первом случае задает функцию , во втором - функцию, тождественно равную константе c.

Шаг индукции. Пусть - произвольная формула глубины . Тогда , где и A₁, ..., A_m - формулы, для которых max_{1 < = i < = m}{dep(A_i)}=k. Предположим (по индукции), что этим формулам уже сопоставлены функции g₁(X₁,..., X_n), ..., g_m(X₁,..., X_n). Тогда формула задает функцию .

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

Определение 3.3.

· Базис индукции. 0, 1 и каждая переменная являются формулами глубины 0.

· Шаг индукции. Пусть и - формулы, .

Тогда выражения и являются формулами. При этом , а .

В соответствии с этим определением выражения и являются формулами. Глубина равна 3, а глубина равна 4. Выражения же , и (X₁ + X₂ + X₃) формулами не являются (почему? ).

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

⇐ Предыдущая 123 Следующая ⇒