Операции булевой алгебры: Булева алгебра — Boolean algebra

Булевы решетки и булевы алгебры

Определение: Дистрибутивная решетка с дополнениями называется Булевой решеткой.

Определение: Булева Алгебра А=(А, ∨, ∧, ⌐, 0, 1) есть множество А на котором определены три операции:
1) x∨y: AxA → A
2) x∧y: AxA → A
3) ⌐x: A → A
и два отмеченных элемента (0, 1) (универсальные границы) удовлетворяющие следующим аксиомам ∀ x,y,z ∈A:

B1) x∧x=x, x∨x=x
B2) x∧y=y∧x, x∨y = y∨x
B3) x∧(y∧z) = (x∧y)∧z, (x∨y)∨z = x∨(y∨z)
B4) x∧(x∨y) = x, x∨(x∧y) = x
B5) x∧(y∨z) = (x∧y)∨(x∧z), x∨(y∧z) = (x∨y)∧(x∨z)
B6) ⌐⌐x = x
B7) x∧1=x, x∧0=0, x∨1=1, x∨0=x
B8) x∨⌐x=1, x∧⌐x=0
B9) ⌐(x∨y)=⌐y ∧⌐x, ⌐(x∧y)= ⌐x ∨ ⌐y – правило де Моргана.

Замечание: иногда вместо x∧y пишут x&y, xy xy

Пример 1: Если U – есть конечное множество с n элементами и P(U) — есть множество всех его 2n подмножеств, то система (P(U), ∨, ∧,-,0,1) – есть Булева алгебра в которой для подмножеств А и В.
A∨B=A∪B
A∧B=A∩B
A=U-A
0=∅
I=U

Пример 2: система ({0,1},∨,&,¬,0,1) – есть Булева алгебра.

Замечание: (Принцип двойственности): Если в Булевой алгебре истинно некоторое равенство, построенное с помощью ∨, &, ¬, 0, 1 с некоторым расставлением скобок, то истинно и равенство, полученное из исходного заменой: ∨ на &, & на ∨, 0 на 1, 1 на 0 с тем же расставлением скобок.

Теорема (Связь булевых решеток и булевых алгебр). Если алгебра является булевой алгеброй, то – булева решётка. Если алгебра – булева решётка, то , где операция ¬ определена как дополнение в булевой решётке, 0 и 1 – соответственно как ноль и единица в булевой решётке – булева алгебра.

Замечание: всякая Булева алгебра (А, ∨, ∧, ¬,0, 1) – есть решетка (А, ∨, ∧) в которой можно задать отношение частичного порядка, определенного соотношением a ≤ b ↔ a*b=a (или a∨b=b), тогда система (А, ≤) – есть ЧУМ.

Теорема: если A_i =(А_i, ∨_i, ∧_i, ¬ _i,0 i, 1 i) i=1,2 – есть две Булевых алгебры, то A₁ ≅ A₂ ↔ (А₁, ≤₁) ↔ (А₂, ≤₂). Другими словами Булевы алгебры A₁ ≅ A₂ ⇔ когда A₁ и A₂ – изоморфны как ЧУМ.
Без доказательства.

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

Следствие:
1) конечные Булевы Алгебры изоморфны ⇔ они равноправны
2) Число элементов Булевой алгебры равно степени 2
3) Теорема Стоуна (о представлении) справедлива для бесконечной Булевой алгебры.

2 4 Законы Булевой алгебры

2.4. Законы Булевой алгебры.

БА базируется на нескольких аксиомах:

Аксиомы операции отрицания:

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

Для примера преобразуем на основе законов БА функцию:

Раскроем скобки:

Так как закон дополнительности, то

Схемы, реализующие заданную функцию и полученную, представлены на рисунках 2.6 а и 2.6.б.

Аналогично можно минимизировать рассмотренное ранее выражение (2.1):

Для минимизации были использованы соотношения:

Закон дополнительности:

Закон универсального множества:

Схема, реализующая полученную функцию, представлена на рис.2.7.

Математика булевой алгебры (Стэнфордская энциклопедия философии)

Булева алгебра (BA) — это множество \ (A \) вместе с двоичными операции + и \ (\ cdot \) и унарная операция \ (- \), а также элементы 0, 1 из \ (A \) такие, что выполняются следующие законы: коммутативность и ассоциативные законы сложения и умножения, законы распределения как для умножения над сложением, так и для сложения над умножение и следующие специальные законы:

Эти законы лучше понять на базовом примере BA, состоящий из набора \ (A \) подмножеств множества \ (X \) замкнутых при операциях объединения, пересечения, дополнения с относительно \ (X \), с членами \ (\ varnothing \) и \ (X \). Можно легко вывести из этих аксиом многие элементарные законы, имея в виду этот пример для мотивации. Любая БА имеет естественный частичный порядок \ (\ le \) определил на нем, сказав, что \ (x \ le y \) тогда и только тогда, когда \ (x + у = у \). В нашем основном примере это соответствует \ (\ substeq \). Из Особое значение имеет двухэлементная БА, образованная набором \ (X \), чтобы иметь только один элемент. Двухэлементная БА показывает прямую связь с элементарной логикой. Два члена, 0 и 1, соответствуют к лжи и правде соответственно.Затем логические операции выражают обычные таблицы истинности для дизъюнкции (с \ (+) \), конъюнкции (с \ (\ cdot) \) и отрицанием (с \ (-) \). Важный элементарный В результате уравнение выполняется во всех БА тогда и только тогда, когда оно выполняется в двухэлементный БА. Затем мы определяем \ (x \ oplus y = (x \ cdot -y) + (y \ cdot -x) \). Тогда \ (A \) вместе с \ (\ oplus \) и \ (\ cdot \), вдоль с 0 и 1, образует кольцо с единицей, в котором каждый элемент идемпотентный. Наоборот, для такого кольца с добавлением \ (\ oplus \) и умножение, определите \ (x + y = x \ oplus y \ oplus (x \ cdot y) \) и \ (- x = 1 \ oplus x \).Это превращает кольцо в BA. Эти двое процессы противоположны друг другу и показывают, что теория Булевых алгебр и колец с единицей, в которых каждый элемент идемпотенты по определению эквивалентны. Это ставит теорию БА в стандартный объект исследования в алгебре. Атом в БА — это ненулевой элемент \ (a \) такой, что не существует элемента \ (b \) с \ (0 \ lt б \ л а \). БА является атомарной, если каждый ненулевой элемент БА выше атом. Конечные БА атомарны, как и многие бесконечные БА.Под частичный порядок \ (\ le \) выше, \ (x + y \) является точной верхней границей \ (x \) и \ (y \), а \ (x \ cdot y \) — точная нижняя граница \ (х \) и \ (у \). Мы можем обобщить это: \ (\ Sigma X \) — наименьшее верхняя граница множества \ (X \) элементов, а \ (\ Pi X \) — наибольшее нижняя граница множества \ (X \) элементов. Это не для всех множества во всех булевых алгебрах; если они существуют всегда, логическое алгебра называется полной.

Некоторые алгебраические конструкции имеют очевидные определения и простые свойства БА: подалгебры, гомоморфизмы, изоморфизмы и прямые произведения (даже бесконечного числа алгебр).Некоторые другие Стандартные алгебраические конструкции более характерны для БА. Идеал в BA — это подмножество \ (I \), замкнутое относительно +, с 0 в качестве члена, и такое что если \ (a \ le b \ in I \), то также \ (a \ in I \). Хотя нет сразу очевидно, это то же самое, что и теоретико-кольцевой концепция. Существует двойственное понятие фильтра (без аналога в кольца в целом). Фильтр — это подмножество \ (F \), замкнутое относительно \ (\ cdot \), имеющий 1 в качестве члена и такой, что если \ (a \ ge b \ in F \), то также \ (а \ в F \). Ультрафильтр на \ (A \) — это фильтр \ (F \) с следующие свойства: \ (0 \ not \ in F \), и для любого \ (a \ in A \) либо \ (а \ в F \) или \ (- а \ в F \).Для любого \ (a \ in A \) пусть

Тогда \ (S \) — изоморфизм на БА подмножеств множества \ (X \) все ультрафильтры на \ (A \). Это устанавливает основной камень теорема о представлении и проясняет происхождение БА как конкретных алгебры множеств. Более того, множества \ (S (a) \) можно объявить база топологии на \ (X \), что превращает \ (X \) в полностью несвязное компактное хаусдорфово пространство. Это устанавливает однозначный соответствие между классом БА и классом таких пробелы.Как следствие, очень часто используемые в теории БА, многие топологические теоремы и концепции имеют последствия для БА. Если \ (x \) является элементом БА, пусть \ (0x = -x \) и \ (1x = x \). Если \ ((x \) (0), \ (\ ldots x (m — 1)) \) — конечная последовательность элементов BA \ (A \), то каждый элемент подалгебры в \ (A \), порожденный \ (\ {x (0), \ ldots, x (m — 1) \} \) можно записать как сумму мономов \ (e (0) x (0) \ cdot \ ldots \ cdot e (m — 1) x (m — 1) \) для \ (e \) в некотором наборе функций, отображающих \ (m = \ {0, \ ldots, m — 1 \} \) в \ (2 = \ {0, 1 \} \). Это алгебраическое выражение дизъюнктивной нормальной формы Теорема сентенциальной логики. Функция \ (f \) из множества \ (X \) образующие БА \ (А \) в БА \ (B \) продолжаются до гомоморфизм тогда и только тогда, когда

всегда означает, что

