Заметим, что в левой части таблицы перечислены всевозможные комбинации входных переменных (наборы значений), а в правой - возможные реакции выходных сигналов. В табл. 2.5 представлены функции у4-у9, полностью соответствующие функциям табл. 2.4, а также новые, часто используемые и интересные функции у4-у9. При этом местоположение функций и их нумерация в таблице особого значения не имеют. По данной таблице нетрудно составить аналитическое выражение (зависимость) для каждой функции от двух аргументов вида (2.2). Для этого наборы переменных, на которых функция принимает значение единицы, записываются как конъюнкции (логическое умножение) и связываются знаками логического сложения. Такие формы функций получили название дизъюнктивных нормальных форм (ДНФ). Если в этих функциях конъюнкции содержат все без исключения переменные в прямом или инверсном значениях, то такая форма функций называется совершенной.
Функция у4представляет собой функцию логического сложения, дизъюнкцию. Она принимает значение единицы, если значение единицы имеет хотя бы одна переменная х1или х2:
Функция y5 является инверсной функцией по отношению к y4:
Она имеет название “ отрицание дизъюнкции”. Иногда в литературе встречается ее специальное название “стрелка Пирса”, по фамилии математика, исследовавшего ее свойства.
Функция у6 является функцией логического умножения. Она очень похожа на операцию обычного умножения и принимает значение единицы в тех случаях, когда все ее переменные равны единице:
Функция y7 является инверсной функцией по отношению к у6:
Она называется “отрицание конъюнкции” или “ штрих Шеффера”. Функция к называется логической равнозначностью, она принимает значение единицы, если все ее переменные имеют одинаковое значение (или 0 или 1):
Функция y9 является инверсной по отношению к y8:
Она принимает значение единицы, если ее переменные имеют противоположные значения. Ниже будет показано, что функции у8 и у9 являются основой для построения сумматоров, так как они соответствуют правилам формирования цифр двоичных чисел при сложении (вычитании).
Из перечисленных функций двух переменных можно строить сколь угодно сложные зависимости, отражающие алгоритмы преобразования информации, представленной в двоичной системе счисления. Алгебра логики устанавливает правила [6] формирования логически полного базиса простейших функций, из которых могут строиться любые более сложные. Наиболее привычным базисом является набор трех функций {инверсия - é , дизъюнкция - v, конъюнкция - Λ или &}. Работа с функциями, представленными в этом базисе, очень похожа на использование операций обычной алгебры.
Алгебра логики устанавливает, что существуют и другие комбинации простейших логических функций, обладающих свойством логической полноты. Например, наборы логических функций {инверсия, дизъюнкция} и {инверсия, конъюнкция} также являются логически полными. Наиболее интересны минимальные базисы, включающие по одной операции {“отрицание дизъюнкции (ØÚ )”} и {“отрицание конъюнкции (ØÙ )”}. Однако работа с функциями, представленными в указанных базисах, требует от специалистов по проектированию ЭВМ определенных навыков.
Из определения вышеприведенных функций можно установить целый ряд простейших свойств:
В алгебру логики установлен целый ряд законов, с помощью которых возможно преобразование логических функций (ЛФ):
коммутативный (переместительный)
x1*x2=x2*x1
ассоциативный (сочетательный)
(x1*x2)*x3=(x1*x3)*x2=x1*(x2*x3)
Эти законы полностью идентичны законам обычной алгебры;
дистрибутивный (распределительный)
Закон поглощения. В дизъюнктивной форме ЛФ конъюнкция меньшего ранга, т.е. с меньшим числом переменных, поглощает все конъюнкции большего ранга, если ее изображение содержится в них. Это же справедливо и для конъюнктивных форм:
Закон склеивания
Закон свёртки
.
Правило де Моргана Заказать перевод
где F - логическая функция общего вида, не зависящая от переменной х.
Убедиться в тождественности приведенных зависимостей можно путем аналитических преобразований выражений или путем построения таблицы истинности для ЛФ, находящихся в левой и правой частях.
Используя данные зависимости, можно преобразовывать исходные выражения в более простые (минимизировать их). По упрощенным выражениям можно построить техническое устройство, имеющее минимальные аппаратурные затраты.
.