Introduzione alla logica booleana

Introduzione alla logica booleana

Autore: Antonello Urso (01/07/11)

www.pianetagalileo.eu - (ultimo aggiornamento: 08/07/15) – (SS)

A. Urso – Introduzione alla logica booleana

Introduzione

E' facile accorgersi del fatto che tale argomento destinato in genere a studenti delle scuola

superiore viene purtroppo trattato da molti libri di matematica in modo troppo rigido e assiomatico

per poter apprezzare la sua straordinaria importanza pratica; viceversa nei testi di elettronica digitale

viene trattato in modo troppo tecnico per poter apprezzare tutti gli interessanti risvolti matematici.

Questa trattazione viene svolta tenendo in debito conto le varie esigenze al fine di poter fare

finalmente chiarezza su un tema che ha rivoluzionato il modo di concepire la matematica.

L’algebra booleana è stata sviluppata da George Boole nel 1854, ed è diventata famosa intorno al

1938 grazie a Claude Shannon poiché permette l’analisi delle reti di commutazione (i cui soli stati

possono essere 1 e 0) ed ha lo scopo di verificare la correttezza o meno di un ragionamento, per far

questo si trasformano le frasi di tutto il discorso in formule matematiche che entreranno in un

sistema di calcolo dal quale è possibile stabilire se esse sono corrette o no.

I principi di questa algebra binaria sono strettamente legati a quelli della teoria degli insiemi dalla

quale discende e che costituiscono quindi un prerequisito per la sua comprensione.

Definizioni importanti:

Si dice proposizione un enunciato per il quale è possibile stabilire se è vero o falso.

➢ Si dice tautologia un enunciato sempre vero, e contraddizione un enunciato sempre falso.

➢ Si dicono connettivi logici delle operazioni che possono legare una o più proposizioni.

➢

Una proposizione ammette tre principi fondamentali:

Principio di identità : Ogni proposizione deve mantenere

sempre lo stesso significato durante il discorso.

Principio di non contraddizione: Una proposizione non

può essere contemporaneamente vera e falsa.

Principio del terzo escluso: Una proposizione può essere

vera o falsa e non esiste una terza possibilità.

Collegamenti con la teoria degli insiemi  



U 1

Se consideriamo un insieme universo composto da un solo elemento: possiamo avere solo

  

1 e

i seguenti sottoinsiemi: .

Se ora prendiamo tutte le combinazioni possibili di questi due sottoinsiemi rispetto all'operazione

di unione e di intersezione avremo:

Per l'intersezione:

Per l' unione : Per i complement

ari :

I

 Æ Æ = Æ  

     

1

{ }

    I

Æ = Æ

 1

   

1 1 (1)

  1

{ }

    I

 Æ = Æ

1

 

1 1

      { } { } { }

I

 =

 1 1 1

1 1 1

Riscriviamo adesso tutto semplificando la notazione e facendo le seguenti sostituzioni: 2

A. Urso – Introduzione alla logica booleana

 

     

(OR o ) ; (AND o ) (2)

    

1 1 ; 0



dove il segno “+” e il segno “ “ indicano rispettivamente una somma logica e un prodotto logico e

non aritmetico . Avremo quindi nell'algebra di Boole due soli “numeri” 1 e 0 , o più esattamente

due stati logici visto che non si devono intendere in senso aritmetico e si potrebbero anche sostituire

con due simboli contrapposti qualunque, per esempio: V (vero) e F (falso).

 

Otteniamo così anche il connettivo NOT: dove la parola “complementare”, della

1 0 ; 0 1

teoria degli insiemi, nell'algebra di Boole verrà sostituita con la parola “negato” e si dirà: 1 negato è

uguale a 0 , e 0 negato è uguale a 1. Similmente si potrà dire che il negato di vero è falso e il negato

di falso è vero.

Facendo le sostituzioni (2) nella (1) otteniamo le cosiddette tabelle della verità o tabelle logiche.

Le prime due colonne si chiamano ingressi e per 2 ingressi A e B abbiamo un totale di 4

combinazioni possibili. La terza colonna si chiama uscita e deriva dal calcolo della formula in

esame secondo i vari casi all'ingresso.

Connettivo OR:

Si può dire che se A o B (cioè l'uno o l'altro) sono allo stato 1 allora l'uscita sarà pure allo stato 1.

Notiamo l'uso della congiunzione alternativa inclusiva “o” che è interpretabile in questo caso come

 

A B U

una somma logica. Per esempio dire: almeno Aldo o Bruno è italiano si traduce in ,

tenendo conto dei seguenti stati: 

A B A B

0 0 0

0 1 1

