Самые распространенные логические заблуждения

[psilogic]

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

Миф 4.
Гёдель доказал, что нельзя доказать все

Миф состоит в том, что теоремы Гёделя применяют там, где их применять нельзя. Что именно доказал Гёдель (и его последователи)? Они доказали, что в аксиоматической системе, основанной на классическом исчислении предикатов и арифметике Пеано, существуют недоказуемые утверждения, и среди таких утверждений - непротиворечивость системы.

Пояснения к терминам:

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

"Классическое исчисление предикатов" (КИП) - аксиоматическая система, описывающая основные логические операции: "и", "или", "не", а также предикаты и два квантора ("для всех" и "существует"). Это совсем не то же самое, что булева алгебра, привычная программистам, но некий ее "дальний родственник". Есть множество вариантов КИП по-разному построенных и в разной степени "навороченных". Вот, некий вариант используется в теореме Гёделя.

И сразу одна "неприятность": обычно в КИП используется та самая аксиома
A => (B => A).

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

"Основанной на" - то есть, некая аксиоматика, в которой есть аксиомы КИП, аксиомы арифметики Пеано, и может быть еще какое-то количество аксиом, добавленных с некоторыми оговорками.

Что это может быть за система? Ну например, некая значительная часть математики, скажем, весь матанализ (дифференциальное и интегральное исчисление). Вот если попытаться выстроить "матан" именно как аксиоматическую систему на базе КИП и арифметики Пеано, то получится нечто (аксиоматизированный матан).

И это нечто не сможет доказать отсутствие противоречий в самом себе.

А еще что не сможет доказать? Про любую произвольную формулу нельзя сказать, можно ее доказать или нет, но вот по крайней мере отсутствие противоречий доказать нельзя.

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

Каково практическое применение этой теоремы вне математики? Похоже, что никакое. Вне математики строгие аксиоматические системы не используются. В естественных науках как метод доказательства применяется эксперимент, неполная индукция, разные нестрогие (по меркам математики) рассуждения, которые к аксиоматическим системам отношения не имеют.

Тем не менее, Гёделя постоянно поминают всуе. Обычно это происходит, когда кто-нибудь пытается обосновать свой "гносеологический пессимизм" (С) falcao. То бишь, заявить, что некую проблему невозможно решить или некое утверждение невозможно доказать. И дальше следует ссылка на Гёделя. Но то, что невозможно доказать согласно Гёделю, обычно не равно тому, что обсуждается. Создается впечатление, что Гёдель дал этим товарищам своего рода индульгенцию: право ставить клеймо "недоказуемо" на произвольно выбранные утверждения.


Миф 5.
Нельзя все доказывать, надо что-то принимать на веру

Начну с простого примера. Пусть у вас есть уравнение: x + 5 = y. Уравнение в действительных числах. Пусть нам даже известен повод, по которому уравнение было составлено. Скажем, нам стало известно, что цена за бутылку пива "Уебалтика" на 5 рублей выше, чем цена за бутылку пива "Хуевское". Переменные x и y как раз выбраны по первым буквам марок пива.

Мы знаем, что величина x - вполне определенное число, выражающее цену в рублях, но не знаем, какое именно Из уравнения мы можем получить следствия, например, узнать, насколько дешевле обойдется ящик хуевского пива. Обратите внимание, что мы не обязаны верить в то, что переменная x равна конкретному числу 20, 30 или 40.

Примерно так же обстоит дело во всех других случаях, когда вам навязывают мысль, что надо непременно во что-то верить. Кроме состояний "истина" и "ложь", есть еще куча переменных с неизвестными значениями. Это не третье состояние, это вообще "перпендикулярная" характеристика. Например, если вы хотите заключить сделку и не уверены в честности партнера, то должны ли вы непременно уверовать в его честность или уверовать в его нечестность? Не лучше ли сохранить трезвомыслие и сказать себе: я не знаю, обманет ли он меня, я осознаю, что есть риск и действую с учетом этого риска?

Наброс: если девушка клянется вам в любви, должны ли вы ей верить?


Миф 6.
Бинарная логика – отстой, нечеткая спасет мир

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

Я люблю приводить пример про желтого цыпленка.

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

Когда наступает этот момент? Какой процент тела должен сменить цвет, чтобы утверждение "цыпленок желтый" стало ложным (заметьте: это пока двузначная логика)?

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

Уверен, вы сталкивались с такими процентами в жизни. Это - выборы. Хорош ли кандидат в президенты Волков? 40% избирателей считают, что да. Не истина и не ложь. Это и есть нечеткая логика. Ну и как... спасает она мир? :)

Comments

[psilogic.livejournal.com]

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

Для той логики, которой мы пользуемся повседневно, в том числе, когда в научной или учебной литературе пишут доказательства текстом для этой логики (назову ее условно ЛПУ - логикой по-умолчанию) интерпретация такова:

1. Аксиомы истинны.
2. Все утверждения, выводимые из аксиом - истинны.
3. Все утверждения, которые являются отрицанием истинных утверждений - ложны.
4. Для оставшихся утверждений истинность неопределена.

Обратите внимание: невыводимые утверждения поделились на два класса: ложные и неопределенные. X ложно, если можно вывести (не Х). Если мы не можем вывести ни X, ни (не X) - это что-то неопределенное - не ложь, не истина, не третье значение истинности, а аналог неизвестной числовой переменной в математике. Совсем плохо, когда можно вывести и X, и (не X) - такая ситуация называется "противоречивой теорией", и для ЛПУ означает, что непорядок в аксиомах - надо их менять.

Теперь ваш пример. Это у вас самый обыкновенный парадокс лжеца.

"Это утверждение ложно". Обозначим это утверждение как X. Оно утверждает ложность самого себя - эдакая рекурсия, ну пусть будет рекурсия. Утверждение означает (см. выше), что есть вывод обратного: (не X).
Метод доказательства от противного требует для начала рассмотреть отрицание этого. Что будет отрицанием? Им будет утверждение, что нет вывода (не X) - т.е. что оно невыводимо. Невыводимо - значит ложно или неопределенно. Ложно - ведет к противоречию, остается - неопределенно. Вывод - утверждение в парадоксе лжеца является невыводимым с неопределенной истинностью.

[bsivko.livejournal.com]

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

Из ложных тогда получается нельзя выводить истинные? Т.е. если мы знаем, что не-A ложно, то мы не можем вывести, что A истинно? Т.е. надо обязательно искать истинное и из него выводить?

---

Сейчас пытаюсь разобраться с док-вом от противного, а парадокс лжеца просто пример. На нем как-то не совсем получается донести мысль.. Попробуем с примером в вики? там где корень из 2-х:
http://ru.wikipedia.org/wiki/Доказательство_от_противного

Изначально есть утверждение (Y): "\sqrt{2} рационально".
Так понимаю, что Y изначально может находится в одном из 3-х состояний:
[1] выводимо и истинно ("\sqrt{2} рационально").
[2] ложно ("\sqrt{2} не является рациональным").
[3] невыводимо (неизвестно, рационально \sqrt{2} или нет и узнать в рамках данной теории невозможно).

Теперь попробуем док-ть, как в вики. Допустим противное Y: "\sqrt{2} рационально" (то, что выполняется [1], т.е. что Y в состоянии [1]). Потом бла-бла-бла, приходим к противоречию. В качестве вывода в вики написано:

"Значит, исходное предположение было неверным, и \sqrt{2} — иррациональное число."

Каким образом?

Мы приняли, что Y выполняется. Ничего не вышло. Я так понимаю, что из этого следует, что Y не может находится в состоянии [1] ( выводимо и истинно ("2 рационально") ), но может находится в состоянии [2] или [3]. Но в вики делается вывод о том, что Y находится в состоянии [2], т.е. это не рациональное число. Почему утверждение не может находится в состоянии [3], т.е. быть невыводимым?

[psilogic.livejournal.com]

[ Мне почему-то всегда казалось, что ложные утверждения также выводятся. Т.е. например если нам известна истинность A, то мы можем сделать вывод (т.е. вывести), что не-A ложно. ]

Тут две очень важные оговорки. Во-первых, да, ложные выводятся. Но во-вторых то, что вы привели не ложное!

Начну со второго.

Высказывание "не-А ложно" истинно и мы его можем вывести, да. Однако это не будет высказывание просто "не А"! Если вспомнить правила булевой алгебры, то сравните:
~ A = false
и просто
~ A
Когда A истинно, первое истинно, второе - ложно.

Теперь о первой оговорке.

Ложное утверждение можно вывести, но не из аксиом! Его можно вывести из так называемой "гипотезы" - так называют утверждения, которые сами пока ниоткуда не выведены.

И вот в этом как раз заложен метод от противного. Если мы из гипотезы G вывели A, про которое известно, что оно ложно, то мы тем самым вывели не-G. То есть тогда не-G выводимо и истинно, не-A тоже выводимо и истинно, а A и G невыводимы и ложны.

Или схематично:

Если ((если G то A) и не A) то (не G)

[ Я так понимаю, что из этого следует, что Y не может находится в состоянии [1] ( выводимо и истинно ("2 рационально") ), но может находится в состоянии [2] или [3]. ]

Нет, идея док-ва от противного в том, что состояни [3] тогда быть не может. Отличие от парадокса лжеца в том, что там мы не смогли получить ложное утверждение на выходе.

[bsivko.livejournal.com]

> Во-первых, да, ложные выводятся. Но во-вторых то, что вы привели не ложное!

Я как раз имел ввиду, что можно вывести то, что ~A является ложным.

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

> И вот в этом как раз заложен метод от противного. Если мы из гипотезы G вывели A, про которое известно, что оно ложно, то мы тем самым вывели не-G. То есть тогда не-G выводимо и истинно, не-A тоже выводимо и истинно, а A и G невыводимы и ложны.

