Булевы функции. Определение. Функцию от одной или нескольких переменных, аргументы и значение которой могут принимать только значения 0 или 1

Определение. Функцию от одной или нескольких переменных, аргументы и значение которой могут принимать только значения 0 или 1, называют булевой функцией (в честь английского математика Джорджа Буля (1815 - 1864), одного из основателей математической логики).

Примеры.

Конъюнкция: = 1 тогда и только тогда, когда x и y оба равны 1.

Дизъюнкция: = 1 тогда и только тогда, когда x и y оба равны 1.

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

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

x	y

x	y

Эквивалентность: (Значение выражения равно 1, если значения x и y совпадают)

x	y

Симметрическая разность: (Значение выражения равно 1, если значения x и y не совпадают)

x	y

Импликация: (Мнемоническое правило: из нуля следует что угодно – и ноль, и единица)

x	y

Отрицание:

x