Информатика

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

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

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

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

Примеры:

Предложение «7 – нечётное число» следует считать высказыванием, так как оно истинное. Предложение «Лондон – столица Германии» тоже высказывание, так как оно ложное.

Не всякое предложение является логическим высказыванием. Высказываниями не являются, например, предложения «Студент первого курса» и «Математика – интересный предмет».

Первое предложение ничего не утверждает о студенте, а второе использует слишком неопределённое понятие «интересный предмет».

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

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

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

Алгебра логики рассматривает любое высказывание только с одной точки зрения – является ли оно истинным или ложным. Заметим, что зачастую трудно установить истинность высказывания.

Так, например, высказывание «Площадь поверхности Индийского океана равна 75 млн. кв. км» в одной ситуации можно посчитать ложным, а в другой – истинным. Ложным – так как указанное значение неточное и вообще не является постоянным. Истинным – если рассматривать его как некоторое приближение, приемлемое на практике.

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

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

Примеры:

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

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

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

Чтобы обращаться к логическим высказываниям, им назначают имена.

Пусть через А обозначено высказывание «Тимур поедет летом на море», а через В – высказывание «Тимур летом отправится в горы». Тогда составное высказывание «Тимур летом побывает и на море, и в горах» можно кратко записать как А и В. Здесь «и» – логическая связка, А, В – логические переменные, которые могут принимать только два значения – «истина» или «ложь», обозначаемые, соответственно, «1» и «0».

Часто используют следующие логические связки (логические операции):

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

Высказывание ложно тогда и только тогда, когда А истинно, а В ложно.

Пример.

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

Рассмотрим составное высказывание AB, понимаемое как «если данный четырёхугольник квадрат, то около него можно описать окружность». Есть три варианта, когда высказывание AB истинно:

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

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

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

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

Пример.

Высказывания «24 делится на 6 тогда и только тогда, когда 24 делится на 3», «23 делится на 6 тогда и только тогда, когда 23 делится на 3» истинны, а высказывания «24 делится на 6 тогда и только тогда, когда 24 делится на 5», «21 делится на 6 тогда и только тогда, когда 21 делится на 3» ложны.

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

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

Импликацию можно выразить через дизъюнкцию и отрицание:

АВ = A v В.

Эквиваленцию можно выразить через отрицание, дизъюнкцию и конъюнкцию:

АВ = (A v В) · (B v А).

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

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