Только так понимаю что в конце A и G выводимы и ложны.

После некоторых размышлений над всем этим пришёл к следующим выводам.
В теории мы изначально имеем набор аксиом. Они являются истинными утверждениями. Автоматически, если мы к аксиомам прикрутим "не", то получим набор ложных утверждений (например есть аксиома А, значит мы автоматически получаем, что ~A имеет значение "ложно").
Далее по правилам вывода мы можем получать новые утверждения. Если мы из A вывели B, то оно истинно, что автоматически означает, что ~B является ложным.
(?) Аналогично по ложным утверждениям мы тоже можем (или не можем?) применять правила вывода. Например если мы имеем ~A, которое является ложным, то можем попробовать из него вывести C, которое будет тоже ложным. Применив отрицание, можно получить ~C, которое будет уже истинным.
Док-во от противного. Мы берем произвольное утверждение D. И пытаемся из него вывести какое-нибудь известное (истинное или ложное утверждение). Если мы выводим ложное, то получается, что D ложно, соответственно ~D истинно, что и требовалось док-ть. Если же мы выведем истинное, то это означает, что D истинно, и соответственно ~D ложно, и все это уже будет выглядеть как обычное док-во по правилам вывода без противного.

Все верно?

[psilogic.livejournal.com]

[ Только так понимаю что в конце A и G выводимы и ложны. ]

Нет, именно НЕвыводимы - в том смысле, что мы не сможем вывести их из аксиом. Но поскольку "выводить" можно не только из аксиом, то термин "выводимо" чреват путаницей.

[ Аналогично по ложным утверждениям мы тоже можем (или не можем?) применять правила вывода. ]

Можем. С той оговоркой, что некоторые правила вывода требуют в каких-то местах истинные утверждения, в каких-то местах ложные, а в каких-то местах ничего не требуют.

[ Если же мы выведем истинное, то это означает, что D истинно, ]

Неверно (перед этим все верно). Вот как раз пример, когда есть требование. Доказательство от противного - это тоже правило вывода. Оно требует, чтобы на выходе из D получилось ложное E, и тогда тем самым доказывается, что D ложно, а ~D истинно. Но если на выходе получается истинное E, то применять док-во от противного нельзя.

[bsivko.livejournal.com]

> Нет, именно НЕвыводимы - в том смысле, что мы не сможем вывести их из аксиом. Но поскольку "выводить" можно не только из аксиом, то термин "выводимо" чреват путаницей.

Из ложности не-A мы не можем получить истинность не-не-А=A? Или двойное отрицание превращается в "невыводимо или истинно"?

> Неверно (перед этим все верно). Вот как раз пример, когда есть требование. Доказательство от противного - это тоже правило вывода. Оно требует, чтобы на выходе из D получилось ложное E, и тогда тем самым доказывается, что D ложно, а ~D истинно. Но если на выходе получается истинное E, то применять док-во от противного нельзя.

То, что док-во от противного в этом случае аннулируется, я понял. Но вопрос чуть в другом. Например мы имеем две аксиомы:
a = b + 1
a = 2
допустим противное: b = 1 (X)
тогда a = 1 +1, и a = 2. Противоречия нет. Понятно, что док-во противного уже использовать нельзя. Но означает ли наша цепочка рассуждений, что X истинно? Или эта цепочка вообще ничего не означает?

[psilogic.livejournal.com]

[ Из ложности не-A мы не можем получить истинность не-не-А=A? Или двойное отрицание превращается в "невыводимо или истинно"? ]

да, можем получить. я ж говорю - термин "выводимо" - неудачный.

[ Или эта цепочка вообще ничего не означает? ]

вообще ничего

[bsivko.livejournal.com]

Мирослав, спасибо за разъяснения.

[psilogic.livejournal.com]

Док-во от противного также называют еще modus tollens.

На входе:
(если A то B) - истинно
(B) - ложно
На выходе:
(A) - ложно

А для чисто истинных есть modus ponens:

На входе:
(если A то B) - истинно
(A) - истинно
На выходе:
(B) - истинно

При этом многие правила можно юзать рекурсивно, по схеме: если где-то когда-то на входе было A, а на выходе B, то тем самым доказано:
"если A то B" - истинно.

[bsivko.livejournal.com]

С фокуса на modus tollens вроде как понятно, и чуть прояснилось..

А что происходит в случае, если при док-ве от противного мы берем некоторое противное утверждение Z, которое на самом деле невыводимое, но мы об этом не знаем? Получится, что мы не сможем ничего доказать (выйти на известные истинные или ложные), или мы можем все таки выйти на какие-то известные или ложные?

И становится непонятным, можно ли каким-либо образом доказать, что Z невыводимо?

[psilogic.livejournal.com]

доказать, что что-то нельзя доказать обычно довольно трудно