Компьютерная схемотехника
Методическое пособие - Компьютеры, программирование
Другие методички по предмету Компьютеры, программирование
ческих функций отражают принцип двойственности булевой алгебры.
3.6 Основные тождества булевой алгебры
А+0=А;А+1=1;
А+А=А;А+=1;
А*0=0;А*1=А;
А*А=А;А*=0;=А.
3.7 Основные законы и теоремы булевой алгебры
3.7.1 Законы
Переместительный (свойство коммутативности): А+В=В+А; А*В=В*А.
Сочетательный (свойство ассоциативности): (А+В)+С=А+(В+С); (А*В)*С=А*(В*С).
Распределительный (свойство дистрибутивности): А*(В+С)=А*В+А*С; А+В*С=(А+В)*(А+С).
3.7.2 Теоремы
Поглощения: А+А*В=А; А*(А+В)=А.
Склеивания:
Де Моргана. Существует две формы записи теоремы де Моргана:
Форма 1:(3.1.1)
Форма 2:(3.1.2)
Последние два выражения вытекают из принципа двойственности булевой алгебры (раздел 3.5).
Теорема без названия. Существует еще одна теорема без названия, которую представим следующим образом:
(3.1.3)
Два полезных соотношения:
(3.1.4)
3.8 Совершенная дизъюнктивная нормальная форма (СДНФ) записи булевых выражений
СДНФ является одной из аналитических форм представления переключательных функций. Булевы выражения простых логических функций можно записать по их словесному описанию. В общем случае для получения аналитической формы (булевого выражения) используют таблицы истинности.
Предположим, логическая функция трех переменных задана таблицей истинности (таблица 3.4).
Таблица 3.4
№набораСВАF0000010011201003011041001510116110171110
Эта функция имеет четыре конституенты единицы К1, К4, К5 и К6 (коституента единицы это единичное значение ПФ на одном конкретном наборе. Всего для ПФ трех переменных может быть восемь конституент единицы, если функция принимает единичное значение на всех наборах). Конституента единицы записывается в виде конъюнкции. Для нашего примера ; .
Булево выражение ПФ в СДНФ представляет сумму конституент единицы:
.(3.2)
Поскольку конституенты единицы записываются в виде конъюнкций, то СДНФ представляет сумму конъюнкций, каждая из которых содержит все переменные в прямом или инверсном виде не более одного раза. Очевидно, что логическая функция имеет единственное булево выражение в СДНФ, что следует из методики его получения.
СДНФ называется дизъюнктивной (состоит из суммы конъюнкций), совершенной (все конъюнкции содержат по одному разу каждую переменную в прямом или инверсном виде) и нормальной (двухуровневой) для ее реализации требуются логические элементы двух видов: конъюнкторы и дизъюнкторы, при этом предполагается, что исходные переменные поступают в прямом и инверсном виде.
3.9 Дизъюнктивная нормальная форма (ДНФ)
Если в выражении (3.2) во всех или некоторых конъюнкциях отсутствуют отдельные переменные (в прямой или инверсной форме) или ряд конъюнкций, отображающих конституенты единицы, отсутствуют вообще, то такая форма представления булевого выражения называется дизъюнктивной нормальной формой (ДНФ).
Переключательная функция может описываться несколькими булевыми выражениями в ДНФ, одно из которых является минимальным (содержит минимум конъюнкций и минимум входящих в них переменных).
3.10 Совершенная конъюнктивная нормальная форма (СКНФ) записи булевых выражений
Описанная таблицей 3.4 переключательная функция помимо конституент единицы содержит конституенты нуля К0, К2, К3 и К7 (конституента нуля это нулевое значение ПФ на одном конкретном наборе). Всего для ПФ 3-х переменных может быть восемь конституент нуля, если функция принимает нулевое значение на всех наборах. Конституента нуля записывается в виде дизъюнкции. Для нашего примера (таблица 3.4) это
Булево выражение в СКНФ представляет собой произведение конституент нуля:
.(3.3)
СКНФ называется конъюнктивной (состоит из произведения дизъюнкций), совершенной (все дизъюнкции включают по одному разу каждую переменную в прямом или инверсном виде) и нормальной (двухуровневой) для ее реализации требуются логические элементы двух видов: конъюнкторы и дизъюнкторы, при этом предполагается, что исходные переменные поступают в прямом или инверсном виде.
Логическая функция имеет единственное булево выражение в СКНФ.
3.11 Конъюнктивная нормальная форма (КНФ)
Если в выражении (3.3) все дизъюнкции или отдельные из них не содержат всех переменных в прямом или инверсном виде, а также некоторые дизъюнкции вообще отсутствуют, то такая форма представления булевого выражения называется конъюнктивной нормальной формой (КНФ).
Переключательная функция может описываться несколькими булевыми выражениями в КНФ, одно из которых является минимальным (содержит минимум дизъюнкций и минимум входящих в них переменных).
3.12 Минимизация логических функций
Минимизацией называют процедуру упрощения аналитического выражения, представляющего переключательную (логическую) функцию, направленную на то, чтобы булево выражение ПФ содержало минимальное количество членов с минимальным числом переменных.
Способы минимизации:
алгебраический;
с помощью диаграмм Вейча (карт Карно).
3.12.1 Алгебраический способ минимизации ПФ
В некоторых простых случаях можно осуществить минимизацию булевого выражения ПФ,