Какова явная причина доказательства от противного?

Кажется, в вашей проблеме есть несколько пересекающихся проблем с доказательством от противного.

1. У вас есть возражение против таблицы истинности для материального следствия:

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

2. Вы, кажется, неправильно понимаете доказательство от противного:

1. Покажите, что p -> q, где "->" — условное выражение. 2. Показать, что q ложно. 3. Выведите из таблицы истинности, что p должно быть ложным.

Начну со второго вопроса. Я бы сказал, что лучшее определение доказательства от противного выглядит следующим образом:

1. Учитывая Р, А
2. Учитывая P, а не A
3. Следовательно, учитывая P, A, а не A
4. Таким образом, не P из-за противоречия, когда P

Как вы правильно заметили, это отчасти связано с материальным значением. Но на самом деле речь идет не о том, чтобы доказать, что А ложно, а о том, чтобы доказать, что А и не А одновременно истинны. Но так как это невозможно в стандартной логике, то мы должны были ошибиться, приняв Р, следовательно, не Р.

Возвращаясь к теме стандартной логики, мы можем частично развеять ваши опасения по поводу материального следствия. Есть три фундаментальных правила, которым следует классическая логика:

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

Мы также можем выразить это кратко:

1. А = А
2. Для любого A, истинного или ложного
3. не (А и не А)

Материальная импликация — это логический оператор, оперирующий двумя терминами и живущий в этом мире. Его назначение — работать с условиями, т.е. местами, где значение одной переменной зависит от другой. Учитывая, что у нас есть 2 переменные, каждая из которых (по правилу 2 может иметь два значения), у нас есть четыре возможности.

Для А -> В,

1. А верно и Б верно
2. А верно, а Б ложно
3. А ложно, а Б верно
4. А ложно и Б ложно

Импликация проверяет, верна ли импликация. Таким образом, мы принимаем, что оно выполняется (видим, что все импликации верны), когда истинно А и истинно В. Мы также должны быть в состоянии увидеть, что импликация ложна, когда А истинно, но В ложно.

Ситуация немного сложнее и запутаннее, когда A ложно (если мы думаем «если, то», а не просто принимаем это как оператор). Совсем недавно объяснение, которое я давал на своих занятиях, было следующим:

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

Но дело в том, что нам это не нужно специально для доказательства от противного, потому что в доказательстве от противного мы показали, что некоторое предположение P приводит к противоречию. А противоречия недопустимы исходя из третьего правила. Следовательно, само предположение должно быть отвергнуто.

Доказательство от противного в общем случае не ограничивается использованием условного .

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

Что необходимо, так это понятие логического следствия или логического следствия .

Это понятие лежит в основе всей логики. Впервые это четко определил Аристотель :

Вся логика Аристотеля вращается вокруг одного понятия: дедукции ( sullogismos ). [...] Что же такое вычет? Аристотель говорит:

Дедукция — это речь ( логос ), в которой из предполагаемых вещей по необходимости возникает нечто отличное от этих предполагаемых, поскольку они таковы. ( Предварительная аналитика I.2, 24b18–20)

Каждая из «предполагаемых вещей» есть посылка ( protasis ) рассуждения, а какие «следствия необходимости» есть заключение ( sumperasma ).

Ядром этого определения является понятие «вытекающее из необходимости». Это соответствует современному понятию логических следствий : X неизбежно следует из Y и Z , если X не может быть ложным, когда Y и Z истинны. Таким образом, мы могли бы принять это за общее определение «действительного аргумента».

Таким образом, действительный аргумент - это аргумент, который из истинных предпосылок выводит верный вывод.

Если мы из множества посылок Γ ∪ {A} выводим что-то ложное , как противоречие , посредством правил логики, мы должны заключить, что по крайней мере одна из посылок ложна , потому что по определению логического следствия :

если все посылки верны, то обязательно верно и заключение .

Таким образом, мы заключаем, что утверждение A «ответственно» за противоречие и что оставшийся набор посылок Γ влечет отрицание A , т. е. ¬ A .

В вашем примере, если мы доказали

П → Q ,

то поступаем следующим образом:

1) предположим П

2) вывести ¬ Q ;

по modus ponens мы выводим из P → Q и 1) также:

3) В

Теперь у нас есть противоречие , и поэтому мы должны заключить, что наше исходное предположение P ложно , т.е.

4) ¬ П .

В другой форме, если P → Q и P → ¬Q , используя тавтологию : (P → Q) → ((P → ¬Q) → ¬P) , путем двух применений modus ponens мы заключаем с ¬P , что сводится к высказыванию:

¬ P является логическим следствием P → Q и P → ¬ Q .

В символах:

P → Q, P → ¬ Q ⊨ ¬ P

Явным обоснованием доказательства от противного являются два закона

«non (non A) = A» и «Если A => B и B false, то A false»

Эти законы выполняются в логике высказываний. Истинный метод доказывает второй закон.

