Глава 5. Логические основы компьютеров

Что такое алгебра логики?

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

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

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

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

Джордж Буль

Так, например, предложение " 6 — четное число " следует считать высказыванием, так как оно истинное. Предложение " Рим — столица Франции " тоже высказывание, так как оно ложное.

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

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

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

Алгебра логики рассматривает любое высказывание только с одной точки зрения — является ли оно истинным или ложным. Заметим, что зачастую трудно установить истинность высказывания. Так, например, высказывание " площадь поверхности Индийского океана равна 75 млн кв. км " в одной ситуации можно посчитать ложным, а в другой — истинным. Ложным — так как указанное значение неточное и вообще не является постоянным. Истинным — если рассматривать его как некоторое приближение, приемлемое на практике.

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

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

Так, например, из элементарных высказываний " Петров — врач ", " Петров — шахматист " при помощи связки " и " можно получить составное высказывание " Петров — врач и шахматист ", понимаемое как " Петров — врач, хорошо играющий в шахматы ".

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

Истинность или ложность получаемых таким образом составных высказываний зависит от истинности или ложности элементарных высказываний.

Чтобы обращаться к логическим высказываниям, им назначают имена. Пусть через А обозначено высказывание "Тимур поедет летом на море", а через В — высказывание "Тимур летом отправится в горы". Тогда составное высказывание "Тимур летом побывает и на море, и в горах" можно кратко записать как А и В. Здесь "и" — логическая связка, А, В — логические переменные, которые мoгут принимать только два значения — "истина" или "ложь", обозначаемые, соответственно, "1" и "0".

Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение:

НЕ Операция, выражаемая словом "не", называется отрицанием и обозначается чертой над высказыванием (или знаком ). Высказывание истинно, когда 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 — тесно связаны) и обозначается знаком . Высказывание ложно тогда и только тогда, когда А истинно, а В ложно.

Каким же образом импликация связывает два элементарных высказывания? Покажем это на примере высказываний: "данный четырёхугольник — квадрат" (А) и "около данного четырёхугольника можно описать окружность" (В). Рассмотрим составное высказывание , понимаемое как "если данный четырёхугольник квадрат, то около него можно описать окружность". Есть три варианта, когда высказывание истинно:

1. А истинно и В истинно, то есть данный четырёхугольник квадрат, и около него можно описать окружность;
2. А ложно и В истинно, то есть данный четырёхугольник не является квадратом, но около него можно описать окружность (разумеется, это справедливо не для всякого четырёхугольника);
3. A ложно и B ложно, то есть данный четырёхугольник не является квадратом, и около него нельзя описать окружность.

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

В обычной речи связка "если..., то" описывает причинно-следственную связь между высказываниями. Но в логических операциях смысл высказываний не учитывается. Рассматривается только их истинность или ложность. Поэтому не надо смущаться "бессмысленностью" импликаций, образованных высказываниями, совершенно не связанными по содержанию. Например, такими: "если президент США — демократ, то в Африке водятся жирафы", "если арбуз — ягода, то в бензоколонке есть бензин".

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

Высказывания А и В, образующие составное высказывание , могут быть совершенно не связаны по содержанию, например: "три больше двух" (А), "пингвины живут в Антарктиде" (В). Отрицаниями этих высказываний являются высказывания "три не больше двух" (), "пингвины не живут в Антарктиде" (). Образованные из высказываний А и В составные высказывания A B и истинны, а высказывания A и B — ложны.

Итак, нами рассмотрены пять логических операций: отрицание, конъюнкция, дизъюнкция, импликация и эквиваленция.

Импликацию можно выразить через дизъюнкцию и отрицание: А В = v В. Эквиваленцию можно выразить через отрицание, дизъюнкцию и конъюнкцию: А В = ( v В) ^. ( v А).

Таким образом, операций отрицания, дизъюнкции и конъюнкции достаточно, чтобы описывать и обрабатывать логические высказывания.

Порядок выполнения логических операций задается круглыми скобками. Но для уменьшения числа скобок договорились считать, что сначала выполняется операция отрицания ("не"), затем конъюнкция ("и"), после конъюнкции — дизъюнкция ("или") и в последнюю очередь — импликация.