30

но

но

но

или

Для обозначения конъюнкции используется знак "*" и записывается

Y=А*В

и

0 * 0 = 0

0 * 1 = 0

1 * 0 = 0

1 * 1 = 1

Логическое отрицание.

Присоединение частицы "НЕ" к сказуемому данного простого высказывания А называется операцией логического отрицания. Операция логическое отрицание над высказыванием А записывается А. Возможные наборы значений и итогового высказывания Y можно изобразить с помощью таблицы 2.4, которая называется таблицей истинности.

Таблица 2.4

		Таблица истинности
А	Y = А		A	Y
истинно	ложно		1	0
ложно	истинно		0	1
		или

Логическое следование. Соединение двух высказываний в одно с использованием оборота речи "Если …, то…" называется операцией логического следования или импликацией. Операция импликации над высказываниями А и В записывается А → В (читается "А имплицирует В" или "В следует из А"). По определению импликацией называется сложное высказывание, которое ложно тогда и только тогда, когда А – истинно, а В – ложно. Рассмотрим пример с двумя высказываниями А и В. Тогда все возможные наборы их значений и итогового сложного высказывания Y можно изобразить с помощью таблицы 2.5, которая называется таблицей истинности.

						31
					Таблица 2.5
		Таблица истинности
А	В	Y=А→В		A	B	Y=А→В
истинно	истинно	истинно		1	1	1
истинно	ложно	ложно		1	0	0
ложно	истинно	истинно		0	1	1
ложно	ложно	истинно		0	0	1
			или

Эквивалентность.

Соединение двух простых высказываний А и В в одно с использованием оборота речи, или, как принято говорить, связки "…тогда и только тогда…", называется операцией эквивалентности. Многоточием помечены высказывания, над которыми проводится операция эквивалентности. Операция эквивалентности над высказываниями А и В записывается А~B (читается "А эквивалентно В"). Эквивалентностью называется сложное высказывание, которое истинно тогда и только тогда, когда А и В – одновременно истинны или ложны. Рассмотрим пример с двумя высказываниями А и В. Тогда все возможные наборы их значений и итогового сложного высказывания Y можно изобразить с помощью таблицы 2.6, которая называется таблицей истинности.

					Таблица 2.6
		Таблица истинности
А	В	Y=А~В		A	B	Y=А~В
истинно	истинно	истинно		1	1	1
истинно	ложно	ложно		1	0	0
ложно	истинно	ложно		0	1	0
ложно	ложно	истинно		0	0	1
			или

Три логические операции: дизъюнкция, конъюнкция и отрицание составляют "полную систему" – это значит, что любое логическое выражение можно составить с использованием только этих трех операций. Например, операцию импликации А→В можно заменить на 1-А+А*В, а операцию эквивалентность А~В заменить на 1-(А-В)2.

32

ОСНОВНЫЕ ЗАКОНЫ АЛГЕБРЫ ЛОГИКИ

Закон		Для ИЛИ		Для И
Переместительный
Сочетательный
Распределительный
Правила де Моргана
Идемпотенции
Поглощения
Склеивания
Операция переменной с
ее инверсией
Операция с
константами
Двойного отрицания

2. Логические элементы. Таблица истинности. Структурная формула. Функциональная схема.

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

Из этого следует два вывода:

33

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

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

Логический элемент

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

другие, а также триггер.

Чтобы представить два логических состояния – “1” и “0” в логических элементах, соответствующие им входные и выходные сигналы имеют один из двух установленных уровней напряжения: +5 вольт и 0 вольт.

Высокий уровень обычно соответствует значению “истина” (“1”), а низкий – значению “ложь” (“0”).

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

Рассмотрим некоторые логические элементы.

Логический элемент ИЛИ, выполняет логическое сложение (дизъюнкция), имеет не менее 2-х входов и один выход.

Схема элемента и таблица истинности.

34

Работа логического элемента описывается таблицей истинности. Таблица истинности

– это табличное представление логической схемы (операции), в котором перечислены все возможные сочетания значений истинности входных сигналов (операндов) вместе со значением истинности выходного сигнала (результата операции) для каждого из этих сочетаний. Она содержит n+1 столбец (где n – количество входов (аргументов) и один выход (функция)) и 2n строк. Чтобы ее построить, мы должны перечислить все возможные комбинации сигналов, которые можно подать на входы. Их будет 2n. Если 2 входа, то комбинаций 4, если 3 входа, то комбинаций 8. На выходе логического элемента ИЛИ будет ноль тогда и только тогда, когда на всех входах нули.

