Высказывания и операции над ними

Лекция 6. Элементы классической математической логики. Логика высказываний

Изучение математической логики мы начнем с наиболее простой ее части – логики высказываний.

Высказывания и операции над ними

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

A = “Число √2 является иррациональным ”.

B = “Неверно, что число √2 является иррациональным ”.

C = “Число √2+1 является иррациональным ”.

D = “Если число √2 является иррациональным, то число √2 +1 также является иррациональным ”.

E = “Число x является иррациональным ”.

F = “Который час?”

G = “Идите решать задачу к доске!”

Первые четыре предложения являются высказываниями, последние три – нет. Предложения F и G не являются повествовательными, а значение истинности повествовательного предложения E зависит от того, какие значения получит переменная x. Высказывания A, C и D истинны, высказывание B – ложно. Более точно, значение истинности высказываний A, C и D есть истина, а значение истинности высказывания B есть ложь. В дальнейшем истину будем обозначать символом 1, а ложь – символом 0.

Проанализируем высказывания A – D с точки зрения их “внутреннего строения”. Высказывания А и C можно назвать простыми, высказывания B и D – составными, полученными из простых высказываний A и C. Этот пример показывает, что в языке (в данном случае, в русском языке) существуют способы построения одних высказываний из других, которые мы будем называть операциями. В естественных языках существует много таких операций. Мы выделим в качестве основных пять операций.

Определение. Пусть X и Y – некоторые высказывания. Тогда высказывание

1) “ X и Y ” называется конъюнкцией высказываний X и Y;

2) “ X или Y ” называется дизъюнкцией высказываний X и Y;

3) “не X ” называется отрицанием высказывания X;

4) “если X, то Y ”называется импликацией высказываний X и Y;

5) “ X тогда и только тогда, когда Y ” называется эквиваленцией высказываний X и Y.

Высказывание B из вышеприведенного примера является отрицанием высказывания A, а высказывание D – импликацией высказываний A и C. Введем следующие обозначения для операций: & – конъюнкция, v – дизъюнкция, – отрицание, → – импликация, ↔ – эквиваленция. Так, B = A, D = A → C. Символы &, v,, →, ↔ называются связками.

Зависимость значения истинности новых высказываний от значений истинности исходных высказываний определяется таблицей истинности связок (см. таблицу 1.1). Напомним, что единица означает, что высказывание истинно, а ноль – ложно.

Т а б л и ц а 1.1

Можно сказать, что таблица 1.1 содержит пять таблиц истинности, по одной для каждой из связок. Эти пять таблиц для удобства объединены в одну. Прокомментируем таблицы истинности дизъюнкции и импликации. В русском языке союз “или” понимается в двух смыслах: разделительном – или то, или другое, но не оба, и соединительном – или то, или другое, или оба. Как видно из таблицы 1.1, союз “или” мы будем понимать в соединительном смысле. Перейдем к импликации. Если дана импликация X → Y, то высказывание X называется посылкой импликации, а Y – заключением. Если посылка X импликации ложна, то вся импликация X → Y истинна (см. третью и четвертую строки таблицы 1.1). Это свойство импликации часто формулируют в виде следующего принципа: “из ложного утверждения (имеется в виду X) следует все что угодно (имеется в виду Y)”. В силу этого следующее высказывание “если 2*2 = 5, то π – иррациональное число” является истинным, поскольку оно представляет собой импликацию, посылка которой ложна. Подчеркнем, что при этом не надо искать доказательство или опровержение того, что π – иррациональное число. Аналогично, первая и третья строки таблицы 1.1 показывают нам, что если заключение Y импликации истинно, то вся импликация X → Y также истинна. Это свойство импликации тоже формулируют в виде принципа: “истинное утверждение (имеется в виду Y) следует из чего угодно (имеется в виду X)”. Из этого принципа сразу следует истинность высказывания “если π – ирррациональное число, то 2*2 = 4”, поскольку оно представляет собой импликацию с истинным заключением.