Loogilise programmeerimise 1.kontrolltöö konspekt (0)

1. Sissejuhatus:
1.1. Mis on loogiline programmeerimine?
l Programmeerimise paradigma
l loogiline (LP)
l funktsionaalne (FP) l jt
Fookus :
MIDA ARVUTADA
l LP ja FP on deklarati vsed programmeerimissti lid;
l LP põhineb loogika printsi pidel ja kasutab automaattõestamise protseduure
( resolutsioon , unifitseerimine);
l LP keel on Prolog , kuid LP ≠ Prolog;
1.1. Mis on loogiline programmeerimine? (2)
l LP sobib tehisintel ekti rakenduste programmeerimiseks:
l loomuliku keele analüüs ( DCG grammatikareeglid )
l ekspertsüsteemid (otsingu- ja järeldusreeglid)
l kujundituvastus (tuvastusreeglid)
l kitsendustega planeerimine ( logistika , marsruudi otsimine) l rekursi vsete
funktsioonide püsipunkti arvutus
l jne
l LP ei sobi:
l Kiired numbrilised arvutused (n. maatriksarvutused, võrrandid)
l OOP (kuigi on toetatud mõnes prologis)
l kasutajali deste programmeerimine (tugi on nõrk)
l masingraafika
1.1. Mis on loogiline programmeerimine? (3) Miks tasub õppida LP?
l Õpetab mõtlema probleemikeskselt ja esitama lahendusi abstraktsel kujul
l Programmi põhifunktsioonid:
l reaalse maailma probleemide abstraktne esitamine,
l abstraktsioonide teisendamine ja sidumine omavahel
l abstraktsioonide põhjal arvutamine/otsuste tegemine
l Programeerimiskeel peab võimaldama
l kirjeldada ja analüüsida abstraktsioone arvutile sobival kujul
l Deklarati vsed programmerimiskeeled sobivad
l abstraktsete objektide ja nende seoste kirjeldamiseks
l väldivad protseduurseid detaile

