Алгебра логики: основы и элементы

Тема данной статьи - особая ветвь алгебры, в которой значения переменных являются истинными и ложными, обычно обозначаемыми 1 и 0 соответственно. Вместо классической математики, где значения переменных являются числами, а простыми операциями считаются сложение и умножение, основными задачами логики алгебры являются конъюнкция и обозначается, как ∧; дизъюнкция позиционируется, как ∨, а отрицание не записывается, как ¬.

Происхождение

Алгебра логики была введена Джорджем Булем и более полно изложена в его труде «Исследование законов мышления» (1854). Согласно Хантингтону, сам термин был впервые предложен Шеффером в 1913 году. В наших широтах он не закрепился. Алгебра логики была фундаментальной в развитии цифровой электроники.

История исследований

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

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

Особенности

В то время как в элементарной алгебре выражения обозначают в основном числа, в языке алгебры логики они обозначают истинные значения false и true. Эти значения представлены битами (или двоичными цифрами). Они могут быть идентифицированы с элементами двухэлементного поля GF (2), то есть целочисленная арифметика по модулю 2. Затем сложение и умножение играют булеву роль XOR (исключающее-или) и AND (конъюнкция) соответственно, с дизъюнкцией x∨y (включительно) или определяется как x + y - xy.

Алгебра логики высказывания также имеет дело с функциями, значения которых находятся в множестве {0, 1}. Последовательность битов является обычно используемой такой функцией. Другим распространенным примером являются подмножества набора E: например, с F в E связана функция индикатора, которая принимает значения 1 на F и 0 за пределами его. Наиболее общий пример - это элементы булевой алгебры со всеми приведенными выше примерами.

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

Законы и принципы

Закон булевой алгебры - это тождество. Булев термин определяется как выражение, построенное из переменных и констант 0 и 1 с использованием операции ∧, ∨ и ¬. Концепция может быть расширена до терминов, включающих другие булевы операции, такие как ⊕, → и ≡, но такие расширения не нужны для целей, к которым применяются законы. Такие цели включают определение булевой алгебры, как любой модели из этих законов и как средство для выведения новых показателей из старых, как описано в разделе об аксиоматизации.

Принятие x = 2 в третьем законе показывает, что это не обычный канон алгебры, поскольку 2 × 2 = 4. Остальные пять законов могут быть фальсифицированы в обычной точной науке, если принять все переменные равными 1.

Новаторская роль

Все законы, которые рассматривались до сих пор, касались соединения и дизъюнкции. Эти операции имеют свойство, заключающееся в том, что изменение либо аргумента, либо исходных показателей оставляет последние без перемен, либо выходные данные меняются так же, как и входные. Эквивалентно, изменение любой переменной от 0 до 1 никогда не приводит к изменению вывода с 1 на 0. Операции с этим свойством называются монотонными. Таким образом, аксиомы до сих пор существовали для монотонной булевой логики. Немонотонность вступает через дополнение ¬ следующим образом:

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

Пояснение

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

Или промежуточное понятие аксиомы можно вообще обойти стороной, определив булев закон как любую тавтологию, понимаемую, как уравнение, которое выполняется для всех значений ее переменных, равных 0 и 1. Можно показать, что все эти определения булевой алгебры эквивалентны.

Принцип: если {X, R} является набором, то {X, R (обратный)} также является набором.

Изменения

Одним из изменений, которое нам не нужно было вносить в рамках этого обмена, было дополнение. Мы говорим, что дополнение является самодвойственной операцией, например, «тождество» или «ничего не делать» x (копирование ввода на выход) также является таковой.

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

• единичная;
• дополнения;
• двойная функция;
• противоположная (дополненная двойственной).

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

Диаграмма Венна

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

• Внутренняя и внешняя части области x соответствуют значениям 1 (правда) и 0 (ложь) для переменной x.
• Затенение указывает на значение операции для каждой комбинации регионов, где темный обозначает 1, а светлый 0.

Три диаграммы Венна на рисунке ниже представляют соответственно конъюнкцию x∧y, дизъюнкцию x∨y и дополнение ¬x.

Для соединения область внутри обоих кругов заштрихована, чтобы указать, что x∧y равен 1, когда обе переменные равны 1. Другие отделы остаются не заштрихованными, чтобы указать, что x∧y равно 0 для трех других комбинаций. Эта математическая модель очень полезна для того, чтобы изучать сложные и абстрактные законы логики с помощью счета и умножения многочисленных цифр, а также других вычислительных операций. Таким образом, это низведение философской логики на более конкретный математический уровень.

Хотя мы не показали диаграмм Венна для констант 0 и 1, они тривиальны и представляют собой соответственно белый и темный прямоугольники, причем ни один из них не содержит круг. Однако мы можем поставить кружок для x в этих полях, и в этом случае каждый из них будет обозначать функцию с одним аргументом x, которая возвращает одно и то же значение независимо от x, называемую постоянной функцией. Что касается их выходных данных, разница в том, что константа не имеет аргументов, называемых нулевой (или нулевой операцией), а константа является унарной операцией.

Диаграммы Венна полезны для визуализации законов. Нормы коммутативности для ∧ и ∨ можно увидеть из симметрии диаграмм: бинарная операция, которая не была коммутативной, не имела бы соответствующей диаграммы, потому что взаимозаменяемость x и y обладала бы эффектом отражения графика по горизонтали, а любой сбой коммутативности затем появляются, как нарушение симметрии.

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

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

Чтобы увидеть первый закон поглощения, x∧ (x∨y) = x, начните с диаграммы в середине для x∨y и обратите внимание, что часть затененной области, общая с кругом x, является целым кругом x.

Для второго закона поглощения, x∨ (x∧y) = x, начните с левой диаграммы для x∧y и обратите внимание, что затемнение всего круга x приводит к затенению только области x, так как предыдущая заливка была внутри х.

Чтобы визуализировать ее, (¬x) ∧ (¬y) = ¬ (x∨y), начните со средней диаграммы для x∨y и дополните ее штриховкой так, чтобы затемнилась только область вне обоих кругов, которая это то, что описывает правая часть закона. Результат находится как вне круга х, так и вне круга у, т. е. в соединении их внешних элементов.

Второй пример, (¬x) ∨ (¬y) = ¬ (x∧y), работает одинаково с двумя взаимозаменяемыми диаграммами.

Первый закон дополнения, x∧¬x = 0, говорит, что внутренняя и внешняя части круга x не перекрываются. Второй закон дополнения, x∨¬x = 1, говорит, что все находится либо внутри, либо снаружи круга x.

Цифровая логика

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

Далее следует объяснить другие важные моменты, непосредственно относящиеся к теме. Значение ввода представлено напряжением на выводе. Для так называемой логики «активный-высокий», 0 представлен напряжением, близким к нулю, или «землей», а 1 представлен аналогом, близким к напряжению питания; активный-низкий меняет это. Линия справа от каждого вентиля представляет выходной порт, который обычно соответствует тем же соглашениям по напряжению, что и входные порты.