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

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

1. Булева функция f(x1, x2 ... xn) принимающая значение 1 на всех наборах нулей и единиц называется константой 1, или тождественной единицей. Обозначение: 1.

2. Булева функция f(x1, x2 ... xn) принимающая значение 0 на всех наборах нулей и единиц называется константой 0, или тождественным нулем. Обозначение: 0.

3. Отрицанием называется булева функция одной переменной, которая определяется следующей таблицей истинности:

x01
f(x)10

Обозначения: ¬x. Запись ¬x читается «не икс» или «отрицание икс».

4. Конъюнкцией называется булева функция двух переменных, которая определяется следующей таблицей истинности:

x0011
y0101
f(x, y)0001

Другие названия: логическое умножение (произведение); логическое «и».

Обозначения: x&y, x⋅y, min(x,y).

Запись x&y может читаться так: «икс и игрек» или «икс умножить на игрек».

5. Дизъюнкцией называется булева функция двух переменных, которая определяется следующей таблицей истинности:

x0011
y0101
f(x, y)0111

Другие названия: логическое сложение (сумма); логическое «или».

Обозначения: x∨y, max(x,y).

Запись x∨y может читаться так: «икс или игрек» или «сумма икс и игрек».

6. Импликацией называется булева функция двух переменных, которая определяется следующей таблицей истинности:

x0011
y0101
f(x, y)1101

Другое название: логическое следование.

Обозначения: x→y, x⇒y, x⊃y.

Запись x→y может читаться так: «из икс следует игрек».

7. Эквивалентностью называется булева функция двух переменных, которая определяется следующей таблицей истинности:

x0011
y0101
f(x, y)1001

Обозначения: x∼y, x↔y.

Запись x∼y может читаться так: «икс эквивалентно игрек» или «икс равносильно игрек».

8. Cуммой по модулю 2 называется булева функция двух переменных, которая определяется следующей таблицей истинности:

x0011
y0101
f(x, y)0110

Другое название: антиэквивалентность.

Обозначения: x⊕y, x+y.

Запись x⊕y может читаться так: «икс плюс игрек».

9. Штрих Шеффера это булева функция двух переменных, которая определяется следующей таблицей истинности:

x0011
y0101
f(x, y)1110

Другое название: отрицание конъюнкции, логическое «не-и».

Обозначение: x|y.

Запись x|y может читаться так: «не икс или не игрек», «икс и игрек несовместны», «икс штрих Шеффера игрек».

10. Стрелка Пирса это булева функция двух переменных, которая определяется следующей таблицей истинности:

x0011
y0101
f(x, y)1000

Другое название: отрицание дизъюнкции, логическое «не-или», функция Вебба.

Обозначение: x↓y; для функции Вебба - x°y.

Запись x↓y может читаться так: «ни икс и ни игрек», «икс стрелка Пирса игрек».

Замечание: Символы ¬, &, ∨, →, ∼, ⊕, |, ↓ участвующие в обозначениях элементарных функций будем называть связками или операциями.

x00000111
y00111001
z01001011
f(x,y,z)00001011

Булева функция также однозначно задается перечислением всех наборов, на которых она принимает значение 0, либо перечислением всех наборов, на которых она принимает значение 1.Полученную в примере функцию f можно также задать следующей системой равенств: f(0,0,0) = f(0,0,1) = f(0,1,0) = f(1,0,0) = 0.

Вектором значений булевой функции y=f(x1, x2 ... xn) называется упорядоченный набор всех значений функции f, при котором значения упорядочены по лексикографическому порядку. Например, пусть функция трех переменных f задана вектором значений (0000 0010) и необходимо найти набор, на котором f принимает значение 1. Т.к. 1 стоит на 7 месте, а нумерация в лексикографическом порядке начинается с 0, то необходимо найти двоичное разложение 6. Таким образом, функция f принимает значение 1 на наборе (110).