Булева алгебра является алгеброй логики. Он имеет дело с переменными, которые могут иметь два дискретных значения: 0 (False) и 1 (True); и операции, которые имеют логическое значение. Самый ранний метод манипулирования символической логикой был изобретен Джорджем Булем и впоследствии стал известен как Булева алгебра.
В настоящее время булева алгебра стала незаменимым инструментом в области компьютерных наук благодаря ее широкому применению в теории коммутации, создании базовых электронных схем и проектировании цифровых компьютеров.
Булевы функции
Булева функция — это особый вид математической функции f:Xn rightarrowX степени n, где X= lbrace0,1 rbrace — булева область, а n — неотрицательное целое число , Он описывает способ получения логического вывода из логических входных данных.
Пример — Пусть, F(A,B)=A′B′. Это функция степени 2 из набора упорядоченных пар булевых переменных в набор lbrace0,1 rbrace, где F(0,0)=1,F(0,1)=0,F(1,0)=0 и F(1,1)=0
Логические выражения
Булево выражение всегда создает логическое значение. Логическое выражение состоит из комбинации логических констант (True или False), логических переменных и логических связок. Каждое логическое выражение представляет логическую функцию.
Пример — AB′C является логическим выражением.
Булевы тождества
Закон о двойном дополнении
sim( simA)=A
Закон о дополнениях
A+ simA=1 (ИЛИ Форма)
$ A. \ sim A = 0 $ (форма AND)
Идемпотентный закон
A+A=A (ИЛИ Форма)
$ A. A = A $ (И Форма)
Закон об идентичности
A+0=A (ИЛИ Форма)
$ A. 1 = A $ (форма И)
Закон о доминировании
A+1=1 (ИЛИ Форма)
$ A. 0 = 0 $ (форма И)
Коммутативное право
A+B=B+A (ИЛИ Форма)
$ A. B = B. A $ (И Форма)
Ассоциативное право
A+(B+C)=(A+B)+C (ИЛИ Форма)
$ A. (B. C) = (A. B). C $ (И Форма)
Закон поглощения
$ A. (A + B) = A $
A+(A.B)=A
Закон об упрощении
$ A. (\ sim A + B) = A. B $
A+( simA.B)=A+B
Распределительный закон
$ A + (B. C) = (A + B). (A + C) $
$ A. (B + C) = (A. B) + (A. C) $
Закон Моргана
sim(A.B)= simA+ simB
$ \ sim (A + B) = \ sim A. \ sim B $
Канонические Формы
Для булева выражения есть два вида канонических форм:
- Форма суммы minterms (SOM)
- Произведение формы maxterms (POM)
Форма Сумма Минтерм (SOM) или Сумма Продуктов (SOP)
Минтерма — это произведение всех переменных, взятых либо в их прямой, либо в дополненной форме. Любая булева функция может быть выражена как сумма ее 1-минут, а обратная функция может быть выражена как сумма ее 0-минут. Следовательно,
F (список переменных) = ∑ (список 1-минутных индексов)
а также
F ‘(список переменных) = ∑ (список 0-минутных индексов)
| В | С | Срок | Minterm | |
|---|---|---|---|---|
| 0 | 0 | 0 | x’y’z» | м 0 |
| 0 | 0 | 1 | x’y’z | м 1 |
| 0 | 1 | 0 | x’yz» | м 2 |
| 0 | 1 | 1 | x’yz | м 3 |
| 1 | 0 | 0 | xy’z» | м 4 |
| 1 | 0 | 1 | xy’z | м 5 |
| 1 | 1 | 0 | хуг» | м 6 |
| 1 | 1 | 1 | хуг | м 7 |
пример
Пусть F(x,y,z)=x′y′z′+xy′z+xyz′+xyz
Или F(x,y,z)=m0+m5+m6+m7
Следовательно,
F(x,y,z)= sum(0,5,6,7)
Теперь мы найдем дополнение F(x,y,z)
F′(x,y,z)=x′yz+x′y′z+x′yz′+xy′z′
Или F′(x,y,z)=m3+m1+m2+m4
Следовательно,
F′(x,y,z)= sum(3,1,2,4)= sum(1,2,3,4)
Форма «Продукт Maxterms» (POM) или «Сумма продукта» (POS)
Максимум — это сложение всех переменных, взятых либо в их прямой, либо в дополненной форме. Любая булева функция может быть выражена как произведение ее 0-maxterms, а обратная функция может быть выражена как произведение ее 1-maxterms. Следовательно,
F (список переменных) = pi (список индексов 0-maxterm).
а также
F ‘(список переменных) = pi (список индексов 1-maxterm).
| В | С | Срок | Maxterm | |
|---|---|---|---|---|
| 0 | 0 | 0 | х + у + г | М 0 |
| 0 | 0 | 1 | x + y + z ‘ | М 1 |
| 0 | 1 | 0 | x + y ‘+ z | М 2 |
| 0 | 1 | 1 | x + y ‘+ z’ | М 3 |
| 1 | 0 | 0 | x ‘+ y + z | М 4 |
| 1 | 0 | 1 | x ‘+ y + z’ | М 5 |
| 1 | 1 | 0 | x ‘+ y’ + z | М 6 |
| 1 | 1 | 1 | x ‘+ y’ + z ‘ | М 7 |
пример
Пусть $ F (x, y, z) = (x + y + z). (x + y + z ‘). (х + у ‘+ г). (х ‘+ у + г) $
Или $ F (x, y, z) = M_0. М_1. М_2. M_4 $
Следовательно,
F(x,y,z)= pi(0,1,2,4)
$ F » (x, y, z) = (x + y ‘+ z’). (x ‘+ y + z’). (x ‘+ y’ + z). (Х ‘+ у’ + г ‘) $
Или $ F (x, y, z) = M_3. М_5. М_6. M_7 $
Следовательно,
F′(x,y,z)= pi(3,5,6,7)
Логические ворота
Булевы функции реализуются с помощью логических элементов. Ниже приведены логические элементы —
НЕ Ворота
Гейт НЕ инвертирует однобитовый вход в один бит вывода.
| ~ A | |
|---|---|
| 0 | 1 |
| 1 | 0 |
И Ворота
Логический элемент И представляет собой логический вентиль, который дает высокий выходной сигнал, только если все его входные данные являются высокими, в противном случае он дает низкий выходной сигнал. Точка (.) Используется для отображения операции AND.
| В | AB | |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
ИЛИ Ворота
ИЛИ вентиль — это логический вентиль, который дает высокий выходной сигнал, если хотя бы один из входов имеет высокий уровень. Плюс (+) используется для отображения операции ИЛИ.
| В | А + В | |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
NAND Gate
Вентиль NAND — это логический вентиль, который выдает низкий выходной сигнал, только если все его входы являются высокими, в противном случае он дает высокий выходной сигнал.
| В | ~ (АВ) | |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
NOR Gate
Вентиль NOR — это логический вентиль, который дает высокий выход, если оба входа низки, в противном случае он дает низкий выход.
| В | ~ (А + В) | |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
XOR (Эксклюзив ИЛИ) Ворота
Вентиль XOR — это логический вентиль, который дает высокий выход, если входы различны, в противном случае он дает низкий выход.
| В | A⊕B | |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Ворота X-NOR (Эксклюзив NOR)
Вентиль EX-NOR — это логический вентиль, который дает высокий выходной сигнал, если входы одинаковы, в противном случае он дает низкий выходной сигнал.