Гильберт, Бернайс - Основания математики. Логические исчисления и формализация арифметики (947375), страница 35
Текст из файла (страница 35)
Однако мы можем адесь сделать и более сильное утнерждение: как покааал М. Вайсберг «), можно задать бесконечную последовательность формул исчисления предикатов таких, что все они тождественны в конечном, однако нн одна из них не выводима из остальных средствами исчисления предикатон. Результаты, показывающие необратимость теоремы 1, играют особенно важную роль в связи с вопросом о полноте исчисления предикатое. Для одноместного исчисления предикатов вопрос о его полноте решается в утвердительном смысле теоремой о том, что всякая ) Вопрос о том являются ла формулы ~Э н 10< незавясниынн друг от друга внутри всчнслевня предвлатов, был решен Гизбертом Хазенъегером, который доказал, что вн -7)у нз 70), ял )6) из 7$ по нашли основвыы правилам не выноднмы.
См. его работу: Н а ее п)а е де г 6. СЬег е1ве Лг< чоп 1)пчо11з<авй)хйе1«)ез Ргай1йа<евйарла1« бег егэ<еэ Б<э1е.— 1. ЗушЬо1<с Ьех)с, 1950, 15, р. 273 н далее. ') На это свойство формулы $ обратил внимание Курт Шютте. ') То, что формула ) 0) может быть выведена нз ~5 путем подстзновля вместо формульной переменной А, было показано в уже упоыннавшейся выше работе Хазенъегера. ') См.
% а 1 з Ь е г 9 М. Векгая гэг Ме<зшасйеша<)Ь.— Ма<Ь. Аэв., 1933, 109, Б, 200 229. 1<* [гл. гч ИСЧИСЛЕНИЕ ПРЕДИКАТОВ ВОПРОСЫ СИСТЕМАТИКИ 165 формула, тождественная в конечном, одновременно является и выводимой. Эта теорема, которую мы в дальнейшем еще должны будем доказать, представляет собой аналог теоремы о полноте дедуктивного исчисления высказываний, согласно которой всякая тождественная формула исчисления высказываний выводима из системы формул 1 — У ').
Правда, мы здесь не имеем аналога теоремы о том, что при добавлении какой-либо невыводимон формулы к числу исходных выводимой становится уже любая формула»). В самом деле, если мы к исходным формулам одноместного исчисления предикатов добавим, например, какую-либо 1-тождественную формулу, то в результате опять окажутся выводимыми только 1-тождественные — и, значит, не произвольные — формулы.
2. Экскурс в теоретико-множественную логику предикатов; предварительные замечания к вопросу о полноте; проблема разрешимости и ее уточнение с дедуктивной точки зрения. Если мы теперь начнем рассматривать исчисление преднкатов в его полном объеме, то увидим, что после всего установленного нами понятие формулы, тождествеяной в конечном, оказывается неподходящим для старта в направлении проблемы полноты, так как мы ааранее внаем, что совокупность выводимых формул является более узкой, чем совокупность формул, тождественных в конечном.
Теперь, как ввиду универсального характера логических законов, подлежащих формализации посредством нашего исчисления, так и вследствие аналогии с исчислением высказываний, напрапшвается мысль о том, чтобы ликвидировать ту исключительную роль конечного, которая находит свое отражение в понятии формулы, тождественной в конечном, и распространить понятие тождественной формулы с исчисления высказываний ка исчисление предикатов. Требующееся в связи с этим обобщение понятия тождественной формулы на случай исчисления предикатов представляет собой не что иное, как уже введенное в гл.
1 понятие о б щ е а н а ч и м о й формулы а). Однако мы ух«е там укааывали на принципиальные трудности, которые выаывает применение этого понятия в случае бесконечной нндивидяой области. Эти трудности, связанные с понятием бесконечного, как раа и были причиной того, что при уточнении пашей программы мы остановились не на положительной трактовке непротиворечивости математики в смысле в ы и о ли и и о с т н соответствующих аксиоматическнх систем, а на отрицательной — в смысле невозмохсяости получить какое-либо противоречие путем дедукции.
См. с, 96 и далее. См, с, 98. См. с. 31. В исчислении предикатов мы избежали проблематики, связанной с бесконечным, тем, что построили зто исчисление как дедуктивную систему, а не по аналогии с теорией истннностных функций. Однако в любом случае желательно познакомиться с таким излол<ением логики предикатов, которое примыкает к теории истинностных функций логики выскааываний. Этот способ излоясення логики преднкатов, который из-аа его тесной связи с теорией множеств мы будем нааывать т е о р е т и к о - м н о ж е с т в е нн ы м, безраздельно господствовал в течение длительного времени. Правда, он не удовлетворяет требованиям кашей финитной точки зрения, так как использует принцип «ге««1нт поп даспг» в применении ке только к элементам индивидной области (в Отношении которых он может рассматриваться как условие применимости исчисления предякатов), но и к целым числам н предикатам; кроме того, он требует нспольаовакия принципа выбора.
И все же различные рассмотрения, проводимые в этой теории, мы можем использовать при изучении исчисления предикатов в эвристических целях как путеводное средство, позволяющее находить теоремы н доказательства, поскольку результаты этих рассмотрений чаще всего допускают уточнения финнтного характера. Поэтому мы вкратце изложим здесь основные идеи теоретико- множественной логики преднкатов. г«ак уя«е говорилось, речь будет идти об определенном обобщении теории истинностных функций.
Подобно тому, как в этой теории мы приписывали формульным переменным А, В, значения «истнна» или «ложь», здесь аначения какой-либо пере- менной А (а) с одним аргументом а будут задаваться посредством подходящей .логической функции, т. е. такой функции, которая любому элементу индивндной области, к которой относится рассматриваемый аргумент, сопоставляет одно из значений, «истина» или «ложь».
Аналогичным образом, значение формулькой переменной с несколькимн аргументами задается логической функцией с тем же числом аргументов, пробегающих рассматриваемую нндивидную область. Логические функции находятся в теснейшей связи с множествами. Любой логической функции, зависящей от одного аргумента, соответствует множество тех элементов нз индивидной области, на которых зта логическая функция принимает значение «истина»; любой логической функции, зависящей от двух аргументов, соответствует множество тех упорядоченных пар Влементов нз рас- 166 ИСЧИСЛЕНИЕ ПРЕДИКАТОВ ВОПРОСЫ СИСТЕМАТИКИ сматриваемой индивидной области, для которых эта функция принимает значение «истина»; аналогично, функции трех аргументов соответствует множество упорядоченных троек элементов ит.
д, Применяя истинностные функции логики высказываний, мы из заданных логических функций получим новые функции этого рода, которым снова будут сопоставлены некоторые мноясества. Пусть, например, Ф (а) представляет собой логическую функцию одного аргумента. Тогда т Ф (а) будет представлять такую функцию, которая значение «истина», соответственно «ложь», принимает на тех элементах инднвидной области, на которых Ф (а) принимает значение «ложь», соответственно «истина». Множество, соответствующее функции 1Ф (а), является дополнением к мно;кеству, соответствугощему функции Ф.
Если Ф (а) и Ч' (а) — две логические функции, то Ф (а) А Ч" (а) представляет собой такую функцию, которая принимает значение «истнна» на тех и только тех элементах, на которых обе функции Ф и Ч" принимают аначение «истина». Соответствующее множество является пересечени«ж множеств, соответствующих функциям Ф и чу, т. е.
множеством элементов, принадлежащих обоим этим множествам одновременно, Точно так же функции Ф (о) ~/ Ч" (а) соответствует объединение множеств, соответствующих функциям Ф и Ч". Операции, соответствующие кванторам всеобщности и существования, понимаются как конъюнкция и дизъюнкция, распространенные на всю индивидную область. Поэтому для произвольной логической функции Ф (а) выражение 'тх Ф (х) принимает аначение «истина» плн «ложь» в зависимости от того, совпадает или пе совпадает множество, соответствующее функции Ф, со всей индивидной областью, а Лх Ф(х) принимает значение «ложь» или «истина» в зависимости от того, пусто или непусто множество, соответствующее Ф.
Если теперь в какой-либо формуле исчисления предикатов мы подставим вместо формульныл переменных логические функции с тем же самым числом аргументов и при этом все индивидные переменные окажутся связанными, то в силу укааанной интерпретацип зта формула получит одно из аначений «истина» или «ложью Если же в этой формуле имеются свободные индивидные переменные, то при всякой подстановке логических функций вместо формульных переменных рассматриваемая формула будет принимать в качестве значения некоторую новую логическую функцию.
В соответствии со скааанным, формула без свободных переменных представляет собой некоторое высказывание о логических функциях, могущих быть подставленными вместо формульных переменных. Вли же о множествах, сопоставленных этим функциям; это высказывание является истинным или ложным в зависимости от того, какое значение — «истина» или «ложь» — доставляют рассматриваемой формуле подставляемые логические функции илн соответствующие нм множества. Рассмотрим, например, формулу 7х (А (х) -~- В (х)). Для всякой пары логических функций Ф (а), Ч" (а) с соответствующими им множествами «з и ф она принимает значение «истина» тогда и только тогда, когда для всякого элемента и инднвидной области имплнкацня Ф (я) — ~ Ч' (и) принимает значение «истина», т.
е, если для всякого элеме»ла, для которого Ф принимает аначенпе «истина», Ч" также принимает значение «истина», или, выражаясь в терминах множеств, если всякий элемент множества ~Р принадлен;ит множеству ~. Таким образом, формула 7х (Ф (х) — +- Ч" (х)) равнозначна высказыванию о том, что «Р является подмполсеппвом множества ф Аналогично, формула Ух (Ф (х) Ч' (х)) выран«ает тот факт, что множества «р и «р совпадают, а формула Эх(Ф(х) д«Ч'(х)) говорит о том, что множества «Р и «р имеют непустое пересечение. Пример другого рода представляет собой формула зул (а, у).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
