о кванторах (математическое)

[avva]

I hate the Pumping Lemma (англ.)

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

В обсуждении на Hacker News кто-то справедливо заметил, что лемму о накачке следует объяснять, начиная с доказательства, потому что оно практически тривиально и очень интуитивно. Правда, даже если доказательство понятно, многим трудно переварить что-то вроде "∀ регулярного языка L ∃ n > 0, так что ∀ слова длиной больше n ∃ такая его разбивка, что.... (и еще внутри этого: ∀ степени i...)".

Но может быть, подумал я, это как раз является одной из причин, по которым лемма о накачке неизбежно оказывается частью обучения степени Computer Science? Для студента CS она оказывается обычно первым "заумным" с точки зрения логики утверждением, таким, которое требует нормального понимания чередующихся кванторов. А это понимание надо наработать в себе тем или иным образом, надо сквозь него пройти. Более сложный материал в более сложных курсах потом всегда будет принимать это понимание как данное.

Людям, вообще говоря, трудно даются цепочки чередующихся кванторов: утверждения типа "для каждого X сущестует такое Y, что для каждого Z..." Никто не понимает такие утверждения, встретив их впервые, сразу и интуитивно: надо сломать на них мозги, надо как следует продумать их. Даже цепочка длиной 2 уже трудна для неподготовленного человека; студенты-первокурсники часто путают ∀∃ с ∃∀. Многие, пройдя сквозь этот процесс тренировки, забывают о нем потом; цепочки длиной 2-3 кажутся им тривиальными и немедленно доступными любому.

Как раз недавно мне попался типичный пример - на том же форуме HN обсуждали запись в блоге программиста-самоучки (без высшего образования), о том, как понять нотацию O() без математики. Запись, по-моему, была не очень удачная, но меня поразил один комментарий: "да вообще-то это просто. Скажем, время работы O(n) означает, что есть такая константа..." и дальше словами выписано, что такое для функции быть O(n), и заканчивается так: "видите, хоть и математика, но очень просто!". Причем это было написано совершенно без иронии, автор комментария был искренне уверен, что выписанное словами утверждение с чередующимися кванторами будет совершенно прозрачным для любого программиста-самоучки без высшего образования.

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

Comments

[vesch9.livejournal.com]

В конце курса матанализа наш преподаватель переживал за нас: "Как же вы будете жить без эпсилон больше нуля?!" :)

Просьба

[sspr.livejournal.com]

Можно для общего развития ссылку на литературу по этому вопросу?

[a-konst.livejournal.com]

Я хоть и не автор, но спрошу - по какому вопросу?
Вообще про кванторы? Про пределы и непрерывность в мат-анализе?
Про обучение восприятию длинных цепочек кванторов?

[stf-life.livejournal.com]

Да простят меня знатоки, но объясните, обязательно ли самоучкам знать мат. анализ? Возможно он им действительно никогда не пригодится в тех работах, которые встретит. Но и буду благодарен за пример работы, где без мат.. анализа ну никак не выкрутиться.

[aafin.livejournal.com]

Максимум минимум искать понадобится самоучкам?

[pilpilon.livejournal.com]

существуют, конечно, самоучки, что все задачи, которые они решают, не требуют понимания кванторов.

[buddha239.livejournal.com]

Мне коллеги говорили, что в былые годы первокурсников матмеха косил матан, а вот в последнее время - алгебра.

[a-konst.livejournal.com]

О, времена меняются. Наших однокурсников, помнится, тоже больше косил матан. А потом фан.

[migmit.livejournal.com]

Мне не сразу удалось прочитать правильно фразу "первокурсников косил матан".

[xp0m0u.livejournal.com]

на радиофаке УПИ всё ещё так и дают с первого курса - матан+линейная алгебра, потом уже остальное

[ztarlitz.livejournal.com]

В Урфу надо сказать этим же все примерно и заканчивается, никакой современной математики там не было и не предвидится, правда и в других вузах дело обстоит не лучше.

[d-ohrenelli.livejournal.com]

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

Мой младший брат во время армии взял какой-то начальный математический курс в открытом университете (линейная алгебра, вроде). Он служил в Гивати, в роте Цабар. Так вот, какой-то деятель из роты попросил у него посмотреть учебник и отреагировал на увиденное внутри так: "Эти идиоты не знают английского потому что А и Е пишут наоборот."

