Булевы выражения и функции
Булева алгебра является алгеброй логики. Он имеет дело с переменными, которые могут иметь два дискретных значения: 0 (False) и 1 (True); и операции, которые имеют логическое значение. Самый ранний метод манипулирования символической логикой был изобретен Джорджем Булем и впоследствии стал известен как Булева алгебра.
В настоящее время булева алгебра стала незаменимым инструментом в области компьютерных наук благодаря ее широкому применению в теории коммутации, создании базовых электронных схем и проектировании цифровых компьютеров.
Булевы функции
Булева функция - это особый вид математической функции $ f: X ^ n \ rightarrow X $ степени n, где $ X = \ lbrace {0, 1} \ rbrace $ - булева область, а n - неотрицательное целое число , Он описывает способ получения логического вывода из логических входных данных.
Пример - Пусть, $ F (A, B) = A'B '$. Это функция степени 2 из множества упорядоченных пар булевых переменных в набор $ \ lbrace {0, 1} \ rbrace $, где $ F (0, 0) = 1, F (0, 1) = 0, F (1, 0) = 0 $ и $ F (1, 1) = 0 $
Логические выражения
Булево выражение всегда создает логическое значение. Булево выражение состоит из комбинации логических констант (True или False), логических переменных и логических связок. Каждое логическое выражение представляет логическую функцию.
Пример - $ AB'C $ является логическим выражением.
Булевы тождества
Закон о двойном дополнении
$ \ sim (\ sim A) = A $
Закон дополнения
$ A + \ sim A = 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 + (\ sim A. B) = A + B $
Распределительный закон
$ A + (B. C) = (A + B). (A + C) $
$ A. (B + C) = (A. B) + (A. C) $
Закон Моргана
$ \ sim (A. B) = \ sim A + \ sim B $
$ \ 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 '+ x y' z + xy z '+ xyz $
Или $ F (x, y, z) = m_0 + m_5 + m_6 + m_7 $
Следовательно,
$ F (x, y, z) = \ sum (0, 5, 6, 7) $
Теперь мы найдем дополнение $ F (x, y, z) $
$ F '(x, y, z) = x' yz + x 'y' z + x 'y z' + x y 'z' $
Или $ F '(x, y, z) = m_3 + m_1 + m_2 + m_4 $
Следовательно,
$ F '(x, y, z) = \ sum (3, 1, 2, 4) = \ sum (1, 2, 3, 4) $
Форма «Продукт Maxterms» (POM) или «Сумма продукта» (POS)
Максимум - это сложение всех переменных, взятых либо в их прямой, либо в дополненной форме. Любая булева функция может быть выражена как произведение ее 0-maxterms, а обратная функция может быть выражена как произведение ее 1-maxterms. Следовательно,
F (список переменных) = $ \ pi $ (список 0-максимальных индексов).
и
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 является логическим вентилем, который дает высокий выходной сигнал, если входы одинаковы, в противном случае он дает низкий выходной сигнал.
| В | A X-NOR B | |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |