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à:
X0		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à:
X1	X0		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 = X0 + X1 Z = X0 OR X1 Z = X0 ? X1

Tabella della verità:
X1	X0		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 = X0X1

Tabella della verità:
X1	X0		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 = X0+X1

Tabella della verità:
X1	X0		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 = X0 ⊕ X1

Tabella della verità:
X1	X0		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₀ ⊕ X₁ = X₀X₁+X₀X₁

NB:esistono altri modi equivalenti per scrivere l'espressione

 

Porta Logica: XNOR

Espressione:

Z = X0 ⊕ X1

Tabella della verità:
X1	X0		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₀ ⊕ X₁ = X₀ X₁+X₀X₁

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:
	X0	VERO	FALSO		Za		Zb		Zc		Zd
	0	1	0	0+1 = 1	0* 0 = 0	0+0 = 0	0* 1 = 0
	1	1	0	1+1 = 1	1* 0 = 0	1+0 = 1	1* 1 = 1
	X0	VERO	FALSO	VERO	FALSO	X0	X0

 

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₀ è condizione sufficiente ma non necessaria per X₀+X₁;

se X₀ è vera sicuramente X₀+X₁ è vera (sufficiente), ma X₀+X₁ potrebbe essere vera anche se X₀ è falsa (non necessaria)

X₀ + X₁ è condizione necessaria ma non sufficiente per X₀;

Sapere che X₀ + X₁ è vera (oppure falsa) è necessario per sapere se X₀ è vera (oppure falsa) ma non è sufficiente perché occorre conoscere anche X₁

• Proprietà b):

X₀X₁ è condizione sufficiente ma non necessaria per X₀;

X₀ è condizione necessaria ma non sufficiente per X₀X₁;

Tabella della verità:
	X1	X0		X0 + X1		X0X1
	0	0	0	0
	0	1	1	0
	1	0	1	0
	1	1	1	1

 

c) $X_{0}\vee X_{0}=X_{0}$

d) $X_{0}\land X_{0}=X_{0}$

dimostrazione:
	X0	X0		X0 + X0		X0X0
	0	0	0+0 = 0	0* 0 = 0
	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:
	X1	X0		X0 + X1		X1 + X0		X0* X1		X1X0
	0	0	0+0 = 0	0+0 = 0	0* 0 = 0	0* 0 = 0
	0	1	1+0 = 1	0+1 = 1	1* 0 = 0	0* 1 = 0
	1	0	0+1 = 1	1+0 = 1	0* 1 = 0	1* 0 = 0
	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:
	X2	X1	X0		X0X1	X0X2	X1X2		X0+X1	X0+X2	X1+X2		(X0+X1)+X2	X0+(X1+X2)		(X0X1)X2	X0(X1X2)		X0(X1+X2)	(X0X1)+(X0X2)		X0+(X1X2)	(X0+X1)(X0+X2)
	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
	0	0	1	0	0	0	1	1	0	1	1	0	0	0	0	1	1
	0	1	0	0	0	0	1	0	1	1	1	0	0	0	0	0	0
	0	1	1	1	0	0	1	1	1	1	1	0	0	1	1	1	1
	1	0	0	0	0	0	0	1	1	1	1	0	0	0	0	0	0
	1	0	1	0	1	0	1	1	1	1	1	0	0	1	1	1	1
	1	1	0	0	0	1	1	1	1	1	1	0	0	0	0	1	1
	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:
	X1	X0		X1	X0		X0X1	X0+X1		(X0X1)	X0+X1		(X0 + X1)	X0 X1
	0	0	1	1	0	0	1	1	1	1
	0	1	1	0	0	1	1	1	0	0
	1	0	0	1	0	1	1	1	0	0
	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})$