contents
Булева алгебра

Аксиомы и тождества


expand
Джордж Буль
Джордж Буль - английский математик и логик

Джордж Буль - один из основателей математической логики. В своей работе "Исследование законов мышления" он описал операции над логическими высказываниями. Раздел математики, который мы изучаем, в его честь назвали Булева алгебра.

Ранее мы говорили, что булева алгебра включает конъюнкцию, дизъюнкцию, отрицание, а также логический нуль и логическую единицу. Теперь рассмотрим основные правила обращения с булевыми выражениями.

Знание свойств булевых выражений поможет нам лучше понимать формулы; упрощать их без использования графических представлений и без построения таблицы истинности; находить наиболее оптимальные формулы для реализации функции на логических элементах.

Аксиомы
ᖰ0ᖳ = 1
ᖰ1ᖳ = 0
0 ∨ 0 = 0
0 ∨ 1 = 1
1 ∨ 0 = 1
1 ∨ 1 = 1
0 ∧ 0 = 0
0 ∧ 1 = 0
1 ∧ 0 = 0
1 ∧ 1 = 1
Теоремы одной переменной
a ∧ 0 = 0
a ∧ 1 = a
a ∧ ᖰaᖳ = 0
a ∨ 0 = a
a ∨ 1 = 1
a ∨ ᖰaᖳ = 1
двойная инверсия:
¬ᖰaᖳ = a
Свойства (тождества)

1) Коммутативность
От перемены мест операндов результат не изменится.
a ∨ b = b ∨ a
a ∧ b = b ∧ a
2) Ассоциативность(лат. associatio соединение)
a ∨ (b ∨ с) = (a ∨ b) ∨ с
a ∧ (b ∧ с) = (a ∧ b) ∧ с
Это свойство позволяет раскрыть скобки. В дальнейшем будем опускать знак конъюнкции для наглядности.
a ∨ (b ∨ с) = a ∨ b ∨ с
a(bс) = abс
3) Дистрибутивность (лат. distributivus — распределительный)
a ( b ∨ c) = ab ∨ ac
a ∨ (bc) = (a ∨ b)(a ∨ c)
Это свойство позволяет раскрывать скобки в выражениях и выносить общий "множитель" за скобки:
a ( b ∨ c ∨ d ) = ab ∨ ac ∨ ad
a ∨ bcd = ( a ∨ b )( a ∨ c )( a ∨ d )
4) Идемпотентность (лат. idem – тот же самый и potens – сильный)
Повторное применение операции даёт тот же результат, что и однократное.
a ∨ a = a
a ∧ a = a
Поэтому в булевых выражениях нет коэффициентов и степеней.
5) Поглощение
a ( a ∨ b) = a
a ∨ ab = a
6) Склеивание
( a ∨ b )( a ∨ ᖰbᖳ ) = a
ab∨( aᖰbᖳ) = a
7) теорема Блейка-Порецкого
a ( ᖰaᖳ ∨ b) = ab
a ∨ ᖰaᖳb = a ∨ b
aс ∨ bᖰcᖳ = ac ∨ bᖰcᖳ ∨ ab
( a∨с )( b ∨ ᖰcᖳ) = ( a∨с )( b ∨ ᖰcᖳ)( a∨b )
8) теорема де Моргана
Здесь добавим знак конъюнкции для ясности:
ᖰ( a ∧ b )ᖳ = ᖰ a ᖳ ∨ᖰ b ᖳ
ᖰ( a ∨ b )ᖳ = ᖰ a ᖳ ∧ᖰ b ᖳ

Знак конъюнкции нужно вставлять, если знаки инверсии сливаются, например выражение ᖰabᖳ может быть понято как ᖰa ∧ bᖳ и как ᖰaᖳ ∧ ᖰbᖳ, что приведет к различным результатам. Будьте внимательны, т.к. это источник многих ошибок.

Чтобы подтвердить или опровергнуть вышеописанные теоремы, постройте таблицу истинности для выражений слева и справа от знака равенства. Если таблицы идентичны, значит теорема верна.