Формулы мат логика: Математическая логика · oнлайн с подробным объяснением

Содержание

Теория моделей – Гуманитарный портал

Теория моделей — это раздел математической логики (см. Логика математическая), изучающий модели формальных теорий, соотношения между моделями и теориями, а также преобразования моделей. Под моделями в математической логике понимаются интерпретации каких-либо логико-математических положений и их систем в контексте логической семантики. Теория моделей возникла как обобщение существующих подходов решения метаматематических проблем, связанных с алгеброй и математической логикой. Сами эти подходы существовали давно, но при этом длительное время не рассматривались во всей своей общности, в рамках единой логической системы. Предшественниками теории моделей были Б. Больцано и Э. Шрёдер, осознавшие понятие выполнимости формулы на интерпретации. Основное развитие теория моделей получила в работах А. Тарского, А. И. Мальцева и А. Робинсона. Название «теория моделей» было впервые предложено А.

Тарским в 1954 году.

В настоящее время теория моделей делится на следующие разделы:

Классическая теория моделей, изучающая теоретико-множественные модели классических теорий.
Алгебраическая теория моделей, изучающая прежде всего модели неклассических логик (см. Логики неклассические), базирующиеся на обобщённой семантике истинностных значений.
Теория моделей С. Крипке, изучающая модели неклассических логик, базирующиеся на семантике возможных миров (см. Семантика возможных миров).
Интерпретации реализуемости, моделирующие логики и теории как исчисления задач.

Классическая теория моделей берёт своё начало от работ Л. Лёвенгейма (1915) и Т. Скулема (1920), установивших существование моделей любой бесконечной мощности для любой непротиворечивой теории, имеющей бесконечную модель. Этот результат вначале рассматривался как парадоксальный, потому что из него следовало существование счётных моделей несчётных множеств, а мощность множества в те времена содержательно интерпретировали как число элементов, по аналогии с конечными множествами, а не как сложность его задания, как сейчас делается по аналогии с

теорией алгоритмов.

Фундаментальным результатом классической теория моделей стала теорема К. Гёделя о полноте классической логики предикатов (первого порядка), из которой следует существование моделей у любых (основанных на этой логике) непротиворечивых теорий. В 1970-е годы выяснилось, что теорема Гёделя о полноте эквивалентна аксиоме выбора теории множеств.

Если задана некоторая сигнатура (перечисление констант, функциональных символов и предикатов вместе с числом аргументов у них), то (классической) интерпретацией данной сигнатуры является непустое множество объектов — универсум интерпретации, и функция вычисления значения

ζ, сопоставляющая каждой константе — элемент универсума, n-местной функции f — функционал Uⁿ → U, n-местному предикату Ρ — функционал Uⁿ → {0, 1}. В интерпретации естественно определяется понятие значения любого терма и любой формулы теории (точное определение истинности формулы в интерпретации было впервые дано А.

Тарским). Интерпретация называется моделью теории, если в ней истинны все аксиомы теории. Ещё одной формулировкой теоремы полноты Гёделя является совпадение множества теорем с множеством формул, истинных в любой модели теории.

Согласно теореме А. И. Мальцева о компактности, теория имеет модель тогда, и только тогда, когда любое конечное число её аксиом имеет модель. Эта теорема послужила основой для построения нестандартных моделей традиционных математических объектов, таких, как действительные и натуральные числа. В самом деле, взяв в качестве теории все истинные на стандартной модели формулы и добавив новое число

ω и бесконечную совокупность аксиом ω> 0, ω> 1, ω > n, мы получаем, что любая конечная совокупность новых аксиом удовлетворяется на стандартной модели. Значит, есть и модель, где они все выполнены. Она сохраняет все выразимые на языке логики предикатов свойства стандартной модели, но пополнена новыми элементами.

