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

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

Фраза естественного языка	Формула
Если Р, то Q Для Р необходимо Q Для P достаточно Q P, если Q	PQ PQ QP QP
Необходимым условием Р является Q Достаточным условием P является Q	PQ QP
Р если и только если Q Для Р необходимо и достаточно Q Р тогда и только тогда, когда Q	PQ PQ P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. 