Игошин Математическая логика и теория алгоритмов (1019110), страница 95
Текст из файла (страница 95)
эффективно узнать, истинно ли высказывание Р(т, п). Следовательно, Р(х, у) — такой вычислимый предикат, что Ц = [х: (Зу)(1.[Р(х, у)] = !)). Сформулируем теперь определение. Определение 37.9. Формальная арифметика называется адекватной, если лля каждого перечислимого множества Ц натуральных чисел существует вполне представимый в этой арифметике предикат Р(х, у) такой, что Ц = [х: (Лу)(Х[Р(х, у)] = 13. Под полнотой формальной арифметики будем понимать абсолютную полноту, т.е.
если для каждой замкнутой формулы Рэтой теории либо она сама, либо ее отрицание является теоремой этой теории: »- Р или ь- — Р. Теперь мы можем перейти непосредственно к формулировке и доказательству теоремы Геделя. Теорема Геделя о неполноте. Теорема утверждает следующее.
Всякая го-непротиворечивая и адекватная формальная арифметика не является полной. Доказательство. Согласно теореме 35.7, выберем такое множество Ц натуральных чисел, которое перечислимо, но неразрешимо. Так как наша формальная арифметика адекватна, то существует вполне представимый в ней перидикат Р(х, у) такой, что («) Д = [х: (Лу)(к[Р(х, у)] = 1)). Вполне представимость предиката Р(х, у) в формальной арифметике означает, что найдется такая формула Р(х, у) этой теории, содержащая лишь две свободных предметных переменных, что для каждой пары натуральных чисел (а, Ь), для которой Х[Р(а, Ь)] = 1, имеет место теорема: ь- Р(а*, Ь*), а для каждой пары натуральных чисел (а, Ь), для которой 7[Р(а, Ь)] = О, имеет место теорема: Р(а*, Ь*), Применим к формуле Р(х, у) квантор общности по переменной у.
Получим формулу с единственной свободной предметной переменной х: б(х) =— (Лу)(Р(х, у)). Покажем, что 382 (вФ) Предположим, что и в О. Тогда (согласно (*.)) найдется такое натуральное л, что высказывание Р(т, и) истинно. Следовательно, имеет место теорема: ~- Г(т*, л'). В силу аксиомы арифметики (АА) имеем теорему: Г(т* л*) + (Лу)(Г(т* у)). Из двух последних теорем по правилу МР заключаем: ~- (ЛУ)(Г(т*, у)), т.е.
~- 6(т*). Это означает, что и в (х: ~- 6(х*)). Таким образом, Д с (х: ~- ~- 6(х*)). Обратно, предположим, что а в (х: ь- 6(х')), т.е. ~- 6(т*), т.е. ~- (Лу)(Г(а*, у)). Отсюда, в силу известного выражения (по закону де Моргана) квантора существования через квантор общности, заключаем, что ~- — (~УУ)(- Г(а*, у)), Поскольку наша формальная арифметика, кроме того, со-непротиворечива, то, ввиду наличия в ней последней теоремы, должно существовать такое натуральное число лм что формула Г(т*, ло) не является теоремой этой арифметики. А раз так, то высказывание Р(т, ло) истинно (если бы оно было ложно, то мы имели бы теорему ~- -Г(т*, ло), что не так). По определению (~) множества Д, это означает, что и в Ц.
Таким образом, (х: ~- 6(х*)) с Д. Итак, равенство (*~) доказано. Теперь выясним, в каком отношении находятся между собой множества Ц (дополнение Д) и (х: ~- 6(х*)). Пусть и в (х: ~- 6(х*)), т.е. ь- — 6(х'). Тогда т в Д, ибо если бы и в Д, то в силу ( .*) мы имели бы ~ — 6(т*) и наша формальная арифметика была бы противоречивой, но это не так в силу ее гв-непротиворечивости (по условию) и теоремы 37.7.
Таким образом, (х: ~- 6(х*)) <= Д. Покажем, что последнее включение является строгим. Напомним, что мы выбрали множество Д перечислимым, но не являющимся разрешимым. Тогда согласно следствию 37.5 из теоремы 37.4, никакая формальная теория не может быть полной для 9 Равенство (е~) говорит, что наша формальная арифметика полуполна для Д.
Если бы имело место равенство Ц = (х: ~- 6(х*)), то это означало бы, что наша формальная арифметика полуполна и лля Д и, значит, она была бы полной для Ц. Последнее невозможно в силу следствия 37.5 из теоремы 37.4. Следовательно, (х: ь- 6(х')) ~ О. Итак (х: ~- —,6(х*)) с Д.
Следовательно, существует такое число то в О, что т, в (х: ~ — 6(х*)), т.е. неверно, что ~- — 6(т*,). В то же время неверно также, что ь- 6(т,*), поскольку это, в силу (**), 383 означало бы, что т, е О, а это не так. Следовательно, мы нашли формулу 6(т»), такую, что ни она сама, ни ее отрицание 6(щ,) не являются теоремами нашей формальной арифметики. Это и оз начает, что данная формальная арифметика не является полной, Теорема Геделя полностью доказана.
С) Обратимся еше раз к высказыванию 6(т»). Согласно равен ству (*»), его можно интерпретировать как т» е Д и, следова тельно, оно обязательно является «истинным» высказыванием. Но тем не менее оно не является теоремой нашей формальной ариф метики. Если добавить формулу 6(т*) к списку аксиом и рассмотреть новую формальную арифметику, то положение не изменится: для вновь полученной формальной арифметики верны все те предпосылки, которые привели нас к теореме Геделя. Значит, мы снова найдем такое число ль, что высказывание 6(гл*,) истинно, но не является теоремой новой формальной арифметики и т.д. Гедель и его роль в математической логике ХХ в.
Курт Гедель родился 28 апреля 1906 г. в г. Брюнне (ныне г. Брно в Чехии). Окончил Венский университет, где защитил докторскую диссертацию и был доцентом в период !933 — 1938 гг. После оккупации Австрии фашистской Германией эмигрировал в США. С 1940 по 1963 г. Гедель работает в Принстонском институте высших исследований (с 1953 г. он профессор этого института). Гедель — почетный доктор Йельского и Гарвардского университетов, член Национальной академии наук США и Американского философского общества. В 195! г.
Гедель удостоен высшей научной награды США— Эйнштейновской премии. В статье, посвященной этому событию, другой крупнейший математик нашего времени Джон фон Нейман писал: «Вклад Курта Геделя в современную логику поистине монументален. Это — больше, чем просто монумент, это веха, разделяющая две эпохи... Без всякого преувеличения можно сказать, что работы Геделя коренным образом изменили сам предмет логики как науки». Гедель заложил основы целых разделов математической логики: теории моделей (1930), конструктивной логики (1932 — 1933), формальной арифметики (1932 — 1933), теории алгоритмов и рекурсивных функций (!934), аксиоматической теории множеств (1938).
Гедель умер в Принстоне (США) 14 января 1978 г. Г л а в а Ч111 МАТЕМАТИЧЕСКАЯ ЛОГИКА И КОМПЬЮТЕРЫ, ИНФОРМАТИКА, ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ Образно выражаясь, можно сказать, что компьютер состоит из материальной части и математического (программного) обеспечения, или, используя профессиональную лексику, из «железа» и «обуви», И к тому, и к другому имеет самое непосредственное отношение математическая логика, ни первое, ни второе без математической логики обойтись не могут. В в 12 и 13 было рассмотрено применение математической логики к релейно-контактным (переключательным) схемам, являющимся неотъемлемой составной частью современного компьютера.
Часть настоящей главы также посвящена вопросам взаимодействия математической логики и компьютеров. Так, в В 38 рассказывается о применении математической логики к языкам программирования и к самому процессу программирования и получающимся в результате этого программам. В 8 39 лается характеристика обратного процесса — применению компьютеров лля поиска доказательств теорем математической логики и других математических дисциплин.
Значительное внимание уделено методу резолюций для доказательства теорем в исчислениях высказываний и предикатов. В 8 40 кратко описывается язык ПРОЛОГ— принципиально новый язык программирования, выросший непосредственно из математической логики (логики.предикатов) и призванный стать языком компьютеров пятого поколения. В свою очередь, информатика как наука начала оформляться вместе с созданием и бурным развитием вычислительной техники. Ее формирование и определение ее предмета продолжаются по настоящее время.
Информатика — наука о хранении, обработке и передаче информации с помощью компьютеров. Она включает в себя крупные разделы, изучающие алгоритмические, программные и технические средства хранения, обработки и передачи информации. Математическая логика оказалась единственной математической наукой, методы которой стали мощнейшими инструментами познания во всех разделах информатики. Поэтому сколько-нибудь серьезное изучение информатики немыслимо без освоения основ математической логики. Вторая часть настоящего раздела посвящена тем вопросам математической логики, которые находят наиболее яркое примене- 385 И о»и ние в информатике, а также краткому показу того, как математи ческая логика работает в некоторых разделах информатики.
Здесь будет рассказано о применении математической логики при ис следованиях, посвященных базам данных, базам знаний Я 41) и системам искусственного интеллекта (э 42). й 38. Математическая логика и программное обеспечение компьютеров Чтобы компьютер работал, он должен быть оснащен программным обеспечением, т.е. комплексом программ, ориентирующих компьютер на решение задач того или иного класса. (Слово «программа» имеет греческое происхождение и означает «объявление», «распоряжение».) Уже само понятие компьютерной программы, предусматривающее четкое алгоритмическое предписание компьютеру о порядке и характере действий, предусматривает проникновение в программу, а также в процесс ее составления (в программирование) теории алгоритмов.
Но при более пристальном рассмотрении процесс проникновения логики в программы и программирование оказывается значительно более глубоким и органичным. Не только один ее раздел — теория алгоритмов — работает здесь, но исключительно действенным оказывается само существо математической логики — ее язык, ее аксиоматические теории, выводы и теоремы в них, свойства этих теорий. В данном параграфе дается краткий обзор основных направлений, по которым математическая логика внедряется в программирование, из которых программирование возникло и без которых существовать не может.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
