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

[ИС]

Объясните пожалуйста как так получается что если мы доказывает утверждение $A\Rightarrow B$ можо доказать $\overline{A} \Rightarrow \overline{B} $ и это будет означать, что $A\Rightarrow B$ ?

[gris]

только наоборот: $\overline{B} \Rightarrow \overline{A} $ и из этого следует $A\Rightarrow B$
А вдруг Вы интуиционист?

[VAL]

gris в сообщении #373374 писал(а):

только наоборот: $\overline{B} \Rightarrow \overline{A} $ и из этого следует $A\Rightarrow B$

Ну почему же?! Как у топикстартера даже проще. Допустим, что A - неверно. Но нам дано A. Противоречие!
У меня многие студенты так доказывают.
Быстро и эффективно. И главное от B вообще не зависит.

А еще можно доказать $A\Rightarrow B$, не используя A:
Допустим, что B верно. Что и требовалось доказать!
И такой способ я неоднократно встречал. И никаких тебе контрапозиций.

[rush]

A \Rightarrow B ~~~~~~~~~~~~~~~~~~ = ~~~~~~~~~~~~~~~~~~ \overline A \bigcup B

\overline B \Rightarrow \overline A ~~~~~~~~~~~~~~~~~~ = ~~~~~~~~~~~~~~~~~~ B \bigcup \overline A

[TOTAL]

rush в сообщении #373386 писал(а):

A \Rightarrow B ~~~~~~~~~~~~~~~~~~ = ~~~~~~~~~~~~~~~~~~ \overline A \bigcup B

Что здесь написано? Словами объясните, пожалуйста.

[ИС]

gris

Очепятался (( действительно, там должно быть $\overline{B} \Rightarrow \overline{A} $

Так как так получается что если мы доказывает утверждение $A\Rightarrow B$ , то можо доказать что $\overline{B} \Rightarrow \overline{A} $, и это будет означать, что $A\Rightarrow B$ ?

[gris]

совершенно верно. прямая теорема равносильна теореме, противоположной к обратной.

Диагонали ромба взаимно перпендикулярны.

Если диагонали четырёхугольника не взаимноперпендикулярны, то это не ромб.

но если четырёхугольник не ромб, то его диагонали могут быть взаимно перпендикулярны, а могут быть и не взаимно перпендикулярны

если диагонали четырёхугольника взаимно перпендикулярны, то это божет быть ромб или не ромб.

Почувствуйте разницу. Есть необходимые и достаточные условия. Иногда они совпадают.

[ИС]

ммм...

так...
Еще раз..

Если доказано, что из А=>B, то это означает:
1) Если А истинно, то и В истинно.
2) Если $\overline{B}$ истинное утверждение, то и $\overline{A}$ истинное. утверждение

Если доказать, что $\overline{B} \Rightarrow \overline{A} $, то это означает
1) если $\overline{B}$ истинно, то и $\overline{A}$ истинно.
2) Если А истинно, то и B истинно.


Ой.. так этож одно и тоже ))) я как-то раньше этого не замечал...
Т.е. Прямая теорема означает совершенно тоже самое что и обратная??? т.е. это прям совсем одно и тоже, только разница в написании? я нигде не ошибся?

[gris]

Только не обратная, а противоположная к обратной (то же самое, что обратная к противоположной)
$A\,\Rightarrow \,B$ - прямая
$B\,\Rightarrow \,A$ - обратная
$\overline{A}\,\Rightarrow \,\overline{B}$ - противоположная
$\overline{B}\,\Rightarrow \,\overline{A}$ - обратная к противоположной

[Виктор Викторов]

Есть закон контрапозиции:

$$A\to B\equiv \neg B\to \neg A$$

Предполагаем отрицание $B$ и получаем отрицание $A$. Пример: если число делится на четыре, то число делится на два. Докажу я это так: если число не делится на два, то число не делится на четыре. Разумно назвать такое доказательство доказательством от противного (предположили противное и получили противное).
Но любую вещь можно назвать трамваем. Об этом нужно только договориться. Так вот договорились, что закон контрапозиции отдельно, а приведение к абсурду и доказательство от противного это одно и то же. Таким образом приведение к абсурду (оно же доказательство от противного):

$$A\to B\equiv A\wedge \neg B \to C \wedge \neg C$$

$$A\to B\equiv A\wedge \neg B \to \neg A$$

$$A\to B\equiv A\wedge \neg B \to \neg B$$

Т. е. предположить противное и придти к абсурду. Наиболее ярко это представлено первой формулой. Детали смотрите в книге Юрия Шихановича "Введение в современную математику" страница 141. Книга доступна в сети.

Прямая теорема: если A, то B.
Обратная: если B, то A. (Может быть ложна, даже если прямая теорема истинна)
Противоположная: если не A, то не B.
Обратная к противоположной: если не B, то не A. (Истинна, тогда и только тогда, когда прямая теорема истинна)

Пример. Если число делится на 4, то оно делится на 2. (Истина)
Обратная: Если число делится на 2, то оно делится на 4. (Ложь)
Противоположная: Если число не делится на 4, то оно не делится на 2. (Ложь)
Обратная к противоположной: Если число не делится на 2, то оно не делится на 4. (Истина)

[epros]

