| [ следующий ] [ начало главы ] [ предыдущий ] | [ содержание ] |
5.1. Что такое алгебра логики?
| Алгебра логики — это раздел математики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности) и логических операций над ними. |
Алгебра логики возникла в середине Х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 — тесно связаны) и
обозначается знаком 
.
Высказывание 
ложно
тогда и только тогда, когда А
истинно, а В ложно.
Каким же образом импликация связывает
два элементарных высказывания? Покажем
это на примере высказываний: "данный
четырёхугольник — квадрат" (А) и "около
данного четырёхугольника можно описать
окружность" (В). Рассмотрим
составное высказывание ,
понимаемое как "если данный
четырёхугольник квадрат, то около него
можно описать окружность". Есть три
варианта, когда высказывание
истинно:
- А истинно и В истинно, то есть данный четырёхугольник квадрат, и около него можно описать окружность;
- А ложно и В истинно, то есть данный четырёхугольник не является квадратом, но около него можно описать окружность (разумеется, это справедливо не для всякого четырёхугольника);
- 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 А). |
Таким образом, операций отрицания, дизъюнкции и конъюнкции достаточно, чтобы описывать и обрабатывать логические высказывания.
Порядок выполнения логических операций задается круглыми скобками. Но для уменьшения числа скобок договорились считать, что сначала выполняется операция отрицания ("не"), затем конъюнкция ("и"), после конъюнкции — дизъюнкция ("или") и в последнюю очередь — импликация.