Это критерий расширения Сикорского. Каждый BA \ (A \) может быть вложено в полный BA \ (B \) таким образом, что каждый элемент \ (B \) — наименьшая верхняя граница набора элементов \ (A \).\ (B \) есть единственна с точностью до \ (A \) — изоморфизма и называется пополнением \ (А \). Если \ (f \) — гомоморфизм БА \ (А \) в полную БА \ (B \), и если \ (A \) — подалгебра в \ (C \), то \ (f \) может быть продолжается до гомоморфизма \ (C \) в \ (B \). Это Теорема Сикорского о продолжении. Еще одно общее алгебраическое понятие применительно к булевым алгебрам — понятие свободного алгебра. Это может быть конкретно сконструировано для БА. А именно бесплатные BA на \ (\ kappa \) — это БА замкнутых открытых подмножеств двух элементов дискретное пространство возведено в степень \ (\ kappa \).

Есть много важных специальных классов булевой алгебры. как для внутренней теории БА, так и для заявок:

• Атомарные БА, уже упомянутые выше.
• безатомных БА, которые определяются как БА без атомов. Например, любое бесконечное свободный БА безатомен.
• Полные BA, определенные выше. Это специально важен в основах теории множеств.
• Интервальные алгебры. Они получены из линейно упорядоченных множеств \ ((L, \ lt) \) с первым элементом следующим образом.Один берет самое маленькое алгебра подмножеств \ (L \), содержащая все полуоткрытые интервалы [\ (a, b) \) с \ (a \) в \ (L \) и \ (b \) в \ (L \) или равно \ (\ infty \). Эти БА полезны в изучение алгебр Линденбаума-Тарского. Каждый счетный БА изоморфна интервальной алгебре, а значит, счетная БА может быть описывается указанием упорядоченного набора, который изоморфен соответствующая интервальная алгебра.
• Древовидные алгебры. Дерево — это частично упорядоченное множество \ ((T, \ lt) \) в в котором множество предшественников любого элемента упорядочено.Данный такое дерево, рассматривается алгебра подмножеств \ (T \), порожденная всеми множествами вида \ (\ {b: a \ le b \} \) для некоторого \ (a \) в \ (Т \).
• Суператомные БА. Это БА которые не только атомарны, но таковы, что каждая подалгебра и гомоморфный образ атомарен.

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

1. Клеточность \ (c (A) \) БА есть верхняя грань мощности множеств попарно непересекающихся элементов \ (A \).
2. Подмножество \ (X \) БА \ (A \) является независимым, если \ (X \) — набор свободных образующих подалгебры, генерирует. Независимость \ (A \) есть супремум мощности независимых подмножеств \ (A \).
3. Подмножество \ (X \) БА \ (A \) плотно в \ (A \), если каждый ненулевой элемент \ (A \) является \ (\ ge \) ненулевым элементом \(ИКС\). \ (\ Pi \) — вес \ (A \) — это наименьшая мощность плотного подмножества \ (A \).
4. Два элемента \ (x, y \) из \ (A \) несравнимы если ни один из них не является \ (\ le \) другим. Супремум мощностей подмножество \ (X \) в \ (A \), состоящее из попарно несравнимых элементов — это несравнимость \ (A \).
5. Подмножество \ (X \) из \ (A \) неизбыточно, если ни один элемент \ (X \) находится в подалгебре, порожденной другими.

Важным фактом, касающимся клеточности, является метод Эрдеша-Тарского. Теорема: если клеточность БА — особый кардинал, то существует фактически представляет собой набор непересекающихся элементов такого размера; на клеточность штатный лимит (недоступен), есть контрпримеры. Каждый бесконечная полная БА имеет независимое подмножество того же размера, что и алгебра. Каждый бесконечный BA \ (A \) имеет неизбыточную несравнимую подмножество, размер которого равен \ (\ pi \) — весу \ (A \). Каждый интервал алгебра имеет счетную независимость.Суператомная алгебра не даже иметь бесконечное независимое подмножество. Любая древовидная алгебра может быть вложено в интервальную алгебру. БА только с удостоверением личности автоморфизм называется жестким. Существуют жесткие полные БА, а также жесткие интервальные алгебры и жесткие древовидные алгебры.

Совсем недавно многие кардинальные функции типа min-max были учился. Например, малая независимость — это наименьший размер бесконечное максимальное независимое множество; и малая клеточность — это наименьший размер бесконечного разбиения единицы.

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

Очень важная конструкция, которая переносится на многие логики и многих алгебр, кроме булевых, является построением Булева алгебра связана с предложениями в некоторой логике.В Самый простой случай — это логика предложений. Здесь есть символы предложений, и общие связки, составляющие из них более длинные предложения: дизъюнкция, союз и отрицание. Дан набор \ (A \) предложений в этом языке два предложения \ (s \) и \ (t \) эквивалентны по модулю \ (A \) тогда и только тогда, когда двусмысленность между ними является логическим следствие \ (A \). Классы эквивалентности могут быть преобразованы в БА. такой, что + соответствует дизъюнкции, \ (\ cdot \) — конъюнкции и \ (- \) к отрицанию. Любая БА изоморфна одной из этих форм.Можно сделайте что-нибудь подобное для теории первого порядка. Пусть \ (T \) — теория первого порядка в языке первого порядка \ (L \). Мы называем формулы \ (\ phi \) и \ (\ psi \) эквивалент при условии, что \ (T \ vdash \ phi \ leftrightarrow \ psi \). Класс эквивалентности предложения \ (\ phi \) обозначается [\ (\ phi \)]. Пусть \ (A \) — совокупность всех классы эквивалентности по этому отношению эквивалентности. Мы можем сделать \ (A \) в БА следующими определениями, которые легко обосновано:

