Жасанды интеллектінің негізгі ұғымдары мен даму тенденциялары

Енді  бұл ойларды эксперттік жүйенің  келесі формалды анықтамасына сәйкес қортамыз.Эксперттік жүйе — бұл  компьютерлерге арналған программа ,ол шешім немесе кеңес беру мақсатында белгілі бір аймақты шаншыйды.Эксперттік жүйе шешім қабылдайтын адамның  ассистенті және толығымен адам қатысуын сұрайтын функцияларды орындай алады .Кім шешім қабылдайды сол өзінің құқығы бар эксперт бола алады,және сол кезде ғана программа өзінің бар болуын ақтайды . Альтернативті  вариант — осындай программмамен  істейтін адам оның көмегімен жоғары сапалы үлкен жетістіктерге жете алады. Адам мен машина арасындағы функциялардың  дұрыс бөлінуі эксперттік жүйенің  еңгізілуінің  жақсы нәтижелігінің  біріде бір кілттік .

Резолюция әдісі

Бұл тарауда G формуласының логикалық нәтижесі F₁,F₂,...,F_k формуласы болатынын дәлелдеу әдісіне берілген. Бұл әдіс Резолюция әдісі деп аталады. Логикалық құралдар туралы есеп есептің орындалуына әкеледі. Расындада, G формуласының  логикалық құралы F₁,F₂,...,F_k формуласы болады және {F₁,F₂,...,F_k, G}жиын формуласы орындалмайды.  Резолюция әдісі нақты айтқанда орындалмауын көрсетеді. Бұл әдістің бірінші ерекшелігі. Екінші ерекшелігіол туынды формуланы көрсетпей, дизъюнктарды (немесе элементар дизъюнкцияны) көрсетеді.

Алдымен логикалық құралдарды қарастырайық. Литерал деп атомарлы формуланы  немесе оның терісін, дизъюнкт – литералдар дизъюнкциясын айтқанбыз. Дизъюнкт бір литералдан тұруы мүмкін. Дизъюнктті біз литералдар жиыны деп алсақ  болады немесе дизъюнктті айырмасақ  та болады, себебі, коммутативті және ассоциативті дизъюнкциядан бір-бірінің көмегімен шығады, және де идемпотенттілік шығады. Мысалы X Y X и X Y дизъюнкттері тең. Бізге ерекше бос (ішінде литералы жоқ) дизъюнкт керек. Оны "квадратпен" белгілейміз □. Бос дизъюнкт кез келген интерпретацияда жалған деп есептейміз. Бұдан F&□ формуласы □ тең , ал F □ формуласы F-ке тең. Бос дизъюнкт те тура солай, себебі атомарлы формула 0, контекстті  резолюция әдісінде □-ті қолдану керек. .

 

 

 

 

 

Анықтама. L және L литералы қарама-қарсы деп аталады.

Логикалық құралдарда резолюция әдісі  резолюция ережесіне негізделген.

Анықтама. Резолюция ережесі логикалық құралдардан келесі ереже шығады: резолюция ережесінен Х F и X G дизъюнктінен F G дизъюнкті шығады.

Мысалы, X Y Z и X Y дизъюнкттерден Y Z Y дизъюнкттері шығады. Назар аударар болсақ, бірінші екі дизъюнкттерде тағы бір жұп қарама-қарсы литералдар шығады. Резолюция ережесі тек сол литералдарда қолданады деген тұжырым алсақ. Онда Y және  Y-ке қолданылған резолюция ережесінен X Z X шығады. Условимся еще о следующем: в дизъюнктке қайталанатын литералдарды және □ жазбасақ, онда басқа литералдар бар болады.

Анықтама. S – дизъюнкттар жиыны болсын. S-ң нәтижесі деп, дизъюнкттар тізімін айтады.

D₁,D₂,...,D_n дегеніміз S-ға қатысты әрбір дизъюнкт тізімі немесе бұдан резолюцияның соңғы ережесі шығады. D дизъюнкті S-ң нәтижесі, егер S-ң соңғы дизъюнкті D болса.

Мысалы, егер S={ X Y Z, Y U, X}, онда D₁= X Y Z, D₂= Y U, D₃= X Z U, D₄=X, D₅=Z U – S-дан шыққан нәтижесі. Z U дизъюнкті S-дан шығады.

Резолюция әдісін қолдану келесі тұжырымнан шығады және ол толық резолюция әдісінің теоремасы деп аталады.

Теорема 1. Логикалық құралдар дизъюнкттар S жиыны орындалмайды сонда тек сонда ғана S – дан бос дизъюнкт шықса.

Дәлелдеу үшін, G формуласы логикалық жиыны F₁,…,F_k формуласына резолюция әдісі келесі түрде қолданылады. Алдымен  T={F₁,…,F_k, G} формулалар жиыны құрылады. Одан кейін бұл формулалардың әр қайсысы КНФ-ке келтіріледі және шыққан формулалардан конъюнкция сызылады. S дизъюнкттар жиыны шығады. Және , нәтижесінде  S-дан бос дизъюнктті іздейді. Егер S-дан бос дизъюнкт алсақ, онда G  формуласы үшін F₁,…,F_k логикалық формула болады.  Егер S-дан алынбаса, онда G формуласы F₁,…,F_k логикалық формуласы шықпайды.

Бұл мысалды кері алсақ, G=Z формула. G=Z формуласы логикалық болады, нәтижесінде F₁= X Y X&Z, F₂= Y Z. T={F₁,F₂, G}жиындар формуласы. F₁ және F₂ формуласын КНФ-қа келтіреміз ( G формуласында осы форма болады). Нәтижесінде

F₁ эквивалентті X&( Y Z),

F₂  эквивалентті  (Y Z).

Онда S дизъюнкттар жиыны тең:

{X, Y Z, Y Z, Z}.

S жиынынан бос дизъюнкт оңай  алынады:

Y Z, Z, Y, Y Z, У, □.

Бұдан G формуласы  F₁, және F₂ логикалық формуласын шығады.

Бірінші қатарлы логикаға көшейік. Айнымалыға байланысты дизъюнктке тапсырыс берейік, ол жалпы кванторлармен  байланыста болады, бірақ кванторларды өіміз жазбаймыз. Бұдан шығады, екі  бірдей айнымалы әртүрлі дизъюнкттарда  әртүрлі болады.

Байқайтын болсақ, бірінші қатарлы  логикада резолюция ережесінің бұл  түрі орындалмайды. Расында да S={P(x),ØP(a)} дизъюнкттар жиыны орындалмайды, (себебі х айнымалысы жалпы квантормен байланысты). Осы уақытта егер логикалық  құралдар үшін резолюция ережесін қолдансақ, онда S бос дизъюнктін ала алмаймыз. Бұл жағдайда не істеу керек. P(x) дизъюнктін  кез келген х үшін P(x) ақиқат, бірақ P(x) ақиқат болады және x=a үшін де. х=а  деп алсақ , S^/={P(a),ØP(a)} дизъюнкттар жиынын аламыз. S жиыны және  S^/ бір мезетте орындалады (немесе орындалмайды). S^/ ішінен бастапқы резолюция ережесінің көмегімен тривиалды түрі шығады. Бұл мысалда бірінші қатарлы логикадағы резолюция ережесіне қосымша мүмкіндіктер қосу қажет екендігін көрсетеді.

Қажетті тұжырымдар берейік.

Анықтама. Ауыстыру деп теңсіздіктер жиыны аталады s={x₁=t₁, x₂=t₂,…, x_n=t_n},

x₁,x₂,…,x_n – әртүрлі айнымалы, t₁,t₂,…,t_n – терм, t_i термінде x_i (1£ i £ n) айнымалысы жоқ.

