Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

для каких-то целей. В зависимости от того, для каких целей должно быть достаточно теорем, будем в дальнейшем вводить различные понятия полноты. Рассмотренные свойства - непротиворечивость и полнота, являются важнейшими свойствами дедуктивной теории. Кроме этих свойств, имеется и ряд других свойств. Рассмотрим еш,е два свойства дедуктивной теории. Независимость аксиом теории. Отдельная аксиома дедуктивной теории называется независимой, если эту аксиому нельзя вывести в этой теории из остальных аксиом. Система аксиом называется независимой, если каждую из них нельзя вывести из остальных. Разрешимость теории. Дедуктивная теория называется разрешимой, если в этой теории понятие теоремы эффективно, т.е. суш,ествует правило (метод), позволяюш,ее для произвольной формулы за конечное число действий выяснить, является она теоремой или нет. Пусть заданы две дедуктивные теорииBj и В2, такие что: 1) алфавит теории Bj содержится в алфавите теории В2 или эти алфавиты совпадают; 2) каждая формула изBj является формулой из В2; 3) каждая теорема изBj является теоремой в В2. При выполнении этих условий говорят, что теория В2 является расширением теории Bj. В следующих параграфах данной главы изучим более подробно каждую из введенных дедуктивных теорий, их свойства, а также примеры таких теорий. Очень трудно е каждой науке отобрать и расположить в надлежащем порядке элементы, из которых все дальнейшее следует. И во всем этом система элементов Евклида превосходит все остальное, ... . Прокл (около 410-485 гг.) А открытие неевклидовой геометрии было величайшей революцией в области человеческой мысли, какую только знает история науки. Inde irae^. В.Ф. Коган § 4. Пример полуформальной аксиоматической теории - геометрия Согласно § 2 полуформальная аксиоматическая теория считается заданной, если задан язык этой теории и из множества предложений (формул) этого языка выделено подмножество - множество аксиом. Таким образом, полуформальная аксиоматическая теория (теория В ) считается заданной, если: 1) заданы алфавит^ (алфавит теории В) и правила образования выражений (слов) теории В; «Отсюда гнев» (Ювенал) 103