Алгебра буля

Дистрибутивные операции.

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

x * (y + z) = (x * y) + (x * z) и
(x + y) * z = (x * z) + (y * z),
где * и + — некоторые
логические операции.

Первую схему будем называть левой дистрибутивностью, вторую
схему — правой дистрибутивностью, а если срабатывают обе
схемы, то будем говорить о полной дистрибутивности или просто
дистрибутивности.

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

Результаты программы выглядят так.

Из полученных правил наибольший практический интерес
представляют:

x & (y z) = (x & y) (x & z)(x y) & z = (x & z) (y & z)x (y & z) = (x y) & (x z)(x & y) z = (x z) & (y z)x & (y z) = (x & y) (x & z)(x y) & z = (x & z) (y & z)

Как видите, дистрибутивность между логическим умножением
и сложением в алгебре логики такая же как в обычной
алгебре (где она называется «распределительным законом»).
Обратите внимание, что и для операций «» и «&» можно
раскрывать скобки таким же способом. Причем обе операции
оказываются равноправны: можно раскрывать скобки когда
в них стоит «&», а вне скобок — «», а можно и в обратной
ситуации — когда внутри скобок стоит «»

Понимание булевой алгебры

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

Понятие булевой алгебры было впервые введено Джорджем Булем в его книге «Математический анализ логики» и далее расширено в его книге «Исследование законов мысли». Поскольку ее концепция была подробно описана, булевская алгебра в основном использовалась в языках программирования. Его математические цели используются в теории множеств и статистике.

Обозначение

Операторы булевых алгебр отмечаются по-разному. В логической интерпретации как конъюнкции, дизъюнкции и отрицания, они записываются как , и и вербализуются , как И, ИЛИ, НЕ или И, ИЛИ, НЕ. В теоретико-множественной интерпретации как пересечение, объединение и дополнение они записываются как , и ( ). Для того, чтобы подчеркнуть абстракции в общей булевой алгебре, пары символов , такие как , или , также используются.
∧{\ Displaystyle \ клин}∨{\ displaystyle \ lor}¬{\ displaystyle \ neg}∩{\ displaystyle \ cap}∪{\ Displaystyle \ чашка}∁{\ displaystyle ^ {\ complement}}А.∁{\ Displaystyle А ^ {\ дополнение}}⊓{\ displaystyle \ sqcap}⊔{\ displaystyle \ sqcup}*{\ displaystyle \ ast}∘{\ displaystyle \ circ}

Математики иногда пишут «·» вместо И и «+» вместо ИЛИ (из-за их отдаленного сходства с умножением и сложением других алгебраических структур) и НЕ обозначают чертой, тильдой ~ или конечным штрихом . Это обозначение также в цифровой алгебре переключения для описания схем логических функций обычно; там часто используются определяемые ссылки NAND (NOT AND), NOR (NOT OR) и XOR (EXCLUSIVE OR).

В этой статье используются символы операторов , и .
∧{\ Displaystyle \ клин}∨{\ displaystyle \ lor}¬{\ displaystyle \ neg}

Аксиоматизация[править | править код]

В 1933 году американский математик Хантингтон предложил следующую аксиоматизацию для булевых алгебр:

1. Аксиома коммутативности: x + y = y + x.
2. Аксиома ассоциативности: (x + y) + z = x + (y + z).
3. Уравнение Хантингтона: n(n(x) + y) + n(n(x) + n(y)) = x.

Здесь использованы обозначения Хантингтона: + означает дизъюнкцию, n — отрицание.

Герберт Роббинс поставил следующий вопрос: можно ли сократить последнюю аксиому так, как написано ниже, то есть будет ли определённая выписанными ниже аксиомами структура булевой алгеброй?

Аксиоматизация алгебры Роббинса:

1. Аксиома коммутативности: x + y = y + x.
2. Аксиома ассоциативности: (x + y) + z = x + (y + z).
3. Уравнение Роббинса: n(n(x + y) + n(x + n(y))) = x.

Этот вопрос оставался открытым с 1930-х годов и был любимым вопросом Тарского и его учеников.

В 1996 году Вильям МакКьюнru_en, используя некоторые полученные до него результаты, дал утвердительный ответ на этот вопрос. Таким образом, любая алгебра Роббинса является булевой алгеброй.

Основные понятия и определения

Не вдаваясь в глубины, разберемся с терминологией. Итак, булева алгебра предполагает наличие:

• высказываний;
• логических операций;
• функций и законов.

Высказывания – любые утвердительные выражения, которые не могут быть истолкованы двузначно. Они записываются в виде чисел (5 > 3) или формулируются привычными словами (слон – самое большое млекопитающее). При этом фраза «у жирафа нет шеи» также имеет право на существование, только булева алгебра определит её как «ложь».

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