Каждая БА изоморфна БА Линденбаума-Тарского. алгебра.Однако одно из самых важных применений этих классических Алгебры Линденбаума-Тарского должны описать их для важных теорий. (обычно разрешимые теории). Для счетных языков это может быть делается путем описания их изоморфных интервальных алгебр. Обычно это дает доскональное знание теории. Вот несколько примеров:

В теории моделей можно принимать значения в любом полном БА, а не в двухэлементный БА. Эта теория булевозначных моделей была развита примерно в 1950–1970 годах, но с тех пор почти не работал. Но частный случай, булевозначные модели для теории множеств, очень авангард современных исследований в области теории множеств. Это фактически формирует эквивалентный способ взглянуть на форсирующую конструкцию Коэна, и имеет ряд технических преимуществ и недостатков. Философски это кажется более удовлетворительным, чем концепция принуждения. Мы описываем это случай теории множеств здесь; тогда станет очевидно, почему только завершать Рассмотрены БА.Пусть B — полная БА. Сначала мы определяем Булевозначный универсум \ (V (B) \). Обычный теоретико-множественный универсум можно отождествить с \ (V \) (2), где 2 — двухэлементная БА. Определение дается трансфинитной рекурсией, где \ (\ alpha, \ beta \) — порядковые числа, а \ (\ lambda \) — предельный порядковый номер:

где \ (\ dom (f) \) — область определения функции \ (f \), а \ (\ range (f) \) — диапазон функции \ (f \). \ (B \) -значная вселенная является собственно класс \ (V (B) \), который является объединением всех этих \ (V \) s. Следующий определяется довольно сложной трансфинитной рекурсией над обоснованно устанавливает значение теоретико-множественной формулы с элементами булевозначной вселенной, присвоенной его свободным переменным:

Рис.1: Репрезентативное изображение всех логических операций

Может быть 16 возможных комбинаций результатов между двумя логическими переменными, скажем X и Y.Эти результаты показаны в следующей таблице истинности —

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

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

F0: Null — Выходное значение false для всех входов логических переменных называется Null. Это эквивалентно двоичной константе 0. Функция эквивалентна логическому выражению F = 0.Соответственно следующим 16 комбинациям возможных исходов, существуют следующие логические операции —

F1: AND — Выходное значение «истина», когда оба входа логических переменных имеют значение «истина», в противном случае выходное значение «ложь» называется операцией «И». Это одна из основных логических операций. В логической алгебре он представлен оператором точка (.). Функция эквивалентна логическому выражению F = xy или F = x.y.

F2: Запрещение — Выход, истинный для одной переменной, истинной, но не для другой, называется запретом.Для функции F2 результат истинен, если x истинно, но не y. В логических алгебраических обозначениях это записывается как x / y. Функция эквивалентна логическому выражению F = xy ’.

F3: Передача — Выходное значение «истина» тогда и только тогда, когда одна из логических переменных имеет значение «истина», называется передачей. Для функции F3 результат истинен при условии, только если x истинно, независимо от y. В булевых алгебраических обозначениях это представляется просто записью x. Функция эквивалентна логическому выражению F = x.

F4: Запрещение — Выход, истинный для одной переменной, истинной, но не истинной для другой, называется запрещением. Функция F4 аналогична функции F2. Для F4 результат истинен, если y истинно, но не x. В логической алгебраической записи это записывается как y / x. Функция эквивалентна логическому выражению F = x’y.

F5: Передача — Выходное значение «истина» тогда и только тогда, когда одна из логических переменных имеет значение «истина», называется передачей. Функция F5 аналогична функции F3.Для F5 результат истинен при условии, только если y истинно независимо от x. В булевых алгебраических обозначениях это обозначается просто буквой y. Функция эквивалентна логическому выражению F = y.

F6: Исключающее ИЛИ — Выходное значение истинно только тогда, когда одна из логических переменных истинна, но не другая, называется Исключающее ИЛИ. Для этой функции результат истинен, если x или y истинны, но не оба одновременно. В булевой алгебре операция EX-OR представлена ​​оператором.Функция эквивалентна логическому выражению F = xy ‘+ x’y.

F7: OR — Выходное значение «истина», если одна или обе логические переменные истинны, называется операцией ИЛИ. Это одна из основных логических операций. Он представлен оператором Плюс (+) в булевой алгебре. Функция эквивалентна логическому выражению F = x + y.

