Булева алгебра (структура) — boolean algebra (structure)

Функции и законы

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

Ассоциативность означает, что в высказываниях типа «и А, и Б, и В» последовательность перечисления операндов не играет роли. Формулой это запишется так:

(A∧Б)∧В=A∧(Б∧В)=A∧Б∧В,

(A∨Б)∨В=A∨(Б∨В)=A∨Б∨В.

Как видим, это свойственно не только конъюнкции, но и дизъюнкции.

Коммутативность утверждает, что результат конъюнкции или дизъюнкции не зависит от того, какой элемент рассматривался вначале:

A∧Б=Б∧A; A∨Б=Б∨A.

Дистрибутивность позволяет раскрывать скобки в сложных логических выражениях. Правила схожи с раскрытием скобок при умножении и сложении в алгебре:

A∧(Б∨В)=A∧Б∨A∧В; A∨Б∧В=(A∨Б)∧(A∨В).

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

A∧0=0,A∧1=A; A∨0=A,A∨1=1.

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

Б∧Б=Б; Б∨Б=Б.

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

A∧Б∨Б=Б; (A∨Б)∧Б=Б.

Многозначная логика

Операции, называемой в двоичной логике конъюнкция, в многозначных логиках обычно сопоставляется операция минимум: min(a,b){\displaystyle min(a,b)}, где a,b∈{,…,k−1},{\displaystyle a,b\in \{0,\dots ,k-1\},} а k{\displaystyle k} — значность логики; впрочем, возможны и другие варианты обобщения обычной конъюнкции на многозначный случай. Как правило, стараются сохранить совместимость с булевой алгеброй для значений операндов {\displaystyle 0} и k−1{\displaystyle k-1}.

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

Определение

Базовыми элементами, которыми оперирует алгебра логики, являются высказывания.

Высказывания строятся над множеством {B, ¬{\displaystyle \lnot }, ∧{\displaystyle \land }, ∨{\displaystyle \lor }, 0, 1}, где B — непустое множество, над элементами которого определены три операции:

¬{\displaystyle \lnot } отрицание (унарная операция),

∧{\displaystyle \land } конъюнкция (бинарная),

∨{\displaystyle \lor } дизъюнкция (бинарная),

а логический ноль и логическая единица 1 — константы.

Так же используются названия

• Дизъю́нкт — пропозициональная формула, являющаяся дизъюнкцией одного или более литералов (например x1∨¬x2∨x4{\displaystyle x_{1}\lor \neg x_{2}\lor x_{4}}).
• Конъюнкт — пропозициональная формула, являющаяся конъюнкцией одного или более литералов (например x1∧¬x2∧x4{\displaystyle x_{1}\land \neg x_{2}\land x_{4}}).

Унарная операция отрицания в тексте формул оформляется либо в виде значка перед операндом (¬x{\displaystyle \lnot x}) либо в виде черты над операндом (x¯{\displaystyle {\bar {x}}}), что компактнее, но в целом менее заметно.

История

Термин «булева алгебра» чтит Джорджа Буля (1815–1864), английского математика-самоучки. Первоначально он представил алгебраическую систему в небольшой брошюре «Математический анализ логики» , опубликованной в 1847 году в ответ на продолжающийся общественный спор между Августом Де Морганом и Уильямом Гамильтоном , а затем в более содержательной книге «Законы мысли» , опубликованной в 1854. Формулировка Буля отличается от описанной выше в некоторых важных отношениях. Например, конъюнкция и дизъюнкция в Boole не были парными операциями. Булева алгебра появилась в 1860-х годах в работах Уильяма Джевонса и Чарльза Сандерса Пирса . Первое систематическое представление булевой алгебры и дистрибутивных решеток причитается 1890 Vorlesungen от Эрнста Шрёдера . Первое обширное исследование булевой алгебры на английском языке — это Универсальная алгебра А. Н. Уайтхеда 1898 года . Булева алгебра как аксиоматическая алгебраическая структура в современном аксиоматическом смысле начинается со статьи Эдварда В. Хантингтона 1904 года . Булева алгебра достигла зрелости как серьезная математика с работами Маршалла Стоуна в 1930-х годах и с Теорией решеток 1940 года Гаррета Биркгофа . В 1960-х годах Пол Коэн , Дана Скотт и другие нашли глубокие новые результаты в математической логике и аксиоматической теории множеств, используя ответвления булевой алгебры, а именно модели с принуждением и булевозначные модели .

