Можно ли обойтись без доказательства от противного

[alex1910]

Пусть доказано, что A <--> B. (1)

Из (1), разумеется, следует, что не A <--> не В. (2).

Можно ли, имея (1), доказать (2), не используя доказательство от противного?

[caxap]

Вроде бы в закон контрапозиции ($(A\to B)\leftrightarrow (\neg B\to\neg A)$) даже интуционисты верят.

[alex1910]

caxap в сообщении #452289 писал(а):

Вроде бы в закон контрапозиции ($(A\to B)\leftrightarrow (\neg B\to\neg A)$) даже интуционисты верят.

То есть либо доказательство от противного, либо логика с аксиомой "закон контрапозиции"? А без аксиомы (и доказательства от противного) никак?

[caxap]

Если бы можно доказать иначе, то зачем бы тогда вообще вводили эту аксиому?

(Оффтоп)

У меня лишь поверхностные познания в логике (в объеме половины 2-й книжки Верещагина--Шеня), но, насколько я понял, в контрапозицию верят все (она уж слишком интуитивно очевидна). Недоверие вызывает только закон снятия двойного отрицания (с его помощью, в частности, можно доказывать теоремы от противного), а остальные аксиомы вроде как все принимают.

Но не воспринимайте все мои высказывания в этой теме серьёзно. Лучше подождать более квалифицированных ответов.

[alex1910]

Так есть разные исчисления с разным количеством аксиом.
И не факт, что контрапозиция есть везде. Также не уверен, что эта аксиома независимая.

UPD. Если верить википедии, то в Гильбертовой системе аксиом контрапозиции нет: http://ru.wikipedia.org/wiki/%D0%98%D1% ... 0%B8%D0%B9

[iig]

Надо доказывать не тодько истинность исходного положения, но и неистинность противоположного.
Последнее и есть от противного, но из него не следуеит истинность первого.

по этому поводу моя логика четырехзначная:

Да- значит дам (денги)
Нет -не дам
Не знаю-в другой раз
А кто ты такой?

Извиняюсь за легкий флейм, но по смыслу подходит

Да - достаточность
Нет - необходимость
Не вышел степенью с профессорами спорить
Вопрос не стоит моего внимания.

[BapuK]

alex1910 в сообщении #452319 писал(а):

Так есть разные исчисления с разным количеством аксиом.
И не факт, что контрапозиция есть везде. Также не уверен, что эта аксиома независимая.

UPD. Если верить википедии, то в Гильбертовой системе аксиом контрапозиции нет: http://ru.wikipedia.org/wiki/%D0%98%D1% ... 0%B8%D0%B9

аксиомы то нет, но данная формула является теоремой в Гильбертовском исчислении высказываний

[alex1910]

BapuK в сообщении #456444 писал(а):

alex1910 в сообщении #452319 писал(а):

Так есть разные исчисления с разным количеством аксиом.
И не факт, что контрапозиция есть везде. Также не уверен, что эта аксиома независимая.

UPD. Если верить википедии, то в Гильбертовой системе аксиом контрапозиции нет: http://ru.wikipedia.org/wiki/%D0%98%D1% ... 0%B8%D0%B9

аксиомы то нет, но данная формула является теоремой в Гильбертовском исчислении высказываний

В Гильб. исч. высказываний есть 10-я или 11-я аксиома, применение которой эквивалентно доказательству от противного.

И я не уверен, что можно вывести желаемое без этой аксиомы - так что вопрос остается открытым.

[man]

alex1910 в сообщении #452262 писал(а):

Пусть доказано, что A <--> B. (1)
Из (1), разумеется, следует, что не A <--> не В. (2).
Можно ли, имея (1), доказать (2), не используя доказательство от противного?

Нет, если подразумевается снятие двойного отрицания.

[alex1910]

Оно и подразумевается. А как доказать, что "нет"?

[beroal]

caxap в сообщении #452289 писал(а):

Вроде бы в закон контрапозиции ($(A\to B)\leftrightarrow (\neg B\to\neg A)$) даже интуционисты верят.

Ваша формула логически эквивалентна снятию двойного отрицания. Поэтому не верят. Однако верят в более слабую $(A\to B) \to (\neg B\to\neg A)$

-- Sun Jun 12, 2011 20:41:37 --

alex1910 в сообщении #456545 писал(а):

BapuK в сообщении #456444 писал(а):

аксиомы то нет, но данная формула является теоремой в Гильбертовском исчислении высказываний

В Гильб. исч. высказываний есть 10-я или 11-я аксиома, применение которой эквивалентно доказательству от противного.
И я не уверен, что можно вывести желаемое без этой аксиомы - так что вопрос остается открытым.

Путаница в вопросе. Вы называете «доказательство от противного» то аксиомой, то теоремой. В любом доказательстве можно избавиться от упоминания любой теоремы: замените упоминание теоремы T на доказательство теоремы T. Если же «доказательство от противного» есть аксиома, то скажите, в какой системе аксиом?

[alex1910]

Это у Вас путаница.

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

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

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

Пример: число рационально <--> его непрерывная дробь конечна. (A)

Можно ли, исходя из (A), доказать (B)

число иррационально <--> его непр. дробь бесконечна (B)

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

[epros]

alex1910 в сообщении #457462 писал(а):

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

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

Если в качестве "какого-либо альтернативного исчисления" взять конструктивную логику, то ответ здесь:

beroal в сообщении #457227 писал(а):

caxap в сообщении #452289 писал(а):

Вроде бы в закон контрапозиции ($(A\to B)\leftrightarrow (\neg B\to\neg A)$) даже интуционисты верят.

Ваша формула логически эквивалентна снятию двойного отрицания. Поэтому не верят. Однако верят в более слабую $(A\to B) \to (\neg B\to\neg A)$

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

[beroal]

alex1910 в сообщении #457462 писал(а):

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

Это уже похоже на фричество. Ну докажите, что они фактически эквивалентны.

Дальше я привёл доказательство, которое IMO наиболее релевантно вашему вопросу. Возьмём гильбертовскую систему из Википедии. C помощью естественного вывода выводим
$A_{10} \vdash (A\to B) \to (\neg B\to\neg A)$
$A_3, A_4, A_5, (A\to B) \to (\neg B\to\neg A) \vdash (A \leftrightarrow B) \to (\neg A \leftrightarrow \neg B)$
(могу подробнее, но это надо рисовать диаграммы). Согласно теореме о дедукции, естественный вывод транслируется в $MP, A_1, A_2$. Таким образом, вывод не использует $A_{11}$ (исключение третьего), которая эквивалентна снятию двойного отрицания.

[gefest_md]

В аппарате логики есть также формулы:
1. $(A\to\neg A)\leftrightarrow\neg A$
2. $(\neg A\to A)\leftrightarrow A$
Некоторые авторы на первую ссылаются, когда упоминают метод "reductio ad absurdum".