Учебники

Цифровые схемы – булева алгебра

Булева алгебра – это алгебра, которая имеет дело с двоичными числами и двоичными переменными. Следовательно, он также называется бинарной алгеброй или логической алгеброй. Математик по имени Джордж Буль разработал эту алгебру в 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’ .