Тема 4. Логические основы информатики

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

Алгебра логики возникла в середине ХIХ века в трудах английского математика Джорджа Буля. Ее создание представляло собой попытку решать традиционные логические задачи алгебраическими методами.

Что же такое логическое высказывание?

Логическое высказывание — это любoе повествовательное пpедлoжение, в oтнoшении кoтopoгo мoжно oднoзначнo сказать, истиннo oнo или лoжнo.

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

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

НЕ    Операция, выражаемая словом "не", называется отрицанием и обозначается чертой над высказыванием (или знаком ).   Высказываниеистинно, когда A ложно, и ложно, когда A истинно.   Пример. "Луна — спутник Земли" (А); "Луна — не спутник Земли" ().

И    Операция, выражаемая связкой "и", называется конъюнкцией (лат. conjunctio — соединение) или логическим умножением и обозначается точкой " ^. " (может также обозначаться знакамиили&). Высказывание А ^. В истинно тогда и только тогда, когда оба высказывания А и В истинны. Например, высказывание   "10 делится на 2 и 5 больше 3"   истинно, а высказывания     "10 делится на 2 и 5 не больше 3",     "10 не делится на 2 и 5 больше 3",     "10 не делится на 2 и 5 не больше 3"     —   ложны.

ИЛИ    Операция, выражаемая связкой "или" (в неисключающем смысле этого слова), называется дизъюнкцией (лат. disjunctio — разделение) или логическим сложением и обозначается знаком v (или плюсом). Высказывание А v В ложно тогда и только тогда, когда оба высказывания А и В ложны.   Например, высказывание   "10 не делится на 2 или 5 не больше 3"   ложно,     а высказывания "10 делится на 2 или 5 больше 3",   "10 делится на 2 или 5 не больше 3",   "10 не делится на 2 или 5 больше 3"     —   истинны.

ЕСЛИ-ТО   Операция, выражаемая связками   "если ..., то",  "из ... следует",  "... влечет ...",  называется импликацией (лат. implico — тесно связаны) и обозначается знаком . Высказываниеложно тогда и только тогда, когдаА  истинно,  а  В  ложно.

РАВНОСИЛЬНО   Операция, выражаемая связками "тогда и только тогда", "необходимо и достаточно", "... равносильно ...", называется эквиваленцией или двойной импликацией и обозначается знаком  или~.   Высказывание истинно тогда и только тогда, когда значенияА и В совпадают.       Например, высказывания     "24 делится на 6 тогда и только тогда, когда 24 делится на 3",    "23 делится на 6 тогда и только тогда, когда 23 делится на 3"   истинны,   а высказывания   "24 делится на 6 тогда и только тогда, когда 24 делится на 5",   "21 делится на 6 тогда и только тогда, когда 21 делится на 3"   ложны.

Логический элемент компьютера

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

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

Электронный элемент, реализующий логическую функцию, называется логическим элементом или

Логический элемент компьютера – это часть электронной логической схемы, которая реализует элементарную логическую функцию.

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

Логическими элементами компьютеров являются электронные схемы И, ИЛИ, НЕ, И-НЕ, ИЛИ-НЕ и др. (называемые также вентилями), а также триггер, регистр, сумматор.

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

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

Сумматор – это устройство, предназначенное для суммирования двоичных кодов.

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

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

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

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

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

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

Логические схемы И, ИЛИ, НЕ, И—НЕ, ИЛИ—НЕ

Схема И

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

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

Связь между выходом z этой схемы и входами x и y описывается соотношением: z = x . y (читается как "x и y"). Операция конъюнкции на структурных схемах обозначается знаком "&" (читается как "амперсэнд"), являющимся сокращенной записью английского слова and.

Схема ИЛИ

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

Условное обозначение на структурных схемах схемы ИЛИ с двумя входами представлено на рис. 2. Знак "1" на схеме — от устаревшего обозначения дизъюнкции как ">=1" (т.е. значение дизъюнкции равно единице, если сумма значений операндов больше или равна 1). Связь между выходом z этой схемы и входами x и y описывается соотношением: z = x v y (читается как "x или y").

Схема НЕ

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

Если на входе схемы 0, то на выходе 1. Когда на входе 1, на выходе 0. Условное обозначение на структурных схемах инвертора — на рисунке 3

Схема И—НЕ

Схема И—НЕ состоит из элемента И и инвертора и осуществляет отрицание результата схемы И. Связь между выходом z и входами x и y схемы записывают следующим образом:, гдечитается как "инверсия x и y". Условное обозначение на структурных схемах схемы И—НЕ с двумя входами представлено на рисунке 4.

Схема ИЛИ—НЕ

Схема ИЛИ—НЕ состоит из элемента ИЛИ и инвертора и осуществляет отрицание результата схемы ИЛИ. Связь между выходом z и входами x и y схемы записывают следующим образом: , где, читается как "инверсия x или y ". Условное обозначение на структурных схемах схемы ИЛИ—НЕ с двумя входами представлено на рис. 5.