[ R A V E N @ 19.05.2014. 19:58 ] @
Koliko ima Booleovih funkcija od , , , i promenljivih?

Izdanje XX

Izrada:
Iz jedne knjige znam da je taj broj , ali me interesuje kako se došlo do tog broja ? Inače, u Miličić - Ušćumlić knjizi je netačno navedeno .
[ djoka_l @ 19.05.2014. 22:08 ] @
Recimo da Bulove funkcije nad n parametara obeležimo sa , tj. da odredimo koliko različitih funkcija oblika postoji.
Pošto su bulove promenljnive, broj kombinacija koje predstavljaju različite vrednosti tog vektora su .
Rezultat funkcije je, prema tome vektor Bulovih vrednosti (binarni vektor) dužine , a takvih različitih vektora ima tačno

Primer, za dva parametra, postoji 16 Bulovih funkcija
Code:

x y | 0 1 2 3 4 5 6 7 8 9 A B C D E F
0 0 | 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 1 | 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
1 0 | 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 1 | 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1


Funkcija 0 je konstanta 0, F je konstanta 1, 7 je OR, 1 je AND, 8 je NOR, E je NAND, 6 je XOR.
Obrati pažnju da neke od ovih funkcija, zapravo nisu funkcije dve promenljive, na primer funkcija 3 je x, 5 je y, C je NOT x, A je NOT y, 0 i F su konstante, ali se sve one računaju kao jedna od mogućih f-ja dve promenljive.
[ R A V E N @ 20.05.2014. 23:21 ] @
U redu, hvala ti, djoka_l, proučiću tvoj odgovor nešto kasnije.
[ djoka_l @ 21.05.2014. 09:55 ] @
Uzgred, ako imamo skup A koji ima p elemenata, tada je broj različitih preslikavanja jednak .
Ista je logika kao i za Bulove funkcije, broj različitih n-torki koje pripadaju skupu je jednak broju varijacija sa ponavljenjem n-te klase od p elemenata.
Tada je svako preslikavanje jedna od varijacija sa ponavljem klase od p elemenata, a njihov broj je .

[ MajorFatal @ 26.05.2014. 00:55 ] @
Citat:
djoka_l:
Recimo da Bulove funkcije nad n parametara obeležimo sa , tj. da odredimo koliko različitih funkcija oblika postoji.
Pošto su bulove promenljnive, broj kombinacija koje predstavljaju različite vrednosti tog vektora su .
Rezultat funkcije je, prema tome vektor Bulovih vrednosti (binarni vektor) dužine , a takvih različitih vektora ima tačno

Primer, za dva parametra, postoji 16 Bulovih funkcija
Code:

x y | 0 1 2 3 4 5 6 7 8 9 A B C D E F
0 0 | 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 1 | 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
1 0 | 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 1 | 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1


Funkcija 0 je konstanta 0, F je konstanta 1, 7 je OR, 1 je AND, 8 je NOR, E je NAND, 6 je XOR.
Obrati pažnju da neke od ovih funkcija, zapravo nisu funkcije dve promenljive, na primer funkcija 3 je x, 5 je y, C je NOT x, A je NOT y, 0 i F su konstante, ali se sve one računaju kao jedna od mogućih f-ja dve promenljive.


2 je Inhibicija = xy' (x, not y) takodje x>y tj. y<x
4 -||- -||- y>x
(mada bi ja cinimise ono x, not y pisao kao x i ne y)

9 je ekvivalencija, jednakost, (x = y), takodje ekskluzivno NOR

B je imlikacija, y implicira x, ili x + y' (ako y onda x) takodje y >= x
D -||- -||- (ako x onda y)
(i ovde mislim da je odgovarajuca oznaka x -> y (iz x sledi y))

mslm, ja ovo iz tabele:



[ MajorFatal @ 26.05.2014. 01:08 ] @
@ R A V E N Mozda ti moze biti od pomoci knjiga iz koje sam preuzeo ovu tabelu Art Of Assembly Language http://portal.aauj.edu/portal_...mbly_language32bit_edition.pdf ima poglavlje o Bulovim funkcijama kao i par razlicitih nacina kako se mogu pisati te koliko ih ima za koliko parametara itd, ali ne iz knjige Art Of Intel Assembly kao ovde:



ladno su zamenili mesta funkcijama 2 i 4.
[ R A V E N @ 26.05.2014. 17:09 ] @
OK, preuzeo sam knjigu.