1) «Условие – действие», т.Е. Если построенные объекты удовлетворяют некоторым условиям, то для построений нового объекта нужно выполнить такое-то действие;

2)  «посылки – заключение», т.е. если уже построены объекты вида A₁, …, A_n, то объект вида А_n+1 также считается построенным.

Формальные системы называют также исчислениями или дедуктивными системами, правила формальной системы - правилами вывода, исходные объекты - аксиомами; объекты, которые можно построить из исходных и уже построенных объектов путем последовательного применения правил - выводимыми или допустимыми, а саму последовательность примененных правил - выводом. Правила при этом имеют вид «посылки – заключение».

Примером формальной системы может служить множество арифметических формул с переменными а, b, с и целочисленными константами (или, если выражаться более точно, формальная система, задающая множество таких формул). Алфавит системы состоит из символов переменных, знаков, арифметических переменных и скобок: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, с, +, -, , :, (, ). Исходные объекты: а, b, с, 0, 1, 2, ..., 9 (переменные и цифры являются формулами). При этом цифры называются числами.

19) Формальная арифметика

        формулировка арифметики в виде формальной (аксиоматической) системы (см. Аксиоматический метод). Язык Ф. а. содержит константу 0, числовые переменные, символ равенства, функциональные символы +, •, ' (прибавление 1) и логические связки (см. Логические операции). Постулатами Ф. а. являются аксиомы (См. Аксиома) и правила вывода (См. Правило вывода) исчисления предикатов (классического или интуиционистского в зависимости от того, какая Ф. а. рассматривается), определяющие равенства для арифметических операций:

         а + 0 = а, а + b’ = (а + b),

         а •0 = 0, а •b’ = (а•b) + а,

        аксиомы Пеано:

         ⌉(а’ = 0), a’= b’ → а = b,

         (a = b & а = с) → b = с, а = b →a' = b'

        и схема аксиом индукции:

         А (0) & ∀x (А (х) → А (x')) → ∀xa (x).

         Средства Ф. а. достаточны для вывода теорем элементарной теории чисел. В настоящее время, по-видимому, неизвестно ни одной содержательной теоретико-числовой теоремы, доказанной без привлечения средств анализа, которая не была бы выводима в Ф. а. В Ф. а. изобразимы Рекурсивные функции и доказуемы их определяющие равенства. Это позволяет, в частности, формулировать суждения о конечных множествах. Более того, Ф. а. эквивалентна аксиоматической теории множеств (См. Аксиоматическая теория множеств) Цермело – Френкеля без аксиомы бесконечности: в каждой из этих систем может быть построена модель другой.

19) Арифметика есть формально-описательная система. Тогда:"Невозможно создать целостную формально-описательную систему, не прибегая к понятиям, заимствуемым как аксиомы из мира за пределами этой системы." Т.е. нет самодостаточной "теории всего".

Первая теорема о неполноте

Первая теорема Гёделя о неполноте, по всей видимости, является наиболее знаменательным результатом в математической логике. Она звучит следующим образом:

Для произвольной непротиворечивой формальной и вычислимой теории, в которой можно доказать базовые арифметические высказывания, может быть построено истинноеарифметическое высказывание, истинность которого не может быть доказана в рамках теории^[1]. Другими словами, любая вполне полезная теория, достаточная для представления арифметики, не может быть одновременно непротиворечивой и полной.

Здесь слово «теория» обозначает «бесконечное множество» высказываний, некоторые из которых полагаются истинными без доказательств (такие высказывания называются аксиомами), а другие (теоремы) могут быть выведены из аксиом, а потому полагаются (доказываются) истинными. Словосочетание «доказуемый в теории» обозначает «выводимый из аксиом и примитивов теории (константных символов алфавита) при помощи стандартной логики (первого порядка)». Теория является непротиворечивой (согласованной), если в ней невозможно доказатьпротиворечивое высказывание. Словосочетание «может быть построено» обозначает, что существует некоторая механическая процедура (алгоритм), которая может построить высказывание на основе аксиом, примитивов и логики первого порядка. «Элементарная арифметика» заключается в наличии операций сложения и умножения над натуральными числами. Результирующее истинное, но недоказуемое высказывание часто обозначается для заданной теории как «последовательность Гёделя», однако существует бесконечно количество других высказываний в теории, которые имеют такое же свойство: недоказуемая в рамках теории истинность.

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

Первая теорема о неполноте была озаглавлена как «Теорема VI» в статье Гёделя от 1931 года On Formally Undecidable Propositions in Principia Mathematica and Related Systems I. В оригинальной записи Гёделя она звучала как:

«Общий вывод о существовании неразрешимых пропозиций заключается в следующем:

Теорема VI.

Для каждого ω-согласованного рекурсивного класса k ФОРМУЛ существуют рекурсивные ЗНАКИ r такие, что ни (vGenr), ни ¬(vGenr) не принадлежат Flg(k) (где v есть СВОБОДНАЯ ПЕРЕМЕННАЯ r)^[2]».

Обозначение Flg происходит от нем. Folgerungsmenge – множество последовательностей, Gen происходит от нем. Generalisation – обобщение.

Грубо говоря, высказывание Гёделя G утверждает: «истинность G не может быть доказана». Если бы G можно было доказать в рамках теории, то в таком случае теория содержала бы теорему, которая противоречит сама себе, а потому теория была бы противоречива. Но если G недоказуемо, то оно истинно, а потому теория неполна (высказывание G невыводимо в ней).

Это пояснение на обычном естественном языке, а потому не совсем математически строго. Для предоставления строгого доказательства, Гёдель пронумеровал высказывания при помощи натуральных чисел. В этом случае теория, описывающая числа, также принадлежит множеству высказываний. Вопросы о доказуемости высказываний представимы в данном случае в виде вопросов о свойствах натуральных чисел, которые должны быть вычислимы, если теория полна. В этих терминах высказывание Гёделя гласит, что не существует числа с некоторым определённым свойством. Число с этим свойством будет являться доказательством противоречивости теории. Если такое число существует, теория противоречива вопреки первоначальному предположению. Так что предполагая, что теория непротиворечива (как предполагается в посылке теоремы), получается, что такого числа не существует, и высказывание Гёделя истинно, но в рамках теории этого доказать невозможно (следовательно, теория неполна). Важное концептуальное замечание состоит в том, что необходимо предположить, что теория непротиворечива, для того чтобы объявить высказывание Гёделя истинным.

Вторая теорема Гёделя о неполноте

Вторая теорема Гёделя о неполноте звучит следующим образом:

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

Иными словами, непротиворечивость достаточно богатой теории не может быть доказана средствами этой теории. Однако вполне может оказаться, что непротиворечивость одной конкретной теории может быть установлена средствами другой, более мощной формальной теории. Но тогда встаёт вопрос о непротиворечивости этой второй теории, и т.д.

Использовать эту теорему для доказательства того, что разумная деятельность не сводится к вычислениям, пытались многие. Например, еще в 1961 году известный логик Джон Лукас (John Lucas) выступал с подобной программой. Его рассуждения оказались довольно уязвимыми – однако он и задачу ставил более широко. Роджер Пенроуз использует несколько другой подход, который излагается в книге полностью, «с нуля».

20) Формальная грамматика или просто грамматика в теории формальных языков — способ описания формального языка, то есть выделения некоторого подмножества из множества всех слов некоторого конечного алфавитa. Различают порождающие и распознающие (или аналитические) грамматики — первые задают правила, с помощью которых можно построить любое слово языка, а вторые позволяют по данному слову определить, входит оно в язык или нет.

