psilogic | Хана импликации :)

Entry tags:

логика

Хана импликации :)

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

Рассмотрим утверждение:

"Неправда, что если погода пасмурная, то идет дождь"

Это утверждение истинное во всех смыслах: действительно, пасмурная погода не всегда сопровождается дождем. Обычно верно обратное: при дожде практически всегда стоит пасмурная погода (ну кроме редких случаев "слепого дождика").

Переведем это на язык логики с импликацией. "Неправда, что" переводится операцией отрицания. Все утверждение формализуется как ~(A => B), где
A - истинность высказывания "погода пасмурная",
B - истинность высказывания "идет дождь".
Все высказывание в целом истинно, согласно рассуждениям выше.

~(A => B) = true

Левая часть будет истинна при единственной комбинации истинностей переменных: A = true, B = false. Таким образом, мы доказали, что: погода пасмурная всегда и дождь не идет никогда. Очевидно, что это противоречит реальности.

Threaded | Top-Level Comments Only

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

"Неправда, что если погода пасмурная, то (обязательно) идет дождь"

То есть это, строго говоря, просто не импликация.

При формализации мы привыкли игнорировать модальности, заменяя их, когда возможно, кванторами. Пусть S -- ситуация, о которой мы говорим (я когда-то обосновывал мысль, что истинностный статус возникает только в пределах ситуаций). Тогда по смыслу мы получаем вот что:

"Неправда, что во всех ситуациях выполнено условие: если погода пасмурная, то идёт дождь".

То есть на языке формул будет так:

~((\forall S)(A(S)=>B(S)))

Это логически эквивалентно вот чему:

(\exist S)(~(A(S)=>B(S)))

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

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

[ В данном случае в процитированной Вами фразе я "слышу" модальность ...
То есть это, строго говоря, просто не импликация. ]

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

Наверное, да. (С одной оговоркой, о которой ниже.)

Если истинностный статус A и B уже известен, и это некие фиксированные высказывания, то форма "если A то B" в обиходной речи неуместна. Естественнее просто сказать, что B истинно, или же ложно A. Но представим себе вот какое явление. Может оказаться, что речь идёт о фиксированных высказываниях с не известными пока истинностными значениями. Так часто бывает и в математике, когда доказывают, что положительный ответ на один вопрос влечёт положительный вопрос на другой. Причём можно рассмотреть такие случаи, когда A и B в принципе не зависят от переменных. Ну, например, если задача о тавтологиях исчисления высказываний решается детерминистски за полиномиальное время (ответ здесь только "да" или "нет"), то это же верно относительно задачи распознавания конечгого графа на предмет свойства "быть гамильтоновым".

Во всех этих случаях можно добавить модальности по такой схеме: "если окажется, что верно A, то необходимо выполняется B". Следует учитывать то, что модальности бывают разные. Когда модальность "онтологична" (то есть истинностный статус известен господу Богу в виде ответа "да" или "нет"), то её можно не привлекать. Если же мы мыслим оба ответа возможными (в смысле того, что нет оснований исключить ни один из них), то тогда меняется и смысл употребляемых модальностей.

Импликация налагает некие ограничения в форме того, что некоторые комбинации истинностных значений типа |A|=1, |B|=0 она считает невозможными. А это уже есть модальная форма.

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

Что касается гамильтоновых графов :) А нет ли там некоего более общего правила, леммы, теоремы типа: "если... задача x решается за полиномиальное время и есть определенная связь между задачами x и y, то задача y тоже решается за полиномиальное время"?

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

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

Гамильтоновы графы, распознавание тавтологий -- это всё примеры так называемых "NP-полных задач". Их общее количество количество исчисляется тысячами. Когда возникает новый вопрос о том, не будет ли задача X являться NP-полной, то подыскивается любая подходящая задача Y, про которую NP-полнота уже известна, а затем осуществляется прямое сведение одного к другому. То есть излагается явный алгоритм, который решает задачу Y за полиномиальное время при условии, что при помощи некой гипотетической подпрограммы задачу X за полиномиальное время мы умеем решать.

Суть в том, чтобы установить "максимальную сложность" задачи X, то есть обосновать, почему умение её решать "быстро" (за полиномиальное время) влечёт возможность решать столь же быстро все остальные задачи из длинного списка NP-полных.

