Univerzitet u Kragujevcu
Prirodno-matemati~ki fakultet
Silvana Marinkovi}
JEDNA^INENANEKIMMRE@AMA
Doktorska disertacija
Kragujevac, 2011.
Sadr`aj
Predgovor 2
1 Uvod 4
1.1 O jedna~inama uop{te . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Algebre. Osnovni pojmovi i tvr|ewa . . . . . . . . . . . . . . . . . . . . 6
1.3 Mre`e. Definicija, osobine i klasifikacija. . . . . . . . . . . . . . . . 9
2 Funkcije i jedna~ine na Bulovim algebrama 15
2.1 Bulove funkcije . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2 Bulove jedna~ine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3 Jedna~ine na Stonovim algebrama 20
3.1 Funkcije i jedna~ine na mre`ama . . . . . . . . . . . . . . . . . . . . . . 20
3.2 Reproduktivna re{ewa jedna~ina na Stonovim algebrama . . . . . . . . . 21
4 Jedna~ine u vi{evrednosnoj logici 26
4.1 Osnovni pojmovi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.2 Op{ta re{ewa jedna~ina sa jednom nepoznatom
u vi{evrednosnoj logici . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
5 Jedna~ine na Postovim algebrama 32
5.1 Definicija i osnovne osobine Postovih algebri . . . . . . . . . . . . . 32
5.2 Postove funkcije . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
5.3 Postove jedna~ine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
Literatura 51
Dodatak 54
1
Predgovor
Osnove prou~avawa Bulovih funkcija i jedna~ina su postavili Boole, Schro¨der i
Lo¨wenheim u drugoj polovini devetnaestog i po~etkom dvadesetog veka. Ova oblast se
intenzivno razvija u drugoj polovini dvadesetog veka. Taj razvoj se uglavnom odvija u dva
osnovna pravca: u pravcu specijalizacije i pravcu generalizacije.
Kada se govori o specijalizaciji, misli se na prou~avawe pojedinih vrsta Bulovih
funkcija i jedna~ina, kao{to su proste Bulovefunkcije i jedna~ine, vrednosne ( swit-
ching“) funkcije i jedna~ine, Bulove diferencijalne jedna~ine, zatim na prou~avawe
Bulovihjedna~inanapojedinimvrstamaBulovihalgebri(relacionealgebre,kompletne
Bulove algebre), kao i wihovu primenu u raznim oblastima: u detekciji gre{aka u
logi~kimmre`ama, teoriji kodirawa, teoriji automata, teoriji grafova, optimizaciji
itd.
Kada se govori o generalizaciji misli se na uop{tavawe poznatih rezultata o
Bulovim jedna~inama na jedna~ine na drugim mre`ama, kao {to su ograni~ene dis-
tributivne mre`e, pseudokomplementarne distributivne mre`e, Stonove algebre i dr.
Prirodno uop{tewe Bulovih jedna~ina su jedna~ine na vi{evrednosnoj logici. Ak-
siomatizacijom algebre koja odgovara Postovoj vi{evrednosnoj logici (nazvane Pos-
tovom algebrom) otvara se novo poqe generalizacije -- Postove jedna~ine. I rezultati
izlo`eniuovomradupredstavqajugeneralizacijunekihtvr|ewaoBulovimjedna~inama
na jedna~ine na Stonovim algebrama, vi{evrednosnoj logici i Postovim algebrama.
Rad se sastoji od pet poglavqa.
Prvo, uvodno poglavqe se sastoji od tri odeqka. Sve jedna~ine koje su razmatrane u
ovom radu su tipaPre{i}eve apstraktne jedna~ine, pa je prvi odeqak uvodnog poglavqa
posve}en ovoj jedna~ini i rezultatima koje su dobili Pre{i} i wegovi sledbenici. U
drugom i tre}em delu uvoda, radi lak{eg ~itawa teksta i preciznosti date su neke dobro
poznate definicije i tvr|ewa iz univerzalne algebre i teorije mre`a, koje }e biti
kori{}ene u daqem tekstu.
Osnovu za prou~avawefunkcija i jedna~inana svimmre`ama~ineBulovefunkcije i
jedna~ine. Mnogatvr|ewakojaseodnosena jedna~inenaStonovimiPostovimalgebrama
predstavqaju generalizaciju tvr|ewa koja se odnose na Bulove jedna~ine. To je razlog
{to su u drugom poglavqu dati najva`niji rezultati u prou~avawu Bulovih funkcija i
jedna~ina.
Utre}empoglavquposmatrane su jedna~inenaStonovimalgebrama. Uprvomodeqku
navodenisupoznatirezultatiofunkcijamai jedna~inamanamre`amauop{te. Udrugom
2
odeqkunajprejedataBecerovateoremakojapredstavqauop{teweLevenhajmoveteoreme
na jedna~ine na Stonovim algebrama. Zatim je navedena teorema kojom se, primenom
Becerove metode, opisuje klasa reproduktivnih re{ewa jedna~ine na Stonovoj algebri,
pod uslovom da je poznato jedno op{te re{ewe. Ova teorema predstavqa originalni
rezultat i publikovana je u radu Reproductive general solutions of equations on Stone
algebra, Journal of Multiple-Valued Logic and Soft Computing, Vol. 16, 1-2 (2010),
1–6.
^etvrto poglavqe je posve}eno jedna~inama u vi{evrednosnoj logici. Na kraju
ovog poglavqa je navedena teorema u kojoj je opisano jedno op{te re{ewe jedna~ine sa
jednom nepoznatom u vi{evrednosnoj logici. Ovaj rezultat je objavqen u radu General
solutions of equations in multiple-valued logic, Journal of Multiple-Valued Logic and
Soft Computing, Vol. 16, 3-5 (2010), 421–426.
U petom poglavqu prou~avane su jedna~ine na Postovim algebrama. Ovo poglavqe
se sastoji iz tri odeqka. U prvom odeqku je data definicija Postove algebre i nave-
dena su pravila za operacije u Postovim algebrama, koja }e biti kori{}ena u drugom
i tre}em odeqku. Karakterizacija Postovih funkcija i wihove najva`nije osobine su
izlo`ene u drugom odeqku. U tre}em odeqku su razmatrane Postove jedna~ine. Na-
jpre su navodeni poznati rezultati Carvaillo-a, Serfati-ja i Bordat-a: svo|ewe na
jednu jedna~inu, uslov konzistentnosti, metoda eliminacije nepoznatih, konstrukcija
reproduktivnog pomo}u partikularnog re{ewa i drugo. Zatim su prikazani dobijeni
rezultati u prou~avawu otvorenog problema koji je u radu Boolean sets and most gen-
eral solutions of Boolean equations ([41]) postavio Rudeanu. Naime, u pomenutom
radu Rudeanu se bavi obratnim problemom od problema re{avawa Bulove jedna~i-
ne, problemom nala`ewa Bulove funkcije ~ije su nule poznate i zadate parametarski.
Tako|e, bavi se i problemom odre|ivawa uslova koje treba da ispuwava niz rekurentno
zadatih intervala da bi predstavqao op{te re{ewe nekeBulove jedna~ine. Na kraju, on
postavqa problem pro{irewa istra`ivawa na Postove algebre. Do kraja ovog odeqka
su prikazani dobijeni originalni rezultati u re{avawu ovog problema.
* * *
Zahvaqujem se mentoru prof. dr Dragi}u Bankovi}u koji me je uputio u ovu oblast,
posvetio veliku pa`wu mom radu i zna~ajno doprineo ovoj disertaciji.
Autor
3
Glava 1
Uvod
Kako su sve jedna~ine koje su prou~avane u ovom radu tipa Pre{i}eve apstrak-
tne jedna~ine, u prvom odeqku su navedene najva`nije definicije i tvr|ewa vezana za
ovu jedna~inu. Zbog preciznosti i lak{eg ~itawa rada, u drugom odeqku su date poz-
nate definicije onih pojmova iz univerzalne algebre koji }e biti kori{}eni u radu.
Definicijamre`e, osnovnapravilara~unaiklasifikacijamre`a sunavedeni u tre}em
odeqku. Posebno je nagla{ena veza izme|u Bulove i Stonove algebre.
Za pisawe ovog dela rada kori{}ena je, uglavnom, monografija S. Rudeanu-a
 Lattice functions and equations.
1.1 O jedna~inama uop{te
U raznim oblastima matematike izu~avaju se razli~ite vrste jedna~ina. Na prvi
pogled, ni{ta uop{teno (a netrivijalno) se ne bimoglo re}i owima. Me|utim,Pre{i}
[32] uvodi pojam jedna~ine uop{te, tj. jedna~ine na skupu, kao i pojmove op{teg i re-
produktivnog re{ewa takve jedna~ine. Ovakvom definicijom jedna~ine obuhva}ene su,
izme|u ostalog, sve jedna~ine na mre`ama, Postovim i Bulovim algebrama.
Neka je T neprazan skup i r unarna relacija na T , dakle podskup skupa T . Zbog uzaja-
mno jednozna~ne korespondencije izme|u skupovaP(T ) i {0, 1}T (0 i 1 su dva razli~ita
objekta - logi~ke vrednosti), relaciju r mo`emo smatrati i preslikavawem skupa T u
skup {0, 1}.
DEFINICIJA 1.1. [32] Pod jedna~inom nad nepraznim skupom T podrazumevamo jedna-
kostoblika r(x) = 1, gde je r unarna relacija na skupuT , odnosno preslikavawe skupaT
u skup{0, 1}. ElementiskupaS = {x ∈ T |r(x) = 1} se zovure{ewa jedna~ine r(x) = 1.
Ako je S 6= ∅ ka`emo da je jedna~ina konzistentna. Jedna~ina za koju va`i S = T je
identitet.
Za ovakve jedna~ine Pre{i} defini{e pojmove op{teg i reproduktivnog re{ewa,
koji }e predstavqati uop{tewe poznatih pojmova op{teg i reproduktivnog re{ewa
jedna~ina u raznim oblastima matematike.
4
DEFINICIJA 1.2. [32] Neka je r(x) = 1 konzistentna jedna~ina na skupu T . Formula
x = f(t), gde f : T → T , odre|uje op{te re{ewe jedna~ine r(x) = 1 ako i samo ako
va`i
(∀x ∈ T )(r(x) = 1⇐⇒ (∃t)x = f(t)).
DEFINICIJA 1.3. [32] Op{te re{ewe x = f(t) konzistentne jedna~ine r(x) = 1 na
skupu T , je reproduktivno ako i samo ako va`i
(∀x ∈ T )(r(x) = 1 =⇒ x = f(x)).
POSLEDICA 1.1. [32]Formulax = f(t), gdef : T → T , odre|ujereproduktivnore{ewe
konzistentne jedna~ine r(x) = 1 na skupu T ako i samo ako va`i
(∀x ∈ T )(r(f(x)) = 1 ∧ (r(x) = 1 =⇒ x = f(x))).
OdPre{i}a je potekla i ideja uvo|ewa algebarske strukture na skupu T (ne znaju}i
da je ovo ve} uradio Post [30]). On uvodi elemente 0 i 1 koji mogu biti van skupa T ili
dva razli~ita elementa skupa T i defini{e dve binarne parcijalne operacije na skupu
T ∪ {0, 1} na slede}i na~in:
x+ 0 = 0 + x = x, x · 0 = 0 · x = 0, x · 1 = 1 · x = x (x ∈ T ∪ {0, 1}).
Tako|e, on defini{e
′ : {0, 1} → {0, 1}, 0′ = 1, 1′ = 0. Koriste}i ovu strukturu
Pre{i} daje formulu za nala`ewe svih reproduktivnih re{ewa jedna~ine r(x) = 1,
pod uslovom da je poznato jedno op{te re{ewe.
TEOREMA 1.1. [32] Neka je r unarna relacija na nepraznom skupu T i f : T → T takvo
preslikavawedaformulax = f(t)odre|ujeop{tere{ewejedna~iner(x) = 1. Formula
x = F (t) odre|uje reproduktivno op{te re{ewe jedna~ine r(x) = 1 ako i samo ako
postoji funkcija g : T → T takva da va`i
F (t) = r(t) · t+ r′(t) · f(g(t)).
Nakon Pre{i}a, op{ta i reproduktivna re{ewa apstraktnih jedna~ina izu~avali
su Bankovi}, Ke~ki}, Bo`i} i Chvalina.
Pre{i} je inicirao i pru~avawe konzistentne jedna~ine r(x) = 1 na kona~nom
skupu T = {t0, . . . , tm}. Pored operacija+ i · on je definisao i operacije
xy =
{
1, x = y
0, x 6= y (x, y ∈ T ∪ {0, 1}),
kao i
0∑
i=0
xi = x0,
n+1∑
i=0
xi =
(
n∑
i=0
xi
)
+ xn+1 (n ∈ N).
Sada je mogu}e svaku funkciju na T zapisati pomo}u prethodnih operacija.
5
TEOREMA 1.2. [40] Svaka funkcija f : T → T se mo`e zapisati u obliku
f(x) =
m∑
i=0
fix
ti (x ∈ T ),
gde su koeficijenti jedinstveno odre|eni sa
fi = f(ti) (i = 0, . . . ,m).
Prou~avawe jedna~ine oblika
a0x
t0 + a1x
t1 + · · ·+ amxtm = 0, (1.1)
gde su a0, . . . , am ∈ {0, 1} a nepoznata x ∈ T , je tako|e zapo~eo Pre{i}. On je dao uslov
konzistentnosti i opisao wena reproduktivna re{ewa. Bankovi} [3] daje jednostavniji
dokaz tog rezultata. On tako|e dopuwuje Pre{i}eve rezultate slede}im tvr|ewima [8].
TEOREMA 1.3. [8] Pretpostavimo da je jedna~ina (1.1) konzistentna. Funkcija
f : T → T defini{e op{te re{ewe jedna~ine (1.1) ako i samo ako je oblika
f(x) =
m∑
k=0
(a0ik,0tik,0 + aik,0a
0
ik,1
tik,1 + . . . + aik,0aik,1 · · · a0ik,m−1tik,m−1 +
+ aik,0aik,1 · · · aik,m−1tik,m−1)xtk ,
gde su (ik,0, ik,1, . . . , ik,m), za svako k ∈ {0, 1, . . . ,m}, permutacije skupa {0, 1, . . . ,m}, a
(i0,0, i1,0, . . . , im,0) je permutacija skupa {0, 1, . . . ,m}.
TEOREMA 1.4. [8] Pretpostavimo da je jedna~ina (1.1) konzistentna. Funkcija
f : T → T defini{e reproduktivno op{te re{ewe jedna~ine (1.1) ako i samo ako
je oblika
f(x) =
m∑
k=0
(a0ik,0tik,0 + aik,0a
0
ik,1
tik,1 + . . . + aik,0aik,1 · · · a0ik,m−1tik,m−1 +
+aik,0aik,1 · · · aik,m−1tik,m−1)xtk ,
gde su (ik,0, ik,1, . . . , ik,m), za svako k ∈ {0, 1, . . . ,m}, permutacije skupa {0, 1, . . . ,m}, a
(i0,0, i1,0, . . . , im,0) = (0, 1, . . . ,m)).
1.2 Algebre. Osnovni pojmovi i tvr|ewa
Kao {to je poznato, algebra A je ure|eni par (A,F ), gde je A neprazan skup koji se
naziva nosa~ (univerzum, domen), a F = (fi)i∈I familija preslikavawa fi : Ani → A,
i ∈ I, koje se nazivaju (osnovne) operacije. Broj ni ∈ N ∪ {0} se zove arnost operacije
fi i obele`ava sa ar(fi). Posebno, ako je ar(fi) = 0 ka`emo da je fi nularna operacija,
tj. fi ∈ A. Ako je F = {f1, . . . , fk} kona~an skup obi~no se umesto (A,F ) pi{e
6
(A, f1, . . . , fk) i ka`e da je algebraA tipa σ = (ar(f1), . . . , ar(fk)). ^esto se algebraA
ozna~ava isto kao i wen nosa~A.
Neprazan podskupB skupaA je zatvoren za operacije iz F ako i samo ako
(∀i ∈ I)(∀x1, . . . , xni ∈ B)fi(x1, . . . , xni) ∈ B,
(∀i ∈ I)(ni = 0 =⇒ fi ∈ B).
U tom slu~aju se algebra (B, (fi|Bni )i∈I) zove podalgebra algebreA.
Preslikavawe ϕ : A → B je homomorfizam algebre (A,F ) u istotipnu algebru
(B,G) ako i samo ako za svako i ∈ I i svako x1, . . . , xni ∈ A va`i
ϕ(fi(x1, . . . , xni)) = gi(ϕ(x1), . . . , ϕ(xni)).
Posebno,
(∀i ∈ I)(ni = 0 =⇒ ϕ(fi) = gi).
Relacija ekvivalencije∼ skupaA je kongruencija algebreA ako i samo ako za svako
i ∈ I i svako x1, y1, . . . , xni , yni ∈ A va`i
(∀k ∈ {1, . . . , ni})xk ∼ yk =⇒ fi(x1, . . . , xni) ∼ fi(y1, . . . , yni).
Sada navodimo definiciju algebarske funkcije.
DEFINICIJA 1.4. [40]
(i) Projekcije, tj. funkcije oblika
pij(x1, . . . , xn) = xj (j ∈ {1, . . . , n})
su algebarske funkcije.
(ii) Konstantne funkcije, tj. funkcije oblika
fa(x1, . . . , xn) = a (a je fiksirani element izA)
su algebarske funkcije.
(iii) Ako je f osnovna operacija algebreA du`ine n, a g1, . . . , gn algebarske funkcije,
onda je f(g1, . . . , gn) algebarska funkcija.
(iv) Algebarske funkcije se dobijaju samo kona~nom primenom (i), (ii) i (iii).
Posebnu klasu algebarskih funkcija ~ine polinomi. To su funkcije dobijene pri-
menom (i), (iii) i (iv), tj. funkcije koje se mogu izraziti termima jezika algebre A.
Preciznije:
7
DEFINICIJA 1.5. [40]
(i) Projekcije, tj. funkcije oblika
pij(x1, . . . , xn) = xj (j ∈ {1, . . . , n})
su polinomi.
(ii) Ako je f osnovna operacija algebre A du`ine n, g1, . . . , gn polinomi, onda je
f(g1, . . . , gn) polinom.
(iii) Polinomi se dobijaju samo kona~nom primenom (i) i (ii).
Napomena 1.1. U definicijama 1.4 i 1.5 se koristi terminologija koju koriste Ru-
deanu i Beazer. Kod nekih autora ( Serfati) termin polinom se koristi za funkcije
iz Definicije 1.4. Gra¨tzer za term i polinom (u Rudeanovom smislu) koristi izraze
polinom i polinomna funkcija.
Veza izme|u algebarskih funkcija i polinoma je data u slede}em tvr|ewu.
TEOREMA 1.5. [40]Algebarska funkcija g : An → A je svaka funkcija oblika
g(x1, . . . , xn) = p(a1, . . . , am, x1, . . . , xn) (x1, . . . , xn ∈ A),
gde je m ∈ N ∪ {0}, a1, . . . , am su fiksirani elementi skupa A i p : Am+n → A je
polinom.
Dakle, algebarskefunkcijesedobijajuizpolinomafiksirawemnekihpromenqivih.
Odatle sledi:
POSLEDICA 1.2. Svaka funkcija dobijena iz algebarske funkcije fiksirawem nekih
promenqivih je tako|e algebarska funkcija.
TEOREMA 1.6. [40] Skup polinoma (algebarskih funkcija) je zatvoren za kompoziciju
funkcija.
DEFINICIJA 1.6. [14]Funkcija f : An → A ima svojstvo zamene ako i samo ako za svaku
kongruenciju∼ algebreA va`i
(∀i ∈ {1, . . . , n})xi ∼ yi =⇒ f(x1, . . . , xn) ∼ f(y1, . . . , yn).
Iz definicija 1.4 i 1.6 sledi
TEOREMA 1.7. [40] Svaka algebarska funkcija ima svojstvo zamene.
Da nisu sve funkcije sa svojstvom zamene algebarske pokazuje Primer 2.1. u Glavi 2.
Pomenimo jo{ lepu osobinu funkcija sa svojstvom zamene da se one ~uvaju homo-
morfizmima.
8
LEMA 1.1. [24, 14] Neka su (A, (fi)i∈I) i (B, (gi)i∈I) istotipne algebre, ϕ : A → B
sirjektivni homomorfizam i f : An → Afunkcija sa svojstvom zamene. Defini{imo
funkciju g : Bn → B na slede}i na~in
g(ϕ(x1), . . . , ϕ(xn)) = ϕ(f(x1, . . . , xn)) (∀x1, . . . , xn ∈ A).
Tada je g funkcija sa svojstvom zamene.
DEFINICIJA 1.7. [40]Algebarska jedna~ina nad algebromA je jedna~ina oblika
f(X) = g(X),
gde su f, g : An → A algebarske funkcije algebre A, a X = (x1, . . . , xn) n-torka
nepoznatih.
1.3 Mre`e. Definicija, osobine i klasifikacija.
Najpre navodimo definicije mre`e (kao parcijalno ure|enog skupa i kao algebre)
i dajemo neke wene osobine. Zatim defini{emo neke potklase klase mre`a kao {to su
distributivne mre`e, ograni~ene mre`e, Stonove algebre i Bulove algebre. Posebno
}emo se zadr`ati na Bulovim algebrama kao najprou~avanijim mre`ama.
DEFINICIJA 1.8. Parcijalno ure|eni skup (L,≤) je mre`a ako i samo ako za svako
x, y ∈ L postoji sup{x, y} i inf{x, y}.
Drugu, algebarsku definiciju mre`e je uveo Dedekind.
DEFINICIJA 1.9. Nekasu∧i∨binarneoperacijenanepraznomskupuL. Ure|enatrojka
(L,∧,∨) je mre`a ako i samo ako va`i:
(M1)
(x ∧ y) ∧ z = x ∧ (y ∧ z),
(x ∨ y) ∨ z = x ∨ (y ∨ z) (asocijativnost),
(M2)
x ∧ y = y ∧ x,
x ∨ y = y ∨ x (komutativnost),
(M3)
x ∧ (x ∨ y) = x,
x ∨ (x ∧ y) = x (apsorptivnost),
(M4)
x ∧ x = x,
x ∨ x = x (idempotentnost).
Ove dve definicije mre`e su ekvivalentne. Ako na mre`i u smislu Definicije 1.8
defini{emo binarne operacije∨ i∧ na slede}i na~in
x ∨ y = sup{x, y}, x ∧ y = inf{x, y},
lako se proverava da one imaju osobine (M1)-(M4). Obrnuto, ako na mre`i u smislu
Definicije 1.9 defini{emo relaciju≤ na slede}i na~in
x ≤ y ⇐⇒ x ∨ y = y
9
mo`e se proveriti da je (L,≤) parcijalno ure|en skup u kome za svako x i y postoji
sup{x, y} = x ∧ y i inf{x, y} = x ∨ y, pa je (L,≤) mre`a u smislu Definicije 1.8.
Tako|e se lako proverava da va`i
x ≤ y ⇐⇒ x ∧ y = x. (1.2)
Iz definicije je o~igledno da svaki lanac (linearno ure|eni skup) predstavqa
mre`u.
DEFINICIJA 1.10. [40]Mre`a (L,∧,∨)kojaimanajmawielement, ozna~ensa0, inajve}i
element, ozna~en sa 1, se zove ograni~ena mre`a.
U ograni~enoj mre`i (L,∧,∨) za svako x, y va`i:
0 ≤ x, x ≤ 1,
x ∧ 0 = 0, x ∨ 1 = 1,
x ∧ 1 = x, x ∨ 0 = x,
x ∧ y = 1⇔ x = y = 1, x ∨ y = 0⇔ x = y = 0.
Napomena 1.2. U ograni~enoj mre`i va`i princip dualnosti, {to zna~i da zajedno sa
nekim tvr|ewem va`i i wemu dualno tvr|ewe dobijeno iz wega uzajamnom zamenom ∨ i
∧, 0 i 1.
DEFINICIJA 1.11. [40]Neka je (L,∧,∨)mre`a sa najmawim elementom 0 i neka jex ∈ L.
Ako postoji element
x∗ = max{y ∈ L|x ∧ y = 0}
onda se x∗ zove pseudokomplement elementa x. Za element x ka`emo da je pseudokom-
plementaran. Mre`a L je pseudokomlementarna ako su svi weni elementi pseudokom-
plementarni.
Analogno se u mre`i sa 1 mo`e definisati dualni pseudokomplement x+ elementa
x:
x+ = min{y ∈ L|x ∨ y = 1}.
Ukoliko postoji dualni pseudokomplement elementa x ka`emo da je element x du-
alno pseudokomplementaran. Mre`a je dualno pseudokomplementarna ako su svi weni
elementi dualno pseudokomplementarni.
O~igledno, ukoliko element x ima pseudokomplement, onda je on jedinstven. Isto
va`i i za dualni pseudokomplement.
PRIMER 1.1. Svaki ograni~eni lanac je pseudokomplementaran i dualno pseudokomple-
mentaran jer va`i
0∗ = 1, x∗ = 0 za svako x 6= 0, 1+ = 0, x+ = 1 za svako x 6= 1.
Primetimo da je svaka pseudokomplementarna mre`a ograni~ena. Zaista, imamo da
va`i 0∗ = 1 zbog {y ∈ L|0 ∧ y = 0} = L.
10
DEFINICIJA 1.12. Mre`a (L,∧,∨) je distributivna ako i samo ako za svako x, y i
z ∈ L va`i
x ∧ (y ∨ z) = (x ∧ y) ∨ (y ∧ z).
LEMA 1.2. [40] U pseudokomplementarnoj distributivnoj mre`i L, za svako x, y ∈ L
va`i:
x ∧ y = 0⇔ y ≤ x∗,
x ∧ x∗ = 0,
x∗ = 1⇔ x = 0,
0∗ = 1, 1∗ = 0,
x ≤ x∗∗,
x∗∗∗ = x∗,
x ≤ y ⇒ y∗ ≤ x∗,
(x ∧ y)∗∗ = x∗∗ ∧ y∗∗,
(x ∨ x∗)∗ = 0,
(x ∨ y)∗ = x∗ ∧ y∗,
(x ∨ y)∗∗ = (x∗∗ ∨ y∗∗)∗∗.
LEMA 1.3. [40] Slede}i identiteti su ekvivalentni u svakoj pseudokomplementarnoj
distributivnoj mre`i:
x∗ ∨ x∗∗ = 1,
(x ∧ y)∗ = x∗ ∨ y∗,
(x ∨ y)∗∗ = x∗∗ ∨ y∗∗.
DEFINICIJA 1.13. [40] Pseudokomplementarna distributivna mre`a u kojoj va`i
bilo koji od ekvivalentnih uslova iz Leme 1.3 se zove Stonova algebra. Mre`a koja je
Stonova algebra i dualna Stonova algebra se zove dvostruka Stonova algebra.
DEFINICIJA 1.14. [40] Element x ograni~ene mre`e L je Bulov ako postoji element
x′ ∈ Ltakav da va`i
x ∧ x′ = 0 i x ∨ x′ = 1.
Utomslu~aju se elementx′ zove komplementodx. Mre`a u kojoj je svaki elementBulov
zove se komplementarna mre`a. Skup svih komplementarnih elemenata ograni~ene
mre`eL }emo ozna~avati saB(L).
Napomena1.3. Usvakojograni~enojmre`i0i1su jedinstvenikomplementi jednodrugom.
Ostali elementi ograni~ene mre`e ne moraju imati jedinstven komplement. Element
ograni~ene mre`e mo`e imati jedinstven komplement, mo`e imati vi{e komplemenata
a mogu}e je i da nema komplement, {to se vidi iz slede}ih primera:
11
PRIMER 1.2. U petoelementnoj ograni~enoj mre`i dijamant (Sl. 1) ~iji su najmawi
i najve}i element 0 i 1, a elementi a, b i c me|usobno neuporedivi, svaki od elemenata
a, b, c je komplement preostala dva. Jedini pseudokomplementarni elementi su 0 i 1.
¶
¶
¶
¶
¶
¶
¶
¶
S
S
S
S
S
S
S
S
¶
¶
¶
¶
¶
¶
¶
¶
S
S
S
S
S
S
S
S
b
bb b
b
0
a cb
1
A
A
A
A
A
A
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯T
T
T
T
T
T
0
a
b
1
c
Slika 1 Slika 2
PRIMER 1.3. U petoelementnoj ograni~enoj mre`i petougao (Sl. 2) ~iji su najmawi
i najve}i element 0 i 1, a za preostale elemente a, b, c va`i a < b i c je neuporedivo
sa preostala dva, elementi a i b imaju jedinstven komplement (u oba slu~aja je to c),
koji je istovremeno i wihov pseudokomplement. Element c ima dva komplementa a i b.
Pseudokomplement od c je b.
PRIMER 1.4. U ograni~enom lancu nijedan element, razli~it od 0 i 1, nema komplement.
Me|utim, u distributivnoj mre`i nema svih ovih mogu}nosti.
TEOREMA 1.8. [40]Uograni~enoj distributivnojmre`isvakiBulov elementima jedin-
stven komplement.
Dokaz. Neka su y1 i y2 komplementi od x. Tada
y1 = y1 ∧ 1 = y1 ∧ (x ∨ y2) = (y1 ∧ x) ∨ (y1 ∧ y2) = 0 ∨ (y1 ∧ y2) =
(x ∧ y2) ∨ (y1 ∧ y2) = (x ∨ y1) ∧ y2 = 1 ∧ y2 = y2.
¤
Postoji vi{e ekvivalentnih definicija pojma Bulove algebre.
DEFINICIJA 1.15. [40] Bulova algebra je komplementarna distributivna mre`a.
Imaju}i u viduprethodne definicije i tvr|ewa, Bulova algebra semo`edefinisati
i na slede}i na~in:
12
DEFINICIJA 1.16. [37]Algebra (B,∧,∨,′ , 0, 1)tipa (2, 2, 1, 0, 0) je Bulova algebra ako
i samo ako u woj va`e slede}i identiteti:
(x ∧ y) ∧ z = x ∧ (y ∧ z),
x ∧ y = y ∧ x,
x ∧ (x ∨ y) = x,
x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z),
x ∨ 1 = 1,
x ∨ x′ = 1,
(x ∨ y) ∨ z = x ∨ (y ∨ z),
x ∨ y = y ∨ x,
x ∨ (x ∧ y) = x,
x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z),
x ∧ 0 = 0,
x ∧ x′ = 0.
Napomena 1.4. Iz prethodne definicije sledi da za Bulove algebre va`i princip
dualnosti. Princip dualnosti tako|e va`i i za dvostruke Stonove algebre.
TEOREMA 1.9. [40] U svakoj Bulovoj algebri (B,∨,∧,′ , 0, 1), za svako x, y, z ∈ B, va`i:
x ∧ x = x, x ∨ x = x,
x ∧ x′ = 0, x ∨ x′ = 1,
0′ = 1, 1′ = 0,
x′′ = x,
(x ∧ y)′ = x′ ∨ y′, (x ∨ y)′ = x′ ∧ y′,
x ∧ (x′ ∨ y) = x ∧ y, x ∨ (x′ ∧ y) = x ∨ y,
x ≤ y =⇒ y′ ≤ x′,
x ≤ y ⇐⇒ x ∧ y′ = 0⇐⇒ x′ ∨ y = 1,
x = y ⇐⇒ (x′ ∨ y) ∧ (x ∨ y′) = 1⇐⇒ (x ∧ y′) ∨ (x′ ∧ y) = 0.
TEOREMA 1.10. [40] Svaka Bulova algebra B je dvostruka Stonova algebra u kojoj za
svako x ∈ B va`i
x∗ = x+ = x′.
Dokaz. Doka`imo najpre da svaki element x Bulove algebre (B,∧,∨,′ , 0, 1) ima
pseudokomplement x∗ = x′. Iz x ∧ x′ = 0 sledi da x′ ∈ {y|x ∧ y = 0}. Neka je y ∈ B
takav da je x ∧ y = 0. Tada
y = y ∧ 1 = y ∧ (x ∨ x′) = (y ∧ x) ∨ (y ∧ x′) = 0 ∨ (y ∧ x′) = y ∧ x′,
odakle sledi y ≤ x′, pa je
x′ = max{y ∈ B|x ∧ y = 0} = x∗.
Dakle, svaka Bulova algebra je pseudokomplementarna distributivna mre`a. Kako je
x∗ ∨ x∗∗ = x′ ∨ x′′ = x′ ∨ x = 1 sledi da jeB Stonova algebra. Iz principa dualnosti
sledi da jeB dvostruka Stonova algebra. ¤
13
Ako uBulovoj algebri (B,∧,∨,′ , 0, 1) defini{emo operacije+ i · na slede}i na~in
x+ y = (x ∧ y′) ∨ (x′ ∧ y), x · y = x ∧ y,
lako mo`emo proveriti da je algebra (B,+, ·, 0, 1) komutativan prsten sa jedinicom.
Ovaj prsten se zove Bulov prsten. On je karakteristike 2 (x + x = 0, za svako x). U
wemu je svaki element idempotentan (x · x = x, za svako x).
Va`i i obratno, svaki Bulov prsten sa jedinicom (B,+, ·, 0, 1) postaje Bulova alge-
bra (B,∧,∨,′ , 0, 1), ako operacije defini{emo na slede}i na~in:
x ∧ y = x · y, x ∨ y = x+ y + x · y, x′ = x+ 1.
TEOREMA 1.11. [40] Ako je L ograni~ena distributivna mre`a onda je B(L) Bulova
algebra.
DEFINICIJA 1.17. [40] Element x pseudokomplementarne mre`e L je regularan ako i
samo ako va`i x∗∗ = x. Skup regularnih elemenata mre`eL }emo ozna~avati saR(L).
Napomena 1.5. Element x pseudokomplementarne mre`e je regularan ako i samo ako je
pseudokomplement nekog elementa, tj. x = y∗ za neko y ∈ L.
LEMA 1.4. [40] Ako je L Stonova algebra onda je B(L) = R(L) i x′ = x∗, za svako
x ∈ B(L).
Dokaz. Neka je x′ komplement elementa x ∈ B(L). Tada iz x ∧ x′ = 0 sledi x′ ≤ x∗,
pa je 1 = x ∨ x′ ≤ x ∨ x∗. Iz x ∨ x∗ = 1 dobijamo
x∗∗ = x∗∗ ∧ (x ∨ x∗) = x∗∗ ∧ x ≤ x ≤ x∗∗,
pa je x = x∗∗, odnosno x ∈ R(L). Dakle,B(L) ⊆ R(L). Ako x ∈ R(L) onda x ∧ x∗ = 0
i x ∨ x∗ = x∗∗ ∨ x∗ = 1{to zna~i da je x∗ komplement elementa x, tj. x ∈ B(L). ¤
Slede}a teorema daje vezu izme|u Stonove i Bulove algebre.
TEOREMA 1.12. Neka je (L,∧,∨, ∗, 0, 1) Stonova algebra. Tada
(i) (B(L),∧,∨, ∗, 0, 1) je Bulova algebra.
(ii) Preslikavawe ϕ : L → L, definisano sa ϕ(x) = x∗∗, je homomorfizam i va`i
ϕ(L) = B(L).
(iii) Lupslopekerϕ ∼= B(L), pri ~emu x kerϕy ⇐⇒ x∗ = y∗, za x, y ∈ L.
POSLEDICA 1.3. Stonova algebra (L,∧,∨, ∗, 0, 1) je Bulova algebra ako i samo ako je
preslikavawe ∗ : L→ L injektivno.
Dokaz. Neka jeStonova algebra (L,∧,∨, ∗, 0, 1)iBulova algebra. Tada jeL = B(L).
Neka su x, y ∈ L takvi da je x∗ = y∗. Iz Leme 1.4 i osobina komplementirawa i
pseudokomplementirawa sledi da je
x = x′′ = x∗∗ = y∗∗ = y′′ = y,
pa je preslikavawe ∗ injektivno. Pretpostavimo sada da je ∗ injektivno. Doka`imo
da je L ⊆ B(L). Neka je x ∈ L. Kako u Stonovoj algebri va`i x∗ = x∗∗∗ (za svako
x ∈ L), iz injektivnosti ∗ sledi da je x = x∗∗, pa je x regularan. Prema Lemi 1.4 sledi
da x ∈ B(L). ¤
14
Glava 2
Funkcije i jedna~ine na Bulovim
algebrama
Kako su od svih jedna~ina na mre`ama najpre i najvi{e prou~avane algebarske
jedna~ine na Bulovim algebrama (Bulove jedna~ine) i kako su mnoga tvr|ewa koja se
odnose na jedna~ine na {irim klasama mre`a generalizacija odgovaraju}ih tvr|ewa
koja se odnose na Bulove jedna~ine, prirodno je najpre navesti najva`nije rezultate u
prou~avawu Bulovih funkcija i jedna~ina. Za pisawe ovog dela uglavnom je kori{}ena
monografija S. Rudeanua Boolean functions and equations“.
2.1 Bulove funkcije
Osnoveprou~avawuBoolovihfunkcijai jedna~inasuudrugojpolovinidevetnaestog
i po~etkom dvadesetog veka postavili Boole, Schro¨der i Lo¨wenheim.
Bulove funkcije su algebarske funkcije na Bulovoj algebri. Preciznije:
DEFINICIJA 2.1. Bulove funkcije od n variabli na Bulovoj algebri (B,∧,∨,′ , 0, 1) su
odre|ene po slede}im pravilima:
1◦ Konstantne funkcije, tj. funkcije fa : Bn → B, a ∈ B, definisane sa
fa(x1, . . . , xn) = a (za svako x1, . . . , xn ∈ B)
su Bulove funkcije.
2◦ Projekcije, tj. funkcije pii : Bn → B, i ∈ {1, . . . , n}, definisane sa
pii(x1, . . . , xn) = xi (za svako x1, . . . , xn ∈ B)
su Bulove funkcije.
15
3◦ Ako su f, g : Bn → B Bulove funkcije onda su funkcije f ∧ g, f ∨ g, f ′ : Bn → B
definisane sa
(f ∧ g)(x1, . . . , xn) = f(x1, . . . , xn) ∧ g(x1, . . . , xn) (za svako x1, . . . , xn ∈ B),
(f ∨ g)(x1, . . . , xn) = f(x1, . . . , xn) ∨ g(x1, . . . , xn) (za svako x1, . . . , xn ∈ B),
f ′(x1, . . . , xn) = (f(x1, . . . , xn))′ (za svako x1, . . . , xn ∈ B)
tako|e Bulove funkcije.
4◦ Svaka Bulova funkcija se dobija primenom pravila 1◦, 2◦ i 3◦ kona~an broj puta.
DEFINICIJA 2.2. Bulove funkcije koje se dobijaju primenom pravila 2◦, 3◦ i 4◦ se zovu
proste Bulove funkcije.
Uvedimo slede}e oznake:
Operaciju∧ }emo ozna~avati sa · ili }emo izostaviti znak za operaciju. Za x ∈ B i
α ∈ {0, 1} neka je
x1 = x, x0 = x′,
a zaX = (x1, . . . , xn) ∈ Bn, A = (α1, . . . , αn) ∈ {0, 1}n neka je
XA = xα11 . . . x
αn
n .
Karakterizaciju Bulovih funkcija daje slede}a teorema.
TEOREMA 2.1. Neka je (B, ·,∨,′ , 0, 1) Bulova algebra i n prirodan broj. Funkcija
f : Bn → B je Bulova ako i samo ako se mo`e napisati u obliku
f(X) =
∨
A∈{0,1}n
cAX
A (∀X ∈ Bn), (2.1)
gde su koeficijenti cA jedinstveno odre|eni sa
cA = f(A) (∀A ∈ {0, 1}n).
Desna strana jednakosti (2.1) se zove kanonska disjunktivna forma funkcije f .
DEFINICIJA 2.3. Neka je B2 = {0, 1} dvoelementna Bulova algebra i n ∈ N . Svaka
funkcija f : B2
n → B2 se zove vrednosna funkcija.
Lako se mo`e proveriti da je svaka vrednosna funkcija prosta Bulova funkcija, a
samim tim i Bulova funkcija. Me|utim, na Bulovoj algebri B 6= B2 postoje funkcije
koje nisu Bulove. Na primer, defini{imo f : Bn → B tako da f(A) = 0, za svako
A ∈ {0, 1}n, i f(Ξ) = 1, za neko Ξ ∈ Bn \ {0, 1}n. Ako bi ova funkcija bila Bulova,
onda bi se mogla napisati u kanonskoj disjunktivnoj formi (Teorema 2.1), odakle bi
sledilo f(Ξ) = 0, kontradikcija.
TEOREMA 2.2. [23]Neka jeB Bulova algebra. Funkcija f : Bn → B je Bulova ako i samo
ako ima svojstvo zamene.
16
2.2 Bulove jedna~ine
Bulove jedna~ine defini{emo kao algebarske jedna~ine (Definicija 1.7) na Bulo-
vim algebrama:
DEFINICIJA 2.4. Bulova jedna~ina (nejedna~ina) sa n nepoznatih na Bulovoj algebri
B je jedna~ina (nejedna~ina) oblika
f(X) = g(X) (f(X) ≤ g(X)), (2.2)
gde su f, g : Bn → B Bulove funkcije, aX = (x1, . . . , xn) n-torka nepoznatih. Ako za
A ∈ Bn va`i f(A) = g(A) (f(A) ≤ g(A)) onda je A partikularno re{ewe jedna~ine
(nejedna~ine) (2.2). Re{iti Bulovu jedna~inu (nejedna~inu) zna~i odrediti skup svih
wenih re{ewa. Ako je taj skup re{ewa neprazan ka`emo da je jedna~ina (nejedna~ina)
konzistentna. Dve jedna~ine (nejedna~ine) su ekvivalentne ako imaju jednake skupove
re{ewa.
TEOREMA 2.3. Svaka Bulova jedna~ina ili nejedna~ina ili sistem jedna~ina i/ili
nejedna~ina je ekvivalentna jednoj Bulovoj jedna~ini oblika f(X) = 0.
Neka jeX = (x1, . . . , xn), T = (t1, . . . , tn) iϕ1, . . . , ϕn : B
n → B Bulove funkcije.
DEFINICIJA 2.5. Formula
X = (ϕ1(T ), . . . , ϕn(T ))
defini{e op{te re{ewe konzistentne Bulove jedna~ine f(X) = 0 ako i samo ako
(∀X ∈ Bn) (f(X) = 0⇔ (∃T )X = (ϕ1(T ), . . . , ϕn(T ))) .
DEFINICIJA 2.6. Formula
X = (ϕ1(T ), . . . , ϕn(T ))
defini{ereproduktivnore{ewekonzistentneBulove jedna~ine f(X) = 0 ako i samo
ako
(∀X ∈ Bn) (f(X) = 0⇔ X = (ϕ1(X), . . . , ϕn(X))) .
Primetimo da su ove definicije saglasne Definiciji 1.2 op{teg i Definiciji 1.3
reproduktivnog op{teg re{ewa jedna~ine uop{te.
Posmatrajmo najpre Bulove jedna~ine sa jednom nepoznatom, tj. jedna~ine oblika
f(x) = 0, gde je f : B → B Bulova funkcija. Iz Teoreme 2.1 sledi da je svaka Bulova
jedna~ina sa jednom nepoznatom oblika
ax ∨ bx′ = 0, a, b ∈ B.
Uslov konzistentnosti ove jedna~ine, re{ewe u obliku intervala, kao i reproduktivno
parametarsko re{ewe je dao Schro¨der.
17
TEOREMA 2.4. Neka je (B, ·,∨,′ , 0, 1) Bulova algebra i a, b, x ∈ B. Slede}i uslovi su
ekvivalentni
(i) ax ∨ bx′ = 0;
(ii) b ≤ x ≤ a′.
TEOREMA 2.5. Bulova jedna~ina ax ∨ bx′ = 0 je konzistentna ako i samo ako ab = 0. U
tom slu~aju formula
x = b ∨ a′t
ili, ekvivalentno,
x = a′t ∨ bt′
defini{e reproduktivno op{te re{ewe ove jedna~ine.
Posmatrajmo sada Bulovu jedna~inu sa n nepoznatih f(X) = 0, gde je f : Bn → B
Bulova funkcija. Problem wene konzistentnosti su re{ili Boole i Schro¨der.
TEOREMA 2.6. Neka je f : Bn → B Bulova funkcija. Jedna~ina
f(X) = 0 (2.3)
je konzistentna ako i samo ako ∏
A
f(A) = 0.
Re{avawe jedna~ine (2.3) se metodom sukcesivnih eliminacija nepoznatih svodi na
re{avawen jedna~ina sa jednomnepoznatom. Re{ewe semo`eizraziti ili rekurentnim
nejednakostima ili parametarski.
DEFINICIJA 2.7. [18]Neka je f : Bn → B Bulovafunkcija. Preslikavawa fi : Bn−i →
B, (i = 1, . . . n) definisana sa
f1(x1, . . . , xn) = f(x1, . . . , xn)
fi(xi, . . . , xn) = fi−1(1, xi, . . . , xn)fi−1(0, xi, . . . , xn) (i = 2, . . . , n)
fn+1 = fn(1)fn(0)
}emo zvati eliminantama funkcije f .
TEOREMA 2.7. [18] Neka je f : Bn → B Bulova funkcija. Ako je fn+1 = 0 onda je
jedna~ina
f(X) = 0
konzistentna i skup re{ewa je opisan rekurentnim nejednakostima
fn(0) ≤ xn ≤ f ′n(1)
fi(0, xi+1, . . . , xn) ≤ xi ≤ f ′i(1, xi+1, . . . , xn) (i = n− 1, . . . , 1)
(2.4)
18
Slede}a teorema ( Lo¨wenheim) daje formulu za dobijawe reproduktivnog re{ewa
Bulove jedna~ine ukoliko je poznato jedno partikularno re{ewe te jedna~ine.
TEOREMA 2.8. [26] Neka je ξ partikularno re{ewe Bulove jedna~ine f(X) = 0. Tada
formula
X = ξf(T ) ∨ Tf ′(T )
defini{e reproduktivno op{te re{ewe jedna~ine f(X) = 0.
Dakle, za primenu ove teoreme potrebno je poznavawe jednog partikularnog re{ewa.
U nekim slu~ajevima je ono unapred dato ili se lako mo`e pogoditi. Sam Lo¨wenheim
je predlo`io nala`ewe jednog partikularnog re{ewa iz kanonske disjunktivne forme
funkcije f : ako term XA nedostaje u woj to zna~i da je f(A) = 0, pa je X = A
jedno re{ewe jedna~ine f(X) = 0. Naravno, mo`e se desiti da ova jedna~ina, iako je
konzistentna, nema re{ewe u skupu {0, 1}n. Tada se partikularno re{ewe mo`e dobiti
iz rekurentnih nejednakosti (2.4) sa n uzastopnih izbora. Biraju}i uvek najmawe xi
dobijamo partikularno re{ewe (ξ1, . . . , ξn) za koje va`i ξi = fi(0, ξi+1, . . . , ξn) (i =
1, . . . n).
Primenom Lo¨wenheim-ove teoreme dokazuje se slede}a, Mu¨ller- Lo¨wenheim-ova
teorema, koja se veoma koristi prilikom dokazivawa identiteta koji va`e u Bulovim
algebrama. Ona ka`e da neki identitet va`i na Bulovoj algebri ako i samo ako va`i na
podalgebri {0, 1}.
TEOREMA 2.9. [26, 29]Neka je (B, ·,∨,′ , 0, 1) Bulova algebra. Tada va`i
(∀X ∈ Bn)f(X) = 0⇐⇒ (∀A ∈ {0, 1}n)f(A) = 0.
POSLEDICA 2.1. Neka su f, g : Bn → B Bulovefunkcije i neka je bar jedna od jedna~ina
f(X) = 0, g(X) = 0 konzistentna. Tada
(∀X ∈ Bn))(f(X) = 0⇐⇒ g(X) = 0) ako i samo ako f = g.
Bankovi} u [4] daje generalizaciju Levenhajmove teoreme. Naime, on daje formulu za
odre|ivawe svih reproduktivnih re{ewa konzistentne Bulove jedna~ine pod uslovom
da je poznato jedno op{te re{ewe.
TEOREMA 2.10. [4]Neka jeB Bulova algebra i f, g1, . . . , gn, h1, . . . , hn : B
n → B Bulove
funkcije. Neka je formulama
xi = gi(T ) (i = 1, . . . , n)
odre|eno op{te re{ewe konzistentne Bulove jedna~ine f(x1, . . . , xn) = 0. Formule
xi = hi(T ) (i = 1, . . . , n)
defini{u op{te reproduktivno re{ewe jedna~ine f(X) = 0 ako i samo ako postoje
Bulove funkcije p1, . . . pn : B
n → B tako da je
hi(T ) = tif
′(T ) ∨ f(T )gi(p1(T ), . . . , pn(T )) (i = 1, . . . , n).
19
Glava 3
Jedna~ine na Stonovim algebrama
Algebarskim jedna~inama na ograni~enim distributivnim mre`ama je prvi po~eo
da se bavi Goodstein [21]. On je dao uslov konzistennosti i algoritam za nala`ewe
re{ewa, ako ono postoji. Kasnije je Beazer pokazao da se u Stonovim algebrama neki
od ovih rezultata mogu uop{titi na{iru klasu funkcija i jedna~ina od algebarskih, na
klasu funkcija sa svojstvom zamene.
3.1 Funkcije i jedna~ine na mre`ama
Algebarske funkcije na mre`i (L,∧,∨) su (Definicija 1.4) funkcije dobijene od
konstantnih funkcija i projekcija kona~nom primenom operacija∧ i∨.
TEOREMA 3.1. [21] Neka je (L,∧,∨, 0, 1) ograni~ena distributivna mre`a, n ∈ N i
M = {1, . . . , n}. Funkcija f : Ln → L je algebarska ako i samo ako se mo`e zapisati u
obliku
f(x1, . . . , xn) =
∨
S⊆M
f(δS1 , . . . , δSn) ∧
∧
h∈S
xh,
gde je
δSh =
{
1, h ∈ S
0, h /∈ S za svako S ⊆M.
POSLEDICA 3.1. Algebarska funkcija f : Ln → L na ograni~enoj distributivnoj
mre`iL je potpuno odre|ena svojom restrikcijom na {0, 1}n.
Algebarske jedna~ine na mre`i (L,∧,∨) su jedna~ine oblika f(X) = g(X), gde su
f i g algebarske funkcije na mre`iL. Iz ekvivalencija
f = g ⇐⇒ f ∧ g = f ∨ g ⇐⇒ f ∨ g ≤ f ∧ g,
f ≤ g ⇐⇒ f ∧ g = f ⇐⇒ f ∨ g = g
20
sledi da je u svakoj mre`i problem re{avawa neke jedna~ine ekvivalentan problemu
re{avawa neke nejedna~ine [21]. Me|utim, za razliku od Bulovih jedna~ina, u op{tem
slu~aju se re{avawe algebarske jedna~ine f(X) = g(X) na mre`i ne mo`e svesti na
re{avawe algebarske jedna~ine oblika h(X) = 0. Uslov konzistentnosti algebarske
nejedna~ine (a samim tim i jedna~ine) na ograni~enoj distributivnojn mre`i je dao
Goodstein [21].
TEOREMA 3.2. [21]Neka je L ograni~ena distributivna mre`a, n ∈ N i f, g : Ln → L
funkcije mre`e. Tada nejedna~ina
f(x1, . . . , xn) ≤ g(x1, . . . , xn) (3.1)
je konzistentna ako i samo ako
f(0, . . . , 0) ≤ g(1, . . . , 1).
Utom slu~aju svaka n−torka (x1, . . . , xn) za koju va`i
f(0, . . . , 0) ≤ x1 ≤ g(1, . . . , 1),
f(x1, . . . xh−1, 0, . . . , 0) ≤ xh ≤ g(x1, . . . , xh−1, 1, . . . , 1) (2 ≤ h ≤ n),
je re{ewe jedna~ine 3.1.
3.2 Reproduktivna re{ewa jedna~ina na Stonovim alge-
brama
U ovom odeqku }e se razmatrati funkcije i jedna~ine na Stonovim algebrama. Bi}e
navedeni neki Beazer-ovi rezultati (uop{tewe Lo¨wenheim-ove teoreme na Stonove
algebre i uop{tewe Mu¨ller-Lo¨wenheim-ove teoreme na Stonove algebre sa najmawim
gustim elementom). Posledwa teorema u ovom odeqku predstavqa originalni rezultat
dobijen kori{}ewem Beazer-ove metode.
DEFINICIJA 3.1. Stonove funkcije su algebarske funkcije na Stonovoj algebri
(L,∧,∨, ∗, 0, 1).
Na osnovu Definicije 1.4 Stonove funkcije su funkcije na Stonovoj algebri dobi-
jene od konstantnih funkcija i projekcija superpozicijom osnovnih operacija: ∧,∨ i ∗.
Podsetimo se da su funkcije sa svojstvom zamene na nekoj algebri one funkcije koje se
sla`u sa svakom kongruencijom te algebre. Jasno je da svaka algebarska funkcija ima
svojstvo zamene. Gra¨tzer je pokazao da svaka funkcija na Bulovoj algebri f : Bn → B
kojaimasvojstvozamenejeBulovafunkcija. Sli~nojeiuPostovimalgebrama. Me|utim,
nije svaka funkcija sa svojstvom zamene na Stonovoj algebri, algebarska (Stonova). To
pokazuje slede}i primer.
PRIMER 3.1. Neka je L3 = {0, p, 1} troelementni lanac. Kako je svaki lanac Stonova
algebrato jeiL3Stonovaalgebra. Operacijeovealgebremo`emoprikazatitablicama:
21
∧ 0 p 1
0 0 0 0
p 0 p p
1 0 p 1
,
∨ 0 p 1
0 0 p 1
p p p 1
1 1 1 1
,
∗
0 1
p 0
1 0
.
Jedina netrivijalna kongruencija ove algebre je kongruencija ~ije su klase {1, p}
i {0}. Funkcija f : L3 → L3 definisana sa f(0) = 1, f(p) = 1, f(1) = p ima
svojstvo zamene. Poka`imo da ova funkcija nije algebarska. Ako bi ova funkcija bila
algebarska, onda indukcijom po slo`enostifunkcije f mo`emo dokazati da se ona mo`e
izraziti u obliku
f(x) = (a ∧ x) ∨ (b ∧ x∗) ∨ (c ∧ x∗∗).
Tada iz f(p) = 1 i f(1) = p dobijamo
(a ∧ p) ∨ c = 1 i a ∨ c = p,
pa je
p = p ∨ (p ∧ c) = (a ∨ c) ∧ (p ∨ c) = (a ∧ p) ∨ c = 1,
kontradikcija. Dakle, f nije algebarska funkcija.
Koriste}i pomo}nuBulovufunkciju na centruB(L)Stonove algebreL,Beazer daje
uslov konzistentnosti i opisuje re{ewa jedna~ine f(x1, . . . , xn) = 0, gde je f funkcija
sa svojstvom zamene.
TEOREMA 3.3. [15] Neka je L Stonova algebra i n ∈ N . Pretpostavimo da funkcija
f : Ln → L ima svojstvo zamene i da je funkcija f¯ : B(L)n → B(L) definisana na
slede}i na~in
f¯(x∗∗1 , . . . , x
∗∗
n ) = (f(x1, . . . , xn))
∗∗ (x1, . . . , xn ∈ L).
Tada
(i) f¯ je Bulova funkcija;
(ii) f(x1, . . . , xn) = 0⇔ f¯(x∗∗1 , . . . , x∗∗n ) = 0.
(iii) f(x1, . . . , xn) = 0 va`i identi~ki ako i samo ako f(α1, . . . , αn) = 0 za svako
α1, . . . , αn ∈ {0, 1};
(iv) jedna~ina f(x1, . . . , xn) = 0 ima re{ewe ako i samo ako∧
A∈{0,1}n
f(A) = 0.
Utom slu~aju, (x1, . . . , xn) je re{ewe ako i samo ako va`i
xj =
∧
(aj+1,...,an)∈{0,1}n−j
f(x1, . . . , xj−1, 0, aj+1, . . . , an) (j = 1, . . . , n).
22
Navedimo definicije pojmova op{teg i reproduktivnog op{teg re{ewa jedna~ine
na Stonovoj algebri.
Neka je (L,∧,∨, ∗, 0, 1) Stonova algebra,X = (x1, . . . , xn), T = (t1, . . . , tn) ∈ Ln.
DEFINICIJA 3.2. [15]Neka jeL Stonova algebra i f, h1, . . . , hn : L
n → L. Formule
xi = hi(t1, . . . , tn) (i = 1, . . . , n)
defini{u op{te re{ewe konzistentne jedna~ine f(x1, . . . , xn) = 0 ako i samo ako
(∀X ∈ Ln) (f(X) = 0⇔ (∃T ∈ Ln)X = (h1(T ), . . . , hn(T ))) .
DEFINICIJA 3.3. [15]Neka jeL Stonova algebra i f, h1, . . . , hn : L
n → L. Formule
xi = hi(t1, . . . , tn) (i = 1, . . . , n)
odre|uju reproduktivno op{te re{ewe konzistentne jedna~ine f(x1, . . . , xn) = 0 ako
i samo ako
(∀X ∈ Ln) (f(X) = 0⇔ X = (h1(X), . . . , hn(X))) .
Slede}a teorema predstavqa uop{tewe Lo¨wenheim-ove teoreme (Teorema 2.8) na
jedna~ine na Stonovim algebrama.
TEOREMA 3.4. [15] Neka je L Stonova algebra i f : Ln → L funkcija sa svojstvom
zamene. Neka je (ξ1, . . . , ξn) ∈ Ln partikularno re{ewe jedna~ine f(x1, . . . , xn) = 0.
Tada je formulama
xi = (ξi ∧ f(t1, . . . , tn)) ∨ (ti ∧ (f(t1, . . . , tn))∗) (i = 1, . . . , n)
odre|eno reproduktivno re{ewe jedna~ine f(x1, . . . , xn) = 0.
Napomena 3.1. Kako u Stonovoj algebri va`i
f ≤ g∗ ⇐⇒ f ∧ g∗∗ = 0
to se prethodna teorema mo`e primeniti i prilikom re{avawa nejedna~ina oblika
f ≤ g∗.
DEFINICIJA 3.4. Neka je (L,∧,∨, ∗, 0, 1) Stonova algebra. Ako postoji element
d = min{x ∈ L|x∗ = 0} onda se on zove najmawi gust element.
KlasaStonovihalgebrisanajmawimgustimelementomsemo`eposmatratiikao jed-
nakosna klasa algebri oblika (L,∧,∨, ∗, 0, 1, d), gde je (L,∧,∨, ∗, 0, 1)Stonova algebra
i va`e jednakosti
d∗ = 0,
(∀x ∈ L) d ∧ (x ∨ x∗) = d.
U Stonove algebre sa najmawim gustim elementon spadaju, izme|u ostalog, kona~ne
Stonove algebre, dobro ure|eni skupovi sa najve}im elementom itd.
Beazer je uop{tioiMu¨ller-Lo¨wenheim-ovuteoremunafunkcije sa svojstvomzamene
u Stonovim algebrama sa najmawim gustim elementom.
23
TEOREMA 3.5. [15] Neka je L Stonova algebra sa najmawim gustim elementom d i neka
su f, g : Ln → Lfunkcije sa svojstvom zamene. Tada
f = g ⇐⇒ (∀(δ1, . . . , δn) ∈ {0, d, 1}n) f(δ1, . . . , δn) = g(δ1, . . . , δn).
Slede}a teorema je originalni publikovan rezultat. U woj je opisana klasa repro-
duktivnih re{ewa jedna~ine naStonovoj algebri, pod uslovom da je poznato jedno op{te
re{ewe.
TEOREMA 3.6. [27] Neka je L Stonova algebra i f, g1, . . . , gn : L
n → L funkcije sa
svojstvom zamene. Neka je formulama
xi = gi(T ) (i = 1, . . . , n)
odre|eno op{te re{ewe jedna~ine f(x1, . . . , xn) = 0. Ako su p1, . . . , pn : L
n → L
funkcije sa svojstvom zamene onda je formulama
xi = (ti ∧ (f(T ))∗) ∨ (f(T ) ∧ gi(p1(T ), . . . , pn(T ))) (i = 1, . . . , n) (3.2)
definisano reproduktivno op{te re{ewe jedna~ine f(x1, . . . , xn) = 0.
Dokaz. Neka je formulama xi = gi(t1, . . . , tn) (i = 1, . . . , n) odre|eno op{te
re{ewe jedna~inef(x1, . . . , xn) = 0naStonovoj algebri (L,∧,∨, ∗, 0, 1). Defini{imo
funkcije f¯ , g¯i : (B(L))
n → B(L) (i = 1, . . . , n) na slede}i na~in
f¯(x∗∗1 , . . . , x
∗∗
n ) = (f(x1, . . . , xn))
∗∗
g¯i(x
∗∗
1 , . . . , x
∗∗
n ) = (gi(x1, . . . , xn))
∗∗,
za svako (x1, . . . , xn) ∈ Ln. Prema Teoremi 3.3, f¯ , g¯i (i = 1, . . . , n) su Bulove funkcije.
Najpre }emo dokazati da je sa x∗∗i = g¯i(t
∗∗
1 , . . . , t
∗∗
n ) definisano op{te re{ewe pomo}ne
Bulove jedna~ine f¯(x∗∗1 , . . . , x
∗∗
n ) = 0 u Bulovoj algebriB(L). Iz
f(g1(X), . . . , gn(X)) = 0, za svakoX ∈ Ln,
dobijamo (f(g1(X), . . . , gn(X)))
∗∗ = 0. Prema Teoremi 3.3 sledi da je
f¯((g1(X))
∗∗, . . . , (gn(X))∗∗) = 0
i
f¯(g¯1(X
∗∗), . . . , g¯n(X∗∗)) = 0 za svakoX∗∗ ∈ (B(L))n.
Pretpostavimo da je f¯(Y ) = 0 za neko Y ∈ (B(L))n. Prema Teoremi 1.12 sledi da
postojiX ∈ Ln tako da je Y = X∗∗. Odavde je f¯(X∗∗) = 0{to, prema Teoremi 3.3 daje
f(X) = 0. Iz pretpostavke da je formulama xi = gi(T ) (i = 1, . . . , n) odre|eno op{te
re{ewe jedna~ine f(x1, . . . , xn) = 0 sledi da postoji T ∈ Ln tako da je xi = gi(T )
(i = 1, . . . , n). Tada je
x∗∗i = (gi(T ))
∗∗ = g¯i(T ∗∗),
24
odakle sledi da je formulama x∗∗i = g¯i(T
∗∗) (i = 1, . . . , n) definisano op{te re{ewe
Bulove jedna~ine f¯(x∗∗1 , . . . , x
∗∗
n ) = 0. Ozna~imo desnu stranu jednakosti (3.2) sa hi(T )
tj.
hi(T ) = (ti ∧ (f(T ))∗) ∨ (f(T ) ∧ gi(p1(T ), . . . , pn(T ))) (i = 1, . . . , n).
Iz Leme 1.2 i Leme 1.3 sledi
(hi(T ))
∗∗ =
(
t∗∗i ∧ ((f(T ))∗∗)∗
) ∨ ((f(T ))∗∗ ∧ (gi (p1(T ), . . . , pn(T )))∗∗) , T ∈ Ln.
Defini{imo preslikavawa h¯i : (B(L))
n → B(L), h¯i(X∗∗) = (hi(X))∗∗, X ∈ Ln.
Tada je
h¯i(T
∗∗) =
(
t∗∗i ∧ (f¯(T ∗∗))∗
) ∨ (f¯(T ∗∗) ∧ g¯i ((p1(T ))∗∗, . . . , (pn(T ))∗∗)) , T ∈ Ln.
Po{to su p1, . . . , pn funkcije sa svojstvom zamene, prema Teoremi 3.3 sledi da su
p¯i : (B(L))
n → B(L), p¯i(T ∗∗) = (pi(T ))∗∗ Bulove funkcije i da va`i
h¯i(T
∗∗) =
(
t∗∗i ∧ (f¯(T ∗∗)∗)
) ∨ (f¯(T ∗∗) ∧ g¯i (p¯1(T ∗∗), . . . , p¯n(T ∗∗))) , T ∗∗ ∈ (B(L))n.
Prema Teoremi 2.10 imamo da je formulama x∗∗i = h¯i(T
∗∗) (i = 1, . . . , n) odre|eno
op{te reproduktivno re{ewe Bulove jedna~ine f¯(x∗∗1 , . . . , x
∗∗
n ) = 0.
Tada je
f¯
(
h¯1(X
∗∗), . . . , h¯n(X∗∗)
)
= 0 ⇒ f¯ ((h1(X))∗∗, . . . , (hn(X))∗∗) = 0
⇒ (f(h1(X), . . . , hn(X)))∗∗ = 0
⇒ f(h1(X), . . . , hn(X)) = 0.
Pretpostavimo sada da je f(X) = 0. Tada
hi(X) = (xi ∧ (f(X))∗) ∨ (f(X) ∧ gi(p1(X), . . . , pn(X)))
= (xi ∧ 1) ∨ (0 ∧ gi(p1(X), . . . , pn(X)))
= xi.
Dakle, formule xi = hi(T ), (i = 1, . . . , n) odre|uju reproduktivno op{te re{ewe
jedna~ine f(x1, . . . , xn) = 0. ¤
25
Glava 4
Jedna~ine u vi{evrednosnoj logici
Po~ecivi{evrednosnelogikenalaze se jo{uradovimaAristotela, aweniosniva~i
u dana{wem smislu su Lukasiewicz i Post. Danas je ova oblast u velikoj ekspanziji, pre
svega zbog svoje primene u kompjuterskoj tehnologiji.
Vi{evrednosnalogika jenastalakaouop{teweiskazne (dvovrednosne)logikeizpo-
trebe za iskazima koji mogu imati vi{e od dve vrednosti. U algebarskom smislu, Bulovu
algebru B2 = {0, 1} (koja odgovara iskaznoj logici) zamewujemo linearno ure|enim
skupom (lancem)K = {0, 1, . . . , k − 1} celih brojeva, koji u odnosu na operacijemin i
maxpredstavqadistributivnumre`u. Funkcijei jedna~inenaovojmre`ipredstavqaju
uop{tewe Bulovih funkcija i jedna~ina na dvoelementnoj Bulovoj algebriB2.
4.1 Osnovni pojmovi
U ovom odeqku }e biti navedene definicije i neke osobine elementarnih operacija
na skupu K = {0, 1, . . . , k − 1} logi~kih vrednosti k-vrednosne logike, a zatim i
va`na teorema reprezentacije k-vrednosnih operacija na skupuK . Za pisawe ovog dela
kori{}ena je monografija S. Jablonskij  Introduction to discrete mathematics.
DEFINICIJA 4.1. Neka je k pozitivan ceo broj i K = {0, 1, . . . , k − 1}. Elemente
skupaK }emo zvati logi~ke vrednosti. Svako preslikavawe f : Kn → K }emo zvati
n−arna k−vrednosna operacija.
Neke od elementarnih operacija naK su:
1. Ii(x) =
{
k − 1, za x = i
0, za x 6= i,
2. min(x1, x2) (uop{tewe konjunkcije),
3. max(x1, x2) (uop{tewe disjunkcije),
26
4. x = x+ 1(modk),
5. Nx = k − 1− x ( Lukasiewicz-eva negacija, uop{tewe komplementa).
Operacije min(x1, x2) i max(x1, x2) su komutativne, asocijativne i zadovoqavaju
distributivni zakon, pa je (K,min,max) distributivna mre`a sa najmawim elementom
0 i najve}im elementom k − 1. Umestomin(x1, x2) pisa}emo x1 · x2 ili x1x2, dok }emo
umestomax(x1, x2) pisati x1 ∨ x2. Iz
x∗ = max{y|x ∧ y = 0} =
{
0, x 6= 0
k − 1, x = 0 = I0(x)
sledi da je (K, ·,∨, I0, 0, k − 1) pseudokomplementarna mre`a. Kako je jo{
I0(x) ∨ I0(I0(x)) = k − 1,
pomenuta pseudokomplementarna mre`a je Stonova algebra. Iz
I0(I0(x)) =
{
I0(k − 1), x = 0
I0(0), x 6= 0 =
{
0, x = 0
k − 1, x 6= 0
sledi da je
I0(I0(x)) = x⇐⇒ x ∈ {0, k − 1},
pa su jedini regularni, a samim tim i Bulovi elementi 0 i k − 1. Jasno je, tako|e,
da je (K, ·,∨, I0, . . . , Ik−1, 0, 1, . . . , k − 1) Postova algebra, pri ~emu su disjunktivne
komponente proizvoqnog elementa i ∈ K date sa
ih = Ih(i) =
{
k − 1, h = i
0, h 6= i .
Lako se mo`e proveriti da se svaka n−arna k−vrednosna funkcija mo`e prikazati
u formi sli~noj disjunktivnoj normalnoj formi za Bulove funkcije.
TEOREMA 4.1. [25]Neka je f : Kn → K n−arna k−vrednosna funkcija. Tada
f(x1, . . . , xn) =
∨
(σ1,...,σn)∈Kn
f(σ1, . . . , σn)Iσ1(x1) . . . Iσn(xn),
tj. svaka k-vrednosna funkcija se mo`e izraziti pomo}u ·, ∨ i Ii(x).
4.2 Op{ta re{ewa jedna~ina sa jednom nepoznatom
u vi{evrednosnoj logici
Jedna~ine na vi{evrednosnoj logici su prvi po~eli da prou~avaju Itoh, Goto i
Carvallo. Oni su (nezavisno jedan od drugih) dali uslov konzistentnosti jedna~ine sa
jednom nepoznatom, metodu sukcesivne eliminacije, uop{tewe Lo¨wenheim-ove teoreme
27
i drugo. Bankovi} je opisao sva reproduktivna re{ewa jedna~ine sa jednom nepoz-
natom. Navodimo neke od ovih rezultata. Tako|e }e biti opisana sva op{ta re{ewa
ovakvih jedna~ina. Napomiwemo da je, imaju}i u vidu Teoremu 4.1 i ~iwenicu da je
(K, ·,∨, I0, . . . , Ik−1, 0, 1, . . . , k − 1) Postova algebra, ovakve jedna~ine mogu}e posma-
trati i kao Postove jedna~ine.
DEFINICIJA 4.2. Jedna~ina oblika
f(x1, . . . , xn) = g(x1, . . . , xn), (4.1)
gde su f, g : Kn → K k−vrednosne funkcije, se zove k−vrednosna jedna~ina.
DEFINICIJA 4.3. Partikularno re{ewe, ili samo re{ewe, jedna~ine (4.1), je svaka
n−torka (x1, . . . , xn) ∈ Kn koja zadovoqava jedna~inu (4.1). Re{iti k−vrednosnu
jedna~inu zna~i odrediti skup S svih wenih re{ewa.
Sada }e biti razmatrane k−vrednosne jedna~ine sa jednom nepoznatom.
TEOREMA 4.2. [9] Svaka k−vrednosna jedna~ina sa jednom nepoznatom ili sistem
k−vrednosnih jedna~ina sa jednom nepoznatom je ekvivalentan jednoj k−vrednosnoj
jedna~ini oblika h(x) = 0.
Iz Teoreme 4.2 i Teoreme 4.1 sledi da je svaka jedna~ina sa jednom nepoznatom u
vi{evrednosnoj logici oblika
a0I0(x) ∨ a1I1(x) ∨ · · · ∨ ak−1Ik−1(x) = 0 (a0, . . . , ak−1 ∈ K). (4.2)
DEFINICIJA 4.4. [9]Neka je f(x) = 0 konzistentna k−vrednosna jedna~ina. Formula
x = g(t), gde g : K → K , defini{e op{te re{ewe jedna~ine f(x) = 0 ako i samo ako
(∀x ∈ K)(f(x) = 0⇔ (∃t ∈ K)x = g(t)).
DEFINICIJA 4.5. [9]Neka je f(x) = 0 konzistentna k−vrednosna jedna~ina. Formula
x = g(t), gde g : K → K , defini{e reproduktivno op{te re{ewe jedna~ine f(x) = 0
ako i samo ako
(∀x ∈ K)(f(x) = 0⇔ x = g(x)).
TEOREMA 4.3. [9] Vrednost n ∈ {0, . . . , k − 1} je re{ewe jedna~ine
a0I0(x) ∨ · · · ∨ ak−1Ik−1(x) = 0
ako i samo ako an = 0.
TEOREMA 4.4. [9] Jedna~ina
a0I0(x) ∨ · · · ∨ ak−1Ik−1(x) = 0
je konzistentna ako i samo ako
a0a1 . . . ak−1 = 0. (4.3)
28
Sva reproduktivna op{ta re{ewa jedna~ine (4.2) je opisao Bankovi}.
TEOREMA 4.5. [9]Neka je (4.2) konzistentna jedna~ina i neka su
(im,0, im,1, . . . , im,k−1) permutacije skupaK (m = 0, 1, . . . , k − 1)
takve da je
(i0,0, i1,0, . . . , ik−1,0) = (0, 1, . . . , k − 1).
Formula x = φ(t) defini{e reproduktivno op{te re{ewe jedna~ine (4.2) ako i samo
ako
φ(t) = I0(ait,0)it,0 ∨ I0(I0(ait,0))I0(ait,1)it,1 ∨ I0(I0(ait,0))I0(I0(ait,1))I0(ait,2)it,2 ∨ . . .
∨I0(I0(ait,0))I0(I0(ait,1)) . . . I0(I0(ait,k−2))I0(ait,k−1)it,k−1.
Sva op{ta re{ewa jedna~ine (4.2) su opisana u slede}oj teoremi (originalni pub-
likovan rezultat).
TEOREMA 4.6. [28]Neka je (4.2) konzistenta jedna~ina i neka su
(im,0, im,1, . . . , im,k−1) permutacije skupaK (m = 0, 1, . . . , k − 1) (4.4)
takve da je
(i0,0, i1,0, . . . , ik−1,0) permutacija skupaK (m = 0, 1, . . . , k − 1). (4.5)
Formula x = φ(t) defini{e op{te re{ewe jedna~ine (4.2) ako i samo ako
φ(t) = I0(ait,0)it,0 ∨ I0(I0(ait,0))I0(ait,1)it,1
∨I0(I0(ait,0))I0(I0(ait,1))I0(ait,2)it,2 ∨ . . . (4.6)
∨I0(I0(ait,0))I0(I0(ait,1)) . . . I0(I0(ait,k−2))I0(ait,k−1)it,k−1.
Dokaz. Dokaza}emo da formula x = φ(t), data u (4.6), defini{e op{te re{ewe
jedna~ine (4.2). Neka je t ∈ K = {0, 1 . . . , k − 1}. Uslovi (4.3) i (4.4) daju
ait,0ait,1 . . . ait,k−1 = 0,
iz ~ega sledi da postoji element niza ait,0 , ait,1 , . . . , ait,k−1 koji je jednak 0. Neka je ait,s
prvi takav element u nizu. Tada
I0(ait,n) = 0, za n < s,
I0(I0(ait,0))I0(I0(ait,1)) . . . I0(ait,s)it,s = (k − 1)(k − 1) . . . (k − 1)it,s = it,s,
I0(I0(ait,0))I0(I0(ait,1)) . . . I0(I0(ait,s)) . . . I0(ait,n)it,n = 0, za n > s,
(zbog I0(I0(ait,s)) = I0(k − 1) = 0).
Dakle φ(t) = it,s. Po{to je ait,s = 0, prema Teoremi 4.4 sledi da it,s zadovoqava (4.2) tj.
x = φ(t) je re{ewe jedna~ine (4.2).
29
Neka je r re{ewe jedna~ine (4.2). Dokaza}emo da postoji element t ∈ K takav da je
r = φ(t). Po{to je (i0,0, i1,0, . . . , ik−1,0) permutacija skupaK , postoji s ∈ K tako da je
is,0 = r. Uzimaju}i t = s dobijamo
φ(s) = I0(ais,0)is,0 ∨ I0(I0(ais,0))I0(ais,1)is,1 ∨ I0(I0(ais,0))I0(I0(ais,1))I0(ais,2)is,2 ∨ . . .
∨I0(I0(ais,0))I0(I0(ais,1)) . . . I0(I0(ais,k−2))I0(ais,k−1)is,k−1.
Kako je ais,0 = ar = 0 imamo da va`i I0(ais,0) = k − 1 i I0(I0(ais,0)) = I0(k − 1) = 0.
Odavde je φ(s) = (k − 1) · is,0 ∨ 0 · is,1 ∨ · · · ∨ 0 · is,k−1 = is,0 = r.
Sada}emopokazati da se svakoop{tere{ewe jedna~ine (4.2)mo`enapisati uobliku
(4.6). Neka
F =
(
0 1 . . . k − 1
y0 y1 . . . yk−1
)
predstavqa op{te re{ewe jedna~ine (4.2). Neka je R = {i|ai = 0}. Prema Teoremi
4.3,R je skup svih re{ewa jedna~ine (4.2). Kako F predstavqa op{te re{ewe, imamo da
je R = {y0, . . . yk−1}. Svakako je ayi = 0 za svako i ∈ K . Neka je A ⊂ K takav da je
F : A → R bijekcija. Po{to je card(A) = card(R) i card(K \ A) = card(K \ R),
sledi da postoji funkcija g : K \ A → K \ R koja je bijekcija. O~igledno je da je
funkcija h : K → K , odre|ena sa
h(x) =
{
F (x), x ∈ A
g(x), x /∈ A
tako|e bijekcija. Za svako m ∈ {0, 1, . . . , k − 1} defini{imo permutaciju
(im,0, im,1, . . . im,k−1) na slede}i na~in:
• im,0 = h(m),
• ako im,0 6= ym onda im,1 = ym,
• ako im,0 = ym onda im,1 = z, za neko z 6= ym,
• ostali ~lanovi permutacije (im,0, im,1, . . . , im,k−1) su proizvoqni, ali takvi da je
(4.5) zadovoqeno.
Pokaza}emo da je F = φ. Neka je t proizvoqan element skupaK . Tada je it,0 = h(t).
(i) Ako t ∈ A onda it,0 = h(t) = F (t) = yt. Po{to je yt odnosno it,0 re{ewe
jedna~ine (4.2), po Teoremi 4.3 sledi da je ait,0 = 0. Odatle je I0(ait,0) = k − 1 i
I0(I0(ait,0)) = 0, iz ~ega sledi
φ(t) = (k − 1)it,0 ∨ 0 · it,1 ∨ · · · ∨ 0 · it,k−1 = it,0 = yt = F (t).
(ii) Ako t /∈ A onda it,0 = h(t) = g(t) ∈ K \ R i it,1 = yt. Dakle it,0 nije re{ewe
jedna~ine (4.2), a it,1 je re{ewe jedna~ine (4.2), pa jeait,0 6= 0 iait,1 = 0, poTeoremi
4.3. Daqe je
I0(ait,0) = 0, I0(I0(ait,0)) = k − 1, I0(ait,1) = k − 1, I0(I0(ait,1)) = 0,
30
iz ~ega sledi
φ(t) = 0 · it,0 ∨ (k− 1)(k− 1) · it,1 ∨ · · · ∨ (k− 1) · 0 · · · it,k−1 = it,1 = yt = F (t).
¤
Napomena 4.1. Lako se proverava da je vrednost n (0 ≤ n ≤ k − 1) re{ewe jedna~ine
I0(I0(a0))I0(x) ∨ · · · ∨ I0(I0(ak−1))Ik−1(x) = 0 (4.7)
akoi samo akoan = 0. Imaju}i u viduTeoremu 4.3, jedna~ine (4.2) i (4.7) su ekvivalentne.
Primetimo da je I0(I0(a0)), . . . , I0(I0(ak−1)) ∈ {0, k − 1}. Mo`e se pokazati da je
jedna~ina (4.7) specijalan slu~aj Pre{i}eve jedna~ine (1.1). Uzimaju}i za T skupK , za
istaknute elemente (0 i 1) elemente 0 i k− 1, a za operacije+, ◦ ixy na skupuT ∪{0, 1}
operacije∨, · i Ix(y) proveravamo da je
x∨0 = 0∨x = x, x·0 = 0·x = 0, x·(k−1) = (k−1)·x = x, Ix(y) =
{
k − 1, x = y
0, x 6= y .
Stavqaju}i jo{ (s0, s1, . . . , sm) = (I0(I0(a0)), I0(I0(a1)), . . . , I0(I0(ak−1))), zakqu~uje-
mo da je jedna~ina (4.7) oblika (1.1). Sva op{ta re{ewa jedna~ine (1.1) su opisana u
Teoremi 1.3.
PRIMER 4.1. Re{iti jedna~inu a0I0(x) ∨ a1I1(x) ∨ a2I2(x) = 0 u 3-vrednosnoj logici.
Prema Teoremi 4.6, op{te re{ewe je odre|eno sa
φ(t) = I0(ait,0)it,0 ∨ I0(I0(ait,0))I0(ait,1)it,1 ∨ I0(I0(ait,0))I0(I0(ait,1))I0(ait,2)it,2,
gde su (it,0, it,1, it,2)permutacije skupa{0, 1, 2}, (za t ∈ {0, 1, 2}), takve da je (i1,0, i2,0, i3,0)
tako|e permutacija skupa {0, 1, 2}.
Ako, na primer, a0 = 0, a1 = 0 i a2 = 2, uzimaju}i permutacije (1, 0, 2), (0, 2, 1) i
(2, 0, 1), dobijamo op{te re{ewe
x =
(
0 1 2
1 0 0
)
.
Uzimaju}i permutcije (0, 2, 1), (1, 2, 0), (2, 0, 1) dobijamo reproduktivno re{ewe
x =
(
0 1 2
0 1 0
)
.
31
Glava 5
Jedna~ine na Postovim algebrama
Problemom jedna~ina u distributivnim mre`ama, u koje spadaju i Postove al-
gebre, prvi su po~eli da se bave Goodstein (mre`e sa 0 i 1) i Rudeanu (mre`e bez
0 i 1). U [43] Serfati objavquje neke rezultate o parametarskim re{ewima jedna~ina,
nejedna~ina i sistema jedna~ina uPostovim algebrama. Do najva`nijih rezultata u ovoj
oblasti su do{li Serfati, Bordati Carvallo, nezavisno jedanod drugog. Ve}ina tvr|ewa
predstavqa generalizaciju odgovaraju}ih tvr|ewa u teoriji Bulovih algebri.
5.1 Definicija i osnovne osobine Postovih algebri
Prvi sistem aksioma za algebre koje odgovaraju vi{evrednosnoj Postovoj logici je
dao Rosenbloom [35] 1924. godine, koji ih je i nazvao Postovim algebrama. Me|utim,
wegov sistem aksioma je bio veoma nerazumqiv i komplikovan za primenu u daqem
prou~avawu ovih algebri. Epstein [22] daje mnogo jednostavniju i operativniju aksi-
omatizacijuPostovih algebri. Ovde}ebitikori{}ena Epstein-ova definicija, koju je
doneklemodifikovao Rudeanu [40]. Pored definicije, u ovomodeqku }e biti navedene
i osnovne osobine ra~una u Postovim algebrama.
Neka je r fiksiran ceo broj, r ≥ 2.
DEFINICIJA 5.1. [40]Nizelemenatax0, x1, . . . , xr−1 ograni~enedistributivnemre`e
(P,∧,∨, 0, 1) ~ini ortonormalan sistem ako i samo ako va`i
r−1∨
i=0
xi = 1, xi ∧ xj = 0 (i, j = 0, . . . , r − 1, i 6= j).
LEMA 5.1. [40] Svaki element xi ortonormalnog sistema (x0, x1, . . . , xr−1) je Bulov
element.
Dokaz. Iz
xj ∨
r−1∨
i=0,i6=j
xi = 1, (
r−1∨
i=0,i 6=j
xi) ∧ xj =
r−1∨
i=0,i6=j
(xi ∧ xj) = 0 (j = 0, . . . , r − 1)
32
sledi
(xj)′ =
r−1∨
i=0,i6=j
xi (j = 0, . . . , r − 1).
¤
TEOREMA 5.1. [40] Neka je (P,∧,∨, 0, 1) ograni~ena distributivna mre`a i neka ele-
menti e0, e1, . . . , er−1 zadovoqavaju uslov e0 = 0 < e1 < e2 < · · · < er−1 = 1. Tada su
slede}i uslovi ekvivalentni
(i) svaki element x ∈ P ima jedinstvenu reprezentaciju u obliku
x =
r−1∨
k=1
(x(k) ∧ ek),
gde su x(k) ∈ B(P ) (k = 1, . . . , r − 1) i va`i x(1) ≥ x(2) ≥ · · · ≥ x(r−1).
(ii) svaki element x ∈ P ima jedinstvenu reprezentaciju u obliku
x =
r−1∨
i=0
(xi ∧ ei),
gde x0, x1, . . . , xr−1 ~ine ortonormalan sistem.
POSLEDICA 5.1. Ako u ograni~enoj distributivnoj mre`i (P,∧,∨, 0, 1) va`e ekviva-
lentni uslovi (i) i (ii) iz Teoreme 5.1 onda su koeficijenti x(k) i x
i
iz reprezentacija
(i) i (ii) povezani slede}im relacijama:
x0 = x′(1), x
i = x(i) ∧ x′(i+1) (i = 1, . . . , r − 2), xr−1 = x(r−1),
x(k) =
r−1∨
j=k
xj (k = 1, . . . , r − 1).
DEFINICIJA 5.2. [40] Postova algebra reda r je algebra (P,∧,∨, e0, e1, . . . , er−1), gde
je (P,∧,∨, 0, 1) ograni~ena distributivna mre`a, elementi ei zadovoqavaju uslov
e0 = 0 < e1 < · · · < er−1 = 1 i va`e ekvivalentni uslovi (i) i (ii) iz Teoreme 5.1. Niz
e0, . . . , er−1 se zove lanac konstanti Postove algebre P , xo, . . . , xr−1 su disjunktivne
iliPostovekomponenteelementax, ax(1), . . . , x(r−1)monotonekomponenteelementa
x.
Ovakodefinisanaalgebrajetipa(2, 2, (0)r). Me|utim,akodisjunktivnekomponente
posmatramo kao niz unarnih operacija na skupu P , {to nam omogu}ava Teorema 5.1 (ii),
Postovu algebru mo`emo smatrati algebrom tipa (2, 2, (1)r, (0)r).
U svakoj Postovoj algebri monotone i disjunktivne komponente elemenata ei su date
formulama
(ei)(k) =
{
1, k ≤ i
0, k > i
, za k = 1, . . . , r − 1
33
i(ei)
h =
{
1, h = i
0, h 6= i , za h = 0, 1, . . . , r − 1. (5.1)
PRIMER 5.1. Svaki r−elementni lanac Cr = {e0 = 0, e1, . . . , er−1 = 1}, e0 < e1 <
· · · < er−1, postaje r−Postova algebra, ako se ∨ i ∧ defini{u kao max i min, a za
lanac konstanti uzme ceo skupCr. Jedini Bulovi elementi u ovoj Postovoj algebri su 0
i 1 (Primer 1.4).
TEOREMA 5.2. [40]Neka jeP Postova algebra i i ∈ {0, 1, . . . , r− 1}. Za element x ∈ P
slede}i uslovi su ekvivalentni:
(i) xi = 1;
(ii) xj = 0 za svako j 6= i;
(iii) x(1) = · · · = x(i) = 1, x(i+1) = . . . x(r−1) = 0;
(iv) x = ei.
TEOREMA 5.3. [40]Slede}i uslovi su ekvivalentni za svaki element xPostove algebre
P :
(i) x ∈ B(P );
(ii) x(k) = x za svako k ∈ {1, . . . , r − 1};
(iii) x(k) = x za neko k ∈ {1, . . . , r − 1};
(iv) x0 = x′, xi = 0 (i = 1, . . . , r − 2), xr−1 = x;
(v) xi = 0 (i = 1, . . . , r − 2).
TEOREMA 5.4. [40]SvakaPostovaalgebra jeStonovaalgebraidualnaStonovaalgebra.
Pri tome, za svako x ∈ P , pseudokomplement je
x∗ = x′(1) = x
0,
dok je dualni pseudokomplement jednak
x+ = x′(r−1) = (x
r−1)′.
Radi jednostavnijeg zapisa uvedimo slede}e oznake:
1) Operaciju ∧ ozna~imo sa · ili je jednostavno izostavimo. Dakle, pisa}emo x · y
ili xy umesto x ∧ y.
2) Za i ∈ {0, 1, . . . , r − 1} i x ∈ P pisa}emo xi = xei .
3) ZaX = (x1, . . . , xn) ∈ P n iA = (α1, . . . , αn) ∈ Cnr uvodimo
XA = xα11 . . . x
αn
n .
34
Iz Teoreme 5.2 i jednakosti (5.1) sledi da za α, β ∈ Cr va`i
αβ =
{
1, α = β
0, α 6= β ,
{to daqe, zaA,B ∈ Cnr , daje
AB =
{
1, A = B
0, A 6= B .
TEOREMA 5.5. [16, 46]Neka je P Postova algebra i x, y ∈ P . Tada va`i
x = y ⇐⇒
r−1∨
i=0
xi(yi)′ = 0⇐⇒
r−1∨
i=0
xiyi = 1. (5.2)
POSLEDICA 5.2. Neka je P Postova algebra i x, y ∈ P . Tada
x ≤ y ⇐⇒
r−1∨
i=0
r−1∨
h=i
xiyh = 1⇐⇒
r−2∨
i=0
r−1∨
h=i+1
xhyi = 0.
Napomena 5.1. Ako se defini{e binarna operacija+ na slede}i na~in
x+ y =
r−1∨
i=0
xi(yi)′, x, y ∈ P,
onda se (5.2) mo`e zapisati u obliku
x = y ⇐⇒ x+ y = 0.
5.2 Postove funkcije
PodPostovomfunkcijom podrazumeva se algebarskafunkcija (u smisluDefinicije
1.4) na Postovoj algebri (P,∧,∨, (i)i=0,...,r−1, (ei)i=0,...,r−1). Dakle, Postova funkcija
je svaka funkcija sagra|ena od konstantnih funkcija i projekcija kona~nom primenom
operacija ∧,∨, (i)i=0,...,r−1. Pod prostom Postovom funkcijom podrazumeva se polinom
nad Postovom algebrom, tj. algebarska funkcija u kojoj ne figuri{u konstante.
Karakterizaciju Postovih funkcija daje slede}a teorema.
TEOREMA 5.6. [22, 43]Neka je P Postova algebra, n ∈ N i f : P n → P . Funkcija f je
Postova ako i samo ako se mo`e zapisati u obliku
f(x1, . . . , xn) =
∨
(α1,...,αn)∈Cnr
f(α1, . . . , αn)x
α1
1 · · · xαnn . (5.3)
Jednakost (5.3) je poznata kao disjunktivna normalna forma Postove funkcije f .
35
POSLEDICA 5.3. SvakaPostovafunkcijaponpromenqivih jepotpunoodre|enasvojom
restrikcijom na skupCnr .
POSLEDICA 5.4. Svaka funkcija f : Cnr → P se na jedinstven na~in mo`e ra{iriti u
Postovu funkciju f : P n → P .
POSLEDICA 5.5. Ako su f, g : P n → P Postove funkcije onda va`i
f = g ⇐⇒ (∀A ∈ Cnr )f(A) = g(A).
Jasno je iz prethodnih tvr|ewa da identiteti koji va`e na svimPostovim algebrama
su oni koji va`e uCnr .
TEOREMA 5.7. [43] Skup svih Postovih funkcija f : P n → P je Postova algebra u
odnosu na operacije definisane na slede}i na~in:
(f · g)(A) =
∨
A∈Cnr
(f(A) · g(A))XA,
(f ∨ g)(A) =
∨
A∈Cnr
(f(A) ∨ g(A))XA,
f i(X) =
∨
A∈Cnr
(f(A))iXA (i = 0, . . . , r − 1),
ei(X) = ei (i = 0, 1, . . . , r − 1).
POSLEDICA 5.6. Za svaku Postovu funkciju f : P n → P slede}i uslovi su ekviva-
lentni:
(i) f je Bulov element algebre Postovih funkcija definisane u Teoremi 5.7;
(ii) f(X) ∈ B(P ) za svakoX ∈ P n;
(iii) f(A) ∈ B(P ) za svakoA ∈ Cnr .
Poznato je da svaka algebarska funkcija ima svojstvo zamene, a da obratno, u op{tem
slu~aju, ne va`i. Za slu~aj Bulovih funkcija Gra¨tzer je dokazao da su funkcije sa
svojstvom zamene isto {to i Bulove funkcije. Slede}a teorema daje generalizaciju te
teoreme na Postove algebre.
TEOREMA 5.8. [15] Neka je P r-Postova algebra. Funkcija f : P n → P ima svojstvo
zamene ako i samo ako je Postova funkcija.
5.3 Postove jedna~ine
Najva`niji rezultati u teoriji Postovih jedna~ina (svo|ewe na jednu jedna~inu,
uslov konzistentnosti, metoda eliminacije nepoznatih, konstrukcija reproduktivnog
pomo}upartikularnogre{ewa) predstavqaju generalizaciju odgovavaraju}ihrezultata
36
iz teorije Bulovih jedna~ina. Do osnovnih tvr|ewa su, nezavisno jedan od drugih, do{li
Carvallo, Serfati i Bordat. Carvallo je prvi objavio svoje rezultate, oni su, uglavnom,
bili bez dokaza i odnosili su se na Postovu algebru Cr, ali se ispostavilo da va`e u
proizvoqnoj Postovoj algebri.
Postove jedna~ine su jedna~ine koje se mogu izraziti pomo}u Postovih funkcija.
Preciznije:
DEFINICIJA 5.3. Postova jedna~ina (nejedna~ina) sa n nepoznatih na Postovoj alge-
bri P je jedna~ina (nejedna~ina) oblika
f(X) = g(X) (f(X) ≤ g(X)), (5.4)
gde su f, g : P n → P Postove funkcije. Ako za A ∈ P n va`i f(A) = g(A) (f(A) ≤
g(A)) onda jeA partikularno re{ewe jedna~ine (nejedna~ine) (5.4). Re{iti Postovu
jedna~inu (nejedna~inu) zna~i odrediti skup svih wenih re{ewa. Ako je taj skup
re{ewa neprazan ka`emo da je jedna~ina (nejedna~ina) konzistentna. Dve jedna~ine
(nejedna~ine) su ekvivalentne ako imaju jednake skupove re{ewa.
TEOREMA 5.9. [19, 43, 16] Svaki sistem Postovih jedna~ina i/ili nejedna~ina ekviva-
lentan je jednojPostovoj jedna~inioblika f = 0, atako|e i jednojPostovoj jedna~ini
oblika g = 1.
Dokaz. Posmatrajmo sistem odm jedna~ina i nejedna~ina
fk(X)Rk gk(X), Rk ∈ {=,≤}, (k = 1, . . . ,m) (5.5)
gde jeX ∈ P n i fk i gk su Postove funkcije (k = 1, . . . ,m). Kako va`i
fk ≤ gk ⇐⇒ fk · gk = fk (iz 1.2)
i fk · gk je Postova funkcija sledi da je svaka Postova nejedna~ina ekvivalentna nekoj
Postovoj jedna~ini, pa sistem (5.5) mo`emo posmatrati kao sistem jedna~ina. Iz
fk = gk ⇐⇒
r−1∨
i=0
(fk)
i((gk)
i)i = 0 (prema Teoremi 5.5)
i ~iwenice da je hk =
∨r−1
i=0 (fk)
i((gk)
i)i Postova funkcija sledi da je dati sistem
ekvivalentan sistemu jedna~ina
hk(X) = 0 (k = 1, . . . ,m).
Na kraju, iz
(∀k ∈ {1, . . . ,m})hk = 0⇐⇒
m∨
k=1
hk = 0
i ~iwenice da je h =
∨m
k=1 hk Postova funkcija, sledi da je sistem (5.5) ekvivalentan
jednoj Postovoj jedna~ini
h(X) = 0.
37
Svo|ewe na oblik g = 1 se izvodi na sli~an na~in. ¤
KaoikodBulovih jedna~inaprirodno jetra`itiparametarskureprezentacijuskupa
re{ewa. Zato se defini{u pojmovi op{teg (parametarskog) re{ewa i reproduktivnog
op{teg re{ewa. Ove definicije su saglasne Definiciji 1.2 i Definiciji 1.3.
DEFINICIJA 5.4. Neka su f, ϕ1, . . . , ϕn : P
n → P Postove funkcije i neka je
Φ = (ϕ1, . . . , ϕn). Formule
xi = ϕi(t1, . . . , tn) (i = 1, . . . , n), (5.6)
ili u vektorskoj formi X = Φ(T ), odre|uju parametarsko op{te re{ewe jedna~ine
f(X) = 0 ako i samo ako
(∀X) (f(X) = 0⇐⇒ (∃T ∈ P n)X = Φ(T )) . (5.7)
DEFINICIJA 5.5. Neka su f, ϕ1, . . . , ϕn : P
n → P Postove funkcije i neka je
Φ = (ϕ1, . . . , ϕn). Formule
xi = ϕi(t1, . . . , tn) (i = 1, . . . , n),
ili u vektorskoj formiX = Φ(T ), odre|uju reproduktivno op{te re{ewe jedna~ine
f(X) = 0 ako i samo ako
(∀X) (f(X) = 0⇐⇒ X = Φ(X)) . (5.8)
Najpre }emo posmatrati jedna~ine sa jednom nepoznatom. Iz Teoreme 5.9 i Teoreme
5.6 sledi
POSLEDICA 5.7. Svaki sistem Postovih jedna~ina i/ili nejedna~ina sa jednom nepo-
znatom je ekvivalentan jedna~ini oblika
r−1∨
i=0
cix
i = 0
gde je x nepoznata i ci ∈ P (i = 0, . . . , r − 1).
Navodimo najva`nije rezultate do kojih su do{li Carvallo, Serfati i Bordat.
TEOREMA 5.10. [19, 43, 16]Postova jedna~ina
r−1∨
i=0
cix
i = 0 (5.9)
je konzistentna ako i samo ako
r−1∏
i=0
ci = 0.
38
Utom slu~aju skup re{ewa je podmre`a od P sa najmawim elementom
η =
r−1∏
i=0
(c∗∗i ∨ ei)
i najve}im elementom
ζ =
r−1∨
i=1
c∗i ei.
Iako je skup re{ewa konzistentne Postove jedna~ine ograni~ena mre`a, za razliku
od Bulovih jedna~ina, to ne mora biti interval, {to pokazuje slede}i primer.
PRIMER 5.2. Za svako k ∈ {1, . . . , n}, jedna~ina x = x(k) ima kao skup re{ewa skup
B(P ) svih Bulovih elemenata algebre P (Teorema 5.3), tako da je η = 0 i ζ = 1, ali
[0, 1] = P 6= B(P ).
Neke Postove jedna~ine imaju za skup re{ewa interval. Wihovu karakterizaciju
daje slede}a teorema.
TEOREMA 5.11. [16, 17]Skup re{ewa konzistentnePostove jedna~ine (5.9) je interval
[η, ζ] ako i samo ako va`i(
i−1∨
h=0
c∗h
)(
r−1∨
j=i+1
c∗j
)
≤ c∗i (i = 1, . . . , r − 2).
Mo`ese definisatiiobratniproblem: ako je dat interval [u, v] uPostovoj algebri
P da li postoji Postova funkcija f takva da skup re{ewa jedna~ine f(x) = 0 bude dati
interval? Odgovor daje slede}a teorema.
TEOREMA 5.12. Neka su u, v elementi Postove algebre P takvi da je u ≤ v. Tada
postoji Postova funkcija f : P → P takva da va`i
f(x) = 0⇐⇒ u ≤ x ≤ v.
Dokaz. Neka su u, v ∈ P takvi da je u ≤ v. Tada je
u ≤ x ≤ v
⇐⇒ u ≤ x& x ≤ v
⇐⇒
r−2∨
i=0
r−1∨
h=i+1
uhxi = 0&
r−2∨
i=0
r−1∨
h=i+1
xhvi = 0 (na osnovu Posledice 5.2)
⇐⇒
r−2∨
i=0
r−1∨
h=i+1
(uhxi ∨ xhvi) = 0.
Neka je
f(x) =
r−2∨
i=0
r−1∨
h=i+1
(uhxi ∨ xhvi).
39
Tada dobijamo f(x) = 0 ⇔ u ≤ x ≤ v. Kako je u ≤ v, postoji element x ∈ P takav da
va`i u ≤ x ≤ v, pa je jedna~ina f(x) = 0 svakako konzistentna. ¤
Napomena 5.2. U specijalnom slu~aju kada je r = 2, va`iP = B(P ), tj. Postova algebra
je Bulova algebra. Tada funkcija f postaje
f(x) = u1x0 ∨ x1v0 = ux′ ∨ xv′.
Ekvivalencijau ≤ x ≤ v ⇐⇒ ∨r−2i=0 ∨r−1h=i+1(uhxi∨xhvi) = 0postaje poznata relacija
u ≤ x ≤ v ⇐⇒ ux′ ∨ xv′ = 0 koja va`i u svakoj Bulovoj algebri.
Neki oblici op{teg i reproduktivnog re{ewa Postove jedna~ine sa jednom nepo-
znatom su dati u radovima Serfati-ja [43, 44], Bordat-a [16, 17] i Bankovi}a [8].
TEOREMA 5.13. [16, 17]Ako je jedna~ina (5.9) konzistentna onda formula
x = η ∨
r−1∨
i=0
c∗i t
iei,
gde je η partikularno re{ewe dato u Teoremi 5.10, defini{e reproduktivno op{te
re{ewe jedna~ine (5.9).
Sada }emo posmatrati Postove jedna~ine sa n nepoznatih.
TEOREMA 5.14. [46, 16, 14]Postova jedna~ina
f(x1, . . . , xn) = 0
je konzistentna ako i samo ako va`i∏
A∈Cnr
f(A) = 0.
Kao i kodBulovih jedna~ina, re{avawePostovih jedna~ina san nepoznatih se mo`e
metodom sukcesivnih eliminacija svestinare{avawen jedna~ina sa jednomnepoznatom.
KodBulovihjedna~inaovajmetodimadvevarijante: prvu,kodkojeseskupre{ewaopisuje
sistemom rekurentnih nejednakosti i drugu, kod koje se re{ewe daje u parametarskom
obliku. Zbog poznate ~iwenice da re{ewe Postove jedna~ine sa jednom nepoznatom ne
mora biti interval kod Postovih jedna~ina se, u op{tem slu~aju, mo`e primeniti samo
druga varijanta.
Eliminante Postove funkcije f : P n → P se defini{u rekurzivno na slede}i
na~in
f1(x1, . . . , xn) = f(x1, . . . , xn),
fk(xk, . . . , xn) =
r−1∏
i=0
fk−1(ei, xk, . . . , xn) (k = 2, . . . , n),
fn+1 =
r−1∏
i=0
fn(ei).
40
O~igledno je da je za svako k ∈ {1, . . . , n} eliminanta fk Postova funkcija. Ako je
fn+1 6= 0 onda jedna~ina fn(xn) = 0 nije konzistentna, sledi da za svako k ∈ {n, n −
1, . . . , 1} jedna~ina fk(xk, . . . , xn) = 0 nije konzistentna, a samim tim i jedna~ina
f(x1, . . . , xn) = 0 nije konzistentna (za k = 1). Ako je fn+1 = 0, imamo da su sve
jedna~inefk(xk, . . . , xn) = 0konzistentne, zak ∈ {n, n−1, . . . , 1}. Trougaonisistem
jedna~ina
fk(xk, . . . , xn) = 0 (k = 1, . . . , n),
se re{ava u obrnutom redosledu, polaze}i od posledwe jedna~ine fn(xn) = 0. Po
Teoremi 5.13 ova jedna~ina ima parametarsko re{ewe oblika xn = ϕn(tn), gde je ϕn
Postova funkcija. Zamenom dobijenog xn u preostalim jedna~inama elimini{e se jedna
nepoznata, tj. sistem se svodi na trougaoni sistemodn−1 jedna~ine san−1nepoznatom.
Ponavqawem postupka jo{ n− 1 puta dobijamo re{ewe u obliku
xk = ϕk(tk, tk+1, . . . , tn), (k = 1, . . . , n). (5.10)
Carvaillo, Bordat i Serfati su dokazali da parametarsko re{ewe (5.10) sistema Post-
ovih jedna~ina fk(xk, . . . , xn) = 0 (k = 1, . . . , n) predstavqa i op{te re{ewe jedna~ine
f(x1, . . . , xn) = 0.
TEOREMA 5.15. [16, 19, 20, 43, 44] Jedna~ina f(x1, . . . , xn) = 0 je konzistentna ako i
samoako jefn+1 = 0. Utomslu~ajuformule (5.10)odre|ujuop{tere{eweove jedna~ine.
Slede}a teorema predstavqa generalizaciju poznate Lo¨wenheim-ove teoreme iz
teorije Bulovih jedna~ina. Ona daje formulu za dobijawe reproduktivnog re{ewa ako
je poznato jedno partikularno re{ewe Postove jedna~ine.
TEOREMA 5.16. [19, 16, 45] Neka je Ξ = (ξ1, . . . , ξn) ∈ P n partikularno re{ewe
jedna~ine f(x1, . . . , xn) = 0. Tada formule
xk = ξkf
∗∗(t1, . . . , tn) ∨ tkf ∗(t1, . . . , tn) (k = 1, . . . , n),
ili, u vektorskom obliku
X = Ξf ∗∗(T ) ∨ f ∗(T )T,
defini{u reproduktivno re{ewe ove jedna~ine.
TEOREMA 5.17. [46]Nekasuf, g : P n → P Postovefunkcije. Ako je jedna~inaf(X) = 0
konzistentna, onda va`i
(∀X ∈ P n)(f(X) = 0⇐⇒ g(X) = 0)⇐⇒ g∗ = f ∗.
Slede}a teorema predstavqa uop{tewe Teoreme 5.16. Ona daje formulu za odre|i-
vawe svih reproduktivnih re{ewa Postove jedna~ine pod uslovom da je poznato jedno
op{te re{ewe.
TEOREMA 5.18. [10] Neka su f, gk, hk : P
n → P (k = 1, . . . , n) Postove funkcije i
G = (g1, . . . , gn), H = (h1, . . . , hn). Pretpostavimo da jeG op{te re{ewe jedna~ine
f(X) = 0. Tada jeH reproduktivnoop{tere{eweove jedna~ineakoisamoakopostoji
n−torka P = (p1, . . . , pk) Postovih funkcija pk : P n → P (k = 1, . . . , n) tako da
va`i
H(X) = f ∗(X)X ∨ f ∗∗(X)G(P (X)) (za svakoX ∈ P n).
41
U radu [41] Rudeanu se bavi obratnim problemom od problema re{avawa Bulove
jedna~ine, problemom nala`ewa Bulove funkcije sa n promenqivih ~ije su nule po-
znate i zadate parametarski. Tako|e, bavi se i problemom odre|ivawa uslova koje
treba da ispuwava niz rekurentno zadatih intervala da bi predstavqao op{te re{ewe
neke Bulove jedna~ine. Na kraju, on postavqa problem pro{irewa istra`ivawa na
Postove algebre. Do kraja ovog odeqka prikazujemo dobijene rezultate u re{avawu ovog
problema.
DEFINICIJA 5.6. Neka je k ∈ {1, . . . , n} i (bk, . . . , bn) ∈ P n−k+1. Postova funkcija
f : P n → P je nulabilna u odnosu na (bk, . . . , bn) ∈ P n−k+1 ako i samo ako jedna~ina
f(x1, . . . , xk−1, bk, . . . , bn) = 0 ima re{ewe (x1, . . . , xk−1) ∈ Bk−1. Funkcija f je nula-
bilna ako i samo ako je jedna~ina f(x1, . . . , xn) = 0 konzistentna.
TEOREMA 5.19. Neka je f : P n → P Postova funkcija, k ∈ {1, . . . , n} i
(xk, . . . , xn) ∈ P n−k+1. Tada su slede}i uslovi ekvivalentni:
(i) f je nulabilna u odnosu na (xk, . . . , xn);
(ii) fk(xk, . . . , xn) = 0.
Dokaz.
fk(xk, . . . , xn) = 0 ⇐⇒
r−1∏
i=0
fk−1(ei, xk, . . . , xn) = 0
⇐⇒ (∃xk−1)fk−1(xk−1, xk, . . . , xn) = 0
⇐⇒ . . .⇐⇒ (∃xk−1) . . . (∃x1)f1(x1, . . . , xk−1, xk, . . . , xn) = 0
⇐⇒ f je nulabilna u odnosu na (xk, . . . , xn).
¤
Za neke Postove jedna~ine (one koje imaju re{ewe u obliku intervala) mo`emo
definisati pojam op{teg intervalnog re{ewa. Zapravo, ovaj pojam se mo`e defin-
isati u vezi sa bilo kojom Postovom jedna~inom, ali ima zna~aja samo za jedna~ine sa
intervalnim re{ewem.
DEFINICIJA 5.7. Neka je f : P n → P nulabilna Postova funkcija i neka su
uk, vk : P
n−k → P (k = 1, . . . , n− 1), un, vn ∈ P, (5.11)
Postove funkcije. Sistem nejednakosti
uj(xj+1, . . . , xn) ≤ xj ≤ vj(xj+1, . . . , xn) (j = 1, . . . , n− 1),
un ≤ xn ≤ vn
(5.12)
odre|uje op{te intervalno re{ewe jedna~ine f(x1, . . . , xn) = 0 ako i samo ako za svako
k ∈ {1, . . . , n} i svako (xk, . . . , xn) ∈ P n−k+1 slede}i uslovi su ekvivalentni:
42
(i) f je nulabilna u odnosu na (xk, . . . , xn);
(ii) formule (5.12) va`e za svako j = k, . . . , n.
DEFINICIJA 5.8. Neka je f : P n → P Postova funkcija i f1, . . . , fn+1 wene elimi-
nante. Niz g1, . . . , gn+1 Postovih funkcija
gk : P
n−k+1 → P (k = 1, . . . , n), gn+1 ∈ P
je rekurentno pokrivawe funkcije f ako i samo ako va`i
n+1∨
i=k
gi = fk (k = 1, . . . , n+ 1).
TEOREMA 5.20. Neka su f : P n → P i uj, vj : P n−j → P (j = 1, . . . , n) Postove
funkcije. Ako niz funkcija g1, . . . , gn definisanih sa
gj(xj, . . . , xn) =
r−2∨
i=0
r−1∨
h=i+1
(uhj (xj+1, . . . , xn)x
i
j ∨ xhj vij(xj+1, . . . , xn)), (5.13)
(j = 1, . . . , n− 1),
gn(xn) =
r−2∨
i=0
r−1∨
h=i+1
(uhnx
i
n ∨ xhnvin), (5.14)
gn+1 = 0, (5.15)
predstavqarekurentnopokrivaweodf , ondasistem (5.12)odre|ujeop{teintervalno
re{ewe jedna~ine f(x1, . . . , xn) = 0.
Dokaz. Neka je niz (g1, . . . , gn+1) definisan sa (5.13), (5.14) i (5.15) rekurentno
pokrivawe funkcije f . Tada va`i fn+1 = gn+1 = 0, pa je f nulabilna, po Teoremi 5.15.
Neka jek ∈ {1, . . . , n}i (xk, . . . , xn) ∈ P n−k+1. Tada je ta~an slede}iniz ekvivalencija
f je nulabilna u odnosu na (xk, . . . , xn)
⇐⇒ fk(xk, . . . , xn) = 0
⇐⇒
n∨
j=k
gj(xj, . . . , xn) = 0
⇐⇒ gj(xj, . . . , xn) = 0 (j = k, . . . , n)
⇐⇒
r−2∨
i=0
r−1∨
h=i+1
(uhj (xj+1, . . . , xn)x
i
j ∨ xhj vij(xj+1, . . . , xn)) = 0 (j = k, . . . , n− 1)
&
r−2∨
i=0
r−1∨
h=i+1
(uhnx
i
n ∨ xhnvin) = 0
⇐⇒ uj(xj+1, . . . , xn) ≤ xj ≤ vj(xj+1, . . . , xn) (j = k, . . . , n− 1) & un ≤ xn ≤ vn.
(na osnovu dokaza Teoreme 5.12).
43
Saglasno Definiciji 5.7 sistem (5.12) odre|uje op{te intervalno re{ewe jedna~ine
f(x1, . . . , xn) = 0. ¤
TEOREMA 5.21. Neka su uj, vj : P
n−j → P (j = 1, . . . , n) Postove funkcije. Postoji
nulabilna Postova funkcija f takva da niz Postovih nejednakosti (5.12) odre|uje
op{te intervalno re{ewe jedna~ine f(X) = 0 ako i samo ako su ispuweni slede}i
uslovi
r−2∨
i=0
r−1∨
h=i+1
uhkv
i
k ≤
n∨
j=k+1
(
r−2∨
i=0
r−1∨
h=i+1
(uhjx
i
j ∨ xhj vij)
)
(k = 1, . . . , n− 1), (5.16)
r−2∨
i=0
r−1∨
h=i+1
uhnv
i
n = 0. (5.17)
Dokaz. Neka za date Postove funkcije uj, vj (j = 1, . . . , n) va`e uslovi (5.16) i
(5.17). Tada va`i slede}i niz ekvivalencija:
uj(xj+1, . . . , xn) ≤ xj ≤ vj(xj+1, . . . , xn) (j = 1, . . . , n− 1), un ≤ xn ≤ vn
⇐⇒ uj(xj+1, . . . , xn) ≤ xj & xj ≤ vj(xj+1, . . . , xn) (j = 1, . . . , n− 1)
& un ≤ xn & xn ≤ vn
⇐⇒
r−2∨
i=0
r−1∨
h=i+1
uhjx
i
j = 0&
r−2∨
i=0
r−1∨
h=i+1
xhj v
i
j = 0 (j = 1, . . . , n)
(na osnovu Posledice 5.2)
⇐⇒
r−2∨
i=0
r−1∨
h=i+1
(uhjx
i
j ∨ xhj vij) = 0 (j = 1, . . . , n)
⇐⇒
n∨
j=1
r−2∨
i=0
r−1∨
h=i+1
(uhjx
i
j ∨ xhj vij) = 0.
Defini{imo funkcije f : P n → P i gk : P n−k+1 → P (k = 1, . . . , n), gn+1 ∈ P,
na slede}i na~in
f(x1, . . . , xn) =
n∨
j=1
r−2∨
i=0
r−1∨
h=i+1
(uhjx
i
j ∨ xhj vij), (5.18)
gj(xj, . . . , xn) =
r−2∨
i=0
r−1∨
h=i+1
(uhj (xj+1, . . . , xn)x
i
j ∨ xhj vij(xj+1, . . . , xn)) (5.19)
(j = 1, . . . , n− 1),
gn(xn) =
r−2∨
i=0
r−1∨
h=i+1
(uhnx
i
n ∨ xhnvin), (5.20)
gn+1 = 0. (5.21)
44
Iz (5.18)-(5.21) dobijamo
f =
n+1∨
k=1
gk. (5.22)
Uslov (5.16) sada mo`emo zapisati u slede}em obliku
r−2∨
i=0
r−1∨
h=i+1
uhkv
i
k ≤
n∨
j=k+1
gj (k = 1, . . . , n− 1). (5.23)
Dokaza}emodaniz(5.12)odre|ujeop{teintervalnore{ewejedna~inef(x1, . . . , xn) =0.
Najpre poka`imo da za svako k ∈ {1, . . . , n} va`i slede}i niz jednakosti:
r−1∏
s=0
gk(es, xk+1, . . . , xn) =
r−2∨
s=0
r−1∨
h=s+1
uhkv
s
k. (5.24)
Uvedimo oznaku ωs =
∨r−1
h=s+1 u
h
k ∨
∨s−1
h=0 v
h
k (s = 1, . . . , r − 2). Tada iz (5.19) i (5.20)
dobijamo
r−1∏
s=0
gk(es, xk+1, . . . , xn) =
=
(
r−2∨
i=0
r−1∨
h=i+1
(uhke
i
0 ∨ eh0vik)
)
r−2∏
s=1
(
r−2∨
i=0
r−1∨
h=i+1
(uhke
i
s ∨ ehsvik)
)
·
·
(
r−2∨
i=0
r−1∨
h=i+1
(uhke
i
r−1 ∨ ehr−1vik)
)
=
=
(
r−1∨
h=1
uhk
)
r−2∏
s=1
ωs
(
r−2∨
i=0
vik
)
.
(5.25)
Sada doka`imo da va`i (
r−1∨
h=1
uhk
)
ω1 =
r−1∨
h=2
uhk ∨ u1kv0k, (5.26)(
r−1∨
h=s
uhk ∨
s−2∨
t=0
s−1∨
h=t+1
uhkv
t
k
)
ωs =
r−1∨
h=s+1
uhk ∨
s−1∨
t=0
s∨
h=t+1
uhkv
t
k, (5.27)
(s = 2, . . . , r − 2).
Primenom distributivnosti, apsorpcije i ortogonalnosti disjunktivnih komponenti
45
dobijamo (
r−1∨
h=1
uhk
)
ω1 =
(
u1k ∨
r−1∨
h=2
uhk
)(
r−1∨
h=2
uhk ∨ v0k
)
=
r−1∨
h=2
uhk ∨
r−1∨
h=2
uhkv
0
k ∨ u1kv0k
=
r−1∨
h=2
uhk ∨ u1kv0k.
Sli~no,(
r−1∨
h=s
uhk ∨
s−2∨
t=0
s−1∨
h=t+1
uhkv
t
k
)
ωs =
(
r−1∨
h=s
uhk ∨
s−2∨
t=0
s−1∨
h=t+1
uhkv
t
k
)(
r−1∨
l=s+1
ulk ∨
s−1∨
t=0
vtk
)
=
r−1∨
h=s+1
uhk ∨
r−1∨
h=s
s−1∨
t=0
uhkv
t
k ∨
s−2∨
t=0
s−1∨
h=t+1
r−1∨
l=s+1
ulku
h
kv
t
k ∨
s−2∨
t=0
s−1∨
h=t+1
s−1∨
l=0
vlku
h
kv
t
k
=
r−1∨
h=s+1
uhk ∨
r−1∨
h=s+1
s−1∨
t=0
uhkv
t
k ∨
s−1∨
t=0
uskv
t
k ∨
s−2∨
t=0
s−1∨
h=t+1
uhkv
t
k
=
r−1∨
h=s+1
uhk ∨
s−1∨
t=0
uskv
t
k ∨
s−2∨
t=0
s−1∨
h=t+1
uhkv
t
k
=
r−1∨
h=s+1
uhk ∨
s−2∨
t=0
uskv
t
k ∨
s−2∨
t=0
s−1∨
h=t+1
uhkv
t
k ∨ uskvs−1k
=
r−1∨
h=s+1
uhk ∨
s−2∨
t=0
s∨
h=t+1
uhkv
t
k ∨ uskvs−1k
=
r−1∨
h=s+1
uhk ∨
s−1∨
t=0
s∨
h=t+1
uhkv
t
k.
46
Daqe, primenom (5.26) i (5.27) u (5.25) dobijamo
r−1∏
s=0
gk(es, xk+1, . . . , xn) =
(
r−1∨
h=1
uhk
)
r−2∏
s=1
ωs
(
r−2∨
i=0
vik
)
=
(
r−1∨
h=1
uhk)
)
ω1
r−2∏
s=2
ωs
(
r−2∨
i=0
vik
)
=
(
r−1∨
h=2
uhk ∨ u1kv0k
)
ω2
r−2∏
s=3
ωs
(
r−2∨
i=0
vik
)
=
(
r−1∨
h=3
uhk ∨
1∨
t=0
2∨
h=t+1
uhkv
t
k
)
ω3
r−2∏
s=4
ωs
(
r−2∨
i=0
vik
)
= · · · =
(
ur−1k ∨
r−3∨
t=0
r−2∨
h=t+1
uhkv
t
k
)(
r−2∨
i=0
vik
)
=
r−2∨
t=0
r−1∨
h=t+1
uhkv
t
k.
Sada}emoindukcijompok dokazati danizfunkcija g1, . . . , gn+1 predstavqarekurentno
pokrivawa funkcije f , tj. da va`i fk =
∨n+1
j=k gj za svako k = 1, . . . , n + 1, gde su fk
eliminante funkcije f . O~igledno, jednakost je ta~na za k = 1. Pretpostavimo da je
ta~na za neko k ∈ {1, . . . , n− 1}. Tada
fk+1(xk+1, . . . , xn) =
r−1∏
s=0
fk(es, xk+1, . . . , xn)
=
r−1∏
s=0
n∨
j=k
gj(es, xk+1, . . . , xn) (po indukcijskoj hipotezi)
=
r−1∏
s=0
(
gk(es, xk+1, . . . , xn) ∨
n∨
j=k+1
gj
)
=
(
r−1∏
s=0
gk(es, xk+1, . . . , xn)
)
∨
n∨
j=k+1
gj
=
r−2∨
s=0
r−1∨
h=i+1
uhkv
s
k ∨
n∨
j=k+1
gj (iz (5.24))
=
n∨
j=k+1
gj (iz (5.23)).
Najzad, za k = n+ 1 imamo
47
fn+1 =
r−1∏
s=0
fn(es)
=
r−1∏
s=0
gn(es)
=
r−2∨
s=0
r−1∨
h=i+1
uhnv
s
n
= 0 (iz (5.17)).
Timejedokazanodanizg1, . . . , gn+1predstavqarekurentnopokrivawePostovefunkcije
f , pa poTeoremi5.20 sledi da sistem (5.12) odre|uje op{teintervalnore{ewe jedna~ine
f(x1, . . . , xn) = 0.
Pretpostavimo sada da postoji Postova funkcija f : P n → P takva da sistem (5.12)
odre|uje op{te intervalno re{ewe jedna~ine f(x1, . . . , xn) = 0. Neka su f1, . . . , fn+1
wene eliminante, a funkcije gk (k = 1, . . . , n+ 1) neka su date formulama (5.16), (5.17)
i (5.18). Doka`imo da va`e (5.13) i (5.14). Najpre }emo dokazati da je
f ∗∗k =
n+1∨
j=k
gj (k = 1, . . . , n+ 1).
Funkcije g1, . . . , gn+1 su Postove, jer su takve funkcije uk, vk (k = 1, . . . , n). Iz
konzistentnosti jedna~inef(x1, . . . , xn) = 0sledida jefn+1 = 0idaqef
∗∗
n+1 = 0
∗∗ = 0.
Iz (5.21) dobijamo da je gn+1 = f
∗∗
n+1. Neka je k ∈ {1, . . . , n}. Tada va`i
fk(xk, . . . , xn) = 0
⇐⇒ f je nulabilna u odnosu na (xk, . . . , xn) (prema Teoremi 5.19)
⇐⇒ uj(xj+1, . . . , xn) ≤ xj ≤ vj(xj+1, . . . , xn) (j = k, . . . , n− 1), un ≤ xn ≤ vn
(jer (5.12) odre|uje op{te intervalno re{ewe jedna~ine f(X) = 0)
⇐⇒
r−2∨
i=0
r−1∨
h=i+1
(uhjx
i
j ∨ xhj vij) = 0 (j = k, . . . , n) (prema Teoremi 5.12)
⇐⇒ gj(xj, . . . , xn) = 0 (j = k, . . . , n)
⇐⇒
n∨
j=k
gj(xj, . . . , xn) = 0
⇐⇒
n+1∨
j=k
gj(xk, . . . , xn) = 0 (uvo|ewem fiktivnih varijabli).
48
Iz fn+1 = 0 sledi da je fk nulabilna. Na osnovu Teoreme 5.17 imamo da je
f ∗k =
(
n+1∨
j=k
gj
)∗
.
Po{to je svaka Postova algebra i Stonova algebra, a elementi gj(xj, . . . , xn)
(j = 1, . . . , n+ 1) su Bulovi (iz (5.19)-(5.21)), dobijamo da je
f ∗∗k =
(
n+1∨
j=k
gj
)∗∗
=
n+1∨
j=k
g∗∗j =
n+1∨
j=k
gj.
Iz konzistentnosti jedna~ine fn(xn) = 0 sledi konzistentnost jedna~ine f
∗∗
n (xn) = 0.
Jednakost gn = f
∗∗
n implicira konzistentnost jedna~ine gn(xn) = 0. Dakle, postoji
y ∈ P takvo da je gn(y) = 0. Po{to je gn(xn) =
∨r−2
i=0
∨r−1
h=i+1(u
h
nx
i
n ∨ xhnvin), dobijamo
da je
r−2∨
i=0
r−1∨
h=i+1
(uhny
i ∨ yhvin) = 0 ⇔
r−2∨
i=0
r−1∨
h=i+1
uhny
i = 0&
r−2∨
i=0
r−1∨
h=i+1
yhvin = 0
⇔ un ≤ y & y ≤ vn
⇔ un ≤ vn
⇔
r−2∨
i=0
r−1∨
h=i+1
uhnv
i
n = 0.
Dakle, va`i uslov (5.17).
Ako jem ∈ {1, . . . , n− 1} onda
(fm+1(xm+1, . . . , xn))
∗∗ =
(
r−1∏
s=0
fm(es, xm+1, . . . , xn)
)∗∗
=
r−1∏
s=0
(fm(es, xm+1, . . . , xn))
∗∗
=
r−1∏
s=0
n∨
j=m
gj(es, xm+1, . . . , xn)
≥
r−1∏
s=0
gm(es, xm+1, . . . , xn)
=
r−2∨
s=0
r−1∨
h=s+1
uhm(xm+1, . . . , xn)v
s
m(xm+1, . . . , xn)
pa dobijamo
r−2∨
s=0
r−1∨
h=s+1
uhmv
s
m ≤ (fm+1(xm+1, . . . , xn))∗∗.
49
Kako je
f ∗∗m+1 =
n∨
j=m+1
gj =
n∨
j=m+1
(
r−2∨
i=0
r−1∨
h=i+1
(uhjx
i
j ∨ xhj vij)
)
sledi da va`i (5.16). ¤
Napomena 5.3. Kao specijalan slu~aj, za r = 2, dobijamo odgovaraju}u Rudeanovu teoremu
za Bulove algebre ( [41]).
U pomenutom radu [41] Rudeanu pokazuje da za svaku Bulovu transformaciju postoji
Bulova jedna~ina ~ije je op{te parametarsko re{ewe dato tom transformacijom:
TEOREMA 5.22. [41] Za svaku Bulovu transformaciju Φ, formula X = Φ(T ) odre|uje
parametarsko op{te re{ewe jedna~ine
∏
A∈{0,1}n
n∨
i=1
(xi + ϕi(A)) = 0.
Uop{ti}emo prethodnu teoremu na Postove algebre.
TEOREMA 5.23. ZasvakutransformacijuΦ = (ϕ1, . . . , ϕn), gdesuϕi : P
n → P Postove
funkcije, formulaX = Φ(T ) odre|uje parametarsko op{te re{ewe jedna~ine
∏
A∈Cnr
n∨
i=1
(xi + ϕi(A)) = 0.
Dokaz. Neka je f(X) =
∏
A∈Cnr
∨n
i=1(xi+ϕi(A)). Tada je f Postovafunkcija i va`i
f(X) = 0 ⇐⇒
∏
A∈Cnr
n∨
i=1
(xi + ϕi(A)) = 0
⇐⇒ (∃T )
n∨
i=1
(xi + ϕi(T )) = 0
⇐⇒ (∃T )(∀i ∈ {1, . . . , n})xi + ϕi(T ) = 0
⇐⇒ (∃T )(∀i ∈ {1, . . . , n})xi = ϕi(T )
⇐⇒ (∃T )X = Φ(T ).
Konzistentnost jedna~ine f(X) = 0 sledi iz
(∃X)f(X) = 0⇐⇒ (∃X)(∃T )X = Φ(T ),
jer va`i (∃X)(∃T )X = Φ(T ).
¤
50
Literatura
[1] Bankovic´ D., On general and reproductive solutions of arbitrary equations,
Publ. Inst. Math. (Beograd) 26(40)(1979), 31–33.
[2] Bankovic´ D., All general solutions of finite equations, Publ. Inst. Math.
(Beograd) 47(61)(1990), 5–12.
[3] Bankovic´ D., A new proof of of Presˇic´‘s theorem on finite equations, Publ.
Inst. Math. (Beograd) 51(65)(1992), 22–24.
[4] Bankovic´ D., A generalization of Lo¨wenheim’s theorem, Bull. Soc. Math.
Belgique Ser. B 44(1992), 59–65.
[5] Bankovic´ D., Formulas of general reproductive solutions of Boolean equations,
Fuzzy Sets and Systems 75(1995), 203–207.
[6] Bankovic´ D., All general solutions of Presˇic´‘s equations, Discrete Mathemat-
ics 137(1995), 1–6.
[7] Bankovic´ D., Formulas of general solutions of Boolean equations, Discrete
Mathematics 152(1996), 25–32.
[8] Bankovic´ D., All solutions of finite equations, Discrete Mathematics
169(1997), 163–168.
[9] Bankovic´ D., Equations on multiple-valued logic, Multi. Val. Logic
3(1998),89–95.
[10] Bankovic´ D., All reproductive general solutions of Postian equations, Rev.
Roumaine Math. Pures Appl. 45(2000), 925–930.
[11] Bankovic´ D., A note on Postian equations, Mult.-Val. Logic 6(2001), 1–10.
[12] Bankovic´ D., General reproductive solutions of Postian equation, Facta uni-
versitatis, Ser. Math. Inform. 17(2002), 1–4.
[13] Bankovic´ D., Distance in Post algebras, Discrete Mathematics 263(2003),
269–274.
51
[14] Beazer R., Functions and equations in classes of distributive lattices with
pseudocomplementation, Proc. Edinburgh Math. Soc. II Ser.19(1974), 191–
203.
[15] Beazer R., Some remarks on Post algebras, Coll. Math. 29(1974), 167–178.
[16] Bordat J.P., Treillis de Post. Application aux fonctions et aux e´quations de
la logique a` p valeurs, The`se, Univ. Sci. Tech. Languedoc, Montpellier, 1975.
[17] Bordat J.P., Re´solution des e´quations de la logique a` p valeurs, Rev.
Roumaine Math. Pures Appl. 23(1978), 507–531.
[18] Brown F.M, Rudeanu S., Recurrent covers and Boolean equations, Coll.
Math. Soc. Ja´nos Bolyai 33 (Lattice Theory), Szeged(Hungary), 1980, 55–
86.
[19] Carvallo M., Sur la re´solution des e´quations de Post, C. R. Acad. Sci., Paris,
265(1967), 601–602.
[20] Carvallo M., Sur la re´solution des e´quations de Post a` ν valeurs, C. R. Acad.
Sci., Paris, 267(1968), 628–630.
[21] Goodstein L., The solutions of equations in a lettice, Proc. Roy. Soc. Edin-
burgh, Sect. A 67(1967),231-242.
[22] Epstein G., The lattice theory of Post algebras, Trans. Amer. Math. Soc.
95(1960), 300–317.
[23] Gra¨tzer G., On Boolean functions (Notes on lattice theory II), Rev.
Roumaine Math. Pures Appl. 7(1962), 693–697.
[24] Gra¨tzer G., Universal algebra, Springer–Verlag, New York, 1968.
[25] Jablonskij S.V., Introduction to discrete mathematics, Nauka, Moskow, 1979.
[26] Lo¨wenheim L., U¨ber das Auflo¨sungsproblem im logische Klassenkalkul,
Sitzungsber. Berl. Math. Geselschaft. 7(1908), 89–94.
[27] Marinkovic´ S., Bankovic´ D., General solutions of equations in multiple-valued
logic, J. Mult.-Valued Logic Soft Comput., Vol. 16, 3-5(2010),421–426.
[28] Marinkovic´ S., Reproductive general solutions of equations on Stone algebra,
J. Mult.-Valued Logic Soft Comput., Vol. 16, 1-2(2010),1–6.
[29] Mu¨ller E., Abriss der algebra der logik I,II (Appendix to Schro¨der) (1909-
1910).
[30] Post E.L., Introduction to a general theory of elementary propositions, Amer.
J. Math. 43(1921), 163–185.
52
[31] Presˇic´ S., Une me´thode de re´solution des e´quations dont toutes les solu-
tions appartiennent a` un ensemble fini donne´, C.R. Acad. Sci. Paris Ser. A
272(1971) 654–657.
[32] Presˇic´ S., Ein Satz u¨ber reproducktive Lo¨sungen, Publ. Inst. Math. Beograd
14(28)(1972), 133–136.
[33] Presˇic´ S., All reproductive solutions of finite equations, Publ. Inst. Math.
Beograd 44 (58)(1988), 3–7.
[34] Reischer C., Simovici D.A., Stojmenovic I., Tosˇic´, A characterization of
Boolean collections of set-valued functions, Inform. Sci. 99(1997), 195–204.
[35] Rosenbloom P.C., Post algebras. Postulates and the general theory. Amer. J.
Math. 64(1924), 167–188.
[36] Rudeanu S., On functions and equations in distributive lattices, Proc. Edin-
burgh Math. Soc. 16(1968), 49–54.
[37] Rudeanu S., Boolean functions and equations, North Holland, Amsterdam,
1974.
[38] Rudeanu S., On the range of a Boolean transformation, Publ. Inst. Math.
(Belgrade) 19 (33)(1975), 139–145.
[39] Rudeanu S., On equations in bounded lattices, An. St. Univ. Ovidius Con-
stanta 9(1)(2001), 101–106.
[40] Rudeanu S., Lattice functions and equations, Springer, Berlin, 2001.
[41] Rudeanu S., Boolean sets and most general solutions of Boolean equations,
Inform. Sci. 180(2010), 2440–2447.
[42] Ruso G., Post algebras and pseudo–Post algebras Fundamenta Mathematicae
67(1970), 133–145
[43] Serfati M., Introduction aux alge`bres de Post et a` leurs applications, Inst.
Statistique Univ. Paris, Cahiers du Bureau Univ. de Rech. Ope´rationnelle,
Cahier no.21, Paris, 1973.
[44] Serfati M., Sur les polynomes postiens, Comptes Rendus de l’Acade´mie des
Sciences, Se´rie A 276(1973), 677–679.
[45] Serfati M., Une me´thode de re´solution des e´quations postiennes a` partir d‘une
solution particulie`re, Discrete Math. 17(1977), 187-189.
[46] Serfati M., On Postian algebraic equations, Discrete Math. 152(1996), 269-
285.
53
Dodatak
Summary
This doctoral dissertation belongs to the scientific discipline Algebra and logic.
General solutions of an equation are present in various fields of mathematics.
Especially, the general solutions were extensively studied in Boolean algebras. In this
doctoral dissertation some known results about Boolean equations are generalized
to equations on Stone algebras, equations on multiple-valued logic and to equations
on Post algebras.
The dissertation consists of five chapters divided in sections, Appendix and Ref-
erences.
In Introduction some basic notations which will be used in next chapters are
given.
Because of many theorems from this field represent generalizations of the cor-
responding results for Boolean equations, main results on Boolean functions and
equations are exposed in Chapter 2.
In Chapter 3, assuming that a general solution is known, the class of reproductive
general solutions of the equation f(x1, . . . , xn) = 0, where L is a Stone algebra and
f : Ln → L is the function with substitution property, is described.
All general solutions of equations in one variable on multiple-valued logic are
described in Chapter 4.
S. Rudeanu in [41] determined the most general form of the subsumptive general
solution of a Boolean equation. He also proved that every Boolean transformation
was the parametric general solution of a consistent Boolean equation. He stated
an open problem: extend this research to Post algebras. Chapter 5 contains some
results related this problem. A necessary and sufficient conditions for the existence
of a Post function f : P n → P (P is a Post algebra) such that the given set of
reccurent inequalities be the solution of equation f(x) = 0, are given. We also proved
that every Post transformation was the parametric solution of some consistent Post
equation.
54
Biografija
SilvanaMarinkovi} je ro|ena 6. aprila 1960. godine uRa~i, gde je zavr{ilaosnovnu
{kolu i gimnaziju.
Prirodno-matemati~kifakultet uKragujevcu, studijska grupa matematika, upisala
je 1978. godine, a diplomirala 1982. godine sa prose~nom ocenom 8.60.
Poslediplomske magistarske studije zavr{ila je naMatemati~komfakultetu Uni-
verziteta u Beogradu 27.8.1997. godine, odbranom magistarske teze pod naslovom Alge-
brizacija jedne verovatnosne logike sa beskona~nim predikatima.
Od 1982. do 1988. godine radila je u sredwim {kolama Me{ovita gimnazija u Ra~i i
Go{auSmederevskojPalanci, a zatim u radnoj organizaciji RomanijaizKragujevca.
Od septembra 1990. godine radi u Institutu za matematiku i informatiku Prirodno-
matemati~kog fakulteta u Kragujevcu, najpre u zvawu asistenta pripravnika, a od 1998.
godine u zvawu asistenta za u`u nau~nu oblast Algebra i logika.
U periodu 2001.-2007. godine radila je u Vi{oj tehni~koj{koli uKragujevcu u zvawu
predava~a.
U dosada{wem radu u Institutu za matematiku i informatiku Prirodno-matemati-
~kog fakulteta dr`ala je ve`be iz predmeta: Algebra, Matemati~ka logika i skupovi,
Linearna algebra i polinomi, Algebarske strukture, Teorijske osnove informatike 2,
Matematika 1 iMatematika 2 (za studenteFizike) iMatematika 1 (za studenteHemije).
U Vi{oj tehni~koj {koli u Kragujevcu dr`ala je predavawa iz predmeta Matematika,
Matematika 1 iMatematika 2.
Silvana Marinkovi} se bavi nau~no istra`iva~kim radom u oblasti logike i alge-
bre. Rezultate istra`ivawa objavila je u slede}im nau~nim radovima:
1. Marinkovic´ S., Rasˇkovic´ M. and -Dord¯evic´ R., Weak probability logic with
infinitary predicates, Publ. Inst. Math., Nouv. Ser. 65(79) (1999), 8-17.
2. Marinkovic´ S., Rasˇkovic´ M. and -Dord¯evic´ R., Weak probability polyadic
algebras, Facta Universitatis Ser. Math. Inform. 16(2001), 1-12.
3. Marinkovic´ S., Bankovic´ D., General solutions of equations in multiple-valued
logic, J. Mult.-Valued Logic Soft Comput., Vol. 16, 3-5(2010),421–426.
4. Marinkovic´ S., Reproductive general solutions of equations on Stone algebra,
J. Mult.-Valued Logic Soft Comput., Vol. 16, 1-2(2010),1–6.
55