me.neoascetic

Introduction to mathematical thinking

Первый мой завершённый курс из многих интересных, представленных на Coursera. В целом - понравился, хотя по времени я едва вывозил. Экзамен так и вообще завалил, думал, что буду довольствоваться обычным сертификатом о завершении, но - приятная неожиданность! - в результате получил “with distinction”, с отличием, то бишь, ибо, как написал профессор, много кто экзамен завалил.

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

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


В математической логике, о которой в курсе рассказывалось больше, чем о чем-то другом, когда рассматривалась импликация (следствие) одного высказывания из другого, я не смог сразу поверить и понять, что A → B истинно всегда, за исключением случая, когда А истинно, но B ложно. Это было контринтуитивно, пришлось копнуть.

Понятно, что если А истинно и B истинно, A → B тоже истинно. Можно даже понять, что если А и B ложны, A → B истинно. Поверить, что A → B истинно даже когда А истинно, но B ложно (т. е. 1 → 0), уже труднее. А ложна импликация лишь в тех случаях, когда B ложно при истинном A.

  A      B     A → B
----------------------
  0      0       1
  1      1       1
  0      1       1
  1      0       0

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

Проще всего относиться к импликации, как к некоторому “обещанию”. К примеру, пусть:

A = "ты выучишь математику"
B = "я дам тебе конфету"

A → B = "если ты выучишь математику, я дам тебе конфету"

И, по порядку:

  1. “Ты НЕ выучил математику, и я НЕ дал тебе конфету”. Обещание не нарушено, импликация истинна.

  2. Второй случай - просто выполнение обещания. Ты выполнил своё: выучил математику, а я - своё: дал тебе за это конфету. Все довольны, импликация истинна.

  3. “Ты выучил математику, но я НЕ дал тебе конфету”. Вот это подлость! Вот это обман! Нарушение обещания, сразу же видно! Поэтому и импликация - ложна.

  4. “Ты НЕ выучил математику, но я все-таки дал тебе конфету”. Хм. Тот самый странный случай, который вызывает сомнения. Обещание нарушено… или нет? Я ведь обещал дать конфету, если ты выучишь математику, но не обещал её не давать, если не выучишь! Так что обещание все-таки не нарушено, и импликация - истинна.

Этот хинт я нашёл на форуме курса на Coursera.


Вторая зарубка на память - про кванторы: всеобщности (∀) и существования (∃). Конкретно с ними мне было непонятно, как они объединяются в сложных выражениях, когда несколько кванторов (одинаковых ли, различных) идут друг за другом. Этот вопрос я из лекции не уловил. Если он там вообще присутствовал.

Итак, одинаковые кванторы в границах между другими можно менять как душе угодно, потому как они объединяются конъюнкцией: ∀x∈N ∀y∈Q … (“для всех Х принадлежащих натуральным числам И всех Y принадлежащих рациональным…”). Если мы поменяем кванторы для X и Y местами, ничего страшного не случится.

Различные же кванторы указывают на импликацию, поэтому их порядок следования важен, менять относительно друг друга нельзя: ∀x∈N ∃y∈Q ∃z∈Q … (“для всех X принадлежащих натуральным числам существует такие Y и Z, принадлежащие рациональным…”), то есть здесь описывается следование: “если число X принадлежит натуральному ряду, значит для него существуют такие рациональные Y и Z, что…”

Если мы поменяем кванторы общности и существования местами, получится совершенно иное высказывание: “существуют такие рациональные числа Y и Z, для которых все натуральные числа…” или “существует такое рациональное число Y, для которого для всех натуральных чисел существует такое рациональное число Z…”, и это высказывание может оказаться как ложным, так и вообще нелепым.