i i “kolofon” — 2017/6/30 — 9:13 — page 1 — #1 i i i i i i OBZORNIK ZA MATEMATIKO IN FIZIKO Glasilo Društva matematikov, fizikov in astronomov Slovenije Ljubljana, MAREC 2017, letnik 64, številka 2, strani 41–80 Naslov uredništva: DMFA–založništvo, Jadranska ulica 19, p. p. 2964, 1001 Ljubljana Telefon: (01) 4766 553, 4232 460 Telefaks: (01) 4232 460, 2517 281 Elektronska pošta: zaloznistvo@dmfa.si Internet: http://www.obzornik.si/ Transakcijski račun: 03100–1000018787 Mednarodna nakazila: SKB banka d.d., Ajdovščina 4, 1513 Ljubljana SWIFT (BIC): SKBASI2X IBAN: SI56 0310 0100 0018 787 Uredniški odbor: Peter Legiša (glavni urednik), Sašo Strle (urednik za matematiko in odgovorni urednik), Aleš Mohorič (urednik za fiziko), Mirko Dobovišek, Irena Drevenšek Olenik, Damjan Kobal, Petar Pavešić, Marko Petkovšek, Marko Razpet, Nada Razpet, Peter Šemrl, Matjaž Zaveršnik (tehnični urednik). Jezikovno pregledal Janez Juvan. Računalniško stavila in oblikovala Tadeja Šekoranja. Natisnila tiskarna COLLEGIUM GRAPHICUM v nakladi 1250 izvodov. Člani društva prejemajo Obzornik brezplačno. Celoletna članarina znaša 24 EUR, za druge družinske člane in študente pa 12 EUR. Naročnina za ustanove je 35 EUR, za tujino 40 EUR. Posamezna številka za člane stane 3,19 EUR, stare številke 1,99 EUR. DMFA je včlanjeno v Evropsko matematično društvo (EMS), v Mednarodno matematično unijo (IMU), v Evropsko fizikalno društvo (EPS) in v Mednarodno združenje za čisto in uporabno fiziko (IUPAP). DMFA ima pogodbo o recipročnosti z Ameriškim matematič- nim društvom (AMS). Revija izhaja praviloma vsak drugi mesec. Sofinancira jo Javna agencija za raziskovalno dejavnost Republike Slovenije iz sredstev državnega proračuna iz naslova razpisa za sofi- nanciranje domačih znanstvenih periodičnih publikacij. c© 2017 DMFA Slovenije – 2033 Poštnina plačana pri pošti 1102 Ljubljana NAVODILA SODELAVCEM OBZORNIKA ZA ODDAJO PRISPEVKOV Revija Obzornik za matematiko in fiziko objavlja izvirne znanstvene in strokovne članke iz mate- matike, fizike in astronomije, včasih tudi kak prevod. Poleg člankov objavlja prikaze novih knjig s teh področij, poročila o dejavnosti Društva matematikov, fizikov in astronomov Slovenije ter vesti o drugih pomembnih dogodkih v okviru omenjenih znanstvenih ved. Prispevki naj bodo zanimivi in razumljivi širšemu krogu bralcev, diplomantov iz omenjenih strok. Članek naj vsebuje naslov, ime avtorja (oz. avtorjev), sedež institucije, kjer avtor(ji) dela(jo), izvle- ček v slovenskem jeziku, naslov in izvleček v angleškem jeziku, klasifikacijo (MSC oziroma PACS) in citirano literaturo. Slike in tabele, ki naj bodo oštevilčene, morajo imeti dovolj izčrpen opis, da jih lahko večinoma razumemo tudi ločeno od besedila. Avtorji člankov, ki želijo objaviti slike iz drugih virov, si morajo za to sami priskrbeti dovoljenje (copyright). Prispevki so lahko oddani v računalni- ški datoteki PDF ali pa natisnjeni enostransko na belem papirju formata A4. Zaželena velikost črk je 12 pt, razmik med vrsticami pa vsaj 18 pt. Prispevke pošljite odgovornemu uredniku ali uredniku za matematiko oziroma fiziko na zgoraj na- pisani naslov uredništva. Vsak članek se praviloma pošlje dvema anonimnima recenzentoma, ki morata predvsem natančno oceniti, kako je obravnavana tema predstavljena, manj pomembna pa je originalnost (in pri matematičnih člankih splošnost) rezultatov. Če je prispevek sprejet v objavo, potem urednik prosi avtorja še za izvorne računalniške datoteke. Le-te naj bodo praviloma napisane v eni od standardnih različic urejevalnikov TEX oziroma LATEX, kar bo olajšalo uredniški postopek. Avtor se z oddajo članka strinja tudi z njegovo kasnejšo objavo v elektronski obliki na internetu. i i “Vuksic” — 2017/6/30 — 13:12 — page 41 — #1 i i i i i i POLNI NABORI RESNIČNOSTNIH FUNKCIJ IN POSTOVA MREŽA LARA VUKŠIĆ Fakulteta za matematiko in fiziko Univerza v Ljubljani Math. Subj. Class. (2010): 06E30 Resničnostne funkcije so preslikave iz množice {0, 1}n v {0, 1} za neko naravno število n. Množico vseh resničnostnih funkcij označimo s P2. Skupaj s petimi operacijami na re- sničnostnih funkcijah, ki jih imenujemo operacije Malceva, P2 tvori strukturo, imenovano funkcijska algebra. Podmnožice P2, zaprte za operacije Malceva, so podrazredi. Množica resničnostnih funkcij je poln nabor natanko tedaj, ko ni vsebovana v nobenem izmed petih maksimalnih podrazredov P2. FUNCTIONALLY COMPLETE SETS OF BOOLEAN FUNCTIONS AND POST’S LATTICE Boolean functions are maps from {0, 1}n to {0, 1} for some natural number n. P2 is the set of all such functions. Together with the five Maltsev operations on Boolean functions, P2 forms a structure called function algebra. The subsets of P2 that are closed under Maltsev operations are called the subclasses of P2. A set of Boolean functions is functionally complete if and only if it is not contained in any of the five P2’s maximal subclasses. Uvod Vprašanje, s katerimi resničnostnimi funkcijami je mogoče izraziti vse pre- ostale, je precej staro. V prvem zvezku monumentalnega dela Principia Mathematica [6], izdanem leta 1910, Bertrand Russell in W. N. Whitehead pokažeta, da za to zadošča že en par resničnostnih funkcij, denimo dis- junkcija z negacijo, Sheffer pa je leta 1912 pokazal, da je vse resničnostne funkcije mogoče izraziti z enim samim veznikom, ki je po njem dobil tudi svoje ime. Emil Leon Post je leta 1921 [4] (in podrobneje leta 1941 [5]) odkril, kaj je potreben in zadosten pogoj za to, da lahko z neko množico resničnostnih funkcij izrazimo vse preostale. Taka množica pomeni poln nabor resničnostnih funkcij. V članku poleg nekaj najpogosteje uporabljanih resničnostnih funkcij predstavimo tudi nekaj operacij na takih funkcijah ter strukturo, ki jo z nji- hovo pomočjo tvori množica vseh resničnostnih funkcij. Lastnosti te stuk- ture, ki se imenuje funkcijska algebra, nam bodo pomagale pri dokazu Po- stovega izreka, ki poda karakterizacijo polnih naborov resničnostnih funkcij. Izrek o polnih naborih resničnostnih funkcij, ki ga sicer pogosto srečamo kot Obzornik mat. fiz. 64 (2017) 2 41 i i “Vuksic” — 2017/6/30 — 13:12 — page 42 — #2 i i i i i i Lara Vukšić posledico izreka o strukturi Postove mreže, v članku obravnavamo kot sa- mostojen rezultat in zato podamo kraǰsi in enostavneǰsi dokaz. Resničnostne funkcije Pri logiki se operatorje, ki jih predstavimo v članku, namesto kot funkcije obravnava kot izjavne veznike, s pomočjo katerih iz enostavnih izrazov tvo- rimo kompleksneǰse. Ker bo za naš namen lažje uporabiti drugačen pristop, definiramo pojem resničnostne funkcije. Definicija 1. Naj bo n ∈ N. Resničnostna funkcija n spremenljivk je pre- slikava iz {0, 1}n v {0, 1}. Če želimo poudariti, da je funkcija f funkcija n spremenljivk, namesto f pǐsemo fn. Množico vseh resničnostnih funkcij označimo s P2, množico vseh resničnostnih funkcij n spremenljivk pa s P n 2 . Če je A podmnožica P2, z A n označimo A ∩ Pn2 . Vsako resničnostno funkcijo je mogoče predstaviti s tabelo resničnostnih vrednosti, iz katere lahko za vsako n-terico x = (x1, . . . , xn) ∈ {0, 1}n razbe- remo vrednost f(x). Tako so v tabelah 1 in 2 predstavljene nekatere funkcije ene oz. dveh spremenljivk, ki so najpogosteje v uporabi. V prvi tabeli tako definiramo negacijo, v drugi pa (po vrsti) konjunkcijo, disjunkcijo, implika- cijo, negacijo implikacije, ekvivalenco, strogo disjunkcijo ter Shefferjev in Lukasiewiczev veznik. x ¬x 0 1 1 0 Tabela 1. Negacija. x y x ∧ y x ∨ y x→ y x 6→ y x↔ y x+ y x ↑ y x ↓ y 0 0 0 0 1 0 1 0 1 1 0 1 0 1 1 0 0 1 1 0 1 0 0 1 0 1 0 1 1 0 1 1 1 1 1 0 1 0 0 0 Tabela 2. Nekaj resničnostnih funkcij dveh spremenljivk. Poleg tega za vsako konstanto a ∈ {0, 1} in vsako naravno število n definiramo konstantno funkcijo cna in, če velja 1 ≤ i ≤ n, tudi eni – projekcijo poljubne n-terice x na njeno i-to komponento eni : cna(x1, . . . , xn) = a, eni (x1, . . . , xn) = xi. 42 Obzornik mat. fiz. 64 (2017) 2 i i “Vuksic” — 2017/6/30 — 13:12 — page 43 — #3 i i i i i i Polni nabori resničnostnih funkcij in Postova mreža Funkcijska algebra nad P2 Nekatere resničnostne funkcije lahko izrazimo s pomočjo drugih. Tako velja npr. x→ y = ¬x ∨ y, x 6→ y = ¬(x→ y), x ↑ y = ¬(x ∧ y), x ↓ y = ¬(x ∨ y). Znani sta tudi De Morganovi formuli, ki opǐseta medsebojno odvisnost disjunkcije, konjunkcije in negacije: ¬x ∧ ¬y = ¬(x ∨ y), ¬x ∨ ¬y = ¬(x ∧ y). Poleg tega lahko v vsaki resničnostni funkciji izenačimo spremenljivke, ki v njej nastopajo, ali pa zamenjamo njihov vrstni red. Te postopke lahko opǐsemo s pomočjo spodnje peterice operacij na resničnostnih funkcijah. Z njimi bo množica P2 dobila algebraično strukturo. Definicija 2. Operacije Malceva so naslednje operacije, definirane na funk- cijah f ∈ Pn2 in g ∈ Pm2 : 1. (ζf)(x1, . . . , xn) = f(x2, x3, . . . , xn, x1) za n ≥ 2, ζf = f za n = 1, 2. (τf)(x1, . . . , xn) = f(x2, x1, x3, . . . , xn) za n ≥ 2, τf = f za n = 1, 3. (4f)(x1, . . . , xn−1) = f(x1, x1, x2, . . . , xn−1) za n ≥ 2, 4f = f za n = 1, 4. (5f)(x1, . . . , xn+1) = f(x2, x3, . . . , xn+1) za n ≥ 1, 5. (f ?g)(x1, . . . , xm+n−1) = f(g(x1, . . . , xm), xm+1, . . . , xm+n−1) za n ≥ 1, m ≥ 1. Pokazali bomo, da s komponiranjem operacij Malceva dobimo še veliko drugih operacij na resničnostnih funkcijah. Z njimi lahko med drugim for- maliziramo izražanje veznikov s pomočjo drugih, kar nam bo omogočilo, da kasneje definiramo polni nabor. Trditev 3. Za vsako permutacijo π ∈ Sn velja, da lahko s komponiranjem operacij ζ in τ dobimo takšno operacijo nad funkcijo fn ∈ P2, ki bo permu- tirala spremenljivke funkcije tako, kot določa π. 41–53 43 i i “Vuksic” — 2017/6/30 — 13:12 — page 44 — #4 i i i i i i Lara Vukšić Dokaz. Trditev, ki jo želimo dokazati, je ekvivalentna trditvi, da cikel in transpozicija generirata celotno grupo permutacij Sn oz. da velja [(12), (12 . . . n)] = Sn. Ker je vsaka permutacija produkt transpozicij, bo do- volj, če pokažemo, da lahko tako dobimo poljubno transpozicijo. Če najprej za poljuben i od 1 do n vzamemo produkt (12 . . . n)n−i+1(12) (12 . . . n)i−1, vidimo, da je enak transpoziciji (i, i + 1). Z dobljenimi tran- spozicijami zaporednih elementov lahko nadalje izrazimo transpozicije oblike (1i) za vsak i v obliki (12)(23) . . . (i − 1, i)(i − 2, i − 1) . . . (12). Ker lahko poljubno transpozicijo (ij) zapǐsemo kot produkt (1i)(1j)(1i), je trditev do- kazana. Operacija4 izenači prvo in drugo spremenljivko resničnostne funkcije. S pomočjo zgornje trditve pa hitro vidimo, da lahko ta operacija v kompoziciji s prvima dvema izenači poljubno število spremenljivk na poljubnih mestih. Za opis četrte operacije si bomo pomagali s spodnjo definicijo. Definicija 4. Naj bo fn ∈ P2 in i ∈ {1, . . . , n}. Če velja f(a1, . . . , ai−1, 0, ai+1, . . . , an) = f(a1, . . . , ai−1, 1, ai+1, . . . , an) za vse vrednosti a1, . . . , ai−1, ai+1, . . . , an, pravimo, da je i-ta spremenljivka xi v f nebistvena ali fiktivna. Sicer je xi bistvena spremenljivka funkcije f . Vidimo, da operacija 5 funkciji f doda nebistveno spremenljivko na prvo mesto. Podobno kot zgoraj se lahko prepričamo, da je s komponira- njem operacije 5 s permutacijami spremenljivk mogoče dobiti operacijo, ki resničnostni funkciji doda poljubno mnogo nebistvenih spremenljivk na poljubna mesta. Zadnja izmed petih operacij, ?, je kompozicija dveh funk- cij, ki na mesto prve (ali, če to operacijo zopet komponiramo s permu- tacijami spremenljivk, katerekoli druge) spremenljivke prve funkcije vstavi drugo funkcijo. Sedaj ko smo opisali operacije Malceva in videli, da lahko s komponira- njem teh operacij ustvarimo še več drugih operacij na resničnostnih funkci- jah, lahko definiramo algebraično strukturo nad P2 ter nekaj z njo povezanih uporabnih pojmov. Definicija 5. Funkcijska algebra nad P2 je množica P2 skupaj z operacijami Malceva. Pravimo, da je množica A ⊆ P2 zaprta ali da je podrazred P2, če za poljubni funkciji f, g ∈ A velja ζf, τf,4f,5f, f ? g ∈ A. Podrazred P2 je pravi podrazred, če ni enak P2. Zaprtje neke množice A ⊆ P2 znotraj funkcijske algebre je najmanǰsi podrazred P2, ki vsebuje A. Označimo ga z [A]. Zgleda podrazredov P2 sta, kot ni težko preveriti, denimo množica vseh projekcij in množica vseh konstantnih funkcij. V razširjeni verziji Postovega 44 Obzornik mat. fiz. 64 (2017) 2 i i “Vuksic” — 2017/6/30 — 13:12 — page 45 — #5 i i i i i i Polni nabori resničnostnih funkcij in Postova mreža izreka je opisanih vseh števno neskončno mnogo podrazredov P2, ki glede na relacijo vsebovanosti tvorijo t. i. Postovo mrežo, nas pa bodo zanimali predvsem podrazredi z neko posebno lastnostjo. Definicija 6. Neprazen pravi podrazred F ( P2 je maksimalen, če za vsako funkcijo f ∈ P2 \ F velja [{f} ∪ F ] = P2. Maksimalni podrazredi nam bodo v veliko pomoč pri karakterizaciji pol- nih naborov resničnostnih funkcij. Polni nabori resničnostnih funkcij Če problem, ki smo ga definirali v uvodu, prevedemo v jezik funkcijske alge- bre, nas zanimajo takšne množice resničnostnih funkcij, za katere velja, da je njihovo zaprtje enako P2. V tem razdelku poǐsčemo potreben in zadosten pogoj za to, da ima neka množica takšno lastnost. Definicija 7. Poln nabor resničnostnih funkcij je množica funkcij A ⊆ P2, za katero velja [A] = P2. Če je A poln nabor resničnostnih funkcij, za vsako funkcijo f ∈ P2 torej obstajajo k ∈ N in funkcije f1, . . . , fk ∈ A, s katerimi lahko s pomočjo operacij Malceva izrazimo f . Poln nabor je minimalen, če nobena njegova prava podmnožica ni poln nabor. Čeprav bomo polne nabore v celoti karakterizirali šele proti koncu članka, lahko za nekatere množice resničnostnih funkcij že sedaj ugotovimo, da po- menijo poln nabor resničnostnih funkcij. Naj bo fn resničnostna funkcija, ki ni konstantno enaka nič, predsta- vljena z resničnostno tabelo. Vsaki vrstici te tabele, pri kateri je vrednost f enaka ena, priredimo konjunkcijo n izrazov oblike bodisi xi, če je vrednost i-te spremenljivke v tabeli v tej vrstici enaka 1, bodisi ¬xi v nasprotnem primeru. Potem je disjunktivna normalna oblika funkcije f definirana kot disjunkcija vseh takih izrazov. Če pa je f funkcija, ki ni konstantno enaka 1, ji lahko priredimo konjunktivno normalno obliko. Ta je enaka konjunk- ciji negacij tistih izrazov, ki so enako kot zgoraj prirejeni tistim vrsticam resničnostne tabele, pri katerih f zavzame vrednost 0. Primer 8. S pomočjo tabele 3 definiramo funkcijo f na treh spremenljiv- kah. Disjunktivna normalna oblika funkcije f je (¬x∧¬y ∧¬z)∨ (¬x∧¬y ∧ z) ∨ (¬x ∧ y ∧ z) ∨ (x ∧ ¬y ∧ z), konjunktivna normalna oblika pa ¬(¬x ∧ y ∧ ¬z) ∧ ¬(x ∧ ¬y ∧ ¬z) ∧ ¬(x ∧ y ∧ ¬z) ∧ ¬(x ∧ y ∧ z) oziroma (x ∨ ¬y ∨ z) ∧ (¬x ∨ y ∨ z) ∧ (¬x ∨ ¬y ∨ z) ∧ (¬x ∨ ¬y ∨ ¬z). 41–53 45 i i “Vuksic” — 2017/6/30 — 13:12 — page 46 — #6 i i i i i i Lara Vukšić x y z f(x, y, z) 0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 0 1 1 1 0 Tabela 3 Očitno je, da obe obliki na vseh n-tericah zavzameta isto vrednost kot f . Torej smo tako pri disjunktivni kot pri konjunktivni normalni obliki funkcije to izrazili zgolj s pomočjo disjunkcije, konjunkcije in negacije. Ker lahko vsaki funkciji priredimo vsaj eno izmed teh dveh oblik, sledi spodnji rezultat. Trditev 9. {∨,∧,¬} je poln nabor resničnostnih funkcij. Če za neko množico M ⊆ P2 velja, da lahko s pomočjo njenih elemen- tov izrazimo vse funkcije nekega polnega nabora, potem očitno sledi, da je tudi M poln nabor, saj lahko s pomočjo njenih elementov izrazimo vse resničnostne funkcije. To dejstvo uporabimo v dokazu naslednje posledice. Posledica 10. Množice {¬,∨}, {¬,∧}, {¬,→}, {¬, 6→}, {↑} in {↓} so polni nabori resničnostnih funkcij. Dokaz. Ker iz De Morganovih formul sledi x ∧ y = ¬(¬x ∨ ¬y) in x ∨ y = ¬(¬x∧¬y), sta prvi dve množici v posledici polna nabora, saj smo pokazali, da je množica {∨,∧,¬} vsebovana tako v [{¬,∨}] kot tudi v [{¬,∧}]. Velja tudi x ∨ y = ¬x→ y = ¬(¬x 6→ y), iz česar sledi, da sta polna nabora tudi množici {¬,→} in {¬, 6→}. Njuni zaprtji namreč obe vsebujeta polni nabor {∨,¬}. Da dokažemo, da sta tudi {↑} in {↓} polna nabora, se najprej prepri- čamo, da lahko tako iz Shefferjevega kot tudi iz Lukasiewiczevega veznika dobimo negacijo: ¬x = x ↑ x = x ↓ x. Zato iz enakosti x ∧ y = ¬(x ↑ y) in x ∨ y = ¬(x ↓ y) sledi {¬,∧} ⊆ [{↑}] in {¬,∨} ⊆ [{↓}], s čimer smo pokazali, da sta tudi zadnji dve množici v posledici polna nabora. Poleg zgornjih dveh oblik si bomo pomagali s še eno normalno obliko, v kateri lahko izrazimo resničnostne funkcije. Spomnimo se, da je ideal I kolobarja K njegov podkolobar, za katerega velja ak ∈ I in ka ∈ I za 46 Obzornik mat. fiz. 64 (2017) 2 i i “Vuksic” — 2017/6/30 — 13:12 — page 47 — #7 i i i i i i Polni nabori resničnostnih funkcij in Postova mreža vse a ∈ I in k ∈ K. Z 〈a1, . . . , an〉 označimo najmanǰsi ideal, ki vsebuje elemente a1, . . . , an ∈ K. Kvocientni kolobar po idealu K/I pa je množica ekvivalenčnih razredov elementov iz K, za katere velja, da elementa k1 in k2 pripadata enakemu ekvivalenčnemu razredu k1 + I = k2 + I natanko tedaj, ko je njuna razlika k1 − k2 vsebovana v I. Tako poistovetimo tiste v K različne elemente, ki pomenijo enak ekvivalenčni razred v K/I. Izrek 11. Naj bo n ∈ N, f ∈ Pn2 in Jn = 〈x21 − x1, x22 − x2, . . . , x2n − xn〉 ideal v kolobarju polinomov Kn = Z2[x1, . . . , xn]. Potem obstaja natanko določen polinom p ∈ Kn/Jn, tako da velja: f(x) = p(x) = ∑ (i1,...,in)∈{0,1}n ai1,...,in · x i1 1 · x i2 2 · · · · · x in n za vse x ∈ {0, 1}n. Opomba 12. Elementi Kn/Jn za neki n ∈ N sicer niso polinomi, temveč ekvivalenčni razredi polinomov iz Kn. Vrednost nekega elementa p + Jn ∈ Kn/Jn v neki točki a ∈ {0, 1}n je kljub temu dobro definirana. Res, razlika dveh polinomov p, q ∈ Kn, ki pripadata istemu ekvivalenčnemu razredu iz Kn/Jn, je namreč vsebovana v Jn = 〈x21−x1, x22−x2, . . . , x2n−xn〉. Ker pa je 02 = 0 in 12 = 1, za vsak polinom h ∈ Jn in vsako n-terico a ∈ {0, 1}n velja h(a) = 0. Iz tega sledi, da imajo vsi elementi nekega ekvivalenčnega razreda p + Jn pri dani n-terici a enako vrednost. Zato lahko za poljuben element p + Jn ∈ Kn/Jn definiramo njegovo vrednost pri neki n-terici a s q(a), kjer je q poljuben predstavnik ekvivalenčnega razreda p+ Jn. Zavoljo preglednosti zapisa bomo ekvivalenčni razred p+Jn predstavili s polinomom q ∈ Z2[x1, . . . , xn], ki je v vsaki od spremenljivk x1, . . . , xn stopnje največ 1. Ti polinomi se imenujejo polinomi Žegalkina [7]. Dokaz. Izrek dokažemo z indukcijo po n. Če je n = 1, f bodisi nima bistvenih spremenljivk oz. je konstantna funkcija, ki jo lahko izrazimo s konstantnim polinomom p(x) = 0 oz. q(x) = 1 iz K1/J1, bodisi ima f na- tanko eno bistveno spremenljivko. V tem primeru velja f(x) = e11(x) = x ali f(x) = ¬x. Identiteto lahko predstavimo s polinomom p(x) = x, negacijo pa s polinomom q(x) = x+1 izK1/J1. Predpostavimo, da trditev velja za vsako funkcijo manj kot n spremenljivk, in poljubno funkcijo f ∈ Pn2 zapǐsimo ta- kole: f(x1, . . . , xn) = (1 − xn) · f(x1, . . . , xn−1, 0) + xn · f(x1, . . . , xn−1, 1). Tako smo funkcijo f izrazili s pomočjo dveh funkcij n− 1 spremenljivk, za kateri pa po predpostavki obstajata polinoma iz Kn−1/Jn−1, s katerima se ujemata pri vseh (n− 1)-tericah (x1, . . . , xn−1). Če v našem zapisu z njima nadomestimo pripadajoči funkciji, dobimo iskani polinom. 41–53 47 i i “Vuksic” — 2017/6/30 — 13:12 — page 48 — #8 i i i i i i Lara Vukšić Pokazati moramo še, da je ta polinom enolično določen. Ni težko vi- deti, da je preslikava, ki vsaki funkciji f ∈ Pn2 priredi ustrezni ekviva- lenčni razred iz Kn/Jn, predstavljen s polinomom Žegalkina, injektivna. Res: če dvema funkcijama n spremenljivk pripada enak ekvivalenčni razred in posledično enak polinom Žegalkina, potem sta enaki za vse vrednosti (x1, . . . , xn) ∈ {0, 1}n. Zato zadošča pokazati, da sta za vsak n ∈ N množici Pn2 in Kn/Jn enako veliki, saj bo iz tega sledilo, da je zgoraj definirana pre- slikava med njima bijekcija. Vsaka funkcija fn ∈ Pn2 je enolično določena z 2n vrednostmi, ki jih zavzame na vseh n-tericah iz {0, 1}n. Ker za vsako teh vrednosti obstajata dve možnosti, 0 ali 1, sledi |Pn2 | = 22 n . Polinom Žegalkina funkcije n spremenljivk pa je po drugi strani enolično določen s koeficienti ai1,...,in ∈ {0, 1} za vsak (i1, . . . , in) ∈ {0, 1}n, iz česar sledi |Kn/Jn| = |Pn2 | = 22 n . V tabeli 4 so poleg nekaterih resničnostnih funkcij zapisani pripadajoči polinomi Žegalkina. Funkcija iz P2 Polinom Žegalkina ¬x x+ 1 x ∨ y x+ y + xy x ∧ y xy x→ y x+ xy + 1 x+ y x+ y x↔ y x+ y + 1 Tabela 4. Polinom Žegalkina za nekatere funkcije P2. Pet maksimalnih podrazredov Sedaj lahko naštejemo nekatere podrazrede P2. V naslednjem razdelku se bo izkazalo, da so to edini maksimalni razredi P2. Definicija 13. Pravimo, da resničnostna funkcija f ohranja vrednost 0, če velja f(0, . . . , 0) = 0. Množico vseh tovrstnih funkcij označimo s T0. Pravimo, da resničnostna funkcija f ohranja vrednost 1, če velja f(1, . . . , 1) = 1. Množico vseh tovrstnih funkcij označimo s T1. Funkcija f je monotona, če iz x ≤ y sledi f(x) ≤ f(y). Pri tem velja (x1, . . . , xn) ≤ (y1, . . . , yn) natanko tedaj, ko je xi ≤ yi za vsak 1 ≤ i ≤ n, pri čemer je 0 ≤ 1. Množico vseh monotonih funkcij označimo z M . Funkcija f je sebidualna, če za vsak x velja: ¬f(¬x) = f(x), kjer je ¬(x1, . . . , xn) = (¬x1, . . . ,¬xn). Množico vseh sebidualnih funkcij označimo s S. 48 Obzornik mat. fiz. 64 (2017) 2 i i “Vuksic” — 2017/6/30 — 13:12 — page 49 — #9 i i i i i i Polni nabori resničnostnih funkcij in Postova mreža Afine funkcije so natanko tiste, za katere ima pripadajoči polinom Že- galkina skupno stopnjo ≤ 1. Množico vseh afinih funkcij označimo z L. S tabelo 5 naprej pokažemo, da so zgoraj navedene množice paroma neprimerljive glede na relacijo vsebovanosti. 6∈ T0 6∈ T1 6∈M 6∈ S 6∈ L ∈ T0 + + ∧,∨ ∧,∨ ∈ T1 → ↔ ∧,∨ ∧,∨ ∈ L c11 + ¬ + ∈M c11 c10 ∧,∨ ∧,∨ ∈ S ¬ ¬ ¬ h Tabela 5. Funkcije, ki dokazujejo neprimerljivost podrazredov P2. Tu je h funkcija treh spremenljivk, katere polinom Žegalkina je enak xy + xz + yz. Pokazati moramo tudi, da so zgornje množice zaprte za operacije Malceva. Trditev 14 ([3]). Množice T0, T1,M, S in L so podrazredi P2. Dokaz. Ni težko preveriti, da je vseh pet množic zaprtih glede na prve štiri operacije Malceva. Dokažimo še, da so vse zaprte tudi za kompozicijo. Naj bosta f in g funkciji n oz. m spremenljivk, iz česar sledi, da je h = f ? g funkcija m+ n− 1 spremenljivk. Naj velja f, g ∈ T0. Potem je h(0, . . . , 0) = f(g(0, . . . , 0), 0, . . . , 0) = f(0, 0, . . . , 0) = 0. Torej je T0 zaprta za kompozicijo. Analogno dokažemo, da to velja tudi za T1. Naj bosta zdaj f in g ∈M . Če velja (x1, . . . , xm+n−1) ≤ (y1, . . . , ym+n−1), potem je h(x1, . . . , xm+n−1) = f(g(x1, . . . , xm), xm+1, . . . , xm+n−1) ≤ f(g(y1, . . . , ym), xm+1 . . . , xm+n−1) ≤ f(g(y1, . . . , ym), ym+1, . . . , ym+n−1) = h(y1, . . . , ym+n−1). Iz tega sledi, da je M zaprta za kompozicijo. 41–53 49 i i “Vuksic” — 2017/6/30 — 13:12 — page 50 — #10 i i i i i i Lara Vukšić Če sta f in g ∈ S, velja: h(x1, . . . , xm+n−1) = f(g(x1, . . . , xm), xm+1 . . . , xm+n−1) = ¬f(¬g(x1, . . . , xm),¬xm+1, . . . ,¬xm+n−1) = ¬f(g(¬x1, . . . ,¬xm),¬xm+1, . . . ,¬xm+n−1) = ¬h(¬x1, . . . ,¬xm+n−1). Torej je za kompozicijo zaprta tudi S, zaprtost L pa sledi iz tega, da je kompozicija afinih funkcij spet afina. Pokazali smo, da je pet zgoraj opisanih množic zaprtih za operacije Malceva, s čimer smo dokazali trditev. Postov izrek V spodnjem izreku podamo potreben in zadosten pogoj, ki mu mora neka množica A ⊆ P2 zadoščati, da pomeni poln nabor resničnostnih funkcij. Iz njega bo sledilo, da so T0, T1,M,L in S edini maksimalni podrazredi P2. Izrek 15 ([2, izrek 3.2.4.1]). Množica A ⊆ P2 je poln nabor resnično- stnih funkcij natanko tedaj, ko ni vsebovana v nobenem od podrazredov T0, T1,M,L in S. Dokaz. Če je A vsebovana v nekem podrazredu B ∈ {T0, T1,M,L, S}, velja [A] ⊆ B ( P2. Torej A ni poln nabor resničnostnih funkcij. Predpostavimo sedaj, da A ni vsebovana v nobenem izmed petih pod- razredov v izreku. Pokazali bomo, da v tem primeru velja {∨,∧,¬} ⊆ [A], iz česar po lemi 9 sledi [A] = P2. Ker velja A 6⊆ B za vsako množico B ∈ {T0, T1,M,L, S}, obstajajo funkcije f0, f1, fM , fS , fL ∈ A, ki med se- boj niso nujno različne in za katere velja: f0 /∈ T0, f1 /∈ T1, fM /∈M,fS /∈ S, fL /∈ L. Če sedaj izenačimo vse spremenljivke funkcije f0, dobimo funkcijo ene spremenljivke f ′0 ∈ [A], za katero velja f ′0(0) = 1. Ločimo dva primera glede na to, ali velja f ′0(1) = 1, s čimer dobimo konstantno funkcijo c 1 1, ali pa velja f ′0(1) = 0, kar nam da f ′ 0(x) = ¬x. Primer 1: Predpostavimo najprej, da velja f ′0(1) = 1. Dobljeno kon- stantno funkcijo c11 vstavimo v f1. Ker ta ne ohranja vrednosti 1, velja f1(1, . . . , 1) = 0, s čimer smo dobili tudi drugo konstantno funkcijo c 1 0. Ker fM , funkcija n ≥ 1 spremenljivk (konstantni funkciji sta monotoni), ne pripada razredu M , obstajata n-terici a ≤ b, za kateri velja fM (a) > fM (b). Naj bo I množica vseh takšnih 1 ≤ i ≤ n, za katere velja ai = bi, 50 Obzornik mat. fiz. 64 (2017) 2 i i “Vuksic” — 2017/6/30 — 13:12 — page 51 — #11 i i i i i i Polni nabori resničnostnih funkcij in Postova mreža J pa naj bo množica [n] \ I, kjer z [n] označimo množico {1, 2, . . . , n}. Če za vsak i ∈ I na i-to mesto v fM vstavimo konstantno funkcijo, enako ai oz. bi, spremenljivke na mestih j ∈ J pa med seboj izenačimo, dobimo negacijo. Res, naj brez škode za splošnost velja J = {1, 2, . . . , k} in I = {k + 1, . . . , n} za 1 ≤ k ≤ n, saj lahko spremenljivke med seboj poljubno permutiramo. Tedaj je f ′M (x) = fM (x, . . . , x, ak+1, . . . , an) in velja 1 = f ′M (0) = fM (0, . . . , 0, ak+1, . . . , an) > fM (1, . . . , 1, ak+1, . . . an) = f ′ M (1) = 0. Dokazali smo, da velja {c10, c11,¬} ⊆ [A]. Ker velja fL /∈ L, jo lahko brez škode za splošnost zapǐsemo s polinomom Žegalkina skupne stopnje najmanj 2: fL(x) = a0 + n∑ i=1 ai · xi + xi1 · xi2 · · · · · xir + g(x), kjer je r ≥ 2, 1 ≤ i1 i2 · · · ir ≤ n in je g polinom, katerega vsak člen je skupne stopnje r ali več, koeficient pri xi1 ·xi2 · · · · ·xir v g pa je enak nič. Naj bo f ′L(x, y) funkcija, ki jo dobimo iz fL(x), če spremenljivko xi1 nado- mestimo z x, spremenljivke xi2 , xi3 , . . . , xir z y, vse preostale spremenljivke pa s konstantno funkcijo c10. Potem lahko funkcijo f ′ L(x, y) predstavimo s polinomom Žegalkina oblike a+bx+cy+xy ∈ Z2[x, y]. Vseh osem možnosti za funkcijo f ′L prikazuje tabela 6. a b c a+ bx+ cy + xy f ′L(x, y) 0 0 0 xy x ∧ y 0 0 1 y + xy y 6→ x 0 1 0 x+ xy x 6→ y 0 1 1 x+ y + xy x ∨ y 1 0 0 1 + xy x ↑ y 1 0 1 1 + y + xy y → x 1 1 0 1 + x+ xy x→ y 1 1 1 1 + x+ y + xy x ↓ y Tabela 6. Funkcija f ′L glede na parametre a, b in c. V vseh primerih je {¬, f ′L} poln nabor resničnostnih funkcij. To sledi iz posledice 10. Ker velja {¬, f ′L} ⊆ [A], sledi, da je tudi A poln nabor. Primer 2: Predpostavimo sedaj, da velja f ′0(1) = 0 in zato f ′ 0(x) = ¬x. Ker velja fS /∈ S, obstaja takšna n-terica (a1, . . . , an), da je fS(a1, . . . , an) = fS(¬a1, . . . ,¬an). Naj bo za to n-terico I množica tistih indeksov 1 ≤ i ≤ n, za katere je ai = 0, in J = [n] \ I. Brez škode za splošnost naj velja I = {1, . . . , k} ter J = {k + 1, . . . , n} za 0 ≤ k ≤ n. Potem je fS(0, . . . , 0, 1, . . . , 1) = fS(1, . . . , 1, 0, . . . , 0). V fS(x1, . . . , xn) prvih k 41–53 51 i i “Vuksic” — 2017/6/30 — 13:12 — page 52 — #12 i i i i i i Lara Vukšić spremenljivk nadomestimo z ¬x, preostale pa z x. Tako dobimo funkcijo f ′S(x) = fS(¬x, . . . ,¬x, x, . . . , x). Ker velja f ′S(1) = fS(0, . . . , 0, 1, . . . , 1) = fS(1, . . . , 1, 0, . . . , 0) = f ′ S(0), je funkcija f ′ S konstantna. Dobili smo bodisi c10 bodisi c 1 1 in ker imamo na voljo tudi negacijo, smo primer 2 prevedli na primer 1. Posledica 16. Maksimalni podrazredi P2 so natanko T0, T1, L,M in S. Dokaz. Najprej pokažimo, da so T0, T1, L,M, S maksimalni podrazredi P2. Pa recimo, da obstaja neki podrazred B ∈ {T0, T1, L,M, S}, ki ni maksi- malen. Potem obstaja taka funkcija f ∈ P2 \ B, da velja [B ∪ {f}] ( P2. Po izreku 15 zato velja, da je množica B ∪ {f} vsebovana v nekem podra- zredu C ∈ {T0, T1, L,M, S}\{B}, saj ni poln nabor. To pa je v nasprotju z dejstvom, da so podrazredi T0, T1,M,L in S medsebojno različni in paroma neprimerljivi glede na relacijo vsebovanosti. Pokazati moramo še, da so T0, T1,M,L in S edini maksimalni podrazredi P2. Naj bo B maksimalen podrazred P2, različen od T0, T1, L,M in S. Zaradi maksimalnosti sledi, da ni vsebovan v nobenem od njih, zato je po izreku 15 poln nabor in velja: B = [B] = P2. To pa je v nasprotju z definicijo 6, po kateri so maksimalni razredi prave podmnožice P2. Torej takega podrazreda ni. Sedaj ko smo spoznali potreben in zadosten pogoj za to, da je neka množica resničnostnih funkcij poln nabor, lahko za poljubno podmnožico P2 povemo, ali je poln nabor. Določimo vse minimalne polne nabore, ki so vsebovani v P 22 in imajo moč kvečjemu dve. Najprej si oglejmo, katerim maksimalnim podrazredom pripadajo funkcije iz P 22 . Ker sta projekciji e 2 0 in e21 vsebovani v vseh maksimalnih podrazredih, ne nastopata v nobenem minimalnem polnem naboru. V tabeli 7 prikažemo, katerim maksimalnim podrazredom pripada večina preostalih funkcij iz P 22 . c20 c 2 1 ¬x1 → 6→ ∧ ∨ ↔ + ↑ ↓ T0 ∈ /∈ /∈ /∈ ∈ ∈ ∈ /∈ ∈ /∈ /∈ T1 /∈ ∈ /∈ ∈ /∈ ∈ ∈ ∈ /∈ /∈ /∈ L ∈ ∈ ∈ /∈ /∈ /∈ /∈ ∈ ∈ /∈ /∈ M ∈ ∈ /∈ /∈ /∈ ∈ ∈ /∈ /∈ /∈ /∈ S /∈ /∈ ∈ /∈ /∈ /∈ /∈ /∈ /∈ /∈ /∈ Tabela 7. Pripadnost nekaterih funkcij iz P 22 podrazredom T0, T1, L,M, S. Edine funkcije ene ali dveh spremenljivk, ki jih še nismo navedli, so ¬x2, ← in 6←. Ker pa lahko te funkcije s pomočjo operacije τ dobimo iz ¬x1, → oz. 6→ in obratno, sledi, da so funkcije ¬x2, ← oz. 6← vsebovane v natanko istih maksimalnih podrazredih kot ¬x1, → oz. 6→. 52 Obzornik mat. fiz. 64 (2017) 2 i i “Vuksic” — 2017/6/30 — 13:12 — page 53 — #13 i i i i i i Polni nabori resničnostnih funkcij in Postova mreža S pomočjo tabele 7 vidimo, da sta ↑ in ↓ edini funkciji iz P 22 , ki nista vsebovani v nobenem maksimalnem podrazredu, iz česar sledi, da sta {↑} in {↓} edina polna nabora, ki vsebujeta natanko en element P 22 . Poǐsčimo še minimalne polne nabore, ki vsebujejo dve funkciji iz P 22 . Jasno je, da nobeden od njih ne vsebuje ne ↑ ne ↓. 1. Nabori, ki vsebujejo →: Dodati moramo funkcijo, ki ni vsebovana v T1. Minimalni polni nabori, ki vsebujejo →, so torej {→, c20}, {→,¬}, {→, 6→} in {→,+}. 2. Nabori, ki vsebujejo 6→, ne pa →: Dodati moramo funkcijo, ki ni vse- bovana v T0. Tako dobimo {6→, c21}, {6→,¬} in {6→,↔}. 3. Nabori, ki vsebujejo ¬, a ne vsebujejo ne → ne 6→: Dodati moramo funkcijo, ki ni niti v L niti v S. Tako dobimo {¬,∨} in {¬,∧}. Minimalni polni nabori, ki ne vsebujejo nobene izmed funkcij →, 6→ in ¬, pa vsi vsebujejo vsaj tri elemente. Res: vsebovati morajo funkcijo, ki ni v T0, funkcijo, ki ni v T1, in funkcijo, ki ni v L. Zato morajo vsebovati vsaj po eno funkcijo iz množic {c21,↔}, {c20,+} in {∧,∨}. Sledi, da so edini minimalni polni nabori, ki vsebujejo dve funkciji iz P 22 , v točkah (1), (2) in (3). Za konec V članku smo predstavili maksimalne podrazrede funkcijske algebre P2 v povezavi s polnimi nabori resničnostnih funkcij. Omenili pa smo tudi, da razširjena verzija Postovega izreka poleg maksimalnih razredov predstavi vse druge podrazrede P2 ter odnose med njimi glede na vsebovanost. Strukturo funkcijske algebre pa lahko definiramo tudi na množicah funkcij, ki slikajo iz {0, 1, . . . , k− 1}n za neki n v {0, 1, . . . , k− 1}, kjer je k poljubno naravno število. Tudi v teh strukturah lahko določimo maksimalne razrede, a je to zaradi tega, ker se njihovo število zelo hitro povečuje, zahtevno. LITERATURA [1] G. P. Gavrilov in A. A. Sapozhenko, Problems and Exercises in Discrete Mathematics, Kluwer, Dordrecht, Boston, London, 1996. [2] D. Lau, Function Algebras on Finite Sets, Springer, Berlin, 2006. [3] F. J. Pelletier in N. M. Martin, Post’s functional completeness theorem, Notre Dame J. Formal Logic 31 (1990) 462–475, dostopno na www.sfu.ca/~jeffpell/papers/ PostPellMartin.pdf, ogled 2. 1. 2017. [4] E. L. Post, Introduction to a general theory of elementary propositions, Amer. J. Math. 43 (1921) 163–185. [5] E. L. Post, The Two-Valued Iterative Systems of Mathematical Logic, Princeton Uni- versity Press, Princeton, New Jersey, 1941. [6] A. N. Whitehead in B. Russell, Principia mathematica, vol. 1, Cambridge University Press, Cambridge, 1910. [7] Zhegalkin polynomial, v: Wikipedia: The Free Encyclopedia, dostopno na en. wikipedia.org/wiki/Zhegalkin_polynomial, ogled 16. 9. 2016. 41–53 53 i i “Zitko” — 2017/6/30 — 13:13 — page 54 — #1 i i i i i i NOBELOVA NAGRADA ZA FIZIKO 2016 ROK ŽITKO Institut Jožef Stefan Fakulteta za matematiko in fiziko, Univerza v Ljubljani PACS: 02.40.-k, 75.70.-i, 73.43.-f, 75.10.Pq Nobelova nagrada za fiziko je bila podeljena trem teoretičnim fizikom, ki so s koncepti in orodji iz topologije kot prvi ugotovili, da se lahko različne faze snovi med seboj razli- kujejo ne le po svojih simetrijskih lastnostih, temveč tudi po topološkem redu. Razložili so, kako pride do faznih prehodov brez zloma simetrije v dvodimenzionalnih sistemih, v katerih kot možne vzbuditve nastopajo vrtinci, kako kvantizirana prevodnost v kvantnem Hallovem pojavu prikaže topologijo pasu zasedenih stanj ter v čem se razlikujejo spinske verige s celoštevilskim in polceloštevilskim spinom. THE NOBEL PRIZE IN PHYSICS 2016 The Nobel prize in physics 2016 was awarded to three theoretical physicists who were the first to apply the concepts and tools from topology to demonstrate that different phases of matter may be distinguished not only by their symmetry properties, but also through their topological order. They have explained how there can be phase transitions without any symmetry breaking in two-dimensional systems hosting vortex excitations, how the quantized conductance in quantum Hall systems reflects the topology of the occupied states, and how differ spin chains with integer and half-integer spin. Nobelova nagrada za fiziko je bila leta 2016 podeljena trem teoretičnim fizikom, ki so v sedemdesetih in osemdesetih letih preǰsnjega stoletja med prvimi začeli uporabljati koncepte in orodja iz matematične veje topologije za razlago osnovnih lastnosti različnih faz kondenzirane snovi ter faznih pre- hodov med njimi [15]. Polovico nagrade je dobil David Thouless, preostali četrtini pa sta si delila Duncan Haldane in Michael Kosterlitz. Vsi trije so v času podelitve nagrade živeli in delali v Združenih državah Amerike, so pa sicer iz Velike Britanije (Haldanova mama je, mimogrede, slovenskega rodu). V delih, za katera so nagrajeni, so uporabili sicer zelo preproste topološke pojme (prva homotopska grupa krožnice oz. ovojno število, prvi Chernov razred in Chernovo število, druga homotopska grupa krogelne lupine), so pa s tem odprli povsem nove raziskovalne smeri v teoretični fiziki večdelčnih sistemov, ki so se naglo razvile in začele črpati tudi bolj napredna spoznanja iz topologije [22, 2]. Danes sta pojem »topoloških kvantnih števil« in razvr- ščanje faz snovi v različne topološke razrede postala v fiziki že kar domača, področje pa se je še dodatno razživelo po letu 2008 z odkritjem topoloških izolatorjev, to je snovi, ki so pasovni izolatorji in torej neprevodne v no- tranjosti, imajo pa kovinska mejna stanja in lahko zato prevajajo električni 54 Obzornik mat. fiz. 64 (2017) 2 i i “Zitko” — 2017/6/30 — 13:13 — page 55 — #2 i i i i i i Nobelova nagrada za fiziko 2016 tok po svoji površini, kar je zaradi velike potencialne uporabne vrednosti vzbudilo veliko zanimanje. Fazni prehodi brez zloma simetrije David Thouless je v začetku 70. let delal kot profesor matematične fizike na Univerzi v Birminghamu, kjer se mu je kot podoktorski sodelavec pri- družil Michael Kosterlitz, ki se je sicer pred tem ukvarjal s fiziko delcev, a je želel poskusiti še kaj drugega. Začela sta sodelovati pri vprašanju faznih prehodov v nizkodimenzionalnih sistemih ter pri vlogi topoloških defektov. Topološki defekti so vzbuditve sistema, ki so homotopsko različne od njego- vega osnovnega stanja in jih torej ni mogoče odstraniti na »gladek« način z zveznimi spremembami stanja. Primer so vrtinci v superfluidnem 4He, domenske stene v magnetih ter dislokacije v kristalih. Thouless je ugotovil, da ima enodimenzionalni Isingov model magneta z interakcijami dolgega dosega, ki padajo kot 1/r2, fazni prehod pri končni temperaturi Tc, medtem ko Isingov model z interakcijami kratkega dosega ne more biti urejen pri od nič različnih temperaturah. Kosterlitz se je po svojem prihodu lotil re- levantne literature, med drugim člankov Phila Andersona in sodelavcev na temo Kondovega modela nečistoče, ki se preslika na Isingov model z 1/r2 interakcijo, za katerega je Anderson razvil metodo reševanja, ki je bila prav- zaprav predhodnica renormalizacijske grupe, s katero se je kasneje proslavil Kenneth Wilson. Obravnava z renormalizacijsko grupo je tudi odigrala po- membno vlogo pri nadaljnjih raziskavah Kosterlitza in Thoulessa. Lotila sta se zagonetnega vprašanja urejenih faz v tako zelo tankih plasteh materialov, da jih lahko obravnavamo kot dvodimenzionalne (2D) snovi. Šlo je pred- vsem za tankoplastne magnete, katerih magnetizacija leži v ravnini, tanke plasti 4He ter dvodimenzionalne kristale. Tedaj je bilo splošno sprejeto, da ne more biti prehodov v urejeno stanje pri končnih temperaturah v 2D sis- temih z zvezno simetrijo in z interakcijami kratkega dosega, za kar so bili na voljo strogi dokazi, ki so jih bili prispevali Mermin, Wagner, Wegner in Hohenberg [14, 21]. Malo manj je bilo znano, da ti izreki pravzaprav prepo- vedujejo le pravi red dolgega dosega. Eksperimenti (numerični z računalni- škimi simulacijami in laboratorijski na pravih efektivno dvodimenzionalnih materialih) so že tedaj namigovali na obstoj nekakšnih prehodov med raz- ličnimi fazami. Thoulessov in Kosterlitzev poglavitni dosežek je bil dokaz, da so vendarle mogoči termični fazni prehodi pri končni temperaturi tudi v dveh dimenzijah, le da nizkotemperaturna faza ne more imeti pravega reda dolgega dosega, temveč korelacije zelo počasi (potenčno) padajo z razdaljo proti nič [12]. V seriji člankov sta postavila na čvrste temelje natančno ma- 54–64 55 i i “Zitko” — 2017/6/30 — 13:13 — page 56 — #3 i i i i i i Rok Žitko Slika 1. Levo: spinski val. Desno: vrtinec. Puščice ponazarjajo smer magnetnega momenta v ravnini, θ. tematično teorijo tovrstnih prehodov [13]. Do nekaterih podobnih spoznanj je neodvisno in približno sočasno prǐsel tudi ruski fizik Vadim Berezinski. Thouless in Kosterlitz sta med drugim obravnavala 2D magnet, pri ka- terem magnetni momenti ležijo v ravnini in jih lahko opǐsemo s kotom rav- ninskega zasuka θ(r), kjer je r položaj izbrane magnetnice. Ta sistem se imenuje tudi model XY. Ima zvezno simetrijo U(1), saj lahko vse magne- tnice hkrati zasukamo za enak kot, ne da bi se ob tem spremenila energija sistema. Nizkoenergijske vzbuditve, spinske valove (slika 1, levo), opisuje Hamiltonov operator H ∝ ∫ d2r[∇θ(r)]2. (1) Spinski valovi imajo energijo, ki je obratno sorazmerna s kvadratom njihove valovne dolžine in je torej v termodinamski limiti lahko poljubno majhna. Ker pa je Hamiltonov operator periodičen za operacijo θ(r) → θ(r) + 2π, kot možne rešitve obstajajo tudi vrtinci (slika 1, desno). To so topološke vzbuditve z visoko energijo in jih je torej malo, kljub temu pa so pomembne, ker dodatno rušijo ureditev sistema. Vsak vrtinec nosi »topološki naboj«, definiran kot ovojno število n: ∮ C dθ = 2πn, (2) kjer je C zaključena pot okoli sredice vrtinca. Ovojno število meri, koli- kokrat se zasuka vektor magnetizacije okoli navpične osi vzdolž poljubne 56 Obzornik mat. fiz. 64 (2017) 2 i i “Zitko” — 2017/6/30 — 13:13 — page 57 — #4 i i i i i i Nobelova nagrada za fiziko 2016 krivulje C, in je celo število, pozitivno ali negativno. Največ je vrtincev z n = 1 in antivrtincev z n = −1. Posamični vrtinci imajo visoko energijo, ki narašča logaritemsko z velikostjo sistema, kar je posebnost 2D sistemov. Hkrati pa je tudi prispevek k entropiji posameznega vrtinca sorazmeren z logaritmom ploščine celotnega sistema, saj je možnih mest, kjer je lahko vrtinec, približno enako P/P0, kjer je P ploščina sistema in P0 efektivna plo- ščina enega vrtinca. Pri končnih temperaturah je stanje sistema določeno preko proste energije F = E − TS. Odvisno od temperature lahko pro- sti vrtinci prispevajo močno pozitivno ali močno negativno k celotni prosti energiji. To pomeni, da pod neko kritično temperaturo Tc prostih vrtincev sploh ni, nad njo pa se takoj začnejo pojavljati. To si lahko predstavljamo tudi tako: pod Tc so pari vrtinca z n = 1 in antivrtinca n = −1 vezani, nad Tc pa se pari razvežejo in nastanejo prosti vrtinci in antivrtinci: nered se tedaj poveča. Posledično ima pod Tc magnet kvazired dolgega dosega s potenčno upadajočimi korelacijami med vektorji magnetizacije, nad Tc pa je sistem povsem neurejen z eksponentno upadajočimi korelacijami. Fazni prehod je zvezen in zelo blag (»neskončnega reda«); anomalija v specifični toploti je tako šibka, da sploh ni merljiva. Podobni zaključki veljajo tudi za tanke plasti 4He in za 2D kristale. Pri prvih obstajajo vrtinci v fazi ureditvenega parametra za superfluidno stanje, ki je kompleksno število, pri kristalih pa igrajo vlogo topoloških defektov dislokacije (linijske napake v kristalu). Kaj te ugotovitve pomenijo, denimo, za kristale v 2D, ki naj ne bi ob- stajali zaradi strogega dokaza, da v dveh dimenzijah kristalni red dolgega dosega sploh ne more obstajati? Pravzaprav ni nobenega navzkrižja. V nizkotemperaturni fazi dejansko obstaja samo kvazired, ne pa pravi red: korelacijska funkcija na velikih razdaljah pade proti nič, sicer počasi – po- tenčno – a vendarle. Bistveno pa je, da ima kvaziurejena kristalna faza končen prožnostni modul, kar pričakujemo za snov v trdnem stanju. Ter- mične fluktuacije sicer porušijo pravi red dolgega dosega, elastičnost pa kljub temu ostane končna. To se posploši tudi na vse druge primere iz te družine: pri nizkih temperaturah se vzpostavi rigidnost sistema na zunanje motnje, značilna za urejeno fazo, ne da bi obstajal pravi red dolgega dosega. V dveh dimenzijah ob faznem prehodu pride torej do (nezvezne) spremembe v rigi- dnosti, spontanega zloma simetrije pa ni. Urejena faza torej ni definirana preko kristalne rešetke, temveč preko odziva kristala na strižno obremeni- tev: kristal se odzove elastično in se reverzibilno deformira, medtem ko ima tekočina strižni modul enak nič in steče. Ta ključna ugotovitev pomeni, da obstajajo fazni prehodi, ki se jih ne da opisati v Landauovi paradigmi, ki temelji na razmisleku o simetrijah Hamiltonovega operatorja in Taylorjevem 54–64 57 i i “Zitko” — 2017/6/30 — 13:13 — page 58 — #5 i i i i i i Rok Žitko razvoju proste energije po parametru reda, ki opredeljuje zlom simetrije v urejeni fazi. Meritve dvodimenzionalnih superfluidov (tanke plasti 4He) so bile oprav- ljene še pred razvojem teorije Kosterlitza in Thoulessa (KT). Opazili so nezvezni skok v gostoti superfluida, ne da bi opazili nezveznost v specifični toploti. To se ni skladalo s faznim prehodom prvega reda, je pa v skladu s teorijo KT, ki napoveduje tudi, da je velikost skoka univerzalna [16]. Kosterlitz-Thoulessov prehod v 2D superfluidno stanje so leta 2006 za- znali tudi v plinu ohlajenih atomov 87Rb v ravninski optični pasti [7]. To ni enako kot Bose-Einsteinova kondenzacija in omenjena prehoda se zgodita pri različnih temperaturah. Pod prehodom KT so opazili potenčne korelacije, nad prehodom pa proste vrtince. Teorija KT je pomembna tudi v fiziki enodimenzionalnih kvantnih siste- mov in kvantnih nečistoč, saj med temi problemi najdemo takšne, ki imajo povsem enake enačbe renormalizacijske grupe kot klasični dvodimenzionalni model XY. Primer je kar paradigmatski model Kondove nečistoče, ki opi- suje en sam kvantnomehanski lokalni moment, sklopljen s kontinuumom elektronskih stanj v kovini. Če se spremeni predznak Kondove izmenjalne interakcije JK iz antiferomagnetne v feromagnetno, pride do kvantnega fa- znega prehoda iz zasenčene v nezasenčeno fazo, ki je v istem univerzalno- stnem razredu kot prehod KT. Kvantizirana prevodnost odraža topologijo pasu zasedenih stanj Do Hallovega pojava pride, če postavimo ploščat (efektivno dvodimenzio- nalen) prevodni trak v magnetno polje, usmerjeno pravokotno na ravnino traku: opazimo, da se prečno na električni tok in na magnetno polje vzpo- stavi električno polje, ki ravno uravnovesi magnetno Lorentzevo silo, ki de- luje na prevodnǐske elektrone in ukrivlja njihovo pot proti robu vzorca. Nastalo električno polje je sorazmerno s tokom in z magnetnim poljem, so- razmernostni koeficient (Hallov koeficient RH) pa je obratno sorazmeren z nabojem in številsko gostoto nosilcev naboja v prevodniku. V močnem magnetnem polju (reda 10 T) in pri nizkih temperaturah (pod 1 K) pa se elektroni začnejo obnašati povsem drugače. Kot je pokazal Landau, se elek- troni v močnem polju v kvaziklasičnem opisu gibajo po krožnih tirnicah in elektronski nivoji postanejo kvantizirani kot n = (n + 1/2)~ωc, kjer je ωc = eB/m ciklotronska frekvenca. Ti Landauovi nivoji so makroskopsko zasedeni. Namesto linearne odvisnosti od magnetnega polja je Klaus von Klitzing s sodelavci v čistih vzorcih opazil stopničast potek Hallovega koe- ficienta z univerzalnimi vrednostmi, ki so odvisne le od osnovnih fizikalnih 58 Obzornik mat. fiz. 64 (2017) 2 i i “Zitko” — 2017/6/30 — 13:13 — page 59 — #6 i i i i i i Nobelova nagrada za fiziko 2016 Slika 2. Odvisnost Hallove upornosti od magnetnega polja. Po viru [17]. konstant [11]: RH = 1 n h e20 , (3) kjer je h Planckova konstanta, e0 osnovni naboj, n pa celo število, glej sliko 2. Kasneje so v najčisteǰsih vzorcih opazili stopnice tudi pri vrednostih n, ki so ulomki z nizkim števcem in imenovalcem. Pojav kvantizacije pri celih n danes imenujemo celoštevilski kvantni Hallov pojav, pri racionalnih n pa racionalni kvantni Hallov pojav [5]. Številni teoretiki so prispevali k bolǰsemu razumevanju celoštevilskega kvantnega Hallovega pojava: nekateri so poudarili umeritveno invarianco, drugi robna stanja in nelokalni transport, pomembno vlogo nečistoč in ne- reda, tu pa nas bo najbolj zanimala topološka razlaga [20, 18], ki so jo prispevali David Thouless, Mahito Kohmoto, Peter Nightingale in Marcel den Nijs (TKNN) leta 1982. TKNN so v okviru teorije linearnega odziva zapisali izraz za prevodnost sistema, ki vsebuje prispevke vseh zasedenih stanj v Landauovem nivoju, ter pokazali, da je končni rezultat kvantiziran na celoštevilski mnogokratnik e20/h. Pasovno strukturo snovi namreč lahko opǐsemo z lastnimi energijami n in lastnimi funkcijami (Blochovimi stanji) ψn Hamiltonovega operatorja v odvisnosti od točke k v Brillouinovi coni recipročnega prostora, ki je tu dvodimenzionalen. Izraz, ki so ga izpeljali TKNN, pravzaprav meri, kako se »ukrivljajo« valovne funkcije v odvisnosti od k. To je izraženo preko Berryjeve zveze Aj(k) = −i 〈 ψk ∣∣∣ ∂ ∂kj ∣∣∣ψk〉 (4) 54–64 59 i i “Zitko” — 2017/6/30 — 13:13 — page 60 — #7 i i i i i i Rok Žitko Slika 3. Levo: cilindrični trak. Desno: Möbiusov trak. ter Berryjeve ukrivljenosti Fxy = ∂Ax ∂ky − ∂Ay ∂kx . (5) Integral F po Brillouinovi coni, ki je svitek (torus) T2 zaradi periodičnih robnih pogojev v obeh smereh, je matematično gledano topološka invarianta, imenovana prvo Chernovo število: C = − 1 2π ∫ T2 d2k F, C ∈ Z. (6) Različne pasovne strukture namreč lahko topološko klasificiramo tako, da se vprašamo, katere Hamiltonove operatorje lahko gladko preoblikujemo v druge, pod pogojem, da ima snov ves čas končno energijsko režo med zasedenimi in nezasedenimi stanji. Ekvivalenčni razredi se ločijo ravno po vrednosti C. Rečemo tudi, da je snov lahko v različnih topoloških fazah. Te se razlikujejo podobno, kot se med seboj razlikujeta cilindrični in Möbiusov trak (slika 3). Med topološko različnimi osnovnimi stanji lahko pride do topoloških faznih prehodov. Ker ti potekajo pri absolutni ničli (temperaturi T = 0), gre za posebno vrsto kvantnih faznih prehodov, torej za drugačen tip prehoda kot v teoriji Kosterlitza in Thoulessa, ki opisuje termične fazne prehode pri končni temperaturi. Zaradi topološkega izvora je število n = C celo število na devet decimalk natančno. Kvantni Hallov pojav torej omogoča določiti izjemno natančen standard za upornost: od leta 1990 je zato mednarodni standard za elek- trično upornost definiran ravno preko kvanta prevodnosti e20/h. Notranjost traku je izolatorska, tokovi pa tečejo po robovih brez disipacije, saj stanja, ki bi omogočila, da se elektroni na nečistočah odbijejo nazaj, sploh ne obsta- jajo. Danes takšnim stanjem snovi rečemo topološki izolatorji. Od običajnih 60 Obzornik mat. fiz. 64 (2017) 2 i i “Zitko” — 2017/6/30 — 13:13 — page 61 — #8 i i i i i i Nobelova nagrada za fiziko 2016 pasovnih izolatorjev se ločijo prav po od nič različnem Chernovem številu C, ki z vidika fizikalnih posledic ravno šteje, koliko prevodnih robnih stanj obstaja na meji sicer neprevodnega vzorca. Pomembno je na področju fizike Hallovega pojava prispeval tudi Duncan Haldane. Leta 1988 je pokazal, da lahko do podobnih pojavov pride tudi v odsotnosti zunanjega magnetnega polja [9]. Predlagal je model za grafen s periodičnim magnetnim fluksom skozi šesterokotnike. To je dosegel tako, da je v model vključil matrične elemente za preskoke med drugimi najbliž- jimi sosednjimi mesti, ki so kompleksne količine. Takšnega sistema v tistem času niso znali realizirati v laboratoriju. Je pa Haldane s tem delom zase- jal seme, iz katerega je v zadnjem desetletju zraslo celotno področje fizike topoloških izolatorjev. Model za kvantne spinske Hallove sisteme, ki se jih danes intenzivno proučuje, se da, denimo, približno razumeti kot dve kopiji Haldenovega modela, pri čemer imata spin gor in spin dol obratni vrednosti Chernovega števila. Nedavno, leta 2013, pa so tudi neposredno proučili fazo snovi, kot jo je predlagal Haldane, v tankih plasteh s kromom dopiranega (Bi,Sb)2Te3 v odsotnosti zunanjega magnetnega polja. Spinske verige in topološki člen θ Spinske verige so dolge enodimenzionalne verige magnetnih momentov, ki so med seboj sklopljeni preko izmenjalne interakcije. Primer je, denimo, Heisenbergov model: H = ∑ i JSi · Si+1, (7) kjer je Si spinski operator za i-to mesto verige v izbrani reprezentaciji za spin S = 1/2, 1, 3/2, . . ., J > 0 pa je antiferomagnetna Heisenbergova izme- njalna konstanta. Prava Néelova antiferomagnetna ureditev v eni dimenziji ni mogoča zaradi močnih fluktuacij. Najbolj raziskan je primer S = 1/2, ki je točno rešljiv z Bethejevim nastavkom. Za ta model je že dolgo znano, da ima kvaziurejeno osnovno stanje s potenčno upadajočimi korelacijami med magnetnimi momenti, vzbuditve pa so brez energijske reže, kar pomeni, da za dosti dolgo verigo obstajajo vzbujena stanja s poljubno majhno dodatno energijo [6]. Duncan Haldane se je v svojem delu iz leta 1983 vprašal [8], ali nemara obstaja kakšna fundamentalna razlika med verigami s polceloštevil- skim spinom 1/2, 3/2, . . . in tistimi s celoštevilskim spinom 1, 2, . . . Na to ga je navedel zapis nizkoenergijske efektivne kvantne teorije polja, ki se imenuje nelinearni model sigma s simetrijo O(3) in ki terja dodatni topološki člen θ v akciji. Slednji izvira iz potrebe po uvedbi Berryjeve faze, ko se spinske prostostne stopnje zapǐse s koherentnimi stanji pri konstrukciji teorije polja 54–64 61 i i “Zitko” — 2017/6/30 — 13:13 — page 62 — #9 i i i i i i Rok Žitko Slika 4. Levo: konfiguracija vektorjev v dvodimenzionalnem prostoru-času (x, t) z ovoj- nim številom Q = 1. Desno: prerez ob konstantnem času t = 0. v formalizmu integrala po poteh. Oba dela akcije lahko zapǐsemo kot SNLS = 1 2g ∫ dt dx [ 1 v ( ∂n ∂t )2 − v ( ∂n ∂x )2] , (8) Stop = i θ 4π ∫ d2xn · ( ∂n ∂x1 × ∂n ∂x2 ) , (9) kjer je n(x, t) enotski vektor, ki opisuje počasno spreminjanje medmrežnega spinskega polja, v je hitrost spinskih valov, g = 2/S sklopitvena konstanta, θ = 2πS in uporabljene so evklidske koordinate (x1, x2) = (it, x). V izrazu za topološki del akcije Stop je možno razbrati ovojno število Q krogelne lupine na krogelno lupino, π2(S 2), glej sliko 4. Različne spinske konfiguracije k statistični vsoti prispevajo s predfaktorjem ei2πSQ. Za celoštevilske S je ta faktor vedno 1, za polceloštevilske S pa je enak (−1)Q in obravnava postane veliko bolj zapletena. Kombinacija močnih kvantnih fluktuacij v eni dimenziji in možnost izničevanja različnih prispevkov zaradi topološkega člena za polceloštevilske spine vodi k velikim razlikam v obnašanju. Veljalo naj bi, da imajo celoštevilske verige končno energijsko režo in eksponentno upadanje spinskih korelacij, polceloštevilske pa so brez reže in korelacije padajo potenčno. V končno dolgih verigah s S ≥ 1 naj bi na obeh koncih verige obstajala robna stanja s spinom S − 1/2. To je še zlasti pomembno v verigah s celoštevilskim spinom, saj so to edine vzbuditve pri zelo nizkih energijskih skalah. Ker je Haldane do svojih sklepov prǐsel v limiti velikega spina, S →∞, se je postavilo vprašanje o njegovi splošnosti in veljavnosti za majhen spin. Haldanova domneva je bila zato sprva sprejeta z veliko mero skepticizma. Splošno sprejeta slika je namreč bila, da se spinske verige z različnim spinom 62 Obzornik mat. fiz. 64 (2017) 2 i i “Zitko” — 2017/6/30 — 13:13 — page 63 — #10 i i i i i i Nobelova nagrada za fiziko 2016 ne razlikujejo bistveno. Kmalu pa so se pojavili prvi posredni dokazi preko numeričnih simulacij ter tudi analitični argumenti. Ian Affleck, Tom Ken- nedy, Elliott Lieb in Hal Tasaki (AKLT) so predlagali točno rešljiv model za S = 1 [1]: HAKLT = ∑ i J [ Si · Si+1 + 1 3 (Si · Si+1)2 ] . (10) Dokazali so, da ima ta rahlo modificirani Heisenbergov model končno ener- gijsko režo, eksponentno upadanje korelacij ter da obstajajo robna stanja s spinom 1/2 (kar je lep primer frakcionalizacije kvantnih števil, saj imajo osnovne vzbuditve sicer spin 1), vse torej v skladu s Haldanovo domnevo. Kasneje so napovedana robna stanja v celoštevilskih spinskih verigah zaznali tudi v eksperimentih na CsNiCl3 [10]. Sklep: topologija v sodobni statistični fiziki Nobelovi nagrajenci za fiziko v letu 2016 so kot prvi pokazali, da lahko sta- nja snovi razvrščamo ne zgolj po njihovih simetrijskih lastnostih, temveč tudi po topoloških. S tem so odprli nov pogled na razlikovanje med fazami in na prehode med njimi. V zadnjih letih se veliko pozornosti posveča topo- loškim izolatorjem in superprevodnikom [4, 3]. Med slednje se uvršča model verige Kitaeva, ki je ob ustrezni izbiri parametrov topološki superprevodnik s simetrijo p, za katerega je znano, da ima na svojih robovih robni stanji, ki se obnašata kot Majoranova fermiona. Oba skupaj se obnašata kot dvo- nivojski sistem, v katerega lahko shranimo en kubit podatkov. Ker pa sta Majoranova fermiona lokalizirana vsak na svojem koncu verige, sta imuna na motnje iz bližnje okolice. Zaradi tega se pričakuje, da lahko v takšnih sistemih na robusten način hranimo kvantno informacijo in da jo bomo v prihodnje morda lahko celo obdelovali. To bi bila lahko osnova za topološko kvantno računalnǐstvo [19]. LITERATURA [1] I. Affleck, T. Kennedy, E. H. Lieb in H. Tasaki, Rigorous results on valence-bond ground states in antiferromagnets, Phys. Rev. Lett. 59 (1987), 79. [2] A. Altland in B. Simons, Condensed matter field theory, Oxford University Press, 2010. [3] J. K. Asbóth, L. Oroszlány in A. Pályi, A short course on topological insulators, Springer, 2016. 54–64 63 i i “Zitko” — 2017/6/30 — 13:13 — page 64 — #11 i i i i i i Rok Žitko [4] B. A. Bernevig, Topological insulators and topological superconductors, Princeton Uni- versity Press, 2013. [5] Z. F. Ezawa, Quantum Hall effects, World Scientific, 2008. [6] T. Giamarchi, Quantum physics in one dimension, Oxford University Press, 2003. [7] Z. Hadzibabic, P. Krüger, M. Cheneau, B. Battelier in J. Dalibard, Berezin- skii–Kosterlitz–Thouless crossover in a trapped atomic gas, Nature, 441 (2006), 1118. [8] F. D. M. Haldane, Nonlinear field theory of large-spin Heisenberg antiferromagnets: Semiclassically quantized solitons of the one-dimensional easy-axis neel state, Phys. Rev. Lett. 50 (1983), 1153. [9] F. D. M. Haldane, Model for a quantum Hall effect without Landau levels: Condensed- matter realization of the »parity anomaly«, Phys. Rev. Lett. 61 (1988), 2015. [10] M. Kenzelmann, R. A. Cowley, W. J. L. Buyers, Z. Tun, R. Coldea in M. Enderle, Properties of Haldane excitations and multiparticle states in the antiferromagnetic spin-1 chain compound CsNiCl3, Phys. Rev. Lett. 66 (2002), 024407. [11] K. von Klitzing, G. Dorda in M. Pepper, New method for high-accuracy determination of the fine-structure constant based on quantum Hall resistance, Phys. Rev. Lett. 45 (1980), 494. [12] J. M. Kosterlitz in D. J. Thouless, Ordering, metastability and phase transitions in two-dimensional systems, J. Phys. C: Solid State Physics 6 (1973), 1181. [13] J. M. Kosterlitz, The critical properties of the two-dimensional XY model, J. Phys. C: Solid State Physics 7 (1974), 1046. [14] N. D. Mermin in H. Wagner, Absence of ferromagnetism or antiferromagnetism in one- or two-dimensional isotropic Heisenberg models, Phys. Rev. Lett. 17 (1966), 1133. [15] M. Nakahara, Geometry, topology and physics, Taylor and Francis, 2003. [16] D. R. Nelson in J. M. Kosterlitz, Universal jump in the superfluid density of two- dimensional superfluids, Phys. Rev. Lett. 39 (1977), 1201. [17] M. Paalanen, D. Tsui in A. Gossard, Quantized Hall effect at low temperatures, Phys. Rev. B 25 (1982), 5566. [18] Q. Niu, D. J. Thouless in Y.-S. Wu, Quantized Hall conductance as a topological invariant, Phys. Rev. B 31 (1985), 3372. [19] J. K. Pachos, Introduction to topological quantum computation, Cambridge University Press, 2012. [20] D. J. Thouless, M. Kohmoto, M. P. Nightingale in M. den Nijs, Quantized Hall conductance in a two-dimensional periodic potential, Phys. Rev. Lett. 49 (1982), 405. [21] F. Wegner, Spin-ordering in a planar classical Heisenberg model, Z. für Physik 206 (1967), 465. [22] X.-G. Wen, Quantum field theory of many-body systems, Oxford University Press, 2004. http://www.dmfa-zaloznistvo.si/ 64 Obzornik mat. fiz. 64 (2017) 2 i i “RazpetNada” — 2017/6/30 — 8:02 — page 65 — #1 i i i i i i NOVE KNJIGE Christian Ucke in Hans Joachim Schlichting, Spiel, Physik und Spaß, Physik zum Mitdenken und Nachmachen, Sachbuch, Wiley– VCH Verlag GmbH & Co. KGaA, 2011, 146 strani. Udeležencem mednarodnih fizikalnih semi- narjev in konferenc o poučevanju fizike je Christian Ucke dobro znan predvsem po prikazovanju zanimivih fizikalnih poskusov in razlagi delovanja fizikalnih igrač. Prav o teh igračah in uporabi vsakdanjih predme- tov pri poučevanju fizike je govor v pričujoči knjigi. Najprej nekaj o avtorjih. Dr. Christian Ucke je dokončal študij fizike v Göttingenu in Münchnu. V doktoratu na LMU (Uni- verzi Ludwiga Maximiliana) v Münchnu se je posvetil temi »sipanje svetlobe v očesu«. Za drugi študij je izbral pedagogiko in psi- hologijo. Od 2001 do 2007 je bil vodja fizi- kalnega praktikuma za fizike na Fakulteti za fiziko TU (Tehnǐske univerze) v Münchnu in od 2003 do 2006 poobla- ščenec univerze za spodbujanje poučevanja. Leta 2001 je dobil nagrado za dobro poučevanje, ki jo podeljuje Bavarsko ministrstvo za izobraževanje, kulturo, znanost in umetnost. Dr. Hans Joachim Schlichting je študiral fiziko v Hamburgu in tam tudi doktoriral. Študiral je tudi pedagogiko in psihologijo. Nekaj let je vodil Inštitut za didaktiko fizike, ki je deloval v okviru univerze v Münstru, in bil nekaj let vodja odseka za didaktiko fizike pri nemškem fizikalnem društvu. Vedno se zavzema za sodobneǰsi pouk fizike v šolah in povezavo fizike z vsakdanjimi izkušnjami. Profesor Schlichting je leta 2008 prejel nagrado Roberta Wicharda Pohla, ki jo podeljuje nemško fizikalno društvo za izjemne dosežke na področju didaktike fizike oziroma eksperimentalne fizike. Glede uporabe vsakdanjih pripomočkov in igrač pri poučevanju fizike so mnenja deljena. O tem pǐseta avtorja tudi v uvodu knjige. Po mnenju neka- terih so igrače in vsakdanji pripomočki dober uvod v raziskovalno delo, saj motivirajo učence, jih vzpodbujajo k pozorneǰsemu opazovanju, samostoj- nemu raziskovanju, zastavljanju vprašanj in logičnemu sklepanju. Drugi pa menijo, da igrače preusmerjajo pozornost in da se z njimi ne da sistematično obdelati določenih fizikalnih pojmov in povezav med fizikalnimi količinami, skratka, da se učenci z njimi le igračkajo in se ob tem bolj malo naučijo. Obzornik mat. fiz. 64 (2017) 2 65 i i “RazpetNada” — 2017/6/30 — 8:02 — page 66 — #2 i i i i i i Nove knjige Slika 1. Vrtavka, ki se iz začetnega položaja, ko je krogelni del navzdol, med vrtenjem obrne. Pitagorova čaša in lava lučka. Kljub temu pa se v šolah, ne le pri nas, ampak tudi v svetu, vsaj ob poseb- nih priložnostih tudi pri pouku fizike obravnava delovanje nekaterih igrač in vsakdanjih naprav. Z nekaterimi od njih so se igrali tudi zelo priznani znanstveniki, kot na primer Albert Einstein, ki je med drugim zapisal: »Igra je najvǐsja oblika raziskovanja«. Avtorja sta izbrala 44 igrač in predmetov (v nadaljevanju bomo oboje označili z besedo predmet) in jih predstavila na dva različna načina. Ve- dno je najprej na začetku fotografija, sledita opis in skica predmeta. Potem pa je včasih v ospredju eksperimentalni vidik, s kvalitativnim opisom pove- zav med fizikalnimi količinami in nekaj skicami, včasih pa opisu sledi širše teoretično ozadje z enačbami, grafi in tabelami, ki pojasnjujejo dogajanje. Za nekatere predmete navedeta avtorja tudi zgodovino razvoja in njihove iznajditelje ali pa omenita, kateri noveǰsi stroji in pripomočki delujejo po enakem ali podobnem principu. Vedno pa želita avtorja na vabljiv način pritegniti bralca, da bi sam preizkusil delovanje opisanih predmetov in se ob tem na igriv način seznanil z nekaterimi fizikalnimi količinami in povezavami med njimi. Knjiga je razdeljena na 5 poglavij: mehanika, termodinamika, elektro- magnetizem, optika in dodatki. V vsakem poglavju je navedenih nekaj pred- metov, ki jih lahko povežemo z eno od poglavij fizike. Najobsežneǰse je prvo poglavje: Mehanika. Zajema 25 predmetov, kot so: verižica iz sponk za papir, Sakajeva vrtavka iz sponke za papir1, vrtenje obročev, valji in krogle, vrtavka, ki se med vrtenjem obrne na glavo, čoln, ki se nekaj časa vrti v eno, nato pa v drugo smer, vetrnice, vrtopir in javorjeva semena, dvojni stožec, ki se navidezno giblje po klancu navzgor, gibanje dveh majhnih, med seboj pravokotnih krožnih ploščic, krtača na motor, 1Christian Ucke, Sakejeva vrtavka iz sponke za papir, prevod Seta Oblak, Fizika v šoli, 7, 2, december 2001, 117–119 66 Obzornik mat. fiz. 64 (2017) 2 i i “RazpetNada” — 2017/6/30 — 8:02 — page 67 — #3 i i i i i i Spiel, Physik und Spaß vzmeti, detel na palici, peščena ura, Pitagorova čaša2, trenje orehov, model atoma, pojoči kozarci. Termodinamika zajema naslednje predmete: žejno raco, preprost termo- meter, Goethejev termometer, Galilejev termometer, lava lučko, vetrnico na vroč zrak, igrače z bimetalom (prevesna gugalnica s svečo). Elektromagnetizem ima le tri primere: preprost elektromotor, magnetne vrtavke in magnetni top. Optika: preslikave s cilindričnim zrcalom, kitajsko čudežno zrcalo, mi- rage (dvojno konkavno zrcalo), kavstika v skodelici kave, lom svetlobe in ma- vrične barve, oko in barve, oko in prostorsko gledanje (tudi anaglifne slike), barvne vrtavke, opazovanje barv pri vrtenju črno-belih ploskev, igranje s steklenim kozarcem z vodo. Posebej zanimivi deli poglavja iz optike so povezani z uporabo plastičnih folij (leč), katerih spodnja plast je ravna. Folija, pri kateri je prečni pre- sek žagast (prizmatičen), ustvari stereoskopsko sliko zaradi razlik v lomnih količnikih različnih valovnih dolžin. Rdeče obarvani predmeti se nam zdijo bližje, modri pa bolj oddaljeni. Posebej lepe so slike, ki imajo v ozadju vodo ali nebo (modro barvo), spredaj pa rdeče predmete. Z ustreznim barvnim tiskom dobimo občutek prostora. Podoben učinek lahko seveda dosežemo tudi z anaglifnimi slikami. Sliki za desno in levo oko sta prekriti in različnih barv. Rdeče obarvane črte so namenjene gledanju z desnim, modro obar- vane pa z levim očesom (ali obratno). Za gledanje slik zato potrebujemo očala z rdečim in modrim filtrom. Zgornja ploskev folije (leče) je lahko valovita (podobno kot pri valoviti lepenki). Ko na lečo gledamo pod različnimi koti, se povečajo različni deli slike. Linijsko rastersko tehniko uporabljajo tudi pri tiskanju, z njo ustva- rijo globinsko predstavo oziroma omogočijo, da izginejo določeni deli slike oziroma ustvarijo vtis gibanja. Že v preteklosti so znali ustvariti podobe, sestavljene iz dveh samostojnih slik. Na osnovno ploskev so pritrdili letvice s trikotnim presekom (enakostranični trikotnik). Na desne strani trikotnikov so narisali eno sliko (princeso), na leve strani pa drugo (princa). Ko so gledali naravnost, so videli sestavljeno sliko, ko pa so gledali z leve oziroma z desne, so videli princeso oziroma princa. Večina takih slik je obešena v muzejih. Tako sliko lahko ustvarimo tudi z letvicami, ki imajo namesto trikotnega pravokoten prerez. Nekaj več prostora je namenjenega tudi obravnavi vrtenja črno-belih krogov z različnimi vzorci, ki jih nataknemo na vrtavko. Ko se vrtavke vrtijo, opazimo barvne lise. S predstavljenimi predmeti se lahko igrajo tako predšolski otroci kot študentje in učitelji. Le vprašanja, razlage in miselni procesi potekajo na različnih ravneh. Nada Razpet 2Nada Razpet, Pitagorova čaša, Presek, 37, 1, 2009/10, 13–14 Obzornik mat. fiz. 64 (2017) 2 67 i i “Legisa-vesti” — 2017/6/30 — 9:01 — page 68 — #1 i i i i i i ZANIMIVOSTI STRNJENO VZORČENJE Uvod Za razumevanje nove metode strnjenega vzorčenja (snemanja, zajemanja), ki ji v angleščini pravijo compressed sensing, compressive sampling, si najprej oglejmo nekaj dejstev o digitalizaciji slik, zvoka . . . Pri tem bomo spoznali matematična orodja, ki nastopajo tudi v novi metodi zajemanja signalov. Stiskanje Digitalne fotografije v surovi obliki vsebujejo informacijo o intenziteti treh osnovnih barv za vsak piksel posebej. To pomeni množico podatkov. Zato pred posredovanjem fotografij že kamera ali pa naknadno uporabnik foto- grafijo stisne, navadno v zelo uspešni in razširjeni JPEG format, ki tudi nima problemov s patenti. Večinoma lahko stisnemo za faktor 4 praktično brez izgube podrobnosti. Tudi stisk za faktor 10 daje navadno zelo do- bre rezultate. Na slikah imamo namreč pogosto večje površine (kot modro nebo), kjer ni podrobnosti. Tako lahko na sliki najdemo pravokotnike, ki so približno enakomerno obarvani. Tak del slike lahko podamo z mnogo manj podatki. Izvedba tega stiskanja je nekoliko zapletena in matematično zanimiva. Zaradi enostavnosti privzemimo, da imamo črno-belo sliko. Denimo, da kamera daje 8 bitov informacije o osvetljenosti piksla. Torej imamo 28 = 256 odtenkov sivine, od povsem črne (0) do povsem bele (255). Razdelimo sliko na pravokotnike velikosti 8× 8 pikslov. Tak del slike podamo najprej z od- stopanji svetlosti pikslov od vrednosti 27 = 128. Dobimo matriko velikosti 8×8, ki jo imamo lahko tudi za vektor v R64. Na matriki opravimo dvorazse- žno diskretno kosinusno transformacijo, DCT. Gre za razvoj po ortogonalni bazi. V baznih matrikah nastopajo kosinusi, zelo podobno kot pri klasičnem razvoju v Fourierovo vrsto. Enorazsežna DCT deluje na prostoru RN tako, da vektorju x = (x(0),x(1), . . . ,x(N−1)) priredi vektor X v istem prostoru po formuli X(k) = N−1∑ j=0 x(j) cos ( π N ( (j + 1 2 ) k ) . 68 Obzornik mat. fiz. 64 (2017) 2 i i “Legisa-vesti” — 2017/6/30 — 9:01 — page 69 — #2 i i i i i i Strnjeno vzorčenje Formula za dvorazsežno transformacijo je seveda obsežneǰsa in si jo lahko ogledate na Wikipediji. DCT je v tesnem sorodu z diskretno Fourierovo transformacijo (DFT), le da so koeficienti pri razvoju po DCT realni. DFT vsakemu vektorju x ∈ CN priredi vektor x̂ v istem prostoru, tako da je x̂(k) = N−1∑ j=0 x(j) exp (−2πkj N ) . Za izvedbo DFT pri velikih N imamo odličen algoritem, imenovan hitra Fourierova transformacija – FFT, ki jo mnogi dobro poznate. Vrnimo se k naši 8 × 8 matriki osvetljenosti pikslov. Dvorazsežna dis- kretna kosinusna transformacija da novo 8 × 8 DCT matriko iz DCT ko- eficientov. Koeficient z indeksom (0, 0) je povprečje vrednosti elementov originalne matrike. Na tej stopnji lahko iz DCT matrike rekonstruiramo originalno matriko. Ampak koeficienti z majhnima indeksoma so najpomembneǰsi, ker po- dajajo dele slike, ki najbolj padejo v oči. Na tipični sliki so elementi DCT matrike z vǐsjimi indeksi majhni v primerjavi z elementi zgoraj levo, saj ni veliko visokofrekvenčnih elementov na sliki. Težko recimo pričakujemo, da bomo na sliki imeli močno komponento z indeksom (6, 5) v obliki nekakšne modificirane šahovnice s 7×6 polji, kot si lahko ogledate v ilustracijah baze za DCT na [1, str. 15]. Na 8× 8 pikslov velikem delu modrega neba bo po absolutni vrednosti daleč največji element z indeksom (0, 0). Zdaj naredimo kvantizacijo. To je enostaven in grob postopek, ki odseka najmanj pomembne informacije in večinoma zmanǰsa natančnost preostalih podatkov. Obstajajo posebne kvantizacijske matrike, dobljene izkustveno. Elementi kvantizacijske matrike so naravna števila in večinoma naraščajo, ko se gibljemo desno in navzdol po matriki. V literaturi najdemo standardno kvantizacijsko matriko Q. Matrika Q ima vrednost 16 na mestu (0, 0), 121 na mestu (6, 5) in 99 na mestu (7, 7) – glej [2, str. 4] ali [1, str. 20]. Elemente DCT matrike delimo z istoležnimi elementi kvantizacijske ma- trike, odvržemo decimalke. Prav tako vse vrednosti nad 255 porežemo na 255. Podobno naredimo z vrednostmi pod −255. (Angleški izraz za rezanje je clip.) Gre za agresivno zmanǰsanje in pogosto eliminacijo že tako majhnih visokofrekvenčnih komponent ter zmanǰsanje velikosti elementov kvantizi- rane matrike. Elementi v kvantizirani matriki so do predznaka predstavljeni z največ 8 biti. To je bistven korak na poti do stisnjene JPEG slike. Za- Obzornik mat. fiz. 64 (2017) 2 69 i i “Legisa-vesti” — 2017/6/30 — 9:01 — page 70 — #3 i i i i i i Zanimivosti vrgli smo del informacije na originalni sliki (večinoma nezanimivi del), se zadovoljili s približki nekaterih drugih podatkov in originala ne moremo več natančno rekonstruirati. Na tipični sliki ima kvantizirana matrika mnogo ničel, predvsem v desnem spodnjem delu. Zgoraj omenjena matrika Q obi- čajno sliko stisne za faktor približno 7. Matriki, v kateri je večina elementov ničelnih, preostali pa nimajo posebne strukture, rečemo razpršena matrika. Kvantizirana matrika je torej praviloma razpršena. V fotoaparatu z velikim senzorjem (APS-C ipd.) nastavitev na fino (an- gleško fine) da kvantizacijsko matriko z bistveno manǰsimi elementi, velikosti recimo od 1 do 6. To pomeni nižjo kompresijo, nekako za faktor 2. Pri malih tipalih z diagonalo pod 8 mm bo kvantizacijska matrika v načinu fine imela elemente recimo od 1 do 15, saj ustrezne optike običajno nimajo zelo dobre ločljivosti. Pri dekodiranju pomnožimo matriko nazaj z istoležnimi elementi kvan- tizacijske matrike in opravimo inverzno transformacijo k DCT. Dobimo pri- bližek prvotne slike našega kvadrata. Na slikah z mehkimi prehodi med svetlimi in temnimi deli slike to deluje sijajno. Algoritem za JPEG stiska- nje je računsko nezahteven, hiter in robusten. Manǰsi problem se pojavi pri slikah z ogromno podrobnostmi, kot so trava, krzno. Bolǰse kamere tako sliko prepoznajo in bistveno manj stisnejo, se pravi uporabijo drugo kvan- tizacijsko matriko kot sicer. (Slika z ogromno šuma je tudi težava, vendar pa tu nismo zainteresirani za podrobno reprodukcijo.) Pri poceni kamerah pa lahko kombinacija nekakovostnega zoom objektiva in neprilagodljivega stiskanja travnik spremeni v zeleno plundro. JPEG tudi ni najbolǰsi za re- produkcijo grafičnih podrobnosti. Za manǰse risbe in grafike profesionalci raje uporabljajo format PNG. Za zvok je nastal na podlagi JPEG priljubljeni, za zdaj še patentirani format MP3. Omogoča stiskanje v različnih kakovostih. Zelo dober za kompresijo zvoka je tudi prostokodni format (Ogg) Vorbis. Vzorčenje in digitalizacija Nekateri študenti na izpitih rǐsejo grafe funkcij »po točkah«. Večinoma se to ne obnese. Vendar pa je mogoče velik razred funkcij popolnoma rekonstru- irati iz njihovih vrednosti na diskretni množici točk. V knjigi [3] najdemo na str. 373 izrek, ki ga ni težko dokazati: Izrek 1. Naj bo f ∈ L2(R) zvezna in naj bo njena Fourierova transformi- ranka f̂ enaka 0 zunaj intervala [−L,L], kjer je L > 0. Potem je f določena 70 Obzornik mat. fiz. 64 (2017) 2 i i “Legisa-vesti” — 2017/6/30 — 9:01 — page 71 — #4 i i i i i i Strnjeno vzorčenje z vrednostmi (= vzorci) v točkah{ n 2L ;n ∈ Z } takole: f(t) = ∞∑ n=−∞ f ( n 2L )sin(2Lπt− nπ) 2Lπt− nπ . (1) Našo funkcijo f torej lahko rekonstruiramo iz njenih vrednosti = vzor- cev v točkah, medsebojno oddaljenih za intervalček ∆t = 1/(2L), ki mu pravimo Nyquistov interval. V eni sekundi torej vzorčimo 2L-krat, in to je Nyquistova frekvenca. Knjiga pravi, da izrek iz leta 1915 pripada E. T. Whittakerju. Kakšna je Fourierova transformiranka dušenega kosinusnega vala f(t) = exp(−bt2) cos(2πνt) s krožno frekvenco ω = 2πν? Če je b majhen (tako da je val opazen dalj časa), je lahko izračunati, da ima f̂ dva ozka vrhova v ±ν in je bolj ali manj koncentrirana okrog teh dveh točk. Čim manǰsi je b, tem bolj izraziti sta ti konici. Če je ν nekoliko manǰsi od L, je f̂ praktično enaka nič zunaj intervala [−L,L]. Ker je f ∈ L2(R), približno zadošča pogojem izreka. Tako laže razumemo znameniti Shannonov izrek (1948), ki poenostavljeno pravi: za vzorčenje signala, ki vsebuje le frekvence pod ν, moramo vzorčiti vsaj s frekvenco 2ν. Podobne rezultate so že prej dokazali drugi matematiki: Kotelnikov leta 1933 . . . Ljudje navadno ne slǐsimo zvokov nad 20 kHz. Torej moramo za dobro digitalizacijo glasbe najprej odfiltrirati vse zvoke s frekvenco nad 20 kHz in nato vzorčiti s frekvenco več kot 40 kHz. Za CD kakovost vzorčimo s frekvenco 44,1 kHz. To nam omogoča, da iz vzorčenega signala verno rekonstruiramo (sfiltrirani) original. Pri digitalni telefoniji vzorčimo le z 8 kHz, saj so telefoni konstruirani za frekvenčno območje od 300 Hz do 3,4 kHz. To je bolj zasilna rešitev, saj človeški glas sega nekako od 60 Hz do 14 kHz. Gosteǰse vzorčenje in bolǰso kakovost zvoka že zdaj ponuja Skype. Uvajajo se tudi nove rešitve kot HD Voice (vzorčenje s 16 kHz). Aliasing Če vzorčimo s premajhno frekvenco, lahko pride do problemov, ki jih opi- šemo z angleško besedo aliasing. Pri tem se lahko sinusoida v originalu reproducira po digitalizaciji kot sinusoida s povsem drugo frekvenco. Ori- ginalna sinusoida dobi torej svoje drugo življenje – svoj alias, ki pa nam Obzornik mat. fiz. 64 (2017) 2 71 i i “Legisa-vesti” — 2017/6/30 — 9:01 — page 72 — #5 i i i i i i Zanimivosti Slika 1. Funkciji f(x) = sin(2πx) (prekinjena črta) in g(x) = − sin((2/3)πx) (polna črta) se ujemata v točkah { 3k 4 ; k ∈ Z } . dela le težave. Pomislite recimo na funkcijo x 7→ sin(2πx). Tu je ν = 1. Denimo, da jo vzorčimo s korakom 0,5. Če začnemo v x = 0, so vsi vzorci enaki 0. Rekonstrukcija signala iz teh vzorcev nam da napačen rezultat – funkcijo, ki je identično enaka 0. Če našo sinusoido vzorčimo s korakom 3/4 in začnemo v 0, vzorci ustrezajo tudi funkciji x 7→ − sin((2/3)πx), kot vidimo na sliki 1. Pri rekonstrukciji vzorčenega signala bomo v tem primeru dobili alias prvotnega signala v obliki funkcije z eno tretjino frekvence origi- nala in z drugačno fazo, se pravi spet povsem napačen rezultat. Za pravilno rekonstrukcijo moramo vzorčiti s korakom, manǰsim od 0,5. Kaj pa, če ne bi vzorčili v enakomernih presledkih, ampak v slučajno izbranih točkah? V tem primeru tudi pri vzorčenju s korakom, dalǰsim od 0,5, skoraj gotovo ne bi prǐsli do gornjih napačnih rezultatov. V digitalni fotografiji se problemom z aliasingom poskušajo izogniti z anti-aliasing (AA) filtri pred senzorjem. Ti zameglijo (sfiltrirajo) preveč drobne detajle, a obenem malce zmanǰsajo kakovost slike. Efekte aliasinga v fotografiji navadno označimo s francosko besedo moiré, ki jo izgovorimo kot muaré. Strnjeno vzorčenje Vzorčenje s slučajnim korakom je ena od idej za t. i. strnjeno vzorčenje, an- gleško compressed sensing, compressed sampling. Začetek tega sega 72 Obzornik mat. fiz. 64 (2017) 2 i i “Legisa-vesti” — 2017/6/30 — 9:01 — page 73 — #6 i i i i i i Strnjeno vzorčenje v sedemdeseta leta preǰsnjega stoletja, kot lepo opisuje poljudno napisani vir [4]. Geologi, ki so iskali nafto, so eksperimentalno ugotovili, da lahko dobijo želeno sliko zemeljskih slojev z mnogo manj seizmičnimi meritvami, kot bi jih bilo treba po teoriji. To je bila seveda super novica, saj je pov- zročanje mini potresov z eksplozivi moteče. Razložili so si zadevo s tem, da so posamezni sloji precej homogeni. Zanimale so jih le meje med sloji, ki so na instrumentih dajale špice, in pa prisotnost sloja, ki bi lahko vseboval nafto. Skratka, zanimalo jih je le majhno število pomembnih informacij. V devetdesetih letih so metode geologov začeli preučevati matematiki, med njimi David Donoho z Univerze Stanford. Magnetna resonanca (MR) je odlična, ampak draga metoda za slikanje mehkih tkiv. Francoski matematik Emmanuel Candès s Caltecha in njegov mentor pri doktoratu Donoho sta oba začela ugotavljati, da lahko dobita dobre MR slike vzorcev tudi s precej manj posnetki, kot jih predvideva teorija, če vzorčita nekoliko drugače. Kot pri običajnih fotografijah tudi pri MR navadno ni vse na sliki zanimivo. Kot smo videli zgoraj, lahko digitalno sliko ali zvok skoraj zmeraj močno stisnemo z minimalno izgubo kakovosti. Ampak najprej zajamemo čisto vse podatke, da se nato odločimo, kako jih bomo stisnili. Podobno dobri slikarji lahko hitro prepoznajo bistvo portretiranca ali naravne scene in ga podajo z nekaj potezami. Pri strnjenem vzorčenju želimo že vnaprej zajeti manj podatkov, kot jih zahteva Shannonov pogoj. Metoda deluje le takrat, ko ǐsčemo majhno število informacij. Spomnimo se na naslednji problem. Imamo 9 kovancev, med katerimi jih ima 8 enako maso, eden pa je lažji. Le z dvema tehtanjema s staromodno ravnovesno tehtnico, brez uteži, lahko izločimo lažji kovanec, če se tega lotimo pravilno. Candès pripoveduje, da je imel na konferencah ob predstavitvi svojih rezultatov težave, ker so nekateri mislili, da malce prireja rezultate. Poskušal je stvari strogo dokazati, pa se mu je po prvih uspehih zataknilo. Naključje je hotelo, da je Candès imel otroka v isti mali šoli kot Terence Tao z UCLA. (Tao je nekaj let kasneje, 2006, dobil Fieldsovo medaljo). Francoz je Tau zaupal svoje probleme, a mu sogovornik sprva ni verjel in mu je obljubil nasprotni primer za njegove trditve. Tega pa ni mogel najti, zato je stvar vzel resneje, začel sodelovati s Candèsom in prispeval manjkajoči dokaz. Z njima je delal Justin Romberg z Georgia Tech. Preprint njihovih rezultatov je izšel leta 2004, obenem pa je Donoho oznanil podobna dognanja. Obzornik mat. fiz. 64 (2017) 2 73 i i “Legisa-vesti” — 2017/6/30 — 9:01 — page 74 — #7 i i i i i i Zanimivosti Na kratko bom povzel Taovo predavanje [5] iz leta 2009. Rekonstruirati želimo signal x dolžine N , kjer je N ogromen, denimo reda velikosti 106. Za x vemo poleg tega, da je s-razpršen, kar pomeni, da ima največ s koordinat od 0 različnih. Tu je s mnogo manǰsi kot N , kar pǐsemo s  N . Imamo poddoločen sistem m linearnih enačb za x v obliki Ax = b. Tu je b vektor meritev in m < N . Vemo, da ima tak sistem poleg našega signala neskončno rešitev. Trditev 2. Privzemimo, da je vsakih 2s stolpcev matrike A linearno neod- visnih. Če je signal x s-razpršen in zadošča sistemu Ax = b, je ta signal edina s-razpršena rešitev tega sistema. Dokaz. Denimo, da ima sistem še eno s-razpršeno rešitev x′. Vzemimo vektor w = x−x′. Ta vektor ima največ 2s koordinat od 0 različnih. Velja Aw = 0. Toda produkt na levi je enak w(1) krat prvi stolpec matrike A+ . . ., kjer sumacija poteka po neničelnih koordinatah za w, torej ima ta linearna kombinacija največ 2s sumandov. Iz predpostavke sledi, da so vsi w(i) enaki 0 in tako w = 0. Predpostavka trditve pomeni, da je število m vrstic v matriki A vsaj 2s, se pravi, da je meritev vsaj 2s. Posledica 3. Signal x je tista rešitev sistema Ax = b, ki ima najmanj neničelnih koordinat. To je zelo lep rezultat, žal pa je iskanje najbolj razpršene rešitve nume- rično izredno zahtevno. V splošnem je to NP-težak problem. Izkazalo pa se je, da namesto tega lahko ǐsčemo rešitev, za katero bo vsota absolutnih vrednosti koordinat (se pravi `1–norma) vektorja x minimalna. Tej me- todi iskanja rešitve so nadeli angleško ime basis pursuit. Gre za konveksno optimizacijo, ki se je lahko lotimo z metodami linearnega programiranja. Rezultati teorije so tesno povezani z verjetnostjo. Naslednji izrek so Can- dès, Romberg in Tao objavili v IEEE Transactions on Information Theory leta 2006: Izrek 4. Izberimo naključno števila k1, k2, . . . , km iz množice {0, 1, . . . , N − 1}. Obstaja taka konstanta C, da lahko pri pogoju m > Cs lnN z verjetnostjo blizu 1 vsak s-razpršen vektor x ∈ CN rekonstruiramo iz vrednosti diskretnih Fourierovih koeficientov x̂(ki), kjer i teče od 1 do m. 74 Obzornik mat. fiz. 64 (2017) 2 i i “Legisa-vesti” — 2017/6/30 — 9:01 — page 75 — #8 i i i i i i Strnjeno vzorčenje Normalno bi za rekonstrukcijo potrebovali vseh N Fourierovih koeficien- tov. Numerični poskusi sugerirajo, da lahko večinoma rešitev dobimo točno celo pri pogoju, da je meritev vsaj 4s. Metoda deluje pri precej širokem razredu matrik, ne samo pri matriki za diskretno Fourierovo transformacijo. Tu močno pomaga dejstvo, da je N ogromen. Metodo lahko razširimo tudi na primer, da je signal samo približno raz- pršen; v tem primeru dobimo približno rešitev. Če je meritve pokvaril šum, se pravi, da imamo enačbo Ax = b + z, kjer je z šum, bo naša metoda dala približek rešitve. Teorija je zelo zanimiva. Manǰsi problem je, da je metoda računsko precej zahtevna. Konec novembra 2016 je Siemens oznanil, da začenja prodajo opreme za magnetno resonančno (MR) slikanje, ki sloni na strnjenem vzorčenju. Namenjena je slikanju delovanja srca. Po reklami v 25 sekundah naredi tisto, za kar so potrebovali prej do 6 minut. Pacient mora samo enkrat zadrževati dih, namesto desetkrat do štirinajstkrat pri preǰsnjem postopku. Obdelava podatkov poteka v sami napravi. Skrčitev morda ne gre samo na račun strnjenega vzorčenja, ampak tudi drugih algoritemskih in inženirskih izbolǰsav. Prve verzije te inovacije so v uporabi že vsaj leto dni v uglednih bolnǐsnicah, tako da stvar deluje. Siemens obljublja, da bo kmalu ponudil podobne naprave tudi v druge namene. Strnjeno vzorčenje je lahko uporabno marsikje, kjer so senzorji zelo dragi. Verjetno se bo strnjeno vzorčenje pojavilo tudi pri računalnǐski to- mografiji (CT) in zmanǰsalo velike doze sevanja. LITERATURA [1] A. Bruna, JPEG, Catania, 2008, dostopno na www.dmi.unict.it/~battiato/EI_ MOBILE0708/JPEG\%20(Bruna).pdf, ogled: 6. 4. 2017. [2] K. Cabeen in P. Gent, Image compression and the discrete cosine transform, Math 45, College of the Redwoods, dostopno na www.math.cuhk.edu.hk/~lmlui/dct.pdf, ogled: 6. 4. 2017. [3] G. Bachmann, L. Narici in E. Beckenstein, Fourier and wavelet analysis, Universitext, Springer-Verlag, New York, 2000. [4] D. Mackenzie, Compressed sensing makes every pixel count, What’s Happening in Mathematical Sciences 7 (2009), 114–127, dostopno na www.ams.org/samplings/ math-history/hap7-pixel.pdf, ogled: 6. 4. 2017. [5] T. Tao, Compressed sensing or: the equation Ax = b revisited, Mahler lecture 2009, dostopno na www.math.hkbu.edu.hk/~ttang/UsefulCollections/ compressed-sensing1.pdf, ogled: 6. 4. 2017. Peter Legǐsa Obzornik mat. fiz. 64 (2017) 2 75 i i “Kuzman” — 2017/6/30 — 9:03 — page 76 — #1 i i i i i i VESTI »MAϕJSKI VIKEND« – ALI KAKO SI SPOZNAL SVOJE BODOČE KOLEGE Med 27. in 29. januarjem 2017 je na Fakulteti za matematiko in fiziko v Ljubljani potekala zimska šola za dijake, imenovana Maϕjski vikend. Srečanje je 35 dijakom iz vse Slovenije ponudilo sproščen vpogled v pro- store fakultete, jim omogočilo srečanje z nekaterimi profesorji, asistenti in študenti ter jim – vsaj tako upamo – približalo študij matematike ali fizike. Program je odprl prof. dr. Sandi Klavžar, ki je spregovoril o Hanojskih stolpičih. Poslušalce je popeljal skozi vsebino knjige »The tower of Hanoi – Myths and maths«, ki je nedavno izšla v njegovem soavtorstvu, in navdušil z razlago, koliko zanimivih vej matematike lahko povežemo s to klasično uganko. Njegovo predavanje je pomenilo tudi začetek poljudnega cikla z naslovom I<3 MAT, ki je nato z mesečnimi dogodki trajal do poletja. Za njim je fizikalni del večera vodil prof. dr. Anton Ramšak, ki nas je popeljal skozi zanimive zgodbe iz zgodovine fizike ter – ob podpori eksperimentov – razložil, zakaj je bila ustrezna »tehnična podpora« skoraj vedno ključnega pomena pri vseh največjih miselnih preskokih v fizikalnih teorijah. Svoje predavanje je naslovil: »Od Galileia do superprevodnikov«. Sledil je sobotni del, namenjen raziskovanju v manǰsih skupinah. Di- jakom je bilo na voljo šest delavnic, ki so se ponovile tudi v nedeljo. Tako je vsak udeleženec lahko izbral dve temi, ki sta mu bili najbližje. Spre- hodimo se skozi vsebinske sklope . . . Pod mentorstvom Simona Čoparja in 76 Obzornik mat. fiz. 64 (2017) 2 i i “Kuzman” — 2017/6/30 — 9:03 — page 77 — #2 i i i i i i »Maϕjski vikend« – ali kako si spoznal svoje bodoče kolege Marion Van Midden so se dijaki ukvarjali s simetrijami v fizikalnih poskusih ter skušali na podlagi le-teh brez računanja odgovoriti na nekatera sicer zapletena vprašanja. Sergej Faletič je dijake popeljal skozi različne oblike valovanja in jim pokazal, katere lastnosti kvantnega opisa se pojavijo tudi v klasičnih primerih. Pod vodstvom Mateje Hrast so udeleženci spoznali metodo najmanǰsih kvadratov ter jo implementirali s programom Math- emathica in nato uporabili pri eksperimentu »Absorpcija sevanja gama«. Računalnǐsko obarvani sta bili tudi dve matematični delavnici. Delavnica Jureta Slaka – iskanje najkraǰse poti in delavnica Tatiane Elizabethe Sušnik – kriptografija. V prvi so dijaki spoznali nekaj enostavnih algoritmov za iskanje najkraǰse poti v cestnem omrežju, v drugi pa metodo šifriranja RSA. Zadnjo in najbolj obiskano delavnico – geometrije vǐsje dimenzije – je pripravil Rok Gregorič. Obzornik mat. fiz. 64 (2017) 2 77 i i “Kuzman” — 2017/6/30 — 9:03 — page 78 — #3 i i i i i i Vesti Nazadnje omenimo še sobotno popoldne, ki je poskrbelo, da program le ni bil tako zelo »šolski«. Namenjeno je bilo namreč družabnosti, ki je bila kakopak mafijsko začinjena. Predavanju o teoriji iger sta sledila Pobeg iz predavalnice (escape room po mafijsko) in Mafijski activity, za konec dneva pa so udeleženci obiskali tudi observatorij na Golovcu. Tako so svoje druženje, polno doživetij, končali v nedeljo opoldne – kot vse druge dni – v kavarni Maϕja. Za njimi je bil pester vikend! Dovolj pester, da jih bomo jeseni zagledali v klopeh naše fakultete? Morda! Morda pa ne . . . Morda se vidimo šele na naslednjem Maϕjskem vikendu. Vsekakor želim vsem do takrat en lep maϕjski pozdrav. Uroš Kuzman, vodja Maϕjskega vikenda OBVESTILO V Obzorniku za matematiko in fiziko, letnik 49, št. 2, str. 62–63, in na do- mači strani DMFA http://www.dmfa.si/pravilniki/Pravilnik_Drustvena Priznanja.html je objavljen Pravilnik o podeljevanju društvenih priznanj. Vabimo vas, da pisne predloge (z utemeljitvami) v skladu s tem pravil- nikom za letošnja priznanja pošljete do 30. septembra 2017 na naslov: DMFA Slovenije, Komisija za društvena priznanja, Jadranska ul. 19, 1000 Ljubljana. Predsednik DMFA Slovenije: prof. dr. Dragan Mihajlović VABILO Društvo matematikov, fizikov in astronomov Slovenije in Univerza v Novi Gorici vabita na strokovno srečanje in 70. občni zbor, ki bo 20. oktobra 2017 v Lanthierijevem dvorcu v Vipavi. Predlog dnevnega reda občnega zbora Predlog dnevnega reda 70. občnega zbora DMFA s pričetkom ob 17. uri: 1. Otvoritev 2. Izvolitev delovnega predsedstva 3. Društvena priznanja 78 Obzornik mat. fiz. 64 (2017) 2 i i “Kuzman” — 2017/6/30 — 9:03 — page 79 — #4 i i i i i i Cikel poljudnih predavanj I <3 MAT 4. Poročila o delu društva 5. Razprava o poročilih 6. Vprašanja in pobude 7. Računovodsko in poslovno poročilo DMFA Slovenije za leto 2016 8. Razno Urnik in povzetki predavanj bodo objavljeni na spletni strani društva: www.dmfa.si. Vljudno vabljeni. Predsednik DMFA Slovenije: prof. dr. Matej Brešar CIKEL POLJUDNIH PREDAVANJ I <3 MAT Na Fakulteti za matematiko in fiziko UL smo letos prvič organizirali cikel poljudnih predavanj iz matematike I <3 MAT. Predavanja smo namenili našim bodočim študentom, dijakom, mentorjem, staršem in vsem, ki želijo (p)ostati matematično fit. Skupaj s profesorji smo si zastavljali vprašanja in reševali probleme iz vsakdanjega življenja ter raziskovali, kako nam matematika pri tem pomaga. Prav na vsakem predavanju smo se prepričali, da je z matematiko vse lažje. Na prvem predavanju smo s prof. dr. Sandijem Klavžarjem iskali (op- timalne) rešitve igre Hanojski stolp in ob tem spoznali mnogo zanimivih matematičnih rezultatov. S pomočjo prof. dr. Petra Šemrla smo na drugem predavanju o eksponentni funkciji, verjetno najpomembneǰsi funkciji, izvede- li še veliko več, kot smo pričakovali. Na tretjem predavanju z naslovom Geometrija smo s prof. dr. Borisom Lavričem premǐsljevali o definiciji pre- mice in ob tem spoznali zgodovino in lepoto geometrijskega razmǐsljanja. Na sklepnem predavanju pa nas je v aktualno in pomembno temo – Mate- matiko podatkov – uvedel prof. dr. Jaka Smrekar, ki je delo podatkovnega znanstvenika predstavil na primeru analize fotografij z uporabo obilice topo- logije. Na dveh predavanjih so se nam priključili tudi fiziki. Prof. dr. Anton Ramšak nas je naučil, katera fizikalna teorija je »dobra«, in nas izzval z nepredvidljivim vedenjem superprevodnikov. Za interdisciplinarno področje medicinske fizike pa nas je navdušil prof. dr. Robert Jeraj, ki raziskuje najnoveǰse metode za diagnosticiranje in zdravljenja raka. Jeseni pripravljamo nov cikel poljudnih predavanj I <3 MAT. Vabljeni! Dijake in učitelje vabimo, da se preko naslova tinyurl.com/dijaki naročijo na obvestila o poljudnih predavanjih in drugih njim namenjenih aktivnostih. Anita Buckley Obzornik mat. fiz. 64 (2017) 2 79 i i “Legisa-utrinek” — 2017/6/8 — 13:04 — page 80 — #1 i i i i i i UTRINEK LUKRECIJ KAR IN PADANJE TELES Kar naprej slǐsimo, da je šele Galileo Galilei ovrgel Aristotelove teorije o tem, da težja telesa padajo hitreje kot lažja. V resnici je to spoznanje staro že več kot dva tisoč let. Prisluhnimo rimskemu mislecu Titu Lukreciju Karu. Ta sodobnik Julija Cezarja pravi v izredno obsežni pesnitvi O naravi sveta, originalno De rerum natura [1]: Ako kdo misli nemara, da morejo težja telesa, ker se hitreje nesó, padaje navpično v praznini, z vǐska zadeti na lažje in s tem povzročiti udarce, ... daleč izgublja se mož od póti pravilne presoje. Resda, karkoli že pada v vodi in redki zračini, mora, čim težje pač je, tem urneje spešiti padec, namreč zato, ker naravi vodé in rahlemu zraku ni moč sleherno stvar enako zavirati v padcu, ne: premagana v tekmi popuščata težjim hitreje; pač pa, nasprotno, praznina ne more nikjer in nikoli stvari nobeni, ki pada, zaprek postavljati zoper, zmeraj se vdajati mora, to terja že njena narava. Z isto brzino tedaj, četudi različna po teži, morajo sémena vsa se nositi po mirni praznini. (To so verzi 225–239 druge knjige fizikalnega dela te pesnitve v prevodu Antona Sovreta.) Lucretius Carus je pripadal šoli helenističnega filozofa Epikurja. Lu- krecij povsem pravilno pravi, da v vakuumu vsa telesa padajo enako hitro. V zraku ali vodi pa zaradi upora pride do razlik. Res je nenavadno, da so praktično vsi zgodovinarji znanosti spregledali ta odlomek iz sicer dobro znanega Lukrecijevega dela De rerum natura. Lukrecij je bil glavni posrednik in popularizator Demokritove teorije atomov. Tako že takoj na začetku pesnitve O naravi sveta najdemo razdelek: DRUGI AKSIOM: NEVIDNI ATOMI. 80 Obzornik mat. fiz. 64 (2017) 2 i i “Legisa-utrinek” — 2017/6/8 — 13:04 — page 81 — #2 i i i i i i Lukrecij Kar in padanje teles Kot vidimo, je skušal uporabljati matematično terminologijo. Teorijo atomov so po njegovem posredovanju sprejeli tudi novodobni evropski znan- stveniki, utemeljitelji kemije, ki so za obstoj atomov seveda imeli mnogo več dokazov. Lucretius Carus je svoje ideje izrazil v dovršeni književni obliki, v pe- snitvi. Nekateri odlomki imajo neminljivo literarno vrednost in lepoto. Uvod se imenuje SLAVA VENERI in v njem preberemo: kadar priblǐzaš se ti, boginja, zbežijo oblaki, z njimi viharji zbeže, natrosi ti umételna zemlja cvetk vonjavih na pot, smehlja se ti morska gladina, v luči spokojno razliti zasije pomirjeni nébes. V razdelku DEŽ IN DRUGE PADAVINE razloži, kako oblaki nastanejo iz atomov vode, ki se dvigajo iz morij, rek . . . In nato: Ako tu sončni se žarki upró med temačno nevihto ravno z nasprotne strani na dežjà lijočo zaveso mavrice pisani lok zarǐse se v črne oblake. V pesnitvi je zapisal seveda tudi mnoge špekulacije, ki se ne skladajo z današnjim znanjem o naravoslovnih pojavih. Vendar je bil Lukrecij vseeno vrhunski intelektualec z velikim znanjem naravoslovja in kot tak žal med Rimljani osamljen pojav. Odnos Rimljanov do znanosti je bil namreč zelo vprašljiv. Pragmatični, kot so bili, so iz grške in helenistične znanosti in tehnologije vzeli tisto, kar jim je ustrezalo. Večinoma pa niso čutili potrebe, da bi sami napredovali na znanstvenem področju. Zanašali so se na svoj odlični upravni sistem, dobro organizirano vojsko in izkorǐsčanje suženjske delovne sile. Mnogo bolj kot znanost so jih zanimali retorika, administracija, pravo, ekonomija, gradbenǐstvo, arhitektura in literatura. Na teh področjih pa so bili Rimljani izredno ustvarjalni in so naredili marsikaj, kar se nam danes zdi samoumeven del naše civilizacije. LITERATURA [1] T. Lucretius Carus, De Rerum natura, O naravi sveta, prevedel Anton Sovrè, Filo- zofska knjižnica 3. zv., Slovenska matica, Ljubljana 1959, 532 str. Peter Legǐsa Obzornik mat. fiz. 64 (2017) 2 VII i i “kolofon” — 2017/6/30 — 9:13 — page 2 — #2 i i i i i i OBZORNIK ZA MATEMATIKO IN FIZIKO LJUBLJANA, MAREC 2017 Letnik 64, številka 2 ISSN 0473-7466, UDK 51+ 52 + 53 VSEBINA Članki Strani Polni nabori resničnostnih funkcij in Postova mreža (Lara Vukšić) . . . . . 41–53 Nobelova nagrada za fiziko 2016 (Rok Žitko) . . . . . . . . . . . . . . . . . . . . . . . . . 54–64 Nove knjige Christian Ucke in Hans Joachim Schlichting, Spiel, Physik und Spaß, Physik zum Mitdenken und Nachmachen (Nada Razpet) . . . . . . . . . . 65–67 Zanimivosti Strnjeno vzorčenje (Peter Legiša) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68–75 Vesti »Maϕjski vikend« – ali kako si spoznal svoje bodoče kolege (Boštjan Kuzman) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76–78 Obvestilo (Dragan Mihajlović) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 Vabilo (Dragan Mihajlović) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78–79 Cikel poljudnih predavanj I <3 MAT (Anita Buckley) . . . . . . . . . . . . . . . . . . . 79 Utrinek Lukrecij Kar in padanje teles (Peter Legiša) . . . . . . . . . . . . . . . . . . . . . . . . . . . 80–VII CONTENTS Articles Pages Functionally complete sets of Boolean functions and Post’s lattice (Lara Vukšić) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41–53 The Nobel prize in physics 2016 (Rok Žitko) . . . . . . . . . . . . . . . . . . . . . . . . . . 54–64 New books . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65–67 Miscellanea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68–75, 80–VII News . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76–79 Na naslovnici: Helij postane superfluiden pri zelo nizkih temperaturah. Takrat po- stane viskoznost enaka nič. Pojav je povezan z Bose-Einsteinovo kondenzacijo. Helij, ki se nahaja v posodici, se v tanki plasti dviga po stenah navzgor in po zuna- nji strani odteka proti dnu, kjer nastaja kaplja. Vrtinci, ki nastanejo v taki tekočini, ne zamrejo. Vrtinci v tanki plasti superfluidnega helija so topološki defekti, zaradi katerih je stanje homotopsko različno od osnovnega stanja.