Читать онлайн «Вычислимость и логика»

Вычислимость и логика COMPUTABILITY AND LOGIC Third edition GEORGE S. BOOLOS Profeuor of Phil080phy Muuc:huиtts lnatitute of Technology RICHARD С. JEFFREY Profeмor of Phil080phy Princeton Univenity ,. , ... ... . ""'-··� ___ ,. ,, "... ... ,. 4. . ,... , _,,_. ,. ... ,tllll•tut. ,. , u. ,. . ,. "_, а. ,,. м ----­ _ ,_ CAMBRIDGE UNIVERSITY PRESS CAMBRIDGE NEW YORK PORT CHESTER MELBOURNE SYDNEY Дж. Булос, Р. Джеффри Вычислим ость и логика Перевод с английского В. А. Душского и Е. Ю. Ногиной под редакцией С. Н. Артемова Москва «Мир» 1994 ББК 22. 12 Б90 УДК510 Бу. лос Дж. , Джеффри Р. Б90 Вычислимость и логика. Пер. с англ. - М. , Мир, 1994- 396с. , ил. ISBN 5-03-003067-0 Книrа известных американских математиков, . ивляющаиси в настоя­ щее времи одной иэ наиболее известных в США КИИ1' по математической логике, выдержавш&11 там три издании (1974, 1980, 1989 гг. ) . В ней со­ держатси начала и некоторые допоJIНИтеJIЬные главы математической логики, посл�оватеJIЬно и строго излаrаютси классические теореъtь1 о неразрешимости логики пр�тов и разрешимости некоторых ее фраг­ ментов, знаменитые теоремы ГёдеJIЯ о полноте, нестандартные модели и многое другое. Материал дополнен упраж:неНИJ1МИ. Для всех, кто интересуется математической логикой, а также ин­ форматикой, философией и лингвистикой. ввк 22. 12 Издание осуществлено при финансовой поддержке Российского фонда фундаментальных исследований согласно проекту 94-01-21086 Редакция . литературы no математическим наукам ISBN 5-03-003067-0 (русск. ) © Cambridge University Press 1974, ISBN 0-521-38923-2 ( ангп. ) 1980, 1989 © перевод на русский . язык, Душскиlt В. А" Ногина Е. Ю" 1994 Предисловие редактора перевода Эта книга написана профессором Массачусетского технологиче­ ского института Джорджем Булосом и профессором Принстонского университета Ричардом Джеффри на основе их многолетнего опыта преподавания логики студентам и аспирантам разных специально­ стей и является в настоящее время одной из наиболее известных в США книг по математической логике. Она может рассматриваться как учебное пособие для старше­ курсников и аспирантов ( в этом качестве она широко используется в американских университетах ) , хотя живой стиль изложения де­ лает ее весьма привлкательной для широкого круга читателей, ин­ тересующихся математической логикой, в том числе основаниями математики, информатикой , лингвистикой, философской логикой и т. д. Мы также адресуем эту книгу тем, кто решит самостоя­ тельно изучить основы логики.