Интерес представляют трудные задачи, про которые NP-полнота не имеет места, или же это не известно. Скажем, если дано n-значное число, то надо за время n^k, где k=const, распознать это число на простоту. Уже в XXI веке появилась работа трёх индийских математиков (я её подробно разбирал), где это осуществлено. А вот для разложения n-значного числа на простые множители пока ничего не известно. Можно наперёд знать, что n=pq, где p и q -- простые. Скажем, я нашёл большие простые числа, перемножил их, а потом послал Вам ответ. Но находить сами множители по числу n за полиномиальное время пока никто не умеет.

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

[ При желании всегда можно сказать, что модальность наличествует, и я объяснил причину. ]

Ага. Но тогда возвращаемся к первому вашему коменту, где вы говорите, что из-за модальности эта импликация как бы и не импликация вовсе ;) Но, если модальноеть есть всегда, то выходит, что всякая импликация - не импликация - бррр! :))))

Про задачи я почему спросил. Получается, что там все-таки есть некие переменные - в высказывании более общего вида (если задача X ..., то задача Y...) Когда на место переменных подставляются конкретные задачи, то получается высказывание без переменных. Если после подстановки запретить дальнейшие преобразования подставленных частей, то похоже, что удается решить все парадоксы. А если разрешить - то получаются новые. Кажется, я придумал, как разобраться со всеми этими парадоксами, осталось найти время, чтобы оформить это дело :)

У меня есть ощущение, что Вы верно уловили самое основное, что я сказал.

В данном контексте приходится (по традиции) обходиться без модальностей, используя обычные средства исчисления предикатов. (Хотя на самом деле здесь есть выход за их рамки, но это обстоятельство несущественно.) Оттенок "возможно" мы передаём квантором существования, а оттенок "необходимо" -- квантором всеобщности. При этом любая (или почти любая) импликация, встречающаяся "в быту" -- это утверждение вида "для всех ситуаций S верно, что A(S)->B(S)", то есть "по умолчанию" имеется квантор по всем ситуациям, а внутреннюю импликацию можно считать "математической" (или "материальной", как Вы любите говорить).

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

Да, действительно, многие парадоксы разрешаются, если ввести упущенный квантор. Насколько я понимаю, это впервые сделал еще Кларенс Льюис, и он играл именно с модальностями (в strict implication). А потом модальности попытались выразить через кванторы, используя концепцию множественных миров. Но вариант Льюиса тоже несвободен от парадоксов (у него из лжи уже не следует все, но вот из противоречия следует все), так что приходится идти дальше. Я как-то попытался придумать формулу, которая обходит парадоксы strict implication но наткнулся на следующую серию парадоксов :) Сейчас меня осенила очередная идея, так что может что и получится.

Пока такой вариант:
Если A то B истинно при выполнении следующих условий:
1. Tr(A) = a(x, y, z,...) - то есть, истинность текста A выражается некой функцией-предикатом a от переменных x, y, z,...
2. Tr(B) = b(x, y, z,...) - то есть, истинность текста A выражается некой функцией-предикатом b от переменных x, y, z,...
3. При этом не обязательно, чтобы наборы переменных в a и b были одинаковы, но существенно обозначать одинаковыми переменными одинаковые элементы текстов A и B.
4.
\exist x \exist y \exist z... a(x, y, z,...)
&
\exist x \exist y \exist z... ~b(x, y, z,...)
&
~ \exist x \exist y \exist z... (a & ~b(x, y, z,...))
- то есть, a хотя бы иногда (при некоторых x, y, z,...) равно true, b хотя бы иногда false, но не одновременно. Если все эти условия выполняются, то также можно вывести, что a хотя бы иногда false, b хотя бы иногда true.

Также можно подставлять на место переменных некие конкретные значения из области допустимых, получая высказывания вида "Если A(x0) то B(x0)", и эти высказывания тоже будут считаться истинными (но обязательно прежде должно быть доказано высказывание без подстановки).

И, наконец, похоже, придется запретить рассматривать в функции Tr в качестве текстов A и B выражения вида true, false, x & y - в общем, логические функции. Т.е. надо очень строго разделять истинность текстов и функции истинности, которые выражают эту истинность. Сами по себе функции истинности могут иметь значения, но не могут иметь истинности.

Вот как то так, развернуто оформлю как-нибудь позднее.

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

А в чём собственно парадокс тогда?

Напоминает как один политолог спрашивал согласны ли мы с утверждением что "цель оправдывает средства" с таким видом вроде это вопрос на который мы скажем "да/нет" ...

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

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

[ А в чём собственно парадокс тогда? ]

Тогда - когда? Если изменить формализацию, тогда ни в чем.

Рассмотрите тот же пример, но для определенного, конкретного времени и места. Что получится?

[Тогда - когда? Если изменить формализацию, тогда ни в чем.]
да. я просто подумал мало ли. вдруг какая-то глубинная парадоксальность. А так - нормально.