Позитивно использовал существование нестандартных моделей А. Робинсон (1960). Он показал, что в нестандартной модели анализа можно на строгой основе возродить методы математиков XVII–XVIII веков, использовавших бесконечно малые и бесконечно большие величины. Основополагающим явился здесь результат, что любое конечное нестандартное число однозначно разлагается в сумму стандартного и бесконечно малого. Далее, сохранение всех выразимых свойств используется для установления принципов переноса, которые позволяют отбрасывать бесконечно малые либо доказывать общее утверждение о стандартных числах на основе рассмотрения одной бесконечно малой либо бесконечно большой величины. Но здесь приходится строго разделять формулы стандартного языка и формулы метаязыка, говорящего о нестандартной модели. В частности, утверждения, явно включающие предикат «быть [не] стандартным», уже могут нарушать все свойства стандартной модели. Дальнейшее развитие нестандартного анализа привело к теории полумножеств Г.

Хаека и к альтернативной теории множеств С. Вопенки, где конечные нестандартные совокупности могут включать бесконечные подклассы.

Современная классическая теория моделей развивается во многих направлениях, большинство из которых в данный момент имеют дело со сложнейшими идеальными математическими понятиями (абстрактными объектами) без выхода на общенаучные либо методологические результаты. Определённым исключением здесь является совокупность теорем, характеризующих теории частного вида через их модели.

Алгебраическая теория моделей берёт своё начало от предложенной А. Линденбаумом и А. Тарским концепции, согласно которой любая теория может рассматриваться как алгебра, операциями которой являются логические связки, а объектами — классы формул, для которых доказуема эквивалентность. Такая алгебра называется алгеброй Линденбаума — Тарского (ЛТ-алгеброй) теории. ЛТ-алгебра классической теории — это булева алгебра. ЛТ-алгебра интуиционистской теории — это псевдобулева алгебра, теории в модальной логике S4 — это булева алгебра с замыканиями.

Данный подход был вторым основанием и инструментом для построения альтернативной теории множеств. Для неклассических логик он математически эквивалентен семантике возможных миров и поэтому в последнее время употребляется менее интенсивно. Известной трудностью в алгебраической теории моделей является интерпретация кванторов. Для данной цели была развита теория цилиндрических алгебр.

Семантика возможных миров предлагалась уже Аристотелем, который рассматривал теорию модальных суждений. Её предшественником можно считать Г. В. Лейбница, который явно ввёл понятие возможного мира. В современном виде она впервые была предложена для частного случая интуиционистской логики Э. Бетом (1954) и последовательно развита для целого ряда логик С. Крипке, имя которого она и получила. При интерпретациях в семантике возможных миров имеется некоторая алгебраическая система классических (либо, в более тонких случаях, алгебраических) моделей, называемых мирами, связанных отношениями и порой функциями.

Для модальных логик интерпретации в семантике возможных миров обычно используют единственное бинарное отношение достижимости. Логика L называется шкальной, если любая интерпретация с той же системой миров, что у модели L, также является моделью L. Таким образом, шкальные логики накладывают ограничения не на отдельные миры, а на их внешние взаимосвязи. Один из наиболее интересных результатов современной семантики возможных миров — перечисление всех суперинтуиционистских и модальных пропозициональных логик, обладающих интерполяционным свойством Крейга: для любой доказуемой импликации A ⇒ B найдётся формула C, содержащая лишь термины, общие для A и B, такая, что доказуемы A ⇒ C и C ⇒ B. В работах Л. Л. Максимовой показано, что логик, обладающих свойством Крейга, конечное число. Математическая структура вынуждения, использованная П. Дж. Коэном как промежуточный шаг для построения нестандартных классических моделей теоретико-множественных систем, позднее получила название моделей Крипке для интуиционистской логики.

С их помощью решена проблема Гилберта: доказана независимость аксиомы выбора и континуум-гипотезы. Далее, теми же методами установлена невозможность явного построения, в частности, неизмеримого множества действительных чисел и нестандартной модели анализа. Исторически это было одно из первых применений семантики возможных миров.

Последний класс моделей — интерпретации реализуемости. Колмогоровская интерпретация допускает значительную гибкость в классе используемых функционалов, поэтому в интерпретациях реализуемости используются и алгоритмы, и топологические пространства с непрерывными преобразованиями, и категории, и формальные выводы, и комбинации данных объектов. Наиболее значительные в методологических аспектах результаты, полученные за последнее время при помощи интерпретаций реализуемости, следующие. Доказана совместимость с интуиционистской математикой моделей брарровских концепций творящего субъекта и беззаконных последовательностей и построены модели вычислимости, основанные на данных концепциях.