1 0 1

1 1 1

  

1 se Aldo è italiano 1 se Bruno è italiano 1 se la frase è vera

  

A B U

  

0 se Aldo non è italiano 0 se Bruno non è italiano 0 se la frase è falsa

  

Un altro esempio stavolta con l'uso dell'uscita predefinita: è sempre vero (tautologia cioè 1) che una

proposizione (A) può essere sempre vera o falsa, si traduce in:  

A A 1

Connettivo AND:

Si può dire che se A e B (cioè entrambi) sono allo stato 1 allora l'uscita sarà pure allo stato 1.

Notiamo l'uso della congiunzione copulativa “e” che è interpretabile come prodotto logico. Per

 

A B U

esempio: dire Aldo e Bruno sono italiani si traduce in .

A B A B

0 0 0

0 1 0

1 0 0

1 1 1

Un altro esempio con l'uso dell'uscita predefinita: è sempre falso (contraddizione cioè 0) che una

 

proposizione (A) può essere contemporaneamente vera e falsa, si traduce in .

A A 0 3

A. Urso – Introduzione alla logica booleana

Regole e proprietà algebriche:

Regole :

   

A 0 A ; A 1 A (elemento neutro della somma e del prodotto)

   

A 1 1 ; A 0 0 (assorbime

nto assoluto)

   

A A A ; A A A (idempoten

za di OR e AND)

   

A A 1 ; A A 0 (tautologi

a e contraddiz

ione)



A A (doppia negazione)

Proprieta:

+ = + × = ×

A B B A ; A B B A (commutativa)

( ) ( ) ( ) ( )

+ + = + × × = × ×

A B C A B +C ; A B C A B C (associativa)

( ) ( ) ( )

× + = × + × + × = + × +

A B C A B A C ; A B C A B A C (distributiva)

Teoremi:

+ = × × = +

A B A B ; A B A B (De Morgan)

( )

( )

+ × = × +

f A ; B ; C ... ; ; f A ; B ; C ... ; ; (De Morgan generalizzato)

( ) ( ) ( )

= × + ×

f A ; B A f 1 ; B A f 0 ; B (Shannon)

( ) ( ) ( )

é ù

= + × +

é ù

f A ; B A f 0 ; B A f 1 ; B (Shannon d uale)

ë û ë û

( )

+ × = × + =

A A B A ; A A B A (Assorbimento di B )

( )

+ × = + × + = ×

A A B A B ; A A B A B (Assorbimento di A )

Essi derivano come si può facilmente riconoscere direttamente dalla teoria degli insiemi, una volta

   

e

scambiati , rispettivamente con: , e l’insieme universo e l’insieme vuoto

" " e " "

rispettivamente con 1 e 0. Di notevole importanza è il seguente:

Principio di dualità:

Da un identità si può ottenere una nuova identità detta duale della precedente, scambiando gli

operatori AND e OR , e scambiando, ove presenti, le costanti 0 e 1.

Tale principio oltre che a fornire un importante contributo teorico e anche importante per la

semplificazione delle funzioni algebriche. Facciamo qualche esempio sull'uso della tabella della

verità:

Esempio 1 - Dimostrazione del teorema di De Morgan:   

A B A B

A B 

 A B

A B

0 0 1 1

0 1 0 0

1 0 0 0

1 1 0 0

Avremo in questo caso 2 ingressi e 2 uscite (primo e secondo membro).

Ci sono solo quattro casi, dalla tabella si può vedere dopo avere effettuato i calcoli che la terza

colonna è uguale alla quarta; quindi il primo membro della relazione è uguale al secondo membro. 4

A. Urso – Introduzione alla logica booleana

Facciamo adesso vedere il modo di procedere per la prima riga riportando di seguito

rispettivamente la prima e la seconda uscita che dovranno essere uguali.

Per l'ordine delle operazioni valgono le ben conosciute convenzioni algebriche: dopo lo

svolgimento delle singole negazioni si passa prima al prodotto e poi alla somma, inoltre per

semplicità si potrà omettere il simbolo del prodotto nelle formule.

      

Per la prima riga: 0 0 0 1 ; 0 0 1 1 1

      

Per la seconda riga: 0 1 1 0 ; 0 1 1 0 0

      

Per la terza riga: 1 0 1 0 ; 1 0 0 1 0

      

Per la quarta riga: come volevasi dimostrare.

1 1 1 0 ; 1 1 0 0 0

Per esempio per questo teorema la frase: non è vero che Giulia ama Aldo o Bruno ( ) si



A B



traduce ugualmente in: Giulia non ama Aldo e non ama Bruno ( ).

A B

