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

[psilogic]

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

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

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

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

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

~(A => B) = true

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

Comments

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

[psilogic.livejournal.com]

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

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

NP-полнота

[falcao.livejournal.com]

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

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

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

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

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

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

Re: NP-полнота

[psilogic.livejournal.com]

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

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

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

пропущенное

[falcao.livejournal.com]

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

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

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

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

[psilogic.livejournal.com]

Да, действительно, многие парадоксы разрешаются, если ввести упущенный квантор. Насколько я понимаю, это впервые сделал еще Кларенс Льюис, и он играл именно с модальностями (в 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 - в общем, логические функции. Т.е. надо очень строго разделять истинность текстов и функции истинности, которые выражают эту истинность. Сами по себе функции истинности могут иметь значения, но не могут иметь истинности.

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