Забележка 1. Изброените по-горе знаци, непринадлежащи на основната азбука, ще играят роля в следващите въпроси.

      Забележка 2. В конкретните примери, ако не е казано изрично нещо друго, ще приемаме, че основната азбука се състои от малките латински букви, десетте цифри и знака  _ , а допустими сигнатурни символи са точно онези думи над нея, които започват с латинска буква, различна от последните шест букви на латинската азбука (т.е. от буквите u, v, w, x, y, z). Когато малките латински букви, цифрите, знакът  _ , кръглите скоби и запетаята се употребяват като означения на самите себе си, а не в някаква друга роля, ще ги даваме в получерен машинописен шрифт:

      Под сигнатура ще разбираме наредена тройка (Φ,Π,ρ), където Φ и Π са непресичащи се множества от допустими сигнатурни символи, ρ е изображение на обединението на Φ и Π в множеството на неотрицателните цели числа и съществуват безбройно много допустими сигнатурни символи, непринадлежащи на никое от множествата Φ и Π. Ако означим въпросната наредена тройка със Σ, то думите от множествата Φ и Π ще наричаме съответно функционални символи и предикатни символи на Σ, а изображението ρ  -  указател на Σ за брой на аргументите. Когато ρ(ω)=n за даден функционален или предикатен символ ω на Σ, ще казваме, че символът ω е n-местен. Нулместните функционални символи на Σ ще наричаме още константи на Σ.

      Под структура ще разбираме наредена тройка (Σ,D,I), където Σ е сигнатура, D е непразно множество, а I е изображение, което за всяко неотрицателно цяло число n съпоставя на n-местните функционални и предикатни символи на Σ съответно n-местни функции и n-местни предикати в D. Ако означим споменатата наредена тройка с S, то нейните компоненти D и I ще наричаме съответно носител (или универсум) на S и интерпретиращо съответствие на S (разбира се сигнатурата Σ ще наричаме сигнатура на S). За всеки функционален или предикатен символ ω на Σ съответното I(ω) ще наричаме интерпретация на ω в S и ще означаваме с ω^S.

      Нека S е една структура със сигнатура Σ и носител D. Ще означаваме с F^S и с P^S съответно множеството на функциите ω^S, където ω е функционален символ на Σ, и множеството на предикатите ω^S, където ω е предикатен символ на Σ. За една функция в D ще казваме, че е изразима в S, ако тя е изразима чрез множеството F^S. За един предикат в D ще казваме, че е изразим в S (или че е определим от първи ред в S), ако той е изразим чрез F^S и P^S. Аналогично се определят за предикатите в D понятията атомарна изразимост и безкванторна изразимост в S.

      Пример. Да разгледаме сигнатурата Σ=({difference},{positive},ρ), където ρ(difference)=2, ρ(positive)=1, и структурата S=(Σ,D,I), където D е множеството на целите числа, I(difference) е двуместната функция в D, преобразуваща коя да е двойка (d₁,d₂) от цели числа в числото d₁−d₂, а I(positive) е едноместният предикат в D, на който множеството на истинност се състои от положителните цели числа. Твърденията за изразимост и неизразимост, съдържащи се в примера от текста "Атомарна изразимост на предикат чрез дадено множество от функции и предикати" и в примери 1 и 2 от текста "Изразимост на предикат чрез дадено множество от функции и предикати", могат да бъдат изказани като твърдения за изразимост и неизразимост в структурата S.

      Забележка 3. Освен понятията функционален символ, n-местен функционален символ, предикатен символ, n-местен предикатен символ, константа, указател за брой на аргументите и структура ред други понятия, които ще въведем по-нататък, също са свързани с избор на сигнатура и при използването им би трябвало да се предполага, че е дадена такава. За краткост във всички случаи, когато такова предположение не е изрично формулирано, наличието му ще се подразбира и ще се приема, че дадената сигнатура е означена със Σ. Често ще използваме и съкратени термини за съответните понятия, като ще се подразбира, че става дума за сигнатура, означена със Σ  -  например "функционален символ" вместо "функционален символ на Σ" и "структура" вместо "структура със сигнатура Σ".
 

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