Funzione booleana

Le funzioni booleane è una relazione di questo tipo:

$$f:A^n\mapsto A$$

Se prendiamo come supporto $A=\{0,1\}$, quindi nell’algebra di commutazione, la funzione prenderà questa forma:

$$f:\{0,1{\}}^n\mapsto \{0,1\}$$

Le funzioni booleane che possiamo avere sono solamente delle tipologie sotto riportate oppure sono derivate da esse. Qualunche altra cosa al di fuori dalle regole di sottto non è una funzione booleana:

• Funzione costante: $f(x_1,x_2,\dots ,x_n)=a,\forall a\in A$
• Funzione proiezione: $f(x_1,\dots x_n)=x_i,\forall x_i\in \{x_1,\dots ,x_n\}$
• Composizione di funzioni:
  • $(g+h)(x_1,\dots ,x_n)=g(x_1,\dots ,x_n)+h(x_1,\dots ,x_n)$
  • $(g\cdot h)(x_1,\dots ,x_n)=g(x_1,\dots ,x_n)\cdot h(x_1,\dots ,x_n)$
  • $(g^{\prime })=(g(x_1,\dots ,x_n){)}^{\prime }$

Date $n$ variabili si hanno $2^n$ possibili configurazioni (2 perché $A=\{0,1\}$).

Ogni funzione è definita da un insieme di configurazioni.

Funzione non completamente specificata

Una funzione non è completamente specificata quando alcuni output non vengono contemplati. Ci sono due casi per cui ha una funzione viene data questa definizione:

• Funzione non controllabile: la natura del problema garantisce che una data combinazione delle variabili di ingresso non possa presentarsi.
• Funzione non osservabile: non ha importanza quale valore assuma la funzione per una data combinazione delle variabili di ingresso.

Example

Prendiamo la funzione che:

1. Manda in output il valore 1 se entrambe le variabili valgono 0.
2. Manda in output il valore 0 se le variabili sono diverse.

$$f(x_1,x_2)=1⟺x_1=x_2=0\wedge f(x_1,x_2)=0⟺x_1\ne x_2$$

Questa funzione avrà come tabella di verità la seguente:

$$\begin{array}{rrr}{x}_1& x_2& f(x_1,x_2)\\ 0& 0& 1\\ 0& 1& 0\\ 1& 0& 0\\ 1& 1& -\end{array}$$