# Porte logiche di base e Algebra di Boole

In generale con n ingressi si possono creare $2^{2^{n}}$funzioni.

## Porte logiche unarie

Le porte logiche unarie operano su un solo segnale. In base alla regola specificata prima esistono quindi solamente 4 funzioni che operano su un solo ingresso.
| Ingressi | $F_{1}$ | $F_{2}$ | $F_{3}$ | $F_{4}$ |
| 0 | 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 |
Solamente una di queste funzioni è però utile:
* La prima porta qualsiasi ingresso nell'uscita 0.
* La seconda nega l'ingresso.
* La terza porta ogni ingresso in se stesso (funzione identica).
* La quarta porta qualsiasi ingresso nell'uscita 1.
La seconda funzione è infatti quanto realizzato da una delle porte logiche di base, il gate NOT.
* Porta Logica: NOT
* Espressione:
* $Z={\overline {X_{0}}}$
* $Z=\sim X_{0}$
* $Z=\neg X_{0}$
* $Z=!X_{0}$
Tabella della verità: :
| X$_0$ | Z |
| 0 | 1 |
| 1 | 0 |
Descrizione: L'operatore/porta NOT restituisce il valore inverso di quello in entrata.

## Porte logiche binarie

Con 2 ingressi, seguendo la regola sopra specificata, è possibile ottenere 16 funzioni. Di queste soltanto Le porte logiche di base sono 3: NOT AND OR.
* Porta Logica: AND
* Espressione:
* $Z=X_{0}X_{1}$
* $Z=X_{0}\cdot X_{1}$
* $Z=X_{0}\ {\textrm {AND}}\ X_{1}$
Tabella della verità: :
| X$_1$ | X$_0$ | Z |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Descrizione: L'operatore/porta AND (letteralmente e in inglese) restituisce 1 (vero) se e solo se tutti gli operandi hanno valore 1 (vero), altrimenti restituisce 0 (falso). Tale operazione è anche detta prodotto logico.
* Porta Logica: OR
* Espressione:
* Z = X$_0$ + X$_1$
* Z = X$_0$ OR X$_1$
* Z = X$_0$ ? X$_1$
Tabella della verità: :
| X$_1$ | X$_0$ | Z |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Descrizione: L'operatore/porta OR (letteralmente o in inglese) restituisce 1 (vero) se almeno uno degli operandi è 1 (vero); ovvero restituisce 0 (falso) se e solo se tutti gli operandi sono 0 (falso). Tale operazione è anche detta somma logica.

## Altre Porte logiche

Utilizzando le 3 porte logiche di base si può descrivere il comportamento di qualsiasi rete più o meno complessa. Nella pratica esistono altre porte logiche che vengono utilizzate in sostituzione alle più frequenti operazioni logiche.
* Porta Logica: NAND
* Espressione:
* Z = X$_0$X$_1$
Tabella della verità: :
| X$_1$ | X$_0$ | Z |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Descrizione: L'operatore NAND (cioè la negazione del risultato dell'operazione AND) restituisce 0 (falso) se e solo se tutti gli elementi sono 1, mentre restituisce 1 (vero) in tutti gli altri casi.
* Porta Logica: NOR
* Espressione:
* Z = X$_0$+X$_1$
Tabella della verità: :
| X$_1$ | X$_0$ | Z |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
Descrizione: L'operatore NOR, (cioè la negazione del risultato dell'operazione OR) restituisce 1 (vero) se e solo se tutti gli elementi sono 0, mentre restituisce 0 (falso) in tutti gli altri casi.
* Porta Logica: XOR
* Espressione:
* Z = X$_0$ ⊕ X$_1$
Tabella della verità: :
| X$_1$ | X$_0$ | Z |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Descrizione: L'operatore XOR (detto anche OR esclusivo o somma modulo 2) restituisce 1 (vero) se e solo se un unico dei due operandi è 1, mentre restituisce 0 (falso) in tutti gli altri casi. Osservando la tabella della verità dell'operatore XOR, si può riscrivere lo stesso XOR utilizzando le porte logiche di base: Z = X$_0$ ⊕ X$_1$ = X$_0$X$_1$+X$_0$X$_1$
    NB:esistono altri modi equivalenti per scrivere l'espressione