[Рассмотрите тот же пример, но для определенного, конкретного времени и места. Что получится?]
Не вопрос, рассматриваем. Хотя это уже совсем другие фразы и другой пример.
1. В контексте неизвестно (предполагается что может быть неизветным) есть ли дождь/пасмурность в конкретном времени/месте. Тогда фраза приобретает ощутимый оттенок логического вывода, который теряется при указанной формализации. Если воспринимать как фразу "Неправда, что из того что позавчера в Киеве было пасмурно можно сделать вывод что позавчера в Киеве был дождь", то опять никаких парадоксов.

2. В контексте достоверно известно что вот сейчас прям пасмурно и дождя нет (например). Тогда фраза приобретает смысл глупости/шутки в обычном языке. Т.к. никто обычно не говорит "Неправда, что если сейчас здесь пасмурно, то сейчас здесь идёт дождь" гуляя по дождю в пасмурную погоду (или при какой-то другой погоде). Т.е. это будет воспринято как бессмысленные рассуждения или как пример к варианту 1.

Т.е. тут опять вылазит "материальная импликация" про которую я в принципе уже вроде писал как-то давно в коментах, что никаких парадоксов, главное не путать тёплое с мягким. (Дословно не помню что тогда писал, но вряд-ли моё мнение могло так быстро поменяться)

Рассмотрим случай 1.

[ "Неправда, что из того что позавчера в Киеве было пасмурно можно сделать вывод что позавчера в Киеве был дождь" ]

Эта фраза истинна?

Да, истинна.

З.Ы. уточнение "можно сделать вывод"="можно сделать корректный вывод в рамках логики А" (да, я зануда). Иначе фраза вообще говоря ложна конечна, т.к. вывод сделать можно. просто этот вывод не будет соответствовать какой-то логике/действительности. Но это уже занудство :))

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

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

Иначе можно придумать "=>" которое означает "выводится в системе/логике ААА". Но это уже сложнее и зависит от логики ААА. В разных логиках "А => В" может быть по разному связано с "А ИЛИ НЕ В". Примерно так.

т.е. правильно ли я вас понял: по-вашему, эта конкретная фраза не может быть формализована без потери смысла в виде
~(A => B) = ~(A & ~B), где
A истинность фразы "позавчера в Киеве было пасмурно"
B истинность фразы "позавчера в Киеве шел дождь"
?

Да, абсолютно правильно. В рамках булевой логики не может. То что выглядит как (A => B) следует рассматривать как элементарное утверждение С, истинность которого устанавливается какими-то другими средствами.

Да, если что, под "=>" в коменте выше я имел ввиду естественно обычную логическую импликацию, которая выражается через ИЛИ и НЕ.

(кстати там в формуле опечатка (A => B) не равно (A & ~B))

Да, опечатка, конечно, скопипастил "~" :)
Правильно:
~(A => B) = (A & ~B)
Вы писали, что более логично утверждение "существуют ситуации когда погода пасмурная, дождь не идёт".
То есть,
\exist x : A(x) & ~B(x) =
~ \forall x : ~(A(x) & ~B(x)) =
~ \forall x : ~A(x) V B(x) =
~\forall x : A(x) => B(x)

A(x) истинность фразы "в x пасмурно"
B(x) истинность фразы "в x шел дождь"
x - координаты и время.

А это, по-вашему, правильная формализация?

ну да. всё правильно. \exist x : A(x) & ~B(x) = ~\forall x : A(x) => B(x) это я само собой подразумевал. Т.е. посчитал эту цепочку достаточно очевидной (она ж часто в математике применяется, т.н. опровержение через "контрпример").
Просто фраза "существуют ситуации когда погода пасмурная, дождь не идёт" лучше звучит и имеет меньше дополнительных смыслов и неясностей чем исходная.

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

Согласен. Слишком много дополнительных смыслов. Т.е. наверное в некоторых случаях "если" будет уместно, а в некоторых нет. В частности в повседневной жизни частенько неуместно. В математике же скорее да чем нет, особенно в логике исчислений (или как оно по русски называется... ну там ещё формулы логические есть , которые аксиомы штук 3-10 , и правила вывода) так там даже теорема есть что если выводится так импликация и наоборот.

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

Threaded | Top-Level Comments Only

Page 4 of 4

Хана импликации :)

разгадка

Re: разгадка

есть ли модальный "привкус"?

вы меня запутали :)

NP-полнота

Re: NP-полнота

пропущенное

Re: пропущенное

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject