Тема 2_ Арифметические и логические основы ЭВМ

Кафедра	Решение текстовых логических задач
информатики

УГАТУ

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

Задача. Алексей, Роман и Виктор увидели красивую девушку, и каждый их них сделал по два предположения:

Алексей: Эта девушка манекенщица и ей 23 года;

Виктор: Этой девушке всего 19 лет и она не манекенщица.

Роман: Эта девушка студентка и ей 21 год;

Девушка услышала их спор и заметила, что каждый из них прав только в одном из двух предположений. Кто эта девушка и сколько ей лет?

81

Кафедра	Решение
информатики

УГАТУ

Введем обозначения для простых высказываний:

Поскольку в высказываниях каждого молодого человека только одно предположение верно, то их можно записать в виде логических выражений с помощью операции ИСКЛЮЧАЮЩЕЕ ИЛИ:

Девушка - манекенщица

Алексей

M Л23 = M Л23 + M Л23

и ей 23 года

Девушке 19 лет и она

Виктор

M Л19 = M Л19 + M Л19

не манекенщица

Роман

Девушка - студентка и

C Л21 = C Л21 + C Л21

ей 21 год

82

Кафедра	Решение	УГАТУ
информатики

Каждое из данных высказываний равно истине, поэтому объединим их логической операцией конъюнкции:

(M Л23 + M Л23 ) (M Л19 + M Л19 ) (C Л21 + C Л21).

Преобразуем выражение, логически перемножив выражения:

(MЛ23MЛ19 + M Л23 M Л19 + M Л23 М Л19 + +MЛ 23МЛ19) (C Л21 + C Л21) =

(M Л23 Л19 + M Л23 Л19 ) (C Л21 + C Л21) =

M Л23 Л19 C Л21 +

М Л23 Л19 C Л21

+

Все

+

M Л23 Л19 C Л21

+

M Л23 Л19 C Л

21

=

помеченные

выражения

M Л23 Л19 C Л21.

ложны

Значение полученного логического выражения будет истинным только в том случае, если «Эта девушка студентка и ей 23 года».

83

Кафедра	Переключательные схемы
информатики

УГАТУ

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

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

Каждый переключатель имеет только два состояния: замкнутое и разомкнутое.

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

84

Кафедра	Переключательные схемы
информатики
					УГАТУ
Будем считать, что два переключателя Х и					X
связаны следующим образом, когда Х замкнут, то X
разомкнут, и наоборот.
Переключателю Х ставится в соответствие переменная х,
а переключателю		X	–	x
Всей переключательной схема ставится в соответствие
логическая переменная равная 1, если схема проводит ток, и 0
– если не проводит.
Эта переменная называется функцией проводимости, она
зависит от переменных, соответствующих всем переключателям
схемы.
					85
Кафедра	Переключательные схемы
информатики
					УГАТУ
Функции проводимости F некоторых переключательных схем
					86

Кафедра	Переключательные схемы
информатики
	УГАТУ
Пример
	87
Кафедра	Переключательные схемы
информатики
	УГАТУ
Две схемы называются равносильными, если через
одну из них проходит ток тогда и только тогда,
когда он проходит через другую (при одном и том
же входном сигнале).
Из двух равносильных схем более простой
считается та схема, функция проводимости
которой содержит меньшее число логических
операций или переключателей.
При рассмотрении переключательных схем
возникают две основные задачи: синтез и анализ
схемы.
	88

информатики	Переключательные схемы
Кафедра

УГАТУ

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

•составлению функции проводимости;

•упрощению этой функции;

•построению соответствующей схемы. Анализ схемы сводится к следующим этапам:

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

•получению упрощенной формулы.

89

Кафедра Переключательные схемы

информатики

УГАТУ

Пример

Здесь второе логическое слагаемое является отрицанием первого, а дизъюнкция переменной с ее инверсией равна 1.

Упрощенная схема

90

Кафедра	Логические схемы
информатики
		УГАТУ
Логическая схема – графическое представление
логической функции.
Схема строится из логических элементов и отрезков
прямых.
Логический элемент – это прямоугольник, в котором
ставится символ логической операции.
Указанные операции производятся над логическими
переменными на входе в прямоугольник (слева), а
результат операции передается на выход (справа).
Логическую схему можно интерпретировать как
электрическую цепь с преобразователями сигналов в виде
логических элементов. Соответствующие схемы
называются функциональными.
		91
Кафедра	Логические элементы
информатики
		УГАТУ
Наиболее популярные изображения базовых логических
элементов
		92

Кафедра	Логические элементы
информатики
	УГАТУ
Изображения основных логических элементов
	93
Кафедра	Логические элементы
информатики
	УГАТУ
Изображения основных логических элементов
	94

Кафедра	Логические элементы
информатики

УГАТУ

Любой логической функции можно поставить в соответствие некоторую функциональную схему и наоборот.

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

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

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

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

95

Кафедра	Построение логических схем
информатики	по заданной логической функции
		УГАТУ

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

Рекомендуется следующая последовательность действий:

-формируется таблица истинности, которую должна будет реализовать проектируемая функциональная схема;

-по таблице истинности составляется логическая функция, состоящая только из базовых логических операций;

-полученная логическая функция упрощается;

-по упрощенной логической функции строится функциональная логическая схема.

96

Кафедра	Логические элементы
информатики
			УГАТУ
Пример. Построить функциональную схему для функции
A B ( A + B)
	A B	A B
		A B ( A + B)
	A + B
			97
Кафедра	Построение логических схем
информатики	по заданной таблице истинности
			УГАТУ
Пример. Построить функциональную схему по таблице
истинности:	Решение.
	Составим логическую функцию
	по данной таблице истинности:
	A B C + A B C
Функциональная схема будет
иметь вид:
			98

Кафедра	Построение логической функции
информатики	по заданной логической схеме
			УГАТУ
Пример. Построить и проанализировать логическую функцию по заданной
схеме.
		Решение. Запишем логические
		выражения поэлементно слева
		направо и сверху вниз, упрощая
		их на каждом шаге:
	1.	A + B = A B (применили закон де Моргана)
	2.	A B;
	3.	A B A B = 1;
	4. A B + B = A + B + B = 1;
	5.	1 1 = 0
Получается, что данная логическая схема дает на выходе ложные значения при любых
комбинациях A и B, т.е. данная схема реализует функцию F ( A, B) = False.
			99
Кафедра	Логическая схема одноразрядного
информатики	двоичного сумматора
			УГАТУ
Построение логической схемы одноразрядного
двоичного сумматора, имеющего два входа (х1 и х2) и
два выхода (S и P).
1. Составим таблицу истинности сумматора
			100