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