ОПЕРАЦИИ, ПРЕДИКАТИ, СИГНАТУРИ, СТРУКТУРИ

    Под сигнатура ще разбираме наредена четворка (A,W,P,r), за която са изпълнени следните условия:

A е азбука, несъдържаща знаците "(", ")", "[", "]", "<", ">", ",", "Ш", "&" и "Ъ";¹

W и P (множество на функционалните символи и множество на предикатните символи) са непресичащи се множества от думи над A;

r (функция за брой на аргументите) е функция от WИP към множеството на неотрицателните цели числа;

множеството P не е празно и съществуват безбройно много думи над A, непринадлежащи на WИP.

    Ако S=(A,W,P,r) е сигнатура или S=(A,W,P,r,X) е лексика, то думите от W ще наричаме функционални символи на S, а думите от P - предикатни символи на S, като за всяко цяло неотрицателно число n думите от множествата W_n={wОW|r(w)=n} и P_n={pОP|r(p)=n} ще наричаме съответно n-местни функционални символи на S и n-местни предикатни символи на S; стойността на функцията r за произволен функционален или предикатен символ на S ще наричаме брой на аргументите му. Нулместните функционални символи се наричат още константи на S, а нулместните предикатни символи - съждителни символи на S. Когато S=(A,W,P,r,X) е лексика, думите от X ще наричаме променливи на S (тези думи се наричат още и индивидни променливи на S).

    Пример (имащ връзка с езика за програмиране Пролог). Нека азбуката A се състои от главните и малките латински букви, знака "_" и десетте цифри, W и P са непресичащи се множества от думи над A, всяка от които започва с малка латинска буква, r е функция от WИP към множеството на неотрицателните цели числа, а X се състои от онези думи над A, които започват с главна латинска буква или със знака "_". Тогава наредената петорка (A,W,P,r,X) е лексика в смисъла на горната дефиниция.

    Съответна сигнатура на една лексика (A,W,P,r,X) ще наричаме четворката (A,W,P,r). От изискването за всяка сигнатура (A,W,P,r) да съществуват безбройно много думи над азбуката A, които не принадлежат на обединението WИP, е ясно, че всяка сигнатура е съответна на някоя лексика. Същото изискване осигурява възможност от всяка сигнатура да получим друга чрез добавяне на произволен краен брой и даже на изброимо много нови функционални или предикатни символи без да има нужда азбуката да се разширява с нови букви (аналогичното изискване в дефиницията за лексика осигурява подобна възможност за разширяване на лексики, включително и чрез добавяне на нови променливи).

    Нека S=(A,W,P,r) е дадена сигнатура. Структура за S (или S-структура) ще наричаме наредена двойка (C,I), където C е непразно множество, а I е изображение с дефиниционна област WИP, такова, че за всяко неотрицателно цяло число n образите I(w) на елементите w на W_n са n-местни операции в C, а образите I(p) на елементите p на P_n са n-местни предикати в C. Множеството C се нарича носител на структурата, а функцията I - нейно интерпретиращо съответствие. Ако S е лексика, то всяка структура за съответната й сигнатура ще наричаме структура за S.

    Нека е дадена една лексика S=(A,W,P,r,X) и нека S=(C,I) е структура за S. Ще наричаме оценка в S на променливите на S (накратко оценка в S) всяко изображение на множеството X в множеството C (поне едно такова изображение съществува, понеже C не е празно). Ако v е оценка в S, а x е променлива на S, то елемента v(x) на C ще наричаме стойност на x при оценката v. Ако S е лексика, то ще наричаме конфигурация (допълнена структура) за S (или S-конфигурация) всяка наредена двойка (S,v), където S е структура за S, а v е оценка в S. Под носител и интерпретиращо съответствие на конфигурацията (S,v) ще разбираме съответно носителя и интерпретиращото съответствие на структурата S.

    Забележка. Ако S=(A,W,P,r,X) е лексика, то от нея можем да получим една сигнатура Sў=(A,Wў,P,rў), като положим Wў=WИX и означим с rў онова продължение на функцията r върху WўИP, което приема стойност 0 за всички елементи на X (за Sў ще казваме, че е получена от S чрез превръщане на променливите в константи). В случай че ((C,I),v) е конфигурация за S, можем да получим една структура (C,Iў) за Sў, като означим с Iў продължението на I върху WўИP, определено при xОX с помощта на равенството Iў(x)=v(x).

    Оттук нататък постоянно ще предполагаме, че е дадена някоя лексика S=(A,W,P,r,X) и за краткост няма изрично да я споменаваме, когато използваме въведените преди малко термини за понятия, зависещи от нея - например ще говорим просто за функционални и предикатни символи, за променливи, за структури и конфигурации, а ще имаме пред вид съответно функционални и предикатни символи на S, променливи на S, структури и конфигурации за S. Няма да включваме споменаване на S и в редица други термини, които ще дефинираме по-нататък, въпреки че назоваваните чрез тях понятия обикновено ще зависят от избора на лексиката S. Освен това свободно ще използваме въведените означения W_n и P_n за множеството на n-местните функционални символи и множеството на n-местните предикатни символи на тази лексика.

  Последно изменение: 9.01.2001 г.

Next

Contents