По иерархии Хомского, грамматики делятся на 4 типа, каждый последующий является более ограниченным подмножеством предыдущего (но и легче поддающимся анализу):

• тип 0. неограниченные грамматики — возможны любые правила

• тип 1. контекстно-зависимая грамматика — левая часть может содержать один нетерминал, окруженный «контекстом» (последовательности символов, в том же виде присутствующие в правой части); сам нетерминал заменяется непустой последовательностью символов в правой части.

• тип 2. контекстно-свободные грамматики — левая часть состоит из одного нетерминала.

• тип 3. регулярные грамматики — более простые, эквивалентны конечным автоматам.

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

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

Формальные языки классифицируются в соответствии с типами грамматик, которыми они задаются. Однако, один и тот же язык может быть задан разными грамматиками, относящимися к разным типам. В таком случае, считается, что язык относится к наиболее простому из них. Так, язык, описанный грамматикой с фразовой структурой, контекстно-зависимой и контекстно-свободной грамматиками, будет контекстно-свободным.

Так же, как и для грамматик, сложность языка определяется его типом. Наиболее сложные — языки с фразовой структурой (сюда можно отнести естественные языки), далее — КЗ-языки, КС-языки и самые простые — регулярные языки.

21) Контекстно-свободная грамматика (КС-грамматика, бесконтекстная грамматика) — частный случай формальной грамматики (тип 2 по иерархии Хомского), у которой левые части всех продукций являются одиночными нетерминалами. Смысл термина «контекстно-свободная» заключается в том, что возможность применить продукцию к нетерминалу, в отличие от общего случая грамматики Хомского, не зависит от контекста этого нетерминала.

Язык, который может быть задан КС-грамматикой, называется контекстно-свободным языком или КС-языком.

Дерево вывода.

Выводам контекстно-свободной грамматики соответствуют деревья разбора (derivation tree, parse tree) – это некоторые упорядоченные деревья, вершины которых помечены символами алфавита или нетерминального, или терминального множества, корень дерева – начальный символ. Каждому символу, на который заменяется начальный символ на первом шаге вывода, ставится в соответствие вершина дерева, и к ней приводится дуга из корня. Полученные таким образом потомки корня упорядочены.

Например:                                                                   <Пр>                                <П>                  <с>                                  |                        |                               <ис>                <ГФ>                                  |                        |                                 кот                  лежит

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