- история
- Структура
- Приложения
- Постулаты
- Сумма (+)
- Товар (.)
- Напротив (НЕ)
- теоремы
- Правило нуля и единицы
- Равные силы или идемпотентность
- комплементация
- Инволюция или двойное отрицание
- Коммутативный
- ассоциативный
- дистрибутивный
- Законы абсорбции
- Теорема Моргана
- двойственность
- Карта Карно
- Примеры
- Упростите логическую функцию
- Упростите логическую функцию до самой простой формы
- Ссылки
Булева алгебра или Булева алгебра является алгебраическим обозначением , используемым для лечения двоичных переменных. Он охватывает исследования любой переменной, имеющей только 2 возможных результата: дополняющие и взаимоисключающие. Например, переменные, единственная возможность которых - истина или ложь, правильность или неправильность, включены или выключены, являются основой изучения булевой алгебры.
Булева алгебра составляет основу цифровой электроники, что делает ее широко распространенной сегодня. Он регулируется концепцией логических вентилей, на которые в значительной степени влияют известные операции традиционной алгебры.
Источник: pexels.com
история
Булева алгебра была введена в 1854 году английским математиком Джорджем Булем (1815–1864), который в то время был ученым-самоучкой. Его озабоченность возникла в результате существующего спора между Огастесом Де Морганом и Уильямом Гамильтоном по поводу параметров, определяющих эту логическую систему.
Джордж Буль утверждал, что определение числовых значений 0 и 1 соответствует в области логики интерпретации Ничто и Вселенной соответственно.
Намерение Джорджа Буля состояло в том, чтобы определить через свойства алгебры выражения логики высказываний, необходимые для работы с переменными двоичного типа.
В 1854 г. важнейшие разделы булевой алгебры были опубликованы в книге «Исследование законов мышления, на которых основаны математические теории логики и вероятностей».
Это любопытное название позже будет резюмировано как «Законы мышления» («Законы мысли»). Название стало известным благодаря немедленному вниманию математического сообщества того времени.
В 1948 году Клод Шеннон применил его для разработки бистабильных электрических схем переключения. Это послужило введением в применение булевой алгебры во всей электронно-цифровой схеме.
Структура
Элементарные значения в этом типе алгебры - 0 и 1, что соответствует ЛОЖЬ и ИСТИНА соответственно. Основных операций в булевой алгебре три:
- Операция И или соединение. Обозначается точкой (.). Синоним продукта.
- Операция ИЛИ или дизъюнкция. Обозначается крестиком (+). Синоним суммы.
- НЕ операция или отрицание. Обозначается префиксом НЕ (НЕ А). Он также известен как дополнение.
Если в наборе A2 определены 2 закона внутренней композиции, обозначенные как произведение и сумма (. +), То говорят, что тройка (A. +) является булевой алгеброй тогда и только тогда, когда эта тройка удовлетворяет условию того, что она является решеткой. дистрибутивный.
Для определения распределительной решетки должны выполняться условия распределения между данными операциями:
, дистрибутивна по сумме + a. (b + c) = (a. b) + (a. c)
+ является дистрибутивом по отношению к продукту. а + (б. в) = (а + б). (а + с)
Элементы, составляющие набор A, должны быть двоичными, таким образом, иметь универсальные или пустые значения.
Приложения
Его основным сценарием применения является цифровая ветвь, где он служит для структурирования схем, составляющих задействованные логические операции. Искусство упрощения схем в пользу оптимизации процессов - результат правильного применения и практики булевой алгебры.
От разработки электрических панелей, передачи данных до программирования на разных языках - мы часто можем найти булеву алгебру во всех видах цифровых приложений.
Логические переменные очень часто встречаются в структуре программирования. В зависимости от используемого языка программирования в коде будут структурные операции, использующие эти переменные. Условные выражения и аргументы каждого языка допускают логические переменные для определения процессов.
Постулаты
Существуют теоремы, регулирующие структурные логические законы булевой алгебры. Точно так же существуют постулаты, позволяющие узнать возможные результаты в различных комбинациях двоичных переменных в зависимости от выполняемой операции.
Сумма (+)
Оператор ИЛИ , логическим элементом которого является объединение (U), определяется для двоичных переменных следующим образом:
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 1
Товар (.)
Оператор И , логическим элементом которого является пересечение (∩), определяется для двоичных переменных следующим образом:
0. 0 = 0
0. 1 = 0
один . 0 = 0
один . 1 = 1
Напротив (НЕ)
Оператор НЕ , логическим элементом которого является дополнение (X), определяется для двоичных переменных следующим образом:
НЕ 0 = 1
НЕ 1 = 0
Многие постулаты отличаются от своих аналогов в традиционной алгебре. Это связано с областью значений переменных. Например, добавление элементов юниверса в булеву алгебру (1 + 1) не может дать стандартный результат 2, потому что он не принадлежит элементам двоичного набора.
теоремы
Правило нуля и единицы
Любая простая операция, в которой задействован элемент с двоичными переменными, определяется:
0 + А = А
1 + А = 1
0. А = 0
один . А = А
Равные силы или идемпотентность
Операции между равными переменными определяются как:
А + А = А
КО. А = А
комплементация
Любая операция между переменной и ее дополнением определяется как:
А + НЕ А = 1
КО. НЕ А = 0
Инволюция или двойное отрицание
Любое двойное отрицание будет рассматриваться как естественная переменная.
НЕ (НЕ А) = А
Коммутативный
А + В = В + А; Коммутативность суммы.
КО. B = B. К; Коммутативность продукта.
ассоциативный
А + (В + С) = (А + В) + С = А + В + С; Ассоциативность суммы.
КО. (Б.С) = (А.Б). С = А. B. C; Ассоциативность продукта.
дистрибутивный
А + (Б. С) = (А + В). (А + С); Распределимость суммы по товару.
КО. (В + С) = (А. В) + (А + С); Распределимость продукта по сумме.
Законы абсорбции
Среди множества ссылок есть много законов поглощения, некоторые из самых известных:
КО. (А + В) = А
КО. (НЕ A + B) = A. В
НЕ А (А + В) = НЕ А. В
(А + В). (А + НЕ Б) = А
А + А. В = А
А + НЕ А. В = А + В
НЕ А + А. В = НЕ А + В
КО. В + А. НЕ B = A
Теорема Моргана
Это законы преобразования, которые обрабатывают пары переменных, которые взаимодействуют между определенными операциями булевой алгебры (+.).
НЕ (А. Б) = НЕ А + НЕ Б
НЕ (А + В) = НЕ А. НЕ Б
А + В = НЕ (НЕ А + НЕ Б)
КО. B = НЕ (НЕ А. НЕ Б)
двойственность
Все постулаты и теоремы обладают способностью двойственности. Это означает, что путем замены переменных и операций полученное предложение проверяется. То есть при замене 0 на 1 и И на ИЛИ или наоборот; создается выражение, которое также будет полностью действительным.
Например, если принять постулат
один . 0 = 0
И применяется двойственность
0 + 1 = 1
Получается еще один совершенно справедливый постулат.
Карта Карно
Карта Карно - это диаграмма, используемая в булевой алгебре для упрощения логических функций. Он состоит из двухмерного устройства, аналогичного таблицам истинности логики высказываний. Данные из таблиц истинности могут быть непосредственно зафиксированы на карте Карно.
Карта Карно может вместить процессы до 6 переменных. Для функций с большим количеством переменных рекомендуется использовать программное обеспечение, чтобы упростить процесс.
Предложенный в 1953 году Морисом Карно, он был создан как фиксированный инструмент в области булевой алгебры, поскольку его реализация синхронизирует человеческий потенциал с необходимостью упрощения логических выражений, что является ключевым аспектом гибкости цифровых процессов.
Примеры
Булева алгебра используется для уменьшения логических элементов схемы, где приоритетом является доведение сложности или уровня схемы до минимально возможного выражения. Это связано с вычислительной задержкой, которую предполагает каждый вентиль.
В следующем примере мы увидим упрощение логического выражения до его минимального выражения, используя теоремы и постулаты булевой алгебры.
НЕ (AB + A + B). НЕ (А + НЕ В)
НЕ. НЕ (А + НЕ В); Факторинг A с общим множителем.
НЕ. НЕ (А + НЕ В); По теореме A + 1 = 1.
НЕ (А + В). НЕ (А + НЕ В); по теореме А. 1 = А
(НЕ А. НЕ Б). ;
По теореме Моргана НЕ (A + B) = НЕ A. НЕ Б
(НЕ А. НЕ Б). (НЕ A. B); По теореме о двойном отрицании НЕ (НЕ А) = А
НЕ А. НЕ Б. НЕ А. B; Алгебраическая группировка.
НЕ А. НЕ А. НЕ Б. B; Коммутативность продукта A. B = B. К
НЕ А. НЕ Б. B; По теореме А. А = А
НЕ А. 0; По теореме А. НЕ А = 0
0; По теореме А. 0 = 0
КО. B. С + НЕ А + А. НЕ Б. С
КО. C. (B + НЕ B) + НЕ А; Факторинг (A. C) с общим фактором.
КО. C. (1) + НЕ А; По теореме A + NOT A = 1
КО. С + НЕ А; По правилу теоремы нуля и единицы 1. А = А
НЕ А + С ; По закону Morgan A + NOT A. В = А + В
Для этого решения необходимо расширить закон Моргана, чтобы определить:
НЕ (НЕ А). С + НЕ А = НЕ А + С
Потому что НЕ (НЕ А) = А по инволюции.
Упростите логическую функцию
НЕ А. НЕ Б. НЕ С + НЕ А. НЕ Б. С + НЕ А. НЕ C до его минимального выражения
НЕ А. НЕ Б. (НЕ C + C) + НЕ A. НЕ С; Факторинг (НЕ A. НЕ B) с общим фактором
НЕ А. НЕ Б. (1) + НЕ А. НЕ С; По теореме A + NOT A = 1
(НЕ А. НЕ В) + (НЕ А. НЕ С); По правилу теоремы нуля и единицы 1. А = А
НЕ А (НЕ В + НЕ С); Факторинг НЕ А с общим множителем
НЕ А. НЕ (Б. С); По законам Моргана НЕ (A. B) = НЕ A + НЕ B
НЕ По законам Моргана НЕ (A. B) = НЕ A + НЕ B
Любой из 4 вариантов, выделенных жирным шрифтом, представляет возможное решение для снижения уровня цепи.
Упростите логическую функцию до самой простой формы
(A. НЕ B. C + A. НЕ B. B. D + NOT A. НЕ B). С
(A. НЕ B. C + A. 0. D + NOT A. НЕ B). C; По теореме А. НЕ А = 0
(A. НЕ B. C + 0 + НЕ A. НЕ B). C; По теореме А. 0 = 0
(A. НЕ B. C + НЕ A. НЕ B). C; По теореме A + 0 = A
КО. НЕ Б. C. С + НЕ А. НЕ Б. C; По распределенности произведения по сумме
КО. НЕ Б. С + НЕ А. НЕ Б. C; По теореме А. А = А
НЕ Б. С (А + НЕ А) ; Факторинг (НЕ B. C) с общим фактором
НЕ Б. С (1); По теореме A + NOT A = 1
НЕ Б. C; По правилу теоремы нуля и единицы 1. А = А
Ссылки
- Булева алгебра и ее приложения Дж. Элдон Уайтситт. Continental Publishing Company, 1980.
- Математика и инженерия в компьютерных науках. Кристофер Дж. Ван Вик. Институт компьютерных наук и технологий. Национальное бюро стандартов. Вашингтон, округ Колумбия 20234
- Математика для компьютерных наук. Эрик Леман. Google Inc.
Ф. Томсон Лейтон Отделение математики и Лаборатория компьютерных наук и искусственного интеллекта Массачусетского технологического института; Akamai Technologies. - Элементы абстрактного анализа. Мичел О'Сиркоид, доктор философии. Кафедра математики. Университетский колледж Дублина, Бельдфилд, Дублинд.
- Введение в логику и методологию дедуктивных наук. Альфред Тарски, Нью-Йорк, Оксфорд. Издательство Оксфордского университета.