БЕЛОРУССКИЙГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ
КАФЕДРА РЭС
РЕФЕРАТ
НА ТЕМУ:
«Основныеаксиомы и тождества алгебры логики. Аналитическая форма представления булевыхфункций»
МИНСК, 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).
Таблица 1x y
/>
/>
/>
/> 1
/>
/> 1
/>
/> 1 1
/>
/>
Если в логическоевыражение входят операции дизъюнкции и конъюнкции, то следует соблюдать порядоквыполнения операций: сначала выполняется операция конъюнкции, а затем —операция дизъюнкции. Этим устанавливается иерархия операций: конъюнкция —старшая операция, дизъюнкция — младшая.
В сложных логическихвыражениях для задания порядка выполнения операций используются скобки. Дляупрощения записи выражений принято опускать те скобки, которые являются толькоподтверждением иерархии операций, например:
/>.
Но скобки нельзя опуститьв выражении />, поскольку
/>.
Некоторые теоремы итождества алгебры логики имеют особое значение, так как позволяют упрощатьлогические выражения. Например, в соотношениях (6), (10)…(12) и (15)…(18)правая часть проще левой, поэтому, произведя в логических выраженияхсоответствующие преобразования, можно добиться существенного их упрощения. Сэтой целью особенно часто используются тождества (15)…(18).
Перечисленные формулыприводятся без доказательств, но убедиться в их справедливости можно, подставивв правые и левые части равенств значения переменных 0 и 1. Эти формулы неисчерпывают возможных булевых равенств, но они являются основными припреобразовании булевых функций.
Операции дизъюнкции,конъюнкции и отрицания легко реализовать довольно простыми контактами(релейными) цепями и электронными схемами с односторонней проводимостью,имеющими конечное число входов и один выход. Простейшие электронные схемы,реализующие элементарные булевы функции (НЕ, И, ИЛИ, ИЛИ-НЕ, И-НЕ), называютсялогическими элементами (ЛЭ).
Аналитическая формапредставления булевых функций
При решении конкретныхтехнических задач булевы функции, отражающие логические связи, наиболее частозадаются в табличной форме. Однако такая форма задания функций при всей ее наглядностине позволяет ответить на вопрос, каким образом реализовать и если можно, тоупростить данную функцию. Для реализации и последующего упрощения булевуфункцию следует представить в аналитической форме в одном из функциональнополных наборов. Поскольку в настоящее время методы представления и минимизациифункций наиболее полно разработаны в базисе ОФПН, то именно этот базис вдальнейшем и будет рассматриваться.
Допустим, что в ходерешения задачи требуется реализовать переключательную функцию, заданнуютаблицей 2.
Таблица 2
Номер
набора Аргументы
Значение функции на i-ом наборе />
/>
/>
/> 1 1 2 1 3 1 1 1 4 1 5 1 1 6 1 1 1 7 1 1 1 1
Как видно из таблицы,функция должна принимать значение 1 только на 3-ем, 6-ом и 7-ом наборах. Навсех остальных наборах ее значение равно 0. Возникает вопрос, каким образомзаписать эту функцию аналитически, то есть представить в виде формулы.Применительно к основному базису, содержащему элементы дизъюнкции, конъюнкции иотрицания, доказано, что любая переключательная функция, предварительнозаданная в табличной форме, может быть записана аналитически в двух формах,получивших название канонических (нормальных): в дизъюнктивнойсовершенной нормальной форме (ДСНФ) и в конъюнктивной совершенной нормальнойформе (КСНФ).
Аналитическая записьфункций в виде ДСНФ и КСНФ предполагает представление этих функций посредствомсуперпозиции специально вводимых вспомогательных функций: минтермов и макстермов.
Минтермы часто называютконституентами единицы, а макстермы — конституентами нуля. Минтермомназывают булево произведение (конъюнкцию) от n переменных, в котором каждая переменная входит одинраз в прямой ил инверсной форме. Макстермом называют булеву суммуот n переменных, в которой каждаяпеременная входит один раз в прямой или инверсной форме.
Отсюда следует, чтопереключательная функция от nпеременных имеет число минтермов и макстермов, равное числу наборов, на которыхона определена, то есть /> минтермов и макстермов.
В качестве примераприведем минтермы и макстермы двух переменных X1 и X2 (табл. 3 и 4).
Таблица 3.Аргументы Минтермы
/>
/>
/>
/>
/>
/> 1 1 1 1 1 1 1 1
Таблица 4.Аргументы Макстермы
/>
/>
/>
/>
/>
/> 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Согласно приведеннымопределениям минтермы и макстермы двух аргументов выражаются формулами:
/>/>
Запись переключательнойфункции в виде ДСНФ означает, что любая переключательная функция, заданная табличнымспособом, может быть представлена в виде логической суммы конъюнктивныхчленов. При этом каждый из этих членов представляет собой произведениезначения функции на i-ом наборе на i-ый минтерм. Посколькупереключательная функция имеет /> минтермов, то аналитическаязапись функции в ДСНФ имеет вид:
/>.
Таким образом, функция,заданная таблицей состояний (табл. 1.8), запишется аналитически следующимобразом:
/>
Термины сокращенногопредставления функции в виде ДСНФ в частности означают: термин «дизъюнкция»указывает на то, что внешней функцией разложения является дизъюнкция, авнутренней — конъюнкция.
Термин «совершенная»указывает на то, что дизъюнктивные члены формируются из всех аргументов X1 …Xn, то есть на основе минтермов.
Термин «нормальная»указывает на то, что форма записи является двухуровневой, то естьдизъюнкция конъюнкций.
Аналитическая запись функциив виде КСНФ означает, что переключательная функция, заданная табличнымспособом, может быть представлена в виде логического произведения(конъюнкцией) дизъюнктивных членов. При этом каждый из этих членов представляетсобой сумму значений функции на i-омнаборе и i-ого макстерма.
Поскольку от n аргументов существует /> макстермов, тоаналитическая запись функции в КСНФ имеет вид:
/>
В итоге длярассматриваемого примера (табл. 1.8):
/>
или
/>
Сопоставляя две формызаписи одной и той же переключательной функции легко убедиться, что записьфункции в виде КСНФ более громоздкая, так как содержит большее число членов.Это объясняется тем, что число наборов, на которых переключательная функцияравна 0, значительно больше числа наборов, на которых функция равна 1. Дляслучая, когда число наборов, на которых функция равна 0, было бы меньше числанаборов, на которых функция равна 1, более предпочтительным оказываетсяпредставление функции в виде КСНФ. Отсюда следует, что обе формы представленияфункций фактически эквивалентны. Однако при минимизации функций более удобнойоказывается запись их в виде ДСНФ. Поэтому в дальнейшем будем рассматриватьтолько такие формы.
ЛИТЕРАТУРА
1. Новиков Ю.В. Основы цифровой схемотехники. Базовыеэлементы и схемы. Методы проектирования. М.: Мир, 2001. — 379 с.
2. Новиков Ю.В., Скоробогатов П.К. Основы микропроцессорнойтехники. Курс лекций. М.: ИНТУИТ.РУ, 2003. — 440 с.
3. Пухальский Г.И., Новосельцева Т.Я. Цифровые устройства:Учеб. пособие для ВТУЗов. СПб.: Политехника, 2006. — 885 с.
4. Преснухин Л.Н., Воробьев Н.В., Шишкевич А.А. Расчетэлементов цифровых устройств. М.: Высш. шк., 2001. — 526 с.
5. Букреев И.Н., Горячев В.И., Мансуров Б.М. Микроэлектронныесхемы цифровых устройств. М.: Радио и связь, 2000. — 416 с.
6. Соломатин Н.М. Логические элементы ЭВМ. М.: Высш. шк.,2000. — 160 с.