Основы алгебры логики

Размещено на http://www.allbest.ru/

Введение

Курс «Цифровые устройства и микропроцессоры» состоит из двух относительно самостоятельных разделов. В разделе цифровых устройств рассматриваются базовые элементы цифровой техники, а в разделе микропроцессоров рассматривается микропроцессорные устройства, принципы их функционирования, программирование и средства проектирования на примере RISK-микроконтроллеров.

Для самостоятельной подготовки студентами по разделу цифровых устройств могут использоваться учебники [1, 2 и 3], на основе которых составлен данный цикл лекций.

Все цифровые устройства вычислительной техники строятся из логических элементов, напряжения на входах и выходах которых могут принимать конечное число значений в отличие от аналоговых устройств. Наиболее распространены двоичные логические элементы, напряжения в которых могут принимать только два значения. Одно значение считается логической единицей (“1”), а другое - логическим нулем (“0”). Одно логическое значение может соответствовать наличию напряжения, а другое его отсутствию, т.е. нулевому напряжению на проводе.

Логические устройства называют логическими автоматами. Логические автоматы бывают без памяти и с памятью. У первых выходные коды зависят только от текущих кодов на их входах. Такие автоматы называются комбинационными устройствами. Выходные коды логических автоматов с памятью зависят не только от текущих значений кодов на их входах, но и от тех значений входных кодов, которые были ранее. Т.е. автомат с памятью помнит предыдущие значения входных кодов и свое состояние. Чаще всего это запоминание происходит не в явном виде, а из-за того, что изменение состояний некоторых логических узлов зависит от их предыдущих состояний.

При проектировании логических устройств решаются две взаимообратные классические задачи: анализ и синтез. В первом случае исследуют поведение автомата, схема которого известна. Во втором - стремятся построить схему автомата по требуемой логике работы. В обоих случаях используют набор правил функционирования логических устройств. Эти правила называются алгеброй логики. Впервые они были предложены и исследованы ирландским математиком Дж. Булем в середине XIX века, поэтому часто их называют булевой алгеброй.

Курс лекций по цифровым устройствам составлен на основе [1].

1. Описание логических автоматов

логическая функция автомат

Логическая переменная y=f(x₀, x₁ ..., х_п) называется логической (булевой) функцией, если ее аргументы x₀, x₁ ..., х_п, и значения функции могут принимать только два значения: логического 0 и логической 1.

Для задания функции алгебры логики, как и любой другой функции необходимо поставить в соответствие значения функции для всех возможных комбинаций входных аргументов. Если число аргументов функции равно n, то число различных сочетаний (наборов) значений аргументов составляет 2ⁿ, а число различных функций n аргументов . Так при п = 1 число функций 2² = 4, при п = 2 число функций 2⁴ = 16, при п = 3 число функций 2⁸= 512.

Способы задания логических функций:

1. Неформальный. Взаимосвязь значений функции и ее аргументов описывается словесной формулировкой.

2. Табличный. При табличном способе строится таблица истинности, в которой приводятся все возможные сочетания значений аргументов и соответствующие значения логической функции. Так как число таких сочетаний конечно, таблица истинности позволяет определять значение функции для любых значений аргументов. В отличие от таблиц математических функций, которые позволяют задавать значения функции не для всех, а лишь для некоторых значений аргументов.

3. Цифровой. Функцию алгебры логики определяют в виде последовательности чисел (обычно десятичных). При этом последовательно расписывают числовые эквиваленты двоичных кодов, которые соответствуют единичным либо нулевым значениям функции.

4. Аналитический. Функция алгебры логики записывается в виде аналитического выражения, где показаны логические операции, выполняемые над аргументами функции.

2. Основные логические операции и элементы

Алгебра логики основывается на трех базовых логических операциях, с помощью которых можно реализовать любой логический автомат:

Логическое сложение (дизъюнкция). Называется также функцией ИЛИ. Она принимает единичное значение, когда хотя бы один из аргументов ИЛИ х₁, ИЛИ х₂ равен единице. В результате таблица истинности логического сложения имеет следующий вид:

Аналитически операция обозначается символом ? или символом + и описывается формулой

.

Логическое умножение (конъюнкция). По другому функция И принимает единичное значение, когда одновременно оба аргумента и x₁, и х₂ равны единице. В результате таблица истинности логического сложения имеет следующий вид:

Аналитически операция обозначается символом ? или символом умножения в виде точки, которая иногда просто опускается для упрощения записи. Эти варианты операции отражаются формулой

