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"

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

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

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

истинно, а высказывания
"10 делится на 2 и 5 не больше 3",
"10 не делится на 2 и 5 больше 3",
"10 не делится на 2 и 5 не больше 3"

ложны.

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

ложно, а высказывания
"10 делится на 2 или 5 больше 3",
"10 делится на 2 или 5 не больше 3",
"10 не делится на 2 или 5 больше 3"

истинны.

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

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

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


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

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

(5) Операция, выражаемая связками "тогда и только тогда", "необходимо и достаточно", "... равносильно ...", называется эквиваленцией или двойной импликацией и обозначается знаком « или ~ . Высказывание А « В истинно тогда и только тогда, когда значения А и В совпадают.

Например, высказывания
"24 делится на 6 тогда и только тогда, когда 24 делится на 3",
"23 делится на 6 тогда и только тогда, когда 23 делится на 3"

истинны, а высказывания
"24 делится на 6 тогда и только тогда, когда 24 делится на 5",
"21 делится на 6 тогда и только тогда, когда 21 делится на 3"

ложны.

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

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

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

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

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

Другие записи

10.06.2016. 5.8. Что такое сумматор?
Сумматор - это электронная логическая схема, выполняющая суммирование двоичных чисел. Сумматор служит, прежде всего, центральным узлом арифметико-логического устройства компьютера, однако он находит…
10.06.2016. 5.10. Как составить таблицу истинности?
Согласно определению, таблица истинности логической формулы выражает соответствие между всевозможными наборами значений переменных и значениями формулы. Для формулы, которая содержит две переменные,…
10.06.2016. 5.11. Как упростить логическую формулу?
Равносильные преобразования логических формул имеют то же назначение, что и преобразования формул в обычной алгебре. Они служат для упрощения формул или приведения их к определённому виду путем использования…
10.06.2016. 5.12. Что такое переключательная схема?
В компьютерах и других автоматических устройствах широко применяются электрические схемы, содержащие сотни и тысячи переключательных элементов: реле, выключателей и т.п. Разработка таких схем весьма…
10.06.2016. 5.13. Как решать логические задачи?
Разнообразие логических задач очень велико. Способов их решения тоже немало. Но наибольшее распространение получили следующие три способа решения логических задач:   средствами алгебры логики;…