Виктор Викторов в сообщении #373465 писал(а):

Но любую вещь можно назвать трамваем. Об этом нужно только договориться. Так вот договорились, что закон контрапозиции отдельно, а приведение к абсурду и доказательство от противного это одно и то же.

У Вас получается слишком много разновидностей трамваев, можно запутаться.

Приведение $X$ к абсурду - это когда мы из этого самого $X$ некий абсурд выводим. Далее возможны варианты:
- Можно приводить к абсурду $A \wedge \neg B$ (какие дальнейшие выводы из этого будут сделаны - другой разговор).
- Можно считать за абсурд $C \wedge \neg C$ (ибо мы, в отличие от Гегеля, закон противоречия уважаем).
- Можно считать за абсурд $\neg A$ (ибо исходили-то мы из $A \wedge \neg B$, стало быть $A$ подразумевалось).
- Можно считать за абсурд $B$ (по той же самой причине - $\neg B$ подразумевалось).
- И т.д., и т.п., множество трамваев марки "приведение к абсурду" неограниченно...

Доказательство же $X$ от противного - это когда приводится к абсурду "противное", т.е. $\neg X$. Некоторые считают ( ) что такой вариант приведения к абсурду является достаточно убедительным доказательством $X$. А ежели за $X$ у нас было принято $A \to B$, то некоторые считают, что его отрицанием является $A \wedge \neg B$, стало быть приводить к абсурду нужно именно его. Отсюда - та разновидность трамваев, о которой пишете Вы.

Но есть ещё разновидность того же трамвая под названием "контрапозиция": Это когда мы приводим $\neg B$ к $\neg A$, а потом начинаем думать, что бы это значило в том случае, если бы $A$ была в числе аксиом. А значило бы это, что тот же вывод можно проделать из $A \wedge \neg B$, т.е. мы имеем приведение $A \wedge \neg B$ к абсурду, а стало быть (как мы договорились это именовать) - доказательство $A \to B$ "от противного".

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

[VAL]

Виктор Викторов в сообщении #373465 писал(а):

$$A\to B\equiv A\wedge \neg B \to \neg B$$

Очень странная, мягко говоря, равносильность. Справа тавтология, а слева - нет.

[Виктор Викторов]

epros в сообщении #373645 писал(а):

Приведение $X$ к абсурду - это когда мы из этого самого $X$ некий абсурд выводим.

М-да. Продолжайте в том же духе. Я расписал закон контрапозиции и сведение к абсурду по Шихановичу. В основном я с ним согласен. Не согласен я с ним в терминологии. Я бы назвал закон контрапозиции

$$A\to B\equiv \neg B\to \neg A$$

доказательством от противного (как от меня и требовали на экзамене в далёком 1971 году) и также назвал бы доказательством от противного вот эти две формулы

$$A\to B\equiv A\wedge \neg B \to B$$

$$A\to B\equiv A\wedge \neg B \to \neg A$$

а вот эту формулу сведением к абсурду:

$$A\to B\equiv A\wedge \neg B \to C \wedge \neg C$$

-- Чт ноя 11, 2010 12:03:55 --

VAL в сообщении #373668 писал(а):

Виктор Викторов в сообщении #373465 писал(а):

$$A\to B\equiv A\wedge \neg B \to \neg B$$

Очень странная, мягко говоря, равносильность. Справа тавтология, а слева - нет.

Чего странного-то? Просто враньё. Должно быть:

$$A\to B\equiv A\wedge \neg B \to B$$

Спасибо!

[epros]

Виктор Викторов в сообщении #373671 писал(а):

М-да. Продолжайте в том же духе.

А что здесь Вам не понравилось? Для определения приведения к абсурду не нужны лишние навороты, поскольку определение содержится в самой формулировке: "приведение к абсурду". Я только об этой тривиальной вещи и хочу сказать.

Виктор Викторов в сообщении #373671 писал(а):

Я бы назвал ...

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

Да, можно договориться именовать формулу контрапозиции:
$(A \to B) \leftrightarrow (\neg B \to \neg A)$
"схемой доказательства от противного". Только придётся долго объяснять как эту схему нужно применять и почему таковое применение соответствует по смыслу доказательству от противного. А можно просто следовать общеупотребимому смыслу слов: "доказательство от противного" = "приведение к абсурду отрицания".

[Виктор Викторов]

(Оффтоп)

Несколько цитат из epros.

epros в сообщении #373645 писал(а):

У Вас получается слишком много разновидностей трамваев, можно запутаться.

epros в сообщении #373645 писал(а):

Но есть ещё разновидность того же трамвая под названием "контрапозиция":

epros в сообщении #373645 писал(а):

К чему я это? А к тому, что при общем определении понятия "трамвая" вряд ли будет правильно углубляться в описания его частных разновидностей.

epros в сообщении #373911 писал(а):

Для определения приведения к абсурду не нужны лишние навороты, поскольку определение содержится в самой формулировке: "приведение к абсурду".

epros в сообщении #373911 писал(а):

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

epros в сообщении #373911 писал(а):

Только придётся долго объяснять как эту схему нужно применять и почему таковое применение соответствует по смыслу доказательству от противного. А можно просто следовать общеупотребимому смыслу слов: "доказательство от противного" = "приведение к абсурду отрицания".