Лекция 13

Формальные теории , формальные системы и формальные языки

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

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

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

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

Это связано с обыкновенными и необыкновенными множествами.

Обыкновенные не содержат самих себя в качестве элементов.

Необыкновенные содержат.

Примеры обыкновенных множеств :

• множество всех натуральных чисел – это не натуральное число.

• Множество всех людей земли - это не человек

Пример необыкновенного множества:

• Множество всех мыслимых множеств – само является множеством.

Но есть такие множества, которые невозможно отнести ни к тем, ни к другим.

• Например, множество всех обыкновенных множеств.

Каким будет это множество? Обыкновенным или необыкновенным?

Предположим, что оно необыкновенное. Тогда по определению оно должно встречаться среди своих элементов. Но этого быть не может, так как это противоречит условию, в соответствии с которым элементами множества являются обыкновенные множества. Пришли к противоречию. Тогда предположим, что наше множество – обыкновенное. Но тогда оно не встречалось бы среди своих элементов, что опять приводит к противоречию, иначе оно должно было бы быть необыкновенным. И то, и другое приводит к противоречию. Это противоречие называется парадоксом Рассела. Есть и другие парадоксы. Таким образом оказалось, что теория множеств, лежащая в основе современной математики, внутренне противоречива.

Замечание: Алонзо Черч пытался разрешить парадокс Рассела о множестве всех множеств, не включающих в качестве подмножества самих себя с помощью формализма лямбда-исчисления и потерпел на этом поприще поражение, но зато разработанный им формализм лямбда-исчисления Черча помог в дальнейшем перейти к парадигме функционального программирования, то есть рассматривать лямбда-исчисление в качестве теории вычислений.

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

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

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

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

Общая схема построения формальной системы:

• Язык системы :

алфавит,

синтаксис.

• Аксиомы системы – конечное или перечислимое множество формул.

• Правила вывода системы.

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

Компьютер работает с текстами, выполняя вычислительный процесс. Тексты являются последовательностями символов некоторого алфавита.

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

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

Подходящий формализм для работы с текстами – это понятия алфавита, слова и языка.

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

МНОЖЕСТВА.

Множества состоят из элементов.

Если мы пишем x S , это означает, что объект x является элементом множества S.

Если мы пишем x S , это означает, что объект x не является элементом множества S.

Можно задать множество перечислением его элементов через запятые в фигурных скобках. Например, S={1,2,3,4,5} содержит элементы 1,2,3,4,5 и только их. Число 5 является элементом данного множества, а число 6 нет, то есть

5 S , а 6 S

• Множество не может содержать двух одинаковых элементов.

• Порядок элементов не фиксирован.

• Два множества А и В равны, если они состоят из одних и тех же элементов.

В этом случае пишут А=В.

Например, {1,2,3}={3,1,2}

Имеются специальные обозначения:

• обозначает пустое множество, не содержащее ни одного элемента.

• Z – обозначает множество целых чисел (Z={….-2,-1,0,1,2,….}

• R - обозначает множество вещественных (действительных) чисел

• N - обозначает множество натуральных чисел (N=1,2,…..) или N={0,1,2,…}