1. Булеви функции. Теорема на Пост-Яблонски за пълнота. Нека J2 = { 0, 1}. Всяка функция f : J2n  J

Доказателство:

Ще посочим алгоритъм за преобразуване на произволна система чрез еквивалентните преобразувания до система в решен вид или до явно нерешима система. Алгоритъмът се състои от следните стъпки:

1. 
   Ако системата не е в решен вид или не е явно
   

2. 
   Към системата прилагаме някое от четирите еквивалентни преобразувания (което е възможно) и отиваме към 1.
   

За целта трябва да покажем две неща:

1. Ако една система не е в решен вид и не е явно нерешима, то е възможно да се извърши някое от четирите преобразувания.

2. Алгоритъмът приключва след краен брой стъпки.

Нека T₁ = U₁, T₂ = U₂, …, T_n = U_n е система от уравнения между термове, която не е в решен вид и не е явно нерешима.

Да допуснем, че не е възможно да извършим никое от четирите преобразувания. Преди всичко, T_i  U_i за i  { 1, 2, …, n}, тъй като в противен случай бихме могли да извършим премахване на тъждество. Първо ще покажем, че T₁, T₂, …, T_n са променливи.

Да допуснем, че за някое i  { 1, 2, …, n} T_i не е променлива.

Ако U_i е променлива, тогава можем да извършим обръщане – противоречие. Ако U_i е константа, то уравнението T_i = U_i е явно нерешимо, тъй като T_i  U_i  системата е явно нерешима – противоречие. Ако U_i е съставен терм и T_i, U_i имат еднакви функционални символи с един и същ брой аргументи, то можем да извършим разпадане – противоречие. Ако U_i е съставен терм и

T_i, U_i имат различни функционални символи или функционални символи с различен брой аргументи, то уравнението T_i = U_i е явно нерешимо  системата е явно нерешима – противоречие.

Във всички случаи получихме противоречие с допускането,

че T_i не е променлива  T₁, T₂, …, T_n са променливи.

По предположение системата не е явно нерешима и тъй като

T_i  U_i, то T_i  VAR (U_i), i = 1, 2, …, n.

Ако допуснем, че за някои i  j  { 1, 2, …, n} T_i  VAR (U_j)  { T_j}

ще получим противоречие, тъй като бихме могли да извършим заместване. Така променливите T₁, T₂, …, T_n са две по две различни и T_i  VAR (U_j) за всеки i, j  { 1, 2, …, n }, т.е. системата е в решен вид, което е противоречие с допускането, че системата не е в решен вид. Така към всяка система от уравнения между термове, която не е в решен вид и не е явно нерешима може да се приложи някое от четирите еквивалентни преобразувания.

Ще покажем, че алгоритъмът завършва след краен брой стъпки.

Нека T е терм. Дефинираме височина на терма h (T) с индукция по построението.

База: Ако T е променлива, дефинираме h (T) = 1.

Ако T е константа, дефинираме h (T) = 2.

Предположение: Нека T = f (T₁, T₂, …, T_n) и h (T₁), h (T₂), …, h (T_n) са дефинирани.

Стъпка: Дефинираме h (T) = h (T₁) + h (T₂) + … + h (T_n) + 1.

Съвсем лесно с индукция по построението се проверява, че

височината на всеки терм е положително цяло число. При това термовете, които не са променливи имат височина

по-голяма от 1.

Под височина на системата от уравнения между термове

T₁ = U₁, T₂ = U₂, …, T_n = U_n ще разбираме числото

h (T₁) + h (T₂) + … + h (T_n). Ще изследваме как се променя височината на системата при извършване на еквивалентните преобразувания:

1. При премахване на тъждество височината намалява, тъй като от лявата страна премахваме терм и височината на всеки терм е положителна.

2. При разпадане от лявата страна премахваме съставен терм

f (V₁, V₂, …, V_m) и прибавяме термовете V₁, V₂, …, V_m.

От дефиницията за височина на терм височината на системата намалява с 1.

3. При обръщане от лявата страна премахваме терм, който не е променлива и го заменяме с променлива. Тъй като всеки терм, който не е променлива има височина по-голяма от 1, а променливите имат височина 1, то височината на системата намалява.

4. При заместване лявата страна или не се променя или променливи се заместват с термове, така че височината на системата или не се променя или нараства.

Така при първите три преобразувания височината на системата намалява, така че алгоритъмът може да извърши само краен брой пъти тези преобразувания едно след друго, т.е. без извършване на заместване.

Ще казваме, че системата от уравнения между термове

T₁ = U₁, T₂ = U₂, …, T_n = U_n е решена относно променливата x,

ако x = T_i за някое i  { 1, 2, …, n}, x  VAR (T_j)  VAR (U_j),

j  i  { 1, 2, …, n} и x  VAR (U_i), т.е. x не се среща никъде другаде в системата освен като лява част на точно едно уравнение.

Например, ако системата е в решен вид, то тя е решена относно

променливите T₁, T₂, …, T_n.

Нека системата е решена относно променливата x, x = T_i.

Ще покажем, че при всяко от еквивалентните преобразувания системата остава решена относно x:

1. При премахване на тъждество не можем да премахнем

T_i = U_i, тъй като x  VAR (U_i)  T_i  U_i. Така системата остава решена относно x.

2. При разпадане уравнението T_i = U_i не се променя, тъй като T_i не е съставен терм. Ясно е, че в новодобавените уравнения x не присъства, тъй като x не присъства в уравнението, което се разпада. Така системата остава решена относно x.

3. При обръщане уравнението T_i = U_i не се променя, тъй като T_i е променлива. Системата очевидно остава решена относно x.

4. При заместване не можем да използваме уравнението T_i = U_i, тъй като променливата x не се среща на никое друго място в системата. Така заместваме променлива, различна от x (с термове, които не съдържат x) и получената системата ще остане решена относно x.

Нека ₀ е множеството от всички променливи, които се срещат в първоначалната система. Очевидно, ₀ е крайно множество.

Разглеждаме броят на променливите от ₀, относно които системата не е решена. Съгласно горните разсъждения при извършване на кое да е от четирите еквивалентни преобразувания този брой не може да нарастне. Освен това, при заместване този брой намалява с 1. Действително, ако заместваме променливата Т_i, то тази система не е решена относно T_i, тъй като T_i се среща поне на още едно място в системата. Също T_i  VAR (U_i) и след заместване на T_i с U_i в другите уравнения ще получим система, която е решена относно T_i.

От направените разсъждения получаваме, че алгоритъмът може да извърши само краен брой пъти заместване, тъй като ₀ е крайно множество.

Така алгоритъмът извършва само краен брой пъти заместване и само краен брой пъти последователно останалите три преобразувания, така че той приключва след краен брой стъпки.
След приключване на алгоритъма получената система очевидно е еквивалентна на изходната система. Ако получената система е явно нерешима, то изходната система няма решение. Ако получената система е в решен вид, най-общото решение на изходната система се дава с най-общото решение на получената система в решен вид. В частност, всяка система която има поне едно решение има най-общо решение и решенията на системата са частните случаи на най-общото решение.
Твърдение: Ако A и B са две унифицируеми атомарни формули, то измежду техните унификатори има най-общ, т.е. съществува унификатор  на A и B, така че всички унификатори на A и B

са , където  е произволна субституция.

Доказателство: Тъй като A и B са унифицируеми,

то A = p (T₁, T₂, …, T_n), B = p (U₁, U₂, …, U_n), n  1 (p е n-местен предикатен символ) или A = p = B (p е n-местен предикатен символ за n = 0). Тогава унификаторите на A и B (и в двата случая) са решенията на системата T₁ = U₁, …, T_n = U_n. Тази система има решение, тъй като A и B са унифицируеми, така че тя притежава най-общо решение  и всички други решения на системата са , където  е произволна субституция. Така  е най-общ унификатор на A и на B.

Най-естественият начин за представяне на пространството на състоянията е чрез ориентиран граф с възли – състоянията и ориентирани дъги – операторите.

Основните действия свързани с пространството на състоянията са следните:

1. 
   Генериране на състояния – генериране на един от наследниците или на всички наследници на дадено състояние.
   
2. 
   Оценяване на състояния – оценките може да са двоични (например, true/false за целево/нецелево състояние) или числови в определен интервал (оценката на целевите състояния съвпада с единия край на интервала).
   

1. 
   Генериране на цялото пространство на състоянията.
   
