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

Кафедра	Основные логические операции.				Кафедра	Основные логические операции.
информатики		Дизъюнкция			информатики	Строгая дизъюнкция
				УГАТУ						УГАТУ
					Описывается			Результатом операции будет:
					таблицей:
Описывается
		Результатом операции будет:
таблицей:								- ИСТИНА, если хотя бы одно из
		- ИСТИНА, если хотя бы одно из						высказываний истинно.
		высказываний истинно.						- ЛОЖЬ, тогда, когда оба
		- ЛОЖЬ, тогда и только тогда,						высказывания ложны или оба
								истинны;
		когда оба высказывания ложны;
Информатика	ФАТС – 2, 3	курс 1, заочники	семестр 1, 2010 г.	41	Информатика	ФАТС – 2, 3 курс 1, заочники		семестр 1,	2010 г.	42
Кафедра	Основные логические операции.				Кафедра	Основные логические операции.
информатики		Импликация			информатики	Импликация. Пример
				УГАТУ						УГАТУ
					Пример. Высказывание:
					«Если я завалю информатику, то летом никуда не поеду отдыхать».
						A			B
						A	B
					Ясно, что этот студент окажется лжецом только в одном случае: если он
					завалит информатику (A – ИСТИНА), а отдыхать все-таки поедет (B – ЛОЖЬ).
					Если же он информатику сдаст, но отдыхать не поедет, то во лжи его обвинить
					нельзя, т.к. обещание нигде не отдыхать он давал лишь при условии, что не
Описывается					сдаст информатику.
			Результатом операции будет
таблицей:
			ЛОЖЬ, тогда, когда значение
					В математических теоремах импликации формулируются в виде
			первого операнда истинно, а
					доказательства только необходимого или только достаточного условия, при
			второго – ложно.
					этом условие теоремы и заключение всегда связаны по содержанию.
Информатика	ФАТС – 2, 3	курс 1, заочники	семестр 1, 2010 г.	43	Информатика	ФАТС – 2, 3 курс 1, заочники		семестр 1,	2010 г.	44

Кафедра	Основные логические операции.			Кафедра		Основные логические операции.
информатики	Эквиваленция			информатики		Эквиваленция.	Пример
			УГАТУ						УГАТУ
				Пример. Преподаватель информатики утверждает, что он
				«Допустит студента до экзамена тогда и только тогда, когда он
						A
				защитит все лабораторные работы».			A	B
						B
Описывается
таблицей:		Высказывание является		Все возможные
		истинным тогда и только		значения такого
		тогда, когда оба		высказывания:
		высказывания
		одновременно истинны
		или одновременно
		ложны.
	Информатика ФАТС – 2, 3 курс 1, заочники	семестр 1, 2010 г.	45		Информатика	ФАТС – 2, 3 курс 1, заочники	семестр 1,	2010 г.	46
Кафедра	Основные логические операции			Кафедра	Основные логические операции
информатики			УГАТУ	информатики					УГАТУ
С помощью логических переменных и символов,				Для удобства и наглядности отражения сути логических
обозначающих логические операции любое				операций производимых над логическими переменными
высказывание можно формализовать, т.е. заменить				принято использовать таблицы истинности.
логической формулой.				В таблицах истинности записываются все возможные
Приоритеты выполнения логических операций в				сочетания значений логических переменных и
логических выражениях:				соответствующие им значения логической функции.
-	отрицание;			Сводная таблица истинности основных логических операций
-	логическое произведение;
-	логическое сложение, исключающее или;
-	импликация, эквиваленция.
Скобки меняют порядок выполнения операций.
	Информатика ФАТС – 2, 3 курс 1, заочники	семестр 1, 2010 г.	47		Информатика	ФАТС – 2, 3 курс 1, заочники	семестр 1,	2010 г.	48

Кафедра	Построение таблицы истинности		Кафедра	Построение таблицы истинности
информатики	для заданной логической функции		информатики	для заданной логической функции
		УГАТУ			УГАТУ
Для каждой логической функции Y = F(X1,X2,…,Xn)			Пример. Составить таблицу истинности для логической функции
можно построить таблицу истинности.				F ( A, B, C ) = (B or C ) and A
Количество строк в этой таблице будет равно числу			Количество строк, в таблице равно 8 (23), количество столбцов 3 + 3=6.
возможных комбинаций значений логических
переменных, т.е. 2N, где N – число логических
переменных, входящих в логическое выражение.
Количество столбцов в таблице истинности равно сумме
количества логических переменных и количества
логических операций в логическом выражении, т.е. N+M,
где M – число логических операций.
			Последняя колонка полученной таблицы является ответом на
			поставленную задачу.
	Информатика ФАТС – 2, 3 курс 1, заочники семестр 1, 2010 г.	49		Информатика ФАТС – 2, 3 курс 1, заочники семестр 1, 2010 г.	50
