Математическая логика

Это правило называется законом отрицания отрицания.

1.4. Неопределенные высказывания.

Будем обозначать через N множество всех натуральных чисел. Через x условимся обозначать произвольное натуральное число, т.е. произвольный элемент множества N. Рассмотрим теперь следующие предложения:

А(x) ≡ {число х делится на 5},

В(х) ≡{x > 10},

С(х) ≡ {х – простое число},

D(х) ≡ {(х – 5)2 < 10}.

Предложения А(х), В(х), С(х), D(х) высказываниями не являются. Действительно, об истинности, например, А(х) мы ничего не можем сказать, пока нам неизвестно число х. Однако, подставляя в А(х) вместо х различные натуральные числа, мы будем получать высказывания о натуральных числах – иногда истинные, иногда ложные. Подставляя в А(х) вместо х различные натуральные числа, мы получаем, например, следующие высказывания:

А(5) ≡ {число 5 делится на 5}- истинное высказывание,

А(13) ≡ {число 13 делится на 5}- ложное высказывание

и т.д. Можно составить следующую таблицу истинности для этих высказываний:

Указанные выше предложения А(х), В(х), С(х), D(х), содержащие переменное х, можно назвать неопределенными высказываниями (в математике их называют также предикатами). Каждое из них выражает некоторое свойство натурального числа х. Например, С(х) выражает свойство быть простым числом, А(х) – свойство делиться на 5 и т.п. Если вместо х подставить любое натуральное число, то мы получим обычное высказывание.

Неопределенное высказывание может быть задано на любом множестве, а не только на множестве натуральных чисел. Оно представляет собой высказывание о каком-то элементе х рассматриваемого множества. Для одних элементов эти высказывания истины, для других – ложны.

Часто приходится рассматривать неопределенные высказывания, в которых входит не одно, а два или большее число переменных. Рассмотрим, например, следующие предложения, в которых под х и у понимаются произвольные натуральные числа:

А(х,у) ≡ {х<у},

В(х,у) ≡ {х+у = 10},

С(х,у) ≡ {х делится на у}

D(х,у) ≡ {х + у – простое число}.

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

А(1;3) ≡ {1 < 3} – истинное высказывание,

А(2;2) ≡ {2 < 2} – ложное высказывание,

А(5;4) ≡ {5 < 4} – ложное высказывание,

В(1;3) ≡ {1 + 3 = 10} – ложное высказывание,

В(8;2) ≡ {8 + 2 =10} – истинное высказывание    и т.д.

1.5. Знаки общности и существования.

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

Большое затруднение у учащихся вызывает нахождение правильной формулировки отрицания  ┐А в том случае, когда высказывание А содержит слова «все», «каждый», «хотя бы один», «найдется», «существует» и т.п.

Пусть, например, высказывание А имеет вид:

А ≡ {каждое простое число нечетно}.

На вопрос о том, каково будет отрицание этого высказывания, многие отвечают, что отрицанием будет высказывание

В ≡ {каждое простое число четно}.

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

┐А ≡ {не каждое простое число нечетно},

иными словами,

┐А ≡ {найдется (существует) простое число, которое четно},

или еще

┐А ≡ {хотя бы одно простое число четно}.

Это высказывание истинно: существует (только одно!) четное простое число, а именно 2.

Сравним два только что рассмотренных высказывания:

А ≡ {каждое простое число нечетно},

┐А ≡ {хотя бы одно простое число четно}.

Мы видим, что если отбросить начальные слова в формулировках, то высказывание А будет иметь вид {…простое число нечетно}, а его отрицание  ┐А будет иметь вид {…простое число четно}, т.е. вторая часть высказывания просто заменится ее отрицанием. Но очень важно заменить, что при этом первое слово «каждое», стоявшее в высказывании А, заменится в высказывании  ┐А словами «хотя бы одно» (или словом «найдется» или «существует»). Этот факт является общим, и его понимание может избавить от многих неприятных ошибок. Итак, если высказывание А начинается со слов «все», «каждый», «любой» и т.п., то для получения отрицания  ┐А надо либо, ничего не меняя, поставить отрицание «не» перед этими словами, либо же поставить отрицание «не» после этих слов, но тогда эти слова непременно надо заменить на «хотя бы один», «найдется», «существует» и т.п. Разумеется верно и обратное: если в начале высказывания стоят слова «хотя бы один», «найдется», «существует», то при постановке отрицания «не» после этих слов они заменяются на «все», «каждый», «любой». Еще раз подчеркнем, что это происходит при постановке отрицания «не» после  указанных слов. Если же отрицание «не» добавляется (или выбрасывается) перед указанными выше словами, то никакой замены слов не происходит.

Пример:

А ≡ {каждое из чисел a, b, c делится на 7},

┐А ≡{не каждое из чисел a, b, c делится на 7},

или иначе:

┐А ≡ {хотя бы одно из чисел a, b, c не делится на 7}.

Пример:

А ≡ {никакой ромб не может быть вписан в окружность}.

Это высказывание можно сформулировать иначе:

А ≡ {не существует ромба, который может быть вписан в окружность}.

Поскольку здесь «не» стоит впереди, для получения отрицания можно просто отбросить это «не»:

┐А ≡ {существует ромб, который может быть вписан в окружность}.

Пример:

А ≡ {во всяком треугольнике три медианы пересекаются в одной точке},

┐А ≡ {не во всяком треугольнике три медианы пересекаются в одной точке},

или иначе

  ┐А ≡ {найдется треугольник, в котором три медианы не пересекаются в одной точке}.

Иногда используют специальные знаки , . Первый из них (знак общности ) заменяется в словесных формулировках словами всякий, каждый, любой, все. Второй знак  (знак существования) заменяется в словесных формулировках словами существует, найдется, какой-нибудь, хотя бы один. Именно, если Р(х) – некоторое неопределенное высказывание, заданное на множестве М, то запись

(х)Р(х)

означает: для любого элемента х (из множества М) имеет место Р(х). Эта запись уже представляет собой высказывание (а не неопределенное высказывание). Это высказывание истинно, когда Р(а) истинно для каждого элемента а множества М, и ложно в противном случае. Иными словами, чтобы убедиться в истинности высказывания (х)Р(х), нужно перебрать все элементы a, b, c … множества М и убедиться, что все высказывания Р(а), Р(b), Р(c), … истинны (а если мы не можем или не хотим перебрать все элементы множества М, то должны доказать с помощью некоторого рассуждения, что для любого элемента а из М высказывание Р(а) истинно). Для того же, чтобы убедиться в ложности высказывания (х)Р(х), достаточно найти лишь один элемент а множества М, для которого высказывание Р(а) ложно. Иначе говоря, для того, чтобы убедиться в ложности некоторого общего высказывания (т.е. высказывания, содержащего знак общности ), достаточно найти один противоречащий пример.

Пример:

Возьмем следующее неопределенное высказывание, заданное на множестве N всех натуральных чисел:

С(х) ≡ {число 2(2 ) + 1 - простое}.

При х = 1,2,3,4 мы получаем следующие высказывания

С(1) ≡ {число 2(2 ) + 1 = 5 - простое},

С(2) ≡ {число 2(2 ) + 1 = 17 - простое},

С(3) ≡ {число 2(2 ) + 1 = 257 - простое},

С(4) ≡ {число 2(2 ) + 1 = 65537 - простое}.

Все эти высказывания истинны. Но можем ли мы из этого заключить, что истинно высказывание (х)С(х), т.е что для любого натурального n число 2(2 ) + 1 будет простым? Нет, конечно, для такого заключения у нас нет оснований. Ведь мы же не перебрали все натуральные числа, да и не можем этого сделать, так как множество натуральных чисел бесконечно. Интересно, что известный французский математик Пьер Ферма был убежден в справедливости высказывания (х)С(х) и пытался найти общее доказательство этого факта. Однако другой известный математик, Леонард Эйлер, показал, что высказывание С(5) ложно (т.е. что число 2 (2 ) + 1 = 232 + 1 не является простым: оно делится на 641). Таким образом, высказывание (х)С(х), вопреки мнению Ферма, оказалось ложным. Этот пример показывает, что проверка истинности высказывания (х)Р(х) для отдельных значений х не может заменить общего доказательства. Напротив, один противоречащий пример, найденным Эйлером, показывает ложность высказывания.

Пример:

Рассмотрим высказывание (х)D(х), где D(х) – следующее неопределенное высказывание, заданное на множестве N всех натуральных чисел:

D(х) ≡ {число х3 + 5х делится на 6}.

Легко проверить, что высказывания  D(1), D(2), D(3), D(4), D(5) истинны. Тот же результат будет получаться, если мы будем продолжать проверку дальше. Но мы уже знаем, что проверкой для отдельных значений х мы не можем установить истинность высказывания (х)D(х). Даже если мы испытаем миллион значений х, всегда остается опасность, что для миллион первого значения х утверждение D(х) окажется ложным. Доказательство истинности высказывания (х)D(х) можно провести, например, следующим образом. Мы имеем:

х3 + 5х = х3 – х + 6х = х(х2 – 1) + 6х = (х – 1) х(х + 1) +6х.