Обобщения

Удаление требования существования единицы из аксиом булевой алгебры дает «обобщенные булевы алгебры». Формально дистрибутивная решетка B является обобщенной булевой решеткой, если она имеет наименьший элемент 0 и для любых элементов a и b в B таких, что a ≤ b , существует элемент x такой, что a ∧ x = 0 и a ∨ x = б. Определяя a ∖ b как единственный x такой, что (a ∧ b) ∨ x = a и (a ∧ b) ∧ x = 0, мы говорим, что структура (B, ∧, ∨, ∖, 0) является обобщенной булевой алгебры , а (B, ∨, 0) — обобщенная булева полурешетка . Обобщенные булевы решетки — это в точности идеалы булевых решеток.

Структура, которая удовлетворяет всем аксиомам булевых алгебр, кроме двух аксиом дистрибутивности, называется решеткой с ортодополнениями . Ортодополняемые решетки естественным образом возникают в квантовой логике как решетки замкнутых подпространств для сепарабельных гильбертовых пространств .

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

Определение.
Логическая функция MIN в двухзначной (двоичной) логике называется конъюнкция (логи́ческое «И», логи́ческое умноже́ние или просто «И»).

Правило: результат равен наименьшему операнду.

Описание.
В булевой алгебре конъюнкция — это функция двух, трёх или более переменных (они же — операнды операции, они же — аргументы функции). Переменные могут принимать значения из множества {,1}{\displaystyle \{0,1\}}. Результат также принадлежит множеству {,1}{\displaystyle \{0,1\}}. Вычисление результата производится по простому правилу, либо по таблице истинности. Вместо значений ,1{\displaystyle 0,1} может использоваться любая другая пара подходящих символов, например false,true{\displaystyle false,true} или F,T{\displaystyle F,T} или «ложь», «истина», но при таком обозначении необходимо дополнительно доопределять старшинство, например, true>false{\displaystyle true>false}, при цифровом обозначении старшинство естественно 1>{\displaystyle 1>0}.
Правило: результат равен 1{\displaystyle 1}, если все операнды равны 1{\displaystyle 1}; во всех остальных случаях результат равен {\displaystyle 0}.

Таблицы истинности:
для бинарной конъюнкции

a{\displaystyle a}	b{\displaystyle b}	a∧b{\displaystyle a\land b}
{\displaystyle 0}	{\displaystyle 0}	{\displaystyle 0}
1{\displaystyle 1}	{\displaystyle 0}	{\displaystyle 0}
{\displaystyle 0}	1{\displaystyle 1}	{\displaystyle 0}
1{\displaystyle 1}	1{\displaystyle 1}	1{\displaystyle 1}

для тернарной конъюнкции

a{\displaystyle a}	b{\displaystyle b}	c{\displaystyle c}	a∧b∧c{\displaystyle a\land b\land c}
1
1
1	1
1
1	1
1	1
1	1	1	1

Конъюнкция коммутативна, ассоциативна и дистрибутивна по отношению к слабой дизъюнкции.

Связь с естественным языком

Часто указывают на сходство между конъюнкцией и союзом «и» в естественном языке. Составное утверждение «A и B» считается истинным, когда истинны оба утверждения A и B, в противном случае составное утверждение ложно. Это в точности соответствует определению конъюнкции в булевой алгебре, если «истину» обозначать как 1{\displaystyle 1}, а «ложь» как {\displaystyle 0}. При этом часто делают стандартную оговорку о неоднозначности естественного языка. Например, в зависимости от контекста союз «и» может нести дополнительный оттенок «и тогда», «и поэтому», «и потом». Отличие логики естественного языка от математической остроумно выразил американский математик Стивен Клини, заметив, что в естественном языке «Мэри вышла замуж и родила ребёнка» — не то же самое, что «Мэри родила ребёнка и вышла замуж».

Сравнительные операторы

В программировании сравнительные операторы используются для сравнения значений и оценки значения отдельного булева значения true или false.

В таблице ниже показаны булевы операторы сравнения.

Оператор	Значение
==	равно
! =	не равно
<	меньше
>	больше
<=	меньше или равно
>=	больше или равно

Чтобы понять принцип работы этих операторов, присвоим два целочисленных значения двум переменным в программе Go:

Поскольку в этом примере имеет значение , эта переменная меньше со значением .

Используем эти две переменные и их значения для проверки операторов из предыдущей таблицы. В этой программе вы предписываете Go вывести результат true или false для каждого оператора сравнения. Чтобы лучше понять результат, укажите Go распечатать строку, чтобы показывать, что именно оценивается:

Следуя математической логике, Go оценивает выражения следующим образом:

• 5 () равно 8 ()? false
• 5 не равно 8? true
• 5 меньше 8? true
• 5 больше 8? false
• 5 меньше или равно 8? true
• 5 не меньше или равно 8? false

Хотя здесь использовались целые числа, вы можете заменить их значениями с плавающей точкой.

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

Вы можете посмотреть практический пример сравнения строк:

Строка не равна строке , поскольку они не точно совпадают; одно значение начинается с заглавной , а другое — с в нижнем регистре. Однако если вы добавите другую переменную, которой присвоено значение , они будут равняться:

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

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

Предыдущий блок кода оценил, что не равняется .

Обратите внимание на различия между операторами и. Первый оператор является оператором присвоения, который задает одно значение равным другому

Второй оператор является оператором сравнения и оценивает, что два значения будут равны

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

Программирование

В компьютерных языках используется два основных варианта дизъюнкции: логическое «ИЛИ» и побитовое «ИЛИ». Например, в языках C/C++/Perl/PHP логическое «ИЛИ» обозначается символом «||», а побитовое — символом «|». В языках Pascal/Delphi оба вида дизъюнкции обозначаются с использованием ключевого слова «or», а результат действия определяется типом операндов. Если операнды имеют логический тип (например, Boolean) — выполняется логическая операция, если целочисленный (например, Byte) — поразрядная.

Логическое «ИЛИ» применяется в операторах условного перехода или в аналогичных случаях, когда требуется получение результата false{\displaystyle false} или true{\displaystyle true}. Например:

if (a || b)
{
    /* какие-то действия */
};

Результат будет равен false{\displaystyle false}, если оба операнда равны false{\displaystyle false} или {\displaystyle 0}. В любом другом случае результат будет равен true{\displaystyle true}.

При этом применяется стандартное соглашение: если значение левого операнда равно true{\displaystyle true}, то значение правого операнда не вычисляется (вместо b{\displaystyle b} может стоять сложная формула). Такое соглашение ускоряет исполнение программы и служит полезным приёмом в некоторых случаях. Компилятор Delphi поддерживает специальную директиву, включающую

{$B-}

или выключающую

{$B+}

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

if (a == NULL || a->x == )
{
    /* какие-то действия */
};

В этом примере, благодаря проверке в левом операнде, в правом операнде никогда не произойдёт разыменования нулевого указателя.

Побитовое «ИЛИ» выполняет обычную операцию булевой алгебры для всех битов левого и правого операнда попарно. Например,

если
a =	011001012{\displaystyle 01100101_{2}}
b =	001010012{\displaystyle 00101001_{2}}
то
a ИЛИ b =	011011012{\displaystyle 01101101_{2}}

Обозначения

Наиболее часто встречаются следующие обозначения для операции конъюнкции:

a∧b,a&&b,a&b,a⋅b,aANDb,min(a,b){\displaystyle a\land b,\quad a\And \And b,\quad a\And b,\quad a\cdot b,\quad a\,\,\mathrm {AND} \,\,b,\quad \min(a,b)}

(в случае использования точки, как знака логического умножения, этот знак, как и при обычном умножении в алгебре, может быть опущен: ab{\displaystyle ab}).

При этом обозначение a∧b{\displaystyle a\land b}, рекомендованное стандартом ISO 31-11, наиболее широко распространено в современной математике и математической логике, где оно, впрочем, конкурирует со знаком амперсанда &; последний, появившись ещё в I веке до н. э. как графическое сокращение (лигатура) латинского союза et ‘и’, уже Якобом и Иоганном Бернулли в 1685 году использовался в качестве логической связки (у них он, однако, связывал не высказывания, а понятия). Джордж Буль (а за ним — и другие пионеры систематического применения символического метода к логике: У. С. Джевонс, Э. Шрёдер, П. С. Порецкий) обозначал конъюнкцию знаком ⋅{\displaystyle \cdot } — как обычное умножение. Символ ⋀ (перевёрнутый знак дизъюнкции) в качестве обозначения конъюнкции был предложен Арендом Гейтингом (1930).

