Замена эквиваленции и импликации на конъюнкцию, дизъюнкцию и отрицание.

До сих пор мы занимались равносильными преобразованиями формул, не содержащих знаков импликации “® “ и эквиваленции “«“. Сейчас покажем, что всякую формулу, содержащую “® “ или “«“, можно заменить равносильной ей формулой, не содержащей этих знаков.
Имеют место следующие равносильности:
C ® U º UÚ U (1) C ® U º (2)
Докажем равносильности (1) и (2) с помощью таблицы истинности:

X	Y	X® U		Ú U

Сравнивая колонки 3 и 5, 3 и 8, убеждаемся, что равносильности (1) и (2) имеют место.

Эквиваленция выражается через конъюнкцию и импликацию:

C «U º (C ® U) × (U ® C) (3)
Из (3) и (1) получаем:
C «U º ( Ú U) × ( Ú C)º × Ú Y× Ú × XÚ C × U = × Ú C × U (4)
Эта равносильность выражает эквиваленцию через конъюнкцию, дизъюнкцию и отрицание.
Из равносильностей (3) и (2) получаем равносильность:
C «U = U (5),
выражающую эквиваленцию через конъюнкцию и отрицание.

Вывод:

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

Вопросы и задания.

1. Формулы данных высказываний преобразовать в эквивалентные, исключив логическое сложение:
а) ; б) ; в) .

2. Формулы данных высказываний преобразовать в эквивалентные, исключив логическое умножение.
а) ; б) ; в) .

3. Упростить:
а) ; б) .

4. Записать данные высказывания, используя только операции логического умножения и отрицания.
a) ; б) ; в) .

5. Записать данные высказывания, используя только операции логического сложения и отрицания.
а) ; б) ; в)

6. Упростить:
а) ; б) ; в) ;
г) ; д) ;
е) ; ж) ;
з) ; и) ;
й) .

7. Данные высказывания преобразуйте в эквивалентные, но не содержащие отрицаний сложных высказываний:
а) ; б) ; в) .

Логические основы построения ЭВМ

В основе обработки компьютером информации лежит алгебра логики, разработанная Дж. Булем. Было доказано, что все электронные схемы ЭВМ могут быть реализованы с помощью логических элементов И, ИЛИ, НЕ.

Элемент НЕ

A

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

Элемент ИЛИ

А	В	С

Функция “ИЛИ” - логическое сложение (дизъюнкция), ее результат равен 1, если хотя бы 1 из аргументов равен 1.
Здесь транзисторы включены параллельно друг другу. Если оба закрыты, то их общее сопротивление велико и на выходе будет сигнал низкого уровня (логический “0”). Достаточно подать сигнал высокого уровня (“1”) на один из транзисторов, как схема начнет пропускать ток, и на сопротивлении нагрузки установится также сигнал высокого уровня (логическая “1”).

Элемент И

A	B	C

Если на входы Вх1 и Вх2 поданы сигналы низкого уровня (логические “0”), то оба транзистора закрыты, ток через них не проходит, выходное напряжение на R_н близко к нулю.
Пусть на один из входов подано высокое напряжение (“1”). Тогда соответствующий транзистор откроется, однако другой останется закрытым, и ток через транзисторы и сопротивление проходить не будет. Следовательно, при подаче напряжения высокого уровня лишь на один из транзисторов, схема не переключается и на выходе остается напряжение низкого уровня.
И лишь при одновременной подаче на входы сигналов высокого уровня (“1”) на выходе мы также получим сигнал высокого уровня.

 

 

Структурные формулы и функциональные схемы логических устройств

 

Соответствующие схемы называются функциональными. Анализируя функциональную схему, можно понять, как работает логическое устройство, т.е. дать ответ на вопрос: какую функцию она выполняет.
Не менее важной формой описания логических устройств является структурная формула. Покажем на примере как выписывают формулу по заданной функциональной схеме.
Ясно, что элемент “И” осуществляет логическое умножение значений и В.
Над результатом в элементе “НЕ” осуществляется операция отрицания, т.е. вычисляется значение выражения:
Формула и есть структурная формула логического устройства.

 

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

 

 

 

Триггер

 

Триггер - это элементарный цифровой автомат, имеющий два устойчивых состояния равновесия (0 и 1), предназначенный для записи и хранения информации.
Под действием входных сигналов триггер может переключаться из одного устойчивого состояния в другое. Как, правило, триггер имеет 2 выхода: прямой и инверсный.
Q и .
Число входов зависит от выполняемых функций. По способу записи информации триггеры делятся на асинхронные и синхронные.
В асинхронных триггерах информация может изменяться в любой момент времени при изменении входных сигналов.
В синхронизирующих триггерах информация может меняться только в определенные моменты времени, задаваемые дополнительным синхронизирующим сигналом.
По функциональному построению различают схемы:
RS-, T-, D-, JK-триггеры
Асинхронный RS-триггер построен на 2-х логических элементах: ИЛИ - НЕ либо И – НЕ

 

Как он работает?
Пусть на вход элемента № 1 подан сигнал “1”, а на вход элемента № 3 - “0”. На выходе элемента № 1 независимо от того, какой второй сигнал поступит на вход, будет “1”, т.к. это элемент “ИЛИ” (по свойствам дизъюнкции). Пройдя через элемент № 2 сигнал примет значение “0” (Q=0). Следовательно, и на втором входе элемента № 3 установится сигнал “0”. На выходе элемента № 3 - “0”. Пройдя через элемент № 4 сигнал изменится на “1”. Следовательно, = 1.
Убедимся, что данное устройство сохраняет информацию. Запомните, что S=0, R=1, Q=0, =1.
В момент прекращения входных сигналов (S=0, R=0) на выходе =1. Это напряжение подается на вход элемента № 1. На выходе элемента № 1 сохраняется “1”, и на Q - сигнал “0”. На входах элемента №3 - “0”, следовательно =1.

Таким образом, при отсутствии на внешних входах сигналов “1” триггер поддерживает постоянное напряжение на своих выходах. Чтобы изменить напряжение на выходах триггера, надо подать сигнал “1” на вход элемента № 3. Тогда Q=1, =0.

Вход	Выход	Режим
S	R	Q		Работы
				Хранение
				Запись 1
				Запись 0
		Х	Х	Запрещение ()

Cхема RS - триггера на элементах И - НЕ

Вход	Выход	Режим
S	R	Q		работы
				Хранение
				Запись 1
				Запись 0
		Х	Х	Запрещение ()

 

Сумматор

Узел ЭВМ выполняющий арифметическое суммирование кодов чисел, называется сумматором. Операция суммирования осуществляется в сумматорах поразрядно с использованием одноразрядных суммирующих схем. При этом в каждом разряде требуется выполнить сложение трех двоичных цифр данного разряда первого слагаемого Х_i цифры этого же разряда второго слагаемого Y_i и цифры переноса P_i из соседнего младшего разряда.
И тогда такое суммирование разбивают на две аналогичные операции: суммирование двух цифр слагаемых и суммирование полученного результата с переносом из соседнего младшего разряда. Каждая из этих операций выполняется схемой, называемой полусумматором.

Х I	Y i	S i	P i+1

В таблице приведена логика работы сумматора на два входа X _i и Y_i. На его выходах образуется сумма S_i данного разряда и осуществляется перенос Р_i+1 в следующий старший разряд. По таблице можно составить логическое выражение для суммы S_i и переноса Р _i+1:


Преобразуем выражение для суммы к виду:

На рисунке 11.1 приведены функциональная схема полусумматора, составленная в соответствии с полученными логическими выражениями, и условное обозначение его. Схема является комбинационной и реализуется на логических элементах.
Логика работы одноразрядного сумматора на три входа или полного сумматора приведена в таблице А, где Xi, Yi - суммируемые двоичные цифры в i-м разряде, Pi - перенос из младшего разряда, Si - образующаяся сумма данного разряда и осуществляет перенос Pi+1 в следующий старший разряд.

Таблица А.

Xi	Yi	Pi	SI	Pi+1

По таблице можно составить логические выражения:

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

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

Комбинационный сумматор можно реализовать также с использованием двух полусумматоров и логического элемента ИЛИ, как показано на рис.11.3.

В реальных электронных схемах сумматор изображается так.

рис.11.5.

Эта схема называется одноразрядным сумматором.

Число 1	Число 2	Ст.разряд	Мл.разряд
Вх.1	Вх.2	Вых.1	Вых.2

На рис.11.6. показано, как из N сумматоров можно составить устройство для сложения двух N-разрядных двоичных кодов, это схема многоразрядного сумматора.

Регистры

 