F8: NOR — Операция, обратная OR, называется NOR. Его результат верен только тогда, когда обе переменные ложны.В булевой алгебре он представлен стрелкой вниз. Он записывается как. Функция эквивалентна логическому выражению F = (x + y) ’.

F9: Эквивалентность — Выходное значение «истина», только если обе переменные либо истинны, либо обе ложны, называется эквивалентностью. Это инверсия EX-OR, поэтому также называется Exclusive NOR (EX-NOR). В булевой алгебре он представлен как (xy) ’. Функция эквивалентна логическому выражению F = xy + x’y ‘.

F10: Дополнение — В функции F10 вывод является дополнением к одной из логических переменных.Результат истинен, если y ложно, независимо от x. В булевой алгебре он представлен как НЕ из Y. Он записывается как y ’. Функция эквивалентна логическому выражению F = y ’.

F11: Импликация — Выходное значение «истина», если одна из логических переменных имеет значение «ложь» или другое значение «истина», называется импликацией. В функции F11 вывод истинен, если либо y ложно, либо x истинно. В булевой алгебре он представлен как x y. Функция эквивалентна логическому выражению F = x + y ’.

F12: Дополнение — В функции F12 вывод является дополнением к одной из булевых переменных. Результат истинен, если x ложно, независимо от y. В булевой алгебре он представлен как НЕ x. Он записывается как x ’. Функция эквивалентна логическому выражению F = x ’.

F13: Импликация — Выходное значение «истина», если одна из логических переменных имеет значение «ложь» или другое значение «истина», называется импликацией. В функции F13 вывод истинен, если либо x ложно, либо y истинно.В булевой алгебре он представлен как y x. Функция эквивалентна логическому выражению F = x ’+ y.

F14: NAND — Операция, обратная AND, называется NAND. Это одна из основных логических операций. Результатом NAND является ложь, если обе логические переменные истинны, в противном случае — истина. В булевой алгебре он представлен стрелкой вверх (). Он записывается как x y. Функция эквивалентна логическому выражению F = (xy) ’.

F15: Идентичность — Выход, истинный для всех входов логических переменных, называется Идентификацией.Это эквивалентно двоичной константе 1. Функция эквивалентна логическому выражению F = 1.

Все возможные логические операции между двумя логическими переменными сведены в следующую таблицу —

Рис. 3: Таблица, в которой перечислены все логические функции с двумя переменными

Итак, основные логические операции — И, ИЛИ, НЕ, ИСКЛЮЧАЮЩЕЕ ИЛИ, ИСКЛЮЧИТЕЛЬНОЕ ИЛИ, НЕ-ИЛИ, ИЛИ-НЕ вместе с операциями буфера, запрета, импликации, нулевого значения и идентичности являются единственными логическими (логическими) операциями.Операции дополнения и передачи — это унарные операции, которые работают с одним операндом.

В предыдущем руководстве логическое выражение было минимизировано с помощью таблицы истинности. Но это не стандартный или систематический способ минимизировать логическое выражение. В следующем руководстве вы узнаете о минимизации уровня шлюза, которая включает важные методы сопоставления для упрощения логического выражения. Методы K-Map, VEM и QM являются важными методами минимизации уровня логических элементов, которые должны быть известны для реализации логических выражений на уровне элементов управления и, следовательно, для цифровых схем.После того, как станут известны методы минимизации уровня затвора, можно разработать практические цифровые схемы. Итак, основные логические операции — AND, OR, NOT, XOR, XNOR, NAND, NOR вместе с буфером, запретом, импликацией, нулевыми и идентификационными операциями являются единственными логическими (логическими) операциями. Операции дополнения и передачи — это унарные операции, которые работают с одним операндом.

— объяснение XOR, NOR и логических символов

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

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

Но я уверен, что вы все знаете, что такая сложность не может быть достигнута (практически) простым случайным переворачиванием чисел. За этим действительно есть некоторые причины.Есть правила, которые регулируют, как это должно быть сделано. В этой статье мы обсудим эти правила и увидим, как они управляют «мышлением» компьютеров.

Что такое булева алгебра?

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

В своей книге 1854 года британский математик Джордж Буль предложил систематический набор правил для манипулирования ценностями истины. Эти правила дали математическую основу для работы с логическими предложениями. Эти наборы основ привели к развитию булевой алгебры.

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

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

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

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

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

На изображении ниже показан весь набор вещественных чисел. Набор действительных чисел включает натуральные числа (1, 2, 3, 4 . …), целые числа (все натуральные числа и 0), целые числа (…..- 2, -1, 0, 1, 2, 3 …) и так далее. Обычная алгебра занимается всем этим набором чисел.

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

Например, в информатике мы чаще всего представляем эти значения, используя 0 и 1. 0 используется для False и 1 для True.

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

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

Теперь вопрос в том, что если (Истина и Ложь), (0 и 1) — это просто представления, то что они пытаются представить?

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

Предложение — это просто утверждение вроде «Все кошки милые».

Если вышеприведенное утверждение верно, то мы присваиваем ему значение истинности «Истина» или «1», в противном случае мы присваиваем ему «Ложь» или «0».

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

Логические операции и таблицы истинности

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

Булева алгебра состоит из трех основных операций.

ИЛИ : Также известна как Дизъюнкция . Эта операция выполняется с двумя логическими переменными.Результатом операции ИЛИ будет 0, когда оба операнда равны 0, в противном случае — 1.

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

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

ИЛИ Операция

Переменная-1 Переменная-2 Выход
  0 0 0
  0 1 1
  1 0 1
  1 1 1  

И : Также известна как Соединение .Эта операция выполняется с двумя логическими переменными. Результатом операции И будет 1, когда оба операнда равны 1, в противном случае — 0. Таблица истинности представлена ​​следующим образом.

  И Работа

Переменная-1 Переменная-2 Выход
  0 0 0
  0 1 0
  1 0 0
  1 1 1  

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

  Не работает

Выход переменной-1
  0 1
  1 0  

Булева алгебра и цифровые схемы

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

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

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

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

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

И-НЕ : вентиль И-НЕ образован комбинацией вентилей НЕ и И. Логический элемент И-НЕ дает на выходе 0, если оба входа равны 1, иначе 1.

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

  NAND Gate

Переменная-1 Переменная-2 Выход
  0 0 1
  0 1 1
  1 0 1
  1 1 0  

NOR : ворота NOR формируются комбинацией элементов NOT и OR.Логический элемент ИЛИ-НЕ дает на выходе 1, если оба входа равны 0, в противном случае — 0.

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

  NOR Ворота

Переменная-1 Переменная-2 Выход
  0 0 1
  0 1 0
  1 0 0
  1 1 0  

Большинство цифровых схем построено с использованием логических элементов И-НЕ или ИЛИ-ИЛИ из-за их функциональной полноты, а также из-за того, что их легко изготовить.

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

XOR : вентиль XOR или вентиль Exclusive-OR — это особый тип логического элемента, который дает 0 на выходе, если оба входа равны 0 или 1, в противном случае он дает 1.

  XOR Ворота

Переменная-1 Переменная-2 Выход
  0 0 0
  0 1 1
  1 0 1
  1 1 0  

XNOR : вентиль XNOR или вентиль Exclusive-NOR — это особый тип логического элемента, который дает 1 на выходе, когда оба входа равны 0 или 1, в противном случае он дает 0.

  XNOR ворота

Переменная-1 Переменная-2 Выход
  0 0 1
  0 1 0
  1 0 0
  1 1 1  

Заключение

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

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

Булева алгебра — обзор

Теорема A.7

Всякая булева алгебра изоморфна алгебре множеств .

Булевы алгебры связаны с линейными порядками. Если A является линейным порядком, то мы формируем соответствующую алгебру интервалов I ( A ). Предполагая, что A имеет первый элемент, это алгебра наборов, генерируемых полуоткрытыми интервалами [ a, b ), где b — это либо элемент, либо ∞. Если A не имеет первого элемента, мы складываем интервалы (−∞, b ).

Пусть A = ( A , ∨, ∧, ′, 0, 1) булева алгебра. У нас есть отношение x ≤ y , определенное атомарной формулой x ∧ y = x . Атом — это элемент b , такой что для всех x ≤ b либо x = 0, либо x = b . Например, в алгебре интервалов упорядочения типа ω интервалы вида [ n, n + 1) являются атомами.Булева алгебра — это без атомов , если в ней нет атомов. Мы получаем безатомную булеву алгебру, образуя I (η), где η — порядковый тип рациональных чисел. Элемент b является атомарным , если для всех x ≤ b , таких что x ≠ 0, существует атом y ≤ x . Так, например, в интервальной алгебре упорядочения типа ω + η атомарными элементами являются те, которые не содержат плотных подинтервалов.

Для любой булевой алгебры A мы можем определить последовательность отношений конгруэнтности с соответствующими структурными факторами.Пусть x ∼ ₀ y , если x = y , пусть x ∼ _{α + 1} y , если соответствующие элементы A / _∼α отличаются конечным числом атомов, а для предельного ординала α пусть x ∼ _α y , если x ∼ _β y для некоторого β <α. Мы определяем понятие α-атома по индукции, говоря, что x является 0-атомом, если это атом, и для a > 0, x является α-атомом, если x не может быть выражается как конечное соединение β-атомов при β <α, но для всех y в этой форме могут быть выражены либо x ∧ y , либо x ∧ y ′ .

Булева алгебра A — это суператомная алгебра , если существует a такой, что A / _∼α является тривиальной (т.е. это одноэлементная булева алгебра).

Булева алгебра — статья энциклопедии

Логическая алгебра — это форма логического исчисления с двумя бинарными операциями И (умножение, •) и ИЛИ (сложение, +) и одной унарной операцией НЕ (отрицание, ~), которая меняет значение истинности на противоположное. любого заявления.Булеву алгебру можно использовать для анализа компьютерных микросхем и схем переключения, а также логических предложений.

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

