Porte logiche di base e Algebra di Boole

Da Wikiversità, l'università aperta.

Questo modulo necessita di essere "wikificato", ovvero formattato secondo gli standard di Wikiversità (vedi l'). Collabora anche tu a rendere questo articolo conforme alle linee guida (vedi anche qui) poi rimuovi questo avviso.

Nota: Matematica

Indice

[modifica] Porte logiche di base

Le porte logiche di base sono 3: NOT AND OR.

Porta Logica: NOT
immagine:simboloNOT.png
Espressione:
  • Z = X0
  • Z = ~ X0
  • Z = ¬X0
  • Z = !X0
Tabella della verità:
X0 Z
0 1
1 0

Descrizione:
L'operatore/porta NOT restituisce il valore inverso di quello in entrata.

 
Porta Logica: AND
immagine:simboloAND.png
Espressione:
  • Z = X0X1
  • Z = X0 AND X1
  • Z = X0*X1
  • Z = X0?X1
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
immagine:simboloOR.png
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.

 

[modifica] 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 sostituizione alle più frequenti operazioni logiche.

Porta Logica: NAND
immagine:simboloNAND.png
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
immagine:simboloNOR.png
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
immagine:simboloXOR.png
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 = X0 ⊕ X1 = X0X1+X0X1

NB:esistono altri modi equivalenti per scrivere l'espressione
 
Porta Logica: XNOR
immagine:simboloXNOR.png
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 = X0 ⊕ X1 = X0 X1+X0X1

NB:esistono altri modi equivalenti per scrivere l'espressione
 

[modifica] 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).


[modifica] Algebra di Boole

[modifica] 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
 

[modifica] 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):
X0 è condizione sufficiente ma non necessaria per X0+X1;
se X0 è vera sicuramente X0+X1 è vera (sufficiente), ma X0+X1 potrebbe essere vera anche se X0 è falsa (non necessaria)
X0 + X1 è condizione necessaria ma non sufficiente per X0;
Sapere che X0 + X1 è vera (oppure falsa) è necessario per sapere se X0 è vera (oppure falsa) ma non è sufficiente perché occorre conoscere anche X1
  • Proprietà b):
X0X1 è condizione sufficiente ma non necessaria per X0;
X0 è condizione necessaria ma non sufficiente per X0X1;
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
 

[modifica] 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
 

[modifica] 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

[modifica] 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)

Estratto da "http://it.wikiversity.org/wiki/Porte_logiche_di_base_e_Algebra_di_Boole"
Strumenti personali