Булева алгебра — это алгебра, которая имеет дело с двоичными числами и двоичными переменными. Следовательно, он также называется бинарной алгеброй или логической алгеброй. Математик по имени Джордж Буль разработал эту алгебру в 1854 году. Переменные, используемые в этой алгебре, также называются булевыми переменными.
Диапазон напряжений, соответствующий логике «Высокий», обозначен «1», а диапазон напряжений, соответствующий логике «Низкий», представлен «0».
Постулаты и основные законы булевой алгебры
В этом разделе давайте поговорим о булевых постулатах и основных законах, которые используются в булевой алгебре. Они полезны при минимизации булевых функций.
Булевы Постулаты
Рассмотрим двоичные числа 0 и 1, булеву переменную (x) и ее дополнение (x ‘). Булева переменная или ее дополнение называется литералом . Четыре возможных логических операции ИЛИ среди этих литералов и двоичных чисел показаны ниже.
х + 0 = х
х + 1 = 1
х + х = х
х + х ‘= 1
Точно так же четыре возможные логические операции И среди этих литералов и двоичных чисел показаны ниже.
х.1 = х
х.0 = 0
хх = х
x.x ‘= 0
Это простые булевы постулаты. Мы можем легко проверить эти постулаты, заменив логическую переменную на «0» или «1».
Примечание . Дополнение к любой булевой переменной равно самой переменной. т.е. (x ‘)’ = x.
Основные законы булевой алгебры
Ниже приведены три основных закона булевой алгебры.
- Коммутативное право
- Ассоциативный закон
- Распределительное право
Коммутативное право
Если какая-либо логическая операция двух булевых переменных дает один и тот же результат независимо от порядка этих двух переменных, то эта логическая операция называется коммутативной . Логическое ИЛИ и логические И операции двух булевых переменных x & y показаны ниже
х + у = у + х
xy = yx
Символ «+» указывает на логическую операцию ИЛИ. Точно так же символ «.» указывает логическую операцию И, и это необязательно для представления. Коммутативное право подчиняется логическому ИЛИ, логическому И операциям.
Ассоциативное право
Если сначала выполняется логическая операция любых двух логических переменных, а затем выполняется та же самая операция с оставшейся переменной, которая дает тот же результат, то эта логическая операция называется ассоциативной . Логические операции ИЛИ, логические И трех булевых переменных x, y & z показаны ниже.
x + (y + z) = (x + y) + z
x. (yz) = (xy) .z
Ассоциативный закон подчиняется логическому ИЛИ и логическому И операциям.
Распределительный закон
Если какая-либо логическая операция может быть распространена на все члены, присутствующие в булевой функции, то эта логическая операция называется распределительной . Распределение логических ИЛИ и логических И операций трех булевых переменных x, y & z показано ниже.
х. (у + г) = ху + хз
x + (yz) = (x + y). (x + z)
Распределительный закон подчиняется логическому ИЛИ и логическому И операциям.
Это основные законы булевой алгебры. Мы можем легко проверить эти законы, заменив логические переменные на «0» или «1».
Теоремы булевой алгебры
Следующие две теоремы используются в булевой алгебре.
- Теорема двойственности
- Теорема Деморгана
Теорема двойственности
Эта теорема утверждает, что двойственность булевой функции получается путем замены логического оператора AND на логический оператор OR и нулей на единицу. Для каждой булевой функции будет соответствующая двойная функция.
Давайте сделаем булевы уравнения (отношения), которые мы обсуждали в разделе булевых постулатов и основных законов, на две группы. В следующей таблице показаны эти две группы.
| Группа 1 | Group2 |
|---|---|
| х + 0 = х | х.1 = х |
| х + 1 = 1 | х.0 = 0 |
| х + х = х | хх = х |
| х + х ‘= 1 | x.x ‘= 0 |
| х + у = у + х | xy = yx |
| x + (y + z) = (x + y) + z | x. (yz) = (xy) .z |
| х. (у + г) = ху + хз | x + (yz) = (x + y). (x + z) |
В каждой строке есть два булевых уравнения, и они двойственны друг другу. Мы можем проверить все эти булевы уравнения группы 1 и группы 2, используя теорему двойственности.
Теорема Деморгана
Эта теорема полезна при поиске дополнения к булевой функции . В нем говорится, что дополнение логического ИЛИ по крайней мере двух логических переменных равно логическому И каждой дополненной переменной.
Теорема Деморгана с 2 булевыми переменными x и y может быть представлена в виде
(x + y) ‘= x’.y’
Двойственная из вышеупомянутых булевых функций
(xy) ‘= x’ + y ‘
Следовательно, дополнение логического И двух логических переменных равно логическому ИЛИ каждой дополненной переменной. Точно так же мы можем применить теорему Деморгана для более чем 2 булевых переменных.
Упрощение булевых функций
До сих пор мы обсуждали постулаты, основные законы и теоремы булевой алгебры. Теперь давайте упростим некоторые булевы функции.
Пример 1
Упростим булеву функцию: f = p’qr + pq’r + pqr ‘+ pqr
Мы можем упростить эту функцию двумя способами.
Способ 1
Для данной булевой функции f = p’qr + pq’r + pqr ‘+ pqr.
Шаг 1 — В первом и втором членах r является общим, а в третьем и четвертом членах pq является общим. Итак, примите общие термины, используя Распределительный закон .
⇒ f = (p’q + pq ‘) r + pq (r’ + r)
Шаг 2 — Термины, представленные в первых скобках, могут быть упрощены до операции Ex-OR. Термины, присутствующие во второй скобке, могут быть упрощены до «1» с использованием булева постулата
⇒ f = (p ⊕q) r + pq (1)
Шаг 3 — Первый термин не может быть упрощен в дальнейшем. Но второй член можно упростить до pq, используя булев постулат .
⇒ f = (p ⊕q) r + pq
Следовательно, упрощенная булева функция имеет вид f = (p⊕q) r + pq
Способ 2
Для данной булевой функции f = p’qr + pq’r + pqr ‘+ pqr.
Шаг 1 — Используйте булев постулат , х + х = х. Это означает, что операция логического ИЛИ с любой логической переменной n раз будет равна той же самой переменной. Итак, мы можем написать последний член pqr еще два раза.
⇒ f = p’qr + pq’r + pqr ‘+ pqr + pqr + pqr
Шаг 2 — Используйте Распределительный закон для 1- го и 4- го терминов, 2- го и 5- го терминов, 3- го и 6- го терминов.
⇒ f = qr (p ‘+ p) + pr (q’ + q) + pq (r ‘+ r)
Шаг 3 — Используйте булев постулат , x + x ‘= 1 для упрощения терминов, присутствующих в каждой скобке.
⇒ f = qr (1) + pr (1) + pq (1)
Шаг 4 — Используйте булев постулат , x.1 = x для упрощения трех указанных выше терминов.
⇒ f = qr + pr + pq
⇒ f = pq + qr + pr
Следовательно, упрощенная булева функция имеет вид f = pq + qr + pr .
Итак, мы получили две разные булевы функции после упрощения данной булевой функции в каждом методе. Функционально эти две булевы функции одинаковы. Таким образом, исходя из требования, мы можем выбрать одну из этих двух булевых функций.
Пример 2
Найдем дополнение к булевой функции f = p’q + pq ‘.
Дополнением к булевой функции является f ‘= (p’q + pq’) ‘.
Шаг 1 — Используйте теорему Деморгана, (x + y) ‘= x’.y’.
⇒ f ‘= (p’q)’. (Pq ‘)’
Шаг 2 — Используйте теорему Деморгана, (xy) ‘= x’ + y ‘
⇒ f ‘= {(p’) ‘+ q’}. {P ‘+ (q’) ‘}
Шаг 3 — Используйте булев постулат, (x ‘)’ = x.
⇒ f ‘= {p + q’}. {P ‘+ q}
⇒ f ‘= pp’ + pq + p’q ‘+ qq’
Шаг 4 — Используйте булев постулат, хх ‘= 0.
⇒ f = 0 + pq + p’q ‘+ 0
⇒ f = pq + p’q ‘
Следовательно, дополнение к булевой функции p’q + pq ‘равно pq + p’q’ .