Рэймонд Смаллиан
Принцесса или тигр




Аннотация

Задачи по логике

Рэймонд М.Смаллиан
ПРИНЦЕССА ИЛИ ТИГР?



От редактора перевода

В 30-х годах этого века психолог Дж. Струп, языковед Э. Бенвенист и логик К. Гёдель примерно в одно время выполнили три исследования, с разных сторон освещающие одно и то же явление. Друг о друге эти ученые едва ли знали. Все три работы впоследствии стали классикой для профессионалов — психологов, лингвистов и математиков соответственно, — но за пределами этих узких кругов стала известной разве что теорема Гёделя (современный немецкий поэт Ганс Магнус Энценсбергер даже посвятил ей стихотворение).
В экспериментах Струпа испытуемому предъявляли слово, написанное цветными чернилами, и просили быстро назвать цвет чернил. Оказалось, что если красными чернилами написано слово СИНИЙ, то время реакции увеличивается. Смысл слова как бы мешает названию цвета, поскольку не совпадает с ним.
Бенвенист изучал свойство некоторых речевых высказываний, которое можно назвать аутореферентностью — ссылкой на себя. Этим свойством обладают те высказывания, при описании смысла которых следует учитывать сами эти высказывания как элемент действительности. Например, в описание смысла фразы «Приказываю открыть парад» должно входить указание на то, что само произнесение этой фразы является сигналом к открытию парада. Почти все военные команды обладают аутореферентностью. Иногда это разделение смысла команды на две части — содержание команды и приказ к ее исполнению — может быть явным. В строевой команде, произносимой «Нале-во!», часть «нале-» указывает направление поворота, а «-во» является сигналом к исполнению; здесь первая часть перестает быть аутореферентной. Важно отметить, что, как и в опыте Струпа, аутореферентное высказывание может быть внутренне конфликтным. В нашем примере, если приказ отдается лицом, не имеющим на это права, то часть интерпретации «это есть приказ к исполнению» оказывается ложной.
Гёдель исследовал программу аксиоматизации математики. Существует ли, например, такая явная система постулатов о свойствах целых чисел (вроде аксиом евклидовой геометрии), из которой чисто логически можно вывести все истинные теоремы о них? (Ложные при этом не должны выводиться.) Объяснить точно содержание этой задачи не очень легко даже математику, который специально логикой не занимался. Трудность состоит в описании смысла слов «все» и «вывести»— сначала приходится построить целую теорию, формальную систему, внутри которой этими словами можно пользоваться как математическими терминами. Как бы то ни было, Гёдель показал — вопреки некоторым ожиданиям, — что ответ на поставленный вопрос отрицателен, полной системы аксиом арифметики нет. Причина же этого лежит в странных свойствах аутореферентных высказываний, тех же, что и выше. Старинный парадокс лжеца (лжет ли человек, говорящий «я лгу»?) выявляет такую же внутренне конфликтную ситуацию, как слово «синий», написанное красным цветом. Такой конфликт можно имитировать внутри любой достаточно богатой формальной системы, и в рамках этой системы он окажется неразрешимым.
В построении такой имитации и состоит главное техническое достижение Гёделя. Читатель этой книжки, сумевший продумать содержащуюся в ней версию теоремы Гёделя, вероятно, оценит остроумие разных конструкций, которые приходится изобретать. При этом стоит поразмыслить и над тем, почему в опытах Струпа и в парадоксе лжеца внутренне конфликтное аутореферентное высказывание организуется гораздо проще, чем в рассуждении Гёделя. Кажется, ответ связан с тем, что в человеческом сознании «речевая» система, воспринимающая сигнал, отделена от «образной», оценивающей его содержание. В гёделевской же ситуации их приходится реализовывать общими средствами.
Рэймонд М. Смаллиан всю свою профессиональную жизнь занимается вещами, так или иначе связанными с логикой вообще и гёделевой теоремой в частности. В своих математических работах он предложил несколько вариантов формальных систем, в которых идея Гёделя реализуется, по мнению коллег, особенно красиво. В своих же популярных книжках, как эта и предыдущая (Как же называется эта книга? — М.: Мир, 1981), он, подобно каждому писателю, пользуется неведомыми свойствами нашего мозга, чтобы заставить любого терпеливого читателя изумляться, застывать в ожидании, радостно предвкушать и вообще волноваться по поводу вещей, довольно сухих по меркам здравого смысла. Иногда профессор Смаллиан слегка перебарщивает — я не смог заставить себя решать задачки про упырей. Но в лучших головоломках книга заставляет работать речевую и образную системы восприятия так, что они смешно мешают друг другу, вроде ног сороконожки в известной истории.
Логика, оторванная от своего естественного носителя — человеческого мозга, заморожена в микросхемах современных компьютеров. В человеческой голове она живет совершенно иначе, и вечные попытки человечества понять самое себя постоянно возвращают нас к раздумьям, которым посвящена эта книжка. Модели, которые в ней предлагаются, бывают смешны то своей простотой, то эксцентричностью. Смех от души над собственной логикой целителен во многих конфликтах.
Ю.И. Минин

