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

Булевы функции ¹⁾ названы в честь английского математика Х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ⁿ . Отсюда следует утверждение теоремы.

Суперпозицией булевых функций f0 и f1,...,f_n называется функция f(x1,...,x_m) = f0(g1(x1,...,x_m),...,g_k(x1,...,x_m)), где каждая из функций g_i(x1,...,x_m) либо совпадает с одной из переменных (тождественная функция), либо – с одной из функций f1,...,f_n.

19. Число булевых функций от n аргументов. Выражение булевых функций через конъюнкцию, дизъюнкцию и отрицание (теорема о разложении функции по переменной и теорема о представлении булевых функций через конъюнкцию, дизъюнкцию и отрицание).

Дизъюнктивная нормальная форма