Булева Алгебра: Основы

Будучи в Черновцах я сделал ревизию своих старых конспектов и залежей книг и нашел одну чудную книгу автора Касаткина В.Н. "Необычные задачи математики". Помню я ее читал в школьном возрасте и тогда она меня восхитила. Сейчас же я хочу поделиться некоторыми интересными фактами булевой алгебры, которые пригодились мне в моей работе программиста.

Для начала хочется вспомнить задачу, которую мне в свое время заказал мой Папа. А именно, есть коридор, а посередке него лампочка. Выключателей два, в разных концах коридора. Любым выключателем можно включить и выключить лампочку.

Попробуем объясниться с обозначениями принятыми в булевой алгебре. F(A,B) - булева функция двух аргументов A и B.

Далее объясню все более понятным языком.

Логическая операция ИЛИ (A or B). Результат будет 1, если кто-то, А или B, равен 1. Самая низкоприоритетная, потому ее стоит брать в скобки (у них наибольший приоритет), если че.

Логическая операия И (A and B). Результат будет 1, если и А и B равны 1. По приоритету уступает только скобкам (им все уступают) и следующей операции.

Логическая операция НЕТ (not A) (!A). Инвертирует состояние. Было 1, стало 0. Было 0, станет 1. Обозначается как вертикальная линия над выражением.

Инвертировать можно не только один агрумент, а и часть выражения целиком, тогда все выражение стоит надчеркнуть слитной линией (если одналиния уже есть, вторая рисуется чуть выше). Например

стоит понимать как (not(A and (not (B or C))) or (not B)). Согласись с надчеркиваниями проще выглядит.

Скобки (как уже говорил) переопределяют приоритет опреаций. Без них приоритет неивысший у НЕТ, после идет И, а потом ИЛИ. В данном примере из за скобок первым стоит брать В or C, а потом and A к результату.

Но вернемся к нашим лампочкам. Там была такая формула

Что можно сформулировать так. Лампочка будет гореть (F=1) если один из выключателей включен, а второй выключен ((A=0 и B=1) или (A=1 и B=0)).

Если посмотреть на условие, когда лампочка будет гореть ((A=0 и B=1) или (A=1 и B=0)) то по нему можно составить исходную функцию, просто заменив X=0 на X̅, а X=1 на X.

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

Вообще лампочка будет гореть тогда, когда сумма переключений будет не четно (1 или 3). То есть включен либо один из выключателей, либо все три сразу.

К слову сказать, любителям попаять - реализовать то же но с использованием электрических проводов, выключателей и лампочки достаточно интересная задача. Но не об этом сейчас. Решение дам в конце статьи.

Сейчас же интересно другое. Зная алфавит можно попробовать сказать пару слов на языке булевой алгебры. Тут есть некоторые интересные правила.

Комутативность

Ассоциативность

Дистрибутивность

Комплементность

Законы де Моргана (мои любимые), позволяющие преобразовывать AND в OR и наоборот

Законы поглощения

Закон Блейка-Порецкого

Идемпотентность

Закон снятия двойного отрицания

Свойства констант

Склеивание (исходит из дистрибутивности и комплементности)

Не знаю заметил ли ты, но если в каком-то тождестве все операции AND заменить на OR и наоборот, а все встречающиеся символы 0 заменить на 1 и наоборот, то полученное выражение будет тождеством двойственным исходному. Именно потому я прикодил тождества попарно.

И хорошо, а где это все можно использовать? Очень просто,как минимум при рефакторинге комплексных if-else. Например, в одном из прошлых моих постов Refactoring: По чуть-чуть в видео на 12,5 минуте я бы остановился в своем рефакторинге на таком коде.

public String answer(String figure, String glass) {
    boolean isI = figure.equals("I");
    boolean isO = !isI;

    for (int dx = 0; dx <= 10; dx++) {
        if ((isI || isO && (dx % 2 == 0)) && isFree(glass, dx)) {
            return getCommand(dx);
        }
    }
    throw new UnsupportedOperationException();
}

Но я пошел дальше и разделил if на два, зная как работает операция AND

public String answer(String figure, String glass) {
    boolean isI = figure.equals("I");
    boolean isO = !isI;

    for (int dx = 0; dx <= 10; dx++) {
        // если не получается (не 1) первое подвыражение бывшего оператора AND
        if (!(isI || isO && (dx % 2 == 0))) { 
            // то дальше соваться нечего
            continue;
        }
        // иначе проверяем второе подвыражение бывшего AND 
        if (isFree(glass, dx)) {
            return getCommand(dx);
        }
    }
    throw new UnsupportedOperationException();
}

И тут о ужас! добавилось еще одно отрицание в

(!(isI || isO && (dx % 2 == 0))) 

Но зная закон де Моргана его легко можно превратить в

(!isI && !(isO && (dx % 2 == 0)))

а потом и в

(!isI && (!isO || (dx % 2 =! 0)))

зная, что

isI = !isO

можно написать

(isO && (isI || (dx % 2 =! 0)))

Cтало проще? Но фишка тут в другом - теперь я снова могу разделить этот if на два, потому как основная операция у меня в условии AND... Так я и поступил, а что было дальше - можешь изучить на видео в статье Refactoring: По чуть-чуть с 16,5 минуты.

Мы же тут ковырнем булеву алгебру чуть глубже. Для затравки запишу формулы-мостик между булевой алгеброй и обычной арифметикой. Если 1 и 0 представлять в виде простых чисел, то

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

Все сходится... Пока не знаю, где это может пригодится, но сам факт возможности греет.

Идем дальше. Мы тут изучали одну булеву функцию с одним аргументом (унарную) NOT(НЕ) и две функции с двумя аргументами (бинарные) AND(И) и OR(ИЛИ). Их на самом деле по-больше будет (для бинарных - 16 штук, для тернарных - 256). И каждая имеет свое имя :)

Вот такие вот пироги с котятами.

На последок еще одна вкусная штука - программа Atanua - эмулятор электронных логических схем. Кто в молодости паял на K155ЛА3 генераторы, заценит!


И еще, как обещал разгадку задачки - как управлять одной лампочкой с трех

и более выключателей...

Рисунки взяты тут.

Надеюсь, пригодится...