Логические основы ЭВМ

Тождественные преобразования над высказываниями

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

Высказывания, образованные при помощи операций логического сложения, умножения и отрицания, называют сложными высказываниями. Истинность всякого сложного высказывания устанавливают с помощью таблиц истинности (табл. 1.1), которые содержат всевозможные комбинации значений входных переменных вместе с соответствующими им значениями выходных переменных.

Таблица 1.1

	Инверсия	Конъюнкция	Дизъюнкция	Импликация	Эквива-лентность	Неэкви-валентность
Отрицание	Умножение	Сложение	Следование	Равенство	Неравенство
NOT	AND & *	OR +			XOR
А	В		А Ù В	А Ú В	А Þ В	А Û В	А Å В

Например, истинность высказывания F=A& можно установить с помощью таблицы истинности 1.2.

Таблица 1.2

А	В	A&

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

Законы формальной логики, сформулированные Аристотелем:

· закон тождества: в ходе рассуждений истинностные значения высказываний не должны изменяться;

· закон противоречия: никакое высказывание не может быть истинным и ложным одновременно;

· закон исключенного третьего: каждое высказывание должно быть либо истинным, либо ложным.

Согласно закону двойного отрицании отрицать отрицание высказывания то же, что утверждать это высказывание:

Законы коммутативности (переместительный закон) и ассоциативности (сочетательный закон) конъюнкции и дизъюнкции аналогичны одноименным законам сложения и умножения чисел:

A & B = B & A или A * B = B * A

A Ú B = B Ú A или A + B = B + A

(A & B) & C = A & (B & C) или (A * B) * C = A * (B * C)

(A Ú B) Ú C = A Ú (B Ú C) или (A + B) + C = A + (B + C)

В силу законов идемпотентности в алгебре логики нет «показателей степеней» и «коэффициентов»; конъюнкция одинаковых «сомножителей» равносильна одному из них, дизъюнкция одинаковых «слагаемых» равносильна одному из них:

A & A = A или A * A = A

A Ú A = A или A + A = A

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

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

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

Инвентор (NOT)

И (AND)

ИЛИ (OR)

Исключающее ИЛИ (XOR)

И НЕ

Рис. 1.2

Таблица 1.8

Сигналы
Вход	Выход
А	В	И (AND) С = А * В	ИЛИ (OR) C = A + B	Исключающее ИЛИ (XOR) C = A Å B	И НЕ

Для хранения информации используются триггеры. Триггер – базовый элемент памяти, обладающий двумя устойчивыми состояниями. Это означает, что он может хранить один бит информации. Триггер строится на основе базовых логических элементов. Пример логической схемы триггера, построенного на базе логических элементов И НЕ, приведен на рис. 1.3.