Таким образом, обосновано, что содержательный вычислительный метод может быть представлен как композиция алгоритма, творческого процесса и физических измерений. Доказано, что для многих аксиоматических систем добавление аксиомы выбора к конструктивному анализу и к теории множеств с интуиционистской логикой не нарушает эффективности доказательств. Таким образом, аксиома выбора на самом деле не приводит сама по себе к чистым теоремам существования; в данном смысле она концептуально противоречит закону исключённого третьего (см. Закон исключённого третьего), который с необходимостью приводит к таким теоремам.

Математическая логика | это… Что такое Математическая логика?

Математи́ческая ло́гика (теоретическая логика, символическая логика) — раздел математики, изучающий доказательства и вопросы оснований математики. «Предмет современной математической логики разнообразен.»^[1] Согласно определению П. С. Порецкого, «математическая логика есть логика по предмету, математика по методу». Согласно определению Н. И. Кондакова, «математическая логика — вторая, после традиционной логики, ступень в развитии формальной логики, применяющая математические методы и специальный аппарат символов и исследующая мышление с помощью исчислений (формализованных языков).»^[2] Это определение соответствует определению С. К. Клини: математическая логика — это «логика, развиваемая с помощью математических методов».^[3] Также А. А. Марков определяет современную логику «точной наукой, применяющей математические методы».^[4] Все эти определения не противоречат, а дополняют друг друга.

Применение в логике математических методов становится возможным тогда, когда суждения формулируются на некотором точном языке. Такие точные языки имеют две стороны: синтаксис и семантику. Синтаксисом называется совокупность правил построения объектов языка (обычно называемых формулами). Семантикой называется совокупность соглашений, описывающих наше понимание формул (или некоторых из них) и позволяющих считать одни формулы верными, а другие — нет.

Важную роль в математической логике играют понятия дедуктивной теории и исчисления. Исчислением называется совокупность правил вывода, позволяющих считать некоторые формулы выводимыми. Правила вывода подразделяются на два класса. Одни из них непосредственно квалифицируют некоторые формулы как выводимые. Такие правила вывода принято называть аксиомами. Другие же позволяют считать выводимыми формулы , синтаксически связанные некоторым заранее определённым способом с конечными наборами выводимых формул. Широко применяемым правилом второго типа является правило modus ponens: если выводимы формулы и , то выводима и формула .

Отношение исчислений к семантике выражается понятиями семантической пригодности и семантической полноты исчисления. Исчисление И называется семантически пригодным для языка Я, если любая выводимая в И формула языка Я является верной. Аналогично, исчисление И называется семантически полным в языке Я, если любая верная формула языка Я выводима в И.

Математическая логика изучает логические связи и отношения, лежащие в основе логического (дедуктивного) вывода, с использованием языка математики^{[источник не указан 736 дней]}.

Многие из рассматриваемых в математической логике языков обладают семантически полными и семантически пригодными исчислениями. В частности, известен результат К. Гёделя о том, что так называемое классическое исчисление предикатов является семантически полным и семантически пригодным для языка классической логики предикатов первого порядка. С другой стороны, имеется немало языков, для которых построение семантически полного и семантически пригодного исчисления невозможно. В этой области классическим результатом является теорема Гёделя о неполноте, утверждающая невозможность семантически полного и семантически пригодного исчисления для языка формальной арифметики.

Стоит отметить, что на практике множество элементарных логических операций является обязательной частью набора инструкций всех современных микропроцессоров и соответственно входит в языки программирования. Это является одним из важнейших практических приложений методов математической логики, изучаемых в современных учебниках информатики.

Содержание

1 Разделы математической логики
2 См. также
3 Примечания
4 Литература
5 Ссылки

Разделы математической логики

Алгебра логики
Логика высказываний
Теория доказательств
Теория моделей

См. также

Формальная логика
Неполнота математики
Формальная система
Теорема Гёделя о неполноте
Недоказуемые утверждения
Аксиома
Граница множества
Логическое программирование
Доказательное программирование
Логика в информатике
язык Пролог

Примечания

↑ С. И. Адян, Математическая энциклопедия, М.: «Советская энциклопедия», т.3, с. 568, 571.
↑ Н. И. Кондаков, Логический словарь-справочник, М. : «Наука», 1975, с. 259.
↑ С. К. Клини, Математическая логика, М., 1973, с.12.
↑ А. А. Марков, Большая советская энциклопедия, Изд. 3, Предмет и метод современной логики.

Литература

Формальная логика. (Учебник.) Часть вторая. СИМВОЛИЧЕСКАЯ ЛОГИКА. Отв. редактор: доц. И. Н. Бродский. — Л.: ЛГУ, 1977.
Марков А. А.. Элементы математической логики. М.: Изд-во МГУ, 1984.
Новиков П. С. Элементы математической логики. 2-ое изд. М.: Наука, 1973. — 400 с.
Столл Р. Р. Множества. Логика. Аксиоматические теории. М.: Просвещение, 1968. — 232 с.
Стяжкин Н. И. Формирование математической логики. М.: Наука, 1967. 508 с.
Шенфилд Дж. Математическая логика. М.: Наука, 1975.

Ссылки

для представления соединения, v для представления дизъюнкции и для представления отрицания. В этой статье давайте обсудим некоторые основы математической логики, формулы математической логики, а также таблицу истинности и некоторые примеры математической логики с ответами.

История математической логики

Математическая логика возникла как предмет математики в середине XIX века, объединив две традиции: формально-философскую логику и математику. Математическая логика, иногда известная как «логистическая логика», «символическая логика», «алгебра логики», а в последнее время просто «формальная логика», представляет собой совокупность логических идей, разработанных в предыдущем (девятнадцатом) столетии с использованием искусственная запись и строго дедуктивная процедура. До этого логика изучалась с помощью риторики, вычислений, силлогизма и философии. В первой половине двадцатого века произошло множество важных прорывов, сопровождавшихся жаркими спорами об основах математики.

Classification of Mathematical Logic

The Mathematical logic can be subdivided into four different fields which are as follows:

Set Theory
Recursion Theory
Model Theory
Proof Theory

Несмотря на то, что многие подходы и результаты являются общими для различных дисциплин, каждый из них имеет свою специализацию. Границы, отделяющие математическую логику от других разделов математики, а также линии, разделяющие эти области, не всегда ясны. Теорема Гёделя о неполноте важна не только в теории рекурсии и теории доказательств, но и в модальной логике, поскольку она привела к теореме Лёба. Теория множеств, теория моделей и теория рекурсии, а также изучение интуиционистской математики используют принудительный подход.

Теория множеств

Изучение множеств, представляющих собой абстрактные группы элементов, известно как теория множеств. Кантор неофициально определил многие из фундаментальных понятий, таких как порядковые и количественные числа, до того, как были построены формальные аксиоматизации теории множеств. Первая такая аксиоматизация, приписываемая Цермело, была несколько расширена, чтобы сформировать теорию множеств Цермело – Френкеля (ZF), которая сегодня является наиболее широко используемой математической фундаментальной теорией.

Теория моделей

Теория моделей – это изучение моделей различных формальных теорий. Теория — это набор формул с определенной формальной логикой и сигнатурой, тогда как модель — это структура, обеспечивающая осязаемую интерпретацию теории. Теория моделей тесно связана с универсальной алгеброй и алгебраической геометрией, но ее методы делают упор на логические вопросы, а не на вопросы этих предметов.

Элементарный класс — это множество всех моделей данной теории; Классическая теория моделей направлена на обнаружение особенностей моделей в данном элементарном классе или на то, составляют ли определенные виды структур элементарные классы.

Теория рекурсии

Вычислимость функций из натуральных чисел в натуральные числа является предметом классической теории рекурсии. Используя машины Тьюринга, исчисление и другие системы, основные результаты создают устойчивый канонический класс вычислимых функций с несколькими независимыми эквивалентными характеристиками. Структура тьюринговых степеней и решетка рекурсивно перечислимых множеств — еще два дополнительных вывода.

Математические логические операторы

В математике используются три основных математических логических оператора. Это:

Соединение или (И)
Дизъюнкция или (ИЛИ)
Отрицание или (НЕ)

Теперь давайте подробно рассмотрим все эти логические операторы.

Соединение или (И)

Вы можете легко соединить два оператора математической логики, используя операнд И. Его также называют соединением. Вы можете представить его в виде символа как ∧. В этом операторе, если одно из утверждений ложно, то и результат ложен. Если оба утверждения верны, то и результат верен. Входных данных может быть два или более, но на выходе вы получите только один.

Truth Table of the Conjunction (AND) Operator

Input A	Input B	Output A AND B (A ∧ B)
True	True	True
True	False	False
	False

	. 0003	True	False
False	False	False

DISJUMPAT операнд ИЛИ. Его также называют дизъюнкцией. Вы можете представить это в символической форме как ∨. В этом операторе, если одно из утверждений истинно, то и результат, который вы получаете, верен. Если оба утверждения ложны, то и результат ложен. Он состоит из двух или более входов, но только одного выхода.

Truth Table of the Disjunction (OR) Operator

0083

Input A	Input B	Output A OR B (A V B)
True	True	True
True	ЛЕСС	TRUE
FALSE 9003
FALSE
9000 3
9000	True	True
False	False	False

Negation or (NOT)

Negation is an operator that gives the opposite statement of the заявление, которое дано. Его также называют НЕ и обозначают ∼. Это операция, которая дала бы противоположный результат. Когда ввод истинен, вывод, который вы получаете, ложен. Когда ввод ложен, вывод, который вы получаете, верен. Он состоит из одного входа и одного выхода.

Truth Table of the Negation (NOT)

Input	Output
A	Negation A (∼ A)
True	False
False	True

Matematic Logics Проблемы

Теперь, когда вы знаете о логическом логическом примере.

Пример 1:

Постройте таблицу истинности значений конъюнкции для следующих утверждений:

r: x — нечетное число

s: x — простое число

Решение:

Дано:

r: x — нечетное число

s: x — простое число

Поскольку каждое приведенное утверждение представляет собой открытое предложение, истинностное значение r∧s будет зависеть от значения переменной x. Поскольку существует бесконечное количество замещающих значений для x, вы не можете перечислить все значения истинности для r∧s в таблице истинности. Однако вы можете найти истинное значение r∧s для заданных значений x следующим образом:

Если x = 3, то r истинно, а s истинно. Следовательно, конъюнкция r∧s истинна.

Если x = 9, r истинно, а s ложно. Следовательно, конъюнкция r∧s ложна.

Если x = 2, r ложно, а s истинно. Следовательно, конъюнкция r∧s ложна.

Если x = 6, r ложно, а s ложно. Следовательно, конъюнкция r∧s ложна.

0399999.

x Значение	Ввод r	Ввод 90	Output r AND s (r∧s)
3	True	True	True
9	True	FALSE	FALSE
2	ЛЕСС	TRUE	FALSE
FALSE
FALSE
6	False	False	False

Example 2:

Find the negation of the given statement:

Number 4 is an even number

Solution:

Считать P заданным оператором

Следовательно, P = 4 — четное число.

Таким образом, отрицание утверждения дается как

∼S = 4 не является четным числом.

Следовательно, отрицание утверждения состоит в том, что 4 не является четным числом.

Заключение

Логика простыми словами означает рассуждать. Это рассуждение может быть юридическим заключением или даже математическим подтверждением. Некоторыми из основных математических логических операторов являются конъюнкция, дизъюнкция и отрицание. В этой статье давайте обсудим некоторые основы математической логики.

4.2: Сложность формул — Mathematics LibreTexts

Последнее обновление
Сохранить как PDF

Идентификатор страницы: 9701

