Zgled 1. Nepridipravi so razbili vhodna vrata FMF. Glavni osumljenci so študenti Ana, Bor in Cveto. Ko jih vprašamo, kdo je kriv, odgovorijo z naslednjimi izjavami:

• Ana: “Bor je kriv, Cveto pa ne.”

• Bor: “Če je kriva Ana, je kriv tudi Cveto.”

• Cveto: “Jaz nisem kriv, toda vsaj eden od drugih dveh je kriv.”

Pri predmetu se bomo naučili, kako lahko na sistematičen način odkrijemo, kdo je lagal, če krivi lažejo, nedolžni pa govorijo resnico.

Zgled 2. Graf je diskretna struktura, pri kateri dano množico vozlišč povežemo s povezavami. Z grafi lahko opišemo veliko različnih vrst omrežij, na primer internetno omrežje, omrežje prijateljskih povezav na Facebooku, omrežja veriženja blokov (kriptovalute) …

Konkreten graf na spodnji sliki se imenuje Petersenov graf. Ta graf bomo tekom predmeta večkrat srečali. Na koncu predmeta bomo znali dokazati, da se tega grafa ne da narisati v ravnini, brez da bi se vsaj dve povezavi sekali.

Zgled 1.1.

• Ena in ena je tri. Lažna izjava.

• Ena in ena je dve. Resnična izjava.

• Koliko je ena in ena? Ni izjava.

• Pojdimo na kavo! Ni izjava.

Zgled 1.2.

• Vreme je lepo. Osnovna izjava.

• Špela gre v hribe. Osnovna izjava.

• Vreme je lepo in Špela gre v hribe. Sestavljena izjava.

• Če je vreme lepo, potem gre Špela v hribe. Sestavljena izjava.

• Špela ne gre v hribe. Sestavljena izjava.

Zgled 1.3.

• Primer izjavnega veznika reda \(1\) je negacija. Simbol za ta veznik je \(\lnot\). Če je \(p\) izjava, njeno negacijo označimo kot \(\lnot p\) in preberemo kot ne \(p\) ali kot ni res, da velja \(p\). Negacija \(1\)-terici \(0\) priredi vrednost \(1\), \(1\)-terici \(1\) pa priredi vrednost \(0\).

  Resničnostna tabela negacije

  \(p\)	\(\lnot p\)
  0	1
  1	0

• Oglejmo si nekaj pomembnih dvomestnih izjavnih veznikov. Njihovi predpisi so zbrani v tabeli.

  • Konjunkcija izjav \(p\) in \(q\) ima simbol \(p \land q\), kar preberemo kot \(p\) in \(q\).

  • Disjunkcija izjav \(p\) in \(q\) ima simbol \(p \lor q\), kar preberemo kot \(p\) ali \(q\).

  • Implikacija izjav \(p\) in \(q\) ima simbol \(p \Rightarrow q\), kar preberemo kot če \(p\), potem \(q\) ali kot iz \(p\) sledi \(q\) ali kot \(p\) je zadosten pogoj za \(q\) ali kot \(q\) je potreben pogoj za \(p\).

  • Ekvivalenca izjav \(p\) in \(q\) ima simbol \(p \Leftrightarrow q\), kar preberemo kot \(p\) natanko tedaj, ko \(q\) ali kot \(p\), če in samo če \(q\) ali kot \(p\) je ekvivalentno \(q\).

  Resničnostna tabela nekaterih pomembnih dvomestnih izjavnih veznikov

  \(p\)	\(q\)	\(p \land q\)	\(p \lor q\)	\(p \Rightarrow q\)	\(p \Leftrightarrow q\)
  1	1	1	1	1	1
  1	0	0	1	0	0
  0	1	0	1	1	0
  0	0	0	0	1	1

• Izjavni veznik reda \(0\) je funkcija iz množice urejenih \(0\)-teric ničel in enic. Obstaja natanko ena taka \(0\)-terica, in sicer prazna \(0\)-terica. Izjavni veznik reda \(0\) je torej natanko določen s sliko te \(0\)-terice, za kar imamo dve možnosti, \(0\) ali \(1\).

  • Izjavni veznik reda \(0\), ki ima vselej resničnostno vrednost \(0\), imenujemo 0 in preberemo kot lažna izjava.

  • Izjavni veznik reda \(0\), ki ima vselej resničnostno vrednost \(1\), imenujemo 1 in preberemo kot resnična izjava.

  Izjavnima veznikoma reda \(0\) pravimo tudi izjavni konstanti.

Zgled 1.4. Naj bodo \(p,q,r\) izjavne spremenljivke. Tvorimo lahko izjavne izraze \((p \Rightarrow q)\), \((\lnot r)\), \(((p \Rightarrow q) \land (\lnot r))\), …

Zgled 1.5.

• Izjavni izraz \((p \Rightarrow (q \land r))\) pišemo krajše kot \(p \Rightarrow q \land r\).

• Izraz \(p \Rightarrow q \Rightarrow r \Rightarrow s\) je okrajšava za izjavni izraz \((((p \Rightarrow q) \Rightarrow r) \Rightarrow s)\).

• Izraz \(p \lor \lnot q \Leftrightarrow r \Rightarrow q\) je okrajšava za izjavni izraz \((( p \lor (\lnot q)) \Leftrightarrow (r \Rightarrow p))\).

Zgled 1.6. Naj bodo \(p,q,r\) izjavne spremenljivke in naj bo \(f(p,q,r) = (p \Rightarrow q) \land \lnot r\) izjavni izraz. Izračunamo lahko resničnostno tabelo tega izraza in na ta način lahko na \(f\) gledamo kot na izjavni veznik reda \(3\).

Zgled 1.7.

• Izjavna izraza \(1\) in \(p \lor \lnot p\) sta tavtologiji.

• Izjavna izraza \(0\), \(p \land \lnot p\) sta protislovji.

• Izračunajmo resničnostne tabele izjavnih izrazov \(p \Rightarrow q \Leftrightarrow \lnot p \lor q\), \(p \land \lnot (q \Rightarrow p)\) in \(p \land (\lnot q \lor p)\).

  Resničnostne tabele treh izjavnih izrazov

  \(p\)	\(q\)	\(p \Rightarrow q \Leftrightarrow \lnot p \lor q\)	\(p \land \lnot (q \Rightarrow p)\)	\(p \land (\lnot q \lor p)\)
  1	1	1	0	1
  1	0	1	0	1
  0	1	1	0	0
  0	0	1	0	0

  Vidimo, da je prvi izraz tavtologija, drugi protislovje, tretji pa kontingenten.

  Domača naloga 1.1. Prepričaj se, da je resničnostna tabela izjavnega izraza \(p \land (\lnot q \lor p)\) enaka resničnosti tabeli izjavnega izraza \(p\). Sklepaj, da je izjava \(p \land (\lnot q \lor p) \Leftrightarrow p\) tavtologija. Na podoben način se prepričaj, da je izraz \(p \Rightarrow q \Leftrightarrow \lnot q \Rightarrow \lnot p\) tavtologija.

Zgled 1.8. Velja \(p \Rightarrow q \sim \lnot p \lor q \sim \lnot q \Rightarrow \lnot p\) in \(p \land (\lnot q \lor p) \sim p\).

Zgled 1.9. Velja \[p \land (\lnot q \lor p) \Rightarrow (\lnot q \Rightarrow \lnot p) \sim p \Rightarrow (p \Rightarrow q).\]

Zgled 1.10. Izjavni izraz iz zadnjega zgleda lahko z naštetimi zakoni poenostavimo do \[p \Rightarrow (p \Rightarrow q) \sim \lnot p \lor (\lnot p \lor q) \sim (\lnot p \lor \lnot p) \lor q \sim \lnot p \lor q \sim p \Rightarrow q.\]

Zgled 1.11. Naj bo izjavni izraz \(A\) dan z resničnostno tabelo \(T\).

Iskani izjavni izraz \(D\) mora biti resničen natanko v 2., 6. in 8. vrstici tabele \(T\). To je res natanko tedaj, ko velja \(p \land q \land \lnot r\) ali \(\lnot p \land q \land \lnot r\) ali \(\lnot p \land \lnot q \land \lnot r\). Torej lahko vzamemo preprosto \[D = (p \land q \land \lnot r) \lor (\lnot p \land q \land \lnot r) \lor (\lnot p \land \lnot q \land \lnot r)\] in res velja \(D \sim A\). Dobljeni izjavni izraz \(D\) lahko še nekoliko poenostavimo.

Zgled 1.12. V zadnjem zgledu je \(\mathop{\mathrm{DNO}}(A) = D\).

Zgled 1.13. Naj bo \(T\) resničnostna tabela izjavnega izraza \(A\) iz predzadnjega zgleda. Ta tabela je lažna v vrsticah \(1,3,4,5,7\). Sestavimo izjavni izraz \(K\), ki bo lažen natanko v teh vrsticah. To je enakovredno zahtevi, da je \(K\) resničen natanko tedaj, ko nismo v nobeni od vrstic \(1,3,4,5,7\). Slednjo zahtevo lahko izrazimo kot konjunkcijo osnovnih disjunkcij vrstic \(1,3,4,5,7\), se pravi kot \[K = (\lnot p \lor \lnot q \lor \lnot r) \land (\lnot p \lor q \lor \lnot r) \land (\lnot p \lor q \lor r) \land (o \lor \lnot q \lor \lnot r) \land (p \lor q \lor \lnot r).\] Tako sestavljenemu izravnemu izrazu \(K\) pravimo konjunktivna normalna oblika izraza \(A\), krajše \(\mathop{\mathrm{KNO}}(A)\). Sorodno kot za disjunktivno normalno obliko se prepričamo, da velja \(\mathop{\mathrm{KNO}}(A) \sim A\).

Zgled 1.14. Opazujmo naslednje zaporedje izjav.

\(p_1\):

Če je ta žival ptič, potem ima krila.

\(p_2\):

Ta žival nima kril.

\(z\):

Ta žival ni ptič.

Imamo torej sklep \(p_1, p_2, z\). Ta sklep lahko zapišemo nekoliko bolj natančno z upoštevanjem sestavljene strukture izjav v sklepu. Uvedimo izjavi \(p\) in \(q\) kot:

\(p\):

Ta žival je ptič.

\(q\):

Ta žival ima krila.

Sklep \(p_1, p_2, z\) lahko torej zapišemo v obliki \(p \Rightarrow q, \ \lnot q, \ \lnot p\).

Zgled 1.15. Sklep iz zadnjega zgleda smo zapisali v obliki \(p \Rightarrow q, \ \lnot q, \ \lnot p\). Če pri tem gledamo na \(p\) in \(q\) kot na izjavni spremenljivki (in ne kot oznaki za konkretne izjave), se lahko vprašamo o veljavnosti sklepa. V ta namen sestavimo resničnostno tabelo vseh izjavnih izrazov v sklepu.

Edini nabor izjavnih spremenljivk, pri katerih sta resnični obe predpostavki sklepa, je nabor \((p,q)=(0,0)\). Pri tem naboru je resničen tudi zaključek sklepa. Sklep je torej veljaven, se pravi \(p \Rightarrow q, \ \lnot q \models \lnot p\).

Zgled 1.16. Ali je sklep \[p \Rightarrow q, \ p \lor r, \ q \Rightarrow s, \ r \Rightarrow t, \ \lnot s \models t\] veljaven? Ta sklep vsebuje \(5\) izjavnih spremenljivk, zato bi za preverjanje veljavnosti morali sestaviti resničnostno tabelo z \(2^5 = 32\) vrsticami.

Zgled 1.17. S pomočjo izreka o naravni dedukciji utemeljimo veljavnost sklepa iz zadnjega zgleda.

Zgled 1.18. Opazujmo naslednji sklep.

\(p_1\):

Ta žival ima krila ali pa ni ptič.

\(p_2\):

Če je ta žival pritč, potem leže jajca.

\(p_3\):

Ta žival nima kril.

\(z\):

Torej ta žival ne leže jajc.

Ta sklep lahko zapišemo nekoliko bolj natančno, če uvedemo izjave \(p,q,r\) kot:

\(p\):

Ta žival ima krila.

\(q\):

Ta žival je ptič.

\(r\):

Ta žival leže jajca.

Sklep lahko torej zapišemo na naslednji način: \[p \lor \lnot q, \ q \Rightarrow r, \ \lnot p \models \lnot r.\]

Poiščimo protiprimer. Želimo, da so resnične vse predpostavke, zaključek pa lažen. Vzeti moramo torej \(r = 1\) in \(p = 0\), od koder iz prve predpostavke dobimo še \(q = 0\). S to izbiro je tudi druga predpostavka resnična. Nabor \(p = 0, q = 0, r = 1\) je torej protiprimer, ki opazi, da sklep ni pravilen.

Če to prevedemo nazaj v človeški jezik, protiprimer torej predstavlja žival, ki nima kril, ni ptič in leže jajca. Konkretna taka žival je na primer kača ali krokodil.

Zgled 1.19. Dokažimo veljavnost sklepa \[p \Rightarrow q \lor r, \ \lnot r \models p \Rightarrow q.\] Ker ima zaključek obliko implikacije, lahko uporabimo pogojni sklep.

Zgled 1.20. Dokažimo veljavnost sklepa \[p \Rightarrow \lnot (q \Rightarrow r), \ q \land s \Rightarrow r, \ s \models \lnot p.\] Ker ima zaključek obliko negacije, še posebej radi uporabimo sklepanje s protislovjem.

Zgled 1.21. Dokažimo veljavnost sklepa \[p \Rightarrow r, \ q \Rightarrow r, \ p \lor q \models r.\] Tretja predpostavka ima obliko disjunkcije, zato lahko sklep dokažemo s pomočjo analize primerov.

Zgled 2.1. Oglejmo si naslednji sklep, zapisan v slovenščini.

\(p_1\):

Vsak zajec ljubi korenje.

\(p_2\):

Feliks je zajec.

\(z\):

Torej Feliks ljubi korenje.

V izjavnem računu ta sklep zapišemo kot \(p_1, p_2 \models z\). Seveda pa ta sklep v izjavnem računu ni veljaven, protiprimer je namreč nabor \(p_1 = 1, p_2 = 1, z = 0\).

Kljub temu se zdi, da je ta sklep v slovenščini vsekakor pravilen. Predikatni račun je nadgradnja izjavnega računa, v katerem izjavne spremeljivke \(p_1, p_2, z\) obravnavamo nekoliko podrobneje, tako da bo ta sklep pravilen tudi v tem novem računu.

Uvedimo naslednje oznake:

\(Z(x)\):

\(x\) je zajec.

\(K(x)\):

\(x\) ljubi korenje.

\(a\):

Feliks

\(\forall x\):

za vsak \(x\)

S temi oznakami lahko sklep zapišemo bolj natančno takole:

\(p_1\):

\(\forall x \colon (Z(x) \Rightarrow K(x))\)

\(p_2\):

\(Z(a)\)

\(z\):

\(K(a)\)

V predikatnem jeziku bomo torej poleg izjavnih vezikov in ločil iz izjavnega računa imeli individualne spremenljivke (\(x\)), individualne konstante (\(a\)), predikate (\(Z\), \(K\)) in univerzalni kvantifikator (\(\forall\)).

Zgled 2.2. Prevedimo nekaj izjav iz slovenščine v nov jezik predikatnega računa, kot smo to storili v zadnjem zgledu. Izjave so naslednje:

1. Vsi gasilci so hrabri.

2. Nekateri gasilci so hrabri.

3. Nekateri gasilci niso hrabri.

4. Noben gasilec ni hraber.

Uvedimo naslednje oznake:

\(G(x)\):

\(x\) je gasilec.

\(H(x)\):

\(x\) je hraber.

\(\exists x\):

obstaja \(x\)

Izjave v slovenščini lahko s temi oznakami zapišemo na naslednji način:

1. \(\forall x \colon (G(x) \Rightarrow H(x))\)

2. \(\exists x \colon (G(x) \land H(x))\)

3. \(\exists x \colon (G(x) \land \lnot H(x))\)

4. \(\forall x \colon (G(x) \Rightarrow \lnot H(x))\)

Tukaj smo videli še en simbol kvantifikacije, ki ga bomo imeli v predikatnem računu, in sicer eksistenčni kvantifikator (\(\exists\)).

Zgled 2.3. Storimo podobno kot v zadnjih dveh zgledih še za naslednjo matematično izjavo. Evklidov izrek nam pove, da obstaja neskončno mnogo praštevil.

Če želimo to izjavo zapisati na podoben način kot prejšnje izjave v tem poglavju, nam bo v pomoč, če jo prepišemo v nekoliko drugačno obliko, in sicer kot izjavo, da obstajajo poljubno velika praštevila. Še vedno ni jasno, kako bi izrazili del izjave, ki pravi, da obstajajo poljubno velika števila, zato bodimo še nekoliko bolj eksplicitni glede tega dela izjave. Evklidov izrek je ekvivalenten izjavi, da za vsako naravno število obstaja večje naravno število, ki je praštevilo. To zadnjo izjavo pa lahko zapišemo v predikatnem računu.

Uvedimo naslednje oznake:

\(P(x)\):

\(x\) je praštevilo.

\(V(x,y)\):

\(x\) je večje od \(y\).

