Доказательство от противного данного утверждения

[Sdy]

Для случая, когда данное утверждение $X$ (истинность которого требуется установить) не является сложным (в нем нет "базовых" логических операций - конъюнкции, дизъюнкции, отрицания), данная схема доказательства устроена понятным для меня образом - предположим что $\neg X$ истинно и с помощью корректных логических рассуждений придем к $Y$, которое ложно. Но тогда импликация $\neg X \to Y$ истинна (ведь рассуждения были корректны), но $Y$ ложно. Импликация со вторым операндом, значение которого - ложь, истинна тогда и только тогда, когда первый операнд ложен. Но тогда $\neg X$ - ложно. Из этого по закону исключенного третьего следует, что $X$ - истинно. Таким образом с помощью схемы доказательства от противного устанавливается истинность данного утверждения $X$.
Пусть теперь, $X = P \to Q$. Тогда для доказательства от противного нужно взять отрицание импликации. Как известно $(P \to Q) \leftrightarrow (\neg P \vee Q)$, то есть эти две формулы истинны при одних и тех же значениях переменных. Тогда взяв отрицание от $\neg P \vee Q$, мы получаем, что необходимо предположить истинность $P \wedge \neg Q$. Предполагая истинность данного утверждения мы приходим с помощью корректных логических рассуждений к $Y$, которое ложно, т.е. $(P \wedge \neg Q) \to Y$, при этом $Y$ - ложно. Но тогда $P \wedge \neg Q$ должно быть ложно. По закону исключенного третьего это означает, что $\neg P \vee Q$ истинно, но как только истинно $\neg P \vee Q$, так сразу истинно $P \to Q$. При этом мы предполагаем (по условию данного утверждения), что $P$ - истинно. Ну а раз результат импликации (по доказанному) - истина, истинность самого утверждения $P$ нам дана, то и $Q$ истинно, а значит исходное утверждение $X = P \to Q$ доказано с помощью схемы доказательства от противного.

Собственно вопрос - правильно ли я понимаю как работает схема доказательства от противного? Для первого случая, когда в $X$ отсутствуют другие логические операции, все представляется понятным. Для случая импликации - все-таки возникает вопрос, правильно ли я все понимаю. Просто бОльшая часть теорем в разных разделах математики выглядят как импликации и хотелось бы быть уверенным, что я верно понимаю, как работает способ (с точки зрения логики), который очень часто применяется при их доказательстве.

[mihaild]

В целом всё правильно, но нам совершенно не обязательно как-то расписывать $X$. Заметьте, что в рассуждениях в первом абзаце вы никак не пользовались "простотой" $X$ - вам вообще неважно, что это за утверждение. Во втором абзаце не нужно было расписывать импликацию через дизъюнкцию, потом еще её отрицание переписывать и т.д., можно было спокойно оставить просто $\neg X$.
Естественно что при доказательстве $\neg X \to Y$ нам как-то понадобится анализировать $X$, но это уже "внутри" схемы доказательства от противного.

Sdy в сообщении #1538223 писал(а):

Но тогда $P \wedge \neg Q$ должно быть ложно. По закону исключенного третьего это означает, что $\neg P \vee Q$ истинно

Только всё-таки по закону де Моргана. Закон исключенного третьего - это $A \vee \neg A$.

[kernel1983]

Правило доказательства от противного имеет вид $ \neg P \to (R \wedge \neg R) \models P$, в частности, $(P \wedge \neg Q) \to (R \wedge \neg R) \models (P \to Q)$. Проще говоря, чтобы доказать истинность высказывания $P$, доказываем истинность импликации $\neg P \to (R \wedge \neg R)$ (из отрицания высказывания $P$ выводим заведомо ложное высказывание; возможно, для этого понадобится цепочка импликаций, а значит, правило силлогизма $P \to Q, Q \to R \models P \to R$). Из этого, используя правило доказательства от противного, получаем то, что нам нужно (чтобы сделать такой вывод потребуется и правило modus ponens $P. P \to Q \models Q$).

[Sdy]

mihaild, спасибо за ответ.

mihaild в сообщении #1538231 писал(а):

В целом всё правильно, но нам совершенно не обязательно как-то расписывать $X$. Заметьте, что в рассуждениях в первом абзаце вы никак не пользовались "простотой" $X$ - вам вообще неважно, что это за утверждение.

Я понимаю, просто хотел понять, верно ли я провожу некоторые "технические действия" (касающиеся преобразований логических выражений и знания определений логических функций) если $X$ все-таки является сложным. И уж очень часто я вижу утверждения вида $P \to Q$, которые доказываются методом от противного, и не был уверен до конца, правильно ли я представляю себе "внутренность" процесса с точки зрения логики, захотелось себе это таким образом "обосновать", несмотря на то что в литературе написано, что $X$ - произвольное утверждение. Мне как-то проще становится когда я могу в данной теореме "вытащить" $X$, $Y$, а потом их разбить на составные части и получить конкретное логическое выражение, например вида $(A \vee \neg B \wedge C) \to (U \wedge V)$. Ну и для него уже понять что конкретно значит "отрицание" посылки и так далее.

mihaild в сообщении #1538231 писал(а):

Только всё-таки по закону де Моргана. Закон исключенного третьего - это $A \vee \neg A$.