.

Инверсия, иначе называемая функцией Не принимает значения, противоположные аргументу х. Аналитически операция обозначается чертой над инвертируемой переменной

.

В цифровых устройствах техническую реализацию логических функций осуществляют устройства называемые логическими элементами. Логические элементы часто называются по выполняемым ими функциям. Если элемент выполняет сразу несколько функций, они записываются через тирэ. Условные графические обозначения (УГО) наиболее распространенных элементов НЕ, И, ИЛИ, И-НЕ, ИЛИ-НЕ, исключающее ИЛИ, исключающее ИЛИ- НЕ показаны на рис. 1.

Рис.1

УГО элементов цифровой техники строят на основе прямоугольника. Функциональное назначение указывают в верхней части основного поля. Входы изображают слева, они помечены буквами х, выходы у -- справа. Инверсные входы либо инверсные выходы обозначают кружочком.

В зарубежной литературе принято логические элементы обозначать в другом виде (рис. 2).

Рис.2

Практика показала нецелесообразность выпуска логических элементов, реализующих все возможные логические функции. Тем более что с ростом числа переменных число логических функций сильно возрастает. В дальнейшем будет показано, каким образом можно реализовать любую сложную логическую функцию, используя ограниченный набор элементарных логических функций.

3. Логические функции

Число переменных в логических функциях в принципе не ограничено, но в алгебре логики достаточно рассмотреть функции только одной и двух переменных. Функции большего числа переменных легко могут быть сведены и проанализированы через них.

Существует 4 функции одной переменной.

Таблица истинности для функций одной переменной

Функции одного аргумента имеют следующие аналитические записи и названия

f₀(x) = 0 -- константа нуля;

f₁ (x) = х -- повторение х;

f₂ (х) = -- отрицание х, НЕ, инверсия, читается «не x»;

f₃ (х) = 1 -- константа единицы.

Функции одной переменной f₀, f₁, f₃ не представляют интереса с точки зрения технической реализации. Практически применяется только функция f₂(x)= -- инверсия.

f_l (x_l,х₂) = х₁х₂ = х₁х₂ = x_l&x₂ -- логическое умножение, конъюнкция, логическое И;

f₂ (x_l,х₂) = х₁Дх₂ - x₁ запрет по х₂; x₁, но не x₂;

f₃ (x₁,х₂) = х₁ -- повторение x₁;

f₄ (x_l,х₂) = х₂Дх₁ - x₂ запрет по х₁; x₂, но не x₁;

f₅ (x₁,х₂) = х₂ -- повторение x₂;

f₆ (x_l,х₂) = х₁х₂ -- сложение по модулю 2, неравнозначность, исключающее ИЛИ;

f₇(x_1, x₂) = x₁+х₂ -- -- логическое сложение, дизъюнкция, логическое ИЛИ;

-- стрелка Пирса, отрицание ИЛИ; ИЛИ-НЕ;

-- равнозначность, эквивалентность, исключающее ИЛИ-НЕ;

f_l0(x₁ х₂)= --отрицание х₂;

-- импликация; если х₂, то х₁,

f_l2 (x₁ х₂) =х₁, -- отрицание x₁;

-- импликация; если x₁, то х₂; х₁ влечет х₂; х₁ имплицирует х₂.

-- штрих Шеффера, отрицание И; И-НЕ;

f₁₅ (x₁ х₂) = 1 -- константа 1.

Из функций двух переменных не имеют практического интереса f₀ (константа 0), f₃ (повторение x_t), f_s (повторение х₂), f_l5 (константа 1).

Логические функции одной и двух переменных называются элементарными. Они предполагают проведение только одной логической операции.

Литература:

Для самостоятельной подготовки студентами по разделу цифровых устройств могут использоваться следующие учебники:

1. Цифровые устройства и микропроцессоры / Д.А. Безуглов, И.В. Калиенко. - Ростов н/Д.: Феникс, 2006. - 480с.;

2. Угрюмов Е.П. Цифровая схемотехника. СПб, БХВ-Петербург, 2010 - 798 с.

3. Цифровые устройства и микропроцессоры / А.В. Микушин, А.М. Сажев, В.И. Сединин. - СПб.: БХВ-Петербург,2010.- 832 с.: ил.

4. Цифровые устройства и микропроцессоры / А.К.Нарышкин. -М.: Изд.центр «Академия», 2006 -320с.

Размещено на Allbest.ru