Понятие языка с точно заданной структурой

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

Понятие исчисления

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

В исчислении мы имеем дело только с конструктивными объектами.

Конструктивными называются объекты, которые или непосредственно представлены (атомарные объекты – задаются в алфавите), или задаются эффективными способами порождения из ранее построенных объектов.

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

Уточнить понятие исчисления можно следующим образом:

1) зафиксировать исходные объекты (слова), над которыми разрешается производить указанные действия;

2) задать правила, которые позволяют из одних слов строить другие.

Задать исчисление К значит задать:

1) алфавит А этого исчисления – исходные символы, из которых строятся слова;

2) исходные слова (атомы А1,…,Аn), из которых путем преобразований порождаются новые слова;

3) правила R1,…,Rk, позволяющие из одних слов конструировать новые.

В качестве примера зададим исчисления К1 и К2, порождающие слова в фиксированном алфавите А.

К1: Пусть А={x, |}.

(A1)x

(R1) ά → ά| "x" принимается в качестве исходного слова, переменная άпробегает по словам исчисления К1, и сама не является словом в алфавите А.

Задав исчисление (систему допустимых действий над словами), мы тем самым задаем механизм, порождающий одно за другим слова некоторого типа. Класс слов, порождаемых исчислением, называют классом слов, доказуемых в этом исчислении (выводимых из его атомов). Слова x|,x||,x являются доказуемыми в К1, а слова xx или |x таковыми не будут.

К2: А={x, |, +, *}

А1 (атом, или исходное слово): ά Π (множество слов, порождаемое исчислением К1)

А2: | (имя)

R1 (правило): a → a| (a и b – метапеременные, пробегающие по объектам, построенным из атомов)

R2: a, b → a+b

R3: a, b → a*b

T (множество)={x, x|, x+1, |, ||,, x+|, |+|…} (объекты, порождаемые исчислением К2)

ά T ά (объект принадлежит классу Т, е.т.е. ά порождается исчислением К2)

Уточнив понятие исчисления, мы теперь можем уточнить понятие эффективно порождаемого, или эффективно перечислимого, множества. Некоторое множество слов в алфавите А рекурсивно перечислимо, если оно совпадает с множеством слов, выводимых в некотором исчислении (в этом же алфавите или в его расширении). Так, множество переменных П можно задать как множество слов,порождаемых К1: ά П ά.

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

Более сильное понятие – понятие рекурсивного (разрешимого) множества.

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

Если мы назовем Т классом термов, то можно сказать, что Т – это подмножество слов нашего алфавита, это те и только те слова, которые порождаются исчислением К2. Т будет эффективно перечислимым.

К1, К2 разрешимы (рекурсивны), если имеется жесткая процедура установления для любого объекта, принадлежит он к классу Р или нет.

(Класс теорем в логике предикатов неразрешим, но эффективно перечислим.)

Дата добавления: 2015-07-16