Preklopne funkcije in vezja

Preklopne spremenljivke: neodvisne spremenljivke $x_1$, …, $x_n$ $\in \{0,1\}$
Preklopna funkcija: odvisna spremenljivka nad preklopnimi spremenljivkami $f(x_1,...,x_n)\in \{0,1\}$

Vhodni vektorji: ${\vec{w}}_i$ predstavlja število $i$ v binarnem zapisu, pri čemer so $0$ in $1$ razporejene po preklopnih spremenljivkah
Primer: ${\vec{w}}_3=(0,...,0,1,1)$ pomeni, da sta v tabeli najbolj desni spremenljivki v tem primeru nastavljeni na $1$, ostale pa na $0$
Vseh vhodnih vektorjev je $2^n$ - vse kombinacije nastavitev vrednosti $n$ spremenljivk
Pravilnostna tabela:

Logične funkcije: za $n$ spremenljivk obstaja $2^{2^n}$ logičnih funkcij
Logični simboli / operatorji: (podobni/isti kot izjavni vezniki)

Mintermi, makstermi, PDNO in PKNO

$$x^w=\{\begin{array}{l}x;w=1\\ \overline{x};w=0\end{array}$$

Minterm: Spremenljivke povezujemo s konjunkcijami in uporabljamo negacije

$$m_i=x_1^{w_{1i}}...x_n^{w_{ni}}$$

Maksterm: Spremenljivke povezujemo z disjunkcijami in uporabljamo negacije

$$M_{2^n-1-i}=x_1^{\overline{w_{1i}}}\vee x_n^{\overline{w_{ni}}}$$

Primer: 3 spremenljivke

Relacije med mintermi in makstermi:

$$\begin{array}{rl}\overline{m_i}& =M_{2^n-1-i}\\ \overline{M_i}& =m_{2^n-1-i}\end{array}$$

Popolne normalne oblike

Popolna disjunktivna normalna oblika (PDNO): disjunkcija osnovnih konjunkcij vseh (vhodnih) spremenljivk

$$f(x_1,...,x_n)=\underset{i=0}{\overset{2^n-1}{\bigvee }}{m}_i{f}_i$$

Primer zapisa: $f(x_1,x_2,x_3)m_1\vee m_2\vee m_4\vee m_7=\vee (1,2,4,7)$
Popolna konjunktivna normalna oblika (PKNO): konjunkcija osnovnih disjunkcij vseh (vhodnih) spremenljivk

$$f(x_1,...,x_n)=\underset{i=0}{\overset{2^n-1}{\bigwedge }}(M_{2^n-1-i}\vee f_i)$$

Primer zapisa: $f(x_1,x_2,x_3)M_7{M}_4{M}_2{M}_1=\wedge (1,2,4,7)$
Pretvorba med PDNO in PKNO: dvojna negacija funkcije

Popolna Shefferjeva normalna oblika (PSNO): Shefferjevi mintermi ($s_i=x_1^{w_{1i}}\uparrow ...\uparrow x_n^{w_{ni}}$), povezani s Shefferjevim operatorjem

$$f(x_1,...,x_n)={\uparrow }_{i=0}^{2^n-1}(f_i\uparrow s_i)$$

Popolna Pierceva normalna oblika: Piercevi makstermi (P_{2^n-1-i}=x_1^\overline{w_{1i}}\downarrow ... \downarrow x_n^\overline{w_{ni}}), povezani s Piercevim operatorjem

$$f(x_1,...,x_n)={\downarrow }_{i=0}^{2^n-1}(f_i\downarrow P_{2^n-1-i})$$

Veitchev diagram

Obsega $2^n$ polj, vsako polje določa minterm, presečišče polj pa določa funkcijo
Uporablja se za zapis in minimizacijo funkcij

Primer uporabe za minimizacijo:

Ločenje oz. Shannonov teorem

$$\begin{array}{rl}f(x_1,...,x_n)& =f(0,x2,...,x_n)\overline{x_1}\vee f(1,x2,...,x_n)x_1\\ f(x_1,...,x_n)& =(f(0,x2,...,x_n)\vee x_1)(f(1,x2,...,x_n)\vee \overline{x_1})\end{array}$$

Če funkcijo po tem postopku ločimo po vseh spremenljivkah, pridemo do PDNO oblike funkcije

Dekompozicija preklopne funkcije

Funkcijo razdlimo na dva dela, zaradi česar jo lahko (če je možno) realiziramo z manj elementi.

$$f(x_1,...,x_n)=g(h(x_1,...,x_s),x_{s+1},...,x_n)$$

Primer: $f(x_1,x_2,x_3,x_4,x_5)=x_1{x}_2{x}_3\vee x_1{x}_2{x}_4\vee x_1{x}_2{x}_5=x_1{x}_2(x_3\vee x_4\vee x_5)$

Odvisnost funkcije od spremenljivke

$$\frac{df(x_1,x_2,x_3)}{d{x}_i}=f(x_1,...,0,...,x_n)▽f(x_1,...,1,...,x_n)=\{\begin{array}{l}0;\text{funkcija ni odvisna od }{x}_i\\ 1;\text{funkcija je odvisna od }{x}_i\\ 0;\text{funkcija je odvisna od }{x}_i\text{ pod pogojem g}\end{array}$$

Variantnost preklopne funkcije

Funkcija je invariantna za zamenjavo dveh spremenljivk, če se pri zamenjavi neodvisnih spremenljivk med seboj funkcijska vrednost ne spremeni:

$$f(x_1,...,x_i,...,x_j,...,x_n)=f(x_1,...,x_j,...,x_i,...,x_n);i\ne j$$

Simetrične funkcije

Funkcija je:

• popolnoma simetrična, če je invariantna za vse zamenjave
• delno simetrična, če je invariantna samo pri nekaterih zamenjavah
• popolnoma nesimetrična, če je neinvariantna za vse zamenjave

Simetrijska števila

Simetrijsko število $m$ $⟺$ $m$ enic v vektorju vhodnih spremenljivk
Popolnoma simetrična funkcija mora imeti enako vrednost pri vseh simetrijskih številih (če ne bi pomenilo, da obstaja transpozicija enic po vhodnih vrednostih, ki se ne bi skladala z ostalimi)
$f_{\{\vec{m}\}}(x_1,...,x_n)$ - funkcija, simetrična pri simetričnih številih $\vec{m}$

Simetrična števila

Lastnosti simetričnih funkcijah

Simetrične funkcije so tudi:

• Negacija simetrične funkcije
• Negacija vhodnih spremenljivk
• Dualna funkcija

Konjunkcija in disjunkcija ohranjata simetričnost
Ločenje ohranja simetričnost

Testiranje simetričnosti

1. Testiranje vseh $2^n$ vhodnih naborov $(n-1)$ transpozicij
2. S pomočjo razširjenega Veitchevega diagrama - številke v poljih predstavljajo število enic v vhodnem vektorju:
   1. Kot masko premikaš osnovni Veitchev diagram po razširjenem Veitchevem diagramu
   2. Če pokriva vsa enaka števila, je na ta števila simetrična, pri vhodu, kot razberemo iz pozicije zadnega minterma
      Primer modre: pokrite so vse $1$ in $4$, minterm $m_{15}$ predstavlja $\overline{x_1}{x}_2\overline{x_3}{x}_4$ - zato je funkcija pri tem vhodu simetrična funkcija za simetrijska števila $1$ in $4$