Кафедра	Таблицы истинности логических функций		Кафедра	Преобразование логических функций
информатики			информатики
		УГАТУ			УГАТУ
Логические выражения называются тождественно			Логические операции инверсии, конъюнкции и
истинными, если они имеют в таблице истинности			дизъюнкции называют базовыми. Любую функцию с
значения 1 для всех наборов значений входных			помощью тождественных преобразований можно
переменных.			представить таким образом, чтобы она содержала
			только базовые логические операции.
Логические выражения называются тождественно			Тождества, заменяющие операции «исключающее ИЛИ»,
ложными, если они имеют в таблице истинности
значения 0 для всех наборов значений входных			«импликации» и «эквиваленции» базовыми функциями:
переменных.
Логические выражения называются равносильными или
эквивалентными, если они имеют одинаковые значения
в таблице истинности для всех наборов значений
входных переменных.
	Информатика ФАТС – 2, 3 курс 1, заочники семестр 1, 2010 г.	51		Информатика ФАТС – 2, 3 курс 1, заочники семестр 1, 2010 г.	52

Кафедра	Основные законы алгебры логики			Кафедра		Основные законы алгебры логики
информатики				информатики
			УГАТУ					УГАТУ
Информатика		ФАТС – 2, 3 курс 1, заочники семестр 1, 2010 г.	53			Информатика	ФАТС – 2, 3 курс 1, заочники семестр 1, 2010 г.	54
Кафедра		КНФ и ДНФ		Кафедра			КНФ и ДНФ
информатики				информатики
			УГАТУ					УГАТУ
Форма представления логических функций, содержащая только три
основные логические операции: логическое отрицание, логическое
сложение и логическое умножение называется нормальной.				Любая логическая функция приводится к КНФ
Инверсия в нормальной форме представления должна быть только над
					или ДНФ с помощью следующего алгоритма:
переменными (не над выражениями!)
Выделяют две специальные нормальные формы представления логических				1.	избавляются от импликации и эвиваленции;
функций:
1. Конъюнктивно-нормальная форма (КНФ) – представление в виде				2.	избавляются от отрицаний над сложными
произведений суммы элементарных высказываний и их отрицаний					высказываниями;
(дизъюнкции конъюнкций).
Например:		F ( A, B, C) = ( A + B) ( A + B) (B + C + A)		3.	раскрывают скобки, применяя
2. Дизъюнктивно-нормальная форма (ДНФ) – представление в виде суммы					распределительный закон логики.
произведений элементарных высказываний и их отрицаний (конъюнкции
дизъюнкций).
Например:		F ( A, B, C) = A B C + A B + C A
Информатика		ФАТС – 2, 3 курс 1, заочники семестр 1, 2010 г.	55			Информатика	ФАТС – 2, 3 курс 1, заочники семестр 1, 2010 г.	56

Кафедра			КНФ и ДНФ			Кафедра	Построение логической функции
информатики						информатики
					УГАТУ		по заданной таблице истинности	УГАТУ
ПРИМЕР. Привести логическое высказывание						Минтермом называется терм-произведение, в котором каждая
(A → C ) and (B ↔ C )				к ДНФ		переменная встречается только один раз – либо с отрицанием, либо
						без него. Например, A B C
РЕШЕНИЕ						Логическую функцию по заданной таблице истинности
1.	Избавимся от импликации и эвиваленции:				=0	можно построить по следующему алгоритму:
( A → C) and (B ↔ C) = ( A + C) (B C + B C)						1. Для каждой строки таблицы истинности с единичным
2. Раскрываем скобки:						значением функции строится минтерм. Переменные,
						имеющие нулевые значения в строке, входят в минтерм
( A + C) (B C + B C) = A B C + C B + A B C + C B C						с отрицанием, а переменные со значением 1 – без
3. Преобразуем и получаем дизъюнктивную нормальную форму:						отрицания.
A B C + C B + A B C = B C ( A +1) + A B C = B C + A B C						2. Все полученные минтермы объединяются операцией
						дизъюнкция
		=1
	Информатика ФАТС – 2, 3		курс 1, заочники семестр 1, 2010 г.		57		Информатика ФАТС – 2, 3 курс 1, заочники семестр 1, 2010 г.	58
