Введение в схемы, автоматы и алгоритмы


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


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

Обозначим через

B
двухэлементное множество
\{0,1\}
. Тогда
B^n=\underbrace{B\times B \times \ldots \times B}_{n}
- это множество всех двоичных последовательностей (наборов, векторов) длины
n
. Булевой функцией от
n

переменных (аргументов) называется любая функция

f(x_1,\ldots, x_n): B^n \rightarrow B
. Каждый из ее аргументов
x_i, \ 1 \leq i \leq n,\
может принимать одно из двух значений 0 или 1 и значением функции на любом наборе из
B^n
также может быть 0 или 1. Обозначим через
\mathcal{P}_n
множество всех булевых функций от
n
переменных. Нетрудно подсчитать их число:
|\mathcal{P}_n | = 2^{2^n}.

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




Начало    Вперед



Книжный магазин