Алгебра логики

В алгебре логики имеется четыре основных закона: 1. Переместительный, или закон коммутативности для операций сложения и умножения, соответственно: A Ú B = B Ú A; A B = B A. 2. Сочетательный, или закон ассоциативности для сложения и умножения, соответственно: (A Ú B) Ú C = A Ú (B Ú C); (A B) C = A (B C). 3. Распределительный, или закон дистрибутивности для сложения и умножения, соответственно: (A Ú B) C = A C Ú B·C; (A B) Ú C = (A Ú C) (B Ú C). 4. Закон двойственности или инверсии (правило де Моргана) для логических операций сложения и умножения, соответственно: сложение , , , умножение , , , . Благодаря этим правилам появилась возможность выражать дизъюнкцию через конъюнкцию и отрицание, а конъюнкцию – через дизъюнкцию и отрицание. Законы двойственности справедливы для любого числа переменных. Справедливость этих законов можно доказать с помощью таблиц истинности сложных логических связей, описываемых законом, или с помощью логических преобразований. Эти правила широко используют для преобразования переключательных функций с целью их упрощения. Формы переключательной функции являются двойственными, если одна получается из другой путем замены всех символов операции И на символы операции ИЛИ и наоборот; всех нулей на единицы и наоборот. Например, для функции двойственной функцией будет YДВ = = = .     В булевой алгебре при отсутствии в выражении скобок вводится следующий порядок действий: первыми выполняются операции отрицания, далее конъюнкции, затем – дизъюнкции. Наличие в выражении скобок изменяет обычный порядок действий: в первую очередь должны выполняться операции внутри скобок. Тождества и правила Для преобразований логических выражений пользуются легко доказываемыми тождествами (таблица 3.1): Таблица 3.1– Набор логических тождеств А Ú 0 = А А Ú = 1 А·А = А А Ú 1 = 1 А·0 = 0 А· = 0 А Ú А = А А·1 = 1 = А С помощью законов алгебры логики и тождеств могут быть доказаны соотношения, получившие названия правил: поглощения A Ú A×B = A, A×(1 Ú B) = A, склеивания: А·ВÚ А = А; (А·Ú В )(А +) = А. Доказать справедливость этих соотношений можно путем следующих преобразований: А Ú A×B = A – доказательство A + A×B = А (1 + В) = А·1 = А; A×(A Ú B) = A – A×(A Ú B) = А А + А В = А + А В = А; (А·Ú В )(А + ) = А (А·Ú В )(А + ) = А А + А +В А +В = = А (1 + + В + 0) = А. Эти правила широко используют для преобразования переключательных функций с целью их упрощения. Формы переключательной функции являются двойственными, если одна получается из другой путем замены всех символов операции И на символы операции ИЛИ и наоборот; всех нулей на единицы и наоборот. Например, для функции F = = = = = .     Двойственная функция FДВ = Первыми, как и в арифметике, выполняются действия внутри скобок. В булевой алгебре при отсутствии в выражении скобок вводится следующий порядок действий: первыми выполняются операции отрицания, далее конъюнкции, затем – дизъюнкции. Наличие в выражении скобок изменяет обычный порядок действий: в первую очередь должны выполняться операции внутри скобок. 3.4 Элементарные логические функции. Совокупность различных значений переменных называют набором. Булева функция n аргументов может иметь до N = 2n наборов. Поскольку функция принимает только два значения, общее число булевых функций n аргументов равно 2N = 22n. Таким образом, функция одного аргумента может иметь четыре значения: f1 = А, f2= , f3 = 1 (константа 1), f4 = 0 (константа 0). Два аргумента дают 16 значений функции (таблица 3.3.).     Любая из этих функций обращается в единицу (конституента единицы) только на своем наборе, во всех остальных случаях (2n – 1) она равна нулю. Функции взаимно инверсны, если на том же наборе функции обращается в нуль (конституента нуля), а в остальных случаях она равна единице. В число шестнадцати функций входят и вырожденные функции: f0 = 0 – константа 0; f15 = 1 – константа 1; f3 = a – переменная a; f 5 = b – переменная b; f12 = – инверсия a; f10 = – инверсия b. Остальные десять булевых функций сведены в таблицу 3.4. Кратко рассмотрим работу логических элементов, которые не были описаны выше. Логическое ИЛИ-НЕ Функции «дизъюнкция с отрицанием» это логическое ИЛИ-НЕ (NOR gate) f1 = (стрелка Пирса, функция Вебба). Судя по таблице (рис 3.6, а), низкий уровень напряжения устанавливается на выходе, если на любом из входов присутствует высокий уровень напряжения. Там же на рис.3.6, б приведено УГО логическое И-НЕ и эпюры напряжений входах и выходах схемы (рис 3.6в). Число входов можно расширять до любого количества.     Особенностью функции является то, что высокий уровень H на выходе устанавливается лишь при наличии низких уровней L на всех входах. Логическое И-НЕ Следующая функциональная схема – логическое И-НЕ (штрих Шеффера, NAND gate) f7 = . Если на любой из входов подан низкий уровень напряжения, то на выходе устанавливается высокий уровень напряжения (табл. на рис. 3.7, а). Там же приведены УГО логическое И-НЕ и эпюры напряжений входах и выходах схемы (рис. 3.7, а и3.7, б, соответственно).     Особенностью функции является то, что лог. 1 устанавливается на выходе при наличии хотя бы на одном из входов низкого уровня L. Запрет по В Функция «запрет по b» логическая конъюнкция a и f4 = . На рис.3.8, а представлена таблица истинности, условное графическое обозначение показано на рис. 3.8, б и на рис. 3.8, в – эпюры напряжений. В связи с тем, что сигнал b приходит на вход схемы логического умножения в инверсном виде, то сигналы а высокого уровня проходя на выход ЛЭ только при низком уровне управляющего сигнала b, что отражено на эпюрах (рис. 3.8,).     Импликация от В к А Импликация от b к a это дизъюнкция a и f11 = . На рис. 3.8 а, б, в приведена таблица истинности (а), условное графическое обозначение (б) и эпюры напряжений (в).     Логический ноль на выходе устанавливается лишь в одном случае, когда a и принимают низкий уровень. Равнозначность А и В Равнозначность указывает на то, что оба аргумента имеют одинаковый (высокий H или низкий L) уровень. Таблица истинности, условное графическое обозначение и эпюры напряжений приведены на рис. 3.9 а, б, в, соответственно. Функция «логическая равнозначность» широко применяется в разнообразных устройствах контроля. Двойственные функции Свойства двойственности переключательных функций широко используются при проектировании электронных устройств. Как уже указывалось, функцию алгебраического умножения всегда можно заменить функцией алгебраического сложения, используя правило отрицания (де Моргана). Взаимно инверсные функции сведены в табл. 3.4. Первая пара двойственных функций относится к дизъюнкциям. Функция Пирса f1 = инверсна по отношению к функции дизъюнкции f14 = , . Функция Шеффера f7 = инверсна по отношению к конъюнкции f8 = a Ù b: . Функции запрета и импликации также инверсны по отношению друг к другу: Для функции «запрет по b» f4 = b инверсной является «импликация от b к a» f11 = : . В свою очередь «запрет по b» f2 = своей инверсной функцией имеет «импликацию от a к b» f13 = : . Взаимно инверсны функция неравнозначности (сложения по модулю два) f6 = и функция равнозначности f9 = = . Для доказательства этого равенства воспользуемся правилом де Моргана: = = = = . С помощью одного и двух переменных, называемых элементарными логическими функциями, можно, используя принцип суперпозиции, т.е. принцип подстановки булевых функций вместо аргументов в другую функцию, можно построить булеву функцию любой сложности.