153. - Miličić - Ušćumlić

153. - Miličić - Ušćumlić 19.05.2014. u 20:58 · pre 152 meseca #1

Koliko ima Booleovih funkcija od $1$ , $2$ , $3$ , $4$ i $5$ promenljivih?

Izdanje XX

Izrada:
Iz jedne knjige znam da je taj broj $2^{2^{n}}$ , ali me interesuje kako se došlo do tog broja $2^{2^{n}}$ ? Inače, u Miličić - Ušćumlić knjizi je netačno navedeno $2^{2n}$ .

Re: 153. - Miličić - Ušćumlić 19.05.2014. u 23:08 · pre 152 meseca #2

Recimo da Bulove funkcije nad n parametara obeležimo sa $+_k$ , tj. da odredimo koliko različitih funkcija oblika $a_1 +_k a_2 +_k ... +_k a_n$ postoji.
Pošto su $a_1 , a_2 , ... , a_n$ bulove promenljnive, broj kombinacija koje predstavljaju različite vrednosti tog vektora su $2^n$ .
Rezultat funkcije $+_k$ je, prema tome vektor Bulovih vrednosti (binarni vektor) dužine $2^n$ , a takvih različitih vektora ima tačno $2{^{2^{n}}$

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.

Re: 153. - Miličić - Ušćumlić 21.05.2014. u 00:21 · pre 152 meseca #3

U redu, hvala ti, djoka_l, proučiću tvoj odgovor nešto kasnije.

Re: 153. - Miličić - Ušćumlić 21.05.2014. u 10:55 · pre 151 mesec #4

Uzgred, ako imamo skup A koji ima p elemenata, tada je broj različitih preslikavanja $A^n \rightarrow A$ jednak $p^{p^n}}$ .
Ista je logika kao i za Bulove funkcije, broj različitih n-torki koje pripadaju skupu $A^n$ je jednak broju varijacija sa ponavljenjem n-te klase od p elemenata $p^n$ .
Tada je svako preslikavanje jedna od varijacija sa ponavljem $p^n$ klase od p elemenata, a njihov broj je $p^{p^n}}$ .

Re: 153. - Miličić - Ušćumlić 26.05.2014. u 01:55 · pre 151 mesec #5

Citat:

djoka_l:
Recimo da Bulove funkcije nad n parametara obeležimo sa $+_k$ , tj. da odredimo koliko različitih funkcija oblika $a_1 +_k a_2 +_k ... +_k a_n$ postoji.
Pošto su $a_1 , a_2 , ... , a_n$ bulove promenljnive, broj kombinacija koje predstavljaju različite vrednosti tog vektora su $2^n$ .
Rezultat funkcije $+_k$ je, prema tome vektor Bulovih vrednosti (binarni vektor) dužine $2^n$ , a takvih različitih vektora ima tačno $2{^{2^{n}}$

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:

Re: 153. - Miličić - Ušćumlić 26.05.2014. u 02:08 · pre 151 mesec #6

@ 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.

Re: 153. - Miličić - Ušćumlić 26.05.2014. u 18:09 · pre 151 mesec #7

OK, preuzeo sam knjigu.

Forum kao aplikacija na telefonu

Srodne teme