V tem zgledu so naše spremenljivke \(x\) iz množice naravnih števil, v prejšnjih zgledih pa so bile iz množice živali. Pomembno je, da se na začetku dogovorimo o področju pogovora oziroma domeni, saj izjave, ki jih zapišemo, morda v drugi domeni pomenijo čisto nekaj drugega.

Evklidov izrek lahko nazadnje zapišemo v predikatnem računu na naslednji način: \[\forall x \exists y \colon (V(y,x) \land P(y)).\]

Tukaj smo srečali predikat \(V\), ki je nekoliko drugačen od predikatov, ki smo jih videli do sedaj. Predikat \(V\) je namreč dvomesten (ima dva parametra), drugi predikati pa so bili vsi enomestni.

Zgled 2.4. V prejšnjem zgledu smo govorili o praštevilih, za katere smo uvedli predikat \(P\). Seveda pa bi lahko samo dejstvo, da je spremenljivka \(x\) praštevilo, se pravi da je izjava \(P(x)\) resnična, podrobneje opisali v predikatnem računu. To storimo v tem zgledu.

Po definiciji je naravno število \(n\) praštevilo, če in samo če ima natanko dva naravna delitelja. Uvedimo naslednje oznake:

\(f(x,y)\):

produkt \(x\) in \(y\)

\(E(x,y)\):

\(x\) je enak \(y\).

Definicijo predikata \(P\) lahko zapišemo na naslednji način: \[\forall x \colon \left( P(x) \Leftrightarrow V(x,1) \land \forall u \forall v \colon ( E(x, f(u,v)) \Rightarrow E(u,1) \land E(v,1) ). \right)\]

Tukaj smo naleteli še na zadnji fenomen, ki ga bomo imeli v predikatnem računu, in sicer je to funkcijski simbol \(f\), ki iz danih števil izračuna njun produkt.

Zgled 2.5. Naj bo \(a\) individualna konstanta, \(x,y\) individualni spremenljivki, \(f\) enomesten funkcijski simbol, \(g\) dvomesten funkcijski simbol. Tedaj so \[x, \ y, \ a, \ f(x), \ f(a), \ f(f(a)), \ g(x,f(f(y)))\] termi. Tretji, peti in šesti izmed teh so zaprti termi.

Zgled 2.6. V zgledih na začetku tega poglavja smo srečali naslednje izjavne formule: \[Z(x), \ K(x), \ Z(a), \ K(a), \ \lnot H(x), \ \forall x \colon (G(x) \Rightarrow H(x)), \ \forall x \exists y \colon (V(y,x) \land P(x)).\]

Zgled 2.7. Naslednje izjavne formule so zaprte: \[P(a), \ \forall x \colon P(x), \ \forall x \exists y \colon V(x,y).\] Naslednje izjavne formule pa niso zaprte: \[P(x), \ \exists y \colon V(x,y), \ \forall x \colon (V(x,y) \Rightarrow \exists P(y)).\]

Zgled 2.8. Naj bo \(\phi(x) = \exists y \colon R(x,y)\) in \(t = f(a)\). Potem je \(\phi(t) = \exists y \colon R(f(a), y)\).

Zgled 2.9. Naj bo \[\mathcal{F}= \{ P(a), P(x), \forall x \colon P(x), P(f(a,b)) \}\] množica izjavnih formul. Da lahko te formule interpretiramo, moramo izbrati neko intepretacijo. Vzemimo tole intepretacijo \(I\): \[D = \mathbf{N}, \ \bar a = 2, \ \bar b = 3, \ \bar P = \mathbf{P}, \ \bar f(x,y) = 2x + y,\] kjer je \(\mathbf{P}\) množica praštevil. V tej interpretaciji term \(\overline{f(a,b)}\) torej intepretiramo kot \[\overline{f(a,b)} = \bar f (\bar a, \bar b) = 2 \bar a + \bar b = 7.\] Oglejmo si pomene izjavnih formul v \(\mathcal{F}\) v interpretaciji \(I\).

Zgled 2.10. Opazujmo izjavno formulo \(\phi = \forall x \exists y \colon R(x,y)\). Poglejmo si nekaj različnih interpretacij te formule.

Zgled 2.11. Naj bosta \(P\) in \(Q\) enomestna predikata. Opazujmo izjavno formulo \[\phi = \forall x \colon P(x) \lor \forall x \colon Q(x) \Rightarrow \forall x \colon (P(x) \lor Q(x)).\] Prepričajmo se, da je \(\phi\) logično veljavna formula.

V ta namen moramo dokazati, da za vsako interpretacijo \(I\) velja \(I \models \bar \phi\). Naj bo torej \(I\) poljubna interpretacija. V tej interpretaciji moramo torej dokazati, da je izjava \(\bar \phi\) veljavna, kar je enakovredno veljavnosti sklepa \(\models \bar \phi\), se pravi veljavnosti sklepa \[\models \forall x \colon \bar P(x) \lor \forall x \colon \bar Q(x) \Rightarrow \forall x \colon (\bar P(x) \lor \bar Q(x)).\] Zaključek tega sklepa ima obliko implikacije, zato lahko uporabimo pogojni sklep. Dokazati moramo torej veljavnost sklepa \[\forall x \colon \bar P(x) \lor \forall x \colon \bar Q(x) \models \forall x \colon (\bar P(x) \lor \bar Q(x)).\] Predpostavka tega sklepa ima obliko disjunkcije, zato lahko uporabimo analizo primerov.

1. Predpostavimo \(\forall x \colon \bar P(x)\). Dokazati želimo, da je izjava \(\forall x \colon (\bar P(x) \lor \bar Q(x))\) resnična. V ta namen izberimo poljuben \(x_0 \in D\). Po predpostavki za vsak \(x\) iz \(D\) velja \(\bar P(x)\), zato v posebnem to velja za element \(x_0\), se pravi da je izjava \(\bar P(x_0)\) resnična. Od tod sledi, da je resnična tudi izjava \(\bar P(x_0) \lor \bar Q(x_0)\). Ker je bil \(x_0\) poljuben element iz \(D\), smo s tem premislili, da je izjava \(\forall x \colon (\bar P(x) \lor \bar Q(x))\) resnična. To je bil naš cilj, zato je sklep v tem primeru veljaven.

2. Predpostavimo \(\forall x \colon \bar Q(x)\). Kot zgoraj želimo dokazati, da je izjava \(\forall x \colon (\bar P(x) \lor \bar Q(x))\) resnična. Dokaz je povsem analogen tistemu iz prejšnje točke, le \(P\) in \(Q\) zamenjamo med sabo.

S tem smo dokazali veljavnost sklepa in torej veljavnost \(I \models \bar \phi\). Ker je bila interpretacija \(I\) poljubna, je torej \(\phi\) res logično veljavna formula.

Zgled 2.12. Naj bosta \(P\) in \(Q\) enomestna predikata. Opazujmo izjavno formulo \[\psi = \forall x \colon (P(x) \lor Q(x)) \Rightarrow \forall x \colon P(x) \lor \forall x \colon Q(x).\] Prepričajmo se, da \(\psi\) ni logično veljavna.

V ta namen zadošča poiskati neko interpretacijo \(I\), v kateri \(\psi\) ni resnična. Možnosti za to je veliko. Vzamemo lahko naslednjo interpretacijo: \[D = \mathbf{N}, \ \bar P = \{ 2 n \mid n \in \mathbf{N}\}, \ \bar Q = \{ 2n - 1 \mid n \in \mathbf{N}\}.\] Velja \(\psi = \psi_1 \Rightarrow \psi_2\), kjer je \[\psi_1 = \forall x \colon (P(x) \lor Q(x)), \ \psi_2 = \forall x \colon P(x) \lor \forall x \colon Q(x).\] V interpretaciji \(I\) je izjava \(\bar \psi_1\) enakovredna izjavi, da je vsako naravno število sodo ali liho, izjava \(\bar \psi_2\) pa je enakovredna izjavi, da so vsa naravna števila soda ali pa so vsa naravna števila liha. Prva od teh dveh izjav je resnična, druga pa je lažna. V interpretaciji \(I\) je zato \(\bar \psi_1 \Rightarrow \bar \psi_2\) lažna izjava, torej je \(\bar\psi\) lažna v \(I\). Izjavna formula \(\psi\) torej res ni logično veljavna.

Zgled 2.13. Naj bo \(R\) dvomestni predikat. Opazujmo izjavno formulo \[\chi = \exists y \forall x \colon (R(x,y) \Leftrightarrow \lnot R(x,x)).\] Prepričajmo se, da je \(\chi\) protislovna izjavna formula.

