Мой персональный джин

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

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

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

Попробуем объясниться с обозначениями принятыми в булевой алгебре. 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 генераторы, заценит!


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

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

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

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

Подборка #15 Как выбирать? Особенности трансерфинга. Велопрогулка. Gmail. Пикаска.

Есть и другие подборки: #1, #2, #3, #4, #5, #6, #7, #8, #9, #10, #11, #12, #13, #14, #15, #16, #17, #18, #19, #20, #21, #22, #23, #24, #25, #26, #27, #28, #29, #30, #31, #32, #33, #34, #35, #36, #37, #38, #39, #40

Вчера жарил шашлык. Время от времени дул сильный ветер. Волновался как бы не стал причиной пожара. Сегодня пил воду из бюветов и так же волнвался как бы не подхватить какую-то палочку. И таких мелочей почему-то в последнее время множество. Почему? Ответ сразу всплыл - трансерфинг. Помню, когда его курил в прошлый раз (год назад), то тоже волновался по пустякам, причем как бы не уговаривал Зеланд убрать важность, важности становилось все больше. Понаблюдав за его способом изложения я заметил, что в его тесте встречается очень много "НЕ": не делайте так, а говорите так, не думайте так, не, не, не. Возможно это на верных порах влияет. Не знаю. Успокаивает турбосуслик - у этой методики тоже на первых порах, как говорит автор, лезет говно из всех мест. Возможно такой способ восприятия у сознания - все за что бы оно не взялось - все вначале ломается...Читать дальше...

Не говори НЕ

Смотри не порежься, сказанное под руку режущему приводит к травме. Говорят накаркал или сглазил. Это правда и все проще чем может казаться.

Частичка "не" не воспринимается подсознанием. А текст "не делай чего-то-там" подсознанием воспринимается как "сделай это". Сознание пропускает это, т.к. человек вроде бы с заботой о тебе это говорит - все безопасно. Вот так просто обходим защиту сознания. Это простой способ манипуляции, но сейчас не об этом. А скорее о защите от возможных трудностей связанных с НЕ.

НЕ хотите чего-то - получите. НЕ будете чего-то делать - прийдется. НЕ нравится вам это - этого будет еще больше. Просто потому, что сознание пускает эту команду дальше на обработку подсознанию, а то, отбрасывая частичку "не" берется за выполнение поставленной задачи. Все закрепляется постоянным каждодневным повторением: "НЕ хочу..", "НЕ хочу...", "НЕ буду...", "НЕ делай этого...", "НЕ хочу...". А подсознание слышит: "Хочу...", "Хочу...", "Буду...", "Делай это...", "Хочу...".

А потом жалуемся "почему все так нехорошо?" Что? НЕхорошо говоришь? А подсознание слышит "Почему так все хорошо?". Ну раз хорошо, на тебе еще!

В данном контексте Подсознание, Бог, Вселенная, Бесконечность, Душа, Внутренне Я, Ангел Хранитель - синонимы.

Есть такое понятие как позитивная формулировка. Очень классная штука. Язык общения максимально понятный подсознанию. Даю линки для старта.

"Рамка цели"
Позитивная формулировка

Удачных экспериментов!