Вы здесь

Проверочные тесты

148 сообщений / 0 новое
Последнее сообщение
Аватар пользователя id.ilych
id.ilych
Не в сети

Спасибо. Теперь понятно: если одни формулы выводятся из других, причём в обоих направлениях, то выбор базиса неоднозначен, а потому говорить, что аксиомами выбираются формулы, для которых нет доказательства некорректно.

Аватар пользователя Оля
Оля
Не в сети

Во-первых, никто не запрещает аксиомам выводится из других аксиом. Просто если это условие выполняется, то такая система аксиом называется независимой. Но независимость не является обязательной для аксиоматизации.

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

Аватар пользователя id.ilych
id.ilych
Не в сети

Самопроверка после видео 6.2. Вопрос 3 "Где ошибка в следующем доказательстве?". Правильным ответом значится "Индуктивный базис следует проверить не для одного числа Фибоначчи, а для двух подряд идущих чисел Фибоначчи." - как это соответствует методу математической индукции? Ошибка здесь, очевидно, именно в индуктивном шаге. А именно во фразе "по индуктивному предположению F(n−1) и F(n−2) четны" - неверно, по индуктивному предположению верна только чётность F(k), где k хоть и выбирается произвольно, но фиксирован во время совершения индуктивного шага - верность выражения для любых других чисел кроме выбранного k не утверждается.

Аватар пользователя EugenO
EugenO
Не в сети

Но ведь базиса из двух четных чисел не существует, а при отсутствии базиса нет смысла рассматривать индуктивный шаг, разве не так?

Аватар пользователя Надежда
Надежда
ТУСУР
Не в сети

Формула определения числа Фибоначчи содержит в себе сумму двух предыдущих чисел, то индуктивный базис следует проверять для двух подряд идущих чисел - F4 = F3+F2, а F2 - мы не проверили

Аватар пользователя id.ilych
id.ilych
Не в сети

Я исхожу из определения (ŠPˆ(0) & ∀x(‰P(ˆx) ⊃ Pˆ(x+1))) ⊃ ∀n P(ˆn)
В рамках задачи базис 0 равен 3, а предикат P(k) - проверка чётности k-ого числа Фибоначчи.

Ошибка индуктивного шага видна из определения, т.к. фраза

по индуктивному предположению Fn−1 и Fn−2 четны

означает необоснованную подмену исходного определения другой формулой:
(ŠPˆ(0) & ∀x((∀k≤x‰P(k)) ⊃ Pˆ(x+1))) ⊃ ∀n P(ˆn)

А вот как из определения аксиомы математической индукции появляется предположение, будто проверка базиса должна осуществляться каким-то особым образом в зависимости от одной из подформул предиката мне непонятно. Внутренняя структура P(k) в определении не фигурирует.

Аватар пользователя Надежда
Надежда
ТУСУР
Не в сети

Никакой подмены не происходит. Просто применять индуктивное рассуждение можно разными способами (см.конспект лекции 6.2, стр.8 (внизу)). Например, в некоторых случаях необходимо проверять индуктивный базис для более одного элемента. В данном случае как раз это и получается - для выполнения индуктивного шага необходимо проверить индуктивный базис для двух подряд идущих чисел.

Аватар пользователя id.ilych
id.ilych
Не в сети

в некоторых случаях необходимо проверять индуктивный базис для более одного элемента

Из чего это следует? Каково формальное выражение этого правила? Допустим я что-то упускаю в формальном определении, но в конспекте на естественном языке дано такое определение:

индуктивный базис — утверждение, что свойство выполнено для самого маленького из рассматриваемых чисел

Никаких "но если в формуле предиката фигурирует N предыдущих членов ряда, то предикат должен включать проверку для N элементов". Тем более, что в приведённом доказательстве формулы Кассини, которая тоже "про числа Фиббоначи, вычисляемые как сумма двух предыдущих в ряду", в рассмотрении фигурировала одна проверка для конкретного n, несмотря на то, что в формуле предиката фигурировали аж 3 разных числа Фибоначчи.

Не поймите меня неправильно. Ваш ответ, вероятно, корректен. Просто это же учебный курс по логике - всё должно быть логически обосновано, иначе какой в этом смысл?

Аватар пользователя EugenO
EugenO
Не в сети

Чтобы применить определение, предикат P(n)  должен обозначать четность двух последовательных чисел Fn-1 и Fn. P(n+1)  будет обозначать четность чисел Fn и Fn+1. Тогда имеем ∀x(‰P(ˆn) ⊃ Pˆ(n+1)), однако неверно, что существует n: P(n), то есть не выполняется базис.

Аватар пользователя id.ilych
id.ilych
Не в сети

Чтобы применить определение, предикат P(n)  должен обозначать четность двух последовательных чисел Fn-1 и Fn.

