Forma canonica

La forma canonica è una delle forme che una funzione booleana può assumere. Per ogni funzione booleana a $n$ variabili può avere due forme canoniche: prima forma canonica e seconda forma canonica. Prima però di introdurre le forme canoniche bisogna sapere cosa sono i mintermini e i maxtermini.

Mintermine

Un mintermine di variabili $x_0,x_1,\dots ,x_n$ è un prodotto di termini $y_0,y_1,\dots ,y_n$ dove $y_i$ vale $0$ o $1$ in base alla configurazione. Per costruire un mintermine abbiamo di una configurazione $\overline{v}=\{v_0,v_1,\dots ,v_n\}\in \{0,1{\}}^n$. Il mintermine sarà:

$$m_{\overline{v}}=y_0\cdot y_1\cdot \dots \cdot y_n\text{dove}\{\begin{array}{ll}{y}_i=x_i^{\prime }& x_i=0\\ y_i=x_i& x_i=1\end{array}$$

Il mintermine $m_{\overline{v}}$ viene detto mintermine corrispondente alla configurazione $\overline{v}$ ed è un’espressione che vale $1$ solamente per la configurazione $\overline{v}$.

Example

Data la configurazione $\overline{v}=\{1,0,0\}$ avremo il mintermine $m_{\overline{v}}=x{y}^{\prime }{z}^{\prime }$.

Maxtermine

Un maxtermine di variabili $x_0,x_1,\dots ,x_n$ è una somma di termini $y_0+y_1+\dots +y_n$ dove $y_i$ vale $0$ o $1$ in base alla configurazione. Per costruire un maxtermine abbiamo di una configurazione $\overline{v}=\{v_0,v_1,\dots ,v_n\}\in \{0,1{\}}^n$. Il maxtermine sarà:

$$M_{\overline{v}}=y_0+y_1+\dots +y_n\text{dove}\{\begin{array}{ll}{y}_i=x_i^{\prime }& x_i=1\\ y_i=x_i& x_i=0\end{array}$$

Il maxtermine $M_{\overline{v}}$ viene detto maxtermine corrispondente alla configurazione $\overline{v}$ ed è un’espressione che vale $0$ solamente per la configurazione $\overline{v}$.

Example

Data la configurazione $\overline{v}=\{1,0,0\}$ avremo il maxtermine $M_{\overline{v}}=x^{\prime }+y+z$.

Prima forma canonica

La prima forma canonica, o somma di prodotti (SOP), è formata dalla somma dei mintermini dove la funzione assume come valore $1$.

Se si applica il Teorema di espansione di Shannon $n$ volte si otterrà la prima forma canonica di una funzione.

Example

Prendiamo la funzione a 3 variabili $f(x,y,z)$ dove la funzione assume valore se e solo se due variabili valgono 1 e cerchiamo di rappresentarla tramite la tabella di verità.

$$\begin{array}{rrrr}x& y& z& f(x,y,z)\\ 0& 0& 0& 0\\ 0& 0& 1& 0\\ 0& 1& 0& 0\\ 1& 0& 0& 0\\ 0& 1& 1& 1\\ 1& 0& 1& 1\\ 1& 1& 0& 1\\ 1& 1& 1& 0\end{array}$$

I mintermini per ogni riga si calconano mettendo $x$ se $x=1$ e mettendo $x^{\prime }$ se $x=0$.

$$\begin{array}{rrrrr}x& y& z& f(x,y,z)& \text{mintermine}\\ 0& 0& 0& 0& -\\ 0& 0& 1& 0& -\\ 0& 1& 0& 0& -\\ 1& 0& 0& 0& -\\ 0& 1& 1& 1& x^{\prime }\cdot y\cdot z\\ 1& 0& 1& 1& x\cdot y^{\prime }\cdot z\\ 1& 1& 0& 1& x\cdot y\cdot z^{\prime }\\ 1& 1& 1& 0& -\end{array}$$

Dopo aver calcolato tutti i mintermini nelle righe in cui la funzione vale 1, li dobbiamo sommare per poi ottenere la prima forma canonica:

$$(x^{\prime }\cdot y\cdot z)+(x\cdot y^{\prime }\cdot z)+(x\cdot y\cdot z^{\prime })$$

Oppure scritto in una maniera più compatta:

$$x^{\prime }yz+x{y}^{\prime }z+xy{z}^{\prime }$$

Seconda forma canonica

La seconda forma canonica, o prodotto di somme (POS), è formata dal prodotto dei maxtermini in cui la funzione vale $0$.

Se si applica la forma duale del Teorema di espansione di Shannon $n$ volte si otterrà la seconda forma canonica di una funzione.

Example

Prendiamo la funzione a 3 variabili $f(x,y,z)$ dove la funzione assume valore se e solo se due variabili valgono 1 e cerchiamo di rappresentarla tramite la tabella di verità.

$$\begin{array}{rrrr}x& y& z& f(x,y,z)\\ 0& 0& 0& 0\\ 0& 0& 1& 0\\ 0& 1& 0& 0\\ 1& 0& 0& 0\\ 0& 1& 1& 1\\ 1& 0& 1& 1\\ 1& 1& 0& 1\\ 1& 1& 1& 0\end{array}$$

I maxtermini per ogni riga si calconano mettendo $x$ se $x=0$ e mettendo $x^{\prime }$ se $x=1$.

$$\begin{array}{rrrrr}x& y& z& f(x,y,z)& \text{maxtermine}\\ 0& 0& 0& 0& x+y+z\\ 0& 0& 1& 0& x+y+z^{\prime }\\ 0& 1& 0& 0& x+y^{\prime }+z\\ 1& 0& 0& 0& x^{\prime }+y+z\\ 0& 1& 1& 1& -\\ 1& 0& 1& 1& -\\ 1& 1& 0& 1& -\\ 1& 1& 1& 0& x^{\prime }+y^{\prime }+z^{\prime }\end{array}$$

Dopo aver calcolato tutti i mintermini nelle righe in cui la funzione vale 0, li dobbiamo moltiplicare per poi ottenere la seconda forma canonica:

$$(x+y+z)\cdot (x+y+z^{\prime })\cdot (x+y^{\prime }+z)\cdot (x^{\prime }+y+z)\cdot (x^{\prime }+y^{\prime }+z^{\prime })$$