Примеры

• Двухэлементная булева алгебра также важна в общей теории булевых алгебр, потому что уравнение, включающее несколько переменных, обычно истинно во всех булевых алгебрах тогда и только тогда, когда оно истинно в двухэлементной булевой алгебре (что можно проверить с помощью тривиальный алгоритм грубой силы для небольшого числа переменных). Это может, например, использоваться, чтобы показать, что следующие законы ( теоремы консенсуса ) в целом справедливы во всех булевых алгебрах:
  • ( a ∨ b ) ∧ (¬ a ∨ c ) ∧ ( b ∨ c ) ≡ ( a ∨ b ) ∧ (¬ a ∨ c )
  • ( a ∧ b ) ∨ (¬ a ∧ c ) ∨ ( b ∧ c ) ≡ ( a ∧ b ) ∨ (¬ a ∧ c )

Набор мощности (множество всех подмножеств) из любого заданного непустого множества S образует булеву алгебру, в алгебре множеств , причем две операций ∨: = ∪ (союз) и ∧: = ∩ (пересечение). Наименьший элемент 0 является пустое множество , а наибольший элемент 1 является множество S себя.

• Множество всех конечных или конфинитных подмножеств S является булевой алгеброй, алгеброй множеств .
• Начав с исчисления высказываний с κ символов предложений, сформируйте алгебру Линденбаума (то есть набор предложений в исчислении высказываний по модулю логической эквивалентности ). Эта конструкция дает булеву алгебру. Фактически это свободная булева алгебра на образующих κ. Присвоение истинности в исчислении высказываний — это гомоморфизм булевой алгебры из этой алгебры в двухэлементную булеву алгебру.
• Для любого линейно упорядоченного множества L с наименьшим элементом алгебра интервалов — это наименьшая алгебра подмножеств L, содержащая все полуоткрытые интервалы [ a , b ), такие что a находится в L, а b либо в L, либо равно ∞. Алгебры интервалов полезны при изучении алгебр Линденбаума – Тарского ; каждая счетная булева алгебра изоморфна интервальной алгебре.

Диаграмма Хассе булевой алгебры делителей 30.

• Для любого натурального числа п , множество всех положительных делителей из п , определяющее а ≤ Ь , если а делит Ь , образует распределительную решетку . Эта решетка является булевой алгеброй тогда и только тогда , когда п является бесквадратным . Нижний и верхний элементы этой булевой алгебры — это натуральные числа 1 и n соответственно. Дополнение к a дается n / a . Встреча и соединение a и b задаются наибольшим общим делителем (gcd) и наименьшим общим кратным (lcm) чисел a и b соответственно. Сложение кольца a + b дается соотношением lcm ( a , b ) / gcd ( a , b ). На рисунке показан пример для n = 30. В качестве контрпримера, учитывая неквадратное n = 60, наибольший общий делитель 30 и его дополнение 2 будет 2, тогда как это должен быть нижний элемент 1.
• Другие примеры булевых алгебр возникают из топологических пространств : если X — топологическое пространство, то совокупность всех подмножеств X, которые являются как открытыми, так и замкнутыми, образует булеву алгебру с операциями ∨: = ∪ (объединение) и ∧: = ∩ (перекресток).
• Если R — произвольное кольцо и мы определяем множество центральных идемпотентов как A = { e ∈ R  : e 2 = e , ex = xe , ∀ x ∈ R }, то множество A становится булевой алгеброй с операциями e ∨ f  : = e + f — ef и e ∧ f  : = ef .

Логические операции

Простейший и наиболее широко применяемый пример такой алгебраической системы строится с использованием множества B, состоящего всего из двух элементов:

B = { Ложь, Истина }

Как правило, в математических выражениях Ложь отождествляется с логическим нулём, а Истина — с логической единицей, а операции отрицания (НЕ), конъюнкции (И) и дизъюнкции (ИЛИ) определяются в привычном нам понимании. Легко показать, что на данном множестве B можно задать четыре унарные и шестнадцать бинарных отношений и все они могут быть получены через суперпозицию трёх выбранных операций.

Опираясь на этот математический инструментарий, логика высказываний изучает высказывания и предикаты. Также вводятся дополнительные операции, такие как эквиваленция {\displaystyle \leftrightarrow } («тогда и только тогда, когда»), импликация →{\displaystyle \rightarrow } («следовательно»), сложение по модулю два ⊕{\displaystyle \oplus } («исключающее или»), штрих Шеффера ∣{\displaystyle \mid }, стрелка Пирса ↓{\displaystyle \downarrow } и другие.

