Съдържание 
 

АТОМАРНА ИЗРАЗИМОСТ НА ПРЕДИКАТ ЧРЕЗ ДАДЕНО МНОЖЕСТВО ОТ ФУНКЦИИ И ПРЕДИКАТИ

      Аналогично на суперпозицията на m-местна функция с m-орка от n-местни функции се дефинира и суперпозиция на m-местен предикат с такава m-орка. Нека D е дадено множество. Ако p е m-местен предикат в D, а g1, …, gm са n-местни функции в D, където m и n са положителни цели числа, ще означаваме с p(g1,…,gm) и ще наричаме суперпозиция на p с m-орката (g1,…,gm) онзи n-местен предикат q в D, който се дефинира чрез равенството
q(d1,…,dn) = p(g1(d1,…,dn),…,gm(d1,…,dn)).
Означението p(g1,…,gm) има смисъл и в случая, когато m е положително цяло число, p е m-местен предикат в D, а g1, …, gm са 0-местни функции в D  -  тогава p(g1,…,gm) е стойността на предиката p за m-ката (g1,…,gm) от елементи на D. И в този случай ще наричаме p(g1,…,gm) суперпозиция на p с m-орката (g1,…,gm). Когато p е 0-местен предикат в D, а n е положително цяло число, ще означаваме с p(n) и ще наричаме n-местен вариант на p онзи n-местен предикат q в D, който се дефинира чрез равенството
q(d1,…,dn) = p.
Под 0-местен вариант на един 0-местен предикат p в D ще разбираме самия предикат p, който ще означаваме още и с p(0).

      Забележка. Твърденията от забележки 1 и 2 от текста "Изразимост на функция чрез дадено множество от функции" остават в сила и верността им се вижда по аналогичен начин, ако в тях m-местната функция f бъде заменена с m-местен предикат p (разбира се тогава равенствата в тези твърдения ще бъдат между предикати вместо между функции).

      Нека F и P са съответно дадено множество от функции в D и дадено множество от предикати в D. За всяко неотрицателно цяло число n ще наричаме атомарно изразими чрез F и P  а) всички n-местни предикати в D от вида p(g1,…,gm), където m е положително цяло число, p е m-местен предикат от P и g1, …, gm са n-местни функции в D, изразими чрез F, и  б) n-местните варианти в D на 0-местните предикати от P.

      Пример. Нека D е множеството на целите числа, F има като единствен свой елемент двуместната функция, преобразуваща коя да е двойка (d1,d2) от цели числа в числото d1−d2, а P  -  едноместния предикат в D, на който множеството на истинност се състои от положителните цели числа. Тогава са атомарно изразими чрез F и P например едноместният предикат в D с празно множество на истинност, едноместният предикат в D, на който множеството на истинност се състои от отрицателните цели числа, и двуместният предикат в D с множество на истинност, състоящо се от двойките от D2 с пръв член, по-голям от втория. Не е атомарно изразим чрез F и P обаче никой едноместен предикат в D, на който числото 0 принадлежи на множеството на истинност (това е така, защото, както лесно се вижда, всяка едноместна функция в D, изразима чрез F, има стойност 0 за числото 0).

      Дефиницията, която дадохме, осигурява, че всички предикати от множеството P са изразими чрез F и P (защото при n>0 всеки n-местен предикат в D е равен на своята суперпозиция с n-орката от n-те n-местни проекционни функции в D, а всеки 0-местен предикат в D съвпада с 0-местния си вариант). От забележката, която направихме по-горе, следва, че атомарната изразимост на предикати чрез F и P се запазва при суперпозиция на предикатите с функции, изразими чрез F.
 

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