На рис.12.1. показана упрощенная схема регистра для записи чисел, имеющих 4 двоичных разряда.
Функциональный узел ЭВМ, состоящий из триггеров, предназначенный для запоминания многоразрядных кодов и выполнения над ними некоторых логических преобразователей называется регистром.
С помощью регистров можно выполнять следующие операции: установку, сдвиг, преобразование. Основными типами регистров являются параллельные и последовательные (сдвигающие).
Как происходит запись числа в регистр?
Каждая из входных схем “И” имеет 2 входа. Один из них - общий для всех (шина записи).
Если на шину записи подан “0”, то на всех схемах “И” также будет “0”. Однако, если на шину записи подается сигнал “1” - разрешение записи, то напряжение на выходах схем “И”, а, следовательно, и на S - входах триггеров, будет зависеть от того, какой сигнал поступает в этот момент на вторые входы схем “И”.
Если подать на шину записи последовательность 1001 (число 9), то первый и четвертый триггеры установятся в 1, а второй и третий - в 0.
Как только на шину считывания будет подан “1”, то на выходах схем “И” появится сигнал “1” в тех разрядах, в которых на основном выходе триггера была записана “1”.
В схемах реальных регистров используются и дополнительные выходы триггеров. На этих выходах создается так называемый обратный код.
Обратный код используется в ЭВМ для осуществления некоторых арифметических операций с двоичными числами.
Совокупность регистров, используемых ЭВМ для запоминания программы работы, исходных и промежуточных результатов называется оперативной памятью (ОП).
ОП содержит 2¹⁵ регистров = 32768

В ЭВМ применяются регистры 8, 16, 32, 48 и 64 разрядов.

Шифратор и дешифратор

 

Шифратор и дешифратор являются типовыми узлами ЭВМ.
Шифратор (кодер) преобразует единичный сигнал на одном из входов в n-разрядный двоичный код. Наибольшее применение он находит в устройствах ввода информации (пультах управления) для преобразования десятичных чисел в двоичную систему счисления. Предположим, на пульте десять клавиш с гравировкой от 0 до 9. При нажатии любой из них на вход шифратора подается единичный сигнал (Х₀,..., Х₉). На выходе шифратора должен появиться двоичный код (Y₀,..., Y₉) этого десятичного числа. Как видно из таблицы истинности (таблица В), в этом случае нужен преобразователь с десятью входами и четырьмя выходами.

Таблица В.

Входы	Выходы
X	Y3	Y2	Y1	Y0

На выходе Y₀ еденица должна появиться при нажатии любой нечетной клавиши Х₁, Х₃, Х₅, Х₇, Х₉, т.е. Y₀=X₁+X₃+X₅+X₇+X_9.

Y₁=X₂+X₃+X₆+X₇; Y₂=X₄+X₅+X₆+X₇; Y₃=X₈+X_9.

Cледовательно, для реализации шифратора понадобится четыре элемента ИЛИ: пятивходовый, два четырех входовых и двухвходовый (рис.13.1.)

Дешифратор (декодер) - это узел, преобразующий код, поступающий на его входы, а сигнал только на одном из его выходов. Дешифраторы широко применяются в устройствах управления, в системах цифровой индикации с газоразрядными индикаторами, для построения распределителей импульсов по различным цепям и т.д. Схема используется я перевода двоичных цифр в десятичные. Дешифратор двоичного n-разрядного кода имеет 2ⁿ выходов, т.к. каждому из 2ⁿ значений входного кода должен соответствовать единичный сигнал на одном из выходов дешифратора.
Таблица истинности для дешифратора трехразрядного двоичного кода десятичных цифр:

Таблица С.

Входы	Выходы (Y)
Х2	Х1	Х0

Логические функции, описывающие работу такого дешифратора:
Y₀= × ×
Y₁= × × X₀
.
.
.
Y₇=X₂× X₁× X₀
На рисунке 13.2. показаны функциональная схема и условное обозначение одноступенчатого дешифратора на 3 входа.

 

Счетчики

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

Цифры 1, 2, 4, 8, 16, 32 у Q показывают до какого значения может считать данная ступень счетчика. А общее число подсчитываемых счетчиком импульсов равно сумме чисел (1+2+4+8+16+32=63). 64-й импульс сбрасывает счетчик в начальное состояние. Рассмотрим схему счетчика по модулю 10, который считает импульсы от 0 до 9 (от 0000 до 1001).

D	C	B	A

Пусть в начальный момент состояния выходов счетчика соответствуют двоичному коду 0000 (счетчик очищен). При поступлении тактового импульса 1 на синхронный вход Т1.
Этот триггер переключается и возвращает Т1 в исходное состояние, что в свою очередь приводит к переключению триггера Т2 в состояние 1 на индикаторе 0010. Счет продолжается: срез сигнала на выходе каждого триггера запускает следующий триггер.