Логика высказываний послужила основным математическим инструментом при создании компьютеров. Она легко преобразуется в битовую логику: истинность высказывания обозначается одним битом (0 — ЛОЖЬ, 1 — ИСТИНА); тогда операция ¬{\displaystyle \neg } приобретает смысл вычитания из единицы; ∨{\displaystyle \lor } — немодульного сложения; & — умножения; {\displaystyle \leftrightarrow } — равенства; ⊕{\displaystyle \oplus } — в буквальном смысле сложения по модулю 2 (исключающее Или — XOR); ∣{\displaystyle \mid } — не превосходства суммы над 1 (то есть A ∣{\displaystyle \mid } B = (A + B) <= 1).

Впоследствии булева алгебра была обобщена от логики высказываний путём введения характерных для логики высказываний аксиом. Это позволило рассматривать, например, логику кубитов, тройственную логику (когда есть три варианта истинности высказывания: «истина», «ложь» и «не определено»), комплексную логику и др.

Логическая функция «НЕ И»

Функция «НЕ И» представляет собой комбинацию двух отдельных логических функций, функции «И» и функции «НЕ» последовательно. Логическая функция «НЕ И» может быть выражена логическим выражением AB (с верхней чертой)

Функция логического «НЕ И» генерирует выход, только когда «ЛЮБЫЕ» из ее входов отсутствуют, и в терминах булевой алгебры выход будет ИСТИНА, только когда любой из ее входов ЛОЖЬ (0).

Представление функции «НЕ И» на схеме

Таблица истинности для функции «НЕ И» противоположна таблице для предыдущей функции «И», потому что элемент «НЕ И» выполняет обратную операцию элемента «И». Другими словами, элемент «НЕ И» является дополнением элемента «И».

Таблица истинности для функции «НЕ И»

Логика «НЕ И» используется в качестве основных «строительных блоков», чтобы построить другие функции логического элемента и доступны в стандартных IC пакетов, такие как общий TTL — 74LS00 Четырехместный 2-входной «НЕ И» элемент, TTL — 74LS10 Тройной 3-входной «НЕ И» элемент или 74LS20 Двойной 4-х входной «НЕ И» элемент. Есть даже один чип 74LS30 с 8 входами «НЕ И» элемента.

Логическая функция «ИЛИ» (сложение)

Функция логического «ИЛИ» заявляет, что выходное действие станет ИСТИНОЙ, если одно «ИЛИ» больше событий ИСТИНЫ, но порядок, в котором они происходят, не имеет значения, поскольку он не влияет на конечный результат.

Так , например, А + В = В + А . В булевой алгебре функция логического «ИЛИ» подчиняется коммутативному закону так же, как и для логической функции «И», что позволяет изменять положение любой переменной.

Логика или логическое выражение, данное для логического элемента «ИЛИ», является логическим выражением, которое обозначается знаком плюс, ( + ). Таким образом, 2-входной ( АВ ) Логический элемент «ИЛИ» имеет выход термин, представленный булевой выражением: A + B = Q .

Представление функции «ИЛИ» на схеме

Здесь два переключателя А и B соединены параллельно и, либо переключатель A «ИЛИ» переключатель B может быть закрыт, чтобы включить лампу. Другими словами, выключатель может быть замкнут, либо быть на логике «1», чтобы лампа была включена.

Тогда этот тип логического элемента генерирует и выводит только тогда, когда присутствует «ЛЮБОЙ» из его входов, и в терминах Булевой алгебры выход будет ИСТИНА, если любой из его входов ИСТИНЕН. В электрическом смысле логическая функция «ИЛИ» равна параллельной цепи.

Как и в случае с функцией «И», есть два переключателя, каждый с двумя возможными положениями, открытыми или закрытыми, поэтому будет 4 различных способа расположения переключателей.

Таблица истинности для функции «ИЛИ»

Логические «ИЛИ» элементы доступны в виде стандартных пакетов ic, таких как общие TTL 74LS32 Четырехместные 2-входные положительные «ИЛИ» элементы. Как и в предыдущем логическом элементе «И», «ИЛИ» также может быть «каскадно» соединен для создания цепей с большим количеством входов, таких как системы охранной сигнализации (зона A или зона B или зона C и т.д.).

Алгебраические преобразования логических выражений

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

Отрицание

Отрицание и инверсия — самое простое логическое преобразование. Ему соответствует частица «не.» Это преобразование просто меняет утверждение на противоположное. Соответственно, значение утверждения тоже меняется на противоположное. Если утверждение А истинно, то «не А» — ложно. Например, утверждение «прямой угол — это угол, равный девяносто градусов» — истина. Тогда его отрицание «прямой угол не равен девяноста градусам» — ложь.