2. 
   Решаване на задачи върху генерирано пространство.
   
3. 
   Комбинирана задача – едновременно постепенно генериране и оценяване на генерираните до момента състояния.
   

Три са основните типове задачи за търсене в пространството на състоянията:

1. 
   Търсене на път до определена цел – търси се път от някакво начално състояние до определено целево състояние (или кое да е състояние от определено множество от целеви състояния), вариант на това е търсене на оптимален (по някакъв критерий) път, пример е задачата за търговския пътник.
   
2. 
   Търсене на печеливша стратегия (при игра за двама играчи) – примери са шахмат, кръстчета и нулички и др.
   
3. 
   Търсене на цел при ограничителни условия – примери са задачата за осемте царици, решаване на криптограми и др.
   

1. 
   Неинформирано, сляпо търсене – извършва се при липса на допълнителна информация за спецификата на решаваната задача, обикновено се осъществява чрез пълно изчерпване по фиксирана стратегия, крайно неефективно е често дори практически невъзможно поради получаване на комбинаторен взрив и изчерпване на компютърните ресурси.
   
2. 
   Информирано, евристично търсене – извършва се при наличие на допълнителна информация за задачата, осъществява се чрез пълно изчерпване по гъвкава стратегия или чрез търсене с отсичане на част от графа на състоянията, което води до повишаване на ефективността на търсенето, с цената на известен риск – пренебрегват се части от пространството на състоянията и не винаги се достига до оптимален път, а понякога въобще не се достига до решение.
   

Известни са различни методи за решаване на задачата, като

най-популярни са минимаксната и алфа-бета процедурите.

Минимаксната процедура изисква построяване на цялото пространство на състоянията и намиране на оценките на състоянията без наследници. След това оценките се разпространяват отдолу нагоре, като всеки от възлите, съответни на ход на максимизиращия играч получава оценка, равна на максималната от оценките на неговите преки наследници, а всеки от възлите, съответни на ход на минимизиращия играч получава оценка, равна на минималната от оценките на неговите преки наследници.

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

При търсенето на цел при ограничителни условия са дадени множество от променливи със съответни дефиниционни области и множество от ограничения (допустими/недопустими) за тези променливи. Целевите състояния са множествата от стойности на променливите, които не нарушават ограниченията. Основният алгоритъм тук е разпространяване на ограниченията. Първоначалните ограничения се разширяват, като в тях се включват и ограниченията, които са логически следствия от входните. Този процес се нарича разпространяване на ограниченията. След това, ако не е намерено решение, се прави предположение за някой от неуточнените параметри. По такъв начин ограниченията се засилват, след което новополучените ограничения отново се разпространяват и т.н. Целта е да се достигне до противоречие (тогава се осъществява връщане назад и се прави ново предположение за съответния параметър, ако това е възможно и т.н.) или до целево състояние.

Даден е граф и част от върховете му са обявени за начални върхове и част за целеви върхове. Решение на задачата е път от начално до крайно състояние. Пътят може да се търси под формата на списък от възли или списък от дъги в графа на състоянията. Общият алгоритъм за решаване на тази задача е следния: Последователно се изследват пътищата от началното състояние. Поддържа се фронт от пътищата, които са били изследвани. По време на процеса на търсене фронтът се разширява в посока към неизследваните възли, докато се достигне до целеви възел. Начинът, по който фронтът се разширява дефинира стратегията на търсене. Общата схема на алгоритъма е следната:

1. 
   Инициализация. Определят се начално състояние s, целево състояние g и генерираща функция gen, която генерира списък от преките наследници на дадено състояние, създават се списъци unexplored (на неизследваните състояния) и explored (на вече изследваните състояния), като се присвояват начални стойности на двата списъка: unexplored = (s) и explored = ().
   
2. 
   Последователно изпълнение на процедурата search:
   
   1. 
      Ако unexplored == (), към стъпка 3.
      
   2. 
      cs = първият елемент на списъка unexplored.
      
   3. 
      Изтриване на cs от списъка unexplored.
      
   4. 
      Ако cs == g, към стъпка 3.
      
   5. 
      Изпълняване на gen за cs.
      
   6. 
      Наследниците на cs, които не се съдържат в списъка explored се добавят в списъка unexplored.
      
   7. 
      Добавяне на cs към списъка explored.
      
   8. 
      Обратно към a.
      
3. 
   Извеждане на резултата. Ако cs == g се използва списъкът explored за да се изведе пътя до целта g, в противен случай алгоритъмът завършва с неуспех (път не е намерен).
   

При търсенето в широчина се започва от нулевото ниво, което се състои от началните състояния и след това се преминава последователно през всички възли от следващото ниво, което се състои от преките наследници на възлите от предишното ниво. Това се прави докато не се изчерпят всички възли на пространството на състоянията. Търсенето в широчина е пълно,

но е скъпо (експоненциално). Схемата на търсенето в широчина се получава чрез следната модификация на общата схема: в стъпка 2.f. генерираните необходени наследници на cs се добавят в края на списъка unexplored.

При търсенето в дълбочина се обхожда изцяло даден клон и се преминава към следващия, като се започне от най-скоро обходен връх, който има поне един необходен наследник. Търсенето в този случай е евтино (линейно), но не е пълно (при краен граф е пълно). Схемата на търсенето в дълбочина се получава чрез следната модификация на общата схема: в стъпка 2.f. генерираните необходени наследници на cs се добавят

Съществуват някои модификации на двата метода. При метода търсене в ограничена дълбочина, който е модификация на метода за търсене в дълбочина, се изследват само върхове до определена, предварително зададена дълбочина. Схемата на този метод е аналогична със схемата на търсенето в дълбочина с една модификация: в стъпка 2.f. генерираните необходени наследници на cs не се добавят в списъка unexplored, ако дълбочината на възела cs е по-голяма или равна на определената максимална възможна дълбочина. При метода итеративно търсене по нива се изпълнява последователно търсене в ограничена дълбочина, като се започне от максимална дълбочина 1 и на всяка итерация максималната дълбочина се увеличава с 1 до достигане до някаква горна граница (например, броят на дъгите в графа).

Ще опишем реализация на четирите метода за неинформирано търсене на Prolog.
Графът представяме чрез множество от факти от вида
arc (Node1, Node2, Cost) – означава, че съществува ребро от върха Node1 до върха Node2 с цена Cost.
breadth_first ([[Goal|Path]|_], Goal, FinalPath) :–

reverse ([Goal|Path], FinalPath).

breadth_first ([Path|List], Goal, FinalPath) :–

extend (Path, NewPaths),

append (List, NewPaths, NewList),

breadth_first (NewList, Goal, FinalPath).

extend ([Node|Path], NewPaths) :–

findall ([NewNode, Node|Path], (arc (Node, NewNode, _),

\+ member (NewNode, [Node|Path])), NewPaths).
Предикатът breadth_first реализира търсене в широчина.

Първият аргумент на breadth_first е списък от пътища, които започват в началния връх и завършват в някакъв междинен връх (този списък се обработва като опашка), вторият аргумент на breadth_first е целевият възел, в третия аргумент се получава търсеният път.

extend1 (Depth, Path, NewPaths) :–

length (Path, Len),

Len < Depth, !,

extend (Path, NewPaths).

extend1 (_, _, []).

findall (arc (X, Y, Z), arc (X, Y, Z), Graph),

length (Graph, N),

iterative_deepening1 (1, List, Goal, FinalPath, N).

depth_bound (Depth, List, Goal, FinalPath).

iterative_deepening1 (Depth, List, Goal, FinalPath, N) :–

Depth1 is Depth+1,

Depth1 <= N, !,

iterative_deepening1 (Depth1, List, Goal, FinalPath, N).

При метода на най-доброто спускане (best-first search) евристиката се използва не за отсичане, а за осигуряване на гъвкавост при търсенето. При него, на всяка стъпка от изпълнението от списъка на необходените възли се избира най-добрия (тук се намесва евристиката). След това се генерират наследниците на избрания връх, необходените от тях се добавят към списъка на необходените върхове, отново се избира най-добрия възел и т.н. до достигане на целеви възел. Методът е ефективен, но нито е пълен (при краен граф е пълен), нито оптимален. Схемата на този метод за търсене се получава от общата схема със следната модификация: добавя се нова стъпка между 2.f. и 2.g., в която се сортира списъка unexplored по нарастване на евристиките на възлите в него.