MATEMANIJA

Logičkih funkcija on [inlmath]n[/inlmath]- argumenata ima [inlmath]2^{2^n}[/inlmath].
Ako imamo, recimo [inlmath]f(x,y)[/inlmath], onda bi njene vrednosti bile:[inlmath]f(0,0)=0[/inlmath], [inlmath]f(0,0)=1[/inlmath], [inlmath]f(0,1)=0[/inlmath], [inlmath]f(0,1)=1[/inlmath], [inlmath]f(1,0)=0[/inlmath], [inlmath]f(1,0)=1[/inlmath], [inlmath]f(1,1)=0[/inlmath], [inlmath]f(1,1)=1[/inlmath].
Ovde sam [inlmath]0[/inlmath] i [inlmath]1[/inlmath] obeležavao tačno i netačno.
Ovde imam [inlmath]8[/inlmath] funkcija. Gde grešim u tumačenju pojma logičke funkcije?

Mi smo na fakultetu ovako radili, evo iz skripte sa časa.

Pošto kod funkcije [inlmath]f\left(x_1,x_2,\ldots,x_n\right)[/inlmath] svaki od argumenata [inlmath]x_1,x_2,\ldots,x_n[/inlmath] može imati neku od dve vrednosti, [inlmath]0[/inlmath] ili [inlmath]1[/inlmath], tada je broj načina na koji se vrednosti argumenata mogu rasporediti jednak broju varijacija s ponavljanjem od [inlmath]2[/inlmath] elementa [inlmath]n[/inlmath]-te klase i iznosi [inlmath]2^n[/inlmath]. Za svaki od tih [inlmath]2^n[/inlmath] rasporeda vrednosti argumenata, funkcija može dati neku od dve moguće vrednosti, [inlmath]0[/inlmath] ili [inlmath]1[/inlmath]. Znači, broj načina na koji možemo definisati logičku funkciju jednak je broju varijacija s ponavljanjem od [inlmath]2[/inlmath] elementa [inlmath]2^n[/inlmath]-te klase, a to iznosi [inlmath]2^{2^n}[/inlmath].

Evo i ilustracije – prikazano je na koje sve načine možemo definisati logičke funkcije od [inlmath]n[/inlmath] argumenata:
[dispmath]\begin{matrix}
\left.\begin{array}{c}
f_1\left(0,0,\ldots0,0\right)=0\\
f_1\left(0,0,\ldots0,1\right)=0\\
f_1\left(0,0,\ldots1,0\right)=0\\
\vdots\\
f_1\left(1,1,\ldots1,0\right)=0\\
f_1\left(1,1,\ldots1,1\right)=0
\end{array}\;\right\}2^n & \left.\begin{array}{c}
f_2\left(0,0,\ldots0,0\right)=0\\
f_2\left(0,0,\ldots0,1\right)=0\\
f_2\left(0,0,\ldots1,0\right)=0\\
\vdots\\
f_2\left(1,1,\ldots1,0\right)=0\\
f_2\left(1,1,\ldots1,1\right)=1
\end{array}\;\right\}2^n & \left.\begin{array}{c}
f_3\left(0,0,\ldots0,0\right)=0\\
f_3\left(0,0,\ldots0,1\right)=0\\
f_3\left(0,0,\ldots1,0\right)=0\\
\vdots\\
f_3\left(1,1,\ldots1,0\right)=1\\
f_3\left(1,1,\ldots1,1\right)=0
\end{array}\;\right\}2^n\\
\\
& \vdots\\
\\
\left.\begin{array}{c}
f_{m-2}\left(0,0,\ldots0,0\right)=1\\
f_{m-2}\left(0,0,\ldots0,1\right)=1\\
f_{m-2}\left(0,0,\ldots1,0\right)=1\\
\vdots\\
f_{m-2}\left(1,1,\ldots1,0\right)=0\\
f_{m-2}\left(1,1,\ldots1,1\right)=1
\end{array}\;\right\}2^n & \left.\begin{array}{c}
f_{m-1}\left(0,0,\ldots0,0\right)=1\\
f_{m-1}\left(0,0,\ldots0,1\right)=1\\
f_{m-1}\left(0,0,\ldots1,0\right)=1\\
\vdots\\
f_{m-1}\left(1,1,\ldots1,0\right)=1\\
f_{m-1}\left(1,1,\ldots1,1\right)=0
\end{array}\;\right\}2^n & \left.\begin{array}{c}
f_m\left(0,0,\ldots0,0\right)=1\\
f_m\left(0,0,\ldots0,1\right)=1\\
f_m\left(0,0,\ldots1,0\right)=1\\
\vdots\\
f_m\left(1,1,\ldots1,0\right)=1\\
f_m\left(1,1,\ldots1,1\right)=1
\end{array}\;\right\}2^n
\end{matrix}[/dispmath]
[dispmath]\Rightarrow\quad m=2^{2^n}[/dispmath]
Evo ti i primer za logičke funkcije dve promenljive:
[dispmath]\begin{matrix}
\begin{array}{c}
f_1\left(0,0\right)=0\\
f_1\left(0,1\right)=0\\
f_1\left(1,0\right)=0\\
f_1\left(1,1\right)=0
\end{array} & \begin{array}{c}
f_2\left(0,0\right)=0\\
f_2\left(0,1\right)=0\\
f_2\left(1,0\right)=0\\
f_2\left(1,1\right)=1
\end{array} & \begin{array}{c}
f_3\left(0,0\right)=0\\
f_3\left(0,1\right)=0\\
f_3\left(1,0\right)=1\\
f_3\left(1,1\right)=0
\end{array} & \begin{array}{c}
f_4\left(0,0\right)=0\\
f_4\left(0,1\right)=0\\
f_4\left(1,0\right)=1\\
f_4\left(1,1\right)=1
\end{array}\\
\\
\begin{array}{c}
f_5\left(0,0\right)=0\\
f_5\left(0,1\right)=1\\
f_5\left(1,0\right)=0\\
f_5\left(1,1\right)=0
\end{array} & \begin{array}{c}
f_6\left(0,0\right)=0\\
f_6\left(0,1\right)=1\\
f_6\left(1,0\right)=0\\
f_6\left(1,1\right)=1
\end{array} & \begin{array}{c}
f_7\left(0,0\right)=0\\
f_7\left(0,1\right)=1\\
f_7\left(1,0\right)=1\\
f_7\left(1,1\right)=0
\end{array} & \begin{array}{c}
f_8\left(0,0\right)=0\\
f_8\left(0,1\right)=1\\
f_8\left(1,0\right)=1\\
f_8\left(1,1\right)=1
\end{array}\\
\\
\begin{array}{c}
f_9\left(0,0\right)=1\\
f_9\left(0,1\right)=0\\
f_9\left(1,0\right)=0\\
f_9\left(1,1\right)=0
\end{array} & \begin{array}{c}
f_{10}\left(0,0\right)=1\\
f_{10}\left(0,1\right)=0\\
f_{10}\left(1,0\right)=0\\
f_{10}\left(1,1\right)=1
\end{array} & \begin{array}{c}
f_{11}\left(0,0\right)=1\\
f_{11}\left(0,1\right)=0\\
f_{11}\left(1,0\right)=1\\
f_{11}\left(1,1\right)=0
\end{array} & \begin{array}{c}
f_{12}\left(0,0\right)=1\\
f_{12}\left(0,1\right)=0\\
f_{12}\left(1,0\right)=1\\
f_{12}\left(1,1\right)=1
\end{array}\\
\\
\begin{array}{c}
f_{13}\left(0,0\right)=1\\
f_{13}\left(0,1\right)=1\\
f_{13}\left(1,0\right)=0\\
f_{13}\left(1,1\right)=0
\end{array} & \begin{array}{c}
f_{14}\left(0,0\right)=1\\
f_{14}\left(0,1\right)=1\\
f_{14}\left(1,0\right)=0\\
f_{14}\left(1,1\right)=1
\end{array} & \begin{array}{c}
f_{15}\left(0,0\right)=1\\
f_{15}\left(0,1\right)=1\\
f_{15}\left(1,0\right)=1\\
f_{15}\left(1,1\right)=0
\end{array} & \begin{array}{c}
f_{16}\left(0,0\right)=1\\
f_{16}\left(0,1\right)=1\\
f_{16}\left(1,0\right)=1\\
f_{16}\left(1,1\right)=1
\end{array}
\end{matrix}[/dispmath]
Dakle, za [inlmath]n=2[/inlmath] imamo ukupno [inlmath]2^{2^2}[/inlmath], tj. [inlmath]16[/inlmath] mogučih funkcija.

---

Imali smo nedavno vrlo sličan zadatak, samo ne s logičkim funkcijama, već s binarnim relacijama – tamo se u opštem slučaju dobije malko drugačiji rezultat, [inlmath]2^{n^2}[/inlmath]. Možeš i njega pogledati.

Ali valjda je [inlmath]f_1(0,0)=f_2(0,0)=\cdots=f_8(0,0)=0[/inlmath]. To su valjda sve iste funkcije, jer imaju iste argumente i iste vrednosti. Kako su to različite funkcije?

Ne možeš na osnovu toga što neke funkcije za neku određenu kombinaciju vrednosti argumenata daju iste vrednosti, zaključiti da su to iste funkcije. Te funkcije, iako sve za [inlmath]\left(0,0\right)[/inlmath] daju vrednost nula, za neke druge vrednosti argumenata daće međusobno različite vrednosti. Npr. za [inlmath]\left(0,1\right)[/inlmath] funkcije [inlmath]f_1[/inlmath] do [inlmath]f_4[/inlmath] daće nulu a funkcije [inlmath]f_5[/inlmath] do [inlmath]f_8[/inlmath] daće jedinicu.

Posmatrajmo to na primeru funkcija jedne promenljive, npr. [inlmath]f_1\left(x\right)=e^x[/inlmath] i [inlmath]f_2\left(x\right)=x+1[/inlmath]. Pošto je [inlmath]f_1\left(0\right)=f_2\left(0\right)[/inlmath], da li bi odatle zaključio da su funkcije [inlmath]f_1\left(x\right)[/inlmath] i [inlmath]f_2\left(x\right)[/inlmath] iste?

Aha ,dake svaka funkcija je različito "pravilo" koje je izraženo logičkim operacijama i izrazima. Tj. recimo:
[inlmath]f_1(x,y)=x\cdot y[/inlmath] i [inlmath]f_2(x,y)=x+y[/inlmath]. Na fakultetu smo obeležavali operaciju konjukcije [inlmath]\cdot[/inlmath] a disjunkcije [inlmath]+[/inlmath]. I recimo [inlmath]f_1(0,1)=0\cdot1[/inlmath],a [inlmath]f_2(0,1)=0+1[/inlmath],tj. [inlmath]f_1(0,1)=0[/inlmath] a [inlmath]f_2(0,1)=1[/inlmath].
Je li dobro?

Jeste, dobro je.

Inače, funkcija ne mora biti izražena logičkim operacijama. Može biti izražena i tabelarno. Mada, i kada je zadata tabelarno, opet je moguće naći odgovarajući logički izraz, u kojem figurišu logičke operacije, kojim će ta funkcija biti predstavljena.