Логические операции и базовые элементы компьютера

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

Схемные элементы ЭВМ. Преобразование информации в ЭВМ осуществляется элементами (схемами) двух классов:

  • • комбинационными;
  • • последовательностными (схемы с памятью).

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

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

Существует следующее определение — систему логических элементов, с помощью которых путем суперпозиции можно представить любую сколь угодно сложную комбинационную схему, называют функционально полной. Известны различные функционально полные системы элементов, но наибольшее распространение получили системы, использующие логические операции, выражаемые предлогами «НЕ», «И», «ИЛИ».

Логический элемент компьютера — это часть электронной схемы, которая реализует элементарную логическую функцию. Логическими элементами компьютеров являются электронные схемы «И», «ИЛИ», «НЕ», «И-НЕ», «ИЛИ-НЕ» или другие (называемые также вентилями), а также триггер. Можно показать, что с помощью этих схем можно реализовать любую логическую функцию, описывающую работу устройств компьютера. Обычно у вентилей бывает от двух до восьми входов и один или два выхода.

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

Рассмотрим логические операции и соответствующие им элементы логических схем.

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

Логическая схема «И» реализует конъюнкцию двух или более логических значений. Условное обозначение на структурных диаграммах схемы «И» с двумя входами представлено на рис. 1.9, а.

Таблица 1.14. Таблицы истинности конъюнкции и логической суммы высказываний

Конъюнкция

Дизъюнкция

А

В

А л В

А

В

А V В

А хог В

0

0

0

0

0

0

0

0

1

0

0

1

1

1

1

0

0

1

0

1

1

1

1

1

1

1

1

0

Единица на выходе схемы «И» будет тогда и только тогда, когда на всех входах будут единицы. Когда хотя бы на одном входе будет нуль, на выходе также будет нуль.

Связь между выходом I этой схемы и входами х и у описывается соотношением 1 = х&~у (читается как «х И у»). Операция конъюнкции на структурных схемах обозначается знаком «&».

Дизъюнкция. Объединение двух (или нескольких) высказываний с помощью союза или (сж) называется операцией логического сложения, или дизъюнкцией. Эту операцию обозначают знаками «|, V» или знаком сложения «+». Сложное высказывание Л V В истинно, если истинно хотя бы одно из входящих в него высказываний (см. табл. 1.14).

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

Схема «ИЛИ» реализует дизъюнкцию двух или более логических значений. Когда хотя бы на одном входе схемы «ИЛИ» будет единица, на ее выходе также будет единица.

Условное обозначение на структурных схемах схемы «ИЛИ» с двумя входами представлено на рис. 1.9, б. Знак «1» на схеме происходит от классического обозначения дизъюнкции как «>» (т. е. значение дизъюнкции равно единице, если сумма значений операндов больше или равна 1). Связь между выходом і этой схемы и входами х и у описывается соотношением: і = х/ у (читается как «х ИЛИ у»).

Х

*2

f = x і х2

X vy

а

X

У

X

X

V.

J

+ х2

X— >— / = х

X

У

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

Рис. 1.9. Схемные логические элементы вычислительных машин

Инверсия. Присоединение частицы не (not) к некоторому высказыванию называется операцией отрицания (инверсии) и обозначается А (или -,А). Если высказывание А истинно, то В ложно, и наоборот (табл. 1.15).

Таблица 1.15. Таблица истинности отрицания

А

А

0

1

1

0

Схема «НЕ» (инвертор) реализует операцию отрицания. Связь между входом х этой схемы и выходом 1 можно записать соотношением г=х, где х читается как «НЕ л» иди

«ИНВЕРСИЯ х».

Если на входе схемы «О», то на выходе «1», и наоборот. Условное обозначение на структурных схемах инвертора — на рис. 1.9, в.

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

Схема «И - Н Е» состоит из элемента «И» и инвертора и осуществляет отрицание результата схемы «И» (табл. 1.16). Связь между выходом і и входами х и у схемы записывают как х л у, или «ИНВЕРСИЯ х И у». Условное обозначение на структурных схемах схемы «И-НЕ» с двумя входами представлено на рис. 1.9, г.

Таблица 1.16. Таблица истинности схем «И-НЕ», «ИЛИ-НЕ»

Инверсия л: И у

Инверсиях ИЛИ у

X

У

X А у

X

У

X V у

0

0

1

0

0

1

0

1

1

0

1

0

1

0

1

1

0

0

1

1

0

1

1

0

Схема «ИЛИ-НЕ» состоит из элемента «ИЛИ» и инвертора и осуществляет отрицание результата схемы «ИЛИ» (табл. 1.16). Связь между выходом г и входами х и у схемы записывают как х V у, или «ИНВЕРСИЯ х ИЛИ у». Условное обозначение на структурных схемах схемы «ИЛИ-НЕ» с двумя входами представлено на рис. 1.9, д.

Схема «ИСКЛЮЧАЮЩЕЕ ИЛИ» (рис. 1.9, е) соответствует «сложению по модулю два». См. также табл. 1.14.

Следует отметить, что помимо операций и, или, НЕ в алгебре высказываний существует ряд других операций. Например, операция эквивалентности (эквиваленции) А~В (А = В, или А еяу В) (табл. 1.17).