Кафедра		Построение логической функции				Кафедра	Построение логического выражения по
информатики		по заданной таблице истинности				информатики	условиям, заданным в виде текста
					УГАТУ			УГАТУ
ПРИМЕР. Восстановить						С помощью логических переменных и символов, обозначающих
						логические операции любое высказывание можно формализовать,
логическую функцию						т.е. заменить логической формулой.
трех переменных по
заданной таблице
истинности
Решение:
1. В таблице истинности находим строки, в которых F = 1.
Вторую строку описывает минтерм: not X1 and not X2 and X3.
Третью строку описывает минтерм: not X1 and X2 and not X3.
Шестую строку описывает минтерм: X1 and not X2 and X3.
2. Термы объединяем операцией дизъюнкция, получается логическое выражение
	F( X1 , X 2 , X 3 ) = X1 X 2 X 3 + X1 X 2 X 3 + X1 X 2 X 3
	Информатика ФАТС – 2, 3		курс 1, заочники семестр 1, 2010 г.		59		Информатика ФАТС – 2, 3 курс 1, заочники семестр 1, 2010 г.	60

Кафедра	Построение логического выражения по					Кафедра	Переключательные схемы
информатики	условиям, заданным в виде текста					информатики
					УГАТУ			УГАТУ
						В компьютерах и других автоматических устройствах
						применяются электрические схемы, содержащие тысячи
						переключательных элементов: реле. выключателей и т.п.
						Переключательная схема – это схематическое изображение
						некоторого устройства, состоящего из переключателей и
						соединяющих их проводников, а также входов и выходов, на
						которые подается и снимается сигнал.
		(	x ≤ 1) and (	y	≤ 1)	Каждый переключатель имеет только два состояния: замкнутое и
						разомкнутое.
						Переключателю Х ставится в соответствие логическая
						переменная х, которая принимает значение 1 в том и только в
						том случае, когда переключатель Х замкнут и схема проводит
						ток; если переключатель разомкнут, то х равна 0.
	Информатика	ФАТС – 2, 3 курс 1, заочники	семестр 1, 2010 г.		61	Информатика	ФАТС – 2, 3 курс 1, заочники семестр 1, 2010 г.	62
Кафедра		Переключательные схемы				Кафедра	Переключательные схемы
информатики						информатики
					УГАТУ			УГАТУ
Функции проводимости F некоторых переключательных схем						Пример
	Информатика	ФАТС – 2, 3 курс 1, заочники	семестр 1, 2010 г.		63	Информатика	ФАТС – 2, 3 курс 1, заочники семестр 1, 2010 г.	64

Кафедра	Переключательные схемы		Кафедра		Переключательные схемы
информатики			информатики
		УГАТУ				УГАТУ
Две схемы называются равносильными, если через			Синтез схемы по заданным условиям ее работы
одну из них проходит ток тогда и только тогда,				сводится к следующим этапам:
когда он проходит через другую (при одном и том			•	составлению функции проводимости;
же входном сигнале).			•	упрощению этой функции;
Из двух равносильных схем более простой
			•	построению соответствующей схемы.
считается та схема, функция проводимости
которой содержит меньшее число логических			Анализ схемы сводится к следующим этапам:
операций или переключателей.			• определению значения функции проводимости
При рассмотрении переключательных схем				схемы при всех возможных наборах входящих в эту
возникают две основные задачи: синтез и анализ				функцию переменных;
схемы.			•	получению упрощенной формулы.
Информатика	ФАТС – 2, 3 курс 1, заочники семестр 1, 2010 г.	65		Информатика	ФАТС – 2, 3 курс 1, заочники семестр 1, 2010 г.	66
Кафедра	Переключательные схемы		Кафедра		Логические схемы
информатики			информатики
		УГАТУ				УГАТУ
Пример			Логическая схема – графическое представление
				логической функции.
			Схема строится из логических элементов и отрезков
				прямых.
			Логический элемент – это прямоугольник, в котором
				ставится символ логической операции.
	Здесь второе логическое		Указанные операции производятся над логическими
	слагаемое является			переменными на входе в прямоугольник (слева), а
	отрицанием первого, а			результат операции передается на выход (справа).
	дизъюнкция переменной с ее
	инверсией равна 1.		Логическую схему можно интерпретировать как
				электрическую цепь с преобразователями сигналов в
	Упрощенная схема			виде логических элементов. Соответствующие схемы
				называются функциональными.
