Принцесса или тигр? - [63]
3. Трижды гёделева проблема. Построить такие утверждения X, Y и Z, чтобы X говорило о том, что Y допускает распечатку, Y говорило бы о том, что не допускает распечатки, a Z — о том, что X в свою очередь вновь допускает распечатку, и показать, что по крайней мере одно из этих утверждений (правда, нельзя сказать, какое именно) должно быть истинным, но не допускающим распечатки на машине.
Добавим к четырем нашим символам еще один — символ R. Таким образом, теперь у нас пять символов: P, R, N, А, ‒. Пусть нам даны две машины, М>1 и М>2, каждая из которых может печатать различные выражения, составленные из этих пяти символов. При этом под символом P в данном случае мы будем подразумевать «допускающий распечатку первой машиной», а под символом R — «допускающий распечатку второй машиной». Таким образом, запись P‒X означает, что выражение X допускает распечатку первой машиной, а запись R‒X — что выражение X допускает распечатку второй машиной. Запись РА‒X означает, что ассоциат выражения X допускает распечатку первой машиной, а запись RA‒X показывает, что ассоциат выражения X допускает распечатку второй машиной. Наконец, «фразы» NP‒X, NR‒X, NPA‒X, NRA‒X говорят соответственно о следующем: выражение X не допускает распечатки первой машиной; выражение X не допускает распечатки второй машиной; выражение X‒X не допускает распечатки первой машиной; выражение X‒X не допускает распечатки второй машиной. Под утверждением мы будем теперь понимать любое выражение одного из следующих восьми типов: P‒X, R‒X, NP‒X, NR‒X, РА‒X, RA‒X, NPA‒X, NRA‒X. Кроме того, пусть нам известно, что первая машина печатает только истинные утверждения, а вторая — только ложные. Условимся называть некоторое утверждение доказуемым в том и только том случае, если оно допускает распечатку первой машиной, и ложным — в том и только том случае, если оно: может быть напечатано второй машиной. Таким образом, символ P означает «доказуемый» (от англ. provable), а символ R — «опровержимый» (от англ. refutable).
4. Найдите утверждение, которое было бы ложным, но неопровержимым.
5. Имеются такие два утверждения X и Y, что одно из них (правда, нам не известно, какое именно) должно быть либо истинным, но недоказуемым, либо ложным, но неопровержимым (мы не знаем, каким именно). Такие пары можно строить двумя способами, и соответственно я предлагаю вашему вниманию две задачи:
а. Найдите такие высказывания X и Y, чтобы X утверждало доказуемость Y, a Y утверждало опровержимость X. Далее, покажите, что одно из них (мы не можем сказать, какое именно) либо истинно, но недоказуемо, либо ложно, но неопровержимо.
б. Найдите такие высказывания X и Y, чтобы X утверждало недоказуемость Y, а Y утверждало неопровержимость X. Далее покажите, что одно из этих высказываний, X или Y (мы не можем сказать, какое именно), либо истинно, но недоказуемо, либо ложно, но неопровержимо.
6. А теперь рассмотрим задачу с четырьмя неизвестными! Пусть нам требуется найти такие высказывания X, Y, Z и W, чтобы X утверждало доказуемость Y, Y утверждало опровержимость Z, Z утверждало опровержимость W, a W утверждало бы неопровержимость X. Покажите, что одно из этих четырех высказываний должно быть либо истинным, но недоказуемым, либо ложным, но неопровержимым (хотя, какое из этих четырех будет именно таким высказыванием, сказать невозможно).
Возможно, читатель уже отметил определенное сходство приведенных выше задач с некоторыми свойствами первой машины Мак-Каллоха. В самом деле, работа этой машины оказывается связанной с теоремой Гёделя, и вот каким образом.
7. Пусть у нас имеется некоторая математическая система, приводящая к набору утверждений, одни из которых называются истинными, а другие — доказуемыми. Мы предполагаем также, что эта система правильная, то есть каждое доказуемое в ней утверждение является истинным. Далее, пусть каждому числу N ставится в соответствие некоторое утверждение, которое мы будем называть утверждением N. Предположим наконец, что наша система удовлетворяет следующим двум условиям.
Условие Мс>1. Для любых чисел X и Y, если число X порождает число Y в первой машине Мак-Каллоха, утверждение 8X истинно тогда и только тогда, если утверждение Y доказуемо. (Напомним, что число 8X это не 8, умноженное на X, а цифра 8, за которой стоит число X.)
Условие Мс>2. Для любого числа X утверждение 9X истинно тогда и только тогда, если утверждение X не является истинным.
Найдите такое число N, при котором утверждение N истинно, но недоказуемо в данной системе.
8. Предположим, что в условии Mс>1 говорится не о «первой машине Мак-Каллоха», а о «третьей машине Мак-Каллоха». Попробуем теперь найти такое утверждение, которое было бы истинным, но недоказуемым.
9. Парадокс ли это? Вернемся вновь к задаче 1, однако внесем в нее некоторые изменения. Вместо символа P мы будем использовать символ В (в силу определенных психологических причин — каких именно, станет ясно из дальнейшего). Определение «утверждения» остается тем же, что и раньше, только на этот раз символ
Рэймонд Смаллиан счастливо сочетает в одном лице философа, логика, математика, музыканта, фокусника, юмориста, писателя и составителя великолепных задач-головоломок. Искусный писатель и великолепный юморист, Смаллиан любит облекать свои задачи в литературную форму, нередко пародирующую какие-нибудь известные произведения. Делает он это настолько хорошо, что его книги, изобилующие всякого рода парадоксами, курьезами и задачами, с удовольствием читают и те, кто даже не пытается решать задачи.В книге, которую вы держите сейчас в руках, кэрролловская Алиса из Страны Чудес и ее друзья раскрывают перед читателем нескончаемую вереницу задач-головоломок.
Книга американского профессора Р. Смаллиана, написанная в увлекательной форме, продолжает серию книг по занимательной математике и представляет собой популярное введение в некоторые проблемы математической логики. Сюда входят более 200 новых головоломок, созданных необычайно изобретательным автором. Задачи перемежаются математическими шутками, анекдотами из повседневной жизни и неожиданными парадоксами. Завершает книгу замечательная серия беллетризованных задач, которые вводят читателя в самую суть теоремы Курта Гёделя о неполноте, — одного из замечательнейших результатов математической логики 20 века. Можно сказать — вероятно, самый увлекательный сборник задач по логике.
Логические головоломки, парадоксы и курьезы, вошедшие в этот сборник, построены на материале знаменитой «Алисы в Стране Чудес» Л. Кэрролла. Известный американский математик и логик P.M. Смаллиан приглашает читателей последовать за Алисой в Страну Головоломок и вместе с ней решить множество увлекательных задач.
В книге развита теория квантового оптоэлектронного генератора (ОЭГ). Предложена модель ОЭГ на базе полуклассических уравнений лазера. При анализе доказано, что главным источником шума в ОЭГ является спонтанный шум лазера, обусловленный квантовой природой. Приводятся схемы и экспериментальные результаты исследования малошумящего ОЭГ, предназначенного для применения в различных областях военно-космической сферы.
Любую задачу можно решить разными способами, однако в учебниках чаще всего предлагают только один вариант решения. Настоящее умение заключается не в том, чтобы из раза в раз использовать стандартный метод, а в том, чтобы находить наиболее подходящий, пусть даже и необычный, способ решения.В этой книге рассказывается о десяти различных стратегиях решения задач. Каждая глава начинается с описания конкретной стратегии и того, как ее можно использовать в бытовых ситуациях, а затем приводятся примеры применения такой стратегии в математике.
Давид Гильберт намеревался привести математику из методологического хаоса, в который она погрузилась в конце XIX века, к порядку посредством аксиомы, обосновавшей ее непротиворечиво и полно. В итоге этот эпохальный проект провалился, но сама попытка навсегда изменила облик всей дисциплины. Чтобы избавить математику от противоречий, сделать ее «идеальной», Гильберт исследовал ее вдоль и поперек, даже углубился в физику, чтобы предоставить квантовой механике структуру, названную позже его именем, — гильбертово пространство.
Саймон Сингх рассказывает о самых интересных эпизодах мультсериала, в которых фигурируют важнейшие математические идеи – от числа π и бесконечности до происхождения чисел и самых сложных проблем, над которыми работают современные математики.Книга будет интересна поклонникам сериала «Симпсоны» и всем, кто увлекается математикой.На русском языке публикуется впервые.
На протяжении многих веков симметрия оставалась ключевым понятием для художников, архитекторов и музыкантов, однако в XX веке ее глубинный смысл оценили также физики и математики. Именно симметрия сегодня лежит в основе таких фундаментальных физических и космологических теорий, как теория относительности, квантовая механика и теория струн. Начиная с древнего Вавилона и заканчивая самыми передовыми рубежами современной науки Иэн Стюарт, британский математик с мировым именем, прослеживает пути изучения симметрии и открытия ее основополагающих законов.
Сколько имеется простых чисел, не превышающих 20? Их восемь: 2, 3, 5, 7, 11, 13, 17 и 19. А сколько простых чисел, не превышающих миллиона? Миллиарда? Существует ли общая формула, которая могла бы избавить нас от прямого пересчета? Догадка, выдвинутая по этому поводу немецким математиком Бернхардом Риманом в 1859 году, для многих поколений ученых стала навязчивой идеей: изящная, интуитивно понятная и при этом совершенно недоказуемая, она остается одной из величайших нерешенных задач в современной математике.
Произведения Э. Эбботта и Д. Бюргера едины по своей тематике. Авторы в увлекательной форме с неизменным юмором вводят читателя в русло важных геометрических идей, таких, как размерность, связность, кривизна, демонстрируя абстрактные объекты в различных «житейских» ситуациях. Книга дополнена научно-популярными статьями о четвертом измерении. Ее с интересом и пользой прочтут все любители занимательной математики.
Книга известного американского популяризатора науки М. Гарднера содержит множество занимательных задач и головоломок из самых различных областей математики. Благодаря удачному подбору материла, необычной форме его подачи и тонкому юмору автора она не только доставит удовольствие любителям математики, желающим с пользой провести свой досуг, но и может быть полезной преподавателям математики школ и колледжей в их работе.