Основу ЭВМ и других цифровых устройств составляют элементарные логические схемы, которые работают в строгом соответствии с законами и правилами алгебры логики. Знание и понимание этих законов и правил помогает лучше разобраться с принципами работы ЭВМ.
Алгебра логики (булева алгебра – по фамилии ученого Д. Буля1) является частью раздела математики под названием математическая логика, посвященного изучению математических доказательств и вопросов оснований математики. Построенная Д. Булем алгебра служила для описания логических действий над высказываниями. В честь ученого переменные логического типа в языках программирования назвали булевскими переменными (тип Boolean в языках Basic и Pascal, bool в C, C++).
Понятие высказывания
Основными объектами алгебры логики являются высказывания.
Высказывание – это утверждение, которое либо истинно, либо ложно и не может быть тем и другим одновременно. Приведем примеры высказываний:
Число 14 делится на 2 и 7
Париж – столица Испании.
Хабаровск стоит на Амуре.
3 > 1
Высказывания «Число 14 делится на 2 и 7» и «Хабаровск стоит на Амуре» истинны, а высказывания «Париж – столица Испании» и «3 > 1» ложны.
В алгебре логики все высказывания рассматриваются только с точки зрения их логического значения, а от содержания отвлекаются. Истинное значение высказывания обозначают цифрой 1, а ложное – цифрой 0 Таким образом, высказывания фактически являются двоичными объектами.
Высказывание, представляющее собой одно утверждение, принято назы вать простым или элементарным. Будем обозначать простые высказывания буквами латинского алфавита. Запись X = 1 означает, что высказывание X истинно, а запись X = 0, что оно ложно.
Высказывания, которые получаются из простых с помощью логических операций, принято называть сложными или составными. Из вышеприведенных высказываний второе, третье и четвертое являются простыми, а первое высказывание, образованное из простых высказываний «Число 14 делится на 2» и «Число 14 делится на 7», является сложным.
Простые высказывания соответствуют логическим переменным, а сложные – логическим функциям или выражениям. Любая логическая функция может быть задана с помощью таблицы истинности, в левой части которой записываются возможные наборы переменных (аргументов), а в правой – соответствующие им значения функции. Это возможно по той причине, что все сочетания логических аргументов легко перечислить.
Логические операции
Основными операциями алгебры логики являются отрицание, конъюнкция, дизъюнкция, импликация и эквиваленция. В вычислительной технике также часто используется операция исключающее ИЛИ.
Отрицание
Операция отрицания является унарной, т.к. имеет один аргумент. Иначе ее называют инверсией, дополнением, НЕ и обозначают X или ¬X, NOT X. Отрицанием некоторого высказывания называется такое высказывание, которое истинно, когда ложно, и ложно, когда истинно. Определение отрицания может быть записано с помощью таблицы истинности:
Конъюнкция
Операцию конъюнкции еще называют логическим умножением, логическим И.
Для обозначения данной операции используют символы , &, точку, которую можно опускать, .
Конъюнкцией двух высказываний и называется такое высказывание, которое истинно тогда и только тогда, когда истинны оба высказывания X и Y.
Определение конъюнкции может быть записано в виде таблицы истинности:
Дизъюнкция
Операцию дизъюнкции иначе называют логическим сложением, логическим ИЛИ. Для обозначения логического сложения используют символы , +, .
Дизъюнкцией двух высказываний и называется такое высказывание, которое истинно тогда и только тогда, когда истинно хотя бы одно из этих высказываний.
Определение дизъюнкции может быть записано в виде таблицы истинности:
Импликация
Операцию импликации иначе называют логическим следованием.
Импликацией двух высказываний и называется высказывание, которое ложно тогда и только тогда, когда истинно и ложно.
Определение импликации может быть записано в виде таблицы истинности:
Эквиваленция
Операцию эквиваленции иначе называют логическим тождеством, эквивалентностью и для обозначения используют символы =, ~.
Эквиваленцией двух высказываний и называется такое высказывание, которое истинно тогда и только тогда, когда оба эти высказывания истинны или оба ложны.
Определение эквиваленции может быть записано в виде таблицы истинности:
Операция исключающее ИЛИ
Операция исключающее ИЛИ (неравнозначность, сложение по модулю два) отличается от логического ИЛИ только при и . Таким образом, неравнозначностью двух высказываний и называют такое высказывание, которое истинно тогда и только тогда, когда одно их этих высказываний истинно, а другое ложно.
Определение данной операции может быть записано в виде таблицы истинности:
При вычислении значения логического выражения принято следующее старшинство (приоритет) логических операций:
1. инверсия;
2. конъюнкция;
3. дизъюнкция;
4. импликация;
5. эквиваленция.
Для изменения указанного порядка используют скобки.