Рафаель Роузен - Математика для гиков

В настоящее время существует король Франции.

Собаки могут дышать под водой.

Когда светофор красный, автомобили должны остановиться.

Первые два высказывания ложные; третье – истинное. Вот несколько примеров смешанных высказываний:

Солнце светит, и коровы пасутся на холме.

Либо идет дождь, либо снег.

Автомобиль движется, и его колеса поворачиваются.

Давайте разберем каждый пример:

• В случае первой комбинации, если оба высказывания о коровах и о солнце являются истинными, тогда конечное высказывание тоже истина. Если одно из них ложное (или они оба ложные), тогда все высказывание тоже ложное.

• Во втором примере целое высказывание является истиной, если истиной является высказывание о дожде или снеге.

• И опять-таки в третьем примере высказывание истинное, если оба высказывания являются истинными. Если хотя бы одно из них ложное, тогда все высказывание тоже ложное.

Нововведением Буля было то, что он заметил, что можно представлять логические высказывания при помощи символов, которые используются в математике. Если, например, высказывание о солнце было представлено как Х, а высказывание о коровах как Y, вы в некотором смысле могли бы сложить два высказывания и получить значение истинности: 1 для истины, 0 для лжи.

Хотя «и», «или» и «не» – это не просто абстрактные идеи. Инженеры в ХХ веке научились представлять их физическим способом, в виде логических элементов. Эти элементы в конечном итоге стали включаться в транзисторы и компьютерные чипы и лежат в основе вычислительных расчетов, которые делает каждый компьютер и по сей день. Все расчеты выполняются на основе определенной электрической ситуации, будучи «правдой» или «ложью». Таким образом, под каждым модным экраном бьется математическое сердце.

Историки утверждают, что Джордж Буль в детстве сам выучил латынь. Позже он стал деканом факультета естественных наук в Квинс Колледже в городе Корк и женился на Мэри Эверест (племяннице Джорджа Эвереста, в честь которого была названа гора Эверест).

Иногда математика показывает аспекты мира, которые кажутся невозможными, но которые тем не менее являются правдой. Рассмотрим, например, парадокс дней рождения. В любой группе людей какова вероятность того, что у двух из них день рождения в один день? Вероятность, на первый взгляд, не так уж и высока, так как в году 365 дней. Кажется, что вероятность, что в какой-нибудь случайной группе людей двое из них родились в один день, невероятно мала.

А все же это не так. Шанс, что два человека из группы делят один день рождения намного выше, чем вы думаете. На самом деле, в группе, состоящей из 23 человек, вероятность составляет 50 %. Как такое возможно? В конце концов, если вы являетесь членом этой группы, остается 22 человека, которые могли родиться с вами в один день, так что существуют только 22 вероятности совпадения. Это число совсем не впечатляет. Но помните, что вы не сравниваете свой день рождения со всеми. Каждый человек сравнивает дни рождения друг с другом! Итак, помимо 22 сравнений с вашей датой рождения, существует и множество других.

Чтобы увидеть, как такое возможно, представьте всех 23 человек в виде точек, выстроенных в линию. (Если хотите, возьмите лист бумаги и карандаш, чтобы нарисовать их.) Для сравнения дня рождения человека № 1 начертите линии от первой точки до всех остальных. Теперь сделайте то же самое для человека № 2. Заметьте, что линия между человеком № 2 и человеком № 1 такая же, какую вы уже нарисовали от человека №#1 до человека № 2 в первый раз сопоставлений. Так как мы не хотим повторять эти сравнения, число сравнений для человека № 2 на один меньше, чем у человека № 1, то есть 21. Процесс продолжается: для человека № 3 число сравнений равно 20. Общее число сравнений в этом случае равно не 22, а 22 + 21 + 20 + 19 …, и в конце концов выходит 253.

Теперь мы подошли к принципу, который часто используется в математическом мышлении; а именно, чтобы установить истинность, нужно доказать, что обратное является ложью. Итак, как мы можем вычислить вероятность того, что у двух человек из 23 день рождения в один день? Итак, помните, что дата рождения человека имеет 365 возможных вариантов (исключаем 29 февраля, которое появляется на календарях в високосный год). Тогда вероятность совпадения дат рождения составляет 364/365, так как существуют 364 возможных дат, которые будут отличаться от изначальной даты. В итоге получается 99,726027 % вероятность, что любые два человека рождены в разные дни.