Егер s = (x₁=t₁,...,x_n=t_n), ал F – дизъюнкт, s(F) арқылы дизъюнкті белгілейміз, F бірқалыпты айнымалыдан шыққан x₁ –ден t1; және  т.б. x_n -нен t_n. Мысал, егер s={x₁=f(x₂), x₂=c, x₃=g(x₄)), F=R(x₁,x₂,x₃)ÚØP(f(x₂)), онда s(F)=R(f(x₂), c, g(x₄))ÚØP(f(c). Термдер осы сияқты орындалады.

Ыңғайлы болуы үшін бос ауыстыру енгізейік, теңсіздігі жоқ. Бос ауыстыруды е арқылы белгілейік.

Анықтама. {E₁,…,E_k} – литералдар жиыны немесе термдер жиыны болсын. Подстановка s ауыстыруы осы жиын үшін унификатор деп аталады, егер s(E₁)=s(E₂)=…=s(E_k). унификацияланған жиын, егер осы жиын үшін унификатор болса.

Мысал, атомар формулалар жиыны

{Q(a,x,f(x)), Q(u,у,z)}

унификациялайды {u=a, x=у,z=f(у)}, ал жиын

{R(x,f(x)), R(u,u)}

унификацияланбайды. Расында да, егер х-ті u-ға ауыстырсақ {R(u,f(u), R(u,u)} жиыны шығады.

u=f(u) ауыстыру жасау мүмкін емес, және ол пайдасыз, R(f(u), f(f(u))) және R(f(u), f(u)), формуласына келеді.

Егер жиын унификацияланған болса, онда ереже бойынша осы жиынның  бір ғана емес бірнеше унификаторы  болады. Берілген барлық унификаторлардың ішінен жалпы унификатор бөліп алуға  болады.

Анықтама. Егер  x={x₁=t₁, x₂=t₂,…, x_k=t_k} және h={y₁=s₁, y₂=s₂,…, y_l=s_l} – екі теңдеу. x және h ауыстыруы қойылады, тізбектелген болса

{x₁=h(t₁), x₂=h(t₂),…,x_k=h(t_k), y₁=s₁, y₂=s₂,…, y_l=s_l}                       (4)

x_i=x_i үшін 1£ i£ k, y_j=s_j, егер y_jÎ{x₁,…, x_k},  1 £ j £ l үшін осы теңдеулерді сызамыз..

Нәтижесі үшін дизъюнкттің орнына префиксті функционалді жазуды қоямыз, сондықтан x және h орнына h◦x аламыз, x- ті сосын h-ті сызамыз.

Мысал қарастырайық. x = {x=f(y), z=y, u=g(d)}, h = {x=c, y=z} болсын. Онда теңдіктер тізімі (4) келесі түрде болады

{x=f(y), z=z, u=g(d), x=c, y=z}.

Осы тізбектерден h◦x = {x=f(y), u=g(d), y=z} шығады.

Осы тізбектен ассоциативті екенін дәлелдеу қиын емес, сондықтан кезкелген x,h,x үшін x◦(h◦z)=(x◦h)◦z орындалады, және бос ауыстыру көбейтуге қарағанда нейтралды элемент болады. Соңында s◦e=e◦s=s кезкелген ауыстыру үшін шығады.

s = {x₁=t₁}○{x₂=t₂}○…○{x_n=t_n} үшін тізбектер тізімі: s = (x₁=t₁, x₂=t₂,…, x_n=t_n). &s орына дизъюнкт (және терм) қойсақ, тізбек x₁ t₁-ге ауысады, x₂ t₂ - ге ауысады және т.с.с., x_n t_n-ге ауысады

Анықтама. Унификатор s жиындар литералы немесе термдер деп осы жиынның жалпы унификаторы, егер  кез келген t унификаторы үшін литералдар жиыны бар, x ауыстыруы былай болады t=x○s.

Мысал, {P(x,f(а), g(z)), P(f(b),y,v)} жиыны үшін жалпы унификатор болып  s={x=f(b), y=f(a), v=g(z)} ауыстыруы болады. Егер t орына {x=f(b), y=f(a), z=c, v=g(c)} унификаторын алсақ, онда x={z=c}.

Егер литералдар жиын унификацияған болса, жалпы унификатор бар болады. Бұл тұжырымды параграф соңында дәлелдейміз. Ал қазір жалпы унификаторды табу алгоритмі көрсетейік. Алгоритм унификация алгоритмі деп аталады. Алгоритмді көрсету үшін жиыдар теңдігі қажет.

Анықтама. М – литералдар немесе термдер жиыны. Бірінші сол жақ позициясын бөліп аламыз, ол  жерде барлық литералдар бір символдан тұрмайды. Символдан басталатын, сол позицияны алатын әрбір литералдан теңдеу жазып аламыз. (Бұл теңдеу литералдың өзі, атомарлы формула және терм). Теңдеулерден шыққан жиын М –дағы ақылдасқан жиын деп аталады.

Мысал, егер M={P(x, f(y), a), P(x,u, g(y)), P(x, c, v)}, бірінші сол жақ позициясында барлық литералдар бір символдан тұрмайды – бесінші позиция. Ақылдасқан жиын f(y), u, c термдерінен тұрады. Ақылдасқан жиын {P(x, y), ØP(a, g(z))} ол жиын. Егер M={ØP(x, y),ØQ(a, v)}, онда ақылдасқаны мынаған тең: {P(x, y), Q(a, v)}.

Унификация алгоритмі

1 Қадам. k=0, M_k=M, s_k=e аламыз.

2 Қадам. Егер М_k жиыны бір литералдан тұрса, онда s_k –ны жалпы унификатор деп алып, жұмысты аяқтау. Басқа жағдайда N_k жиынын M_k-ға байланысты табу.

3 Қадам. Егер N_k жиынында v_k айнымалысы және терм t_k , v_k – ға кірмейтін бар болса,  онда 4-ке көшеміз, әйтпесе, М жиыны неунификатор және жұмысты аяқтау деген хаттама беру.

4 Қадам. s_k+1={v_k, t_k}○s_k–ға s_k+1–ді қойса, s_k-дан v_k t_k –ға алмасады, және v_k=t_k теңсіздігі жазылуы мүмкін. M_k жиыны v_k=t_k алмасуы орындалуы шыққан литералдар жиынын M_k+1 деп қарастырады.

5 Қадам.  k=k+1 деп және 2 қадамға өтеді.

М={P(x,f(y)), P(a,u)} болсын. Проиллюстрируем работу алгоритиа унификации на множестве М. алгоритмнің басында s₁={x=a} табылады, N₀={x,a} болғандықтан. M₁ жиыны {P(a,f(y)),P(a,u)}-ге тең. Сосын s₂={x=a, u=f(y)} және M₂={P(a,f(u))}-ге ашылады. Себебі M₂ 1 литералдан тұрады жұмысты аяқтайды және s₂ береді.

Екінші мысалды қарастырайық. M={P(x,f(y)), P(a,b)} болсын. Алгоритмнің бірінші  қадамыннан s₁=(x=a) и M₁={P(a,f(y)), P(a,b)}. 3-ші қадамның 2-шісінде М жиыны унификацияланбағаны туралы хаттама жібереді, себебі  N₁={f(y),a} – де айнымалы жоқ.

4 қадам орындалғанда , M_k жиынында айнымалылардың бірі өшіріледі (v_k айнымалысы), және жаңа айнымалы пайда болмайды. Бұл дегеніміз унификация алгоритмі әрқашан жұмысты аяқтайды, себебі 4 қадам шексіз орындала бермейді. Алгоритм 3 қадамда жұмысын аяқтаса, М жиыны унификацияланбаған. Алгоритм 2 қадамда жұмысын аяқтаса, s_k – М жиынының унификаторы. Егер s_k – жалпы унификатор болса, дәлелдеу қиын, бірақ біз дәлелдеп  көрейік.

Теорема 2. Егер М – ақарлы бос емес литералдар. Егер М унификатор, онда алгоритм унификациясы 2 қадамда жұмысын аяқтайды және s_k – М жиынының жалпы унификаторы.

Дәлелдеу. Егер t – М жиынының унификаторы. Индукцией по k индукциясы бойынша дәлелдейміз a_k бар егер t=a_k◦s_k.

Индукция базасы: k=0. онда  s_k=e және a_k орнына t алуға болады.

Қадам  индукциясы: k мағынасы 0£k£ l теңсіздігінде орындалады десек,  a_k дегеніміз t=a_k○s_k.

Егер s_l(M) бір литерал құраса, онда алгоритм келесі 2 қадамда тоқтайды. Сонда s_l жалпы унификатор болады, себебі t=a_l○s_l.

Егер s_l(M) 1 литералдан артық болса. Онда  алгоритм унификациясында жиын N_l – теңеседі. a_l  N_l жиынын унифицировать етуі керек, себебі t=a_l○s_l – М жиынының унификаторы. N_l – унификатор ең болмағанда бір v айнымалысы болады.

Егер t – терм  N_l-ң ішінен v-ден өте жақсы болса,  Множество N_l жиыны a_l унификатор, сондықтан a_l(v)=a_l(t). Бұдан t-ң ішінде v жоқ. 4 қадам алгоритмінде s_l+1 –ді алу үшін v=t, т.е. s_l+1={v=t}○s_l теңдігін қолданған.  a_l(v)=a_l(t) бұдан a_l – ң ішінде v=a_l(t) теңдеуі шығады..

Егер  a_l+1=a_l\{v=a_l(t)}. Онда a_l+1(t)=a_l(t),  t-ң ішінде v жоқ. Ары қарай

a_l+1○{v=t}=a_l+1È{v=a_l+1(t)}=a_l+1È{v=a_l(t)}=a_l.

a_l=a_l+1○{v=t}. Бұдан,

t=a_l○s_l=a_l+1○{v=t}○s_l=a_l+1○s_l+1.

Кез келген k үшін a_k бар, t=a_k○s_k. M жиыны унифицияланған, онда алгоритм 2 қадамда жұмысты аяқтау қажет. Сонда соңғы теңдеу s_k  М жиынының унификаторы,  s_k(М) жиыны жалпы унификатор, себебі туынды унификатор үшін  s_k – ға қойылған t бар, ол  t=a_k○s_k.

Теорема дәлелденді.

 

 

 

 

ҚОРЫТЫНДЫ