Например, дверь имеет несколько замков. Закрытый замок будем обозначать 1. Следовательно, дверь будет закрыта, если закрыт хотя бы 1 замок.

Логический элемент И, выполняет логическое умножение (конъюнкция), имеет не менее 2-х входов и один выход.

Схема элемента и таблица истинности.

На выходе логического элемента И будет единица тогда и только тогда, когда на всех входах будут 1

Логический элемент НЕ, выполняет логическое отрицание, имеет один вход и один выход. Схема элемента и таблица истинности.

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

35

Логические элементы И–НЕ, ИЛИ–НЕ получим из элементов И и ИЛИ, сделав отрицание выходного сигнала.

Приведенные логические схемы как отдельные устройства в современной вычислительной технике вы не встретите. Элементной базой ЭВМ стали интегральные схемы, которые в одном корпусе содержат набор устройств.

Схема, состоящая из логических элементов, называется функциональной.

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

Триггер – простейший цифровой автомат с памятью (изобретен в 1918 году БончБруевичем, руководителем Нижегородской лаборатории связи). Эта электронная схема, широко применяемая в регистрах компьютера для надёжного запоминания одного разряда двоичного кода. Триггер имеет два устойчивых состояния, одно из которых соответствует двоичной единице, а другое– двоичному нулю.

Термин триггер происходит от английского слова trigger – защёлка, спусковой крючок. Для обозначения этой схемы в английском языке чаще употребляется термин flip-flop, что в переводе означает "хлопанье". Это звукоподражательное название электронной схемы указывает на её способность почти мгновенно переходить ("перебрасываться") из одного электрического состояния в другое и наоборот.

Самый распространённый тип триггера – так называемый RS-триггер (имеет два входа S и R, соответственно, от английских set – установка, и reset – сброс и два выхода

прямой - Q и инверсный - ). Он сохраняет своё предыдущее состояние при нулевых входах, и меняет своё выходное состояние при подаче на один из его входов единицы. При подаче единицы на вход S (от английского Set - установить) выходное состояние становится равным логической единице. А при подаче единицы на вход R (от английского Reset - сбросить) выходное состояние становится равным логическому нулю. Обозначение триггера.

Реализацию триггера с помощью логических элементов ИЛИ–НЕ.

36

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

единичное. Выход Q – прямой, а – инверсный, т.к. на потенциал всегда соответствует состоянию, которое противоположно состоянию выхода Q.

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

Регистр – это устройство, представляющее собой отдельные ячейки внутренней быстродействующей памяти микропроцессора. Они используются для временного хранения единицы информации при обработке данных процессором. Количество триггеров в регистре определяет разрядность компьютера: 8-ми, 16-ти, 32-х разрядный компьютер.

Рассмотрим некоторые примеры.

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

1. Составим таблицу истинности и функциональную схему для структурной

формулы , которая содержит две переменные x и y. В первых двух столбцах таблицы запишем четыре возможных пары значений этих переменных, в последующих столбцах — значения промежуточных формул и в последнем столбце — значение формулы. В результате получим таблицу:

Переменные					Промежуточные логические формулы										Формула
0		0		1			0		0		1		1		1
0		1		1			1		1		0		1		1
1		0		0			0		1		0		0		1
1		1		0			0		1		0		0		1

Из таблицы видно, что при всех наборах значений переменных x и y формула принимает значение 1, то есть является тождественно истинной.

37

Функциональная схема.

2. Составим таблицу истинности и функциональную схему для структурной

формулы .

Таблица истинности.

Переменные				Промежуточные логические формулы								Формула
0		0		0		1		1		0		0
0		1		1		0		0		0		0
1		0		1		0		1		1		0
1		1		1		0		0		0		0

Из таблицы видно, что при всех наборах значений переменных x и y формула принимает значение 0, то есть является тождественно ложной.

Функциональная схема.

38

3. Таблица истинности для структурной формулы :

	Переменные							Промежуточные логические формулы										Формула
0			0			0		1		1		0		1		0		0
0			0			1		1		1		0		1		1		1
0			1			0		0		0		1		1		0		1
0			1			1		0		0		1		1		1		1
1			0			0		1		1		0		0		0		0
1			0			1		1		1		0		0		0		0
1			1			0		0		1		0		0		0		0
1			1			1		0		1		0		0		0		0

Из таблицы видно, что формула в некоторых случаях принимает значение 1, а в некоторых — 0, то есть является выполнимой.

Функциональная схема: