Алгебра логики и двоичное кодирование

⇐ ПредыдущаяСтр 12 из 13Следующая ⇒

С помощью математического аппарата алгебры логики очень удобно описывать работу компьютера. Сходство очевидно: при обработке данных используется двоичная система счисления (алфавит состоит из двух символов «0» и «1»), логические переменные могут принимать два значения: «0» и «1».

Следовательно:

– устройства компьютера могут применяться как для хранения и обработки числовой информации, представленной в двоичной системе счисления, так и логических переменных;

– при разработке аппаратного обеспечения компьютера, алгебра логики позволяет упростить логические функции, которые описывают структурные схемы компьютера. А значит, уменьшить число логических элементов, из которых состоят основные узлы компьютера (их количество исчисляется десятками тысяч).

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

Логические элементы компьютера

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

Логическими элементами компьютеров являются электронные схемы И, ИЛИ, НЕ, И–НЕ, ИЛИ–НЕ и другие (называемые вентилями), а также триггер.

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

Чтобы представить два логических состояния – «1» и «0» в вентилях, соответствующие им входные и выходные сигналы имеют один из двух установленных уровней напряжения. Например, +5 вольт и 0 вольт.

Высокий уровень обычно соответствует значению «истина» («1»), а низкий – значению «ложь» («0»).

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

Работу логических элементов описывают с помощью таблиц истинности.

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

Схема И

Схема И (конъюнктор) реализует конъюнкцию двух или более логических значений. Условное обозначение на структурных схемах схемы И с двумя входами представлено на рисунке 11.

Рисунок 11 – Схема И

Единица на выходе схемы И будет тогда и только тогда, когда на всех входах будут единицы. Когда хотя бы на одном входе будет ноль, на выходе также будет ноль.

Связь между выходом F этой схемы и входами x и y описывается соотношением:

F (x, y) = x ∙ y.

Схема ИЛИ

Схема ИЛИ (дизъюнктор) реализует дизъюнкцию двух или более логических значений. Когда хотя бы на одном входе схемы ИЛИ будет единица, на её выходе также будет единица.

Условное обозначение на структурных схемах схемы ИЛИ с двумя входами представлено на рисунке 12.

Рисунок 12 – Схема ИЛИ

Связь между выходом F(x, y) этой схемы и входами x и y описывается соотношением: F(x, y) = x v y.

Схема НЕ

Схема НЕ (инвертор) реализует операцию отрицания. Связь между входом x этой схемы и выходом F(x) можно записать соотношением

Если на входе схемы 0, то на выходе 1. Когда на входе 1, на выходе 0. Условное обозначение инвертора на структурных схемах приведено на рисунке 13.

Рисунок 13 – Схема НЕ

Схема И–НЕ

Схема И–НЕ состоит из элемента И и инвертора и осуществляет отрицание результата схемы И. Связь между выходом F(x,y) и входами x и y схемы записывают следующим образом: . Условное обозначение на структурных схемах схемы И–НЕ с двумя входами представлено на рисунке 14.

Рисунок 14 – Схема И–НЕ

Схема ИЛИ–НЕ

Схема ИЛИ–НЕ состоит из элемента ИЛИ и инвертора и осуществляет отрицание результата схемы ИЛИ. Связь между выходом F(x,y) и входами x и y схемы записывают следующим образом: . Условное обозначение на структурных схемах элемента ИЛИ–НЕ с двумя входами представлено на рисунке 15.

Рисунок 15 – Схема ИЛИ–НЕ

Переключательная схема

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

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

Каждый переключатель имеет только два состояния: замкнутое и разомкнутое. Переключателю Х поставим в соответствие логическую переменную х, которая принимает значение 1 в том и только в том случае, когда переключатель Х замкнут и схема проводит ток; если же переключатель разомкнут, то х равен нулю.

Будем считать, что два переключателя Х и связаны таким образом, что когда Х замкнут, то разомкнут, и наоборот. Следовательно, если переключателю Х поставлена в соответствие логическая переменная х, то переключателю должна соответствовать переменная .

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

Функции проводимости F некоторых переключательных схем приведены в таблице 16.

Таблица 16 – Функции проводимости переключательных схем.

Схема	Характеристика	F
	не содержит переключателей, проводит ток всегда	F = 1
	содержит один постоянно разомкнутый контакт	F = 0
	проводит ток, когда переключатель х замкнут, не проводит – когда х разомкнут	F(x) = x
	проводит ток, когда переключатель х разомкнут, и не проводит, когда х замкнут
	проводит ток, когда оба переключателя замкнуты
Схема	Характеристика	F
	проводит ток, когда хотя бы один из переключателей замкнут
	состоит из двух параллельных ветвей

Две схемы называются равносильными, если через одну из них проходит ток тогда и только тогда, когда он проходит через другую (при одном и том же входном сигнале).

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

При рассмотрении переключательных схем решаются две основные задачи: синтез и анализ схемы.

Синтез переключательной схемы – разработка схемы, условия работы которой заданы таблицей истинности или словесным описанием.

Синтез схемы осуществляется следующим образом:

1) на основе таблицы истинности составляется функция проводимости;

2) производится упрощение (минимизация) этой функции, которое сводится к упрощению соответствующей ей формулы на основании законов алгебры логики.

3) строится соответствующая схема.

Анализ схемы:

1) определяется значение функции проводимости схемы при всех возможных наборах входящих в нее переменных;

2) полученная формула упрощается.

Переключателям, соединенным параллельно, поставим в соответствие операцию дизъюнкции: ток в этой цепи будет протекать или при замкнутом переключателе А, или при замкнутом переключателе В, или при замкнутых переключателях А и В одновременно.

Переключателям, соединенным последовательно, поставим в соответствие операцию конъюнкции: ток в цепи будет течь только тогда, когда замкнуты оба переключателя: А и В.

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

Задача 4.7.2.1. Заполнить таблицу:

Переключательная техника	Алгебра логики
Переключатель
Переключатель замкнут
Переключатель разомкнут
Соединение
Последовательное соединение
Параллельное соединение
Состояние тока
Прохождение тока
Отключение тока

Решение:

Переключательная техника	Алгебра логики
Переключатель	A
Переключатель замкнут	A = 1
Переключатель разомкнут	A = 0
Соединение	F
Последовательное соединение	A ∙ B
Параллельное соединение	A v B
Состояние тока	значение
Прохождение тока	1
Отключение тока	0

Задача 4.7.2.2 Построить схему, содержащую 4 переключателя x, y, z, t. Схема должна проводить ток тогда и только тогда, когда замкнут контакт переключателя t и любой из трёх контактов.

Решение. В данном случае можно обойтись без построения таблицы истинности.

Очевидно, что функция проводимости имеет вид F(x, y, z, t) = t ∙ (x v y v z). В таком случае схема будет выглядеть так:

Задача 4.7.2.3 Построим схему с пятью переключателями, которая проводит ток в том и только в том случае, когда замкнуты ровно четыре из этих переключателей.

Решение:

Схема имеет вид:

Задача 4.7.2.4Найдем функцию проводимости схемы:

Решение. Имеется четыре возможных пути прохождения тока при замкнутых переключателях a, b, c, d, e: через переключатели a, b; через переключатели a, e, d; через переключатели c, d и через переключатели c, e, b.

Функция проводимости: F(a, b, c, d, e) = a ∙ b v a ∙ e ∙d v c ∙ d v c ∙e ∙ b.

Задача 4.7.2.5 Упростить переключательные схемы: