Лекция 15. Логические основы компьютера

Логика – это наука о формах и способах мышления.

Понятие – это форма мышления, фиксирующая основные, существенные признаки объекта.

В жизни мы часто, сами того не замечая, используем логические зависимости в самых разных ситуациях. Примеры.

Привычная алгебра оперирует числами, а алгебра логики — собы­тиями. Алгебру логики иначе называют булевой (в честь ее создателя английского математика Джорджа Буля) или алгеброй высказываний.

Чтобы понимать дальнейшее, вы должны узнать одно очень по­лезное правило — любая формальная математическая система в общем случае состоит из следующих основных множеств:

• операндов (данных для обработки, или, иными словами, информа­ции);

• операций (операторов или действий над информацией);

• постулатов (законов, правил, теорем, аксиом, формул, по которым осуществляется процесс обработки информации).

Этому правилу подчиняется и алгебра логики. Нас будет интере­совать так называемый двузначный вариант алгебры логики, которая в качестве множества элементов содержит два элемента «0» и «1». Будем называть их константами алгебры логики, и, чтобы не путать с двоичными цифрами, говорить о логическом «0» (Ложь) и логической «1» (Истина). Именно по причине использования этих двух констант алгебру логи­ки еще называют переключательной алгеброй, поскольку типовой пере­ключатель имеет два фиксированных положения.

Условимся, что если некоторое событие А произошло, то это за­писывается как А = 1, а если оно не произошло, то А = 0. В любом случае

А = 0, если А ≠ 1;

А = 1, если А ≠ 0.

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

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

Логическое умножение (конъюнкция) или операция И. Давайте сначала попробуем разобраться, что называется «на пальцах». Пред­ставьте себе елочную гирлянду из 10 лампочек, которые включены последовательно. Если хотя бы одна лампочка перегорит, то ток пре­кратится и гирлянда гореть не будет. Следовательно, событие А (гир­лянда горит) наступит тогда и только тогда, когда произойдут события В_ь В₂, В₃,..., B₁₀, где соответственно В₁, — исправность первой лампоч­ки, В₂ — второй и т.д. Сколько может быть комбинаций различных состояний? Мы с вами уже знаем, как это определить. Каждый элемент (лампочка) может иметь два состояния (исправна-неисправна), а все­го таких элементов 10, следовательно, количество комбинаций опреде­лим как

2¹⁰= 1024.

Иными словами, из 1 024 комбинаций событий «исправна-неис­правна лампочка» только при одной комбинации, когда все лампочки исправны, т.е. B₁ = 1, В₂ = 1, В₃= 1,..., В₁₀= 1, произойдет событие А, т.е. А = 1, — гирлянда будет гореть. Во всех остальных 1023 случаях, если хотя бы одно из событий В₁, В₂,..., B₁₀ не наступит, т.е. будет равным 0, гирлянда гореть не будет, — событие А не наступит, т. е. А = 0.

Другой пример. Думаем, что вы согласны с тем, что урок информа­тики в вашей группе (событие S) состоится, если произойдет событие А (пришел класс) и произойдет событие В (пришел учитель). Очевид­но, что S — это событие-функция, наступление которого зависит от наступления событий А и В (события аргументы). Сколько может быть комбинаций значений событий аргументов и, соответственно, значений события-функции? Конечно, четыре.

Обобщая, можно сказать, что событие S произойдет только в том случае, если произойдут и событие А, и событие В. Во всех остальных случаях оно не произойдет. Вот почему логическое умножение иногда называют операцией И. Эту операцию обозначают символом «&», «^», а иногда и символом «*».

Запишем таблицу значений логической функции S = А*В (табл. 3.3).

Если мы рассмотрим логическое выражение А = В*С*D*Е*F, то нетрудно сообразить, что общее количество комбинаций значений логических операндов В, С, D, Е, Сбудет равно 32, но только в одном случае, когда все они будут равны 1, значение логической функции А будет 1, во всех остальных 31 случаях А = 0.

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

в конъюнктивных формах значение логической функции равно 1 только в одном случае — когда все логи­ческие операнды равны 1, во всех остальных случаях значение логи­ческой функции равно 0. Эта закономерность очень пригодится нам при упрощении сложных логических вы­ражений.

Действительно, стоит убедиться, что один из операндов конъюнктивной формы равен 0, и дальше можно не счи­тать, а быть уверенным, что и значение логической функции равно 0.