Бу́лева фу́нкция (или логи́ческая функция, или функция а́лгебры ло́гики)[1] от n аргументов — в дискретной математике — отображение Bn → B, где B = {0,1} — булево множество. Элементы булева множества {1, 0} обычно интерпретируют как логические значения «истинно» и «ложно», хотя в общем случае они рассматриваются как формальные символы, не несущие определённого смысла. Неотрицательное целое число n, обозначающее количество аргументов, называется арностью или местностью функции, в случае n = 0 булева функция превращается в булеву константу. Элементы декартова произведения (n-я прямая степень) Bn называют булевыми векторами. Множество всех булевых функций от любого числа аргументов часто обозначается P2, а от n аргументов — P2(n). Переменные, принимающие значения из булева множества, называются булевыми переменными[2]. Булевы функции названы по фамилии математика Джорджа Буля.
При работе с булевыми функциями происходит полное абстрагирование от того содержательного смысла, какой предполагается в алгебре высказываний[2]. Тем не менее между булевыми функциями и формулами алгебры высказываний можно установить взаимно-однозначное соответствие, если[3]:
Каждая булева функция арности n полностью определяется заданием своих значений на своей области определения, то есть на всех булевых векторах длины n. Число таких векторов равно 2n. Поскольку на каждом векторе булева функция может принимать значение либо 0, либо 1, то количество всех n-арных булевых функций равно 2(2n). Поэтому в этом разделе рассматриваются только простейшие и важнейшие булевы функции.
Практически все булевы функции низших арностей (0, 1, 2 и 3) получили исторически сложившиеся имена. Если значение функции не зависит от одной из переменных (то есть, по сути, для любых двух булевых векторов, отличающихся лишь в значении этой переменной, значение функции на них совпадает), то эта переменная, не играя никакого «значения», называется фиктивной.
Булева функция задаётся конечным набором значений, что позволяет представить её в виде таблицы истинности, например[4]:
При n = 0 количество булевых функций сводится к двум 220 = 21 = 2, первая из них тождественно равна 0, а вторая 1. Их называют булевыми константами — тождественный нуль и тождественная единица.
Таблица значений и названий нульарных булевых функций: