Изразимост на предикат чрез дадено множество от функции и предикати

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

Нека D е дадено множество, а n е дадено неотрицателно цяло число. В множеството на n-местните предикати в D ще дефинираме едноместна операция отрицание и двуместни операции конюнкция и дизюнкция. Нека най-напред разгледаме случая, когато n>0. Тогава, ако p е произволен n-местен предикат в D, ще наричаме отрицание на p n-предикат q, дефиниран с помощта на равенството q(d₁,…,d_n) = 1 − p(d₁,…,d_n), а ако p₁ и p₂ са произволни n-местни предикати в D, ще наричаме конюнкция на p₁ и p₂ и дизюнкция на p₁ и p₂ съответно n-местните предикати q и r в D, дефинирани посредством равенствата q(d₁,…,d_n) = min{ p₁(d₁, …,d_n), p₂(d₁,…,d_n) } ,
r(d₁,…,d_n) = max{ p₁(d₁, …,d_n), p₂(d₁,…,d_n) }. От тази дефиниция следва, че множеството на истинност на отрицанието на p е допълнението до Dⁿ на множеството на истинност на p, а множествата на истинност на конюнкцията и на дизюнкцията на p₁ и p₂ са съответно сечението и обединението на множествата на истинност на p₁ и p₂. Случая, когато n=0, обхващаме чрез уславянията под отрицание на едно число p от множеството {0,1} да разбираме числото 1−p, а под конюнкция и дизюнкция на две числа от това множество да разбираме съответно по-малкото и по-голямото от тези две числа. Ясно е, че отрицанието на едно число от множеството {0,1} е 1 точно тогава, когато самото число не е 1, конюнкцията на две числа от това множество е 1 точно тогава, когато всяко от двете е 1, а дизюнкцията им е 1 точно тогава, когато някое от тях е 1.

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

Пример 1. Нека, както в примера от текста "Атомарна изразимост на предикат чрез дадено множество от функции и предикати", D е множеството на целите числа, F има като единствен свой елемент двуместната функция, преобразуваща коя да е двойка (d₁,d₂) от цели числа в числото d₁−d₂, а P - едноместния предикат в D, на който множеството на истинност се състои от положителните цели числа. Тогава едноместният предикат в D с множество на истинността {0} не е атомарно изразим чрез F и P. Той обаче е безкванторно изразим чрез F и P, защото е отрицание на дизюнкцията на едноместния предикат в D с множество на истинност, състоящо се от положителните цели числа, и онзи с множество на истинност, състоящо се от отрицателните цели числа. Още по-просто се вижда, че едноместният предикат в D с множество на истинност D е безкванторно изразим чрез F и P, макар че не е атомарно изразим чрез F и P - той е отрицание на едноместния предикат в D с празно множество на истинност.

Като се използва, че атомарната изразимост чрез F и P се запазва при суперпозиция на предикатите с функции, изразими чрез F, лесно се вижда, че и безкванторната изразимост чрез F и P има това свойство.

Някои важни операции върху предикати не се свеждат до разгледаните дотук операции отрицание, конюнкция и дизюнкция. Две такива операции са универсалната квантификация и екзистенциалната квантификация. За всяко положително цяло число n тези операции могат да бъдат приложени към кой да е n-местен предикат в D и като резултат от прилагането им към него се получават два n−1-местни предиката в D. При n>1 въпросните операции се дефиннрат така: ако p е произволен n-местен предикат в D, то резултат от универсална квантификация на p и резултат от екзистенциална квантификация на p наричаме съответно n−1-местните предикати q и r в D, дефинирани посредством равенствата

q(d₁,…,d_n−1) = min{ p(d₁, …,d_n−1,d) | d∈D } ,
r(d₁,…,d_n−1) = max{ p(d₁, …,d_n−1,d) | d∈D } . Множествата на истинност на тези два предиката могат да бъдат охарактеризирани така: една n−1-орка (d₁,…,d_n−1) от елементи на D принадлежи на множеството на истинност на q точно тогава, когато за всеки елемент d на D n-орката (d₁, …,d_n−1,d) принадлежи на множеството на истинност на p, а n−1-орката (d₁,…,d_n−1) принадлежи на множеството на истинност на r точно тогава, когато за някой елемент d на D n-орката (d₁, …,d_n−1,d) принадлежи на множеството на истинност на p. Дадената дефиниция разпространяваме за случая, когато n=1, по следния начин: ако p е едноместен предикат в D, то резултат от универсална квантификация на p и резултат от екзистенциална квантификация на p наричаме съответно числата q и r от множеството {0,1}, дефинирани посредством равенствата q = min{ p(d) | d∈D } ,
r = max{ p(d) | d∈D } . Ясно е, че q е 1 точно тогава, когато всички елементи на D принадлежат на множеството на истинност на p, а r е 1 точно тогава, когато някой елемент на D принадлежи на множеството на истинност на p.

Разполагайки и с операциите универсална и екзистенциална квантификация, ние ще дадем индуктивна дефиниция на понятието за предикат в D, който е изразим чрез F и P (предикатите в D, изразими чрез F и P, се наричат още определими от първи ред чрез F и P). Дефиницията се състои от следните точки:
1. Всеки предикат в D, атомарно изразим чрез F и P, е изразим чрез F и P.
2. Отрицанието на всеки предикат в D, изразим чрез F и P, е изразимо чрез F и P.
3. За всяко цяло неотрицателно число n, ако два n-местни предиката в D са изразими чрез F и P, то конюнкцията им и дизюнкцията им също са изразими чрез F и P.
4. За всяко цяло положително число n, ако даден n-местен предикат в D е изразим чрез F и P, то резултатът от универсалната му квантификация и резултатът от екзистенциалната му квантификация също са изразими чрез F и P.

От тази дефиниция следва, че всеки предикат в D, безкванторно изразим чрез F и P, е изразим чрез F и P. Обратното в общия слуяай не е вярно.

Пример 2. В условията на пример 1 се вижда лесно, че само осем едноместни предиката в D са безкванторно изразими чрез F и P, а именно предикатите, на които множествата на истинност са празното множество, множеството на положителните цели числа, множеството на отрицателните цели числа и множеството на целите числа, различни от 0, както и отрицанията на тези четири предиката (за целта може първо да се покаже, че всяка изразима чрез F едноместна функция f в D има вида f(d)=кd, където к е фиксирано цяло число). Оттук следва, че едноместният предикат в D с множество на истинност, състоящо се от целите числа, по-големи от 1, не е безкванторно изразим чрез F и P. От друга страна обаче същият предикат е изразим чрез F и P. И наистина, той съвпада с резултата от екзистенциална квантификация на двуместния предикат в D, чието множество на истинност е съставено от двойките (d₁,d₂) от цели числа, удовлетворяващи неравенствата d₁>d₂>0, а този двуместен предикат е конюнкция на два двуместни предиката, атомарно изразими чрез F и P.

Индуктивно се доказва, че и изразимостта на предикати чрез F и P се запазва при суперпозиция на предикатите с функции, изразими чрез F.

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