Информатика	ФАТС – 2, 3 курс 1, заочники семестр 1, 2010 г.	67		Информатика	ФАТС – 2, 3 курс 1, заочники семестр 1, 2010 г.	68

Кафедра	Логические элементы		Кафедра	Логические элементы
информатики			информатики
		УГАТУ			УГАТУ
Наиболее популярные изображения базовых логических			Изображения основных логических элементов
элементов
Информатика	ФАТС – 2, 3 курс 1, заочники семестр 1, 2010 г.	69	Информатика	ФАТС – 2, 3 курс 1, заочники семестр 1, 2010 г.	70
Кафедра	Логические элементы		Кафедра	Логические элементы
информатики		УГАТУ	информатики		УГАТУ
			Любой логической функции можно поставить в соответствие
Изображения основных логических элементов			некоторую функциональную схему и наоборот.
			Построение логических схем по заданной логической функции
			(синтез) является задачей проектирования функциональных
			схем.
			Задача проектирования функциональных схем возникает,
			например, при проектировании отдельных узлов
			компьютера, если имеется лишь описание алгоритма его
			работы.
			Построение логической функции по заданной логической схеме
			(анализ) является задачей анализа функциональных схем.
			Анализ функциональных схем дает возможность понять, как
			работает логическое устройство, т.е. дать ответ на вопрос:
			какую функцию оно выполняет.
Информатика	ФАТС – 2, 3 курс 1, заочники семестр 1, 2010 г.	71	Информатика	ФАТС – 2, 3 курс 1, заочники семестр 1, 2010 г.	72

Кафедра		Построение логических схем		Кафедра		Построение логических схем
информатики	по заданной логической функции			информатики	по заданной логической функции
			УГАТУ						УГАТУ
При решении задачи проектирования функциональных схем				Пример. Построить функциональную схему для функции
нужно стремиться к уменьшению числа используемых
базовых логических элементов, реализующих требуемую				A B ( A + B)
логическую функцию.							A B
								A B
Рекомендуется следующая последовательность действий:
- формируется таблица истинности, которую должна
будет реализовать проектируемая функциональная								A B ( A + B)
схема;
- по таблице истинности составляется логическая
функция, состоящая только из базовых логических
операций;
- полученная логическая функция упрощается;
- по упрощенной логической функции строится
функциональная логическая схема.						A + B
Информатика		ФАТС – 2, 3 курс 1, заочники семестр 1, 2010 г.	73		Информатика	ФАТС – 2, 3 курс 1, заочники семестр 1,		2010 г.	74
Кафедра		Построение логических схем		Кафедра	Построение логической функции
информатики	по заданной таблице истинности			информатики		по заданной логической схеме
			УГАТУ						УГАТУ
Пример. Построить функциональную схему по таблице				Пример. Построить и проанализировать логическую функцию по заданной
истинности:
		Решение.		схеме.			Решение. Запишем логические
		Составим логическую функцию					выражения поэлементно слева
		по данной таблице истинности:					направо и сверху вниз, упрощая
							их на каждом шаге:
		A B C + A B C				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.
Информатика		ФАТС – 2, 3 курс 1, заочники семестр 1, 2010 г.	75		Информатика	ФАТС – 2, 3 курс 1, заочники семестр 1,		2010 г.	76

Кафедра	Логическая схема одноразрядного					Кафедра	Логическая схема одноразрядного
информатики		двоичного сумматора				информатики		двоичного сумматора
					УГАТУ					УГАТУ
Построение логической схемы одноразрядного						2. По таблице истинности представим выходные
	двоичного сумматора, имеющего два входа (х1 и х2) и						функции S и P в виде ДНФ
	два выхода (S и P).							S = f1(x1 , x2 ) = x1x2 + x1 x2 ,
								P = f2 (x1 , x2 ) = x1x2
						3. По логическим функциям построим схему
1. Составим таблицу истинности сумматора
	Информатика	ФАТС – 2, 3 курс 1, заочники	семестр 1,	2010 г.	77		Информатика	ФАТС – 2, 3 курс 1, заочники семестр 1,	2010 г.	78
Кафедра
информатики
					УГАТУ
	Информатика	ФАТС – 2, 3 курс 1, заочники	семестр 1,	2010 г.	79