Основные понятия алгебры логики
Беленький Павел Павлович кандидат педагогических наук, доцент кафедры ОНП
Основные понятия алгебры логики
Булевыми величинами (или булевыми константами) называются два заранее выбранных разных символа. По традиции применяются символы 0 и 1.
Булевыми переменными называются переменные, которые могут принимать булевы значения.
Для того, чтобы некоторую величину можно было обозначать булевой переменной, должны выполняться следующие ограничения: 1.Величина должна принимать два возможных состояния, но не более того.
2.В любой момент времени величина не может принимать оба состояния одновременно.
3.В любой момент времени величина не может принимать ни одного состояния.
4.Если рассматриваются несколько таких величин, то допускается, чтобы каждая из них принимала одно из двух состояний независимо. 5.Не допускается применять одну пару состояний для одной величины, а для другой - другую.
Унарные операции
Единственная нетривиальная функция - отрицание. Она изменяет значение параметра на противоположное:~0 = 1, ~1 = 0. Знак "~" является знаком унарной операции и обозначает эту функцию.
Бинарные операции
Некоторые из нихвсегда совпадают по значению с булевой константой, булевой переменной или функцией только от одной из двух переменных. Таких функций всего шесть: 0, 1, x, ~x, y, ~y. Далее мы будем из называть тривиальными. Вот таблицы истинности для них:
Бинарные операции |
|
Остальные 10 функций не упрощаются. |
"ИЛИ" |
"И" |
"исключающее ИЛИ"
"ИЛИ-НЕ"
"И-НЕ"
Бинарные операции
Сводная таблица всех бинарных логических операций от двух переменных
Общий формат для обозначения функции от двух аргументов через знак бинарной операции выглядит какF)#(G), где F и G - некоторые формулы, а # - знак бинарной операции. Для вычисления значения формулы (F)#(G) надо вычислить значение формул F и G, и подставить их в таблицу истинности как первый и второй аргументы функции.
Равенства
Правила преобразований мы будем записывать в виде равенств: F = G,
где F и G - булевы функции, заданные в виде формул с унарными и бинарными операциями.
В алгебре логики действуют два правила вывода:
1.Если в обоих частях равенства заменить переменную на любую формулу (одну и ту же во всех местах, где встречается эта переменная), то получится равенство.
Например, из равенства
~(x & y) = x | y путем замены x на x & ~y получим:
~((x & ~y) & y) = (x & ~y) | y.
2. Если F = G, то в любом равенстве можно заменять F на G или G на F и в результате получится равенство. В отличие от предыдущего случая делать замену во всех местах необязательно.
Например, пусть у нас есть два равенства:
~(x & y) = x | y |
(1) |
~(~x) = x |
(2) |
Мы можем взять равенство (1) и в нем вместо x подставить ~(~x), поскольку эти две формулы объединены равенством (2):
~(~(~x) & y) = ~(~x) | y
Свойства логических операций
Закон двойного отрицания. ~(~x) = x
Обратные операции. Формулы обратных операций позволяют убирать знак отрицания в формулах вида ~(x # y) путем замены некоторой
операции # на другую операцию:
~(x & y) = x | y ~(x | y) = x & y ~(x > y) = x y ~(x y) = x > y ~(x < y) = x y ~(x y) = x < y ~(x y) = x y ~(x y) = x y ~(x y) = x y ~(x y) = x y
Свойства логических операций
Коммутативные операции.
Коммутативными называют операции, которые позволяют
переставлять местами свои операнды, не меняя операцию.
x & y = y & x
xy = y x
xy = y x
xy = y x
xy = y x x | y = y | x
Остальные операции также позволяют переставлять операнды, но с
заменой на другую операцию:
x > y = y < x x y = y x
Свойства логических операций
Ассоциативные операции.
Ассоциативными называют операции, которые можно группировать и выполнять в произвольном порядке.
ассоциативны всего лишь 4 операции из 10 нетривиальных:
Из комутативности и ассоциативности этих четырех операций следует, что если мы имеем много переменных подряд, соединенных такой операцией, то переменные можно переставлять в любом порядке, а
значит скобки для указания порядка не обязательны:
(a & b) & (c & d) = a & d & c & b.