Таблица 1.17. Таблицы истинности операций эквивалентности и импликации

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

Импликация

А

В

А~ В

А

В

А -> В

0

0

1

0

0

1

0

1

0

0

1

1

1

0

0

1

0

0

1

1

1

1

1

1

Другим примером может служить логическая операция импликации или логического следования (А -> В, A IMP В), иначе говоря, «ЕСЛИ А, то В» (табл. 1.17).

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

Таблица 1.18. Таблица истинности высказывания А а В

А

в

А

в

А а В

0

0

1

1

1

0

1

1

0

0

1

0

0

1

0

1

1

0

0

0

Высказывания, у которых таблицы истинности совпадают, называются равносильными. Для обозначения равносильных высказываний используют знак_«=» (А = В). Рассмотрим сложное высказывание (А л В) v л В) — табл. 1.19.

Если сравнить эту таблицу с таблицей истинности операции эквивалентности высказываний А и В (см. табл. 1.17), то можно увидеть, что высказывания (А л В) v (А л В) и А ~ В тождественны, т. е. ~ В) = л В) v (Л л В).

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

Свойства операций. Исходя из определений дизъюнкции, конъюнкции и отрицания, устанавливаются свойства этих one-

Таблица 1.19. Таблица истинности выражения л В) v л В)

А

А

в

в

А л В

А л В

л В) v(A л В)

0

1

0

1

0

1

1

0

1

1

0

0

0

0

1

0

0

1

0

0

0

1

0

1

0

1

0

1

раций и взаимные распределительные свойства. Приведем примеры некоторых из этих свойств:

• коммутативность (перестановочность):

А д В = В д А;

Av В = В v А;

• закон идемпотентности:

А л А — А, A v А = А;

• двойное отрицание:

А=А;

• сочетательные (ассоциативные) законы:

Av (В v С) = (A v В) v С = A v В v С;

А л (В л С) = (А л В) л С = А л 5 л С;

• распределительные (дистрибутивные) законы:

Л д v С) = д 5) v (>4 л С);

Л v а С) = (A v 5) л (A v С);

• поглощение:

A v (у! а 5) = Л;

Л л (Л v 5) = А;

  • • склеива н _и е:
    • л В) v (А л В) = В
    • (Av В) a (A v В) = В
  • • операция переменной с ее инверсией:

А а А = false;

A v А = true;

• операция с константами:

A a true =А, Av true = true;

A a false = false, /1 v false = Л;

  • • законы де Моргана:
    • 1. А а В = А у 5 (условно его можно назвать 1-й);
    • 2. Av В = А а В (2-й) — описывает результаты отрицания переменных, связанных операциями и, или.

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

В табл. 1.20 приведено доказательство истинности дистрибутивного закона. Аналогичным образом могут быть доказаны и другие тождества.

Таблица 1.20. Доказательство истинности дистрибутивного закона

А

в

с

В vC

А л(В vC)

А л В

А лС

(А л В) v (А л С)

0

0

0

0

0

0

0

0

0

0

1

1

0

0

0

0

0

1

0

1

0

0

0

0

0

1

1

1

0

0

0

0

1

0

0

0

0

0

0

0

1

0

1

1

1

0

1

1

1

1

0

1

1

1

0

1

1

1

1

1

1

1

1

1

На рис. 1.10, а—ж приведены иллюстрации к основным логическим операциям и их композициям (так называемые диаграммы Эйлера—Венна). В качестве высказывания А здесь принято утверждение х > а, в качестве В — у > Ь. На рис. 1.10, а приведены области истинности каждого из высказываний, здесь же становится понятен смысл дополнения (отрицания), объединения (дизъюнкции), пересечения (конъюнкции) и других операций. Первый из законов де Моргана иллюстрируется рис. 1.10, е, ж.

Побитовые операции. В ряде ЯП присутствуют операции побитового сравнения содержимого машинных слов (которые могут содержать числовые, строчные и др. данные), при этом каждый бит результата образуется в соответствии с табл. 1.21 (для бинар-

Некоторые примеры диаграмм Эйлера—Венна

Рис. 1.10. Некоторые примеры диаграмм Эйлера—Венна: а диаграмма Эйлера—Венна, иллюстрирующая расположение областей истинности высказываний А и В б — конъюнкция высказываний А и В (аыц); в — дизъюнкция высказываний А и В (оя); г — исключающая дизъюнкция (хсж); д — разность высказываний (А - В); е иллюстрация к законам де Моргана (дополнение пересечению высказываний); ж — иллюстрация к законам де Моргана

(объединение дополнений)

Таблица 1.21. Операнды и результаты некоторых операций побитового сравнения

X

У

х & у

X v у

х IMP у

х EQV у

х XOR у

0

0

0

0

1

1

0

0

1

0

1

1

0

1

1

0

0

1

0

0

1

1

1

1

1

1

1

0

ных операций). Унарная операция отрицания (NOT) в данном случае реализует очевидную замену «1» на «О» и наоборот.

 
< Пред   СОДЕРЖАНИЕ     След >