Лекции по логическо програмиране



страница1/22
Дата01.06.2017
Размер2.18 Mb.
  1   2   3   4   5   6   7   8   9   ...   22

Лекции по логическо програмиране

Четени през летния семестър на учебната 2002/2003 година. Лектор тогава беше професор Димитър Скордев.

Използвал съм мои (и на мои колеги) записки от лекции, както и материалите на проф. Скордев на

http://www.fmi.uni-sofia.bg/fmi/logic/skordev/ln/.

Префиксни изрази над множество от думи

нека е дадена азбука A;

дължина на думата   A* ще означаваме с ||;

в азбуката A част от символите са отделени от другите и имат спомагателна роля:



  • леви ограничители;

  • десни ограничители;

  • разделители;

трите множества са чужди помежду си;
например в термините на езика PROLOG можем да си мислим, че A е съставена от всички малки и големи латински букви, десетичните цифри, подчертаване - _, кръглите скоби - (, ),

запетая - ,, двоеточие - :, точка и запетая - ;; единствен лявограничител е лявата скоба, единствен десен ограничител е дясната скоба, разделители са запетаята, двоеточието и точката със запетая;


нека е дадено множество A*, т.е. е множество от думи над азбуката A; част от думите над A ще наречем префиксни изрази над ; дефинираме префиксен израз над индуктивно:

База: всяка дума от е префиксен израз над ;

Предположение: нека w  , E1, E2, …, En (n  1) са префиксни изрази над , l  A е ляв ограничител, r  A е десен ограничител и

s1A, s2A, …, sn-1A са разделители;

Стъпка: тогава думата wlE1s1E2s2…En-1sn-1Enr е префиксен израз над ; (многоточието значи изброяване, то не е дума над A);

Заключение: няма други префиксни изрази над ;


в конкретния пример за езика PROLOG, думата от индукционната стъпка има следния вид: w(E1,E2, …,En);
префиксните изрази от базата на индуктивната дефиниция наричаме прости, от стъпката наричаме съставни;
основен проблем е осигуряването на еднозначен синтактичен анализ на префиксните изрази; това означава, че трябва да са изпълнени следните две изисквания:

  • простите префиксни изрази трябва да са различни от съставните; например, ако = A* това изискване очевидно е нарушено;

  • съставните префиксни изрази трябва да се прочитат еднозначно, т.е. ако

wlE1s1E2s2…En-1sn-1Enr = wlE1s1E2s2…Ek-1sk-1Ekr, то

w = w, l = l, n = k, E1 = E1, E2 = E2 …, En = En, s1 = s1,

s2 = s2, …, sn-1 = sn-1; например, ако , е разделител в A, (, ) са съответно ляв и десен ограничител, w  , ,, и ,, то думата w(,,,,) не се прочита еднозначно;
едно просто достатъчно условие за еднозначен синтактичен анализ е в думите от да не участват леви и десни ограничители и разделители; в следващите разглеждания ще предполагаме, че това условие е изпълнено;

нека   A*;

с ЛО () ще означаваме броят на левите ограничители във ;

с ДО () ще означаваме броят на десните ограничители във ;


Лема 1.: във всеки префиксен израз, броят на левите ограничители е равен на броя на десните ограничители;

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

нека  е префиксен израз;

провеждаме индукция по построението на ;

База: ако   , то ЛО () = ДО () = 0, тъй като по предположение думите от не съдържат леви и десни ограничители;

Предположение: нека  = wlE1s1E2s2…En-1sn-1Enr, където

нека w  , E1, E2, …, En (n  1) са префиксни изрази над ,

l е ляв ограничител, r е десен ограничител, s1, s2, …, sn-1 са разделители и ЛО (Ei) = ДО (Ei) за i = 1, 2, …, n;

Стъпка: тогава ЛО () = ЛО (wlE1s1E2s2…En-1sn-1Enr) =

= ЛО (w) + ЛО (l) + ЛО (E1) + ЛО (s1) + … + ЛО (En-1) + ЛО (sn-1) +

+ ЛО (En) + ЛО (r) = 1 + ЛО (E1) + … + ЛО (En), тъй като множествата на левите ограничители, десните ограничители и разделителите са чужди помежду си и думите от не съдържат леви ограничители;

аналогично ДО () = ДО (wlE1s1E2s2…En-1sn-1Enr) =

= ДО (w) + ДО (l) + ДО (E1) + ДО (s1) + … + ДО (En-1) + ДО (sn-1) +

+ ДО (En) + ДО (r) = ДО (E1) + … + ДО (En) + 1;

от индукционното предположение получаваме, че

1 + ЛО (E1) + … + ЛО (En) = ДО (E1) + … + ДО (En) + 1 и тогава

ЛО () = ДО ();
казваме, че думата   A* е начало на думата   A*, ако съществува   A*, така че  = ; ако   , казваме че  е същинско начало на ;
Лема 2.: нека  е префиксен израз над ; тогава или  не съдържа разделители, или всяко начало на , което завършва с разделител съдържа повече леви ограничители, отколкото десни;

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

индукция по построението на ;

База: ако   , то по предположение  не съдържа разделители и твърдението е изпълнено;

Предположение: нека  = wlE1s1E2s2…En-1sn-1Enr и твърдението е изпълнено за префиксните изрази E1, E2, …, En;

Стъпка: ако n = 1 и E1 не съдържа разделители, то твърдението е изпълнено; нека  съдържа поне един разделител и нека  е произволно начало на , което завършва с разделител;

ако  завършва в sk за някое k  { 1, 2, …, n-1} (това може да се случи при n > 1), то ЛО () = ЛО (wlE1s1E2s2…Ek-1sk) =

= 1 + ЛО (E1) + … + ЛО (Ek-1) и ДО () = ДО (wlE1s1E2s2…Ek-1sk) =

= ДО (E1) + … + ДО (Ek-1);

от лема 1. ЛО (Ei) = ДО (Ei) за i = 1, 2, …, k-1, така че

ЛО () > ДО ();

ако  завършва в разделител в Ek, k  { 1, 2, …, n}, то

 = wlE1s1E2s2…Ek-1sk-1k, където k е начало на Ek, което завършва с разделител; тогава ЛО () = ЛО (wlE1s1E2s2…Ek-1sk-1k) =

= 1 + ЛО (E1) + … + ЛО (Ek-1) + ЛО (k) и ДО () =

= ДО (wlE1s1E2s2…Ek-1sk-1k) = ДО (E1) + … + ДО (Ek-1) + ДО (k);

от лема 1. имаме ЛО (Ei) = ДО (Ei) за i = 1, 2, …, k-1 и от индукционното предположение имаме, че ЛО (k) > ДО (k);

така ЛО () > ДО ();
Лема 3: ако E1s1E2s2…En-1sn-1En = E1s1E2s2…Ek-1sk-1Ek, където

Ei, Ej са префиксни изрази, sm, sp са разделители, то

n = k, E1 = E1, …, En = En, s1 = s1, …, sn-1 = sn-1;

Доказателство: провеждаме индукция по числото n;

База: (n = 1) имаме E1 = E1s1E2s2…Ek-1sk-1Ek;

да допуснем, че k > 1; тогава E1s1 е начало на E1, което завършва с разделител и от лема 2. ЛО (E1s1) > ДО (E1s1) 

ЛО (E1) > ДО (E1), което е противоречие с лема 1.;

така k = 1 и E1 = E1;

Предположение: нека твърдението е изпълнено за n-1 (n > 1);

Стъпка: ще покажем, че твърдението е изпълнено за n;

имаме E1s1E2s2…En-1sn-1En = E1s1E2s2…Ek-1sk-1Ek;

да допуснем, че k = 1; тогава E1s1E2s2…En-1sn-1En = E1 и аналогично на базата ще достигнем до противоречие; така k > 1;

ще покажем, че E1 = E1; тъй като E1 и E1 са начала на една и съща дума, достатъчно е да покажем, че |E1| = |E1|;

ако допуснем, че |E1| > |E1|, то E1s1 е начало на E1, което завършва с разделител (k > 1) и подобно на базата достигаме до противоречие;

ако допуснем, че |E1| < |E1|, то E1s1 е начало на E1, което завършва с разделител (n > 1) и подобно на базата достигаме до противоречие;

така |E1| = |E1|  E1 = E1 

s1E2s2…En-1sn-1En = s1E2s2…Ek-1sk-1Ek  s1 = s1 

E2s2…En-1sn-1En = E2s2…Ek-1sk-1Ek;

за получените думи прилагаме индукционното предположение; получаваме n – 1 = k – 1  n = k, E2 = E2, …, En = En, s2 = s2, …,

sn-1 = sn-1;


сега вече можем да покажем следната
Теорема: при направеното предположение е осигурен еднозначен синтактичен анализ на префиксните изрази;

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

първото изискване очевидно е изпълнено, тъй като простите префиксни изрази не съдържат леви и десни ограничители;

нека wlE1s1E2s2…En-1sn-1Enr = wlE1s1E2s2…Ek-1sk-1Ekr;

първо ще покажем, че w = w; достатъчно е да покажем, че

|w| = |w|;

ако допуснем, че |w| > |w|, то wl е начало на w, което е противоречие, тъй като w не съдържа леви разделители;

ако допуснем, че |w| < |w|, то wl е начало на w, което е противоречие, тъй като w не съдържа леви разделители;

така |w| = |w|  lE1s1E2s2…En-1sn-1Enr = lE1s1E2s2…Ek-1sk-1Ekr  l = l  E1s1E2s2…En-1sn-1Enr = E1s1E2s2…Ek-1sk-1Ekr  r = r

 E1s1E2s2…En-1sn-1En = E1s1E2s2…Ek-1sk-1Ek; от лема 3. получаваме n = k, E1 = E1, …, En = En, s1 = s1, …, sn-1 = sn-1;



  1   2   3   4   5   6   7   8   9   ...   22


База данных защищена авторским правом ©obuch.info 2016
отнасят до администрацията

    Начална страница