Из чего это следует? Каково формальное выражение этого правила? Допустим я что-то упускаю в формальном определении, но в конспекте на естественном языке дано такое определение:

индуктивный базис — утверждение, что свойство выполнено для самого маленького из рассматриваемых чисел

Никаких "но если в формуле предиката фигурирует N предыдущих членов ряда, то предикат должен включать проверку для N элементов". Тем более, что в приведённом доказательстве формулы Кассини, которая тоже "про числа Фиббоначи, вычисляемые как сумма двух предыдущих в ряду", в рассмотрении фигурировала одна проверка для конкретного n, несмотря на то, что в формуле предиката фигурировали аж 3 разных числа Фибоначчи.

Аватар пользователя EugenO
EugenO
Не в сети

Из чего это следует? Из определения чисел Фибоначчи. Вот одна из формулировок:

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

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

По конспекту вопрос не ко мне. Я могу предложить такой вариант (автор - А. Шень, текст для школьников):

 

Итак, общая схема доказательства по индукции такова. Есть некоторая последовательность утверждений (A 1 , A 2 , . . . , A n , . . . ). Мы доказываем, что очередное утверждение (A n ) верно, считая известным, что все предыдущие утверждения (A k при k < n) верны. Это позволяет нам утверждать, что все утверждения A n верны.
Такой способ рассуждения называется математической индукцией, а величина n называется параметром индукции. Говорят, что мы доказываем утверждение A n индукцией по n.

Аватар пользователя id.ilych
id.ilych
Не в сети

Ещё раз: формула Кассини тоже про числа Фибоначчи, но при её доказательстве в базис ничего дополнительного не включалось, хотя непосредственно в сам предикат входило аж 3 числа, каждое из которых сумма двух предыдущих - это тоже было неверное рассуждение?

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

Приведённое Вами описание соответствует варианту, названному в лекции "возвратная индукция". Но в этом варианте база, как отдельный элемент, не рассматривается вовсе, так что задание теста, о котором я завёл речь, не про него. Иначе говоря, использование этого подхода не могло привести к тому, что правильным ответом на вопрос является вариант "Индуктивный базис следует проверить не для одного числа Фибоначчи, а для двух подряд идущих чисел Фибоначчи."

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

Аватар пользователя EugenO
EugenO
Не в сети

Ничего не имею против того, чтобы разобраться. Только я по жизни инженер, а не преподаватель, поэтому мне легче объяснить, почему эта ерунда не работает и как сделать так, чтобы она  работала, чем выстроить методически безупречный курс. Как Чапай говорил, подучиться надо. При этом я вовсе не считаю, что предложенный курс методически идеален, в частности, на мой взгляд, он далековат от практики.

Приведенное описание Шеня говорит об общей схеме, об общем понимании. Мне оно понравилось использованием понятия параметр индукции. Согласен, что схемно-методически наиболее близка здесь возвратная индукция. Однако прочие методы не противоречат общему пониманию. Кстати, об этом в курсе приведена теорема (модуль 6.2, стр.6). Но надо понимать, что применяется она в отношении параметра индукции (натуральных чисел), тогда как в наших предикатах могут фигурировать трансцендентные, комплексные, еще какие-нибудь числа, да и не числа вовсе (вороны, собаки, ...).  В частности, с точки зрения математической индукции несущественно, что числа Фибоначчи являются натуральными. Однако если мы говорим о базисе, то существенно, чтобы он был построен по одной и той же схеме и на этапе доказательства его выполнимости, и на этапе индукционного перехода.

"Классический" метод математической индукции я бы сформулировал так: пусть для некоторого натурального k=k0 выполнено P(k=k0) (это базис) и для любого произвольного натурального k>k0 из P(k) следует P(k+1) (шаг), то P(k)  выполнено для всех k>=k0.

Что касается вопроса в тесте, то я бы ответил таким образом:

Ошибочно выстроена схема, поскольку произведена подмена базиса, а именно: для одного базиса произведена проверка базиса, но на ином базисе построен индукционный переход (шаг). Для того, чтобы иметь право применить такой шаг, "индуктивный базис следует проверить не для одного числа Фибоначчи, а для (хотя бы) двух подряд идущих чисел Фибоначчи."

Но такого варианта ответа не предусмотрено. Вопросы опять же не ко мне.

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

Аватар пользователя EugenO
EugenO
Не в сети

В формуле Кассини проблем не вижу. Если нужно, могу подробно.

Аватар пользователя id.ilych
id.ilych
Не в сети

