Булевы функции

Булевы функции выполняют логические операции над значениями истинности — true и false. Этот раздел математики помогает программистам описывать логику алгоритмов

Понятие булевой функции

Булевы функции — это математический способ описания логических операций. Названы по имени британского математика Джорджа Буля, который в середине XIX века создал науку математической логики — булеву алгебру. Если обычные математические операции проводят с действительными числами, то булева алгебра работает со значениями истинности: true — «правда» и false — «ложь». В двоичной системе счисления, которая используется в программировании, их обозначают цифрами 1 и 0.

Простой пример функции булевых переменных: представим программу умного дома, которая управляет освещением. Чтобы понимать, в каком состоянии находится выключатель, программа использует логические значения. Если свет включён, значение состояния выключателя в программе будет равно 1, или true. Если выключен — 0, или false. Получение ответа «правда» или «ложь» по условию «Включён ли свет?» и есть простейшая булева функция.

У булевых функций есть входы — операнды и выход — результат. Например, выключатели света есть в двух комнатах и в прихожей. Чтобы лампа в прихожей выключалась, когда в обеих комнатах свет выключен, программе умного дома нужно применить булеву функцию AND — И. Эта функция берёт значения с выключателей в комнатах — входы: если оба они выключены (false и false), на выходе тоже будет значение false, и тогда свет в прихожей также выключится.

Какие булевы функции часто используют в программировании:

● AND — И, конъюнкция. Возвращает true, если оба выхода равны true.

● OR — ИЛИ, дизъюнкция. Возвращает true, если хотя бы один из выходов равен true.

● NOT — НЕ, отрицание, инверсия. Инвертирует значение входа: если вход был true, возвращает false, и наоборот.

● XOR — исключающее ИЛИ. Возвращает true, если только один из выходов был true.

● NOR — ИЛИ-НЕ. Инвертирует результат функции OR, то есть возвращает true, только если оба входа равны false.

Таблицы истинности булевых функций

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

1. AND — И, конъюнкция. Возвращает true, если оба выхода равны true. В строках таблицы указывают все возможные комбинации значений входов A и B. В третьем столбце указан результат этих комбинаций с булевой функцией AND, которую также называют конъюнкцией или логическим умножением. Логическое умножение входов A и B обозначают символом ∧.

Из таблицы истинности функции AND видно, что выход 1(true) возможен, только когда оба выхода тоже имеют значение 1 (true). Если хотя бы один вход имеет значение 0 (false), на выходе тоже будет 0 (false).

A	B	A ∧ B
0	0	0
0	1	0
1	0	0
1	1	1

2. OR — ИЛИ, дизъюнкция. Возвращает true, если хотя бы один из выходов равен true. Функцию OR в булевой алгебре также называют дизъюнкцией или логическим сложением. Логическое сложение входов A и B обозначают символом ∨.

Выход функции OR имеет значение 1, если хотя бы один из выходов имеет значение 1. Когда значения входа A и входа B равны 0, результат логического сложения тоже будет равен 0.

A	B	A ∨ B
0	0	0
0	1	1
1	0	1
1	1	1

3. NOT — НЕ, отрицание, инверсия. Инвертирует значение входа: если вход был true, возвращает false, и наоборот. У булевой функции NOT — она же отрицание, или инверсия, — всего один вход, значение которого функция меняет на противоположное.

A	¬A
0	1
1	0

Суперпозиции функций

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

Допустим, задана булева функция (A AND B) OR (C AND D). В этой операции есть четыре входа: A, B, С и D. Как и в обычной математике, сначала нужно выполнить операции AND в скобках, получить новые выходы и затем провести с ними операцию OR.

F1 = (0v0) v (1v1) = 1 F2 = (1v1) v (1v0) = 1 F3 = (0&0) & (1&1) = 0 F4 = ¬1 & (1v1) v (¬0&1) = 1 F5 = (¬1v1) & (1v ¬1) & (¬1v 0) = 0 F6 = (1 & 0) v (¬1 & 1) = 0 F7 = ¬(0 v 1) & (1 & ¬0) = 0 F8 = (1 v 1) & (0 v ¬0) v (1 & 0) = 1 F9 = ¬(¬1 v 0) & (1 v 0) = 1 F10 = (0 & 1) v (¬0 & ¬1) v (1 & 1) = 1 F11 = ¬(1 & 1) v ¬(0 v 0) = 1 F12 = (¬0 v 1) & (¬1 v 0) & (1 & 1) = 0
F13 = (1 v 0) & ¬(0 v 0) v 1 = 1 F14 = ¬(¬(1 & 0) v (1 & ¬0)) = 0 F15 = (1 & (0 v 1)) v (¬1 & (1 v 0)) = 1 F16 = ¬(1 v (0 & ¬1)) & 1 = 0 F17 = (¬0 & (1 v 0)) v (0 & ¬(1 v 1)) = 1 F18 = ((1 & 1) v ¬0) & (¬1 v (0 & 1)) = 0 F19 = ¬(¬(¬1 & 0) v (1 & ¬0)) = 0 F20 = (1 v ¬1) & (¬0 v 1) & (0 & 1) = 0 F21 = ¬((0 v 1) & (¬1 v 0)) v 1 = 1 F22 = (¬1 v ¬0) & ((1 & 0) v ¬1) = 0 F23 = ¬(1 & 0) v ¬(0 v ¬1) & 1 = 1 F24 = (1 & ¬1) v (¬0 & 1) v ¬(1 & 1) = 1 F25 = ¬((¬0 v 1) & (1 & ¬(0 v 0))) = 0