Среди булевых функций особо выделяются так называемые элементарные булевы функции, посредством которых можно описать любую булеву функцию от любого числа переменных.
1. Булева функция f(x1, x2 … xn) принимающая значение 1 на всех наборах нулей и единиц называется константой 1, или тождественной единицей. Обозначение: 1.
2. Булева функция f(x1, x2 … xn) принимающая значение 0 на всех наборах нулей и единиц называется константой 0, или тождественным нулем. Обозначение: 0.
3. Отрицанием называется булева функция одной переменной, которая определяется следующей таблицей истинности:
| x | 0 | 1 |
| f(x) | 1 | 0 |
Обозначения: ¬x. Запись ¬x читается «не икс» или «отрицание икс».
4. Конъюнкцией называется булева функция двух переменных, которая определяется следующей таблицей истинности:
| x | 0 | 0 | 1 | 1 |
| y | 0 | 1 | 0 | 1 |
| f(x, y) | 0 | 0 | 0 | 1 |
Другие названия: логическое умножение (произведение); логическое «и».
Обозначения: x&y, x⋅y, min(x,y).
Запись x&y может читаться так: «икс и игрек» или «икс умножить на игрек».
5. Дизъюнкцией называется булева функция двух переменных, которая определяется следующей таблицей истинности:
| x | 0 | 0 | 1 | 1 |
| y | 0 | 1 | 0 | 1 |
| f(x, y) | 0 | 1 | 1 | 1 |
Другие названия: логическое сложение (сумма); логическое «или».
Обозначения: x∨y, max(x,y).
Запись x∨y может читаться так: «икс или игрек» или «сумма икс и игрек».
6. Импликацией называется булева функция двух переменных, которая определяется следующей таблицей истинности:
| x | 0 | 0 | 1 | 1 |
| y | 0 | 1 | 0 | 1 |
| f(x, y) | 1 | 1 | 0 | 1 |
Другое название: логическое следование.
Обозначения: x→y, x⇒y, x⊃y.
Запись x→y может читаться так: «из икс следует игрек».
7. Эквивалентностью называется булева функция двух переменных, которая определяется следующей таблицей истинности:
| x | 0 | 0 | 1 | 1 |
| y | 0 | 1 | 0 | 1 |
| f(x, y) | 1 | 0 | 0 | 1 |
Обозначения: x∼y, x↔y.
Запись x∼y может читаться так: «икс эквивалентно игрек» или «икс равносильно игрек».
8. Cуммой по модулю 2 называется булева функция двух переменных, которая определяется следующей таблицей истинности:
| x | 0 | 0 | 1 | 1 |
| y | 0 | 1 | 0 | 1 |
| f(x, y) | 0 | 1 | 1 | 0 |
Другое название: антиэквивалентность.
Обозначения: x⊕y, x+y.
Запись x⊕y может читаться так: «икс плюс игрек».
9. Штрих Шеффера это булева функция двух переменных, которая определяется следующей таблицей истинности:
| x | 0 | 0 | 1 | 1 |
| y | 0 | 1 | 0 | 1 |
| f(x, y) | 1 | 1 | 1 | 0 |
Другое название: отрицание конъюнкции, логическое «не-и».
Обозначение: x|y.
Запись x|y может читаться так: «не икс или не игрек», «икс и игрек несовместны», «икс штрих Шеффера игрек».
10. Стрелка Пирса это булева функция двух переменных, которая определяется следующей таблицей истинности:
| x | 0 | 0 | 1 | 1 |
| y | 0 | 1 | 0 | 1 |
| f(x, y) | 1 | 0 | 0 | 0 |
Другое название: отрицание дизъюнкции, логическое «не-или», функция Вебба.
Обозначение: x↓y; для функции Вебба — x°y.
Запись x↓y может читаться так: «ни икс и ни игрек», «икс стрелка Пирса игрек».
Замечание: Символы ¬, &, ∨, →, ∼, ⊕, |, ↓ участвующие в обозначениях элементарных функций будем называть связками или операциями.
| x | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| y | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 |
| z | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| f(x,y,z) | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
Булева функция также однозначно задается перечислением всех наборов, на которых она принимает значение 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).