Тема 3. Логические основы работы компьютера

Учебные вопросы:

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

Рекомендуемая литература:

1. Информатика: базовый курс: Учебник для студентов вузов, бакалавров, магистров, обучающихся по направлениям 552800, 65460 «Информатика и вычислительная техника»/ О.А. Акулов, Н.В. Медведев, –М.:Омега-Л,2004.–М.: Омега-Л, 2004. –с. 116-175

2.  Игошин В.И. Задачник-практикум по математической логике. Учебное пособие для студентов заочников физико-математических факультетов педагогических институтов. – М.: Просвещение, 1986.

3. Шауцукова Л.З. Учебное пособие для 10-11 кл. общеобразоват. учреждений. – 4-е изд. – М.: Просвещение, 2004. – 416 с.: ил

Алгебра логики

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

Для построения сложных высказываний вводятся определенные правила, которые называются операциями над высказываниями.

Отрицание

x
1	0
0	1

Конъюнкция  x × y (x Ù y)     " x и y "					Дизъюнкция x Ú y " x или y "
x	yY	x × y			x	y	x Ú y
0	0	0			0	0	0
0	1	0			0	1	1
1	0	0			1	0	1
1	1	1			1	1	1
Импликация x ® y " если x, то y "				Эквивалентность x º y " x тогда и только тогда, когда y "
x	Yy	x ® y		x		y	x º y
0	0	1		0		0	1
0	1	1		0		1	0
1	0	0		1		0	0
1	1	1		1		1	1

Логические функции

Всякую формулу логики высказываний можно рассматривать как некоторую функцию: каждая буква (высказывание) может принимать одно из двух значений "истина" или "ложь", при этом сложное высказывание, заданное этой формулой, также может быть истинным или ложным. Так, формула: ((x ® y) º )Ú(z × y) = f (x, y, z) выражает функцию от переменных x, y и z.

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

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

Пример 1: (x Ú ); x ® (y ® x); (x × ) ® (x × y).

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

Пример 2: (x × ); (x ® (y ® x)) º (y × ).

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

Пример 3: f = (x º y) ® (x × z) и g = ((x × ) Ú ( × y)) Ú (x × z).