Булева алгебра

А пофиг!

Будучи в Черновцах я сделал ревизию своих старых конспектов и залежей книг и нашел одну чудную книгу автора Касаткина В.Н. «Необычные задачи математики». Помню я ее читал в школьном возрасте и тогда она меня восхитила. Сейчас же я хочу поделиться некоторыми интересными фактами булевой алгебры, которые пригодились мне в моей работе программиста.
Для начала хочется вспомнить задачу, которую мне в свое время заказал мой Папа. А именно, есть коридор, а посередке него лампочка. Выключателей два, в разных концах коридора. Любым выключателем можно включить и выключить лампочку.
Попробуем объясниться с обозначениями принятыми в булевой алгебре. 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 генераторы, заценит!

И еще, как обещал разгадку задачки — как управлять одной лампочкой с трех
и более выключателей…
Рисунки взяты .
Надеюсь, пригодится…

Понятие алгебры логики

На этом уроке знакомимся с алгеброй логики, одним из основателей которой стал английский математик Джордж Буль (1815-1864), который был из довольно бедной семьи, а в юности зарабатывал переводами сочинений древнегреческих философов. За этим занятием его и посетила мысль о том, что высказываниям можно присваивать значения 1 («истина») и 0 «ложь».

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

Создание алгебры логики в середине ХIХ века в трудах Джорджа Буля представляло собой попытку решать традиционные логические задачи алгебраическими методами.

Функция от n переменных называется логической или булевой или переключательной или функцией алгебры логики, если сама функция и любой из ее аргументов могут принимать значения только из множества {0, 1}. Описанную функцию часто называют также булевым вектором. Количество функций от n переменных равно 2 в степени n. То же самое можно сказать и иначе: число различных n-мерных булевых векторов равно 2 в степени n. А число различных функций алгебры логики от этих векторов равно уже .

Значениям переменной в булевой алгебре соответствуют состояниям элементов микросхем компьютера или любого другого электронного устройства: сигнал присутствует (логическая «1») или сигнал отсутствует (логический «0»).

На логических элементах, реализующих булевы функции, строятся логические схемы электронных устройств.

Законы булевой алгебры применяются и в программировании — при написании сложных логических условий и сложных запросов к базе данных. Один пример со скриптом на PHP приведён (это статья о системе многокритериального поиска по сайту с базой данных). Ещё один пример — применение алгебры логики в создании многоуровневого меню сайта, в котором были бы открыты все пункты всех уровней, по которому пролегает путь к конечному открытому пункту меню.

Часто оказывается, что изначально построенное логическое выражение можно упростить, используя аксиомы, теоремы и законы алгебры логики.

Логические функции

Логические функции одной переменной

Функция Название Обозначение
Константа нуля
Повторение x
Логическое отрицание, инверсия, «НЕ»
Константа единицы
Переменная Логические функции
x
0 0 0 1 1
1 0 1 0 1

Логические функции двух переменных

Функция Название Обозначение
Константа нуля или False
Логическое умножение, конъюнкция, «И» или или или
Запрет по или
Переменная
Запрет по или
Переменная
Сложение по модулю 2, отрицание эквивалентности, исключающее «ИЛИ» или или
Логическое сложение, дизъюнкция, «ИЛИ» или или или
Функция Пирса (Вебба), «ИЛИ-НЕ» или или
Логическая равнозначность, эквиваленция или или или
Отрицание
Правая импликация или
Отрицание
Левая импликация или
Функция Шеффера, «И-НЕ» или или
Константа единицы или True
X1 0 0 1 1
X2 0 1 0 1
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1

В логических схемах функции могут быть реализованы с произвольных количеством входных переменных, примеры — в материале Логические схемы и таблицы истинности.

Ответить на контрольные вопросы, а затем посмотреть ответы

Контрольный вопрос 1. Даны две переменные x1 и x2. Число различных булевых векторов и различных ФАЛ от полученных векторов равны соответственно:

  • 8 и 16
  • 8 и 32
  • 4 и 8
  • 4 и 16

Контрольный вопрос 2. Какие из функций не являются ФАЛ одной переменной (и одна, и вторая в варианте ответа):

  • отрицание и сложение по модулю два
  • эквивалентность и повторение x
  • отрицание и импликация
  • функция Шеффера и эквивалентность
  • запрет по x2 и отрицание

Правильные ответы на вопрос 1 и вопрос 2.

This entry was posted in Ремонт. Bookmark the <a href="https://kabel-house.ru/remont/buleva-algebra/" title="Permalink to Булева алгебра" rel="bookmark">permalink</a>.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *