Лекция 8. Элементарные булевы функции

ЧАСТЬ 3. БУЛЕВЫ ФУНКЦИИ.

Элементарные булевы функции

Булевой функцией называется функция φ: Вⁿ→В. Область определения булевой функции –решётка Вⁿ – называется булевым кубом размерности n.

Число элементов Вⁿ – 2ⁿ. Отсюда следует, что число n-местных функций на В – это есть 2 в степени 2 в степени n. Так, при n=2 мы имеем 16 функций, трёхместных уже 256, а четырехместных – 65224. Таким образом, количество булевых функций быстро возрастает и практически недоступно для непосредственного перечисления.

Мы начнём изучение булевых функций с изучения множества Вⁿ – области определения n-местной функции.