[molnij.livejournal.com]

Я в цепочке застрял на "больше n ∃ существует " существует-существует??

А про курсы.. Матан и дифуры (ну и тензоры по хорошему) сильно привязаны например к физике, которая у нас была 1-3 курсах. Отодвигать непрофильный предмет на старшие курсы - спорная затея. Давать физику без матана в универе - вообще время терять.
А кванторы в той же топологии, логике и прочей алгебре вроде встречаются в куда более жестком виде чем в матане, на мой вкус по крайней мере.

[avva.livejournal.com]

Исправил описку, спасибо.

[vodianoj.livejournal.com]

Толик, а можешь прислать линк на обьяснение двойных нотаций ∀∃ и ∃∀? Я чего-то их не припомню :-(
Или ты имеешь ввиду, что они не идут так подряд, а просто утверждения типа: "для любого х существуют такие у, что..."

[avva.livejournal.com]

Да, именно это имею в виду, ничего особенного.

[morfizm.livejournal.com]

Я не вижу какой-то проблемы в понимании формулировки леммы, но я тут явно biased, т.к. у меня в университете была куча логики, абстрактной алгебры, теорий алгоритмов и формальных спецификаций (хоть и конкретно с этой леммой я не сталкивался).

Но ИМХО, человеку, в целом, сообразительному, должно быть сравнительно легко растолковать, только это займёт не 2 минуты, за которые большинство людей привыкли решать все насущные математические вопросы, а, может, час-другой. Проблема в лени, человеку не хочется разбираться час, но вот на написание поста вроде этого (http://bosker.wordpress.com/2013/08/18/i-hate-the-pumping-lemma/) у него час нашёлся.

Но при этом соглашусь, что лемма, правда, слишком заумно сформулирована.
Куда легче сказать, что регулярные языки это те и только те, которые распознаются конечными автоматами, и дальше всё совсем очевидно: у конечного автомата, ясен пень, конечное число состояний (скажем, N), поэтому, как ни крути, совершенно очевидно, что после попадания одно из конечных состояний (не более, чем за N-1 шагов), не позже, чем через ещё N-1 шагов возникнет цикл. Следовательно слово, сооветствующее этому циклу, может повторяться сколько хочешь раз, и всё равно будет матчиться, ЧТД (выбираем p >= N и понеслась...)

[plakhov.livejournal.com]

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

Например, классический язык "сбалансированных скобочек". Вот доказательство его нерегулярности без этой леммы: возьмем конечный автомат А, и докажем, что, каким бы он ни был, он этот язык не распознает. В самом деле, найдутся n и m такие, что после (ⁿ и после (^m автомат А находится в одном и том же состоянии. Это означает, что он ошибется либо на строчке (ⁿ)ⁿ, либо на строчке (^m)ⁿ. Доказательство с применением pumping lemma не лучше, кажется, ни в каком смысле. Оно и длиннее, и хуже воспринимается.

[d-ohrenelli.livejournal.com]

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

На самом деле начала нормальной алгебры можно давать еще в школе. Колумбийская программа unified modern mathematics для школьников тому примером.

[aerffadf.livejournal.com]

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

[xaxam.livejournal.com]

Даже профессиональные математики (за редкими исключениями) с большим трудом понимают высказывания, содержащие три и более квантора.

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

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

Помогают еще "психологические подпорки", когда какие-то объекты объявляются "переменными", какие-то - "параметрами" и т.д.

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

[the-aaa13.livejournal.com]

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

[gul-kiev.livejournal.com]

Про кванторы:

[xgrbml.livejournal.com]

:)))

[cousin-it.livejournal.com]

В тему кванторов: branching quantifiers (http://terrytao.wordpress.com/2007/08/27/printer-friendly-css-and-nonfirstorderizability/) видели? Я сильно удивился, когда узнал.

[avva.livejournal.com]

Да, я когда-то подробно вникал в "independence-free logic" Хинтикки, которую он предложил считать более фундаментальной, чем обычная логика первого порядка, но ее семантика, если я правильно помню, определялась только через игры (что возможно и для обычной логики первого порядка, конечно), и это не добавляло уверенности.

[migmit.livejournal.com]

Помнится, нам К.П. Кохась давал задачку "написать определение того, что эпсилон стремится к нулю, когда дельта стремится к нулю".