Appunti Fondamenti di Informatica teoria - algebra di boole

Algebra di Boole

Algebra boolena – George Boole (1815-1864)

Ramo dell'algebra in cui le variabili possono assumere solamente i valori vero e falso (valori di verità); le operazioni fondamentali sono rappresentate da operatori logici. Le operazioni aritmetiche e logiche possono essere implementate attraverso l'algebra di Boole. L'algebra di Boole è definita su due elementi (vero | falso, 1 | 0);

• Costante booleana ::= 1 | 0;
• Operatore booleano ::= NOT | AND | OR;
• Una variabile booleana può assumere solo uno dei due valori 0 o 1;
• Tale teoria si presta bene quindi allo studio e progettazione dei circuiti elettronici.

Nota

Il simbolo "::=" significa "è definito / composto da". Il simbolo "|" significa "oppure".

Tabella della verità

Dato il numero finito di valori dell'insieme su cui sono definiti gli operatori booleani, è possibile per ciascuno di essi elencare in forma di tabella tutti i possibili casi che possono verificarsi. Tale tabella prende il nome di tabella di verità.

Operatori booleani: NOT

NOT (simbolo):

• Dato un valore booleano, il NOT restituisce il valore di verità opposto.

Operatori booleani: AND

AND (prodotto logico)

• Simbolo * oppure ·
• Commutativa – associativa – idempotenza

Proprietà

• x·y=y·x
• (x·(y·z))=((x·y)·z)
• x·x=x
• x·x=0

Dati due valori booleani, l'AND restituisce 1 se e solo se entrambi gli operandi sono 1, altrimenti il risultato è 0.

Operatori booleani: OR

OR (somma logica); simbolo +

• Commutativa – associativa – idempotenza

Proprietà

• x+y=y+x
• (x+(y+z))=((x+y)+z)
• x+x=x
• x+x=1

Dati due valori booleani, l'OR restituisce 1 se e solo se almeno uno degli operandi è 1, altrimenti il risultato è 0.

Teorema di dualità

Nell'algebra di Boole vale il teorema di dualità (reciprocità dei teoremi)

• che dice: Ogni identità e ogni proprietà resta valida se si scambiano tra loro gli elementi 0 e 1 e gli operatori AND e OR. Una espressione è duale di un'altra se ottenuta scambiando AND con OR e 0 con 1. Se un teorema è vero, anche il suo duale è vero.

Proprietà dell'algebra booleana

Operatori universali

NAND e NOR sono detti universali perché possono da soli realizzare i tre operatori fondamentali NOT, AND e OR.

Operatore OR-esclusivo (EXOR)

L'operatore EXclusive-OR o EXOR è anche detto sommatore modulo 2.

Algebra di Boole e reti logiche

Si presta bene quindi allo studio e progettazione dei circuiti elettronici digitali;