Таблица истинности для отрицания будет такова:

Конъюнкция

Конъюнкция аналогична умножению и соответствует союзу «и». Такое выражение будет верно, только если верны все утверждения, объединённые конъюнкцией. То есть, утверждение «А и Б» будет истинным, только если А — истина и Б — истина. Во всех остальных случаях выражение «А и Б» ложно. Например, высказывание «Земля круглая и плоская» будет ложно, так как первая часть истина, а вторая — ложь.

Таблица истинности конъюнкции

Дизъюнкция

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

Обычная дизъюнкция или логическое сложение соответствует союзу «или». Она будет истинной если хотя бы одно из утверждений, входящих в неё — истина. Например, выражение «Земля круглая или стоит на трёх китах» будет истинным, так как первое утверждение — истинно, хоть второе и ложно.В таблице это будет выглядеть так:

Строгую дизъюнкцию или сложение по модулю также называют «исключающим или». Эта операция может принимать вид грамматической конструкции «одно из двух: либо …, либо …». Здесь значение логического выражения будет ложным, если все утверждения, входящие в него, имеют одинаковую истинность. То есть, оба утверждения либо вместе истинны, либо вместе ложны.

Таблица значений исключающего или

Импликация и эквивалентность

Импликация представляет собой следствие и грамматически может быть выражена как «из А следует Б». Здесь утверждение А будет называться предпосылкой, а Б — следствием. Импликация может быть ложной, только в одном случае: если предпосылка истинна, а следствие ложно. То есть, ложь не может следовать из истины. Во всех остальных случаях импликация истинна. Варианты, когда оба утверждения имеют одинаковую истинность, вопросов не вызывают. Но почему верное следствие из неверной предпосылки — истина? Дело в том, что из ложной предпосылки может следовать что угодно. Это и отличает импликацию от эквивалентности.

В математике (и других доказательных дисциплинах) импликация используется для указания необходимого условия. Например, утверждение А — «точка О — экстремум непрерывной функции», утверждение Б — «производная непрерывной функции в точке О обращается в ноль». Если О, действительно, точка экстремума непрерывной функции, то производная в этой точке будет, и вправду, равна нулю. Если же О не является точкой экстремума, то производная в этой точке может быть нулевой, а может не быть. То есть Б необходимо для А, но не достаточно.

Таблица истинности для импликации выглядит следующим образом:

Логическая операция эквивалентность, по сути, является взаимной импликацией. «А эквивалентно Б» означает, что «из А следует Б» и «из Б следует А» одновременно. Эквивалентность верна, когда оба утверждения либо одновременно верные, либо одновременно неверные.

В математике эквивалентность используется для определения необходимого и достаточного условия. Например, утверждение А — «Точка О является точкой экстремума непрерывной функции», утверждение Б — «В точке О производная функции обращается в ноль и меняет знак». Эти два утверждения эквивалентны. Б содержит необходимое и достаточное условие для А

Обратите внимание, что в данном примере утверждений Б на самом деле является конъюнкцией двух других: «производная в точке О обращается в ноль» и «производная в точке О меняет знак»

Прочие логические функции

Выше были рассмотрены основные логические операции, которые часто используются. Есть и другие функции, которые используются:

• Штрих Шеффера или несовместимость представляет собой отрицание конъюнкции А и Б
• Стрелка Пирса представляет сбой отрицание дизъюнкции.

Джордж Буль

Сама личность автора заслуживает отдельного внимания. Даже учитывая то, что в прошлом люди взрослели раньше нас, все равно нельзя не отметить, что в 16 лет Дж. Буль преподавал в деревенской школе, а к 20 годам открыл собственную школу в Линкольне. Математик отлично владел пятью иностранными языками, а в свободное время зачитывался работами Ньютона и Лагранжа. И все это — о сыне простого рабочего!

В 1839 году Буль впервые послал свои научные работы в Кембриджский математический журнал. Ученому исполнилось 24 года. Работы Буля настолько заинтересовали членов Королевского научного общества, что в 1844 году он получил медаль за вклад в развитие математического анализа. Еще несколько опубликованных работ, в которых были описаны элементы математической логики, позволили молодому математику занять пост профессора в колледже графства Корк. Напомним, что у самого Буля образования не было.

В принципе, булева алгебра очень проста. Существуют высказывания (логические выражения), которые, с точки зрения математики, можно определить только двумя словами: «истина» или «ложь». Например, весной деревья расцветают – истина, летом идет снег – ложь. Вся прелесть этой математики заключается в том, что нет строгой необходимости использовать только числа. Для алгебры суждений вполне подходят любые высказывания с однозначным смыслом.

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

