|
|
Funkcije Lukašijevića i Šefera ↧↥
f1(x,y)=x ↓y funkcija Veba,Lukašijevića ; f2(x,y)=x↑y funkcija Šefera
x y | x ↓y | x↑y
0 0 | 1 | 1
0 1 | 0 | 1
1 0 | 0 | 1
1 1 | 0 | 0
Koristeći KDNF i KKNF i zakone De Morgana ove se funkcije mogu predstaviti Bulovim izrazima:
Poseban interes za ove funkcije postoji zato što svak od ovih funkcija posebno predstavlja potpun sistem za izražavanje Bulovih funkcija n promenljivih. Teorema 1 : Svaka Bulova funkcija n promenljivih može se predstaviti pomoću Šeferove, odnosno pomoću Lukašijevićeve funkcije:
=xVy 
Definicija 1. Bulova funkcija f(x1,...,xn)={1, ako x1=...=xn=0 ; 0, u ostalim slučajevima; zove se funcija Lukašijevića(NILI-funkcija). Umesto f(x1,...,xn) pišemo 
Definicija 2. Bulova funkcija f(x1,...,xn)={ 0,ako x1=x2=...=xn=1 ; 1,u ostalim slučajevima; zove se funkcija Šefera(NI-funkcija). Umesto f(x1,...,xn) pišemo 
Definicija 3. (proširena definicija dualnosti) Ako se u nekoj teoremi T pojavljuju simboli V, <_ (manje i jednako)_> (vece i jednako) , ↑,↓ ,0,1, onda se dualna teorema (T*) dobija medjusobnom zamenom simbola V i <_ (manje i jednako) i _> (vece i jednako), ↑i↓ , 0 i 1 .
Teorema 2. Za ma koju Bulovu funkciju važe jednakosti:
(i) 
(ii)
Teorema 3. Za ma koju Bulovu funkciju važe jednakosti:
(i) 
(ii) 
(iii)
(iv)
Teorema 4.(Važi za izraze koji se grade isključivo na binarnom operatoru 
)
Svaka Bulova funkcija n promenljivih može se predstaviti P-izrazom u binarnim operatorima Šefera. Podrezano drvo je binarno drvo, čiji je svaki neterminalni čvor povezan bar jednom od dve izlazne grane sa terminalnim čvorom,koji odgovara promenljivoj, ili neposredno ili posredstvom jednog čvora. P-drvo je završeno ako svakom terminalnom čvoru odgovara promenljiva date funkcije. Izraz Bulove funkcije koji odgovara završenom P-drvetu zove se P-izraz.