Определение 3.

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

В данном случае не поясняется, что такое "функция". Предполагается, что вы помните это из школьной программы и понимаете, что у функции может быть больше одного аргумента (параметра). Кому-то, возможно, покажется непривычным тот факт, что параметры могут быть не числами, а словами вроде "красный" и "зеленый", "истина" и "ложь". Мы будем применять обозначения 0 и 1, но вы должны понимать, что складывать, вычитать эти обозначения как числа, нельзя. Поскольку в булевой алгебре это - не числа, и для них предусмотрены свои операции (которые, собственно, и называются логическими функциями).

Функции в булевой алгебре принято определять двумя способами. Первый - с помощью таблицы истинности. В такой таблице перечислены все возможные комбинации параметров и результат функции для каждой из комбинаций. В каждой строке слева перечисляются параметры, а в крайнем правом столбце - результат. В верхней строке - обозначения параметров и обозначение функции. Например:

x	y	z	f(x, y, z)
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	0

Для вычисления значения функции по значениям параметров достаточно найти строку, в которой записаны нужные значения в каждом столбце и прочитать результат в крайнем столбце справа. Например, пусть значения переменных равны: x = 0, y = 1, z = 1. Ищем в таблице строку, которая содержит значения 0,1,1. Это - четвертая строка (выделена цветом). В крайнем правом столбце видим результат: 1. Таким образом f(0, 1, 1) = 1.

По традиции варианты перебираются в таком порядке, что цифры во всех столбцах, кроме самого правого представляют собой обычный натуральный ряд: 0, 1, 2, 3, 4, 5,.. но в двоичной системе счисления: 000, 001, 010, 011, 100, 101,..

Количество комбинаций параметров для булевой функции с N аргументами равно 2^N. Количество разных функций с N аргументами равно 2^2N.

Второй способ задания логической функции - в виде формул, в которых применяются знаки унарных и бинарных операций. Знак унарной операции обозначает функцию от одного аргумента. Знак бинарной операции обозначает функцию от двух аргументов. Мы рассмотрим все такие функции.