V ta namen moramo dokazati, da za vsako interpretacijo \(I\) velja, da je izjava \(\bar \chi\) lažna v \(I\). Naj bo torej \(I\) poljubna interpretacija. Dokazati želimo veljavnost sklepa \[\models \lnot \left( \exists y \forall x \colon (\bar R(x,y) \Leftrightarrow \lnot \bar R(x,x)) \right).\] Ker ima zaključek obliko negacije, lahko uporabimo sklepanje s protislovjem. Predpostavimo torej, da je v interpretaciji \(I\) izjava \(\lnot \bar \chi\) lažna, se pravi da je \(\bar \chi\) resnična. Dokazati želimo protislovje \(0\). Po predpostavki o resničnosti \(\bar \chi\) obstaja nek \(y_0 \in D\), za da je izjava \[\forall x \colon (\bar R(x, y_0) \Leftrightarrow \lnot \bar R(x,x))\] resnična. Torej za vsak \(x\) iz \(D\) velja \(\bar R(x, y_0) \Leftrightarrow \lnot \bar R(x,x)\). V posebnem to velja za element \(y_0\), se pravi da je izjava \(\bar R(x_0, y_0) \Leftrightarrow \lnot \bar R(x_0,x_0)\) resnična. Ampak zadnja izjava je po izjavnem računu enakovredna \(0\). Na ta način smo izpeljali, da je \(0\) resnična izjava. To je lažno, zato smo izpeljali \(0\), kar je bil naš cilj dokazovanja s protislovjem. Izjava \(\lnot \bar \chi\) je torej v interpretaciji \(I\) resnična, kar pomeni, da \(\chi\) ni resnična v \(I\). Ker je bila \(I\) poljubna interpretacija, smo se s tem prepričali, da je \(\chi\) protislovna izjavna formula.

Zgled 2.14. Za vsako izjavno formulo \(\phi\) obstaja enakovredna formula \(\psi\), pri kateri stojijo vsi kvantifikatorji na začetku formule. Rečemo, da je \(\psi\) v preneksni obliki. Kako ta transformacija deluje, si oglejmo na dveh konkretnih primerih.

Opazujmo najprej izjavno formulo \[\lnot \forall x \exists y \colon R(x,y).\] S pomočjo negacije kvantificirane formule izpeljemo, da je ta izjavna formula enakovredna formuli \[\exists x \colon (\lnot \exists y \colon R(x,y)) \sim \exists x \forall y \colon \lnot R(x,y),\] slednja pa je v preneksni obliki.

Oglejmo si zdaj še izjavno formulo \[\exists x \colon P(x) \land \exists x \colon Q(x).\] Spremenljivki \(x\) v obeh delih konjunkcije sta neodvisni, zato lahko za večjo jasnost v drugem delu to spremenljivko preimenujemo in dobimo enakovredno izjavno formulo \[\exists x \colon P(x) \land \exists y \colon Q(y).\] Zdaj lahko uporabimo distributivnost kvantifikatorjev glede na konjunkcijo, da dobimo \[\exists x \colon ( P(x) \land \exists y \colon Q(y) ) \sim \exists x \colon ( \exists y \colon Q(y) \land \colon P(x) ).\] Slednja formula je enakovredna \[\exists x \exists y \colon (Q(y) \land P(x)),\] ki je v preneksni obliki.

Zgled 2.15. Dokažimo veljavnost sklepa \[P(a), \ \forall x \colon (P(x) \Rightarrow Q(x)) \models Q(a).\] Dokazati torej želimo, da je formula \[P(a) \land \forall x \colon (P(x) \Rightarrow Q(x)) \Rightarrow Q(a)\] logično veljavna.

V ta namen na bo \(I\) poljubna interpretacija. Dokažimo resničnost izjave \[\bar P( \bar a) \land \forall x \colon (\bar P(x) \Rightarrow \bar Q(x)) \Rightarrow \bar Q(\bar a).\] Za to lahko uporabimo pogojni sklep. Predpostavimo, da je resnična izjava \[\bar P( \bar a) \land \forall x \colon (\bar P(x) \Rightarrow \bar Q(x))\] Dokazati želimo, da je resnična tudi izjava \(\bar Q(\bar a)\).

Najprej na predpostavki uporabimo poenostavitev. Resnični sta torej izjavi \[\bar P( \bar a), \ \forall x \colon (\bar P(x) \Rightarrow \bar Q(x)).\] Torej je za vsak \(x_0 \in D\) resnična izjava \(P(x_0) \Rightarrow Q(x_0)\). V posebnem to velja za \(x_0 = \bar a\), zato je izjava \(\bar P(\bar a) \Rightarrow \bar Q(\bar a)\) resnična. Ker je resnična tudi izjava \(\bar P( \bar a)\), lahko uporabimo modus ponens. Sledi, da je resnična tudi izjava \(\bar Q(\bar a)\). S tem je dokaz zaključen.

Res torej velja \[I \models \bar P( \bar a) \land \forall x \colon (\bar P(x) \Rightarrow \bar Q(x)) \Rightarrow \bar Q(\bar a).\] Ker je bila interpretacija \(I\) poljubna, smo s tem dokazali veljavnost sklepa \[P(a), \ \forall x \colon (P(x) \Rightarrow Q(x)) \models Q(a).\]

V posebnem je veljaven sklep, ki smo ga videli na začetku tega poglavja in ki nas je motiviral k definiciji predikatnega računa.

Zgled 2.16. Dokažimo veljavnost sklepa \[\exists x \colon P(x), \ \forall x \colon (P(x) \Rightarrow \lnot Q(x) \lor \forall y \colon R(y) \models \exists x \colon (Q(x) \Rightarrow R(x)).\] V ta namen naj bo \(I\) poljubna interpretacija. Zopet lahko uporabimo pogojni sklep in predpostavimo, da sta resnični izjavi \[\exists x \colon \bar P(x), \ \forall x \colon (\bar P(x) \Rightarrow \lnot \bar Q(x) \lor \forall y \colon \bar R(y).\] Dokazati želimo resničnost izjave \(\exists x \colon (\bar Q(x) \Rightarrow \bar R(x))\), ki trdi, da obstaja element v \(D\) z neko posebno lastnostjo.

Kako najti ta element? Uporabimo lahko prvo predpostavko, po kateri obstaja element \(\bar a \in D\), da je izjava \(\bar P(\bar a)\) resnična. Hkrati po drugi predpostavki za vsak \(x_0 \in D\) velja \[\bar P(x_0) \Rightarrow \lnot \bar Q(x_0) \lor \forall y \colon \bar R(y).\] V posebnem to velja za \(x_0 = \bar a\), zato je resnična izjava \[\bar P(\bar a) \Rightarrow \lnot \bar Q(\bar a) \lor \forall y \colon \bar R(y).\] Ker je po predpostavki izjava \(\bar P(\bar a)\) resnična, lahko uporabimo modus ponens in sklenemo, da je resnična tudi izjava \[\lnot \bar Q(\bar a) \lor \forall y \colon \bar R(y).\] Zdaj lahko uporabimo analizo primerov.

1. Predpostavimo, da je resnična izjava \(\lnot \bar Q(\bar a)\). Uporabimo pridružitev in sklenemo, da je resnična izjava \[\lnot \bar Q(\bar a) \lor \bar R(\bar a) \sim \bar Q(\bar a) \Rightarrow \bar R(\bar a)\]

2. Predpostavimo, da je resnična izjava \(\forall y \colon \bar R(y)\). Torej za vsak \(y_0 \in D\) velja \(\bar R(y_0)\). V posebnem to velja za \(y_0 = \bar a\). Torej je resnična izjava \(\bar R(\bar a)\). Uporabimo pridružitev in sklenemo, da je resnična izjava \[\lnot \bar Q(\bar a) \lor \bar R(\bar a) \sim \bar Q(\bar a) \Rightarrow \bar R(\bar a).\]

Z analizo primerov smo zaključili, da je resnična izjava \[\bar Q(\bar a) \Rightarrow \bar R(\bar a).\] Torej je resnična tudi izjava \[\exists x \colon ( \bar Q(x) \Rightarrow \bar R(x) ),\] kar smo ravno želeli dokazati.

Zgled 3.1.

• Naj bo \(A = \{ 1,2,3,4 \}\). V tej množici imamo relacijo \[R = \{ (1,2), (2,3), (3,1), (3,3), (3,4) \} \subseteq A \times A.\] To relacijo lahko predstavimo grafično z grafom relacije. Elementi množice \(A\) so vozlišča, vozlišči \(a\) in \(b\) pa povežemo s puščico od \(a\) do \(b\), če je \((a,b) \in R\).

  

• Naj bo \(A = \mathbf{N}_0\) in \(R\) relacija, podana kot \[R = \{ (x,y) \in \mathbf{N}_0 \times \mathbf{N}_0 \mid \exists z \in \mathbf{N}_0 \colon x + z = y \}.\] Ta relacija \(R\) predstavlja relacijo \(\leq\) na množici \(\mathbf{N}_0\), se pravi \((x,y) \in R \Leftrightarrow x \leq y\).

• V vsaki množici \(A\) imamo naslednje relacije:

  • \(R = \emptyset \subset A \times A\). To je prazna relacija. V tej relaciji noben element množice \(A\) ni v relaciji z nobenim drugim.

  • \(R = A \times A \subseteq A \times A\). To je univerzalna relacija. V tej relaciji je vsak element množice \(A\) v relaciji z vsakim drugim.

  • \(R = \{ (x,x) \mid x \in A \} \subseteq A \times A\). To je relacija enakosti. Zanjo uporabljamo oznako \(id_A\). V tej relaciji je vsak element množice \(A\) v relaciji le s sabo.

Zgled 3.2.

• Naj bo \(A = \{ 1,2,3,4 \}\) in \(R = \{ (1,3), (2,2), (4,3) \}\). V tem primeru je \(\mathcal{D}_R = \{1,2,3\}\) in \(\mathcal{Z}_R = \{2,3\}\).

• Naj bo \(A = \mathbf{N}_0\) in \[R = \{ (x,y) \in \mathbf{N}_0 \times \mathbf{N}_0 \mid \exists z \in \mathbf{N}_0 \colon x + z + 1 = y \}.\] Relacija \(R\) predstavlja relacijo \(<\) v \(\mathbf{N}_0\). V tem primeru je \(\mathcal{D}_R = \mathbf{N}_0\) in \(\mathcal{Z}_R = \mathbf{N}\).

Zgled 3.3.

• Opazujmo relacijo enakosti \(=\) v množici \(A\). Od naštetih lastnosti je ta relacija refleksivna, simetrična, antisimetrična, tranzitivna in enolična.

• Opazujmo relacijo \(\leq\) v \(\mathbf{N}_0\). Ta relacija je refleksivna, antisimetrična, tranzitivna in strogo sovisna.

• Opazujmo relacijo \(<\) v \(\mathbf{N}_0\). Ta relacija je irefleksivna, asimetrična, tranzitivna in sovisna.

• Opazujmo relacijo je mama v množici ljudi. Ta relacija je irefleksivna, asimetrična, antisimetrična in intranzitivna.

Zgled 3.4. Naslednje relacije so ekvivalenčne:

• relacija enakosti \(=\),

• univerzalna relacija \(A \times A\),

• relacija vzporednosti premic v \(\mathbf{R}^2\),

• relacija ima enako barvo oči kot v množici ljudi,

• relacija ima enak BDP kot v množici držav.

Zgled 3.5.

• Naj bo \(A\) množica ljudi in \(R\) relacija ima enako barvo oči kot. Ekvivalenčni razred neke osebe z modrimi očmi torej sestavljajo ravno vse osebe z modrimi očmi. Ekvivalenčni razredi torej ustrezajo barvam oči.

• Naj bo \(A\) poljubna množica in \(R\) relacija enakosti v \(A\). Za vsak \(x \in A\) velja \(R[x] = \{ x \}\). Množica ekvivalenčnih razredov je enaka \(A/R = \{ \{ x \} \mid x \in A \}\).

• Naj bo \(A\) poljubna množica in \(R\) univerzalna relacija v \(A\). Za vsak \(x \in A\) velja \(R[x] = A\). Imamo torej en sam ekvivalenčni razred in velja \(A/R = \{ A \}\).

• Naj bo \(A\) množica premic v prostoru \(\mathbf{R}^3\) in naj bo \(R\) relacija vzporednosti premic. Za dano premico \(p\) je torej \(R[p]\) ravno množica vseh premic, ki so vzporedne \(p\). Ekvivalenčni razredi torej ustrezajo vsem smerem v \(\mathbf{R}^3\) oziroma enotskim vektorjem v \(\mathbf{R}^3\).

• Množico \(\mathbf{Z}\) lahko definiramo kot kvocientno množico množice \(A = \mathbf{N}_0 \times \mathbf{N}_0\) po relaciji \(R\), kjer je \((a,b)R(c,d)\), če in samo če \(a+d = b+c\). Velja \[R[(a,b)] = \{ (c,d) \in \mathbf{N}_0 \times \mathbf{N}_0 \mid c-d = a-b \},\] zato lahko množico ekvivalenčnih razredov \(A/R\) identificiramo z množico \(\mathbf{Z}\) prek bijekcije \(R[(a,b)] \mapsto a-b\) za \((a,b) \in A\).

• Naj bo \(m \in \mathbf{N}\). Na množici celih števil \(\mathbf{Z}\) definiramo relacijo kongruence po modulu \(m\) kot \[x \equiv y \pmod{m} \Longleftarrow \exists k \in \mathbf{Z}\mid x - y = k \cdot m.\] Elementa \(x,y \in \mathbf{Z}\) sta torej kongruentna po modulu \(m\), če im samo če dajeta isti ostanek pri deljenju z \(m\). Ni se težko prepričati, da je to ekvivalenčni relacija. Označimo jo z \(R_m\). Ekvivalenčni razredi ustrezajo ostankom pri deljenju z \(m\): \[\begin{aligned} R_m[0] &= \{ x \in \mathbf{Z}\mid \exists k \in \mathbf{Z}\colon x = k m \}, \\ R_m[1] &= \{ x \in \mathbf{Z}\mid \exists k \in \mathbf{Z}\colon x = k m + 1 \}, \\ \vdots \\ R_m[m-1] &= \{ x \in \mathbf{Z}\mid \exists k \in \mathbf{Z}\colon x = k m +m-1 \}. \end{aligned}\] Za \(m = 1\) je torej \(R_1 = A\), za \(m = 2\) pa ima \(R_2\) dva ekvivalenčna razreda, in sicer množico sodih števil in množico lihih števil.

Zgled 3.6. Naj bo \(A = \mathbf{N}\). Med dobro poznanimi relacijami v \(\mathbf{N}\) veljajo naslednje enakosti:

• \((<) \cup (=) = (\leq)\)

• \((\leq) \backslash (=) = (<)\),

• \((\leq) \cap (\geq) = (=)\),

• \((\leq) \cup (\geq) = \mathbf{N}\times \mathbf{N}\),

• \((<) \cap (>) = \emptyset\),

• \((<) \cup (>) = (\neq) = (=)^c\),

• \((\leq)^c = (>)\),

• \((\leq)^T = (\geq)\).

Zgled 3.7. Naj bo \(A\) množica ljudi.

• Kaj je relacija \(\text{hči} \circ \text{mož}\)? Za osebi \(x,y \in A\) velja \[x (\text{hči} \circ \text{mož}) y \Leftrightarrow \exists u \colon (x \text{mož} u \land u \text{hči} y),\] torej kadar je \(x\) hčerin mož \(y\)-a, se pravi kadar je \(x\) zet \(y\). Velja torej \(\text{hči} \circ \text{mož} = \text{zet}\).

• \(\text{oče} \circ \text{brat} = \text{stric}\)

• \(\text{zakonec} \circ \text{mati} = \text{tašča}\)

Zgled 3.8. Najprej velja \[R^1 = R^{0+1} = R^0 \circ R = id_A \circ R = R,\] za tem velja \[R^2 = R^{1+1} = R^1 \circ R = R \circ R\] in induktivno je \(R^n\) enak kompoziciji \(n\)-tih \(R\)-jev. Ker je operacija komponiranja asociativna, nam pri tem ni potrebno postavljati oklepajev, saj je rezultat neodvisen od vrstnega reda izvajanja kompozicij.

Zgled 3.9. Naj bo \(A\) množica ljudi in \(R = \text{otrok}\). Tedaj je \(R^2 = \text{vnuk} \cup \text{vnukinja}\) in \(R^3 = \text{pravnuk} \cup \text{pravnukinja}\) in za vsak \(n \geq 2\) je \[R^n = \text{(pra)$^{n-2}$vnuk} \cup \text{(pra)$^{n-2}$vnukinja}.\]

Zgled 3.10. Naj bo \(A\) množica ljudi in \(R = \text{otrok}\). Velja \(R^+ = \text{potomec} \cup \text{potomka}\).

Zgled 3.11. Naj bo \(A\) množica ljudi. Velja \[\text{otrok}^\text{tranzitivnost} = \text{otrok}^+ = \text{potomec} \cup \text{potomka}.\]

Zgled 4.1.

• Relacija \(\leq\) linearno ureja realna števila \(\mathbf{R}\).

• Relacija deljivosti \(|\) delno ureja naravna števila \(\mathbf{N}\).

• Naj bo \(A\) neka množica množic, na primer \(A = \{ B \mid B \subseteq \{ 1,2,\dots, 10\} \}\). Tedaj relacija \(\subseteq\) vsebovanosti množic delno ureja \(A\).

Zgled 4.2.

• Naj bo \(A = \{ 1,2,\dots, 10 \}\), opremljena z relacijo deljivosti naravnih števil \(|\).

  

• Naj bo \(A = \{ B \mid B \subseteq \{ 1,2,3 \} \}\), opremljena z relacijo \(\subseteq\) vsebovanosti množic.

  

• Naj bo \(A = \{ 1,2,3,4,5 \}\), opremljena z običajno relacijo \(\leq\) (manjše ali enako).

  

Zgled 4.3.

• Naj bo \(A = \{ 1, 2, \dots, 10 \}\), opremljena z relacijo deljivosti \(|\). Minimalni element je \(1\) in to je hkrati tudi prvi element. Maksimalnih elementov je več, in sicer \(7\), \(10\), \(9\), \(6\), \(8\). Zadnjih elementov pa ni.

• Naj bo \(A = \{ B \mid B \subseteq \{ 1, 2, 3 \} \} \backslash \{ \emptyset \}\), opremljena z relacijo vsebovanosti množic \(\subseteq\). Minimalni elementi so \(\{ 1 \}\), \(\{ 2 \}\), \(\{ 3 \}\). Prvih elementov ni. Maksimalni element je \(\{ 1, 2, 3 \}\) in ta je hkrati zadnji.

• Naj bo \(A = \mathbf{Z}\), opremljena z relacijo \(\leq\). Tukaj ni nobenih posebnih elementov.

• Naj bo \(A\) poljubna množica, opremljena z relacijo \(id_A\). Tukaj je vsak element maksimalen in vsak minimalen. Če ima \(A\) vsaj \(2\) elementa, potem ni niti prvih niti zadnjih elementov.

Zgled 4.4.

• Naj bo \(A = \mathbf{R}\), opremljena z relacijo \(\leq\). Naj bo \(B = (0,1)\) odprti interval. Tedaj \(\min B\) in \(\max B\) ne obstajata. Vsako število \(a \geq 1\) je zgornja meja za \(B\) in vsako število \(a \leq 0\) je spodnja meja za \(B\).

• Naj bo \(A = \mathbf{N}\), opremljena z relacijo deljivosti \(|\). Naj bo \(B = \{ 12, 18, 24, 72 \}\). Tedaj \(\min B\) ne obstaja, \(\max B\) pa je enak \(72\). Vsako število oblike \(72k\) za \(k \in \mathbf{N}\) je zgornja meja za \(B\). Števila \(1\),\(2\),\(3\),\(6\) so spodnje meje za \(B\).

Zgled 4.5.

• Naj bo \(A = \mathbf{R}\), opremljena z običajno relacijo \(\leq\). Naj bo \(B = (0,1)\). Velja \(\inf B = 0\) in \(\sup B = 1\).

• Naj bo \(A = \mathbf{N}\), opremljena z relacijo deljivosti \(|\). Naj bo \(B = \{ 12, 18, 24, 72 \}\). Tedaj je infimum \(\inf B\) enak največjemu skupnemu delitelju \(D(12, 18, 24, 72) = 6\), supremum \(\sup B\) pa je enak najmanjšemu skupnemu večkratniku \(v(12, 18, 24, 72) = 72\).

• Infimum in supremum ne obstajata vedno. Na primer, če vzamemo \(A = \mathbf{R}\) z relacijo \(\leq\) in \(B = \{ n \mid n \in \mathbf{N}\}\), potem množica \(B\) nima zgornjih mej v množici \(A\), torej je \(M = \emptyset\). Prazna množica seveda nima prvega elementa, torej množica \(B\) nima supremuma.

Zgled 4.6.

• Vsaka linearno urejena množica \(A\) je mreža. Res, za vsaka \(a,b \in A\) velja \(\inf \{ a, b \} = \min \{ a,b \}\) in \(\sup \{ a, b \} = \max \{ a, b \}\) in tako minimum kot maksimum obstajata, ker je \(A\) linearno urejena in zato v posebnem sovisna.

• Naj bo \(A = \mathbf{N}\), opremljena z relacijo deljivosti \(|\). Ta delno urejena množica je mreža, saj za vsaka \(a, b \in \mathbf{N}\) velja \(\inf \{ a,b \} = D(a,b)\) in \(\sup \{ a, b \} = v(a,b)\).

• Naj bo \(S\) poljubna neprazna množica in naj bo \(A\) množica podmnožic \(S\), se pravi \(A = \{ B \mid B \subseteq S \}\), opremljena z relacijo vsebovanosti množic \(\subseteq\). Ta delno urejena množica je mreža, saj za vsaki množici \(B, C \in A\) velja \(\inf \{ B, C \} = B \cap C\) in \(\sup \{ B, C \} = B \cup C\).

• Zadnji zgled modificirajmo tako, da za množico \(A\) vzamemo le neprazne podmnožice množice \(S\). To je še vedno delno urejena množica. Za različna elementa \(x,y \in S\) infimum \(\inf \{ \{ x \}, \{ y \} \}\) ne obstaja. To torej ni mreža.

Zgled 5.1. Naj bo \(V = \{ 1, 2, 3, 4, 5 \}\) in naj bo \[E = \{ \{ 1, 2 \}, \{ 2, 3 \}, \{ 3, 4 \}, \{ 4, 1 \}, \{ 1, 3 \}, \{ 4, 5 \} \}.\]

Graf \(G = (V,E)\) si lahko vizualiziramo tako, da vozlišča narišemo kot točke v ravnini, za tem pa vozlišči \(u,v \in V\) povežemo, če in samo če je \(\{ u, v \} \in E\).

Zgled 5.2.

Zgled 5.3. Naj bo \(G\) graf, predstavljen na naslednji sliki.

Stopnje vozlišč so \(d(a) = 2\), \(d(b) = 2\), \(d(c) = 3\), \(d(d) = 1\), \(d(e) = 0\). Vozlišče \(d\) je list, vozlišče \(e\) pa je izolirana točka.

Zgled 5.4.

Zgled 5.5. Naj bo \(G\) graf, predstavljen na naslednji sliki. Ta graf bomo srečali še večkrat, zato mu dajmo ime lizika.

Matrika sosednosti lizike je \[A(G) = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}.\] Opazimo, da je ta matrika simetrična. To ni slučaj, saj za vsaka \(i,j\) velja \(a_{ij} = 1\), če in samo če je \(v_i \sim v_j\), torej če in samo če je \(a_{ji} = 1\).

Zgled 5.6. Opazujmo liziko. Povezave označimo kot \(e_1 = \{ 1, 2 \}\), \(e_2 = \{ 1, 3 \}\), \(e_3 = \{ 2, 3 \}\) in \(e_4 = \{ 3, 4 \}\). Incidenčna matrika je \[B(G) = \begin{pmatrix} 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 \end{pmatrix}.\] Ta matrika ni simetrična. V splošnem to niti ni kvadratna matrika, saj je število vozlišč grafa lahko različno od števila povezav.

Zgled 5.7.

• Petersenov graf je \(3\)-regularen graf na \(10\) vozliščih. Iz leme o rokovanju sklepamo, da je \(10 \cdot 3 = 2 \cdot |E|\), torej ima Petersenov graf \(15\) povezav. Ta sklep velja za vsak \(3\)-regularen graf na \(10\) vozliščih.

• Ali obstaja \(3\)-regularen graf na \(9\) vozliščih? Če bi obstajal, potem bi po lemi o rokovanju veljalo \(9 \cdot 3 = 2 \cdot |E|\), torej je \(|E| = 27/2\), kar ni mogoče. Tak graf torej ne obstaja.

Zgled 5.8. Naj bo \(G\) lizika z vozlišči \(V(G) = \{ 1,2,3,4 \}\). Naj bo \(H\) graf z vozlišči \(V(H) = \{ 1,2,3,4 \}\) in povezavami \(E(H) = \emptyset\). Tedaj je \(H\) vpet podgraf grafa \(G\).

Zgled 5.9.

• Poln graf \(K_n\) ni dvodelen graf za \(n \geq 3\).

• Pot \(P_n\) je dvodelen graf za \(n \geq 2\), saj lahko množico \(\mathbf{Z}/n\mathbf{Z}\) zapišemo kot unijo sodih števil (\(A\)) in lihih števil (\(B\)) med \(0\) in \(n-1\), povezave v \(P_n\) pa vedno tečejo le med sodimi in lihimi števili.

• Cikel \(C_n\) je dvodelen graf, če je \(n\) sodo število. V tem primeru lahko namreč uporabimo enak argument kot za pot \(P_n\), saj lahko \(\mathbf{Z}/n\mathbf{Z}\) razdelimo na soda in liha števila in vse povezave v \(C_n\) tečejo le med sodimi in lihimi števili.

  Ta argument pa ne deluje, ko je \(n\) liho število, saj takrat dobimo še dodatno povezavo med sodima številoma \(0 \sim n-1\). Prepričajmo se, da cikel \(C_n\) za \(n\) lih ni dvodelen. Res, denimo, da je z razčlenitvijo vozlišč \(V = A \cup B\). Brez škode lahko predpostavimo, da je \(0 \in A\). Potem je nujno \(1 \in B\) in za tem \(2 \in A\) in za tem \(3 \in B\) in tako dalje vse do \(n-1 \in A\), saj je \(n\) liho. Ker pa je \(0 \sim n-1\) v ciklu \(C_n\), dobimo povezavo dveh vozlišč v množici \(A\), kar je sprto s predpostavko o dvodelnosti grafa. Lihi cikli torej niso dvodelni.

Zgled 5.10.

• Za vsak graf \(G\) je preslikava \[h \colon V(G) \to V(G), \quad u \mapsto u\] avtomorfizem grafa \(G\). Pravimo mu trivialni avtomorfizem.

• Naj bo \(G = C_n\) cikel dolžine \(n\). Ta cikel lahko zavrtimo za \(1\) v smeri urinega kazalca. Natančneje, definirajmo preslikavo \[h \colon \mathbf{Z}/n\mathbf{Z}\to \mathbf{Z}/n\mathbf{Z}, \quad u \mapsto u + 1.\] Za vsaki vozlišči \(u,v \in \mathbf{Z}/n\mathbf{Z}\) velja \[\{ u,v \} \in E(C_n) \Leftrightarrow v = u \pm 1 \pmod{n}\] in \[\{ h(u), h(v) \} \in E(C_n) \Leftrightarrow h(v) = h(u) \pm 1 \pmod{n} \Leftrightarrow v = u \pm 1 \pmod{n}.\] Preslikava \(h\) je torej avtomorfizem grafa \(C_n\).

• Naj bo \(G_1 = C_6\) cikel dolžine \(6\) in \(G_2\) graf z vozlišči in povezavami \[V(G_2) = \{ a,b,c,d,e,f \}, \quad E(G_2) = \{ ad, ae, bd, bf, ce, cf \}.\] Prepričajmo se, da sta grafa \(G_1\) in \(G_2\) izomorfna. Definirajmo preslikavo \[h \colon V(G_1) \to V(G_2), \quad 0 \mapsto d, 1 \mapsto a, 2 \mapsto e, 3 \mapsto c, 4 \mapsto f, 5 \mapsto b.\] Za vsaka \(i,j \in V(G_1)\) velja \(i \sim j\), če in samo če \(h(i) \sim h(j)\). Preslikava \(h\) je torej izomorfizem grafov.

Zgled 5.11. Invariante grafov so število točk, število povezav, dvodelnost, število točk stopnje \(3\), število trikotnikov, …

Zgled 5.12.

• Naj bo \(L\) lizika in \(C_4\) cikel. Lizika ima vozlišče stopnnje \(3\), cikel pa je \(2\)-regularen. Ta dva grafa torej nista izomorfna.

• Dana sta naslednja grafa \(G_1\) in \(G_2\).

  

  

  Ali sta \(G_1\) in \(G_2\) izomorfna? Ujemata se v številu vozlišč in številu povezav. Oba vsebujeta \(5\)-cikel, zato nista dvodelna. Oba sta kubična grafa. Noben od grafov ne vsebuje trikotnika. Ta dva grafa pa se razlikujeta v dolžini najkrajšnega cikla v grafu, ki ji pravimo ožina grafa. Ožina je seveda invarianta grafov. Ožina grafa \(G_1\) je \(5\), ožina grafa \(G_2\) pa je \(4\). Ta dva grafa torej nista izomorfna.

Zgled 5.13. V naslednjem grafu je označen primer poti in primer cikla.

Zgled 5.14. Lizika je povezan graf. Če liziki odstranimo vozlišče stopnje \(3\), dobimo graf, ki je disjunktna unija grafov \(P_2\) in izolirane točke. Ta graf ni povezan, ima dve povezani komponenti.

Zgled 5.15. V naslednjem grafu za vozlišči \(u,v\) na zunanjem ciklu velja \(d(u,v)=2\).

Zgled 5.16. Drevo je povezan graf brez ciklov. Njegova vozlišča stopnje \(1\) so listi.

Zgled 5.17. Lizika vsebuje Eulerjev sprehod, cikel \(C_5\) vsebuje Eulerjev obhod, poln graf \(K_5\) vsebuje Eulerjev obhod.

Zgled 5.18. Oglejmo si naslednji graf.

Ta graf je kubičen, zato nima Eulerjevega obhoda in ga ne moremo narisati v eni potezi. Kolikšno je najmanjše število potez, ki zadoščajo, da narišemo ta graf? Na sliki je prikazano, kako ta graf lahko narišemo s \(4\) potezami. Vsaka poteza je prikazana s svojo barvo. Prepričajmo se, da pa tega grafa ne moremo narisati z manj kot \(4\) potezami. To lahko vidimo tako, da seštejemo stopnje vseh vozlišč v grafu. Po lemi o rokovanju je ta vsota soda. Po drugi strani ima vsaka poteza svoje začetno in končno vozlišče (morda sta to enaki vozlišči), torej skupno prispeva k vsoti stopenj \(2\) za vozlišča na sprehodu in \(1\) za začetno in končno vozlišče. Graf, narisan v \(3\) potezah, bi zato imel kvečjemu \(6\) vozlišč lihe stopnje. Obravnavan graf pa ima \(8\) vozlišč stopnje \(3\).

Zgled 5.19.

• Lizika vsebuje Hamiltonovo pot, poln graf \(K_4\) vsebuje Hamiltonov cikel.

• Naslednji grafi vsebujejo Hamiltonove cikle, ki so označeni z rdečo barvo.

  

• Ali naslednji graf vsebuje Hamiltonov cikel?

  

Zgled 5.20. Ko liziki odstranimo vozlišče stopnje \(3\), razpade na dve komponenti. Lizika torej ni Hamiltonov graf.

Zgled 5.21. Vrnimo se k zadnjemu zgledu iz začetka tega razdelka. Obravnavani graf je dvodelen z biparticijo vozlišč \(A \cup B\), pri čemer je \(|A| = 5\) in \(|B| = 6\). Po posledici ta graf zato ni Hamiltonov.

Zgled 5.22. Dvodelen graf iz zadnjega zgleda ni Hamiltonov, saj z odstranitvijo \(5\) točk graf razpade na \(6\) komponent. Iz tega argumenta pa še ne sledi, da ta graf nima Hamiltonove poti, saj bi za to moral razpasti na vsaj \(7\) komponent. V resnici ta graf ima Hamiltonovo pot, kot je prikazano na naslednji sliki.

Zgled 5.23. Za vsaki različni nepovezani vozlišči v naslednjem grafu velja \(d(u) + d(v) \geq 7\). Po Orejevem izreku je graf Hamiltonov. Poišči Hamiltonov cikel v njem!

Zgled 5.24. Najmanjša stopnja vozlišča v naslednjem grafu je \(3\), število vozlišč pa je \(6\). Po Diracovem izreku je graf Hamiltonov. Poišči Hamiltonov cikel v njem!

Zgled 5.25. Ali je Petersenov graf Hamiltonov? Na naslednji sliki je prikazana Hamiltonova pot.

S protislovjem premislimo, da Hamiltonov cikel ne obstaja. Če bi namreč \(C\) bil Hamiltonov cikel, potem bi vseboval \(10\) vozlišč Petersenovega grafa in \(10\) povezav. Označimo vozlišča na \(C\) z \(v_1v_2 \dots v_{10}\). Ker ima Petersenov graf \(15\) povezav, iščemo torej še \(5\) dodatnih tetivnih povezav, ki jih dodamo ciklu \(C\), da dobimo Petersenov graf. Vemo, da je Petersenov graf \(3\)-regularen, zato moramo po eno tako tetivno povezavo dodati vsakemu vozlišči na ciklu \(C\). Vemo, da Petersenov graf nima \(3\)-ciklov in nima \(4\)-ciklov, hkrati pa ima \(5\)-cikel. Gotovo torej obstaja vozlišče na \(C\), brez škode je to kar \(v_1\), ki ima tetivno povezavo do soseda antipodnega vozlišča \(v_6\), brez škode je to kar \(v_5\). Opazujmo zdaj vozlišče \(v_6\). Tudi to vozlišče mora imeti tetivno povezavo do nekega vozlišča na \(C\). Ker pa Petersenov graf nima \(3\)-ciklov in nima \(4\)-ciklov, taka tetivna povezava ne obstaja. To je protislovje z obstojem Hamiltonovega cikla v Petersenovem grafu.

Zgled 5.26.

• Obravnavajmo šahovnico dimenzij \(3 \times 3\). Če konjiček začne v centralnem polju, potem nima kam skočiti, saj je plošča premajhna. Centralno vozlišče prirejenega grafa je torej izolirana točka in graf ni povezan, zato seveda tudi nima Hamiltonovega cikla.

• Obravnavajmo šahovnico dimenzij \(5 \times 5\). Dobimo graf na \(25\) vozliščih. Če obarvamo vozlišča s črno in belo barvo kot na šahovnici, potem je zaradi dejstva, da konjiček vedno skoči s črnega polja na belo oziroma obratno, prirejeni graf dvodelen. Ker ima šahovnica \(25\) vozlišč, je število belih vozlišč različno od števila črnih vozlišč. Po izreku ta graf torej ni Hamiltonov. Enak argument deluje za vse šahovnice z lihim številom polj.

Zgled 5.27. Nekatere grafe gotovo lahko narišemo v ravnini brez križanja povezav, na primer liziko, cikle, drevesa. Tudi poln graf \(K_4\) lahko narišemo na ta način, kot je prikazano na sliki.

Zgled 5.28. Disjunktno unijo \(K_3 \cup K_3\) lahko narišemo v ravnino na dva vsaj načina, in sicer lahko en trikotnik narišemo znotraj drugega ali pa dva trikotnika narišemo enega ob drugem.

Zgled 5.29.

• Vsaka ravninska vložitev drevesa ima eno samo lice, saj graf nima nobenih ciklov.

• Obe vložitvi grafa \(K_3 \cup K_3\) iz zadnjega zgleda imata \(3\) lica.

  

Zgled 5.30. Obravnavajmo ravninski vložitvi \(K_3 \cup K_3\) iz zadnjega zgleda. V prvi ravninski vložitvi je dolžina rdečega lica enaka \(3\), dolžina modrega je enaka \(6\) in dolžina zelenega je enaka \(3\). V drugi ravninski vložitvi sta dolžini modrega in rdečega lica enaki \(3\), dolžina zelenega pa je enaka \(6\).

Zgled 5.31.

• Uporabimo zadnjo trditev za to, da dokažemo, da graf \(K_{3,3}\), ki smo ga obravnavali na začetku tega razdelka, res ni ravninski. Ta graf ima \(6\) vozlišč in \(9\) povezav. Ker je dvodelen, ne vsebuje \(3\)-ciklov. Če bi bil ravninski, bi zanj torej morala veljati neenakost \(9 \leq 2 \cdot 6 - 4 = 8\), kar pa ne drži.

• Premislimo, da tudi graf \(K_5\) ni ravninski. Ta graf ima \(5\) vozlišč in \(10\) povezav. Če bi bil ravninski, bi zanj morala veljati neenakost \(10 \leq 3 \cdot 5 - 6 = 9\), kar pa ne drži.

Zgled 5.34.

• Liziko lahko obarvamo s \(k = 3\) barvami. Vozlišče stopnje \(3\) najprej obravamo z barvo \(1\), potem pa list in eno od vozlišč stopnje \(2\) obarvamo z barvo \(2\), drugo vozlišče stopnje \(2\) pa z barvo \(3\).

• Graf je dvodelen, če in samo če je vozliščno \(2\)-obarvljiv.

Zgled 5.35.

• \(\chi(G) = 1\), če in samo če v grafu \(G\) ni povezav, se pravi \(E(G) = \emptyset\).

• \(\chi(G) = 2\), če in samo če je graf \(G\) dvodelen.

• Kromatično število cikla \(\chi(C_n)\) je \(2\), če je \(n\) sodo, saj je v tem primeru graf dvodelen. Če je \(n\) liho, pa graf ni dvodelen, zato je \(\chi(C_n) \geq 3\). Po drugi strani pa \(3\) barve zares zadostujejo, da pobarvamo vozlišča lihega cikla.³⁵

• \(\chi(K_n) = n\).

Zgled 5.36.

• Za liziko \(L\) velja \(\omega(L) = 3\) in hkrati \(\chi(L) = 3\).

• Za Petersenov graf \(P\) velja \(\omega(P) = 2\). Ker \(P\) ni dvodelen, velja \(\chi(P) \geq 3\). Ni težko najti barvanja grafa \(P\) s tremi barvami, zato velja \(\chi(P) = 3\).

Zgled 5.37. Opazujmo zemljevid sveta, na katerem so označene državne meje in meje z morji. Države in morja si predstavljajmo kot vozlišča, obstoj skupne meje pa naj pomeni sosednost vozlišč. Na ta način dobimo graf, ki je ravninski, saj je izvirni zemljevid narisan na ravnino. Po izreku je ta graf vozliščno \(4\)-obarvljiv. To pomeni, da lahko zemljevid sveta obarvamo s \(4\) barvami, pri čemer nobeni dve sosednji državi nista enake barve.

Zgled 5.38.

• Za poln graf \(K_n\) velja \(\Delta(K_n) = n-1\) in \(\chi(K_n) = n\), torej za ta graf velja enakost v zadnji trditvi.

• Za cikel \(C_n\) velja \(\Delta(C_n) = 2\), kromatično število \(\chi(C_n)\) pa je bodisi \(2\) za sode \(n\) bodisi \(3\) za lihe \(n\). V primeru sodega cikla je kromatično število torej enako maksimalni stopnji, v primeru lihega cikla pa velja enakost v zadnji trditvi.

Zgled 5.39. Kemična tovarna pri delu uporablja snovi \(S_1, S_2, \dots, S_n\). Zaradi nevarnosti eksplozije nekaterih med njimi ne smemo skladiščiti skupaj. Kolikšno je najmanjše potrebno število prostorov za varno skladiščenje teh snovi? Ta problem imenujemo problem skladiščenja nevarnih snovi.

Za razrešitev problema definirajmo graf \(G\) z vozlišči \(V(G) = \{ S_1, S_2, \dots, S_n \}\), pri čemer sta vozlišči \(u,v \in V(G)\) povezani, če in samo če snovi \(u\) in \(v\) ne smemo skladiščiti skupaj. Razporeditev snovi po prostorih podamo s funkcijo, ki vsakemu vozlišči priredi številko prostora, se pravi s funkcijo \(c \colon V(G) \to \{ 1, 2, \dots, k \}\), za katero pa mora veljati \(uv \in E(G) \Rightarrow c(u) \neq c(v)\). Optimalna rešitev problema je torej vozliščno barvanje grafa \(G\) s \(\chi(G)\) barvami.

Zgled 5.40. Liziko \(L\) lahko povezavno obarvamo s tremi barvami. Vse tri barve porabimo za \(3\)-cikel v liziki, z eno od treh povezav pa potem pobarvamo še dodatno povezavo v liziki.

Zgled 5.41.

• \(\chi'(G) = 0\), če in samo če v grafu \(G\) ni povezav, se pravi \(E(G) = \emptyset\).

• Kromatični indeks cikla \(\chi'(C_n)\) je \(2\), če je \(n\) sodo, saj lahko povezave pobarvamo alternirajoče z dvema barvama. Če je \(n\) liho, pa je \(\chi'(C_n) \geq 3\). Po drugi strani pa \(3\) barve zares zadostujejo, da pobarvamo povezave lihega cikla, podobno kot pri barvanju vozlišč.

• \(\chi'(K_{1,n}) = n\).

Zgled 5.42. Velja \(\chi'(K_{m,n}) = \max \{ m, n \}\).

Zgled 5.43. Naj bo \(P\) Petersenov graf. Velja \(\Delta(P) = 3\), zato je \(3 \leq \chi'(P) \leq 4\). Povezavnega barvanja s štirimi barvami ni težko najti.

Zgled 5.44. Dvodelni grafi so razreda I. Petersenov graf je razreda II.

Zgled 5.45.

• Po trditvi velja \(\chi'(K_{2n+1}) = 2n+1\), torej je \(K_{2n+1}\) razreda II.

• Velja \(\chi'(K_{2n + 2}) = 2n+1\), zato je \(K_{2n+2}\) razreda I. Tako barvanje lahko najdemo na naslednji način. Najprej \(2n+1\) vozlišč grafa razporedimo v cikel, ki ga narišemo kot pravilen \((2n+1)\)-kotnik, zadnje vozlišče pa damo v središče tega cikla. Zunanji cikel je dolžine \(2n+1\), ki ga povezavno obarvamo z \(2n+1\) različnimi barvami. Zdaj izberemo eno od povezav na zunanjem ciklu, obarvamo z barvo \(b\), in povlečemo povezave, vzporedne tej povezavi, vse jih obarvamo z barvo \(b\). Nazadnje povlečemo še povezavo med središčnim vozliščem in vozliščem na ciklu, ki je kraji na nobeno od prej opisanih povezav, tudi to zadnjo povezavo obarvamo z barvo \(b\). Enako ponovimo za vse povezave na zunanjem ciklu. Na ta način dobimo povezavno \((2n+1)\)-barvanje grafa \(K_{2n+2}\).