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

Здесь дано формальное определение http://rghost.ru/7xrxqDjq5.view

Объясните, что требуется сделать в шаге 2. Если я понял, необходимо доказать истинность импликации, но тогда даже если предположение не верно(например оно становится верным при x > z, а в нашем случае x < z), импликация будет верна и шаг будет доказан. И далее, т.к мы действуем из предположения истинности посылки импликации, то это же вовсе не означает её истинность, а вся индукция строится именно на этом предположении, но его проверку мы не проводим.

Если "если" в пункте доказательства индукционного перехода ложно, о чем нам это говорит и возможно ли это? Возможно, конечный вывод надо строить как "если предположение P(x) - верно, то и P("условия задачи при n зависящем от натурального....") тоже верно"..

задан 28 Сен '15 13:02

изменен 28 Сен '15 13:35

@Razgh: это схема общего вида, в пункте 2 реализуется индукционный шаг. Доказать нужно истинность некоторой формулы. Обычно мы берём произвольное $%x$% и доказываем, что импликация истинна. Можно рассмотреть два случая. Если посылка ложна, то импликация истинна. Если посылка истинна, то мы пользуемся истинностью $%P(x)$% и доказываем истинность $%P(x+1)$%.

(28 Сен '15 18:00) falcao

"Если посылка истинна, то мы пользуемся истинностью P(x) и доказываем истинность P(x+1)."

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

"Обычно мы берём произвольное x и доказываем, что импликация истинна"

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

(28 Сен '15 18:35) Razgh

@Razgh: насколько я понимаю, Вас интересует корректность метода, то есть обоснование того, что его применение не может привести к доказательству ложного утверждения. Вы обращаете внимание на случай, когда P(x) ложно и замечаете, что импликация P(x)->P(x+1) истинна. Возникает ощущение, что здесь что-то не так. Объяснение простое: допустим, что P(1), P(2), P(3) истинны, а P(4) ложно. Импликация P(4)->P(5) будет истинна. Но предыдущая импликация P(3)->P(4) ложна, поэтому Вы это утверждение не докажете, и метод не сработает. То есть не сможет дать нам ложное утверждение, что P(n) верно всегда.

(28 Сен '15 19:45) falcao

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

(28 Сен '15 21:39) Razgh

@Razgh: я уже всё разъяснил. Всё зависит только от того, верно ли утверждение $%P(x)$% для всех $%x$%. Если да, то все шаги должны пройти "гладко". Если нет, то на каком-то шаге не удастся доказать переход от $%P(x)$% от $%P(x+1)$%. Либо неверно первое из утверждений, и тогда это выяснится при рассмотрении $%P(1)$%. Надо это обстоятельство осознать, и понять, что все остальные мысли и опасения здесь лишние.

(28 Сен '15 22:18) falcao

Извиняюсь,но мы ведь не устанавливаем - верно или нет P(x) для всех x, мы даже не устанавливаем его для x, мы просто предполагаем, что это так. (в обычном алгоритме доказательства в учебнике) Наверно надо ещё подумать.

(28 Сен '15 22:51) Razgh

@Razgh: если мы применяем метод математической индукции (по стандартной схеме), то это означает, что мы доказываем некоторое утверждение P(x) для всех натуральных x. Это та основная задача, которую мы решаем. Сам метод состоит в том, что мы сначала проверяем истинность утверждения P(1), а затем для произвольного натурального x доказываем, что P(x) влечёт P(x+1). Если то и другое у нас получится, то мы докажем P(1), P(1)->P(2), P(2)->P(3), ... и тогда понятно, что все утверждения вида P(x) будут истинны.

(28 Сен '15 23:11) falcao
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
1

Есть лестница. 1) На первую ступеньку я забираюсь легко. 2) С каждой ступеньки я могу перебраться на следующую. А теперь вопрос. Могу ли я взобраться на 23 ступеньку? А на стотыщпитсотдваццатую ...?

P.S. Ах, да забыл сказать, что я бессмертен, а лестница неразрушаема.

ссылка

отвечен 28 Сен '15 14:17

изменен 28 Сен '15 14:17

Оказывается лестница сломана после 24 ступеньки. Забраться на ступеньку(25) -> Забраться на ступеньку(26) 0 -> 0 = 1 Забраться на n-ую ступеньку - истинна.(что бред). Допустим есть функция с нат. аргументом, имеющая после некоторого аргумента z спад в минус беск. Требуется доказать что каждый послед. знач. функции больше или равно предыдущему. На шаге индкц.перех. x попадается на удовлетворяющий интервал, условия выполняется, импликация верна. Задача доказана (но это ложь). Даже если x попадет в убывающий интервал - из лжи все что угодно - истинна. В чем ошибка?

(28 Сен '15 14:40) Razgh

В формальном определении в нужном месте стоит квантор всеобщности. В неформальной интертрепации это означает, что сломанных ступенек в лестнице нет. Читаем внимательно п.2

С КАЖДОЙ ступеньки я могу перебраться на следующую.

(28 Сен '15 15:22) bot

т.е надо читать так: Доказать, что для любого икс из того что высказывание истинно при икс, следует истинность высказывания (икс + 1) - истинное высказывание, т.е доказать истинность высказывания (икс + 1)?

Какое выражение в задаче "доказать, что при любом натуральном n, (13 в степени n ) + 5, кратно 6 ", выражал бы квантор всеобщности?

(28 Сен '15 16:16) Razgh

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

(28 Сен '15 16:54) bot
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,940
×508
×225

задан
28 Сен '15 13:02

показан
1081 раз

обновлен
28 Сен '15 23:11

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru