DigitElectrLabsPart1 (1274907), страница 4
Текст из файла (страница 4)
Основные аксиомы и законы алгебры–логики0×A=01+A=11×A=A0+A=AA×A=AA+A=AA=AкоммутативностиA+B =B+AA×B =B×AассоциативностиA + B + C = A + (B + C)A × B × C = A × (B × C)дистрибутивностиA × (B + C) = (A × B) + (A × C)A + (B × C) = (A + B) × (A + C)дуальности (теоремы Де–Моргана) A + B = A × BA×B =A+BпоглощенияA+A×B =AA × (A + B) = AАксиомы (тождества)ЗаконыЗаконыЗаконыЗаконыЗаконыВ общем случае логические выражения являются функциями логических переменных A, B, C, . .
. , каждая из которых может принимать значения 0 или 1. Если имеютсяk логических переменных, то они образуют 2k возможных логических наборов из 0 и 1.При k = 1: A = 0 или A = 1; При k = 2: AB = 00, 01, 10, 11 и т. д. Для каждого наборапеременных логическая функция F может принимать значения 0 или 1. Поэтому дляkk переменных можно образовать lk = 22 различных логических функций.
Таким образом, при увеличении k число l растет чрезвычайно быстро: при k = 2 получим lk = 16;при k = 3 получим l3 = 256; при k = 4 получим l4 = 65536 и т. д.Следует отметить, что алгебраические выражения тождеств и законов в таблице 2.2заданы парами, и взаимной заменой операций И, ИЛИ и символов 0 и 1 из одного19выражения получается другое. Используя данные тождества и законы, можно получать новые логические выражения, а также доказывать справедливость тех или иныхзаконов на основании других.Например, с помощью второго закона дистрибутивности и тождества получаем соотношение:A + A · B = (A + A) · (A + B) = A + BИспользуя первый закон дистрибутивности, тождество, аксиому и закон коммутативности, получаем доказательство справедливости второго закона поглощения:A · (A + B) = A · A + A · B = A + A · B = A · (1 + B) = A.Применение данных тождеств и законов позволяет производить упрощение логических функций, т. е.
находить для них выражения, имеющие наиболее простую форму.Используя законы ассоциативности, любую логическую функцию многих переменных (k > 2) можно представить в виде комбинации функции двух переменных.kПолный набор 22 = 16 логических функций двух переменных дан в таблице 2.3.Каждая функция обозначает одну из 16 возможных логических операций над двумяпеременными A, B.Таблица 2.3.
Полный набор логических функций для двух переменныхABF0F1F2F3F4F5F6F7F8F9F10F11F12F13F14F15000000000011111111010000111100001111100011001100110011110101010101010101Условное обозначениеи алгебраическое выражениеF0 = 0F1 = A × BF2 = A × BF3 = AF4 = A × BF5 = BF6 = A ⊕ BF7 = A + BF8 = A ↓ BF9 = A ⊕ BF10 = BF11 = B → AF12 = AF13 = A → BF14 = A|B = A × BF15 = 1202.3Способы записи функций алгебры логикиРассмотрим некоторое логическое устройство, на входе которого присутствует некоторый n–разрядный двоичный код xn−1 , . .
. , x1 , x0 , на выходе соответственно m–разрядный двоичный код zm−1 , . . . , z1 , z0 , (рис. 2.1). Для того, чтобы описать поведение этойсхемы, необходимо определить зависимость каждой из m выходных переменных zi отвходного двоичного кода xn−1 , . . . , x1 , x0 .Рис. 2.1. Обобщенная схема логического устройстваЗависимость выходных переменных zi , выраженная через совокупность входных переменных xn−1 , . .
. , x1 , x0 с помощью операций алгебры–логики, носит название функции алгебры логики (ФАЛ). Иногда данную зависимость также называют переключательной функцией. Задать ФАЛ — это значит определить значения zi для всехвозможных комбинаций переменных xn−1 , . . . , x1 , x0 . Очевидно, что для n-разрядногодвоичного кода xn−1 , . . . , x1 , x0 существует 2n различных значений zi xn−1 , . . . , x1 , x0 .Функция называется полностью определенной, если заданы 2n ее значений.
Есличасть значений функции не задана, то она называется частично определенной илинедоопределенной.Иногда известно, что по условиям работы устройства появление некоторых входных кодов невозможно, и поэтому значения ФАЛ на этих кодах не задаются. При этомвозникают так называемые факультативные или необязательные значения функции, которые могут задаваться произвольными значениями. Входные коды, для которых ФАЛимеет факультативные значения, называются запрещенными.Устройства, поведение которых описывается при помощи ФАЛ, называют логическими.Для описания ФАЛ могут быть использованы различные способы. Основными изних являются: описание функции в словесной форме, в виде таблиц истинности, алгебраических выражений, последовательностей десятичных чисел и т.
д.2.3.1Словесное описание ФАЛДанный вид описания наиболее часто применяется для первоначального, исходного описания поведения логического устройства. Проиллюстрируем словесное описаниеФАЛ на примере.Пример 2.1 Логическая функция трех переменных равна единице, если хотя бы двевходные переменные равны единице.2.3.2Описание ФАЛ в виде таблицы истинностиТаблица, содержащая все возможные комбинации входных переменных xn−1 , .
. . , x1 , x0и соответствующие им значения выходных переменных zi , называется таблицей ис21тинности, или комбинационной таблицей. В общем случае таблица истинности содержит 2n строк и m + n столбцов. Проиллюстрируем построение таблицы истинностина примере.Пример 2.2 Составить таблицу истинности для ФАЛ из примера 2.1.Решение. Количество входных переменных n = 3, т.
о. строк будет — 23 = 8. Количествовыходных переменных m = 1, т. е. количество столбцов — m + n = 1 + 3 = 4. Составимтаблицу истинности (см. таблицу 2.4).Таблица 2.4. Таблица истинности для ФАЛ трех переменныхx2000011112.3.3x100110011x001010101z00010111Описание ФАЛ в виде алгебраического выраженияПри описании ФАЛ алгебраическим выражением используются две стандартныеформы ее представления.1.
Дизъюнктивная нормальная форма (ДНФ). ДНФ называется логическая суммаэлементарных логических произведений, в каждое из которых аргумент или егоинверсия входят один раз. Получена ДНФ может быть из таблицы истинности сиспользованием следующего алгоритма:• для каждого набора переменных, на котором ФАЛ равна единице, записываются элементарные логические произведения входных переменных, причемпеременные, равные нулю, записываются с инверсией. Полученные произведения называют конституентами единицы, или минтермами (m);• логически суммируются все конституенты единицы (минтермы).Пример 2.3 Записать ДНФ для ФАЛ, заданной в примере 2.2.Решение. Составим таблицу конституент единицы (минтермов) для ФАЛ, заданной в примере 2.2.Согласно приведенному выше алгоритму, используя минтермы из таблицы 2.5 иосновные аксиомы (тождества) алгебры-логики (табл.
2.2), получим:z (x2 , x1 , x0 ) = z0 m0 + z1 m1 + z2 m2 + z3 m3 + z4 m4 + z5 m5 + z6 m6 + z7 m7 == 0 · (x̄2 x̄1 x̄0 ) + 0 · (x̄2 x̄1 x0 ) + 0 · (x̄2 x1 x̄0 ) + 1 · (x̄2 x1 x0 ) + 0 · (x2 x̄1 x̄0 ) ++1 · (x2 x̄1 x0 ) + 1 · (x2 x1 x̄0 ) + 1 · (x2 x1 x0 ) == x̄2 x1 x0 + x2 x̄1 x0 + x2 x1 x̄0 + x2 x1 x0Дизъюнктивную нормальную форму, полученную суммированием конституент единицы (минтермов), называют совершенной дизъюнктивной нормальной формой(СДНФ).22Таблица 2.5.
Минтермы ФАЛ z(x2 , x1 , x0 )x200001111x100110011x001010101Минтермы(m) Значение функцииm0 = x2 x1 x0z0 = 0m1 = x2 x1 x0z1 = 0m2 = x2 x1 x0z2 = 0m3 = x2 x1 x0z3 = 1m4 = x2 x1 x0z4 = 0m5 = x2 x1 x0z5 = 1m6 = x2 x1 x0z6 = 1m7 = x2 x1 x0z7 = 12. Конъюнктивная нормальная форма (КНФ). КНФ называется логическое произведение элементарных логических сумм, в каждую из которых аргумент или егоинверсия входят один раз. Получена КНФ может быть из таблицы истинности сиспользованием следующего алгоритма:• для каждого набора переменных, на котором ФАЛ равна нулю, записываютэлементарные логические суммы входных переменных, причем переменные,значения которых равны единице, записывают с инверсией.
Полученные суммы называют конституентой нуля, или макстермами;• логически перемножают все конституенты нуля (макстермы).Пример 2.4 Записать KНФ для ФАЛ, заданной в примере 2.2.Решение. Составим таблицу конституент нуля (макстермов) для ФАЛ, заданнойв примере 2.2.Таблица 2.6. Макстермы ФАЛ z(x2 , x1 , x0 )x200001111x100110011x001010101Макстермы (M )M0 = x2 + x1 + x0M1 = x2 + x1 + x0M2 = x2 + x1 + x0M3 = x2 + x1 + x0M4 = x2 + x1 + x0M5 = x2 + x1 + x0M6 = x2 + x1 + x0M7 = x2 + x1 + x0Значение функцииz0 = 0z1 = 0z2 = 0z3 = 1z4 = 0z5 = 1z6 = 1z7 = 1Согласно приведенному выше алгоритму, используя макстермы из таблицы 2.6 иосновные аксиомы (тождества) алгебры-логики (табл.
2.2), получим:z (x2 , x1 , x0 ) = (z0 + M0 ) · (z1 + M1 ) · (z2 + M2 ) · (z3 + M3 ) · (z4 + M4 ) ×× (z5 + M5 ) · (z6 + M6 ) · (z7 + M7 ) == (x2 + x1 + x0 ) · (x2 + x1 + x̄0 ) · (x2 + x̄1 + x0 ) · (x̄2 + x1 + x0 )Конъюнктивную нормальную форму, полученную суммированием конституент нуля (макстермов), также называют совершенной конъюнктивной нормальной формой (СКНФ).23Рассмотренные методики позволяют получить математическую форму записи длясамой функции. Иногда удобнее применять не саму ФАЛ, а ее инверсию.
В этом случаепри использовании вышеописанных методик для записи СДНФ необходимо выбиратьнулевые, а для записи СКНФ - единичные значения функции.Пример 2.5 Для ФАЛ из примера 2.2 записать СДНФ и СКНФ инверсной функцией.Решение. Воспользовавшись таблицей 2.4, запишемСДНФ: z̄ (x2 , x1 , x0 ) = x̄2 x̄1 x̄0 + x̄2 x̄1 x0 + x̄2 x1 x̄0 + x2 x̄1 x̄0 .СКНФ: z̄ (x2 , x1 , x0 ) = (x2 + x̄1 + x̄0 ) · (x̄2 + x1 + x̄0 ) · (x̄2 + x̄1 + x0 ) · (x̄2 + x̄1 + x̄0 )2.3.4Описание ФАЛ в виде последовательностидесятичных чиселИногда для сокращения записи ФАЛ представляют в виде последовательности десятичных чисел. При этом последовательно записывают десятичные эквиваленты двоичных кодов соответствующих конституент единицы и нуля (минтермов и макстермов).Пример 2.6 Записать в виде последовательности десятичных чисел ФАЛ из примеров 2.3 и 2.4Решение.
В СДНФ из примера 2.3 первая конституента единицы (минтерм — x2 x1 x0 )соответствует двоичному коду 011 (табл. 2.5). Десятичный эквивалент этого кода равен3. Аналогично записываются все остальные конституенты:Xz (x2 x1 x0 ) =(3, 5, 6, 7).В СКНФ из примера 2.4 первая конституента нуля (макстерм — x2 + x1 + x0 ) соответствует двоичному коду 000 (табл. 2.6). Десятичный эквивалент этого кода равен 0.Аналогично записывают все остальные конституенты:Yz (x2 x1 x0 ) =(0, 1, 2, 4).2.3.5Кубические комплексыВ последнее время широкое распространение получило так называемое кубическоепредставление ФАЛ. Такое представление использует ограниченное число символов ипоэтому применяется при автоматизации процессов логического проектирования цифровых интегральных схем (ИС).Основой кубической формы является представление каждого набора входных переменных в качестве n–мерного вектора.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