* Porta Logica: XNOR
* Espressione:
* Z = X$_0$ ⊕ X$_1$
Tabella della verità: :
| X$_1$ | X$_0$ | Z |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Descrizione: L'operatore XNOR (cioè la negazione del risultato dell'operazione XOR) restituisce 0 se e solo se un unico elemento dei due è uguale a 1 e tutti gli altri elementi sono 0 Osservando la tabella della verità dell'operatore XNOR, si può riscrivere lo XNOR stesso utilizzando le porte logiche di base: Z = X$_0$ ⊕ X$_1$ = X$_0$ X$_1$+X$_0$X$_1$
    NB:esistono altri modi equivalenti per scrivere l'espressione

### Ancora sullo XOR

Nella figura sottostante è sono riportate tre "reti logiche" equivalenti che implementano l'operatore xor. In particolare si noti che la seconda e la terza rete differiscono esclusivamente per la notazione grafica, infatti per comodità spesso si preferisce sostituire l'operatore NOT semplicemente con il pallino vuoto all'ingresso/uscita delle altre porte logiche (come avrete già notato nei simboli grafici nel NAND, NOR o XNOR).

# Algebra di Boole
## Operazioni con le Costanti

a)$X_{0}\vee \mathrm {VERO} \ =\mathrm {VERO}$
b)$X_{0}\land \mathrm {FALSO} =\mathrm {FALSO}$
c)$X_{0}\vee \mathrm {FALSO} =X_{0}$
d)$X_{0}\land \mathrm {VERO} \ =X_{0}$
| Dimostrazioni: |
| Dimostrazioni: | X$_0$ | VERO | FALSO | Z$_a$ | Z$_b$ | Z$_c$ | Z$_d$ |
| Dimostrazioni: | 0 | 1 | 0 | 0+1 = 1 | 0* 0 = 0 | 0+0 = 0 | 0* 1 = 0 |
| Dimostrazioni: | 1 | 1 | 0 | 1+1 = 1 | 1* 0 = 0 | 1+0 = 1 | 1* 1 = 1 |
| Dimostrazioni: | X$_0$ | VERO | FALSO | VERO | FALSO | X$_0$ | X$_0$ |

## Proprietà base di AND e OR

a)$X_{0}\to X_{0}\vee X_{1}$
b)$X_{0}\land X_{1}\to X_{0}$
Dimostrazioni: Aiutandosi con la tabella della verità a fianco si ha:
* Proprietà a):
    X$_0$ è condizione sufficiente ma non necessaria per X$_0$+X$_1$;
       se X$_0$ è vera sicuramente X$_0$+X$_1$ è vera (sufficiente), ma X$_0$+X$_1$ potrebbe essere vera anche se X$_0$ è falsa (non necessaria)
    X$_0$ + X$_1$ è condizione necessaria ma non sufficiente per X$_0$;
       Sapere che X$_0$ + X$_1$ è vera (oppure falsa) è necessario per sapere se X$_0$ è vera (oppure falsa) ma non è sufficiente perché occorre conoscere anche X$_1$
* Proprietà b):
    X$_0$X$_1$ è condizione sufficiente ma non necessaria per X$_0$;
    X$_0$ è condizione necessaria ma non sufficiente per X$_0$X$_1$;
| Tabella della verità: |
| Tabella della verità: | X$_1$ | X$_0$ | X$_0$ + X$_1$ | X$_0$X$_1$ |
| Tabella della verità: | 0 | 0 | 0 | 0 |
| Tabella della verità: | 0 | 1 | 1 | 0 |
| Tabella della verità: | 1 | 0 | 1 | 0 |
| Tabella della verità: | 1 | 1 | 1 | 1 |
c) $X_{0}\vee X_{0}=X_{0}$
d) $X_{0}\land X_{0}=X_{0}$
| dimostrazione: |
| dimostrazione: | X$_0$ | X$_0$ | X$_0$ + X$_0$ | X$_0$X$_0$ |
| dimostrazione: | 0 | 0 | 0+0 = 0 | 0* 0 = 0 |
| dimostrazione: | 1 | 1 | 1+1 = 1 | 1* 1 = 1 |
Proprietà Commutativa: e) $X_{0}\vee X_{1}=X_{1}\vee X_{0}$
f) $X_{0}\land X_{1}=X_{1}\land X_{0}$
| dimostrazione: |
| dimostrazione: | X$_1$ | X$_0$ | X$_0$ + X$_1$ | X$_1$ + X$_0$ | X$_0$* X$_1$ | X$_1$X$_0$ |
| dimostrazione: | 0 | 0 | 0+0 = 0 | 0+0 = 0 | 0* 0 = 0 | 0* 0 = 0 |
| dimostrazione: | 0 | 1 | 1+0 = 1 | 0+1 = 1 | 1* 0 = 0 | 0* 1 = 0 |
| dimostrazione: | 1 | 0 | 0+1 = 1 | 1+0 = 1 | 0* 1 = 0 | 1* 0 = 0 |
| dimostrazione: | 1 | 1 | 1+1 = 1 | 1+1 = 1 | 1* 1 = 1 | 1* 1 = 1 |
Proprietà Associativa: g) $(X_{0}\vee X_{1})\vee X_{2}=X_{0}\vee (X_{1}\vee X_{2})$
h) $(X_{0}\land X_{1})\land X_{2}=X_{0}\land (X_{1}\land X_{2})$
Proprietà Distributiva: i) $X_{0}\land (X_{1}\vee X_{2})=(X_{0}\land X_{1})\vee (X_{0}\land X_{2})$
j) $X_{0}\vee (X_{1}\land X_{2})=(X_{0}\vee X_{1})\land (X_{0}\vee X_{2})$
| dimostrazione: |
| dimostrazione: | X$_2$ | X$_1$ | X$_0$ | X$_0$X$_1$ | X$_0$X$_2$ | X$_1$X$_2$ | X$_0$+X$_1$ | X$_0$+X$_2$ | X$_1$+X$_2$ | (X$_0$+X$_1$)+X$_2$ | X$_0$+(X$_1$+X$_2$) | (X$_0$X$_1$)X$_2$ | X$_0$(X$_1$X$_2$) | X$_0$(X$_1$+X$_2$) | (X$_0$X$_1$)+(X$_0$X$_2$) | X$_0$+(X$_1$X$_2$) | (X$_0$+X$_1$)(X$_0$+X$_2$) |
| dimostrazione: | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| dimostrazione: | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 |
| dimostrazione: | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| dimostrazione: | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
| dimostrazione: | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| dimostrazione: | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
| dimostrazione: | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 |
| dimostrazione: | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |

## Leggi di De Morgan

a)${\overline {(X_{0}\land X_{1})}}={\overline {X_{0}}}\vee {\overline {X_{1}}}$
b)${\overline {(X_{0}\vee X_{1})}}={\overline {X_{0}}}\land {\overline {X_{1}}}$
Approfondimento
| dimostrazione: |
| dimostrazione: | X$_1$ | X$_0$ | X$_1$ | X$_0$ | X$_0$X$_1$ | X$_0$+X$_1$ | (X$_0$X$_1$) | X$_0$+X$_1$ | (X$_0$ + X$_1$) | X$_0$ X$_1$ |
| dimostrazione: | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
| dimostrazione: | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 |
| dimostrazione: | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 |
| dimostrazione: | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |

## Proprietà base di NOT

${\overline {X_{0}}}\vee X_{0}=\mathrm {VERO}$
${\overline {X_{0}}}\land X_{0}=\mathrm {FALSO}$
${\overline {\overline {X_{0}}}}=X_{0}$ Doppia negazione

## Implicazione ed Equivalenza

a)$(X_{0}\land (X_{0}\to X_{1}))\to X_{1}$
b)$((X_{0}\to X_{1})\land {\overline {X_{1}}})\to {\overline {X_{0}}}$
c)$((X_{0}\vee X_{1})\land {\overline {X_{0}}})\to X_{1}$
d)$((X_{0}\to X_{1})\land (X_{1}\to X_{2}))\to (X_{0}\to X_{2})$
e)$((X_{0}\to X_{1})\land (X_{2}\to X_{3}))\to ((X_{0}\land X_{2})\to (X_{1}\land X_{3}))$
f)$((X_{0}\to X_{1})\to X_{2})\to ((X_{0}\to (X_{1}\to X_{2}))$
g)$((X_{0}\land X_{1})\to X_{2})=((X_{0}\to (X_{1}\to X_{2}))$
h)$X_{0}\to X_{1}={\overline {X_{0}}}\vee X_{1}$
i)$X_{0}\to X_{1}={\overline {X_{1}}}\to {\overline {X_{0}}}$
l)$(X_{0}\to X_{1})\land (X_{0}\to {\overline {X_{1}}})={\overline {X_{0}}}$
Equivalenza: m)$X_{0}\leftrightarrow X_{1}=(X_{0}\to X_{1})\land (X_{1}\to X_{0})$