![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Entry tags:
Хана импликации :)
На одном форуме нашел очередной "парадокс" импликации. Самый убойный из всех, что я знаю.
Рассмотрим утверждение:
"Неправда, что если погода пасмурная, то идет дождь"
Это утверждение истинное во всех смыслах: действительно, пасмурная погода не всегда сопровождается дождем. Обычно верно обратное: при дожде практически всегда стоит пасмурная погода (ну кроме редких случаев "слепого дождика").
Переведем это на язык логики с импликацией. "Неправда, что" переводится операцией отрицания. Все утверждение формализуется как ~(A => B), где
A - истинность высказывания "погода пасмурная",
B - истинность высказывания "идет дождь".
Все высказывание в целом истинно, согласно рассуждениям выше.
~(A => B) = true
Левая часть будет истинна при единственной комбинации истинностей переменных: A = true, B = false. Таким образом, мы доказали, что: погода пасмурная всегда и дождь не идет никогда. Очевидно, что это противоречит реальности.
Рассмотрим утверждение:
"Неправда, что если погода пасмурная, то идет дождь"
Это утверждение истинное во всех смыслах: действительно, пасмурная погода не всегда сопровождается дождем. Обычно верно обратное: при дожде практически всегда стоит пасмурная погода (ну кроме редких случаев "слепого дождика").
Переведем это на язык логики с импликацией. "Неправда, что" переводится операцией отрицания. Все утверждение формализуется как ~(A => B), где
A - истинность высказывания "погода пасмурная",
B - истинность высказывания "идет дождь".
Все высказывание в целом истинно, согласно рассуждениям выше.
~(A => B) = true
Левая часть будет истинна при единственной комбинации истинностей переменных: A = true, B = false. Таким образом, мы доказали, что: погода пасмурная всегда и дождь не идет никогда. Очевидно, что это противоречит реальности.
разгадка
"Неправда, что если погода пасмурная, то (обязательно) идет дождь"
То есть это, строго говоря, просто не импликация.
При формализации мы привыкли игнорировать модальности, заменяя их, когда возможно, кванторами. Пусть S -- ситуация, о которой мы говорим (я когда-то обосновывал мысль, что истинностный статус возникает только в пределах ситуаций). Тогда по смыслу мы получаем вот что:
"Неправда, что во всех ситуациях выполнено условие: если погода пасмурная, то идёт дождь".
То есть на языке формул будет так:
~((\forall S)(A(S)=>B(S)))
Это логически эквивалентно вот чему:
(\exist S)(~(A(S)=>B(S)))
Что несомненно, так как ситуации, в которых погода пасмурна, а дождя нет, бывают. Что, собственно, и подразумевалось.
Поэтому "виной" всему я вижу устранение модальности при формализации, что привело к удалению квантора всеобщности. При этом в отрицании всеобщего высказывания исчезает подразумеваемый квантор существования, без которого высказывание становится всеобщим. Что, конечно же, не так.
Re: разгадка
То есть это, строго говоря, просто не импликация. ]
А можете ли вы представить себе случаи применения союза если...то... в обиходной речи и _без_ модальности? Причем, я не имею в виду варианты применения если-то в качестве разделительного (если Москва - холодный город, то Афины - теплый) или уступительного (если Москва и теплый город, то разве что по сравнению с Архангельском) союза.
есть ли модальный "привкус"?
Если истинностный статус A и B уже известен, и это некие фиксированные высказывания, то форма "если A то B" в обиходной речи неуместна. Естественнее просто сказать, что B истинно, или же ложно A. Но представим себе вот какое явление. Может оказаться, что речь идёт о фиксированных высказываниях с не известными пока истинностными значениями. Так часто бывает и в математике, когда доказывают, что положительный ответ на один вопрос влечёт положительный вопрос на другой. Причём можно рассмотреть такие случаи, когда A и B в принципе не зависят от переменных. Ну, например, если задача о тавтологиях исчисления высказываний решается детерминистски за полиномиальное время (ответ здесь только "да" или "нет"), то это же верно относительно задачи распознавания конечгого графа на предмет свойства "быть гамильтоновым".
Во всех этих случаях можно добавить модальности по такой схеме: "если окажется, что верно A, то необходимо выполняется B". Следует учитывать то, что модальности бывают разные. Когда модальность "онтологична" (то есть истинностный статус известен господу Богу в виде ответа "да" или "нет"), то её можно не привлекать. Если же мы мыслим оба ответа возможными (в смысле того, что нет оснований исключить ни один из них), то тогда меняется и смысл употребляемых модальностей.
Импликация налагает некие ограничения в форме того, что некоторые комбинации истинностных значений типа |A|=1, |B|=0 она считает невозможными. А это уже есть модальная форма.
вы меня запутали :)
Что касается гамильтоновых графов :) А нет ли там некоего более общего правила, леммы, теоремы типа: "если... задача x решается за полиномиальное время и есть определенная связь между задачами x и y, то задача y тоже решается за полиномиальное время"?
NP-полнота
Правильно ставить вопрос не "есть" или "нет", а "обязательно ли считать, что есть" или "можно считать, что нет". Заметьте, что тут опять всплыли модальности, но уже в другом контексте.
Гамильтоновы графы, распознавание тавтологий -- это всё примеры так называемых "NP-полных задач". Их общее количество количество исчисляется тысячами. Когда возникает новый вопрос о том, не будет ли задача X являться NP-полной, то подыскивается любая подходящая задача Y, про которую NP-полнота уже известна, а затем осуществляется прямое сведение одного к другому. То есть излагается явный алгоритм, который решает задачу Y за полиномиальное время при условии, что при помощи некой гипотетической подпрограммы задачу X за полиномиальное время мы умеем решать.
Суть в том, чтобы установить "максимальную сложность" задачи X, то есть обосновать, почему умение её решать "быстро" (за полиномиальное время) влечёт возможность решать столь же быстро все остальные задачи из длинного списка NP-полных.
Интерес представляют трудные задачи, про которые NP-полнота не имеет места, или же это не известно. Скажем, если дано n-значное число, то надо за время n^k, где k=const, распознать это число на простоту. Уже в XXI веке появилась работа трёх индийских математиков (я её подробно разбирал), где это осуществлено. А вот для разложения n-значного числа на простые множители пока ничего не известно. Можно наперёд знать, что n=pq, где p и q -- простые. Скажем, я нашёл большие простые числа, перемножил их, а потом послал Вам ответ. Но находить сами множители по числу n за полиномиальное время пока никто не умеет.
Если это произойдёт, то могут быть неприятности с используемыми на практике криптографическими алгоритмами.
Re: NP-полнота
Ага. Но тогда возвращаемся к первому вашему коменту, где вы говорите, что из-за модальности эта импликация как бы и не импликация вовсе ;) Но, если модальноеть есть всегда, то выходит, что всякая импликация - не импликация - бррр! :))))
Про задачи я почему спросил. Получается, что там все-таки есть некие переменные - в высказывании более общего вида (если задача X ..., то задача Y...) Когда на место переменных подставляются конкретные задачи, то получается высказывание без переменных. Если после подстановки запретить дальнейшие преобразования подставленных частей, то похоже, что удается решить все парадоксы. А если разрешить - то получаются новые. Кажется, я придумал, как разобраться со всеми этими парадоксами, осталось найти время, чтобы оформить это дело :)
пропущенное
В данном контексте приходится (по традиции) обходиться без модальностей, используя обычные средства исчисления предикатов. (Хотя на самом деле здесь есть выход за их рамки, но это обстоятельство несущественно.) Оттенок "возможно" мы передаём квантором существования, а оттенок "необходимо" -- квантором всеобщности. При этом любая (или почти любая) импликация, встречающаяся "в быту" -- это утверждение вида "для всех ситуаций S верно, что A(S)->B(S)", то есть "по умолчанию" имеется квантор по всем ситуациям, а внутреннюю импликацию можно считать "математической" (или "материальной", как Вы любите говорить).
То есть разрешение многих парадоксов действительно должно получиться, если восстановить пропущенное и подразумеваемое.
Re: пропущенное
Пока такой вариант:
Если 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 - в общем, логические функции. Т.е. надо очень строго разделять истинность текстов и функции истинности, которые выражают эту истинность. Сами по себе функции истинности могут иметь значения, но не могут иметь истинности.
Вот как то так, развернуто оформлю как-нибудь позднее.