БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ
КАФЕДРА РЭС
РЕФЕРАТ
НА ТЕМУ:
«Основные аксиомы и тождества алгебры логики. Аналитическая форма представления булевых функций»
МИНСК, 2009
Основные аксиомы и тождества алгебры логики
Булева алгебра позволяет не только математически описывать переключательные функции, но и преобразовывать их, давая возможность реализовывать эти функции на различных функционально полных системах. Поскольку переключательные функции в конечном счете отражают определенные логические связи между различными узлами цифровых устройств, то тем самым булева алгебра позволяет преобразовывать эти связи и, следовательно, она является аппаратом, позволяющим разработчику осуществлять выбор оптимального варианта.
В настоящее время наиболее полно разработаны методы преобразования выражений, которые содержат переключательные функции ОФПН (основного функционально полного набора). Применительно к такому набору булева алгебра располагает рядом аксиом и законов, основными из которых являются:
Система аксиом:
Аксиома (1) является утверждением того, что в алгебре логики рассматриваются только двоичные переменные, аксиомы (2)…(5) определяют операции дизъюнкции и конъюнкции, а аксиома (5) — операцию отрицания. Если в аксиомах (2)…(5), заданных парами, произвести взаимную замену операций дизъюнкции и конъюнкции, а также элементов 0 и 1, то из одной аксиомы пары получится другая. Это свойство называется принципом двойственности.
Теоремы и тождества алгебры логики
С помощью аксиом алгебры логики можно доказать целый ряд теорем и тождеств. Одним из эффективных методов доказательства теорем является метод перебора всех значений переменных: если теорема истинна, то с учетом (2)…(5) уравнение, формулирующее утверждение теоремы, должно быть истинно при подстановке любых значений переменных в обе его части.
Метод перебора не слишком трудоемок, так как переменные могут иметь только два значения: 0 и 1.
Так, методом перебора легко убедиться в справедливости следующих теорем:
Идемпотентные законы (законы тождества):
(6)
Коммутативные законы (переместительные):
(7)
Ассоциативные законы (сочетательные):
(8)
Дистрибутивные законы:
(9)
Законы отрицания:
(10)
(11)
(12)
Законы двойственности (Теоремы де Моргана):
(13)
Закон двойного отрицания:
(14)
Законы поглощения (абсорбция):
(15)
Операции склеивания:
(16)
Операции обобщенного склеивания:
(17)
(18)
Теоремы (6)…(13) и (15)…(18) записаны парами, причем каждая из теорем пары двойственна другой, так как из одной теоремы пары можно получить другую на основании принципа двойственности, то есть путем взаимной замены операций дизъюнкции и конъюнкции, а также элементов 0 и 1, если они имеются. Теорема (14) самодвойственна, так как она не изменяется по принципу двойственности (отсутствуют элементы 0 и 1 и операции дизъюнкции и конъюнкции). Все теоремы могут быть доказаны аналитически или методом перебора. В качестве примера приведем доказательство тождества (13) методом перебора (табл. 1).
Таблица 1
Если в логическое выражение входят операции дизъюнкции и конъюнкции, то следует соблюдать порядок выполнения операций: сначала выполняется операция конъюнкции, а затем — операция дизъюнкции. ............