Verifichiamo adesso il duale del teorema di De Morgan:   

A B A B

A B 

A B

A B

0 0 1 1

0 1 1 1

1 0 1 1

1 1 0 0

      

Per la prima riga: 0 0 0 1 ; 0 0 1 1 1

      

Per la seconda riga: 0 1 0 1 ; 0 1 1 0 1

      

Per la terza riga: 1 0 0 1 ; 1 0 0 1 1

      

Per la quarta riga: 1 1 1 0 ; 1 1 0 0 0

Per esempio per questo teorema la frase: “non è vero che Giulia ama Aldo e Bruno” ( ) è

A B



equivalente a: “Giulia non ama Aldo o non ama Bruno” ( ).

A B

Un altra dimostrazione del teorema di De Morgan si può ottenere utilizzando il teorema di Shannon:

                   

f A ; B A B A 1 B A 0 B A 1 A B A 0 A B A B

      

   

                

f A ; B A B A 0 B A 1 B A 1 A B 1 A B A B

Per il principio di dualità se una relazione è verificata anche la sua duale sarà verificata. Inoltre se

una relazione è verificata in campo logico allora sarà verificata anche nel suo corrispettivo

insiemistico e viceversa. La dimostrazione di tale principio si basa sul teorema di De Morgan.

Supponiamo di avere una relazione logica (per semplicità in due variabili e i due stati logici, ma si

può facilmente estendere anche ad n variabili) sempre valida del tipo:

( ) ( ) neghiamo adesso primo e secondo membro e

+ × = + ×

f A ; B ; 1 ; 0 ; ; g A ; B ; 1 ; 0 ; ;

applichiamo il teorema di De Morgan generalizzato:

( ) ( )

+ × = + ×

f A ; B ; 1 ; 0 ; ; g A ; B ; 1 ; 0 ; ;

( ) ( ) finora abbiamo ottenuto solo il negato della

× = ×

f A ; B ; 0 ; 1 ; ; + g A ; B ; 0 ; 1 ; ; +

relazione di partenza, ma se sostituiamo otteniamo:

A con A e B con B

( ) ( ) che è proprio la duale della relazione di partenza.

× = ×

f A ; B ; 0 ; 1 ; ; + g A ; B ; 0 ; 1 ; ; + 5

A. Urso – Introduzione alla logica booleana

 

Esempio 2a – dimostrazione del teorema di assorbimento di B: A AB A



A B A AB

0 0 0

0 1 0

1 0 1

1 1 1     

0 0 0 0 0 0

Procediamo adesso con i calcoli logici per le varie righe: Per la prima riga:

         

0 0 1 0 0 0 1 1 0 1 0 1

Per la seconda riga: . Per la terza riga: .

    

Per la quarta riga: 1 1 1 1 1 1

Notiamo che la prima e la terza colonna sono uguali, quindi la relazione è verificata.

Dimostriamo adesso la stessa relazione per via algebrica:

 

     

A AB A 1 B A notando che per qualunque valore di B.

1 B 1

 

 

A A B A

Naturalmente anche la relazione duale è verificata, infatti:

 



A B A A B

0 0 0

0 1 0

1 0 1

1 1 1

 

    

0 0 0 0 0 0

Per la prima riga:  

    

0 0 1 0 1 0

Per la seconda riga:

 

    

1 1 0 1 1 1

Per la terza riga:  

    

1 1 1 1 1 1

Per la quarta riga:    

       

Dimostrazione per via algebrica: A A B AA AB A AB A 1 B A

Esempio 2b - dimostrare algebricamente il teorema di assorbimento di :

A

 

 

               , e per la duale:

A A B A 1 B A B A AB A B A B A A A B 1 A B

 

      , come volevasi dimostrare.

A A B A A AB 0 AB AB

Esempio 3 – dimostrazione della proprietà distributiva del prodotto rispetto alla somma (PS):

 

     

A B C A B A C

In questo caso avremo una tabella con 3 ingressi, quindi 8 casi possibili, e 2 uscite.

 

 

A B C   

A B C A B A C

0 0 0 0 0

0 0 1 0 0

0 1 0 0 0

0 1 1 0 0

1 0 0 0 0

1 0 1 1 1

1 1 0 1 1

1 1 1 1 1 6

A. Urso – Introduzione alla logica booleana

 

          

0 0 0 0 0 0 ; 0 0 0 0 0 0 0

Per la prima riga:  

          

0 0 1 0 1 0 ; 0 0 0 1 0 0 0

Per la seconda riga:  

          

0 1 0 0 1 0 ; 0 1 0 0 0 0 0

Per la terza riga:  