Булевы выражения и функции

Булева алгебра является алгеброй логики. Он имеет дело с переменными, которые могут иметь два дискретных значения: 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