Кристофер Лири и Ларс Кристиансен
SUNY Geneseo и Университет Осло через Open1SUNY 9040
Работаем на языке теории чисел
\[\mathcal{L}_{NT} = \{ 0, S, +, \cdot, E, < \},\] 9y\), а не \(Exy\) или \(xEy\).
Один из способов думать о простейших формулах языка натуральных чисел (фактически любого языка) — это формулы, которые не содержат никаких кванторов. Кажется естественным, что формула \(S0 = y\) проще, чем \(\forall x S 0 = y\). На один маленький шаг сложнее бескванторных формул являются формулы, содержащие то, что мы будем называть ограниченными кванторами:
Определение 4.2.1.
Если \(x\) переменная, не входящая в терм \(t\), условимся использовать следующие сокращения:
\[ \left( \forall x < t \right) \phi \: \text{means} \: \forall x \left( x < t \rightarrow \phi \right) \\ \left( \forall x \leq t \right) \phi \: \text{means} \: \forall x \left( \left( x < t \lor x = t \right) \rightarrow \phi \right) \\ \left( \ существует x < t \right) \phi \: \text{means} \: \exists x \left( x < t \land \phi \right) \\ \left( \exists x \leq t \right) \phi \: \text{means} \: \exists x \left( \left( x < t \lor x = t \right) \land \phi \right).\]
Эти сокращения составят набор из ограниченных кванторов .
Таким образом, формула \(\exists x \left( \left( \forall y < \overline{42} \right) y = Sx \right)\) является формулой с одним ограниченным квантором и одним неограниченным квантором.
Помните, что наша цель состоит в том, чтобы создать предложение, истинное в \(\mathfrak{N}\) и недоказуемое из нашего набора аксиом. Можем ли мы найти такую формулу, которая содержит только ограниченные кванторы? Это было бы очень здорово, но, к сожалению, этого не произойдет. Помните наш набор аксиом \(N\) из раздела 2.8? Если вы вернетесь к этому разделу, вы увидите, что все эти аксиомы являются истинными утверждениями о натуральных числах, поэтому они должны быть следствием любого потенциального набора аксиом для \(Th \left( \mathfrak{N} \right) \). Но \(N\) на самом деле довольно сильный набор утверждений. В частности, \(N\) достаточно надежен, чтобы доказать каждое истинное утверждение о \(\mathfrak{N}\), содержащее только ограниченные кванторы. Более того, \(N\) может опровергнуть каждое ложное утверждение, содержащее только ограниченные кванторы. Мы докажем этот факт в предложении 5.3.14. Поскольку любой потенциальный кандидат на аксиоматизацию \(\mathfrak{N}\) должен быть не менее сильным, чем \(N\), это говорит нам о том, что наш поиск формулы, которая одновременно верна в \(\mathfrak{N} }\) и недоказуемы должны смотреть на формулы, которые содержат хотя бы несколько неограниченных кванторов.
Определение 4.2.2.
Набор \(\Sigma\)-формул определяется как наименьший набор \(\mathcal{L}_{NT}\)-формул такой, что:
1. Каждая атомарная формула является \( \Сигма\)-формула.
2. Всякое отрицание атомарной формулы является \(\Сигма\)-формулой.
3. Если \(\alpha\) и \(\beta\) являются \(\Sigma\)-формулами, то \(\alpha \land \beta\) и \(\alpha \lor \beta\) являются \ (\Сигма\)-формулы.
4. Если \(\alpha\) является \(\Sigma\)-формулой, а \(x\) является переменной, не входящей в терм \(t\), то следующие \(\Sigma\ )-формулы: \(\left( \forall x < t \right) \alpha\), \(\left( \forall x \leq t \right) \alpha\), \(\left( \exists x < t \right) \alpha\), \(\left( \exists x \leq t \right) \alpha\).
5. Если \(\alpha\) является \(\Sigma\)-формулой и \(x\) является переменной, то \(\left( \exists x \right) \alpha\) является \(\Sigma \)-формула.
Позже мы докажем (теорема 5.3.13), что на самом деле наш набор аксиом \(N\) достаточно силен, чтобы доказать каждое истинное \(\Sigma\)-предложение, так что даже эти формулы недостаточно сложны, чтобы установить результат незавершенности. Однако, если вместо того, чтобы допустить неограниченный квантор существования, мы допустим неограниченный квантор всеобщности, ситуация изменится.
Определение 4.2.3.
Совокупность \(\Pi\)-формул является наименьшим набором \(\mathcal{L}_{NT}\)-форм, таких что:
1. Каждая атомарная формула является \(\Pi \)-формула.
2. Всякое отрицание атомарной формулы является \(\Pi\)-формулой.
3. Если \(\alpha\) и \(\beta\) являются \(\Pi\)-формулами, то \(\alpha \land \beta\) и \(\alpha \lor \beta\) являются \ (\Pi\)-формулы.
4. Если \(\alpha\) является \(\Pi\)-формулой, а \(x\) является переменной, не входящей в терм \(t\), то следующие \(\Pi\ )-формулы: \(\left( \forall x < t \right) \alpha\), \(\left( \forall x \leq t \right) \alpha\), \(\left( \exists x < t \right) \alpha\), \(\left( \exists x \leq t \right) \alpha\).
5. Если \(\alpha\) является \(\Pi\)-формулой и \(x\) является переменной, то \(\left( \forall x \right) \alpha\) является \(\Pi \)-формула.
Итак, в то время как множество \(\Sigma\)-формул замкнуто относительно ограниченной квантификации и неограниченной экзистенциальной квантификации, совокупность \(\Pi\)-форм замкнута относительно ограниченной квантификации и неограниченной универсальной квантификации.
Главный результат оставшейся части книги, первая теорема Гёделя о неполноте, утверждает, что если нам дан любой непротиворечивый и разрешимый набор аксиом, то будет \(\Pi\)-формула \(\sigma\) такая что \(\sigma\) является верным утверждением о натуральных числах, но из наших аксиом формулы \(\sigma\) не следует вывода. Таким образом, наш набор аксиом должен быть неполным. Достижение этой теоремы займет у нас все оставшееся время.
Вы могли заметить, что каждое отрицание \(\Sigma\)-формулы логически эквивалентно \(\Pi\)-формуле, и наоборот (см. упражнение 3). Если мы возьмем пересечение набора \(\Sigma\)-формул и набора \(\Pi\)-формул, мы получим \(\Delta\)-формул:
Определение 4.2.4.
Набор \(\Delta\)-формул является пересечением набора \(\Sigma\)-форм с множеством \(\Pi\)-формул.
Таким образом, в каждой \(\Delta\)-формуле все кванторы ограничены. Выяснится, что наш таинственный (ну, на самом деле не такой уж и таинственный) набор аксиом \(N\) достаточно силен, чтобы доказать любую истинность в-\(\mathfrak{N}\) \(\Delta\ )-формулы и опровергнуть каждую ложную-в-\(\mathfrak{N}\) \(\Delta\)-формулу. Это будет очень важно для нас.
1. Ссылаясь на определение 4.2.2, объясните подробно, почему следующие формулы являются (или не являются) \(\Sigma\)-формулами.
  (a) \(S0 + S0 = SS0\)
  (b) \(\neg \left( 0 < 0 \lor 0 < S0 \right)\)
  (c) \(\left( \forall x < \overline{17} \right) x < \overline{17}\)
  (d) \(S0 \cdot S0 = S0 \land \left( \exists y < x \right) \left( \exists z < y \right) y + z = x\)
  (e) \(\left( \forall y \right) \left( y < 0 \rightarrow 0 = 0 \right)\)
  (f) \(\left( \существует x \справа) \слева( x < x \справа)\)
2. Давайте определим набор классных формул как наименьший набор \(\mathcal{L}_{NT}\)-формул, который:
  (a) Содержит все атомарные формулы.
  (b) Содержит все отрицания атомарных формул.
  (c) Замкнут под связками \(\land\) и \(\lor\).
  (d) Замкнут относительно ограниченных кванторов и квантора \(\существует\)
  Докажите, что формула классная тогда и только тогда, когда формула является \(\Сигма\)-формулой. (Четыре приведенных выше условия иногда используются для определения набора \(\Sigma\)-формул. Вы только что доказали, что данное здесь определение эквивалентно определению 4.
  No related posts.