Доказательство от противного применяет эти законы следующим образом: чтобы доказать истинность предложения «А», напротив, предполагается, что «А» ложно. т.е. "не А" правда. Из этого предположения за один или несколько шагов выводится определенное утверждение «В», которое оказывается ложным. Теперь «не A => B» и «B» ложно подразумевает «не A» ложно, следовательно, «A» истинно.

Метод, который вы описываете, не является «доказательством от противного», он называется «доказательством противоположного», что символически выражается как ¬q ⇒ ¬p . Это утверждение логически эквивалентно p ⇒ q . Важно понимать, что оба эти метода связаны с доказательством материальной импликации p ⇒ q , а не (повторяю , нет ) истинности p или q , как вы предполагаете в своих комментариях.

Как это работает? Утверждение p ⇒ q истинно, если только p не может быть истинным, а q ложным. [1]

В описанном вами методе доказательства контрапозитивности следует исходить из предположения, что q ложно, и показать, что из этого следует, что p должно быть ложно. Это означает, что p никогда не может быть истинным, а q ложным, поэтому можно заключить, что p ⇒ q согласно [1] .

В методе доказательства от противного предполагается, что p ⇒ q ложно, т. е. p истинно, q ложно (в отличие от [1] ), и показывается, что это предположение приводит к противоречию, позволяющему нам заключить, что p никогда не может быть истинным . и q ложь. Это эквивалентно высказыванию p ⇒ q , поскольку единственный случай, когда материальная импликация ложна, — это когда возможно p истинно, а q ложно.

Ваши комментарии относительно этих стратегий предполагают, что мы знаем, что p ⇒ q истинно, и затем мы получаем истинностные значения p и q . Это неверно ни в одном из способов доказательства — от противного или противного. Суть этих методов в том, чтобы доказать истинность p ⇒ q .

РЕДАКТИРОВАТЬ

По поводу ваших комментариев (ниже):

1. Как мы можем доказать материальную импликацию, если сначала не установим, какими должны быть истинностные значения p и q?

Оба эти метода работают, предполагая соответствующие значения истинности. В случае доказательства противоположного мы предполагаем, что q ложно, и показываем, что это вынуждает нас признать, что p также должно быть ложным. Вот пример доказательства противоположности:

( примечание: я приведу пример неформального аргумента, так как будет легче проследить, как работают методы. )

ПРИМЕР: Предположим, что n — положительное целое число, и мы хотим доказать, что:

• Если n ² четно, то n четно.

Чтобы использовать метод доказательства противоположного , мы предположили бы, что утверждение q (= n четно) ложно, и показали, что необходимым следствием этого предположения является то, что p (= n ² четно) также должно быть ложным.

Для этого предположим, что n нечетно. Тогда мы можем записать n как 2k+1 для некоторого положительного целого числа k . Следовательно, n ² = ( 2k+1 ) ² . Расширив это выражение и сгруппировав члены, мы можем записать это как n ² = 4(k ² +k)+1 . Поскольку 4(k ² +k)+1 нечетно (поскольку оно не делится на 2), мы показали, что предположение, что n не четно, заставляет нас заключить, что n ² нечетно. Таким образом, мы доказали: «Если n нечетно, то n ²нечетно», или, что то же самое, «Если n ² четно, то n четно». То есть, ¬ q ⇒ ¬p , что эквивалентно p ⇒ q .

Чтобы использовать метод доказательства от противного , мы предположили бы, что p ⇒ q ложно, и получили бы противоречие. Если p ⇒ q ложно, то существует натуральное число n такое, что n ² четно, но n нечетно. Но если n нечетно, то по тому же аргументу, что и в нашем примере с доказательством противоположного, мы должны иметь n ² также нечетно. Это противоречит нашему предположению, что p ⇒ q ложно, и поэтому мы можем заключить, что p ⇒ q должно быть истинным.

2. Используя метод доказательства противоположного, можете ли вы объяснить, почему мы можем показать, что p ложно, предполагая, что q ложно, без использования таблицы истинности? Или это то, что используется для установления этого?

Я считаю, что мои комментарии к вопросу 1 также отвечают на этот вопрос. Пример, который я привел, очевидно, является неформальным аргументом, но легко формализуемым.

Насколько я понимаю, доказательство от противного состоит из следующих шагов. 1. Показать, что p -> q, где «->» — условное выражение. 2. Показать, что q ложно. 3. Выведите из таблицы истинности, что p должно быть ложным.

Вы описываете modus tollens, а не доказательство от противного.

Если мы основываем истинность условного предложения на истинности p и q, как мы можем узнать, что условное выражение истинно, прежде чем узнать, истинны ли оба p и q?

Предположение в символической логике состоит в том, что мы знаем/верим, что условное (или другое допущение) истинно по какой-то причине вне символической логики. Может быть, вы считаете, что последствия очевидны или хорошо подтверждены научными данными. Это определенно не потому, что вы знаете истинное значение p и q.

Единственный сценарий, который приводит к такому результату, — это тот, в котором p также является ложным. Однако я никогда не был удовлетворен аргументом о том, что два ложных утверждения создают истинное следствие. Какие веские основания есть для того, чтобы с этим согласиться?

Во-первых, это фактически не меняет рассуждений о modus tollens. Если бы ложное -> ложное было либо ложным, либо неопределенным, все равно было бы так, что истина -> ложное является ложным. Учитывая, что q ложно, единственный оставшийся вариант состоит в том, что p ложно.

С моей точки зрения, вы не должны думать о материальных условных предложениях как об эквивалентных нашему понятию импликации в естественном языке. Наше понятие импликации в естественном языке больше похоже на понятие из логики предикатов:

(x)(Ax -> Bx)

Это говорит о том, что для всех x, если Ax истинно, Bx истинно. Тривиально верно, когда Ax ложно, но если Ax истинно, то Bx также должно быть истинным.

Рассмотрим предложение: если я президент, ты — Папа. Ни одно из утверждений не верно, но кажется неправильным утверждать, что вывод верен, потому что то, что я президент, не сделает вас папой. Но на самом деле мы имеем в виду что-то вроде того, что во всех возможных мирах, где я президент, вы папа.

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

Когда Γ — набор формул, а P — формула, обозначение

Γ ⊢ P

называется синтаксическим следствием , является утверждением, что существует дедуктивное доказательство P с использованием формул в Γ в качестве гипотез. например введение союза является аксиомой

P, Q ⊢ P ∧ Q

Одна из формулировок доказательства от противного такова:

Γ, P ⊢ Q
Γ, P ⊢ ¬Q
therefore
Γ ⊢ ¬P

В некоторых версиях логики есть символ ⊥, который означает «противоречие», и в этом случае мы, вероятно, вместо этого сформулируем это как

Γ, P ⊢ ⊥
therefore
Γ ⊢ ¬P

такие формы доказательств могут часто использовать

P, ¬P ⊢ ⊥

Условие можно рассматривать как средство преобразования понятия следования в пропозициональную форму; конкретно

Γ, P ⊢ Q      if and only if      Γ ⊢ P → Q

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

P, P → Q ⊢ Q

но вместо этого мы могли бы рассматривать его как тавтологию

⊢ (P ∧ (P → Q)) → Q

Точно так же мы можем перефразировать доказательство от противного как

(P → Q), (P → ¬Q) ⊢ ¬P

или как тавтология

⊢ ((P → Q) ∧ (P → ¬Q)) → ¬P

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

⊢ (P → ⊥) → ¬P

Есть еще одно обозначение

Γ ⊨ P

называется семантическим следствием . Поскольку мы говорим о логике высказываний, один из способов определить это состоит в том, что это утверждение о том, что каждая оценка истинности, которая делает каждое утверждение в Γ истинным, также делает P истинным.

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

Например, мы можем доказать

P ⊨ P ∨ Q

по таблицам истинности, то есть путем проверки того, что каждая строка таблицы истинности P = trueтакже имеет P ∨ Q = true.

Мы хотим, чтобы импликация вела себя так же: например,

Γ, P ⊨ Q      if and only if      Γ ⊨ P → Q

Заметим, что утверждение P⊨Q идентично утверждению

невозможно присвоить значения истинности таким образом, чтобы P было истинным, а Q ложным

Следовательно, строки в таблице истинности, для которых ложно, P→Qдолжны быть именно теми строками, где Pистинно и Qложно — ни больше, ни меньше.

Тогда волшебной вещью в логике высказываний (и в логике первого порядка) являются теорема полноты и теорема обоснованности, которые вместе говорят:

Γ ⊢ P      if and only if      Γ ⊨ P

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

Доказательство от противного — это метод НЕПРЯМОГО доказательства: вы добавляете отрицание того, что хотите условно доказать , к своим предпосылкам в поддоказательстве и показываете, что это приводит к противоречию с предыдущим шагом вашего доказательства. Таким образом, вы можете классически заключить, что то, что вы хотели доказать, должно быть правдой. Не все логики поддерживают эту форму рассуждений — например, интуиционистские логики не поддерживают, поскольку они не принимают безусловной логической эквивалентности между истинным утверждением и отрицанием этого утверждения как ложного.

Если я врежусь на большой скорости в фонарный столб, у меня пойдет кровь из носа. Мой нос не кровоточит. Поэтому я не столкнулся с фонарным столбом.

Вы спросили: «Если мы основываем истинность условного предложения на истинности p и q, как мы можем узнать, что условное выражение истинно, прежде чем узнать, истинны ли оба p и q?»

В примере p и q оба ложны. Я не врезался в фонарный столб, у меня кровь из носа не идет. Но условное верно . p -> q истинно в трех из четырех случаев: если p и q оба ложны, если они оба истинны, и если p ложно, но q истинно. Оно ложно только в том случае, если p истинно, а q ложно.