Булевы функции и их построение

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

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

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

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

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

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

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

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

● ID — тождественность. Возвращает входное значение без изменений. True остаётся true, а false — false.

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

● IF, THEN — «если…, то…», импликация. Определяет отношения между посылкой и следствием. Возвращает следствие true, если посылка true. Если посылка имеет значение false, то следствие может быть и false, и true.

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

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

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

Разбираться в булевых функциях учат на курсе для аналитиков. Студенты изучают линейную алгебру, математический анализ, теорию вероятности, статистику и т. д. Подойдёт тем, кто хочет развиваться в Data Science.

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

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

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

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

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

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

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

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

Таблица истинности для функции (A AND B) OR (C AND D):

Результат суперпозиции — применение функции OR к входам, получившимся в операциях AND над парами входов A, B и С, D.

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

● OR — ИЛИ и AND — И;
● XOR — исключающее ИЛИ и XNOR — исключающее ИЛИ-НЕ;
● NOT — НЕ и ID — тождественность;
● NAND — И-НЕ и NOR — ИЛИ-НЕ.

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

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

● Метод графических карт Карно. Подход основан на преобразовании таблиц истинности булевых функций. Ячейки таблицы нужно поделить на прямоугольники, чтобы объединить соседние единицы. Значения в получившихся прямоугольниках — переменные упрощённого логического выражения функции.

● Разложение Шеннона. Суть метода в разделении таблицы истинности на две части: в одной должны остаться входы, при которых переменная принимает значение 1, в другой — при которых 0. В результате булева функция принимает вид суммы двух подфункций.

● Метод Куайна. Включает два этапа: на первом функцию приводят к сокращённому виду с помощью операций склеивания и поглощения. На втором сокращенную функцию приводят к минимальной, удаляя переменные, которые никак не влияют на результат исходной функции.

● Метод Куайна-Маккласки. Этот подход упрощает обычный метод Куайна. В нём проводят меньше операций склеивания за счёт изначального разделения таблицы истинности на области с равным количеством нулей или единиц.

● Метод Блейка-Порецкого. Способ основан на преобразовании таблицы истинности функции в матрицы Грея, на которых представляют троичные векторы.