Я не говорю, что с ней проблема. Я говорю, что при её доказательстве условие (разницу между квадратом одного числа Ф. и произведением двух соседних) проверялось конкретно для одного n в качестве базы. А  тут почему-то вдруг это стало необходимо включить именно несколько. Хотя в обоих случаях речь идёт о числах Фибоначчи. Вот откуда и проистекает эта разница между двумя доказательствами с появившейся по волшебству необходимостью сформировать предикат более сложным образом мне и хочется понять. Причём желательно в общем виде. Не только как это произошло в этих конкретных случаях, а как это экстраполировать на любые другие гипотезы, касающиеся каких-либо рядов.

Аватар пользователя Оля
Оля
Не в сети

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

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

 

Аватар пользователя id.ilych
id.ilych
Не в сети

Иначе говоря, вы также указываете, что ошибка была именно в  индуктивном переходе, а не в проверке базиса. Базис был введён и сам по себе он верен. Но именно выбранный базис не является основанием для _такого_ индуктивного шага. Таким образом неверен индуктивный шаг, а не базис, который сам по себе вполне корректен. О чём я и говорил в исходном сообщении. 

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

Аватар пользователя EugenO
EugenO
Не в сети

Мы утверждаем, что ошибка именно в конкретном компоненте системы, в том случае, если замена этого компонента на правильный, безошибочный приведет к работоспособности системы. Какой правильный индуктивный шаг в данном случае следует применить, чтобы он "все исправил"?

Аватар пользователя EugenO
EugenO
Не в сети

Итоговый тест по курсу. Вопрос 17 (спор философов). В одной из формул синтаксическая проблема. Так задумано или?

Аватар пользователя Оля
Оля
Не в сети

Там пропущен знак конъюнкции.

Аватар пользователя EugenO
EugenO
Не в сети

Да, именно это. Опечатка или часть задачи?

Аватар пользователя Оля
Оля
Не в сети

Опечатка.

Аватар пользователя EugenO
EugenO
Не в сети

Спасибо.

Аватар пользователя Надежда
Надежда
ТУСУР
Не в сети

Спасибо :-)

Аватар пользователя vadim.barutkin
vadim.barutkin
Не в сети

Итоговый тест к главе 7. Вопрос 15: Для каких задач не известна их сложность?

"Решение систем уравнений с целыми переменными" - диофантовые системы уравнений, сложность не определена

"Составление расписаний, учитывающих определенные условия" - сложность не определена

"Построение множества всех подмножеств данного множества" - экспоненциальная

"Вычисление 2^(2^k) для заданного натурального k" - экспоненциальная

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

"Определение, простое число или нет" - алгоритм AKS - полиноминальная сложность

"Разложение простого числа на простые множители" - ответ 1 и само число

 

Где я не прав?

Аватар пользователя EugenO
EugenO
Не в сети

Чисто интуитивно я бы склонился к тому, что ТУСУР тайно нашел полиномиальный алгоритм для диофантовых и об"явит об этом 11 числа.:-) Хотя нельзя исключать и того, что он разучился раскладывать простые...

Аватар пользователя Надежда
Надежда
ТУСУР
Не в сети

Какие у нас слушатели молодцы! Только дай им повод - они сразу "уколют":-)  Уж простите, совершили опечатку.  А вообще-то у нас (в ТУСУРе) такие ГОЛОВЫ есть, что могут происходить очень даже интересные дела!

Аватар пользователя Оля
Оля
Не в сети

Какие у нас слушатели молодцы! Только дай им повод - они сразу "уколют":-)

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

Аватар пользователя Надежда
Надежда
ТУСУР
Не в сети

Ольга, с нашей стороны хотим Вам особо сказать "СПАСИБО БОЛЬШОЕ" и  за теплые слова, и за поддержку, а особенно, за активность и точные грамотные пояснения! Было приятно, а многим и полезно,  читать Ваши высказывания.

Аватар пользователя EugenO
EugenO
Не в сети

Мы в вас верим!  "Российское могущество прирастать будет Сибирью". Спасибо за курс, за поддержку, а вам успехов.

Аватар пользователя sed.ekb1993
sed.ekb1993
Эксперт
Не в сети

Полностью поддерживаю! Большое спасибо Вам за курс!

А ФДО ТУСУР и за диплом, который я защитил в ноябре 2015 года.

Аватар пользователя Надежда
Надежда
ТУСУР
Не в сети

:-) Спасибо! И Вам процветания!

Аватар пользователя Надежда
Надежда
ТУСУР
Не в сети

EugenO - Спасибо! :-)

Аватар пользователя Надежда
Надежда
ТУСУР
Не в сети

Вы полностью правы. Простите, нами допущена ошибка. Последний ответ должен звучать так : "Разложение НАТУРАЛЬНОГО числа на простые множители."

Аватар пользователя Надежда
Надежда
ТУСУР
Не в сети

