od ubavic » Nedelja, 22. Januar 2017, 13:29
Pozdrav.
U ovakvim zadacima cilj je napisati formulu za svaki element modela, koja je tačna samo za taj element. Formule su naravno formule predikatske logike (logike prvog reda), sastavljene od dobro poznatih veznika i kvantifikatora ([inlmath]\land,\lor,\neg,\Rightarrow,\Leftrightarrow\forall,\exists[/inlmath]). Zadatak u suštini nije težak, samo je bitno poznavanje značenja navedenih simbola predikatske logike.
Najbolje je da potražiš neku "asimetriju" u grafu koji si dobio. Na primer elementi [inlmath]a[/inlmath] i [inlmath]c[/inlmath] su specifični po tome što iz njih idu strelice ka njima samima tj. imaju petlju. Zato je pogodno da se za njih prvo napišu formule, jer se oni po tome razlikuju od ostalih elemenata. Tu se krije i mala začkoljica. Samo na osnovu osobine da je element u relaciji sa samim sobom (da ima petlju) ne možemo razlikovati [inlmath]a[/inlmath] od [inlmath]c[/inlmath]. Zbog toga moramo uvesti u igru i element [inlmath]b[/inlmath].
Element [inlmath]a[/inlmath] ćemo definisati kao element ([inlmath]x[/inlmath]) koji je u relaciji sa samim sobom, i u relaciji je sa nekim elementom ([inlmath]x_1[/inlmath]) koji je opet u relaciji sa elementom koji ima petlju ([inlmath]x_2[/inlmath]). Dakle formula za [inlmath]a[/inlmath] bi izgledala ovako:
[dispmath]\Phi_a(x)=q(x,x)\land\exists x_1\exists x_2\bigl(q(x,x_1)\land q(x_1,x_2)\land q(x_2,x_2)\land\neg q(x_1,x_1)\bigr)[/dispmath] Formula [inlmath]\neg q(x_1,x_1)[/inlmath] nam govori da [inlmath]x_1[/inlmath] nije u relaciji sa samim sobom tj. [inlmath]x_1[/inlmath] ne može biti [inlmath]a[/inlmath]. Inače bi i trojka [inlmath](x_1,x_2,x_3)=(a,a,a)[/inlmath], ili [inlmath](c,c,c)[/inlmath], zadovoljavala formulu. U zavisnosti kako ste definisali jezik logike prvog reda, moguće je (ili nije) koristiti znak jednakosti, pa se i sličan uslov može zapisati [inlmath]\neg x=x_1[/inlmath].
Slično smo mogli da definišemo [inlmath]c[/inlmath]. Međutim za tim sada nema potrebe jer imamo element [inlmath]a[/inlmath] koji možemo iskoristiti za definisanje ostalih elemenata.
Element [inlmath]b[/inlmath] je jedini takav da iz [inlmath]a[/inlmath] ide strelica ka njemu, a pritom on sam nije [inlmath]a[/inlmath]!. Dakle za [inlmath]b[/inlmath] bismo mogli da definišemo ovakvu formulu.
[dispmath]\Phi_b(x)=\exists x_1\bigl(\Phi_a(x_1)\land q(x_1,x)\land\neg q(x,x)\bigr)[/dispmath] Element [inlmath]c[/inlmath] definišemo kao (sada nema potrebe za dodatnim uslovom):
[dispmath]\Phi_c(x)=\exists x_1\bigl(\Phi_b(x_1)\land q(x_1,x)\bigr)[/dispmath] I slično možemo definisati i ostale elemente...
Naravno ovo nije jedino rešenje.