Тут я немного "срезал концы". Полная формулировка должна быть такой: пусть $\neg X = P \wedge \neg Q$. Оно ложно, как мы установили. Тогда отрицание к нему - истинно (по определению операции отрицания). Отрицание мы получаем по закону де Моргана и закону двойного отрицания, $\neg \neg X = \neg P \vee Q = X$. Но как только истинно $\neg P \vee Q$, так сразу истинно $P \to Q$ (в силу их эквивалентности) и далее уже последующий текст.

И ещё, верно ли я написал, что:

Sdy в сообщении #1538223 писал(а):

При этом мы предполагаем (по условию данного утверждения), что $P$ - истинно.

Ну то есть что мы можем полагать для дальнейшего вывода что $Q$ истинно тот факт, что истинность $P$ нам дана? Вроде как это очевидно - ведь ставится задача доказательства импликации при истинности её посылки. (Обычно же теоремы начинаются словами "Пусть выполнено некоторое утверждение $X$, тогда $Y$"). Верно ли что мы можем это использовать в моем рассуждении? Вообще, как я понимаю, "с практической" точки зрения при доказательстве различных импликаций мы сужаем область определения логической функции, со всевозможных значений первого аргумента до одного значения - истинности.

-- 08.11.2021, 23:07 --

kernel1983, спасибо за ответ.
Как это выглядит в "формальном виде", я знаю. Как выше уже писал, меня интересуют некоторые "частности" такой схемы доказательств.

[mihaild]

Sdy в сообщении #1538253 писал(а):

верно ли я провожу некоторые "технические действия"

Верно, но непосредственно к методу доказательства от противного это не относится.

Sdy в сообщении #1538253 писал(а):

Ну и для него уже понять что конкретно значит "отрицание" посылки и так далее.

Всё хорошо, но расписывать отрицание посылки стоит как раз внутри доказательства.

Sdy в сообщении #1538253 писал(а):

И ещё, верно ли я написал, что:

Sdy в сообщении #1538223 писал(а):

При этом мы предполагаем (по условию данного утверждения), что $P$ - истинно.

Правильный вопрос, это я как-то пропустил. Нет, никаких предположений об истинности $P$ мы тут делать не можем. Мы доказали, что $P \to Q$, и всё. Может быть посылка ложна, может быть заключение истино - просто из результата $\neg (P \rightarrow Q) \rightarrow \bot$ нельзя определить истинность $P$.

Sdy в сообщении #1538253 писал(а):

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

Нет. Просто для того, чтобы показать выводимость $P \rightarrow Q$, нам достаточно предположить $P$, и, используя это предположение, вывести $Q$ (теорема о дедукции).

[Sdy]

mihaild, спасибо за ответ.

mihaild в сообщении #1538256 писал(а):

Правильный вопрос, это я как-то пропустил. Нет, никаких предположений об истинности $P$ мы тут делать не можем. Мы доказали, что $P \to Q$, и всё. Может быть посылка ложна, может быть заключение истино - просто из результата $\neg (P \rightarrow Q) \rightarrow \bot$ нельзя определить истинность $P$.

То есть мы доказали, что $P \to Q$ - истинно. А импликация истинна всегда, кроме как в случае когда $P$ - истина, $Q$ - ложь. Таким образом, факт истинности $P \to Q$ можно использовать тремя способами:
1)"Осмысленно-полезный в рамках дальнейшего использования этого факта", когда $P$ и $Q$ истинны, и взяв некоторый объект, для которого утверждение $P$ истинно, мы получим, что для него истинно и $Q$.
Например, если $P = \{$$n$ - нечётное и целое число$\}$, А $Q = \{$Квадрат n нечётен$\}$.
Тогда взяв $n=3$ мы получим что для него истинно $P$, и тогда получим, что его квадрат нечётен.
2) и 3)"Способ использования неполезный в рамках дальнейшего его применения", а именно то что из лжи следует что угодно. Тогда взяв для предыдущего примера $n= 2$ мы получим что $P$ ложно и $Q$ ложно, но истинность импликации от этого не поменяется, так как наша импликация ничего не говорит о тех случаях, когда $P$ ложно, а значит ничего не мешает ей быть истинной. Или же взять $n = \sqrt{3}$. Для такого $n$ $P$ - ложно (так как такое $n$ не является целым), но его квадрат - нечётное число, а значит $Q$ - истинно. Тут все тоже рассуждение - из лжи может следовать что угодно, поэтому импликация все равно остается истинной.

Верно ли я понял Ваше замечание?

[mihaild]

Да, это стандартная ситуация с импликацией, опять же никак не связанное с тем, как мы её получили.
Но случай "$P$ и $Q$ оба ложны" на практике может быть полезен - если мы доказали $P \to Q$ и доказали $\neg Q$, то мы можем из этого получить $\neg P$.

[Sdy]

mihaild, спасибо за ответ.
Ну да, как я понимаю, это следует из того что выполнен закон контрапозиции: $(P \to Q)\leftrightarrow (\neg Q \to \neg P)$.

[epros]

Sdy в сообщении #1538373 писал(а):

Ну да, как я понимаю, это следует из того что выполнен закон контрапозиции: $(P \to Q)\leftrightarrow (\neg Q \to \neg P)$.

Закон контрапозиции (по крайней мере, в одну сторону) работает и в таких логиках, в которых из ложного утверждения следует не что угодно (то, что из ложного утверждения следует что угодно, называется принципом ex falso quodlibet).