Operazioni Binarie

Algebra booleana

Variabili Booleane

Una variabile booleana è una variabile che può assumere il valore 1 o il valore 0. Esse sono utilizzate per analizzare il comportamento dei dispositivi, poiché un generico componente digitale riceve degli ingressi e produce delle uscite costituiti da segnali binari. Spesso si desidera sapere l'uscita o le uscite di un dispositivo in funzione dei valori di ingresso. In questo caso si possono indicare con X1 , X2 , …, Xn le variabili booleane che rappresentano i valori in ingresso e con Y1 , Y2 , …, Ym le variabili che rappresentano i valori di uscita. Poiché ogni variabile in gioco può assumere solo i valori di 1 e di 0, allora esistono 2n diverse combinazioni dei valori di ingresso e 2m possibili combinazioni dei valori d'uscita. Di conseguenza, è possibile costruire una tabella dove si possono inserire tutte le combinazioni di ingresso e le uscite relative. La tabella avrà n+m colonne e 2n righe, ovvero:

X1 X2 Xn Y1 Y2 Ym
0 0 1
1 1 1

Questo tipo di tabella elenca tutte le possibili uscite e descrive completamente il dispositivo. Essa viene detta tavola della verità.

La seguente tavola della verità elenca tutte le uscite in base al valore di 3 variabili di ingresso X1 , X2 , X3:

X1 X2 X3 Y1 Y2
0 0 0 1 1
0 0 1 1 0
0 1 0 0 0
0 1 1 0 0
1 0 0 0 1
1 0 1 1 0
1 1 0 1 1
1 1 1 0 0

NOT

Il NOT è una operazione unaria. Applicata ad un valore booleano X, il valore di NOT X corrisponde all'inverso del valore di X. L'inverso del valore 1 è 0 e l'inverso del valore 0 è 1. L'operazione NOT viene anche chiamata inversione, complementazione o negazione.

X NOT X
0 1
1 0

Proprietà:

  • Doppia negazione: NOT (NOT X) = X

OR

L'operazione binaria OR, o unione di due valori X e Y fornisce come risultato il valore 1 se almeno uno dei due valori è 1, oppure 0 se entrambi hanno valore 0. L'operazione OR può essere considerata la somma logica dei valori X e Y, e viene indicata anche con il segno "+".

X Y X OR Y
0 0 0
0 1 1
1 0 1
1 1 1

Proprietà

  • Associativa: X OR (Y OR Z) = (X OR Y) OR Z
  • Commutativa: X OR Y = Y OR X
  • Complemento: X OR (NOT X) = 1
  • Idempotenza: X OR X = X
  • Identità: X OR 0 = X
  • Elemento nullo: X OR 1 = 1

AND

L'operazione binaria AND, o intersezione di due valori X e Y fornisce come risultato 1 se entrambi i valori sono 1 e come risultato 0 se almeno uno dei due è 0. L'operazione AND può essere considerata come il prodotto logico dei due valori X e Y e viene indicata anche con il segno di prodotto (sottinteso).

X Y X AND Y
0 0 0
0 1 0
1 0 0
1 1 1

Proprietà

  • Associativa: X AND (Y AND Z) = (X AND Y) AND Z
  • Commutativa: X AND Y = Y AND X
  • Complemento: X AND (NOT X) = 0
  • Idempotenza: X AND X = X
  • Identità: X AND 1 = X
  • Elemento nullo: X AND 0 = 0

Dualità

Il principio di dualità stabilisce che data una uguaglianza se ne può ottenere un'altra scambiando gli operatori AND con operatori OR e il valore 1 con il valore 0 e viceversa.
Le proprietà dell'OR e dell'AND sono duali, ad esempio la complementarietà per l'OR stabilisce che:
X OR (NOT X) = 1
Sostituendo l'operatore AND al posto di OR e il valore 0 al posto del valore 1 si ottiene:
X AND (NOT X) = 0
che corrisponde alla proprietà di complementarietà per l'operatore AND.

Ulteriori proprietà delle operazioni AND e OR

  • Assorbimento:

X OR (X AND Y) = X
X AND (X OR Y) = X

  • Distributiva:

X OR (Y AND Z) = (X OR Y) AND (X OR Z)
X AND (Y OR Z) = (X AND Y) OR (X AND Z)

Teoremi di De Morgan

Le formule dei teoremi di De Morgan stabiliscono che l'AND negato di due variabili corrisponde all'OR delle due variabili negate singolarmente. Analogamente, per la dualità con l'OR negato di due variabili.

  • NOT (X AND Y) = (NOT X) OR (NOT Y)
  • NOT (X OR Y) = (NOT X) AND (NOT Y)

XOR

L'operazione di XOR viene anche detta operazione di "OR esclusivo" e fornisce come risultato 1 quando le variabili X e Y hanno valori diversi, mentre fornisce come risultato 0 quando hanno lo stesso valore.

X Y X XOR Y
0 0 1
0 1 0
1 0 0
1 1 1

Proprietà

  • Associativa: X XOR Y XOR Z = (X XOR Y) XOR Z = X XOR (Y XOR Z)
  • Commutativa: X XOR Y = Y XOR X
  • Complemento: X XOR NOT X = 1
  • Idempotenza: X XOR X = 0
  • Identità: X XOR 0 = X
  • Inverso: X XOR 1 = NOT X

NOR e NAND

L'operazione di NOR è equivalente all'operazione di OR negata, quindi
X NOR Y = NOT(X OR Y)
Il risultato è 1 solo quando entrambi i valori di X e Y sono 0.

X Y X NOR Y
0 0 1
0 1 0
1 0 0
1 1 0

L'operazione di NAND corrisponde alla negazione dell'operazione AND, quindi fornisce come risultato 0 quando entrambi i valori di X e Y sono 0.

X Y X NAND Y
0 0 1
0 1 1
1 0 1
1 1 0

Gli operatori NOR e NAND sono universali, ovvero si possono utilizzare questi operatori per effettuare tutte le operazioni relativa agli altri operatori.

NOT

L'operazione NOT equivale all'operatore NAND di X con se stesso:
NOT X = X NAND X

X Y X NAND Y
0 0 1
0 1 1
1 0 1
1 1 0

Allo stesso modo si ottiene l'operatore NOT attraverso l'operatore NOR:
NOT X = X NOR X

X Y X NOR Y
0 0 1
0 1 0
1 0 0
1 1 0

OR

L'operazione OR può essere ottenuta dal teorema di De Morgan: infatti essendo
X NAND Y = NOT X OR NOT Y
allora (NOT X) NAND (NOT Y) = NOT (NOT X) OR NOT (NOT Y) = X OR Y
Sostituendo l'operatore NOT con l'operatore NAND allora si ha
(NOT X) NAND (NOT Y) = (X NAND X) NAND (Y NAND Y)

X Y NOT X NOT Y (NOT X) NAND (NOT Y)
0 0 1 1 0
0 1 1 0 1
1 0 0 1 1
1 1 0 0 1

L'operazione OR si ottiene da un operatore NOR la cui uscita viene negata da un invertitore NOT. Dati X e Y, si calcola X NOR Y e si inverte successivamente questo valore
NOT(X NOR Y) = X OR Y
Sostituendo l'operatore NOT con l'operatore NOR si ha
(X NOR Y) NOR (X NOR Y) = X OR Y

X Y X NOR Y NOT(X NOR Y)
0 0 1 0
0 1 0 1
1 0 0 1
1 1 0 1

AND

L'operazione AND può essere considerata come una operazione NAND negata dall'operatore NOT.
NOT(X NAND Y) = X AND Y
Si sostituisce l'operatore NOT con l'operatore NAND
NOT(X NAND Y) = (X NAND Y) NAND (X NAND Y)

X Y X NAND Y (X NAND Y) NAND (X NAND Y)
0 0 1 0
0 1 1 0
1 0 1 0
1 1 0 1

L'operazione AND si ottiene con il teorema di De Morgan seguente:
X NOR Y = (NOT X) AND (NOT Y)
allora si ha:
(NOT X) NOR (NOT Y) = (NOT (NOT X)) AND (NOT (NOT Y)) = X AND Y
Sostituendo l'operatore NOT con l'operatore NOR si ha
(NOT X) NOR (NOT Y) = (X NOR X) NOR (Y NOR Y)

X Y X NOR X Y NOR Y (X NOR X) NOR (Y NOR Y)
0 0 1 1 0
0 1 1 0 0
1 0 0 1 0
1 1 0 0 1
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License