|
|
Bulove funkcije-kanonske forme
Funkcije ciji je domen i kodomen odredjen skupom L2={0,1}
Zovu se funkcije algebre logike(FAL) a i zovu se jos Bulove funkcije. Def 1. 1.Preslikavanje f: L 2 n →L 2 zove se B. funkcija.B. f. se zadaje tablicom ili B. izrazom. Ako je Bulova f. zadana B. izrazom onda se izracunava neposredno odredjuje te funkcije. Teorema 1. Broj razlicitih Bulovih funkcija od n promenjivih je 2 2 pa na n . U skupu L 2 n postoji 2 n razlicitih n-torki, svakoj od njom mozemo pridruziti 0ili.Broj takvih varijacija je 2 n
x f1 f2 f3 f4 f1(x)=0 ; f2(x)=x; f3(x)=nadvuceno x ; f4(x)=1
0 0 0 1 1
1 0 1 0 1
Postoji 16 razlicitih Bulovih funkcija dve promenjive. Elementarne su sledece Bulove funkcije:
n=0 f1=0 f2=1
n=1 f3=x f4= _x_
n=2 f5(x,y)=xvy dinsjukcija ili funkcija f6 (x,y)=x'i'y konjukcija I funkcija
f7(x,y) =x <=>y ekvivalencija f8(x,y) =x=>y implikacija f9(x,y) =x↓y funkcija Veba nili funk
f10(x,y) = x↑y funkcija Sefera ni funkcija f11(x,y) =x+zaokruzeno y eskluzivno ili alternatvna disjunkcij
def 2. sostemi Bulovih funkcija {f1,f2,..f k } je potpun u klasi R, ako svakoφ E(pripada)R moze biti predstavljena superpozicijom funkcija f1,f2,.. f k . Za R uzimamo klasu Bulovih funkcija koje zavise od n argumenata. Na osnovu teoreme 1 moze se zakljuciti da postoji tivijalan potpun sistem od 2 na 2 na n bulovih funkcija.
Teorema 2. 1) disjunkcija, konjukcija, negacija 2) disj, negacija 3) konj, negacija 4) konj, alternativna disj, konstanta 1 5) funk Veba 6) funk Sefera 7) implikacija, negacija