Операции булевой алгебры
В булевой алгебре над переменными, принимающими значения 0 или 1, производятся следующие основные операции:
1. Логическое сложение (дизъюнкция).
2. Логическое умножение (конъюнкция).
3. Логическое отрицание (инверсия).
1. Логическое сложение (дизъюнкция, или)
Реализуется логическим элементом дизъюнктором
1
F=х1+х2
х2
Таблица истинности – выражает зависимость результата, от совокупности сигналов на входе.
Входы Выход
х1 х2 F
0 0 0
0 1 1
1 0 1
1 1 1
2. Логическое умножение (конъюнкция, и)
Р
еализуется
логическим элементом коньюнктором.
х
1
F=х1*х2 Входы Выход
х2 х1 х2
F
0 0 0
0 1 0
1 0 0
1 1 1
3. Логическое отрицание (инверсия, не)
Реализуется логическим элементом инвертором
1
_
х
F = х
Вход Выход
х F
0 1
1 0
Наряду с основными применяются и другие функции двух аргументов, выраженные через три основных: “и”, “или”, “не”.
4. Импликация (a → b) F= ā + b (не a или b)
F=1, если a=0, b=0, 1; a=1, b=1.
1
a
ā
F = ā + b
b
Импликация "если ..., то" - импликацией с посылкой «А» и следствием «В» называется такое высказывание «А В», которое ложно тогда и только тогда, когда «А» - истинно, а «В» - ложно.
_
5. Функция запрета (a b) F= a * b (a и не b).
F=1, если a=1 и b=0
___
6. Функция Пирса (a ↓ b) F= a + b (a или b не)
F=1, если a=0, b=0.
Логический элемент “или-не”
7. Функция Шеффера (a │ b) F= a * b (a и b не).
F=1, если a=0, b=0.
Логический элемент “и-не”
Функция логической равнозначности ( a ≡ b, иногда обозначается
_
a ~ b) F= ab + ab (a и b не или a и b). ; a ~ b = (a → b) /\ (b → a), если аргументы принимают одинаковые значения.
Эквивалентность "тогда и только тогда, когда" - эквивалентностью высказываний «А» и «В», называется такое новое высказывание «А В», которое истинно только тогда, когда «А» и «В» имеют одинаковые значения, т.е. оба истинны или оба ложны.
9. Функция логической неравнозначности (a b) – сложение по модулю 2 F= ā b +a b (не a и b или a и не b)
В практической деятельности часто приходится производить минимизацию булевых функций (БФ). Это преобразование алгебраического выражения БФ с целью получения самой простой формы, на основе правил и теорем булевой алгебры.
При анализе функций, представленных в стандартной нормальной форме (СдНФ) отыскиваются все соседние слагаемые (то есть различающиеся не более чем в одном элементе) и осуществляется их склеивание:
_
X • Y + X • Y = Y Закон склеивания
_
(X+Y) • (X+Y) = Y
_ _
ABC + ABC = BC(A+A) = BC
Когда все возможности склеивания исчерпаны, избыточные слагаемые исключаются применением закона поглощения:
X
+ X • Y = X
X • (1 + Y
) = X • X = X
Закон