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

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

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

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

двухэлементное множество

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

. Тогда

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

- это множество всех двоичных последовательностей (наборов, векторов) длины

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

. Булевой функцией от

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

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

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

. Каждый из ее аргументов

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

может принимать одно из двух значений 0 или 1 и значением функции на любом наборе из

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

также может быть 0 или 1. Обозначим через

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

множество всех булевых функций от

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

переменных. Нетрудно подсчитать их число:

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

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

Содержание раздела

Главная сайта