Previous  Next  Contents
 

 

ЛИТЕРАЛИ И ДИЗЮНКТИ

    Ще искаме да разгледаме накратко един малко по-различен подход към логическото програмиране, който често се използва при описанието на неговите задачи и методи, макар че е за предпочитане главно в по-обща ситуация от тази, с която обикновено се занимава логическото програмиране. За да изложим нещата в съответствие с този подход, ще имаме нужда и от отрицания на атомарни формули. Нека с not е означена някоя такава дума над базисната азбука, че за никоя атомарна формула А думата not(А) да не е атомарна формула (думата not(А) би могла да се окаже атомарна формула например в случай че атомарната форма A е същевременно и терм, а думата not е едноместен предикатен символ). Най-просто и естествено можем да удовлетворим поставеното изискване, като в качеството на not изберем някой елемент на множеството L на логическите символи, споменато във въпроса "Сигнатури, структури, термове, атомарни формули" (например в условията на пример 1 от посочения въпрос е естествено с not да означим трибуквената дума not). Една друга, обаче твърде изкуствена възможност би била с not да означим някоя променлива. След като сме фиксирали по един или друг начин избора на думата not, ние за всяка атомарна формула A съответната дума not(А) ще наричаме отрицание на A и ще я означаваме още и с ША. Очевидно е, че когато за две атомарни формули A1 и A2 имаме равенството ШA1=ШA2, можем да сме сигурни, че имаме и равенството A1=A2.

    Атомарните формули и техните отрицания ще наричаме с общото име литерали, като атомарните формули ще наричаме още положителни литерали, а техните отрицания - отрицателни литерали. Семантиката на отрицанията на атомарните формули се определя така: ако A е атомарна формула, S е структура и v е оценка в S на променливите, то приемаме, че литералът ША е верен в S при оценката v точно тогава, когато атомарната формула A не е вярна в S при оценката v. За да изразим, че литералът ША е верен в S при оценката v, ще пишем S,vШA, а противното ще означаваме с S,vШA. Ред други понятия, които преди дефинирахме за атомарни формули, без затруднение се пренасят и за отрицания на атомарни формули. Например под множество на променливите на един отрицателен литерал ША разбираме множеството на променливите на атомарната формула A. Също така, ако s е някоя субституция, то за всяка атомарна формула А дефинираме резултат от прилагането на s към ША чрез полагането s(ША)=Шs(А) (очевидно s(ША) е отрицателен литерал). Необходимото и достатъчно условие за вярност на резултата от прилагането на субституция към атомарна формула се обобщава за произволни литерали:

    Необходимо и достатъчно условие за вярност на резултата от прилагане на субституция към литерал. Нека са дадени една субституция s,  една структура S и една оценка v в S. Нека sS(v)=vў. Тогава за всеки литерал L условието S,vs(L) е равносилно с условието S,vўL.

    Доказателство. Нужно е да разгледаме само случая, когато L е отрицателен литерал, т.е. L=ША за някоя атомарна формула A. Тогава имаме

S,vs(L) ЫS,vШs(А) ЫS,vs(А) ЫS,vўАЫS,vўL.  ї

    Всяко крайно множество от литерали (вкл. празното) ще наричаме дизюнкт (празното множество ще наричаме още празен дизюнкт). Ако D е дизюнкт, S е структура и v е оценка в S на променливите, то приемаме, че дизюнктът D е верен в S при оценката v точно тогава, когато някой литерал, принадлежащ на D, е верен в S при оценката v. За да изразим, че дизюнктът D е верен в S при оценката v, ще пишем S,vD, а противното ще означаваме с S,vD (то разбира се означава, че никой литерал, принадлежащ на D, не е верен в S при оценката v).  От тази дефиниция следва  непосредствено, че празният дизюнкт не е верен в никоя структура при никоя оценка, а дизюнкт, сред елементите на който се намират някоя атомарна формула и нейното отрицание, е верен във всяка структура при всяка оценка. За всеки друг дизюнкт може да се окаже изпълнено едното или другото от условията S,vD и S,vD в зависимост от избора на структурата S и на оценката v (това, че може да се удовлетвори второто от тези условия, следва лесно от втората основна лема за разширените ербранови структури).

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

    Множество на променливите на един дизюнкт ще наричаме обединението на множествата на променливите на литералите, от които е съставен. За един дизюнкт ще казваме, че е тъждествено верен в дадена структура S, ако той е верен в S при всяка оценка в S на променливите (т.е. ако при всяка такава оценка някой от литералите, принадлежащи на дизюнкта, е верен в S; разбира се допустимо е при една оценка да е верен един от литералите, а при друга - друг).

    Пример 1. Нека S е структура, чийто носител е множеството на целите числа. Нека succ е едноместен функционален символ, който се интерпретира в S чрез операцията прибавяне на 1, а even и odd са едноместни предикатни символи, които се интерпретират в S съответно чрез предиката, който приема стойност 1 за четните числа и стойност 0 за нечетните, и чрез предиката, който приема стойност 1 за нечетните числа и стойност 0 за четните. Тогава например следните дизюнкти с променлива X са тъждествено верни в S:
(1) {even(X),odd(X)},
(2) {Шeven(X),Шodd(X)},
(3) {even(X),even(succ(X))},
(4) {odd(X),odd(succ(X))}.
Дизюнктите {even(X)} и {odd(X)} пък са примери за дизюнкти, които не са тъждествено верни в S.

    Пример 2. Нека S е структура, чийто носител е някое множество M от хора. Нека p е двуместен предикатен символ и p се интерпретира в S чрез двуместния предикат, приемащ стойност 1 точно за онези елементи на M2, в които първият член е родител на втория (като употребяваме думата "родител", тук подразбираме същински родител и изключваме например родителство по силата на осиновяване или по силата на втори брак на някой от същинските родители). Оказва се, че следните дизюнкти с променливи A, B, C, X, Y, Z са тъждествено верни в S:

{Шp(A,Y),Шp(A,Z),Шp(B,Z),Шp(B,X),Шp(C,X),Шp(C,Y), p(B,Y), p(C,Z)},
{Шp(A,Y),Шp(A,Z),Шp(A,X),Шp(B,X),Шp(C,X),Шp(C,Y), p(B,Y), p(C,Z)}
(аргументация, че това е така, може да се даде чрез използване на някои прости съображения за брой на родители на произволен човек).

    Пример 3. Нека n е положително цяло число, а X1, X2,...,Xn са променливи. Лесно се вижда, че дизюнктът

{Шp(X1,X2),...,Шp(Xn-1,Xn),Шp(Xn,X1)}
е тъждествено верен във всяка структура от вида, разглеждан в пример 2 (допускането, че при дадена оценка на променливите никой литерал от този дизюнкт не е верен в разглежданата структура, води до противоречие с това, че родителите на всеки човек са родени по-рано от него).

    Пример 4. Нека a, b, x, y са такива четири души, че a е родител на x и на y, а b е родител на x, но не е родител на y (тази ситуация се среща в живота!). Нека S е структура от вида, разглеждан в пример 2, но с M={a,b,x,y}. Тогава дизюнктът

{Шp(A,X),Шp(A,Y),Шp(B,X),p(B,Y)}
не е тъждествено верен в S. Действително, ако  v е оценка в S на променливите, за която са в сила равенствата
v(A)=a,   v(B)=b, v(X)=x,  v(Y)=y,
то никой от литералите в горния дизюнкт не е верен в S при оценката v.

    Нека D е един дизюнкт, а s е някоя субституция. Резултат от прилагането на s към D ще наричаме множеството от литералите, получени чрез прилагане на s поотделно към всеки литерал от D. Това множество е крайно (броят на елементите му не надминава броя на елементите на D) и значи е пак един дизюнкт; ще го означаваме със s(D).Частни случаи на даден дизюнкт ще наричаме резултатите от прилагането на субституции към него.

    Пример 5. Нека p е двуместен предикатен символ. Тогава дизюнктът {p(X,X)} е частен случай на дизюнкта {p(X,Y),p(Y,X)}, защото е резултат от прилагане към него на субституцията [X=:Y].

    Необходимото и достатъчно условие за вярност на резултата от прилагане на субституция към литерал се пренася и за дизюнкти. С други думи, за всяка субституция s,  всеки дизюнкт D, всяка структура S и всяка оценка v в S на променливите условието S,vs(D) е равносилно с условието S,vўD, където vў=sS(v). Доказателството се състои от следната верига от равносилности:

S,vs(D) Ы S,vs(L) за някой литерал L от D ЫS,vўL за някой литерал L от D Ы S,vўD.
Оттук следва веднага, че доказаното по-рано твърдение за запазване на тъждествената вярност при преминаване към частен случай се пренася и за дизюнкти, т.е. ако един дизюнкт е тъждествено верен в дадена структура, то и всички негови частни случаи са тъждествено верни в нея.

    Ще използваме току-що изказаното свойство в следния пример.

    Пример 6. Да разгледаме дизюнкта

{Шp(A,Y),Шp(A,Z),Шp(B,Z),Шp(B,X),Шp(C,X),Шp(C,Y), p(B,Y)},
получен от първия дизюнкт от пример 2 чрез пропускане на литерала p(C,Z). Ще покажем, че може да се намери структура S от разглеждания там вид, в която така полученият дизюнкт да не е тъждествено верен. И наистина, лесно се проверява, че ако приложим към този дизюнкт субституцията [A,X=:C,Z], ще получим дизюнкта от пример 4. Следователно разглежданият в настоящия пример дизюнкт не може да бъде тъждествено верен в структурата от пример 4.

    Ще отбележим още едно твърдение за запазване на тъждествената вярност на дизюнкти.

    За един дизюнкт Dў се казва, че е разширение на даден дизюнкт D, ако е налице съотношението DўКD, т.е. ако всички литерали от D принадлежат и на Dў. Очевидно е, че ако един дизюнкт е верен в дадена структура при дадена оценка на променливите, а друг дизюнкт е негово разширение, той също е верен в дадената структура при същата оценка на променливите. Оттук веднага следва, че ако един дизюнкт е тъждествено верен в дадена структура, то всеки дизюнкт, който е негово разширение, също е тъждествено верен в дадената структура.
 

Последно изменение: 29.05.2001 г.
 
 Previous  Next  Contents