2014-02-24
1236Алгебра высказываний была разработана для того, чтобы можно было определять истинность или ложность составных высказываний, не вникая в их содержание.
В булевой алгебре высказывания обычно обозначаются латинскими буквами. Таким образом, мы уходим от конкретного содержания высказываний, нас интересует только их истинность или ложность. Например, можно обозначить буквой A высказывание «Сейчас идет дождь», а буквой B — высказывание «Форточка открыта». Из них строятся сложные высказывания:
не A:«Сейчас нет дождя».
не B: «Форточка закрыта».
A и B: «Сейчас идет дождь, и открыта форточка».
A или B: «Сейчас идет дождь, или открыта форточка».
если A, то B: «Если сейчас идет дождь, то форточка открыта».
Кроме этих, есть еще и другие высказывания, которые можно получить из двух исходных. С некоторыми из них мы также познакомимся.
Операции «НЕ», «И» и «ИЛИ» используются чаще других. Оказывается, с их помощью можно выразить любую логическую операцию, поэтому эти три операции можно считать основными, базовыми.
Операция «НЕ»
Операция «НЕ» часто называется отрицанием, или инверсией. В алгебре логики всего два знака, 0 и 1, поэтому логическое отрицание — это переход от одного значения к другому, от 1 к 0 или наоборот. Если высказывание A истинно, то «не А» ложно, и наоборот.
Для обозначения операции «НЕ» используются несколько способов. Выражение «не А» в алгебре логики записывается как Ā или ¬А.
Операцию «НЕ» можно задать в виде таблицы:
| A | Ā |
Эта таблица состоит из двух частей: слева перечисляются все возможные значения исходного высказывания (их всего два — 0 и 1), а в последнем столбце записывают результат выполнения логической операции для каждого из этих вариантов. Такая таблица называется таблицей истинности логической операции. Таблица истинности задает логическую функцию, то есть правила преобразования входных логических значений в выходные.
Операция «И»
Пусть есть два высказывания: A — «Сейчас идет дождь», B — «Форточка открыта». Сложное высказывание «A и B» выглядит так: «Сейчас идет дождь, и форточка открыта». Оно будет истинным (верным) в том и только в том случае, когда оба высказывания, A и B, истинны одновременно.
Операция «И»Ы (в отличие от «НЕ») выполняется с двумя логическими значениями, которые мы обозначим как A и B. Результат этой операции в алгебре логики записывают как А ⋅ B, А ∧ B или А & B.
| A | B | А∧ B |
В таблице истинности будет уже не один столбец с исходными данными, а два. Число строк также выросло с 2 до 4, поскольку для 2 бит мы получаем 4 разных комбинации: 00, 01, 10 и 11. Эти строчки расположены в определенном порядке: двоичные числа, полученные соединением битов A и B, идут в порядке возрастания. Как следует из определения, в последнем столбце будет всего одна единица, для варианта A = B = 1.
Легко проверить, что этот результат можно получить «обычным» умножением A на B, поэтому операцию «И» называют логическим умножением. Существует и другое название этой операции — конъюнкция (от лат. conjunctio — союз, связь).
Операция «ИЛИ»
Высказывание «Сейчас идет дождь, или форточка открыта» истинно тогда, когда истинно хотя бы одно из входящих в него высказываний, или оба одновременно. В алгебре логики операция «ИЛИ» обозначается как А+B или А ∨ B.
| A | B | А∨ B |
В таблице истинности будет только один ноль, для варианта A = B = 0.
Операцию «ИЛИ» называют логическим сложением, потому что она похожа на обычное математическое сложение. Единственное отличие — в последней строке таблицы истинности: в математике 1 + 1 равно 2, а в алгебре логики — 1. Другое название операции «ИЛИ» — дизъюнкция (от лат. disjunctio — разделение).
Доказано, что операций «НЕ», «И» и «ИЛИ» достаточно для того, чтобы записать с их помощью любую логическую операцию, которую только можно придумать. Например, для двух переменных существует всего 
= 16 логических операций: их таблицы истинности отличаются только последним столбцом, в котором 4 двоичных значения (4 бита).