Обозначение для конъюнкции было использовано и в раннем языке программирования Алгол 60. Однако из-за отсутствия соответствующего символа в стандартных наборах символов (например, в ASCII или EBCDIC), применявшихся на большинстве компьютеров, в получивших наибольшее распространение языках программирования были предусмотрены иные обозначения для конъюнкции. Так, в Фортране IV и PL/I применялись соответственно обозначения и (с возможностью замены последнего на ключевое слово ); в языках Паскаль и Ада используется зарезервированное слово ; в языках C и C++ применяются обозначения для побитовой конъюнкции и для логической конъюнкции).

Наконец, при естественном упорядочении значений истинности двузначной логики (когда полагают, что <1{\displaystyle 0<1}), оказывается, что (a∧b)=min(a,b).{\displaystyle (a\land b)\,=\,\min(a,b).} Таким образом, конъюнкция оказывается частным случаем операции вычисления минимума; это открывает наиболее естественный способ определить операцию конъюнкции в системах многозначной логики (хотя иногда рассматривают и другие способы обобщения конъюнкции — например, такой: (a∧b)=ab(mod⁡k){\displaystyle (a\land b)\,=\,ab\;(\operatorname {mod} k)} в случае k-значной логики, в которой множество значений истинности представлено начальным отрезком {,…,k−1}{\displaystyle \{0,\dots ,k-1\}} полугруппы N{\displaystyle \mathbb {N} } натуральных чисел).

Классификация булевых функций

По количеству n входных операндов, от которых зависит значение на выходе функции, различают нульарные (n = 0), унарные (n = 1), бинарные (n = 2), тернарные (n = 3) булевы функции и функции от большего числа операндов.

По количеству единиц и нулей в таблице истинности отличают узкий класс сбалансированных булевых функций (также называемых уравновешенными или равновероятностными, поскольку при равновероятных случайных значениях на входе или при переборе всех комбинаций по таблице истинности вероятность получения на выходе значения 1 равна 1/2) от более широкого класса несбалансированных булевых функций (так же называемых неуравновешенными, поскольку вероятность получения на выходе значения 1 отлична от 1/2). Сбалансированные булевы функции в основном используются в криптографии.

По зависимости значения функции от перестановки её входных битов различают симметричные булевы функции (значение которых зависит только от количества единиц на входе) и несимметричные булевы функции (значение которых так же зависит от перестановки её входных бит).

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

По алгебраической степени нелинейности отличают линейные булевы функции (АНФ которых сводится к линейной сумме по модулю 2 входных значений) и нелинейные булевы функции (АНФ которых содержит хотя бы одну нелинейную операцию конъюнкции входных значений). Примерами линейных функций являются: сложение по модулю 2 (исключающее «ИЛИ», XOR), эквивалентность, а также все булевы функции, АНФ которых содержит лишь линейные операции сложения по модулю 2 без конъюнкций. Примерами нелинейных функций являются: конъюнкция («И», AND), штрих Шеффера («НЕ-И», NAND), стрелка Пирса («НЕ-ИЛИ», NOR), а также все булевы функции, АНФ которых содержит хотя бы одну нелинейную операцию конъюнкции.

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

Алгебра – это раздел математики, предназначенный для описания действий над переменными величинами, которые принято обозначать строчными буквами латинского алфавита – а, b, x, y и т.д. Действия над переменными величинами записываются в виде математических выражений.

Термин «логика» происходит от древнегреческого “logos”, означающего «слово, мысль, понятие, рассуждение, закон».

Алгеброй логики называется аппарат, который позволяет выполнять действия над высказываниями.

Алгебру логику называют также алгеброй Буля, или булевой алгеброй, по имени английского математика Джорджа Буля, разработавшего в XIX веке ее основные положения. В булевой алгебре высказывания принято обозначать прописными латинскими буквами: A, B, X, Y. В алгебре Буля введены три основные логические операции с высказываниями? Сложение, умножение, отрицание. Определены аксиомы (законы) алгебры логики для выполнения этих операций. Действия, которые производятся над высказываниями, записываются в виде логических выражений.

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

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

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

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

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

• ИЛИ (логическое сложение, дизъюнкция);

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

Логическое отрицание является одноместной операцией, так как в ней участвует одно высказывание. Логическое сложение и умножение — двуместные операции, в них участвует два выска¬зывания. Существуют и другие операции, например операции следования и эквивалентности, правило работы которых можно вывести на основании основных операций.

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