Булева алгебра имеет сильные связи с исчислением высказываний , которое связывает значение истинности вывода со значением истинности предложений, на которых оно основано.Однако это лишь небольшая и необычайно простая ветвь современной математической логики. ^[1]

История

Булева алгебра была введена в 1854 году Джорджем Булем в его книге Исследование законов мысли . ^[2] Эта алгебра была показана в 1938 году Клодом Шенноном как полезная при разработке логических схем. ^[3]

Аксиомы

Операции булевой алгебры, а именно две бинарные операции на множестве A с именами AND (умножение, •) и OR (сложение, +), и одна унарная операция NOT (отрицание, ~ ), дополнены двумя выделенными элементами, а именно 0 (называется ноль ) и 1 (называется один ), которые удовлетворяют следующим аксиомам для любых подмножеств p , q , r набора A :

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

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

Однако это выражение эквивалентно в рамках приведенных выше булевых аксиом. Согласно другим аксиомам, p · p = p . Кроме того, p · r + q · p = p · (q + r). Этот набор находится в пределах p , поэтому интуитивно p + p · (q + r) = p. Используя булевы аксиомы вместо интуиции, p + p · (q + r) = p · (1 + q + r) и согласно свойствам ‘ 1 ‘, (1 + q + r) = 1.Таким образом, элементарный алгебраический результат при интерпретации в терминах булевых аксиом сводится к булеву закону распределения.

Альтернативные обозначения

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

&& &

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

Для получения дополнительной информации см .: Диаграмма Венна .

Диаграммы Венна обеспечивают графическую визуализацию булевых операций. ^[4] Пересечение двух наборов A∩B играет роль операции AND , а объединение двух наборов A∪B представляет функцию OR , как показано серым заштрихованные участки на рисунке. Чтобы представить операцию НЕ , универсальный набор представлен прямоугольником, поэтому ~ A — это набор всего, что не входит в A , что соответствует серой части прямоугольника на третьей панели слева.

Эти диаграммы также обеспечивают визуализацию булевых аксиом. Например, изображение ~ (A∩B) легко увидеть как то же самое, что и (~ A) ∪ (~ B) , как того требует аксиома Де Моргана.

Таблицы истинности

Таблица истинности для логического предложения — это формальный способ определить, является ли вывод действительным или недействительным, где «0» соответствует «недействительному», а «1» — «действительному». В контексте булевой алгебры внимание сосредоточено на булевых функциях , обозначенных f (A, B, C) , где переменные A, B, C и функция f являются допустимыми значениями ‘1’ или ‘ 0 ‘в зависимости от того, действительны или недействительны утверждения, которым они соответствуют.Таблица истинности для f — это просто таблица значений f для всех возможных значений A, B, C . Например, предположим:

Соответствующая таблица истинности находится ниже слева:

Таблица истинности может быть установлена ​​в соответствии с диаграммой Венна, как показано справа. Запись «0» таблицы истинности в столбце A интерпретируется как набор точек , а не в A , тогда как запись «1» используется для ссылки на точки, содержащиеся в A . На схеме обозначение Ā для ~ A используется для сохранения компактности маркировки, а знак «·» для пересечения опущен. Метки обозначают области с границами, окружающими метку, поэтому метка ABC обозначает область, общую для всех трех наборов A , B и C .Цветная область охватывает все точки, соответствующие f = 1 , то есть все точки в области ~ A + B · C , а белое пространство соответствует областям за пределами этой области.

Фактически, A , B , C — это утверждения:

• A: точка p находится в наборе A
• B: точка p находится в наборе B
• C: точка p находится в наборе C

и предложение f :

• f: точка p является общей для наборов B и C или отсутствует в наборе A .

Таблица истинности и диаграмма Венна определяют действительность f для всех вариантов достоверности A , B и C .

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

• A: Набор умных людей
• B: Набор политиков
• C: Множество мошенников

Тогда, если бы Билл был умен и кривым политиком (A · B · C), он попал бы в группу f :

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

Расширение логики

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

Другими словами, A → B ложно тогда и только тогда, когда A истинно, а B ложно.Эта таблица истинности такая же, как ~ A + B . В качестве примера можно взять:

• A: Мяч подброшен.
• B: Собака бежит.

Тогда A → B означает, что собака всегда бежит, когда мяч подброшен, но собака может бегать и в противном случае, или нет.

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

Таким образом, A ↔ B имеет ту же таблицу истинности, что и (A → B) • (B → A) .В качестве примера можно взять:

• A: Переключатель замкнут.
• B: Свет горит.

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

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

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

Список литературы

