Классификация языков по Тарскому (на базе теории семантических категорий).

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

Исходным категориям – n и s – приписывается порядок 1.

Определение порядка. К выражению категории n+1 порядка (функторное выражение) приписываются функторы с любым числом аргументов, порядок аргументов - самое высокое n≤. Порядок одного аргумента должен быть равен n.

Пример.

s (порядок – 1)/nn (порядок – 1). 1+1=2. Порядок выражения s равен 2.

Языки классифицируются:

1) по числу семантических категорий переменных, встречающихся в этом языке;

2) по порядку.

К языкам первой группы относятся языки, в которых все переменные принадлежат к одной и той же семантической категории. (Язык логики предикатов.)

К языкам второй группы принадлежат языки, в которых число категорий, к которым принадлежат переменные, >1, но конечно. (Любая логика предикатов.)

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

К языкам четвертой группы принадлежат языки, в которых переменные принадлежат к категориям с бесконечным порядком. (Язык теории типов.)

1, 2, 3 – языки конечного порядка.

4 – языки бесконечного порядка.

14. Методы введения семантических понятий: определение понятий выполнимости и истинности для языков 2-ой группы, вопросы семантической корректности понятия выполнимости.

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

Добиться семантической однозначности для языков 1-го типа не представляет никакой трудности. С этой целью Тарский вводит понятие последовательности индивидов, поскольку все такого рода последовательности принадлежат к одной и той же семантической категории. Бесконечная последовательность определялась как бинарное отношение, областью которого является множество объектов рассмотрения, а противообластью – класс целых положительных чисел. Бинарные отношения (=последовательности) принадлежат к одной и той же семантической категории, е.т.е. их области принадлежат к одной и той же семантической категории и их противообласти принадлежат к одной и той же семантической категории.

(Любой бинарный предикат R(x,y) принадлежит к одной и той же семантической категории, если его аргументы принадлежат к одной и той же семантической категории.)

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

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

В качестве примера Тарский рассматривает логику бинарных отношений с кванторами по индивидным и предикатным переменным.

x, x|,x||… - индивидные переменные 1-го порядка.

R1, R2, R3… - предикаторные переменные 2-го порядка.

Xyz – элементарная пропозициональная формула, где вместо X – любая переменная 2-го порядка, вместо y и z – любые переменные 1-го порядка.

Vk – к-тая переменная 2-го порядка, vk – к-тая переменная 1-го порядка.

Pk,l,m – элементарная формула, такая, что: Pk,l,m=

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

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

Тарский выделяет два способа такой модификации:

1) метод многострочных последовательностей;

2) метод унификации (объединения) переменных.

1 – понятие выполнимости рассматривается как трехчленное отношение: ВЫП(f, F, ά), где f – последовательность индивидов, F – последовательность бинарных отношений, ά – формула рассматриваемого языка. Последовательности f и F совместно выполняют формулу Pk,l,m, если и только если между индивидами fl и fm имеет место отношение Fk.

2 – идея состоит в том, что если у нас порядок категорий конечен, то бесконечное число семантических категорий переменных может быть сведено к конечному числу для каждого данного порядка. В целом получаем конечное число семантических категорий и можно применять метод многострочных последовательностей.

Каждому индивиду а можно сопоставить бинарное отношение а* так, что различным индивидам сопоставятся различные бинарные отношения. Всегда можно найти эффективную функцию ψ, отображающую множество индивидов на подмножество множества пар индивидов. Так, каждому индивиду а можно сопоставить множество, состоящее из одной пары индивидов, первый и второй члены которой тождественны а. Таким путем каждому классу индивидов однозначным образом сопоставляется класс бинарных отношений указанного вида. Все константы сохраняют свое прежнее значение, а все переменные как 1-го, так и 2-го порядков пробегают по бинарным отношениям. С синтаксической точки зрения переменные по-прежнему принадлежат к двум различным категориям, а в семантическом плане, в силу придаваемой им интерпретации, - к одной и той же семантической категории – категории бинарных отношений. Соответственно, рассматриваем последовательности, принадлежащие к одной семантической категории – последовательности бинарных отношений. Каждой переменной вида vk приписывается член последовательности с индексом 2к-1, а переменной второго порядка Vk – член последовательности с индексом 2к. Последовательность бинарных отношений F выполняет элементарную формулу, если и только если (2l-1)-й и (2m-1)-й члены последовательности F представляют собой такие отношения а* и в*, что между соответствующими им индивидами имеет место отношение F2к. Таким образом, отношение F2к, приписанное предикатной переменной Vk, имеет место между индивидами, но переменным vl и vm приписаны отношения, сопоставленные одно-однозначным образом этим индивидам.

Пример. Такой бинарный предикат, что выполняет (2,2) или (5,5).

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