Самое главное — понять, что совершенно неважно, как мы определили истинность или ложность высказывания. От этих «как» и «почему» нужно абстрагироваться

Значение имеет только констатация факта: истина-ложь.

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

Логическая функция «НЕ» (отрицание)

Функция «Логическое НЕ» — это просто инвертор с одним входом, который изменяет вход логического уровня «1» на выход логического уровня «0» и наоборот.

«Функция логического НЕ» называется так, потому что ее выходное состояние НЕсовпадает с его входным состоянием с ее логическим выражением, обычно обозначаемым чертой или линией ( ¯ ) над его входным символом, который обозначает операцию инвертирования (отсюда ее название как инвертор).

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

Представление функции «НЕ» на схеме

Если A означает, что переключатель замкнут, то «НЕ» A или А (с верхней чертой) говорит, что переключатель НЕ замкнут или, другими словами, он разомкнут. Функция логического НЕ имеет один вход и один выход, как показано на рисунке.

Таблица истинности для функции «НЕ»

Индикатор инверсии для логической функции «НЕ» является символом «пузыря», ( O) на выходе (или входе) символа логических элементов. В булевой алгебре инвертирующая логическая функция «НЕ» следует Закону дополнения, создающему инверсию.

Логические «НЕ» элементы или «Инверторы», как их чаще называют, могут быть связаны со стандартными элементами «И» и» ИЛИ» для создания элементов «НЕ И» и «НЕ ИЛИ» соответственно. Инверторы также могут использоваться для генерации «дополнительных» сигналов в более сложных декодерах / логических схемах, например, дополнение логики A — это «НЕ» A , а два последовательно соединенных инвертора дают двойную инверсию, которая выдает на своем выходе исходное значение A.

При проектировании логических схем вам может понадобиться только один или два инвертора в вашей конструкции, но если у вас нет места или денег для выделенного чипа инвертора, такого как 74LS04. Тогда вы можете легко заставить логику «НЕ» функционировать, используя любые запасные элементы «НЕ А» или «НЕ ИЛИ», просто соединяя их входы вместе, как показано ниже.

Идеалы и фильтры

Идеал булевой алгебры A есть подмножество I , что для всех х , у в I мы имеем х ∨ у в I и для всех а в А мы имеем ∧ х в I . Это понятие идеального совпадает с понятием кольца идеал в булевой кольце A . Идеал I в А называется простой , если I ≠ A , и если ∧ б в I всегда подразумевает в I или б в I . Кроме того, для любого a ∈ A имеем a ∧ -a = 0 ∈ I и тогда a ∈ I или -a ∈ I для любого a ∈ A , если I простое число. Идеал I кольца A называется максимальным, если I ≠ A и если единственный идеал, надлежащим образом содержащий I, — это сам A. Для идеального I , если ∉ я и -a ∉ я , то я ∪ { } или я ∪ { -a } должным образом содержится в другом идеала J . Следовательно, I не является максимальным, и поэтому понятия простого идеала и максимального идеала эквивалентны в булевых алгебрах. Кроме того, эти понятия совпадают с кольцевой теорико одними из простого идеала и максимального идеала в булевом кольце А .

Двойник идеала — это фильтр . Фильтр булевой алгебры А является подмножеством р такое , что для всех х , у в р мы имеем х ∧ у в р и для всех а в А мы имеем ∨ х в р . Двойственный к максимальному (или простому ) идеалу в булевой алгебре является ультрафильтром . В качестве альтернативы ультрафильтры можно описать как двузначные морфизмы из A в двухэлементную булеву алгебру. Оператор каждый фильтр в булевой алгебре может быть продолжен до ультрафильтра называется и не могут быть доказаны в ZF , если ZF является последовательным . В ZF это строго слабее, чем выбранная аксиома . Теорема об ультрафильтре имеет много эквивалентных формулировок: каждая булева алгебра имеет ультрафильтр , каждый идеал в булевой алгебре может быть расширен до простого идеала и т. Д.

Булев базис (логический базис)

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

Инверсия (логическое отрицание, «НЕ»)

.

Конъюнкция (логическое умножение, «И»)

.

Дизъюнкция (логическое сложение, «ИЛИ»)

.

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

Похожие записи:

Активное, емкостное и индуктивное сопротивление. закон ома для цепей переменного тока Ретро проводка в современном доме Где используется фидерный кабель Маркировка smd компонентов: кодовые обозначения Как сделать веб-приложение для вашего собственного bluetooth low energy девайса? Как подключить усилитель в машине