Съдържание 
 

СИГНАТУРИ И СТРУКТУРИ

      В математиката и в информатиката често се разглеждат системи, състоящи се от множество и дадени функции и релации в него (такива системи се наричат съответно математически структури и структури от данни). Разбира се, вместо релациите можем да разглеждаме предикати, на които множествата на истинност се определят чрез тези релации. Във връзка с такъв род разглеждания възникват важни логически въпроси, които са предмет на математическата логика. Нейният подход към тези въпроси изисква да бъдат налице някакви означения за функциите и предикатите. Какви да бъдат тези означения ще уточним чрез въвеждане на понятието сигнатура, а за множества с означени дадени функции и предикати в тях уточнението ще направим чрез понятието математико-логическа структура.

      Оттук нататък ще предполагаме, че е дадена една азбука, имаща поне две букви, която ще наричаме основна (или базисна) и която не съдържа никой от осемте знака

,   (   )   ¬   &   ∨   ∀   ∃
(първия, втория и третия от тях ще наричаме разбира се запетая, лява скоба и дясна скоба, а останалите пет  –  съответно знак за отрицание, знак за конюнкция, знак за дизюнкция, знак за общност и знак за съществуване, като общото наименование на тези пет знака ще бъде логически знаци). В конкретните примери (включително в примерите по-долу) ще приемаме, че основната азбука се състои от главните и малките латински букви, десетте цифри и знака  _ .  Ще предполагаме също, че е избрано едно безкрайно множество от думи над основната азбука, които ще наричаме допустими сигнатурни символи, като ще искаме то да бъде такова, че да съществуват и безбройно много думи над същата азбука със свойството никой техен непразен край да не е начало на допустим сигнатурен символ (понеже всяка дума е начало и край на себе си, очевидно непразните думи с това свойство не могат да бъдат допустими сигнатурни символи). Един начин да изберем такова множество е следният: избираме някаква непразна част на основната азбука, различна от нея, и обявяваме за допустими сигнатурни символи думите над тази азбука, започващи с буква от избраната нейна част (очевидно е, че има безбройно много такива думи, а безбройно много са и думите над основната азбука, които изобщо не съдържат букви от тази част на азбуката и следователно не могат да имат непразен край, който е начало на допустим сигнатурен символ).

      Пример 1 (свързан с езика за програмиране Пролог). Нека допустими сигнатурни символи да бъдат думите над основната азбука, започващи с малка латинска буква.

      Пример 2 (свързан с програмата за търсене на доказателства Prover 9). Нека допустими сигнатурни символи да бъдат думите над основната азбука, започващи с латинска буква, различна от последните шест малки латински букви (т.е. от буквите u, v, w, x, y, z).

      Забележка 1. В по-нататъшните конкретни примери, ако не е казано изрично нещо друго, ще приемаме, че множеството на допустимите сигнатурни символи е онова, което е посочено в пример 2.

      Забележка 2. Когато латинските букви, цифрите, знакът  _ , запетаята и скобите се употребяват като означения на самите себе си, а не в някаква друга роля, ще ги даваме в получерен машинописен шрифт:

ABCDEFGHIJKLMNOPQRSTUVWXYZ
abcdefghijklmnopqrstuvwxyz
0123456789_,()

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

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

      Разширение на една сигнатура (Φ,Π,ρ) ще наричаме всяка сигнатура (Φ′,Π′,ρ'), за която Φ и Π са подмножества съответно на Φ′ и Π′ (евентуално съвпадащи с тях), а ρ' е продължение на ρ.

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

      Обогатяване на една структура (Σ,D,I) ще наричаме такава структура (Σ′,D,I′) със същия носител, за която Σ′ е разширение на Σ и I′ е продължение на I.

      Пример 3. Да разгледаме сигнатурите
Σ=({difference},{positive},ρ),
Σ′=({difference, one},{positive, equal},ρ' ),
където

ρ(difference) = ρ'(difference) = 2,  ρ(positive) = ρ'(positive) = 1,  ρ'(one) = 0,  ρ'(equal) = 2.
Очевидно Σ′ е разширение на Σ. Да разгледаме още и структурите S = (Σ,D,I), S′ = (Σ′,D,I′), където D е множеството на целите числа, I(difference) съвпада с I′(difference) и е двуместната функция в D, преобразуваща кой да е елемент (d1,d2) на D2 в числото d1−d2,  I(positive) съвпада с I′(positive) и е едноместният предикат в D, на който множеството на истинност се състои от положителните числа от D,  I′(one) = 1,  I′(equal) = eqD . Ясно е, че S′ е обогатяване на S.

      Пример 4. Както пример 3, но с тази разлика, че D е множеството на реалните числа.

      Забележка 4. Обикновено ще предпочитаме сигнатури с по-къси функционални и предикатни символи отколкото в горните два примера. Бихме могли да модифицираме тези примери като вместо думите difference, one, positive и equal използваме да речем съответно еднобуквените думи d, o, p и e.

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