Логические основы вычислительных машин

 

 

 


Наряду с обработкой цифровой информации и выполнения арифметических операций в ЭВМ используется специальная математическая теория – алгебра логики. В алгебре логики или булевой алгебры13 для описания функционирования аппаратных средств компьютера используются логические переменные, которые принимают два значения – «истина» и «ложь». Т.е. алгебра логики оперирует с двоичными числами (0 – ложь, 1 - истина), а именно в двоичной системе счисления информация кодируется в ЭВМ. Поэтому одни и те же устройства, входящие в состав вычислительной машины могут использоваться как для преобразования цифровой информации, так и для обработки логических функций.

ПРИМЕЧАНИЕ

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

Алгебра логики оперирует с логическими высказываниями. Высказывание – любое предложение, в отношении которого имеет смысл утверждение о его истинности или ложности [4]. Высказывание бывает либо истинным, либо ложным, другого быть не может, т.е. нет одновременно истинного и ложного утверждения14 – закон исключенного третьего. Высказывания обозначаются строчными латинскими буквами – abc и.т.д.

Пример 2.22. Примеры высказываний

«В одном байте восемь бит» - истинное утверждение;

«^ Я читаю эту книгу летом» - утверждение истинно, если вы читаете эту книгу в июне, июле или августе (что скорее всего не так!) и ложно в течение любого другого календарного месяца;

«^ Астрахань – столица России» - утверждение ложно, хотя астраханцы очень обрадовались бы.

В булевой алгебре существуют простейшие операции, с помощью которых можно представить любую логическую функцию. К таким операциям относятся операция логического сложения15, обозначаемая «+» («»), логического умножения16, обозначаемая «·» («») и отрицания17, обозначаемая чертой над высказыванием. Существует также операция «исключающее ИЛИ» (XOR), которая выполняет сложение по модулю 2 (отрицание равнозначности). XOR используется при определении знака произведения (частного) двоичных чисел в примерах 2.20-2.21.

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

Пример 2.23. Примеры логических функций

 

Таблицы истинности элементарных операций представлены в табл. 2.3-2.6. ^ Таблица истинности – один из способов представления выходных значений элементарных операций и логических функций, в зависимости от комбинации входных сигналов.

Таблица 2.3. Таблица истинности элемента «ИЛИ»



a

0

0

1

1

b

0

1

0

1

a OR b

0

1

1

1

Таблица 2.4. Таблица истинности элемента «И»



a

0

0

1

1

b

0

1

0

1

a AND b

0

0

0

1

Таблица 2.5. Таблица истинности «НЕ»



a

0

1

NOT a

1

0

Таблица 2.6. Таблица истинности «исключающее ИЛИ»



a

0

0

1

1

b

0

1

0

1

a XOR b

0

1

1

0

Существует также словесное описание логических функций, например «конъюнкция» может быть описана так - значение выхода конъюнктора равно нулю, только когда оба входа равны нулю, в остальных случаях выход принимает значение единица. И, наконец, аналитическое описание функции – запись функции в виде логического выражения (см. пример 2.23).

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

Коммуникативный (переместительный).

 

Ассоциативный (сочетательный).

 

Дистрибутивный (распределительный).

 

Правило де Моргана.

 

Все элементарные операции, рассмотренные нами, имеют два входа и один выход. Число возможных комбинаций входных сигналов составляет 4, т.е. «0-0», «0-1», «1-0», «1-1». Это означает, что возможных комбинаций на выходе может быть 16, т.е. 2N, где 2 –число знаков (0 и 1), а N – число выходов.

Таблица 2.7. Элементарные логические операции (элементы с двумя входами)


Функция

Название функции

a

0

0

1

1

b

0

1

0

1

F1= a /\ b

Конъюнкция – логическое умножение (И)

0

0

0

1

F2= a \/ b

Дизъюнкция – логическое сложение

0

1

1

1

F3= a → b

Импликация х1 в х2

1

1

0

1

F4a ← b

Импликация х2 в х1

1

0

1

1

F5=a   b

Запрет х2

0

0

1

0

F6=a  b

Запрет х1

0

1

0

0

F7=a ~ b

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

1

0

0

1

F8=a b

Сложение по модулю 2

0

1

1

0

F9=a/b

И-НЕ – Штрих Шеффера

1

1

1

0

F10=a ↓ b

ИЛИ-НЕ – Стрелка Пирса

1

0

0

0

F11=a

Повторение х1

0

0

1

1

F12=b

Повторение х2

0

1

0

1

F13=1

Константа 1

1

1

1

1

F14=0

Константа 0

0

0

0

0

F15=a^

Инверсия х1- НЕ х1

1

1

0

0

F16=b^

Инверсия х2- НЕ х2

1

0

1

0

Все 16 возможных функций представлены в табл. 2.7.

 


Лекция добавлена 28.02.2013 в 03:24:27