Алгебра логики

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Операция, выражаемая словом «не», называется   отрицанием и обозна­чается чертой над высказыванием (или знаком ┐).

Высказывание  истинно,  когда А ложно,  и ложно,  когда А истинно.   Например, «Луна» - спутник Земли» (А); «Луна» — не спутник Земли» ().

Операция, выражаемая связкой «и», называется конъюнкцией, (лат. conjunctio - соединение) или логическим умножением и обозначается точкой • (может обозначаться знаком ^ или &). Высказывание А•В истинно тогда и только тогда, когда оба высказывания А и В истинны.

Например, высказывание «10 делится на 2 и 5 больше 3» истинно, а высказывания «10 делится на 2 и 5 не больше 3», «10 не делится на 2 и 5 больше 3», «10 не делится на 2 и 5 не больше 3» ложны.

Операция, выражаемая связкой «или» (в неразделительном, не исключающем смысле этого слова), называется дизъюнкцией (лат. disjunctio - разделение) или логическим сложением и обозначается знаком «v» (или плюсом).

Высказывание AvB ложно тогда и только тогда, когда оба высказывания А и В ложны. Например, высказывание «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».

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

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

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

А→В= vB.

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

A↔B = (vB)•(vA).

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

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

Что такое логическая формула?

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

1.  Всякая логическая переменная и символы «истина» («1») и «ложь» («0») - формулы.

2.  Если А и В - формулы, то , (А • В), (AvB), (А→В), (А↔В) - формулы.   |

3.   Никаких других формул в алгебре логики нет.