Логические выражения и функции
Булева алгебра - это алгебра логики. Он имеет дело с переменными, которые могут иметь два дискретных значения: 0 (Ложь) и 1 (Истина); и операции, имеющие логическое значение. Самый ранний метод манипулирования символической логикой был изобретен Джорджем Булем и впоследствии стал известен как булева алгебра.
Булева алгебра теперь стала незаменимым инструментом в информатике из-за ее широкого применения в теории переключений, построении основных электронных схем и проектировании цифровых компьютеров.
Булевы функции
A Boolean function- это особый вид математической функции $ f: X ^ n \ rightarrow X $ степени n, где $ X = \ lbrace {0, 1} \ rbrace $ - логическая область, а n - неотрицательное целое число. Он описывает способ получения логического вывода из логических входов.
Example- Пусть, $ 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 $
Логические выражения
A Boolean expressionвсегда выдает логическое значение. Логическое выражение состоит из комбинации логических констант (True или False), логических переменных и логических связок. Каждое логическое выражение представляет собой логическую функцию.
Example - $ AB'C $ - логическое выражение.
Булевы идентичности
Закон о двойном дополнении
$ \ sim (\ sim A) = A $
Закон дополнения
$ A + \ sim A = 1 $ (форма ИЛИ)
$ A. \ sim A = 0 $ (И форма)
Идемпотентный закон
$ A + A = A $ (форма ИЛИ)
$ A. A = A $ (форма И)
Закон о личности
$ A + 0 = A $ (форма ИЛИ)
$ A. 1 = A $ (форма И)
Закон о господстве
$ A + 1 = 1 $ (форма ИЛИ)
$ A. 0 = 0 $ (форма И)
Коммутативный закон
$ A + B = B + A $ (форма ИЛИ)
$ A. В = В. A $ (форма И)
Ассоциативный закон
$ A + (B + C) = (A + B) + C $ (форма ИЛИ)
$ A. (В. С) = (А. В). C $ (форма И)
Закон поглощения
$ A. (А + В) = А $
$ A + (A. B) = A $
Закон упрощения
$ A. (\ сим А + В) = А. Млрд долларов
$ A + (\ sim A. B) = A + B $
Распределительное право
$ А + (В. С) = (А + В). (A + C) $
$ A. (B + C) = (A. B) + (A. C) $
Закон Де-Моргана
$ \ sim (A. B) = \ sim A + \ sim B $
$ \ sim (А + В) = \ сим А. \ sim B $
Канонические формы
Для логического выражения существует два вида канонических форм:
- Форма суммы минтермов (SOM)
- Продукт формы maxterms (POM)
Форма суммы Minterms (SOM) или Sum of Products (SOP)
Минтерм - это произведение всех переменных, взятых в их прямой или дополненной форме. Любая логическая функция может быть выражена как сумма ее 1-минутных членов, а функция, обратная функции, может быть выражена как сумма ее 0-минутных членов. Следовательно,
F (список переменных) = ∑ (список 1-минутных индексов)
и
F '(список переменных) = ∑ (список 0-минутных индексов)
| А | B | C | Срок | Минтерм |
|---|---|---|---|---|
| 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 | xyz ' | м 6 |
| 1 | 1 | 1 | xyz | м 7 |
Example
Пусть $ F (x, y, z) = x 'y' z '+ xy' z + xyz '+ xyz $
Или $ F (x, y, z) = m_0 + m_5 + m_6 + m_7 $
Следовательно,
$ F (х, у, z) = \ сумма (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) = m_3 + m_1 + m_2 + m_4 $
Следовательно,
$ F '(х, у, z) = \ сумма (3, 1, 2, 4) = \ сумма (1, 2, 3, 4) $
Форма "Произведение макс. Условий" (POM) или "произведение сумм" (POS)
Maxterm - это сложение всех переменных, взятых в их прямой или дополненной форме. Любая логическая функция может быть выражена как произведение ее 0-maxterms, а обратная функция функции может быть выражена как произведение ее 1-maxterms. Следовательно,
F (список переменных) = $ \ pi $ (список индексов 0-maxterm).
и
F '(список переменных) = $ \ pi $ (список 1-maxterm индексов).
| А | B | C | Срок | Maxterm |
|---|---|---|---|---|
| 0 | 0 | 0 | х + у + г | M 0 |
| 0 | 0 | 1 | x + y + z’ | M1 |
| 0 | 1 | 0 | x + y’ + z | M2 |
| 0 | 1 | 1 | x + y’ + z’ | M3 |
| 1 | 0 | 0 | x’ + y + z | M4 |
| 1 | 0 | 1 | x’ + y + z’ | M5 |
| 1 | 1 | 0 | x’ + y’ + z | M6 |
| 1 | 1 | 1 | x’ + y’ + z’ | M7 |
Example
Let $F(x, y, z) = (x + y + z) . (x+y+z') . (x+y'+z) . (x'+y+z)$
Or, $F(x, y, z) = M_0 . M_1 . M_2 . M_4$
Hence,
$F (x, y, z) = \pi (0, 1, 2, 4)$
$F''(x, y, z) = (x+y'+z') . (x'+y+z') . (x'+y'+z) . (x'+y'+z')$
Or, $F(x, y, z) = M_3 . M_5 . M_6 . M_7$
Hence,
$F '(x, y, z) = \pi (3, 5, 6, 7)$
Logic Gates
Boolean functions are implemented by using logic gates. The following are the logic gates −
NOT Gate
A NOT gate inverts a single bit input to a single bit of output.
| A | ~A |
|---|---|
| 0 | 1 |
| 1 | 0 |
AND Gate
An AND gate is a logic gate that gives a high output only if all its inputs are high, otherwise it gives low output. A dot (.) is used to show the AND operation.
| A | B | A.B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
OR Gate
An OR gate is a logic gate that gives high output if at least one of the inputs is high. A plus (+) is used to show the OR operation.
| A | B | A+B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
NAND Gate
A NAND gate is a logic gate that gives a low output only if all its inputs are high, otherwise it gives high output.
| A | B | ~(A.B) |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
NOR Gate
An NOR gate is a logic gate that gives high output if both the inputs are low, otherwise it gives low output.
| A | B | ~(A+B) |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
XOR (Exclusive OR) Gate
An XOR gate is a logic gate that gives high output if the inputs are different, otherwise it gives low output.
| A | B | A⊕B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
X-NOR (Exclusive NOR) Gate
An EX-NOR gate is a logic gate that gives high output if the inputs are same, otherwise it gives low output.
| A | B | A X-NOR B |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |