Существует 16 = 2²² разных булевых функции с 2 аргументами (обозначим их x и y). Некоторые из них всегда совпадают по значению с булевой константой, булевой переменной или функцией только от одной из двух переменных. Таких функций всего шесть: 0, 1, x, ~x, y, ~y. Далее мы будем из называть тривиальными. Вот таблицы истинности для них:

x	y	0
0	0	0
0	1	0
1	0	0
1	1	0

x	y	1
0	0	1
0	1	1
1	0	1
1	1	1

x	y	x
0	0	0
0	1	0
1	0	1
1	1	1

x	y	y
0	0	0
0	1	1
1	0	0
1	1	1

x	y	~x
0	0	1
0	1	1
1	0	0
1	1	0

x	y	~y
0	0	1
0	1	0
1	0	1
1	1	0

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

Конъюнкция

x	y	x&y
0	0	0
0	1	0
1	0	0
1	1	1

Другие названия этой функции: "И", "логическое И", "логическое умножение", "булево умножение". Другие обозначения этой функции: .

Функция "И" дает 1 только когда оба операнда равны 1. Эта функция называется иногда логическим умножением, поскольку ее результаты совпадают с аналогичной операцией в арифметике: 0 * 0 = 0, 0 * 1 = 0, 1 * 0 = 0, 1 * 1 = 1.

Больше

x	y	x>y
0	0	0
0	1	0
1	0	1
1	1	0

Функция ">" дает 1 только когда первый операнд равен 1, а второй 0. Эта функция не имеет общеупотребительных названий или обозначений. Я обозначил ее символом ">" и назвал "больше" поскольку она равна 1, только когда первый операнд больше второго в арифметическом смысле: 1 > 0.

Меньше

x	y	x<y
0	0	0
0	1	1
1	0	0
1	1	0

Функция "<" дает 1 только когда первый операнд равен 0, а второй 1. Эта функция не имеет общеупотребительных названий или обозначений. Я обозначил ее символом "<" и назвал "меньше" поскольку она равна 1, только когда первый операнд меньше второго в арифметическом смысле: 0 < 1.

Сложение по модулю "2"

x	y	xy
0	0	0
0	1	1
1	0	1
1	1	0

Другие названия этой функции: "исключающее ИЛИ", "логическое ЛИБО", "неравносильность", "неэквивалентность", "логическое сложение", "булево сложение".

Другие обозначения этой функции: .

Функция "" дает 1 только когда первый операнд не равен второму операнду. Она похожа на арифметическое сложение: 0 0 = 0, 0 1 = 1, 1 0 = 1, но не всегда: в булевой алгебре 1 1 = 0, а не 2, как в арифметике. Как уже говорилось ранее, булевы величины 1 и 0 не являются числами и для них арифметика неприменима.

Дизъюнкция

x	y	xy
0	0	0
0	1	1
1	0	1
1	1	1

Другие названия этой функции: "ИЛИ", "логическое ИЛИ".

Другие обозначения этой функции:

С обозначением этой функции очень много путаницы. Во-первых, в программировании для нее используется обозначение x|y, но в математике это обозначение уже занято другой логической функцией - штрих Шеффера (см. чуть ниже). Во-вторых, сплошь и рядом для этой функции применяется обозначение "+", но так же часто обозначение "+" применяется для сложения по модулю "2".

Функция "ИЛИ" дает 0 только когда оба операнда равны 0.

Стрелка Пирса

x	y	xy
0	0	1
0	1	0
1	0	0
1	1	0

Другие названия этой функции: "ИЛИ-НЕ".

Эта функция дает 1 только когда оба операнда равны 0.

Равносильность

x	y	xy
0	0	1
0	1	0
1	0	0
1	1	1

Другие названия этой функции: "равносильность".

Другие обозначения этой функции:

Эта функция дает 1 только когда оба операнда равны между собой.

Обратная импликация

x	y	xy
0	0	1
0	1	0
1	0	1
1	1	1

Другие обозначения этой функции:

Эта функция дает 0 только когда первый операнд равен 0, а второй равен 1.

Импликация

x	y	xy
0	0	1
0	1	1
1	0	0
1	1	1

Другие обозначения этой функции:

Эта функция дает 0 только когда первый операнд равен 1, а второй равен 0.

Штрих Шеффера

x	y	x|y
0	0	1
0	1	1
1	0	1
1	1	0

Другие названия этой функции: "И-НЕ".

Другие обозначения этой функции: ' (апостроф).

Эта функция дает 0 только когда оба операнда равны 1.

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

В заключение приведем сводную таблицу всех бинарных логических операций:

x	y	0	xy	x<y	~x	x>y	~y	xy	x|y	x&y	xy	y	xy	x	xy	xy	1
0	0	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
0	1	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	0	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	1	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1

Итак, общий формат для обозначения функции от двух аргументов через знак бинарной операции выглядит как (F)#(G), где F и G - некоторые формулы, а # - знак бинарной операции. Для вычисления значения формулы (F)#(G) надо вычислить значение формул F и G, и подставить их в таблицу истинности как первый и второй аргументы функции.

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

Скобки вокруг F можно опускать, если F имеет вид: 0, 1, ~0, ~1, x, ~x, ~(H), где x - произвольная булева переменная, H - произвольная формула булевой алгебры. Иначе скобки опускать нельзя. То же правило относится и к G. Например: (~z & (x & y)) (~(~t & z) & x).

На практике опускают еще больше скобок, если это не затрудняет понимание, и есть договоренность о том, в каком порядке какие операции вычисляются. Обычно первой вычисляется операция "&", потом "" и "", потом все остальные. Если рядом идут операции одного приоритета, то вычисляются подряд слева направо.