• таблица истинности одноместной логической операции состоит из двух строк: два различных значения аргумента — «истина» (1) и «ложь» (0) и два соответствующих им значения функции;
• в таблице истинности двуместной логической операции — четыре строки: 4 различных сочетания значений аргументов — 00, 01, 10 и 11 и 4 соответствующих им значения функции;
• если число высказываний в логическом выражении N, то таблица истинности будет содержать 2 N строк, так как существует 2 N различных комбинаций возможных значений аргументов.

Математика и логика

Известнейший Готфрид Вильгельм Лейбниц сформулировал понятие «математическая логика», задачи которой были доступны для понимания только узкому кругу ученых. Особого интереса это направление не вызывало, и до середины XIX века о математической логике знали немногие.

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

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

Примечания

1. Гутников В. С. . Интегральная электроника в измерительных приборах. — Л.: Энергия, 1974. — 144 с. — С. 14—16.
2. , с. 534.
3. Стяжкин Н. И. . Формирование математической логики. — М.: Наука, 1967. — 508 с. — С. 320, 349, 352, 368.
4. . // Website Jeff Miller Web Pages. Дата обращения 5 февраля 2016.
5. , с. 149—150.
6. , с. 30.
7. Пратт Т. . Языки программирования: разработка и реализация. — М.: Мир, 1979. — 574 с. — С. 352, 439.
8. Грогоно П. . Программирование на языке Паскаль. — М.: Мир, 1982. — 384 с. — С. 51.
9. Вегнер П. . Программирование на языке Ада. — М.: Мир, 1983. — 240 с. — С. 68.
10. Эллис М., Строуструп Б. . Справочное руководство по языку программирования C++ с комментариями. — М.: Мир, 1992. — 445 с. — ISBN 5-03-002868-4. — С. 65, 86—87.
11. Яблонский С. В. . Введение в дискретную математику. — М.: Наука, 1979. — 272 с. — С. 9—10, 37.
12. Рвачёв В. Л. . Теория R-функций и некоторые её приложения. — Киев: Наукова думка, 1982. — 552 с. — С. 38, 66.

Примеры

∧ 1 1 1

∨ 1 1 1 1 1

а 1 ¬ а 1

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

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

∧ а б 1 а а а б б б 1 а б 1

∨ а б 1 а б 1 а а а 1 1 б б 1 б 1 1 1 1 1 1

Икс а б 1 ¬ х 1 б а

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

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

• Для любого натурального числа п , множество всех положительных делителей из п , определяющее а ≤ Ь , если а делит Ь , образует распределительную решетку . Эта решетка является булевой алгеброй тогда и только тогда, когда n не содержит квадратов . Нижний и верхний элементы этой булевой алгебры — это натуральные числа 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 .

Аксиоматика

Хантингтон 1904 аксиомы булевой алгебры
Idn 1	х ∨ 0 = х	Idn 2	х ∧ 1 = х
Cmm 1	х ∨ у = у ∨ х	Cmm 2	х ∧ у = у ∧ х
Dst 1	х ∨ ( у ∧ г ) = ( х ∨ у ) ∧ ( х ∨ г )	Dst 2	x ∧ ( y ∨ z ) = ( x ∧ y ) ∨ ( x ∧ z )
Капрал 1	х ∨ ¬ х = 1	Капрал 2	х ∧ ¬ х = 0
Сокращения Idn Идентичность См Коммутативность Dst Распределительность Капрал Дополнения

Первая аксиоматизация булевых решеток / алгебр в целом была дана английским философом и математиком Альфредом Норт Уайтхедом в 1898 году. Она включала указанные и дополнительно x ∨1 = 1 и x ∧0 = 0. В 1904 году американский математик Эдвард В. Хантингтон (1874–1952) дал, вероятно, самую экономную аксиоматизацию, основанную на ∧, ∨, ¬, даже доказав законы ассоциативности (см. Вставку). Он также доказал, что эти аксиомы независимы друг от друга. В 1933 году Хантингтон изложил следующую элегантную аксиоматизацию булевой алгебры. Для этого требуется всего одна двоичная операция + и унарный функциональный символ n , который следует читать как «дополнение», что удовлетворяет следующим законам:

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

Герберт Роббинс сразу же спросил: если уравнение Хантингтона заменить двойственным, а именно:

4. Уравнение Роббинса : n ( n ( x + y ) + n ( x + n ( y ))) = x ,

