Глава 2 элементы математической логики

В этой главе мы познакомимся с некоторыми фактами раздела математики, называемого математической логикой. Логика как дисциплина – наука о законах мышления, формирование которой в первую очередь связано с трудами древнегреческого философа Аристотеля (384–322 г. до н. э.).

«Математическая логика» – раздел «логики», в котором логические законы описываются с помощью формул, а при исследовании этих законов используется математический аппарат. Основоположником математической логики считается английский математик Джордж Буль, 1815–1864 (отец Этель Лилиан Войнич, автора известного романа «Овод»).

§1. Высказывание и логические операции

n1. Понятие высказывания

Понятие высказывания является основным (неопределяемым) понятием математической логики. Ограничимся лишь интуитивным описанием этого понятия. Под высказываниями будем понимать повествовательные предложения, для которых не является бессмысленной постановка вопроса об его истинности. При этом требуется выполнение двух условий: высказывание является истинным или ложным; высказывание не может быть одновременно истинным и ложным.

Будем считать, что каждое высказывание обладает некоторым истинностным значением. Именно, каждому истинному высказыванию припишем истинностное значение «Истина» (сокращенно – И), а каждому ложному высказыванию – истинностное значение «Ложь» (сокращенно – Л).

Высказывания обозначают большими латинскими буквами: А, В, С, … . Если A – некоторое высказывание, то символом |A| обозначается истинностное значение высказывания A. Иногда вместо символов «И», «Л» для обозначения истинностных значений используются символы «1», «0» соответственно.

Итак,

Пример 1. Выяснить, являются ли высказываниями следующие предложения: А = «Курск – областной центр», В = «2х2=5», С = «Да здравствуют каникулы!», D = «Подайте мне книгу, пожалуйста».

Решение. Предложения C и D не являются утвердительными, поэтому они не считаются высказываниями. Предложение A (В) является истинным (ложным) утвердительным предложением. Следовательно, А и B являются высказываниями, причем |A|=И, |B|=Л.

n2. Логические операции

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

Определение 1. Пусть A и B – какие-либо высказывания.

Отрицанием высказывания A называется высказывание, обозначаемое одним из символов: , А (читается «не верно, что A» или «не A»), являющееся истинным тогда и только тогда, когда A ложно.

Дизъюнкцией высказываний A и B называется высказывание, обозначаемое символом AB (читается «A или B»), являющееся ложным тогда и только тогда, когда A и B одновременно ложны.

Конъюнкцией высказываний A и B называется высказывание, обозначаемое одним из символов AB, А&B (читается «A и B»), являющееся истинным в том и только в том случае, когда A и B одновременно истинны.

Импликацией высказываний A и B называется высказывание, обозначаемое символом AB (читается «если A, то B»), являющееся ложным тогда и только тогда, когда A истинно, а B ложно.

Эквиваленцией высказываний A и B называется высказывание, обозначаемое символом AB (читается «A тогда и только тогда, когда B») и являющееся истинным в том и только в том случае, когда высказывания A и B имеют одинаковые истинностные значения.

Для высказываний AB, AB, AB, AB сами высказывания A и B называются членами. Для импликации AB высказывание A называется условием или посылкой, а высказывание B – заключением или следствием.

Связь между истинностными значениями высказываний A, B, , AB, AB, AB, AB можно указать с помощью следующей, так называемой таблицы истинности:

|A|	|B|	||	|AB|	|AB|	|AB|	|AB|
И	И	Л	И	И	И	И
И	Л	Л	И	Л	Л	Л
Л	И	И	И	Л	И	Л
Л	Л	И	Л	Л	И	И

Термины: дизъюнкция, конъюнкция и импликация происходят соответственно от латинских слов: «disjunctio» – разобщение, различие; «conjunctio» – союз, связь; «implico» – тесно связываю.

Заметим, что дизъюнкция соответствует русскому союзу «или», взятому в соединительном (не исключающем) смысле, то есть AB считается истинным и в том случае, когда А, B одновременно истинны.

Можно указать на использование дизъюнкции и конъюнкции уже на первых шагах изучения алгебры: символ ав, где а, в  R, является сокращенным обозначением дизъюнкции (а<в)(а=в); символы а<в<с, а<в с, ав<с, авс, где а, в, с  R , являются сокращенными записями конъюнкций (а<в)  (в<с), (а<в)  (вс), (ав)  (в<с), (ав)  (вс) соответственно.

Пример 2. Если A = «23», B = «23<–1», С = «123», то |A|=|(2<3)(2=3)|=И, |В|=|(2 3)(3<–1)|=Л, |С|=И, ||=Л, |AB|=Л, |AB|=И, |AB|=Л, |AB|=Л.

n3. Сложные высказывания. Порядок выполнения логических операций

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

Пример 3. Рассматривая в качестве элементарных высказывания А, В и С из примера 2, можно, например, построить такое сложное высказывание: .

Запись сложных высказываний можно упростить, введя следующие соглашения:

1. опускается «внешняя» пара скобок, то есть пара скобок, между которыми располагаются все остальные символы в записи данного высказывания;

2. каждое из высказываний (A), () разрешается записывать в виде A, , а следовательно, не заключается в скобки запись сложного или элементарного высказывания, стоящего под знаком отрицания;

3. высказывания (AB) и (А&B) разрешается записывать в виде (AB) или (AB);

4. принимаются соглашения о «старшинстве» (или о приоритете) логических операций, то есть считается:

а) отрицание «сильнее» остальных операций;

в) конъюнкция «сильнее» дизъюнкции, импликации и эквиваленции; с) дизъюнкция «сильнее» импликации и эквиваленции;

d) импликация «сильнее» эквиваленции;

5. пару скобок, которую можно «восстановить», учитывая «порядок старшинства», разрешается опустить.

Так, например, благодаря сделанным соглашениям, записи сложных высказываний: (А(ВС)), (А(ВС)), ((АВ)С) и можно заменить записями A(ВС), АВС, АВС и соответственно. Сложное высказывание S из примера 3 можно записать в виде: .

n4. Понятие равносильности и следования для высказываний

Определение 2. Пусть A и В – какие-либо высказывания. Если |A| = |В|, то есть |АВ| = И, то высказывания A и В называются равносильными, при этом пишут: AВ. Если же |AВ|=И, то говорят, что «из A следует В» и пишут AВ.

Так как для высказываний А=«2<3», В=«123», С=«2<3<–1» имеем: |А|=|В|=И, |С|=Л, то АВ, АВ, ВА, СА , но и .