Леди Бланш

Предисловие

Из множества занятных писем, присланных мне после выхода в свет моей первой книги логических головоломок (названия ее я никак не упомню!), одно принадлежало десятилетнему сыну довольно известного математика, с которым я в свое время учился в школе. В письме предлагалась весьма изящная и оригинальная задача, навеянная некоторыми задачками из моей книжки, которую мальчик прочитал взахлеб. Я сразу же позвонил отцу, решив поздравить его с таким умницей. Но тот, прежде чем позвать к телефону самого парнишку, стал заговорщически шептать в трубку: "Ему страшно нравится твоя книга! Но когда будешь с ним толковать, не проговорись, что эта штука называется математикой — в школе он ее просто ненавидит! Чуть заподозрит, что твоя книжка математическая, тут же забросит ее подальше».
Я вспомнил об этой истории потому, что она представляет собой иллюстрацию странного, но распространенного явления. Множество людей, с которыми я сталкивался, утверждали, что ненавидят математику, и в то же время с азартом накидывались на любую логическую или математическую задачу, которую я им подсовывал, стоило лишь облечь ее в форму занимательной головоломки. Я бы ничуть не удивился, если бы хорошие сборники головоломок оказались одним из лучших лекарств против так называемого «страха перед математикой». Более того, любой учебник математики вполне можно переписать в форме набора занимательных задач. Я иногда воображал, что бы произошло, если бы Евклид представил свои классические «Начала» именно в таком виде. Например, вместо того чтобы сформулировать в качестве теоремы утверждение о равенстве углов, лежащих в основании равнобедренного треугольника, а затем строго доказать эту теорему, Евклид начал бы так: «Задача. Дан треугольник с двумя равными сторонами. Всегда ли у него есть два равных угла? Если да, то почему, если нет, то тоже почему? (Решение смотри на странице такой-то.)» А потом и все остальные теоремы постарался бы изложить в таком же духе. Такая книжка вполне могла бы оказаться одним из самых популярных сборников задач в истории!
Вообще-то мои собственные сборники задач отличаются тем, что меня в первую очередь привлекают задачи, связанные с наиболее глубокими и важными результатами логики и математики. Так, истинной целью моей первой книги логических задач было желание дать широкому читателю хотя бы скромное представление о том, в чем же суть великой теоремы Геделя. Книжка, которую вы держите в руках сейчас, — следующий шаг в этом направлении. Многие факты и задачи из нее я использовал в одном из своих курсов лекций, озаглавленном «Головоломки и парадоксы». Тогда-то один из моих студентов заметил мне: «Знаете, профессор, ваша книга — особенно ее третья и четвертая части — читается прямо как какой-то математический роман. Ничего подобного я раньше не встречал!». Мне кажется, что слова «математический роман» в этом случае весьма уместны. Действительно, большая часть книги написана в форме художественного повествования. Поэтому ее вполне можно было бы назвать как-то вроде «Тайна сейфа из Монте-Карло» — ведь в последней части книги речь идет о расследовании, в процессе которого инспектор Крейг из Скотланд-Ярда пытается подобрать комбинацию цифр, позволяющую открыть замок одного из сейфов в Монте-Карло, и тем предотвратить катастрофу. Когда все его усилия вскрыть сейф оказываются безуспешными, инспектор возвращается в Лондон, где по счастливой случайности вновь сталкивается с блестящим и чудаковатым изобретателем цифровых кодирующих машин. Они приглашают еще и специалиста по математической логике, и вскоре все трое погружаются в глубокие воды потока, ведущего в самое сердце великого открытия Гёделя. Конечно же, замок сейфа из Монте-Карло оказывается «гёделевым», а его modus ореrandi Принцип работы (лат.).

