====== Основы алгебры логики ====== В VIII веке английский ученый Дж. Буль, занимаясь теорией высказываний, преобразовал формулы с учетом того, что каждая переменная может иметь только два значений – «правда» или «ложь» («1» или «0» соответственно). Итак, двоичная переменная может иметь только два значения («1» или «0»). Двоичная функция – функция принимающая значения «1» или «0». Например: y = a + b; y = a • b ===== Функции алгебры логики ===== Рассмотрим все возможные функции от одной переменной: ^ x ^ y0 ^ y1 ^ y2 ^ y3 ^ | 0 | 0 | 0 | 1 | 1 | | 1 | 0 | 1 | 0 | 1 | y0 = 0 - константа «0» (земля, GND),\\ y1 = x - повторение,\\ y2 = ~x - инверсия,\\ y3 = 1 - константа «1» (VCC). ===== Условные графические обозначения (УГО): ===== === Функции алгебры логики (ФАЛ) === Рассмотрим теперь все возможные функции от двух переменных: ^ x1 ^ x2 ^ y0 ^ y1 ^ y2 ^ y3 ^ y4 ^ y5 ^ y6 ^ y7 ^ y8 ^ y9 ^ y10 ^ y11 ^ y12 ^ y13 ^ y14 ^ y15 ^ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | Среди этих функций можно найти уже известные нам: y0 = 0;\\ y15 = 1;\\ y3 = x1;\\ y5 = x2;\\ y12 = ~x1;\\ y10 = ~x2; но встречаются и новые:\\ y1 = x1 & x2 = x1 C x2 = x1 • x2 - конъюнкция (И, логическое умножение); y2 = x1 • ~x2 - данная функция не является базовой в цифровой технике а потому и без названия; y4 = ~x1 • x2 - аналогично; y6 = x1 ^ x2 = x1 • ~x2 E ~x1 • x2 - сумма по модулю 2 (исключающее ИЛИ, неравнозначность); y7 = x1 E x2 - дизъюнкция (ИЛИ, логическое сложение); y8 = ~y7 = ~(x1 E x2) = x1 ? x2 - ИЛИ-НЕ (Функция Вебба); y9 = ~y6 = ~(x1 ^ x2) = x1 ? x2 - равнозначность; y11 = x2 ® x1 = ~y4 = ~(~x1 • x2) - импликация x1 из x2; y13 = x1 ® x2 - импликация x2 из x1; y14 = ~(x1 & x2) = x1 / x2 - И-НЕ (функция Шеффера). ФАЛ для числа переменных больше двух выражаются с помощью вышерассмотренных функций. Заметим, что одни функции можно выразить через другие. Таким образом, функционально полный базис – минимальный набор функций, через которые можно выразить любую функцию. Существует несколько таких базисов, например: И, ИЛИ, НЕ (Булев базис);\\ И, НЕ; ИЛИ, НЕ;\\ И-НЕ; ИЛИ-НЕ. ===== Аксиомы алгебры логики. ===== a • a = a; a • ~a = 0; a E ~a = 1; ~(~a) = a; a • 1 = a; a • 0 = 0; a E 0 = a; a E 1 = 1; a E a = a; === Законы алгебры логики. === == Переместительный == a • b = b • a;\\ a E b = b E a. == Сочетательный == (a • b) • c = a • (b • c);\\ (a E b) E c = a E (b E c). == Распределительный == a • b E a • c = a • (b E c);\\ (a E b) • (a E c) = a E b • c. == Де-Моргана == a • b = ~(~a E ~b);\\ ~(a • b) = ~a E ~b;\\ a E b = ~(~a • ~b);\\ ~(a E b) = ~a • ~b. == Закон склеивания == a • b E a • ~b = a • (b E ~b) = a (см. аксиомы 1, 5);\\ A • b E A • ~b = A\\ , где А – любая функция. == Закон поглощения == A • b E A = A;\\ a • B E ~a = B E ~a. ===== Представление ФАЛ. ===== Любая функция алгебры логики может быть представлена в следующем виде: Таблица истинности; Аналитическим образом (в виде формул); В цифровом виде; Геометрическим образом; Рассмотрим подробнее каждый вид представления: - Таблица истинности представляет собой таблицу которая имеет n+1 столбцов и 2n строк, где n – число аргументов функции. В первых n столбцах записываются все двоичные комбинации аргументов, а в n+1-м столбце – значение функции. Например: ^ a ^ b ^ c ^ y ^ | 0 | 0 | 0 | 1 | | 0 | 0 | 1 | 1 | | 0 | 1 | 0 | 1 | | 0 | 1 | 1 | 1 | | 1 | 0 | 0 | 1 | | 1 | 0 | 1 | 0 | | 1 | 1 | 0 | 0 | | 1 | 1 | 1 | 0 | - Для представления функции в аналитическом виде используется любой функционально полный набор (базис) ФАЛ. Например, для получения выражения, описывающего ФАЛ, необходимо записать конъюнкцию переменных или их инверсий для каждого единичного значения функции и объединить их операцией ИЛИ. Такой вид функций называется совершенной дизъюнктивной нормальной формой (СДНФ). В формуле каждый аргумент используется с инверсией, если он равен 0 или без инверсии, если он равен 1. Рассмотрим СДНФ функции из 1го пункта: y = ~a • ~b • ~c E ~a • ~b • c E ~a • b • ~c E ~a • b • c E a • ~b • ~c = В общем случае, любая комбинация переменных и их инверсий называется термом (например, терм, подчеркнутый выше). Термы могут быть конъюнктивными или дизъюнктивными. = ~a • ~b • (~c E c) E ~a • b • (~c E c) E a • ~b • ~c = ~a • ~b E ~a • b E a • ~b • ~c = Подчеркнутая выше формула представлена в виде дизъюнктивной нормальной форм (не совершенной т.к. используется неполный набор переменных в термах). = ~a E a • ~b • ~c = ~a E ~b • ~c. Если число переменных в термах этой формы (ДНФ) минимально, то такое выражение называется минимальной ДНФ (подчеркнутая выше формула). В общем случае, ДНФ называется выражение, конъюнктивные термы которого связаны знаком дизъюнкции. Существует также совершенная конъюнктивная форма (СКНФ). Для получения СКНФ необходимо создать набор дизъюнктивных термов, соединенных знаком дизъюнкции для всех нулевых (в отличие от КНФ) для всех нулевых значений функции, при этом переменные входят в терм с инверсией, если равны 1 и без нее, если равны 0. Рассмотрим все туже функцию из 1го пункта: y = (~a E b E ~c) • (~a E ~b E c) • (~a E ~b E ~c)- СКНФ. Аналогично, добившись с помощью логических преобразований того, что число переменных в текущей форме (КНФ) станет минимальным, мы получим минимальную КНФ. - Для представления ФАЛ в цифровом виде указываются десятичные эквиваленты наборов функций на которых она принимает единичные значения. Например: Y = 1 для {0, 1, 2, 3, 4}. - Геометрический вид применения на практике не нашел. Он заключается в построении кубов n-й размерности, где n – число аргументов. Например: - Карта Карно представляет собой прямоугольную или квадратную таблицу в каждой ячейке которой записывается значение ФАЛ на соответствующем наборе аргументов. Например: ^ a ^ b ^ c ^ y ^ | | | b | | | | | 0 | 1 | | a | 0 | 0 | 1 | | | 1 | 1 | 0 | ^ ^ ^ b,c ^ ^ ^ ^ ^ ^ ^ 00 ^ 01 ^ 11 ^ 10 ^ ^ a ^ 0 | 1 | 0 | 0 | 1 | ^ ^ 1 | 0 | 1 | 1 | 0 | В Карте Карно соседнее ячейки имеют «соседние» коды. Это означает, что они не должны отличаться больше чем в одном разряде. Пример для двух разрядов был представлен в предыдущей Карте Карно, рассмотрим пример для трех разрядов: 000 – 001 – 011 – 010 - 110 – 111 – 101 – 100 Как видно из примера, код симметричен относительно середины за исключением первого бита. Аналогично строятся карты большего размера. - Представление ФАЛ в виде логической схемы представляет собой комбинацию УГО, входы и выходы которых связаны некоторым образом. Например: ===== Минимизация ФАЛ с помощью Карт Карно. ===== Для получения минимальной ДНФ в Карте Карно необходимо объединить прямоугольные или квадратные фрагменты единиц с количеством кратным степени 2. При этом фрагменты должны быть максимальными по размеру и включать только единицы. Для получения аналитического выражения записывают те переменные (их инверсии), которые на данном фрагменте неизменны. Например: <рисунок x10, пример > y = ~a E ~b • ~c. Неизменные переменные и их инверсии формируют конъюнктивные термы, которые в последствии соединяют знаком дизъюнкции. <рисунок x11, пример > В карте Карно с количеством переменных больше 4 могут объединяться разрывные покрытия, симметричные относительно вертикальной или горизонтальной осей. Так же объединяются переменные в соответствующих местах отдельных квадратов. <рисунок x12, пример > Получение минимальной КНФ с помощью Карт Карно. Для получения минимальной КНФ выполняется склеивание по тем же правилам, но только нулевых (в отличие от ДНФ) значений функции. При этом записывают дизъюнктивные термы, соединенные знаком конъюнкции. Каждый терм содержит неизменные переменные или их инверсии причем, если на карте переменная равна 0, то она берется без инверсии, 1 – с инверсией. <рисунок x13, пример > В некоторых случаях требуется ДНФ для инверсного значения функции. Для этого выполняется минимизации функции по нулевым значениям, но записывается ДНФ. Например: ~y = ~a • ~b E a • c = ~(a E b) E ~(~a E ~b) = ~( (a E b) • (~a E ~c) ) ===== Минимизация не полностью определенных ФАЛ. ===== Иногда возникают ситуации, когда значение функции определено не на всех наборах переменных, тогда в таблице истинности это указывается «*», которая в последствии может быть заменена либо на 0 либо на 1 (как удобнее для минимизации). Например: функция принимает значение 1 на первых пяти наборах и 0 на шестом. ^ a ^ b ^ c ^ y ^ | 0 | 0 | 0 | 1 | | 0 | 0 | 1 | 1 | | 0 | 1 | 0 | 1 | | 0 | 1 | 1 | 1 | | 1 | 0 | 0 | 1 | | 1 | 0 | 1 | 0 | | 1 | 1 | 0 | 0 | | 1 | 1 | 1 | 0 | <рисунок х14> y = ~a E ~c. ===== Синтез комбинационных логических схем (КЛС). ===== КЛС называется схема, которая выполняет преобразования данных, поступающих на вход схемы в данный момент времени. На функциональных схемах КЛС обозначают: где n – длина слова (разрядность), поступающего на вход схемы, m – длина преобразованного слова на выходе схемы. В общем случае, работу КЛС можно описать след. формулой: В «есть» значение функции f1 от А в данный момент времени t. Другой тип схем цифровой техники – это схемы с памятью для запоминания предыдущего состояния устройства (последовательностные схемы). На структурных схемах они обозначаются так: В текущий момент времени Вt равно значению функции f2 от текущего состояния Аt и прошлого состояния устройства Мt-1. Все цифровые устройства представляют собой сочетание схем с памятью и КЛС. КЛС характеризуются двумя основными параметрами: быстродействие и затраты оборудования. Быстродействие КЛС характеризуется временем срабатывания логических элементов, входящих максимально длинную (по времени работы) цепочку элементов в КЛС. В данном примере, быстродействие схемы равно времени срабатывания 3х логических элементов: T = 3•tлє. <рисунок Быстродействие КЛС> Затраты оборудования обычно оцениваются либо ценой схемы по Квайну, либо корпусов интегральных микросхем (ИМС). Цена схемы по Квайну – это суммарное кол-во входов всех логических элементов, которые используются в КЛС. ===== Методика синтеза КЛС. ===== Обычно, синтез КЛС производят в следующем порядке: Строится таблица истинности, которая описывает ФАЛ или сумму ФАЛ, описывающих КЛС. По таблице истинности строится карта Карно и выполняется минимизация функции. По полученным формулам выполняют преобразование в заданный базис с учетом критериев быстродействия и/или затрат оборудования. Строится КЛС по полученным формулам. В зависимости от заданного базиса результат минимизации может быть: минимальная ДНФ, минимальная КНФ или минимальная инверсная функция. Если КЛС имеет выходов, которые описываются различными ФАЛ, то одинаковые элементы для разных ФАЛ могут быть использованы совместно. Пример синтеза преобразователя кодов из кода «421» в код «321»: a1 a2 a3 b1 b2 b3 0 0 0 0 0 0 0 1 0 0 1 0 0 1 2 0 1 0 0 1 0 3 0 1 1 1 0 0 4 1 0 0 1 0 1 5 1 0 1 1 1 0 6 1 1 0 1 1 1 7 1 1 1 * * * Реализация схемы в базисе И-НЕ. <Карты Карно для b1,b2,b3> b1 = a1 E (a2 • a3) = ~(~a1 • ~(a2 • a3)) b2 = a1 • a3 E a2 • ~a3 = ~( ~(a1 • a3) • ~(a2 • ~a3) ) b3 = a1 • ~a3 E ~a1 • ~a2 • a3 = ~( ~(a1 • ~a3) • ~(~a1 • ~a2 • a3) ) <схемы b1 & b2, b3> Как видно из приведенных выше схем, цена по Квайну K1=23, а быстродействие T1 = 3*tлэ. Часто в реальных схемах возникают ситуации, когда необходимо ограничить количество входов логических элементов. В этом случае можно применять закон двойной инверсии, которая ставится над необходимым количеством переменных в терме. Пример реализации заданной схемы (b3) в базисе 2И-НЕ: b3 = a1 • ~a3 E ~a1 • ~a2 • a3 = ~( ~(a1 • ~a3) • ~(~a1 • ~a2 • a3) ) ~(~a1 • ~a2 • a3) = ~( ~a1 • ~(~(~a2 • a3)) ) <схема b3 в 2И-НЕ> Для данной схемы T2 = 5*tлэ, К2 = 26. В некоторых случаях в схемах с несколькими выходами могут быть использованы общие элементы. В этом случае схема упрощается. Для этого можно использовать следующие формулы: a • ~b = a • ~(a • b) тогда: b2 = ~( ~(a1 • a3) • ~(a2 • ~(a2 • a3)) ) b3 = ~( ~(a1 • ~(a1 • a3)) • ~(~(a1 • a3) • ~(a2 • a3) • a3) ) <Схема b1 & b2 & b3> K3 = 19, T3 = 3*tлэ. ===== Реализация схем в базисе ИЛИ-НЕ. ===== Приведем формулу b1 в базис ИЛИ-НЕ: b1 = a1 E (a2 • a3) = ~(~( a1 E ~(~a2 E ~a3) )) В этом случае с целью повышения эффективности схемы лучше использовать минимальную КНФ. < карты Карно для b1,b2,b3> b1 = (a1 E a3) • (a1 E a2) = ~( ~(a1 E a3) E ~(a1 E a2) ) b2 = (a2 E a3) • (a1 E ~a3) = ~( ~(a2 E a3) E ~(a1 E ~a3) ) b3 = (a1 E a3) • (a1 E ~a2) • (~a1 E ~a3) = ~( ~( a1 E a3) E ~( a1 E ~a2) E ~(~a1 E ~a3) ) ===== Синтез КЛС в И-ИЛИ-НЕ. ===== При реализации КЛС в базисе И-ИЛИ-НЕ наиболее удобно использовать инверсные значения ФАЛ с последующим преобразованием, используя двойную инверсию, вынесение множества за скобку и закон Де-Моргана. Пример реализации преобразователя кода «421» в «321»: a1 a2 a3 b1 b2 b3 0 0 0 0 0 0 0 1 0 0 1 0 0 1 2 0 1 0 0 1 0 3 0 1 1 1 0 0 4 1 0 0 1 0 1 5 1 0 1 1 1 0 6 1 1 0 1 1 1 7 1 1 1 * * * <карты Карно для b1, b2, b3> ~b1 = ~a1 • ~a2 E ~a1 • ~a3; b1 = ~( ~a1 • ~a2 E ~a1 • ~a3 ) - ДНФ по нулям. ~b2 = ~a2 • ~a3 E ~a1 • a3; b2 = ~( ~a2 • ~a3 E ~a1 • a3 ) ~b3 = ~a1 • ~a3 E ~a1 • a2 E a1 • a3; b3 = ~( ~a1 • ~a3 E ~a1 • a2 E a1 • a3 ) = = ~( ~a1 • (~a3 E a2) E a1 • a3) = ~( ~(a1 E ~(~a3 E a2)) E a1 • a3 ) <схемы b1,b2,b3> Если необходимо выполнить минимизацию в заданном базисе, то удобнее это будет сделать, если: И-НЕ – минимальная ДНФ; ИЛИ-НЕ – минимальная КНФ; И-ИЛИ-НЕ – минимальная ДНФ «по нулям» (ДНФ инверсии ФАЛ). Использование предопределенных функций для минимизации. Если КЛС имеет несколько выходов, а следовательно, и несколько ФАЛ, то одна функция алгебры логики может быть использована для реализации другой. Рассмотрим данный метод на примере одноразрядного сумматора: <рисунки: пример сложения, схема n-разр. сумматора> a b c S P 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 1 1 1 <Карты Карно для S,P> S = ~a • ~b • c E ~a • b • ~c E a • ~b • ~c E a • b • c P = a • c E a • b E b • c Но если использовать следующую таблицу истинности, то получим интересный результат: a b c P S 0 0 0 0 0 0 0 0 1 * 0 0 1 0 1 0 0 1 1 * 0 1 0 0 1 0 1 0 1 * 0 1 1 0 * 0 1 1 1 0 1 0 0 0 1 1 0 0 1 * 1 0 1 0 * 1 0 1 1 0 1 1 0 0 * 1 1 0 1 0 1 1 1 0 * 1 1 1 1 1 <Карта Карно для S> S = c • ~P E b • ~P E a • ~P E a • b • c <схема сумматора>