vadim.barutkin, Вы правы. Мы написали ответ (см.https://www.lektorium.tv/comment/17186#comment-17186 :-)) Извините.

Аватар пользователя id.ilych
id.ilych
Не в сети

Итоговый тест к главе 7. Вопрос 4. 

Определение функции power(x,y)=xypower(x,y)=xy возведения в степень для натуральных аргументов:

  • power(x,0)=1
  • power(x,y+1)=x
  • power(x,y)

Я так понимаю, что подразумевалось две строки, а между 2 и 3 просто знак умножения?

Вопрос 8. Чем является тезис Тьюринга?

Имелся в виду тезис Чёрча/тезис Чёрча — Тьюринга?

Аватар пользователя Надежда
Надежда
ТУСУР
Не в сети

Да

Аватар пользователя Власов Игорь
Власов Игорь
Не в сети

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

Аватар пользователя Ольга Исакова
Ольга Исакова
ТУСУР
Не в сети

Вы можете посмотреть, какие вопросы зачтены как правильные, а какие - нет. Обсудить правильные ответы можно на форуме. 

Аватар пользователя Власов Игорь
Власов Игорь
Не в сети

Сегодня напишу одно рассуждение, завтра все остальные, нужно грамотно попытаться сформулировать.

Итак, был вопрос для каких целей используется индукция в математике (не путайте с математической индукцией)?

Правильно ли я понимаю, что ответом на вопрос является  - Для получения гипотезы:

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

Аватар пользователя Надежда
Надежда
ТУСУР
Не в сети

Правильно.

Аватар пользователя EugenO
EugenO
Не в сети

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

Аватар пользователя Власов Игорь
Власов Игорь
Не в сети

В итоговом тесте был вопрос:

Укажите правильные утверждения.

1) Теоремы исчисления предикатов являются тавтологиями

2) Тавтологии исчисления предикатов являются теоремами.

3) В исчислении предикатов нет правил вывода.

Предполагаю, что по теореме Гёделя о полноте Класс доказуемых замкнутых формул совпадает с классом общезначимых (или тождественно истинных) формул. Она может быть истолкована как некоторая внешняя полнота формализованного исчисления предикатов, его полнота относительно логики предикатов. Исходя из этой теории можно формально доказать все общезначимые формулы логики предикатов. На основании этой теоремы множество теорем формализованного исчисления предикатов совпадает с множеством тавтологий логики предикатов.

Соответственно 1  пункт верный.

Правила вывода в исчислении предикатов есть. п. 3 считаю не верным.

А по второму пункту тавтологии в исчислении описаны (как пример законы де Моргана). В логике высказываний всякая тавтология есть теорема исчисления высказываний, но так ли это в логике предикатов?

Есть есть возможность помогите разобраться.

Аватар пользователя Надежда
Надежда
ТУСУР
Не в сети

По п.2. - Теорема - доказуемая формула. В исчислении предикатов доказуемы все общезначимые формулы и только они (конспект "Модуль _5.4"). А что такое "общезначимая формула"? Формула называется общезначимой, если она истинна в любой интерпретации при любой ее оценке. А что такое "тавтология"? Формула A называется тавтологией (или тождественно истинной), если формула истинна во всех интерпретациях. Значит, тавтологии исчисления предикатов являются теоремами

Аватар пользователя Власов Игорь
Власов Игорь
Не в сети

Спасибо за помощь. Для себя все уяснил.

Аватар пользователя Власов Игорь
Власов Игорь
Не в сети

Последний вопрос:

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

Доказательство от противного. Доказательство с математической индукцией. Доказательство с помощью контропозиции. Доказательство с помощью теоремы о дедукции.

Предполагаю, что доказательство с мат. индукцией.
(1) базис индукции: P(0) первый человек в очереди - мужчина,
(2) индуктивный шаг: для следующего мужчины справедливо, что за ним стоит мужчина, так как правила хорошего тона запрещают мужчине стоять в очереди сразу перед женщиной.
(3) то для всех остальных справедливо что за ними стоят мужчины.

 

 
Если брать случай доказательства с помощью контрапозиции, то сравнивал так: если из А следует В, то из не В следует не А.
Тут в рассуждении не брали обратную ситуацию, что все последующие, стоящие в очереди - не мужчины, хотя похоже это бы
привело доказательство к верному, но тут рассуждение было построено не в этом ключе. Если первый человек в очереди мужчина, то все остальные тоже мужчины.
 
Доказательство с помощью теоремы о дедукции: Чтобы доказать утверждение «Если A, то B», предполагают, что справедливо
A и доказывают справедливость B. Тут не совсем понимаю, как подвести рассуждение.
 
Аватар пользователя Надежда
Надежда
ТУСУР
Не в сети

Формулировка задачи сама подталкивает на использование метода математической индукции - есть базис и есть индуктивный шаг.

Страницы