прекрасно иллюстрирует фундаментальную идею Гёделя, влияние и результаты которой обнаруживаются во многих научных теориях, связанных с таким удивительным явлением, как процесс самовоспроизведения.
В конечном счете исследования Крейга и его друзей приводят к весьма примечательным математическим открытиям, не известным до настоящего времени ни ученому миру, ни тем более широкой публике, — это так называемые «законы Крейга» и «законы Фергюссона», которые впервые преданы гласности на страницах книги. Несомненно, они должны заинтересовать как любителей математики, так и логиков, лингвистов и специалистов по вычислительной технике.
Книгу эту я писал с огромным удовольствием; хотелось бы, чтобы с таким же удовольствием ее и читали. Собираюсь написать еще несколько книг в том же духе. Наконец, я хочу поблагодарить моего редактора Энн Клоуз и технического редактора Мелвина Розенталя за ту неоценимую помощь, которую они мне оказали.
Элка-Парк, штат Нью-Йорк
Рэймонд Смаллиан
Февраль 1982 г.

Часть первая. Принцесса или тигр?

Задачки с подвохом — старые и новые

Начнем с нескольких арифметических и логических задачек. Одни из них новые, а другие могут оказаться знакомыми читателю.
1. Сколько денег? Предположим, что у вас и у меня имеется одинаковая сумма денег. Сколько денег я должен вам дать, чтобы у вас стало на 10 долларов больше, чем у меня? (Решения всех задач приведены в конце каждой главы.)
2 Задача о конгрессменах. В некоем конгрессе заседают сто политических деятелей. Каждый из них либо продажен либо честен. Нам известны следующие два факта:
1) По крайней мере один из конгрессменов является честным
2) Из каждой произвольно выбранной пары конгрессменов по крайней мере один продажен.
Можно ли с помощью этих двух утверждении определить, сколько конгрессменов в этом конгрессе будут честными, а сколько — продажными?
3. Старое вино в не слишком новые мехи. Бутылка вина стоит 10 долларов. Вино на 9 долларов дороже бутылки. Сколько стоит пустая бутылка?
4. Какова прибыль? Самое удивительное в этой задаче, что разные люди решают ее различными путями, каждый получает свой ответ и каждый с пеной у рта готов доказывать, что именно его ответ правильный.
Торговец купил некий товар за 7 долларов, продал его за 8, потом вновь купил за 9 долларов и опять продал его за 10. Какую прибыль он получил?
5. Задача о десяти любимцах. Самым поучительным в этой задаче является то, что, хотя она легко решается посредством элементарных алгебраических выкладок, ее можно решить вообще без всякой математики — лишь с помощью рассуждений. Более того, решение, подсказанное здравым смыслом, по-моему, гораздо интереснее и уж, конечно, более творческое, а также содержит больше информации, чем сугубо математическое решение.
Итак, десяти собакам и кошкам скормили 56 галет. Каждой собаке досталось 6 галет, каждой кошке — пять. Сколько было собак и сколько кошек?
Любой читатель, хотя бы немного знакомый с алгеброй, легко найдет ответ. Можно решить эту задачу и методом проб и ошибок. Ясно, что для числа кошек в задаче есть 11 возможностей (от 0 до 10).
Перебрав все, легко найти правильный ответ. Однако если подойти к этой задаче толково, то оказывается, что есть еще одно удивительно простое решение, для которого не нужно ни алгебры, ни перебора вариантов. Поэтому я советую тем из вас, кто получит ответ ПО-СВОЕМУ, заглянуть в решение, приведенное в конце главы.
6. Большие и маленькие птицы. Вот еще одна задача, которая решатся как алгебраически, так и с помощью рассуждений; я и тут предпочитаю здравый смысл. В зоомагазине продают больших и маленьких птиц. Большая птица вдвое дороже маленькой. Леди, зашедшая в магазин, купила 5 больших птиц и 3 маленьких, Если бы она вместо этого купила 3 больших птицы и 2 маленьких, то потратила бы на 20 долларов меньше. Что стоит каждая птица?
7. Как плохо быть рассеянным. Следующая история произошла на самом деле.
Как хорошо известно, с вероятностью более 50 % можно утверждать, что в группе, состоящей как минимум из 23 человек, всегда найдется по крайней мере двое, у которых день рождения падает на одно и то же число. В свое время я преподавал математику в Принстонском университете и как-то занимался со студентами элементарной теорией вероятностей. Я объяснил своим слушателям, что если число людей в группе увеличить с 23 до 30, то вероятность того, что в ней окажутся по крайней мере двое, которые родились в один и тот же день, окажется близка к единице.
— Но, — продолжал я — поскольку вас здесь всего 19, то вероятность того, что у двоих из вас дни рождения совпадают, будет гораздо меньше 50 %.
Тут один из студентов поднял руку:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28