Но из трех последовательных чисел х – 1, х, х + 1 обязательно одно делится на 3 и одно или два делятся на 2. Следовательно, произведение их делится на 6. Таким образом, и сумма (х – 1) х(х + 1) +6х = х3 + 5х при любом натуральном х делится на 6. Но это и означает истинность высказывания (х)D(х).

Перейдем теперь к знаку существование . Если Р(х) – некоторое неопределенное высказывание, то запись

(х) Р(х)

означает: существует элемент х множества М, для которого имеет место Р(х) (или иначе: найдется хотя бы один элемент х, для котрого имеет место Р(х)).

Запись (х) Р(х) не является неопределенным высказыванием, а представляет собой высказывание. Это высказывание истинно, если можно в множестве М найти элемент а, для которого Р(а) истинно. В противном случае (т.е. если в М нет ни одного элемента а,для которого высказывание Р(а) истинно) высказывание (х) Р(х) ложно.

Пример: Рассмотрим следующее неопределенное высказывание, заданное на множестве N всех натуральных чисел:

С(х) ≡ {х3 – 14х2 + 49х – 1 <0}.

При х = 1, 2, 3, 4 мы получаем следующие высказывания:

С(1) ≡ {13 – 14*12 + 49*1 – 1 < 0 (т.е. 35<0},

С(2) ≡ {23 – 14*22 + 49*2 – 1 < 0 (т.е. 49<0},

С(3) ≡ {33 – 14*32 + 49*3 – 1 < 0 (т.е. 47<0},

С(4) ≡ {43 – 14*42 + 49*4 – 1 < 0 (т.е. 35<0}.

Все эти высказывания ложны. Но можем ли мы из этого заключить, что ложно высказывание (х) С(х), т.е. что так и не найдется натурального n, для которого высказывание С(n) истинно? Нет, конечно, для такого заключения у нас нет оснований. Сколько бы мы чисел ни перебрали, всегда остается возможность, что где-то дальше найдется число n, для которого С(n) истинно.

Продолжим наши пробы дальше:

С(5) ≡ {53 – 14*52 + 49*5 – 1 < 0 (т.е. 19<0},

С(6) ≡ {63 – 14*62 + 49*6 – 1 < 0 (т.е. 5<0},

С(7) ≡ {73 – 14*72 + 49*7 – 1 < 0 (т.е. -1<0}.

Мы видим, что высказывания С(5) и С(6) ложны, а С(7) истинно. Итак, мы нашли такое n (а именно n=7), для которого высказывание С(n) истинно. Следовательно, (х) С(х) – истинное высказывание.

Разумеется, метод проб является далеко не наилучшим для проверки истинности высказывания (х) Р(х) (где Р(х) – некоторое неопределенное высказывание). Ведь «благоприятное» значение n (для которого Р(n) истинно) может встретиться где-то очень далеко, и нахождение этого n методом проб будет мучительной работой. А может случиться, что высказывание Р(n) ложно для всех n, и тогда метод проб вообще ни к чему не приведет. Поэтому более предпочтительным является общее рассуждение. Например, в рассматриваемом случае можно было рассуждать так:

х3 – 14х2 + 49х – 1 = х(х2 – 14х + 49) – 1 = х(х – 7)2 – 1.

Отсюда видно, что при х=7 этот многочлен принимает значение -1 (так как слагаемое х(х - 7)2 обращается в нуль). Итак, высказывание С(7) имеет вид -1 < 0, т.е. истинно, а потому истинно и высказывание (х) С(х).

Глава 2. Необходимые и достаточные условия.

2.1. Необходимые и достаточные условия.

Рассмотрим какую-либо теорему. В большинстве случаев можно в ней выделить условие и заключение. При этом и условие и заключение теоремы являются некоторыми неопределенными высказываниями.

Возьмем, например, теорему Пифагора. Мы рассматриваем некоторый прямоугольный треугольник ABC; c – гипотенуза треугольника, a и b – его катеты. Теорема утверждает, что имеет место соотношение c2 = a2 + b2. Условие теоремы здесь можно записать в виде следующего неопределенного высказывания:

М ≡ {в треугольнике ABC угол С - прямой}.

Заключение теоремы:

N ≡ { c2 = a2 + b2}.

При таком обозначении условия и заключения теорема Пифагора может быть выражена краткой записью:

М→N.

Эта запись означает, что из М следует N. Иными словами, если для некоторого треугольника истинно высказывание М, то истинно и высказывание N. Разумеется, высказывание М не всегда истинно – не всякий треугольник является прямоугольным. Но если высказывание М истинно, если известно, дано, что треугольник ABC – прямоугольный (а его стороны обозначены, как указано выше), то высказывание N также истинно. Это и выражается словами «из М следует N».