образуют ли (1), (2) и (4) основу булевой алгебры? Называя (1), (2) и (4) алгеброй Роббинса , тогда возникает вопрос: каждая ли алгебра Роббинса является булевой алгеброй? Этот вопрос (который стал известен как гипотеза Роббинса ) оставался открытым в течение десятилетий и стал любимым вопросом Альфреда Тарского и его учеников. В 1996 году Уильям МакКьюн из Аргоннской национальной лаборатории , опираясь на более ранние работы Ларри Воса, Стива Винкера и Боба Вероффа, ответил на вопрос Роббинса утвердительно: каждая алгебра Роббинса является булевой алгеброй. Решающим фактором для доказательства МакКьюна была разработанная им программа автоматизированного мышления EQP . Об упрощении доказательства МакКьюна см. Dahn (1998).

Дальнейшая работа была проделана для сокращения количества аксиом; см. Минимальные аксиомы для булевой алгебры .

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

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

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

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

Здесь два переключателя A и B соединены вместе, образуя последовательную цепь. Поэтому в вышеупомянутой цепи оба выключателя A «И» B должны быть замкнуты (логика «1»), чтобы включить лампу. Другими словами, оба переключателя должны быть замкнуты или должны иметь логическую «1», чтобы лампа горела.

Тогда логический элемент этого типа (логический элемент «И» ) создает выход только тогда, когда все его входы истины. В терминах булевой алгебры вывод будет ИСТИНА, только когда все его входы ИСТИНА. В электрическом смысле логическая функция «И» равна последовательной цепи, как показано выше.

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

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

Логические «И» элементы доступны как стандартные пакеты ic, такие как общие TTL 74LS08 Четырехпозиционные 2-входные положительные элементы «И» (или эквивалент CMOS 4081), TTL 74LS11 Тройные 3-входные положительные элементы «И» или 74LS21 Двойные 4-входные положительные элементы «И». «И» ворота можно также «каскадировать» вместе для создания цепей с более чем 4 входами.

Определение

Булева алгебра является шести- кортеж , состоящий из множества A , оснащен двумя бинарными операциями ∧ ( так называемые «концами» или «и»), ∨ ( так называемый «присоединиться» или «или»), А унарная операция ¬ ( так называемый » дополнять или не дополнять) и два элемента 0 и 1 в A (называемые «нижний» и «верхний», или «наименьший» и «наибольший» элементы, также обозначаемые символами ⊥ и ⊤ соответственно), такие, что для Для всех элементов a , b и c из A верны следующие аксиомы

a ∨ ( b ∨ c ) = ( a ∨ b ) ∨ c	a ∧ ( b ∧ c ) = ( a ∧ b ) ∧ c	ассоциативность
а ∨ б = б ∨ а	а ∧ б = б ∧ а	коммутативность
а ∨ ( а ∧ б ) = а	а ∧ ( а ∨ б ) = а	поглощение
а ∨ 0 = а	а ∧ 1 = а	идентичность
a ∨ ( b ∧ c ) = ( a ∨ b ) ∧ ( a ∨ c )	a ∧ ( b ∨ c ) = ( a ∧ b ) ∨ ( a ∧ c )	распределенность
а ∨ ¬ а = 1	а ∧ ¬ а = 0	дополняет

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

(В более старых работах некоторые авторы требовали, чтобы 0 и 1 были отдельными элементами, чтобы исключить этот случай.)

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

Из трех последних пар аксиом выше (тождество, дистрибутивность и дополнения) или из аксиомы поглощения следует, что

a = b ∧ a     тогда и только тогда, когда     a ∨ b = b .

Отношение ≤, определяемое как a ≤ b, если эти эквивалентные условия выполняются, является частичным порядком с наименьшим элементом 0 и наибольшим элементом 1. Встреча a ∧ b и соединение a ∨ b двух элементов совпадают с их точной гранью и супремумом соответственно, относительно ≤.

Первые четыре пары аксиом составляют определение ограниченной решетки .

Из первых пяти пар аксиом следует, что любое дополнение единственно.

Набор аксиом самодвойственен в том смысле, что если заменить ∨ на и 0 на 1 в аксиоме, результатом снова будет аксиома. Следовательно, применяя эту операцию к булевой алгебре (или булевой решетке), можно получить другую булеву алгебру с теми же элементами; это называется его двойственным .