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

Кафедра	Основные логические операции.
информатики	Импликация. Пример
			УГАТУ
Пример. Высказывание:
«Если я завалю информатику, то летом никуда не поеду отдыхать».
	A	B
	A	B
Ясно, что этот студент окажется лжецом только в одном случае: если он
завалит информатику (A - ИСТИНА, а отдыхать все-таки поедет (B – ЛОЖЬ).
Если же он информатику сдаст, но отдыхать не поедет, то во лжи его обвинить
нельзя, т.к. обещание нигде не отдыхать он давал лишь при условии, что не
сдаст информатику.
В математических теоремах импликации формулируются в виде
доказательства только необходимого или только достаточного условия, при
этом условие теоремы и заключение всегда связаны по содержанию.
			61
Кафедра	Основные логические операции.
информатики	Эквиваленция
			УГАТУ
Описывается		Высказывание является
таблицей:		истинным тогда и только тогда,
		когда оба высказывания
		одновременно истинны или
		одновременно ложны.
			62

Кафедра	Основные логические операции.
информатики	Эквиваленция. Пример
		УГАТУ

Пример. Преподаватель информатики утверждает, что он

«Допустит студента до экзамена тогда и только тогда, когда он

A

защитит все лабораторные работы».

A B

B

Все возможные значения такого высказывания:

63

информатики	Основные логические операции
Кафедра

УГАТУ

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

Приоритеты выполнения логических операций в логических выражениях:

-отрицание;

-логическое произведение;

-логическое сложение, исключающее или;

-импликация, эквиваленция.

Скобки меняют порядок выполнения операций.

64

Кафедра	Основные логические операции
информатики

УГАТУ

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

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

Сводная таблица истинности основных логических операций

65

Кафедра Построение таблицы истинности для заданной

информатики

логической функции УГАТУ

Для каждой логической функции Y = F(X1,X2,…,Xn) можно построить таблицу истинности.

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

Количество столбцов в таблице истинности равно сумме количества логических переменных и количества логических операций в логическом выражении, т.е. N+M, где M – число логических операций.

66

Кафедра		Построение таблицы истинности для заданной
информатики		логической функции
			УГАТУ
Пример. Составить таблицу истинности для логической функции
		F ( A, B, C) = (B or C) and A
Количество строк, в таблице равно 8 (23), количество столбцов 3 + 3=6.
Последняя колонка полученной таблицы является ответом на
поставленную задачу.
			67
Кафедра		Таблицы истинности логических функций
информатики
			УГАТУ
Логические выражения называются тождественно
	истинными, если они имеют в таблице истинности
	значения 1 для всех наборов значений входных
	переменных.
Логические выражения называются тождественно
	ложными, если они имеют в таблице истинности
	значения 0 для всех наборов значений входных
	переменных.
Логические выражения называются равносильными или
	эквивалентными, если они имеют одинаковые
	значения в таблице истинности для всех наборов
	значений входных переменных.
			68

Кафедра
информатики
	Таблицы истинности логических функций
	УГАТУ
	69
Кафедра
информатикиПреобразование логических функций
	УГАТУ
Логические операции инверсии, конъюнкции и дизъюнкции
называют базовыми. Любую функцию с помощью
тождественных преобразований можно представить
таким образом, чтобы она содержала только базовые
логические операции.
Тождества, заменяющие операции «исключающее ИЛИ»,
«импликации» и «эквиваленции» базовыми функциями:
	70

Кафедра	Основные законы алгебры логики
информатики
	УГАТУ
	71
Кафедра	Основные законы алгебры логики
информатики
	УГАТУ
	72

Кафедра	КНФ и ДНФ	УГАТУ
информатики

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

Инверсия в нормальной форме представления должна быть только над переменными (не над выражениями!)

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

1. Конъюнктивно-нормальная форма (КНФ) – представление в виде произведений суммы элементарных высказываний и их отрицаний (дизъюнкции конъюнкций).

Например: F ( A, B, C) = ( A + B) ( A + B) (B + C + A)

2. Дизъюнктивно-нормальная форма (ДНФ) – представление в виде суммы произведений элементарных высказываний и их отрицаний (конъюнкции дизъюнкций).

Например: F ( A, B, C) = A B C + A B + C A

73

Кафедра	КНФ и ДНФ
информатики

УГАТУ

Любая логическая функция приводится к КНФ или ДНФ с помощью следующего алгоритма:

1.избавляются от импликации и эвиваленции;

2.избавляются от отрицаний над сложными высказываниями;

3.раскрывают скобки, применяя распределительный закон логики.

74

Кафедра

КНФ и ДНФ

информатики

УГАТУ

ПРИМЕР. Привести логическое высказывание

(A → C ) AND (B ↔ C ) к ДНФ

РЕШЕНИЕ

1. Избавимся от импликации и эвиваленции:

=0

( A → C) AND (B ↔ C) = ( A + C) (B C + B C)

2. Раскрываем скобки:

( A + C) (B C + B C ) = A B C + C B + A B C + C B C

3. Преобразуем и получаем дизъюнктивную нормальную форму:

A B C + C B + A B C = B C ( A +1) + A B C = B C + A B C

=1

75

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

Минтермом называется терм-произведение, в котором каждая переменная встречается только один раз – либо с отрицанием, либо

без него. Например, A B C

Логическую функцию по заданной таблице истинности можно построить по следующему алгоритму:

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

2.Все полученные минтермы объединяются операцией дизъюнкция

76

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

ПРИМЕР. Восстановить логическую функцию трех переменных по заданной таблице истинности

Решение:

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

77

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

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

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

2.Все полученные логические суммы (дизъюнкции) объединяются операциями конъюнкции.

Выбор способа построения логической функции зависит от количества 0 и 1: если в ней значительно больше 0, чем 1, то лучше строить дизъюнктивно-нормальную форму.

78

Кафедра	Построение логического выражения по
информатики	условиям, заданным в виде текста
		УГАТУ
С помощью логических переменных и символов, обозначающих
логические операции любое высказывание можно формализовать,
т.е. заменить логической формулой.
		79
Кафедра	Построение логического выражения по
информатики	условиям, заданным в виде текста
		УГАТУ
	( x ≤ 1) and ( y ≤ 1)
		80