1 files changed, 281 insertions, 0 deletions
diff --git a/prolog/problems/sets/intro_sl.html b/prolog/problems/sets/intro_sl.html
new file mode 100644
index 0000000..3763628
--- /dev/null
+++ b/prolog/problems/sets/intro_sl.html
@@ -0,0 +1,281 @@
+<!DOCTYPE html>
+<html lang="sl">
+<head>
+  <meta charset="utf-8" />
+  <title>Prolog: negacija in rez</title>
+  <link rel="stylesheet" type="text/css" href="../style.css" />
+</head>
+<body>
+
+<h1>Prolog: negacija in rez</h1>
+<p>
+Kot ste videli, smo konjunkcijo in disjunkcijo spoznali že takoj v prvem sklopu.
+Verjetno ste se že tedaj spraševali, kako je s tretjo, na nek način
+komplementarno, logično operacijo, to je negacijo. Tako je, načrtno smo
+zavlačevali z njeno predstavitvijo! Boste hitro videli, zakaj. No, sedaj pa je
+vendarle napočil čas, da ugriznemo še v to jabolko.
+</p>
+
+<h2>Rez (<code>!</code>)</h2>
+<p>
+Začnimo z rezom, saj ga bomo kasneje potrebovali za definicijo negacije. Rez v
+prologu imenujemo posebej cilj, ki ga označimo s klicajem (<code>!</code>). Ta
+cilj vedno uspe (v tem smislu je enak kot <code>true</code>), a ima stranski
+učinek. Le-ta je, da prepreči ostale možne alternative. Poglejmo to kar na
+primeru. Za hip si spet naložimo dejstva o družinskih drevesih iz prvega sklopa,
+da lahko na njih naredimo nekaj demonstracij.
+</p>
+
+<figure>
+  <a href="famrel.svg" target="_blank">
+    <img src="famrel.svg" />
+  </a>
+  <figcaption>Graf (gozd) družinskih relacij</figcaption>
+</figure>
+
+<pre>
+?- parent(thomas, X).
+X = william ;
+X = sally ;
+X = jeffrey ;
+no.
+</pre>
+
+<p>
+Zgornje vprašanje smo v naravnem jeziku interpretirali kot „kdo vse je otrok od
+Thomasa?“ Vidimo, da ima Thomas tri otroke. Zdaj pa bomo na različne načine
+našteli njegove vnuke in pri tem demonstrirali delovanje reza.
+</p>
+<pre>
+?- parent(thomas, X), parent(X, Y).
+X = william, Y = vanessa ;
+X = william, Y = patricia ;
+X = sally, Y = andrew ;
+X = sally, Y = melanie ;
+no.
+</pre>
+
+<p>
+To vprašanje našteje vse vnuke; kar poskusi. No, saj si sprogramiral to v prvem
+sklopu. Vseh vnukov je… štirje so!
+</p>
+<p>
+Kaj pa tole vprašanje?
+</p>
+<pre>
+?- parent(thomas, X), parent(X, Y), !.
+X = william, Y = vanessa ;
+no.
+</pre>
+
+<p>
+Oho! Klicaj (rez) je napravil svoje. Pomislimo, kaj se je zgodilo: ko je naletel
+na klicaj, je prolog zamrznil trenutno (delno) rešitev – vrednosti spremenljivk
+<code>X</code> in <code>Y</code> ter ni več dovolil drugih rešitev, čeprav smo
+videli, da obstajajo. To je navsezadnje njegova naloga.
+</p>
+<p>
+Še bolj zanimiv/poučen primer:
+</p>
+<pre>
+?- parent(thomas, X), !, parent(X, Y).
+X = william, Y = vanessa ;
+X = william, Y = patricia ;
+no.
+</pre>
+
+<p>
+Klicaj smo sedaj postavili med oba cilja. In dobili smo… samo vnuka preko prvega
+starša, torej Williama. Seveda, prolog je naletel na klicaj po tem, ko je našel
+prvo rešitev za cilj <code>parent(thomas, X)</code> in je zato zamrznil rešitev
+samo za spremenljivko <code>X</code>. Cilj <code>parent(X, Y)</code>, ki je
+sedaj v resnici <code>parent(william, Y)</code> se izvaja normalno, v smislu, da
+se generirajo (na zahtevo) vse možne rešitve za <code>Y</code>.
+</p>
+
+<h2>Uporaba reza</h2>
+<p>
+Načeloma se rezu poskušamo izogibati. Seveda pa je včasih zelo koristen za
+optimizacijo, ko odrežemo veje kar sami, ker vemo, da jih ne potrebujemo.
+Dostikrat tudi skrajša kodo – če je to res potrebno v prologu, je veliko
+vprašanje :)
+</p>
+<p>
+Kot ste videli, rez poreže rešitve (od tu mu tudi ime). To seveda dostikrat
+vpliva na prologovo „večsmernost“, ki je običajno zaželena lastnost. Rez jo
+večinoma prepreči.
+</p>
+<p>
+Glavna uporaba reza pa je pri definiciji negacije.
+</p>
+
+<h2>Negacija v prologu</h2>
+<p>
+Negacija je v prologu definirana takole: poskusim dokazati, da velja cilj
+(predikat) <code>P</code>. Če mi to ne uspe, potem rečem, da velja ne
+<code>P</code>. Ali s primerom:
+</p>
+<pre>
+?- parent(jeffrey, X).
+no.
+</pre>
+<p>
+Ta cilj odgovarja na vprašanje „ali je Jeffrey oče?“ Kot vidimo, prolog poskuša
+to dokazati, a je odgovor „no“. Zato rečemo, da velja ravno obratno: „Jeffrey ni
+oče.“ Skratka, če velja negacija v prologu, to pomeni, da prolog ni uspel
+dokazati cilja, ki ga negiramo!
+</p>
+<p>
+Natančna definicija je naslednja:
+</p>
+<pre>
+not(P) :-
+    P, !, fail
+    ;
+    true.
+</pre>
+<p>
+Kot vidiš, smo v tej definiciji uporabili rez. Preberimo logično: če velja, da
+je uspel cilj <code>P</code>, potem to rešitev zamrznemo (rez!) in rečemo „no“
+– za to poskrbi cilj <code>fail</code>, ki nikoli ne uspe.
+</p>
+<p>
+Do cilja true zaradi reza lahko pridemo samo, če <code>P</code> ne uspe in ne
+naletimo na klicaj. Kar poskusi.
+</p>
+<p>
+Še komentar o sintaksi: za negacijo lahko uporabljamo predikat <code>not</code>
+(odvisno od verzije prologa), običajno pa preprosto uporabljamo operator
+<code>\+</code>. Spodnje vprašanje pomeni: „ali Jeffrey ni starš?“
+</p>
+<pre>
+?- \+ parent(jeffrey, X).
+yes.
+</pre>
+<p>
+In še nekaj: rezultat negacije je vedno odgovor da ali ne, spremenljivkam se
+vrednosti ne priredijo. Ne pozabi, da v bistvu cilj pod negacijo ne uspe.
+</p>
+
+<h2>Primer uporabe</h2>
+<p>
+Sprogramirajmo predikat <code>count(X, L, N)</code>, ki prešteje koliko
+elementov <code>X</code> se skriva v seznamu <code>L</code> in rezultat vrne v
+<code>N</code>.
+</p>
+<p>
+Prva, naivna implementacija je naslednja. Razmišljajmo rekurzivno. V praznem
+seznamu je točno nič elementov <code>X</code>. Sicer pa imamo vsaj en element,
+to je glava seznama. Pa predpostavimo, da rekurzija lepo prešteje, koliko
+<code>X</code>-ov se skriva v repu (ki je krajši, torej si rekurzijo lahko
+privoščimo). Sedaj pa imamo dve možnosti: ali je glava enaka <code>X</code>, ali
+pa ni. V prvem primeru rezultatu rekurzije prištejemo ena, v drugem pa ne.
+</p>
+<pre>
+count(X, [], 0).        % robni pogoj: v praznem seznamu se nič ne skriva, tudi X ne ;)
+count(X, [X|T], N) :-   % prva možnost: glava je enaka X
+    count(X, T, NT),    % Hej, rekurzija, koliko X-ov se skriva v repu? Aha, NT, hvala!
+    N is NT + 1.
+count(X, [_|T], NT) :-  % druga možnost: glava ni enaka X
+    count(X, T, NT).
+</pre>
+<p>
+Videti je v redu, tudi logično se bere nekako smiselno. Pa poglejmo, kaj pravi
+prolog.
+</p>
+<pre>
+?- count(a, [a,b,c,a,a,b,b,a,d], N).
+N = 4.
+</pre>
+<p>
+Ha! Deluje! No no, ne tako hitro. Nismo poskusili dobiti vseh odgovorov. Zakaj
+pa bi jih potrebovali, boš vprašal. Jih ne, vendar nikoli ne veš, kdaj bodo
+nenadoma prišli v poštev, ko bo prolog poleg štetja počel še kaj v kombinaciji.
+In navsezadnje, saj nočeš, da vračamo najprej pravilen rezultat, potem pa…
+poglejmo kaj.
+</p>
+<pre>
+?- count(a, [a,b,c,a,a,b,b,a,d], N).
+N = 4 ;
+N = 3 ;
+N = 3 ;
+N = 2 ;
+…
+</pre>
+<p>
+Hmmm. Kako, kako pa to dobimo? Hja, pomislimo. Ena možnost je, da glava enaka
+<code>X</code>, druga pa, da ni enaka <code>X</code>. A tega nikoli nismo zares
+povedali prologu. Druga veja je <code>count(X, [_|T], NT)</code>, ki pa pove, da
+je prvi element (glava) seznama lahko karkoli. Karkoli! Torej tudi
+<code>X</code>. Obe veji si torej nista disjunktni, relacija med njima je OR in
+ne XOR, kot bi si želeli. Kako bi to naredili? Ena možnost je, da z rezom
+preprečimo drugo vejo, kadar prva uspe. Takole.
+</p>
+<pre>
+count(X, [], 0).          % robni pogoj: v praznem seznamu se nič ne skriva, tudi X ne ;)
+count(X, [X|T], N) :- !,  % prva možnost: glava je enaka X
+    count(X, T, NT),      % Hej, rekurzija, koliko X-ov se skriva v repu? Aha, NT, hvala!
+    N is NT + 1.
+count(X, [_|T], NT) :-    % druga možnost: glava ni enaka X
+    count(X, T, NT).
+</pre>
+<p>
+Kot vidiš je v tem primeru rez spremenil logični pomen programa (XOR med vejama
+namesto OR). Tudi zato se ga izogibamo, ker je to lahko nevarno – težje beremo
+program.
+</p>
+<p>
+Druga možnost je uporaba negacije. V drugi veji negiramo cilj, da mora glava
+biti enaka <code>X</code>.
+</p>
+<pre>
+count(X, [], 0).        % robni pogoj: v praznem seznamu se nič ne skriva, tudi X ne ;)
+count(X, [X|T], N) :-   % prva možnost: glava je enaka X
+    count(X, T, NT),    % Hej, rekurzija, koliko X-ov se skriva v repu? Aha, NT, hvala!
+    N is NT + 1.
+count(X, [H|T], NT) :-  % druga možnost: glava ni enaka X
+    \+ X = H,
+    count(X, T, NT).
+</pre>
+<p>
+Seveda bi negiran cilj „<code>X</code> se ne more prilagoditi H“ lahko zapisali
+z operatorjem <code>\=</code>, a smo za demonstracijo uporabili negacijo.
+</p>
+
+<h2>Za konec</h2>
+<p>
+Če se da, se tudi negacije (tako kot reza) izogibamo. Ker vsebuje rez, ima enak
+negativen vpliv na „večsmernost“. Seveda to vedno ne gre, zato pa jo imamo –
+pravim samo, da se je izogni, če se da. Kje še lahko naletiš na probleme? V
+kombinaciji negacije s spremenljivkami, ki še nimajo vrednosti. Poglej tale
+primer, ki želi odgovor na vprašanje, ali ima Thomas kakšnega sina:
+</p>
+<pre>
+?- \+ female(X), parent(thomas, X).
+no.
+</pre>
+<p>
+Kako, prosim? Prologu se je zmešalo! Saj Thomas ima kar dva sina! Ima, ima,
+ampak poglejmo, kaj smo vprašali. Mislili smo povsem logično: <code>X</code> ni
+ženska in je otrok od Thomasa. Vse lepo in prav. Aker je negacija definirana v
+prologu kot neuspeh cilja pod negacijo, je prologovo sklepanje naslednje: ali
+lahko dokažem (zadostim) cilj „<code>X</code> je ženska“? Lahko, v bazi je
+veliko žensk, izberem poljubno za <code>X</code>. Zato pa je negiran cilj
+seveda… napačen! Torej ne! Če bi stvari obrnili, tako da bi negiran cilj
+preverjali za konkretno vrednost za <code>X</code>, bi bilo vse, kot smo si
+zamislili. Takole:
+</p>
+<pre>
+?- parent(thomas, X), \+ female(X).
+X = william ;
+X = jeffrey.
+</pre>
+<p>
+Zdaj vidiš, zakaj nismo negacije uporabljali takoj od začetka. Seveda je zelo
+koristna, včasih brez nje preprosto ne gre. Vendar pa je potrebno biti previden.
+Če se trikov in problemov zavedaš, potem je tudi negacija povsem obvladljiva.
+Seveda pa, če se da, se je je najbolje izogniti.
+</p>
+
+</body>
+</html>