Формулировка и доказательство теорем.

Импликация и эквивалентность, или формулы PÞQ и РÛQ, имеют важнейшее значение в формулировках и доказательствах теорем. Рассмотрим, как соотносятся с этими формулами различные связки естественного языка, часто встречающиеся при формулировке теорем.

Эту таблицу запомнить трудно, но ее и не надо запоминать, тем более, что существует много и других похожих формулировок теорем. Полезно придумать два высказывания, с совершенно ясной логической связью, например: (M) "Идет дождь" и (N) "На небе тучи". Ясно, что MÞN, но не наоборот. Другой подобный пример: (А) “Треугольник равносторонний” и (В) “В треугольнике углы при основании равны”. Очевидно, что АÞВ, но не обратно. Пусть теперь требуется доказать теорему: “Р только тогда, когда Q”. Попробуем заменить Р и Q высказываниями А и В. Очевидно, что Р может быть ассоциировано только с А, а Q - только с В: “Треугольник равносторонний только тогда, когда Треугольник равнобедренный”. Следовательно, формулировка “Р только тогда, когда Q” эквивалентна “Если Р, то Q” или PÞQ. Очевидно, что в импликации АÞВ утверждение А сильнее, чем утверждение В, а В слабее, чем А. Здесь понятия сильнее и слабее относятся к требованиям, налагаемым на элементы универсума - множества реальных объектов, о которых идет речь.

Для доказательства PÞQ можно использовать метод доказательства от противного: “Предположим, что Q не выполняется. Докажем, что тогда Р не выполняется.” Этот метод можно использовать, потому что формулы PÞQ и ØQÞØP эквивалентны. Формула ØQÞØP называется контрапозицией формулы PÞQ. Таким образом, метод доказательства от противного имеет четкое обоснование в логике высказываний, состоящее в том, что формула и ее контрапозиция эквивалентны.

Доказательство необходимости и достаточности PÛQ проводится обычно раздельно: сначала доказывается необходимость ( “для Р необходимо Q”, PÞQ), а потом - достаточность ( “для Р достаточно Q”, QÞP). Такое раздельное доказательство можно использовать, потому что формула (PÞQ)&(QÞP) эквивалентна PÛQ (как это проверить?). Аналогично можно использовать эквивалентность (PÞQ)&(RÞQ) формуле (PÚRÞQ). Для доказательства теорем с более сложными схемами формулировок следует искать такие более простые формулы, конъюнкция которых была бы эквивалентна исходной формуле. Конъюнкция здесь используется потому, что последовательное доказательство истинности нескольких формул эквивалентно доказательству истинности конъюнкции этих формул.

Пример 2.2. Для доказательства теоремы: “Нильпотентный идеал является модулярным и радикальным” необходимо доказать две более простые теоремы: “Нильпотентный идеал является модулярным” и: “Нильпотентный идеал является радикальным”, потому что формула NÞM&R эквивалентна конъюнкции (NÞM)&(NÞR). Каждую из этих более простых теорем можно доказать и от противного. Заметим, что структура доказательства найдена нами совершенно без какой-либо связи с содержанием теоремы.

Пусть теперь нужно доказать более сильную теорему: “Идеал нильпотентен тогда и только тогда, когда он является модулярным и радикальным”. Формальное выражение этого утверждения NÛM&R. Для доказательства всей теоремы следует доказать три более простых теоремы (почему?):

· “Если идеал не является модулярным, то он не может быть нильпотентным” (ØMÞØN)

· “Если идеал не является радикальным, то он не может быть нильпотентным” (ØRÞØN)

· “Если идеал и модулярный, и радикальный, то он нильпотентный” (M&RÞN).ÿ

Пример 2.3.Следующий пример- теорема Поста из главы 1. Схема ее формулировки такова: “Для того, чтобы Р, необходимо и достаточно, чтобы и ØQ₀ и ØQ₁ и ØQ_сам и ØQ_мон и ØQ_лин”, где P - утверждение: “множество функций N является базисом”, аQ_i - утверждение: “множество функций N принадлежит замкнутому классу М_i”. Иными словами, нужно доказать РÛ(ØQ₀&ØQ₁&ØQ_сам&ØQ_мон&ØQ_лин).

Представляем эту формулу как конъюнкцию: необходимость
РÞ(ØQ₀&ØQ₁&ØQ_сам&ØQ_мон&ØQ_лин)

и достаточность:
(ØQ₀&ØQ₁&ØQ_сам&ØQ_мон&ØQ_лин)ÞР.

Вместо первой формулы мы доказывали ее контрапозицию, т.е. Ø(ØQ₀&ØQ₁&ØQ_сам&ØQ_мон &ØQ_лин)ÞØР, что эквивалентно конъюнкции пяти формул: (Q₀ÞØР)&(Q₁ÞØР)&(Q_самÞØР)& (Q_монÞØР)&(Q_линÞØР). Таким образом, доказательство теоремы Поста состоит из пяти независимых доказательств - того, что если множество N булевых функций принадлежит одному из пяти замкнутых классов (Q_i), то оно не является базисом (ØР) (необходимость),и одного доказательства: “если N не принадлежит ни одному из пяти замкнутых классов, то оно является базисом” (достаточность). Эту последнюю формулу упростить уже нельзя, достаточность теоремы Поста доказывается конструктивно: из функций множества N непосредственно строятся функции конъюнктивного базиса, что нами и проделано в главе 1.ÿ