1.1. Mis on loogiline programmeerimine? (4)
l Universaalne keel omaduste/seoste abstraktseks kirjeldamiseks on loogika
l à LP on programmeerimine loogika keeles!
l Prolog – programming in logic
l LP ≠ Prolog
1.2 LP ajalugu
l Prolog (1972)
l Alain Colmerauer, Phil ipe Roussel;
l Edinburgh Prolog (1980 algus)
l David Warren ;
l 1980 – 2015 – laiendamine teiste programmeerimis- paradigmadega
l paral eelsus, OO, andmetüübid jm
l palju Prologi dialekte
1.3 LP meetod
l Piiritleda valdkond :
l reaalse maailma model eeritav situatsioon (domain, use- cases )
l määratleda sel ega seotud põhimõisted
l defineerida mõisteid iseloomustavad attribuudid ja nende omadused
l defineerida seosed attribuutide vahel
l Formaliseerida valdkonna objektid ja seosed LP keeles
l tekib faktide/tuletusreeglite struktuur
l Saadud teadmiste struktuuridel formuleerida päringud
LP “õrnad” kohad
l Teadmiste esitamine on otsingureeglite tundlik
• 
l  päringu tulemus oleneb otsingureeglist ja faktide järjestusest teadmusbaasis
• 
l  tagasivõtu (backtracking) mehhanismist arusaamine nõuab otsingumootori
tundmist
l Keeruline saavutada “puhast deklarati vsust”
l Efektiivsuse saavutamiseks peab tundma Prologi otsingumootorit
l Praktilises programmeerimises vaja ka nn “madala taseme” käske:
l kasutajali desejuhtimine,
l failisüsteemi käsud,
l stringide teisendamine jms.
LP edasiarendused
l Laiendamine teiste programmikeelte paradigmadega
Põhimõisteid
Aatomid -- andmete, programmide, failide jne. nimed:
o alfanumbrilised aatomid
o Prologi jaoks reserveeritud sümbolid , mida ei ole soovitav kasutada aatomites
Termid :
o muutujad
o konstandid
• täisarvud
• reaalarvud
• aatomid
• listid
o Listid -- esitavad loendeid
Predikaadid (faktid)
o kasutaja poolt defineeritavad predikaadid o sisemised e. sisseehitatud predikaadid
Predikaadi tähistus:
teekond /1
teekond – predikaadi funktor
1 – predikaadi aarsus.
Horni lause ( clause )
Lause esineb fakti või reegli kujul.
Iga lause algab predikaadi nimega ja lõpeb punktiga.
Mitu sama funtori ja aarsusega lauset defineerivad Horni lause alternati vid.
Loogikatehted
, - konjunktsioon
; - disjunktsioon
not - eitus (eitus kehtib ainult Prologi andmebaasi kontekstis so
”suletud maailma” eeldus)
b:- a või s:- a -> b (reegli kehas) – implikatsioon s:- not(a);b.
; (käsurealt) nõuab otsingumootorilt järgmist lahendit
Reeglid
Reegel ehk tingimuslik Horni lause.
Päringud (queries)
- Päring defineerib programmi jaoks sihi ( goal ).
- Päring: call (Goal) on semantiliselt samaväärne päringuga ?– Goal
- Päringu muutujad väärtustatakse päringu täitmisel, kui leidub sobiv unifitseering
- ”;” kasutamine päringus sunnib tagasivõtul otsima uut lahendit.
Sisseehitatud predikaadid Loogikavälised predikaadid:
o otsingu juhtimise predikaadid ( repeat ,
o sisend-/väljundpredikaadid (consult, reconsult, get, put,
write, ...)
o aritmeetika predikaadid o operaatorid
Predikaadid tööks termidega:
o termiteisendused
Predikaadid tööks stringidega:
o string_to_atom(? String , ? Atom )
o string_to_list(?String, ?List)
o string_length(+String, - Length )
o string_concat(?String1, ?String2, ?String3)
o sub_string(+String, ?Start, ?Length, ?After, ?Sub)
Predikaadid mitme lahendi leidmiseks:
o findal (+Template, +Goal, -Bag) o bagof(+Template, +Goal, -Bag)
Operaatorid
o Aitavad parandada lähtekoodi loetavust
o Kõik süsteemioperaatorid v.a. ”,” on ümberdefineeritavad
o Omavad kehtivust mooduli piires, kuid saab ka moodulitest välja eksportida
Operaatori deklareerimine
o prioriteet (1, ..., 1500) – väiksem number annab kõrgema prioriteedi.
o tüüp:
§assotsiati vsus(näide:16/2 + 6)
§ kuju ( prefiks , infiks, postfiks )
Kui operaatori # tüüp on yfx, si s täidetakse # korduvesinemisi vasakult
paremale
Kui operaatori # tüüp on xfy, si s täidetakse # korduvesinemisi paremalt
vasakule
Operaatori deklaratsioon :

:- op(Priority, Type, Name).
Võrdus: arg1 = arg2 või =(arg1, arg2)
Võrdus kehtib, kui võrdusega seotud muutujat omavahel unifitseeruvad (väärtused
on võrdsed või kui üks muutja on väärtustamata, siis omandab ta teise väärtuse.
• Rekursioon
Predikaadi poole pöördumine toimub sama predikaadi kehast.
• Programmi dünaamiline muutmine - Dünaamilise predikaadi defineerimine
Päringute dünaamiline loomine (predikaat 'Univ'):
Esituskuju:? Term =.. ?List
Listi esimene element on loodava termi funktor ja ülejäänud elemendid on
loodava termi argumendid. Argumendiks võib olla ka mutuja.
Ettevaatust ! Dünaamiliste faktide kasutust pi rab tagasivõtuga otsing – vältida dün. faktide
loomist/kustutamist nende faktide järgi tehtava otsingu ajal.
o  LOOGIKA on teadus mõtlemise vormidest ja reeglitest.
o  Mõtlemise vormid: abstraktne, kujundiline, inspirati vne
o  Loogika uurib abstraktset mõtlemist, mõtlemis-reegleid ja
nende rakendamist faktidele (mõtlemise grammatika).
o  Aristoteles: ”Loogika on väitluse struktuuri uuriv teadus“
o  !!! Väidete loogiline tõestamine on nende tõesuse näitamine kasutades loogika
reegleid ja teisi (varem tõestatud või postuleeritult) tõeseid väiteid .
Abstraktse mõtlemise mehhanismid :
◦ Deduktsioon
◦ Induktsioon
◦ Abduktsioon
◦ Arutlemine analoogia põhjal
Deduktsioon:
Üldistest reeglitest ja konkreetsetest faktidest lähtudes uute faktide järeldamine
Induktsioon:
Üksikute teadmiste baasil üldistuste (sh reeglite) tuletamine  
Abduktsioon:
“Tagantjärele” seletamine  
} Järeldamisskeem ◦ Olgu teada, et
–  väitest A järeldub B
–  B kehtivus on ratsionaalselt põhjendatav
◦ Järeldus:
–
Siis peab olema põhjendatav ka väite A kehtivus
Arutlemine analoogia põhjal:
} Omaduste ülekandmine objektide sarnasuse põhjal:
} Järeldusskeem:
◦ Eeldused (e. teada olevad faktid):
– Kui objektil A on attribuudid a, b, c ja d
– Ja objektil B on attribuudid a, b, c ◦ Järeldus :
– Siis on tõepärane, et ka objektil B on attribuut d.
Lause esitab teadmist, mis võib olla tõene või väär.
Lauseid tähistame lauseloogikas lausemuutujatega:
• 
Term tähistab objekti, mis sisaldub väites
• 
Term omab tõeväärtusest erinevat väärtust: täisarv, nimi, kaardimast jne
Termide defineerimine:
Defineerimine üldise tüübi ja kitsendava(te) omadus(t)e kaudu:
◦ Definitsioonis ei tohi kasutada defineeritavat termi (ringdefinitsioon e. tautoloogia)
Rekursiivne definitsioon
Uus termi eksemplar defineeritakse varem defineeritud eksemplaride kaudu, kuid
teatud regulaarse modifikatsiooniga.
Definitsioonis tuleb vältida topelt eitust ja võimaluse korral ka eitust.
Ostensi vne definitsioon (osutamise, loetlemise teel).
Defineerimine analoogia kaudu, mil ele on lisatud eristav tingimus.
Tüüplaused:
Kategooriline lause
Kuulutab fakti kehtivaks või mittekehtivaks. Esineb traditsiooniliselt subjekt -predikaat
vormis:
• 
subjekt – objekt, mil e kohta midagi väidetakse
• 
predikaat – subjekti omadus, mil e kehtivust väidetakse Näide: Jumal on surematu
Hüpoteetiline lause
Väite kehtivus sõltub teatud tingimustest
Disjunkti vne lause
Väljendab alternati vi
Dilemma
Väljendab olukorda, kus ükski alternati videst ei rahulda lauses antud tingimust.

Loomuliku keele kasutades esinevaid loogikavigu:
1.  Ekvivooksus – sama termi kasutatakse erinevates tähendustes
2.  Üldise reegli kasutamine sobimatul erijuhul
3.  Konteksti vahetus argumenteerimise käigus
4.  Nõutakse jah/ei tüüpi vastust küsimusele, mil ele ei saa ni  vastata .
5.  Küsimuse tähendus ja vastus oleneb kontekstist
• 
Väited koosnevad lihtlausetest, mis on omavahel seotud loogika seoste ehk
tehetega (ja; või; ei; kui ..., si s ..., jne).
• 
Lausearvutuse seoste korral määravad osalausete tõeväärtused täielikult kogu lause
tõeväärtuse, osalausete konkreetne sisu ei ole aga tähtis.
• 
Lausearvutuse tehteks nimetatakse ni sugust lausetes kasutatavat seost, mil e
tõeväärtus on tema osalausete tõeväärtuste funktsioon ( Boole ’i funktsioon).
Semantika – valemi tõeväärtuse määratlus téma alamvalemite töeväärtuste põhjal.
3 Predikaatarvutus
3.1 Formaliseerimine predikaatarvutuse keeles
Predikaat väljendab objekti omadust või mingit seost (relatsiooni) objektide vahel.
!!! Esimest järku predikaatarvutuses:
- predikát konstandid—puuduvad predikát muutujad st.kui predikát on defineeritud,
siis arutluse käigus tema tähendus ei muutu,
- üks predikaat ei tohi olla teise predikaadi argumendiks.
• Liitlausete formaliseerimine:
- Atomaarne lause e. aatom–sisaldab vaid ühte predikaati
- Liitlause – moodustatakse aatomitest lausearvutuse tehete abil
• Kvantorid
Üldistuse ja abstraktsiooni väljendamiseks
Predikaatarvutuse arutlus kehtib mingi valdkonna objektide kohta Valdkonna
objektide hulka kokku nimetatakse universumiks.
-  Üldisuskvantor ( universal quantifier) - universumi kõikide objektide kohta
käiva väite esitamiseks .
Muutuja on valemis seotud, kui ta esineb koos kvantoriga ja avaldises kvantori
mõjupi rkonnas ja vastasel juhul on muutuja valemis vaba.
Muutuja väärtustamisel saadavat lauset nim. väärtustatuks ja väärtustamata lause
eksemplariks.
3.2 Predikaatloogika süntaks ja semantika
Indiviidtermid on indiviidkonstantide sümbolid ja indiviidmuutujad
• Süntaks(induktiivselt)
Atomaarne valem e. aatom on kujul L, kus L on 0- kohaline predikaatsümbol
e.lausemuutuja
1. Atomaarne valem on valem
2. Kui p on valem, si s ¬ p on valem.
3.Kui p ja q on valemid, siis p∧q,p∨q,p ⇒q,p ≡q on valemid.
4. Kui p on valem ja v on indivi dmuutuja, si s ∀v p ja ∃v p on valemid.
5. Muid valemeid PA-s ei ole
Muutuja on valemis seotud, kui kõik tema esinemised sel es valemis on seotud. Vastasel
juhul on muutuja valemis vaba.
Valem on kinnine (closed), kui kõik tema muutujad on seotud ja vastasel juhul on valem
vaba.
Lauseks nimetatakse predikaatarvutuse valemit, mil es ei ole vabu muutujaid
Semantika esitus aʹla Tarski
! PA lause tõesuse kontrol imiseks on vaja vaadata läbi kõik tema tähendused.
!! Tähendused sõltuvad ka seotud muutujate väärtustustest →
Selleks tõeväärtuse tabelid ei sobi, vaja kompaktsemat esitust tõeväärtuse arvutamiseks.
PA signatuur sisaldab antud arvutuse kõiki predikaat- ja konstantsümboleid.
PA loogika sümbolid – loogikatehte sümbolid ja indivi dmuutujad.
Olgu Const – PA indivi dkonstantide sümbolite loend ja Pred predikaatsümbolite loend, si s
signatuur σ on nende loendite Const ja Pred paar:
σ = 〈 Const ; Pred 〉 
Universum U – kõigi objektide hulk, mida PA termid võivad tähistada
PA interpretatsiooniks I nimetatakse loendit, mis koosneb universumist
Olgu p(x/c) valem, mis on saadud valemist p mutuja x kõigi vabade esinemiste asendamisel
sümboliga c. Kui x on valemi p ainus vaba muutuja ja c universumi mingile elemendile vastav
konstantsümbol, si s on p(x/c) predikaatarvutuse kinnine valem e. lause.
Valem p on PA-s loogiliselt tõene, kui ta on tõene igas interpretatsioonis: ⊨ p
Valem p on PA-s loogiliselt väär, kui ta on väär igas interpretatsioonis: ⊨ ¬p
Kõik ülejäänud valemid on kontingentsed.
Kehtestatavad valemid on loogiliselt tõesed ja kontingentsed
Mitte segamini ajada loogilise järelduvuse mõistega!!!
ØValemite hulgast Γ järeldub loogiliselt valem p, kui iga Γ mudel on ka p mudel.
• Üldjaatav lause (A - väljendab omaduse olemasolu kõigil antud li ki objektidel):
• Osajaatav lause (I - omadus esineb ainult osadel antud li ki objektidel
•  Vastandid - laused, mis ei saa olla korraga tõesed
•  Vasturääkivus e. kontradiktsioon – laused, mil e tõeväärtused on alati erinevad
• Sül ogism on kahe eeldusega kehtivad arutlused .
• Eeldustes on 3 mõistet, kusjuures üks esineb mõlemas eelduses
Samanimeliste kvantorite järjekorra vahetamine on lubatud.
Erinevat tüüpi kvantorite kohti ei saa vabalt vahetada!!!
Loogiline programm on Horni disjunktsioonide (disjunktiivsete valemite) kogu, kus ükski
valem ei sisalda üle ühe positiivse literaali. Kui q1,..., qn on tõesed, si s on ka p tõene” ehk
”Lausetest q1,..., qn järeldub lause p .
q Horni lausete tüübid:
• Fakt – HL, mil el puudub keha e. ainsast positi vsest literaalist koosnev lause:
• Reegel - HL, mil el on pea ja keha e. ühest positi vsest ja vähemalt ühest negati vsest
literaalist koosnev disjunktsioon.
• Päring – HL, mil el on ainult keha e. vähemalt ühest negati vsest literaalist koosnev
disjunktsioon.
Øpäring Prologis on otsingut käivitav käsk, näiteks ?- isa( juku ,X).
Suletud maailma eeldus:
tõene on ainult see väide, mil e tõesuse saab Prolog programmis tuletada olemasolevatest
faktidest.
NB! Faktide puudumine tähendab faktide mittekehtimist so faktide puudumine ei tähenda
määramatust!
4.2 Resolutsiooni meetod
Resolutsioon - Horni lausete kujul oleva dedukti vse süsteemi tuletusreegel.
ØValem Δ ⇒ D kehtib parajasti si s, kui tema eitus ¬ (Δ ⇒ D) ≡ Δ ∧¬ D on vasturääkiv.
ØHorni lause tõestamiseks tõestatakse, et positi vse literaali eituse konjunktsioonist
eeldusdisjunktidega saab tuletada vastuolu.
Øst temast saab tuletada tühja disjunkti.
Tühja disjunkti tuletamiseks kasutame klassikalise loogika reegli modus
ponens üldistust - resolutsiooni reeglit (RR).  
Pärast RR iga rakendamist on saadud valemis 2 literaali vähem kui RR eeldusvalemites.
Muutujat V sisaldav väide tähistab kõikide konkretiseeritud väidete hulka, kus
konkretiseerimise al  mõeldakse V asendamist kas konstantide või muutujaid sisaldavate
termidega.
q Kuidas unifitseerida, kui mõlemad literaalid sisaldavad muutujaid?
Minimaalse substitutsiooni reegel:
Asendamata jäetakse kõik muutujad, mil e jaoks puudub konkretiseeriv asendus.
Definitsioon (Kõige üldisem unifitseerija - mgu):
Termide t1 ja t2 kõige üldisem 
unifitseerija on asendus , mis  rahuldab   
tingimusi:
1.  on termide t1 ja t2 unifitseerija
 t1 ja t2 iga unifitseerija  korral 
leidub veel asendus , nii et  =     
st. iga termi t korral (t) = ((t))  
Märkus : mgu annab kõige vähem konkretiseeritud omavahel unifitseeruvad termid.
Lause:
Leidub algoritm mgu, mis arvutab literaalide või termide x ja y kõige üldisema unifitseerija.
Näiteid:
mgu(P(a,X), P(Y,b))
mgu(P(X, f(X)), P(f(Y), U)) mgu(L(g(X,X)), L(g(f(a), f(a))))
mgu(R(a,b), R(a,b))
Reegel: Disjunktsioonides, mil ele rakendatakse üldistatud RR reeglit, tuleb eelnevalt
asendada samanimelised muutujad.
7.1. Listid
Esitavad järjestatud elementide korteeže
List unifitseerub
• ühe muutujaga
List = [a, d, f, [s, f, [],d]]
• Listi erinevaid osi adresseerivate muutujatega, kui on mitte-tühi list
[Head| Tail ]
Head (listi pea) - listi ilmutatult viidatavad esimesed elemendid
Tail (listi saba) – ülejäänud listi elemendid
| - eraldussümbol.
1. Termi konverteerimine listiks ja vastupidi ”= ..”.
Tulemuseks list, mil e peaks on predikaadi nimi ja sabaks predikaadi argumendid.
Sorteerimispredikaadi defineerimine:
- Ordering := - Ordering := aless , kui alfabeetiline järjestamine, kus
7.2 Semantilised võrgud
Semantiline võrk (SV) on diagramm, mis esitab objekte, nende omadusi ja objektide vahelisi
seoseid . SV annab mõistete konteksti ja aitab selgitada valdkonna mõistete tähendust.
SV graafiline esitus:
- tipud: objektid ja nende omadused
- kaared (suunatud): näitab objektidevahelisi seoseid ja objektide seost omadustega
NB! Omadused, mis kehtivad objektide kohta, peavad kehtima ka kõigi tema alamobjektide
kohta (, mis seotud predikaadi ”on” (”is_a”) kaudu).
7.3 Freimid
Freime kasutatakse andmestruktuuride üldistusena, kus struktuur on paljudel andmetel
ühine, kuid elemendid on erinevat tüüpi või tüüp on täpsustamata.
Freim – abstraktne skelett, mil es on vahetatavate elementide tarvis lahtrid (slots).
Freimi iga lahter võib ol a omakorda freim, kusjuures kõik lahtrite omadused päritakse tema
alamfreimide poolt.
7.4 ”If . . then . .” reeglid ekspertsüsteemides
Võimaldavad spetsifitseerida põhjus-tagajärg seoseid ning (läbi transitiivsuse)
pikemaid põhjuslikkuse ahelaid.