Полная версия

Главная arrow Математика, химия, физика arrow Дискретная математика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

ФОРМАЛЬНЫЕ ТЕОРИИ И ИСЧИСЛЕНИЯ

Данный раздел посвящен представлению разделов дискретной математики с помощью подхода Д. Гильберта (1862—1943) и его школы. Этот подход основывается на построении математической теории как синтаксической теории, в которой все аксиомы записываются в виде формул в некотором алфавите и указываются правила вывода одних формул из других. При таком описании в математическую теорию как бы «встраивается» математическая логика.

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

В данном разделе мы представляем исчисление высказываний и исчисление предикатов.

В работах Гильберта математическая теория, непротиворечивость которой необходимо доказать, сама выступает как предмет другой математической теории, которая называется «метаматематикой» или теорией доказательств.

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

Основные свойства формальных теорий

Для определения формальной теории необходимо задать [1]

Т = <А, Р, В, /?>, где

  • • множество А символов, образующих алфавит;
  • • множество слов Ев алфавите А, которые называются формулами;
  • • подмножество В формул В е Р, которые называются аксиомами;
  • • множество /? отношений на множестве формул Я е Рп+ которые называются правилами вывода.

Алфавит может быть конечным или бесконечным.

Множество формул обычно задается индуктивно; как правило, оно бесконечно.

Множества Л и У7 по совокупности определяют язык формальной теории, или сигнатуру.

Множество аксиом может быть конечно или бесконечно. Бесконечное множество аксиом, как правило, задают в виде конечного множества схем и правил порождения из этих схем конкретных аксиом. Множество правил вывода обычно конечно.

Для каждой формальной теории важнейшими понятиями являются следующие свойства:

  • • выводимость;
  • • интерпретация;
  • • общезначимость;
  • • разрешимость;
  • • непротиворечивость;
  • • полнота;
  • • независимость.

Выводимость. Пусть 7^, Ръ ..., Рю С— формулы теории Г, т.е. Рь Ръ ..., Рю Се У7. Если существует такое правило вывода У?, что ь Р2,

У7,, С) е У?, то говорят, что формула С непосредственно выводима из формул Рь Р2п по правилу вывода К:

^1, Рь р„

где формулы Р2,называются посылками, а формула С — зя-кточением.

Вывод формулы С из формул ^ ^ •••, — это такая последова

тельность формул Рь Р2,..., У7,,, что Рп - (7, а любая формула Т7 — либо аксиома, либо исходная формула, либо непосредственный вывод из ранее полученных формул.

Если В теории Т существует ВЫВОД формулы (7 ИЗ формул У7!, /*2, ..., У7,,, то записывают

Т7!, ^2, ..., Рп Ь С, где Р{, Р2п гипотезы.

Теорема — формула, выводимая только из аксиом, без гипотез.

Интерпретацией формальной теории Тв область интерпретации М называется функция, которая каждой формуле Р теории Т однозначно сопоставляет некое содержательное высказывание относительно объектов множества М, И: Р —» М. Это высказывание может быть истинно или ложно или не иметь истинностного значения. Но если оно истинно, то говорят, что формула выполняется в данной интерпретации.

Например, рассматривая далее исчисление высказываний, мы будем приписывать значение 0 или 1 атомарным формулам (простым высказываниям), которые входят в сложные. Это и будет называться интерпретацией к.

Мы говорим, что формула Л исчисления истинна при некоторой интерпретации к тогда и только тогда, когда к(А) = 1, в противном случае говорят, что А ложна при интерпретации к.

Формальная теория Т называется разрешимой, если существует алгоритм, который для любой формулы теории определяет, является она теоремой или нет.

Под алгоритмом в интуитивном смысле мы понимаем такую последовательность действий, выполнение которых позволяет получить решение задачи регулярным путем за конечное число шагов. Свойствами алгоритма являются:

  • • дискретность шагов;
  • • детерминированность;
  • • регулярность;
  • • конечность;
  • • массовость.

Дискретность шагов означает, что весь процесс решения задачи делится на элементарные действия — шаги, последовательное выполнение которых приводит к результату.

Под свойством «детерминированность» понимают, что последовательность действий алгоритма определена однозначно. Регулярность подразумевает, что многократное выполнение одного и того же алгоритма на одних и тех же исходных данных дает один и тот же результат.

Конечность означает, что число шагов алгоритма, проделанных для получения результата, конечно.

Массовость означает, что алгоритм решает целый класс задач. Например, совокупность правил дорожного движения не является алгоритмом, так как они не являются однозначными («прямо и направо», «прямо и налево» и т.д.).

Формула общезначима (тавтология), если она истинна в любой интерпретации.

Формула называется противоречием, если она ложна в любой интерпретации.

Формальная теория семантически непротиворечива, если ни одна из ее теорем не является противоречием.

Формальная теория формально непротиворечива, если в ней не являются выводимыми одновременно формулы /’и Р.

Формальная теория называется полной, если каждому истинному высказыванию соответствует теорема теории.

Система аксиом формальной теории называется независимой, если ни одна из аксиом не выводится из оставшихся.

 
<<   СОДЕРЖАНИЕ   >>