1. ↑ Эллиотт Мендельсон (1970). «Глава 1: Алгебра логики», Схема булевой алгебры и коммутационных схем Шаума . Макгроу-Хилл. ISBN 0070414602.
2. ↑ Джордж Буль (1854 г.). Исследование законов мышления, на которых основаны математические теории логики и вероятностей . Macmillan and Co . .
3. ↑ Например, см. Джонатан Стерн (2003). «Шеннон, Клод (1916-2001)», Стив Джонс, изд: Энциклопедия новых медиа: важная ссылка на коммуникацию и технологии .Публикации SAGE, стр. 406. ISBN 0761923829.
4. ↑ Для обсуждения см. J. Eldon Whitesitt (1995). «§1–4: диаграммы Венна», Булева алгебра и ее приложения , Републикация Эддисона-Уэсли, 1961 изд. Courier Dover Publications, pp. 5 ff . ISBN 0486684830.

математических единиц за минуту: логическая алгебра

Простая таблица истинности, показывающая все
возможных значений « A И B ».

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

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

В этом новом виде арифметики (называемом булевой алгеброй ) переменные представляют собой логические утверждения (грубо говоря, предложения, которые либо истинны, либо ложны).Поскольку они могут принимать только два значения, мы можем написать 0 для утверждения, которое, как мы знаем, ложно, и 1 для утверждения, которое, как мы знаем, истинно. Затем мы можем переписать OR как своего рода дополнение, используя только 0 и 1:

0 + 0 = 0 (поскольку «ложь ИЛИ ложь» — ложь)
1 + 0 = 0 + 1 = 1 (поскольку «истина ИЛИ ложь» и «ложь ИЛИ истина» оба истинны)
1 + 1 = 1 (поскольку «истина ИЛИ истина» верно).

Мы можем переписать AND как своего рода умножение:

0 x 1 = 1 x 0 = 0 (поскольку «ложь И истина» и «истина И ложь» оба ложны)
0 x 0 = 0 (поскольку «ложь И ложь» — ложь)
1 x 1 = 1 (поскольку «правда И правда» верно).

Поскольку переменные могут иметь только значения 0 и 1, мы можем определить операцию НЕ как дополнение, взяв число, противоположное ее значению:

Если A = 1, то НЕ A = 0
Если A = 0, то НЕ A = 1
A + НЕ A = 1 (поскольку «истина ИЛИ ложь» истинна)
A x НЕ A = 0 (поскольку «истина И ложь» — ложь).

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

A + A x B

не имеет значения, независимо от того, какое значение имеет B или какое логическое утверждение оно представляет. Это потому, что если A истинно (или, что эквивалентно A = 1), то A OR ( A И B ) истинно независимо от того, истинно ли утверждение B . И если A ложно (то есть A = 0), то ( A AND B ) ложно независимо от значения B , и поэтому A OR ( A AND B ) ложно. Итак, булева алгебра предоставляет нам исчезающий акт: выражение A + A x B равно простому маленькому A :

A + A x B = A .

Кроме того, в булевой алгебре существует своего рода обратная двойственность между сложением и умножением:

( A + B ) ‘= A ‘ x B ‘и ( A x B )’ = A ‘+ B ‘.

Эти два равенства известны как Законы Де Моргана в честь британского математика Августа де Моргана (1806–1871). (Вы можете убедиться, что они верны, используя эквивалентные таблицы истинности.)

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

Алгебра переключений или булева алгебра

Булева алгебра или алгебра переключений — это система математической логики для выполнения различных математических операций в двоичной системе.Это всего лишь два элемента 1 и 0, с помощью которых должны выполняться все математические операции. Есть только три базовых двоичных операции: И, ИЛИ и НЕ, с помощью которых должны выполняться как простые, так и сложные двоичные математические операции. В булевой алгебре существует множество правил, по которым выполняются эти математические операции.
В булевой алгебре переменные представлены английскими заглавными буквами, например A, B, C и т. Д., И значение каждой переменной может быть либо 1, либо 0, ничего больше.

Некоторые базовые логические логические операции —
операция И,

операция ИЛИ,

Не операция,

Некоторые основные законы булевой алгебры,

A.0 = 0, где A может быть 0 или 1.
A. 1 = A, где A может быть 0 или 1.
A. A = A, где A может быть 0 или 1.
A. Ā = 0, где A может быть 0 или 1.
A + 0 = A, где A может быть 0 или 1.
A + 1 = 1, где A может быть либо 0, либо 1.
A + Ā = 1
A + A = A
A + B = B + A, где A и B могут быть 0 или 1.
A. В = В. A, где A и B могут быть 0 или 1.
Законы булевой алгебры также верны для более чем двух переменных, например,

Кумулятивные законы для булевой алгебры

Ассоциативные законы для булевой алгебры

Распределительные законы для логической алгебры

Избыточное буквенное правило

Из таблицы истинности,

Из таблицы истинности доказано, что ,

Законы поглощения для булевой алгебры

Доказательство по таблице истинности,

Входные данные			Выходные данные
A	B	AB	A + A. B
0	0	0	0
0	1	0	0
1	0	0	1
1	1	1	1

Столбцы A и A + AB одинаковы.

Доказательство из таблицы истинности,

И A, и A.Столбцы X или A (A + B) совпадают.

Терем Де Моргана,

Доказательство из таблицы истинности,

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

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