Corso di Execl 2000/2003 – L’Algebra Booleana

Sviluppata nel 1854 dal matematico inglese George Boole è un sistema algebrico costituito da:
–          Un insieme B di cardinalità pari a 2 o superiore su cui è definita una relazione transitiva, riflessiva e simmetrica, detta di uguaglianza

–          Due operatori binari, detti operatori booleani, chiamati somma logica (indicata con il simbolo +), prodotto logico (indicato con il simbolo ·) per cui valgono la proprietà distributiva e commutativa.

–          Due elementi rappresentati mediante i simboli 0 ed 1 (a cui però non è associato alcun significato numerico), detti elementi neutri, che godono delle seguenti proprietà:

Per il valore 0 detto elemento zero,

Per il valore 1 detto elemento unità,

–          Un operatore unario detto complementazione o negazione (indicato con il simbolo ¯ posto sopra l’elemento in esame) per cui vale la proprietà seguente:

, dove x è il complemento di y (e viceversa), percui applicando l’operatore a x otteniamo come risultato y.

Attualmente la quasi totalità dei dispositivi per l’elaborazione dell’informazione utilizza dispositivi che operano su dispositivi i quali possono assumere due distinti stati fisici distinti convenzionalmente chiamati on/off, vero/falso, 0/1 (senza nessun significato numerico), tale grandezza è detta binaria. Risulta facile costruire dispositivi a due stati, ed inoltre l’informazione può essere memorizzata in termini di 0 ed 1.

Ora definiamo l’insieme B dell’algebra booleana come B = {0,1} dove gli elementi dell’insieme rappresentano gli stati fisici costanti 0 ed 1, i quali coincidono con gli elementi neutri 0 ed 1 definiti nel sistema algebrico di Boole.

Gli operatori +, · e ¯ vengono rinominati rispettivamente AND (chiamata anche congiunzione[1] ed indicata con il simbolo ), OR (chiamata anche disgiunzione ed indicata con il simbolo ) e NOT, ad essi sono associate le seguenti tabelle operazionali che ne definiscono il significato :

AND (Congiunzione)

A B

A Ù B

 

A

B

A AND B

0 0

0

FALSO

FALSO

FALSO

0 1

0

FALSO

VERO

FALSO

1 0

0

VERO

FALSO

FALSO

1 1

1

VERO

VERO

VERO

Si può sintetizzare questa tabella asserendo che la congiunzione da come risultato 1 se e solo se tutte le variabili booleane coinvolte sono uguali ad 1.

OR (Disgiunzione)

A B

A Ú B

 

A

B

A OR B

0 0

0

FALSO

FALSO

FALSO

0 1

1

FALSO

VERO

VERO

1 0

1

VERO

FALSO

VERO

1 1

1

VERO

VERO

VERO

Anche in questo caso possiamo sintetizzare questa tabella asserendo che la disgiunzione da come risultato 0 se e solo se tutte le variabili booleane coinvolte sono uguali ad 0.

NOT (Negazione o Complementazione)

A -A   A NOT A
0 1 FALSO VERO
1 0 VERO FALSO

Proprietà degli operatori Logici

Gli operatori logici godono delle seguenti proprietà :

  Proprietà Commutativa

A + B = B + A                                   {A OR B  =  B OR A}

A ּ B =  B ּ A                                              {A AND B  =  B AND A}

  Proprietà Associativa

A + (B + C)  =  (A + B)  +  C           {A  OR (B OR C)  =  (A OR B) OR C}

A ּ (B ּ C)  =  (A ּ B)  ּ  C                       {A  AND (B AND C)  =  (A AND B) AND C}

  Proprietà Distributiva

A ּ (B + C)  =  (A ּ B) + (A ּ C)    {A  AND (B OR C)  =  (A OR B) AND (A OR C)}

A + (B ּ C)  =  (A + B) ּ (A + C)   {A  OR (B AND C)  =  (A AND B) OR (A AND C)}

Legge di Idempotenza

A + A  =  A                                        {A OR A = A}

A  ּ A  =  A                                       {A AND A = A}

Legge di Assorbimento

A + (A ּB) = A                                 {A OR (A AND B) = A}

A ּ (A + B) = A                                {A AND (A OR B)}

Legge di DeMorgan

(A + B) = A ּ B                                {NOT(A OR B)  =  (NOT A) AND (NOT B)}

(A ּ B) = A +ּ B                              {NOT(A AND B)  =  (NOT A) OR (NOT B)}

dove A, B, C sono variabili booleane binarie qualsiasi.

Definiamo ora una funzione booleana come

dove BN è uno spazio binario n-dimensionale formato da tutte le tuple composte da 0 ed 1 di lunghezza minore od uguale ad n.

Questa è solitamente composta da variabili booleane binarie correlate mediante gli operatori definiti precedentemente.

Torna alla lezione precendente Creare Formule o passa alla lezione successiva I Grafici. Per informazioni sul corso leggi l’introduzione 


[1] Il termine è usato prevalentemente in algebra proposizionale

Annunci

, , ,

  1. Lascia un commento

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger hanno fatto clic su Mi Piace per questo: