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

È 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 complementari:

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 (assorbimento assoluto)

   

A A A; A A A (idempotenza di OR e AND)

   

A A 1; A A 0 (tautologia e contraddizione)



A A (doppia negazione)

Proprietà:

+ = + × = ×

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 duale)

ë û ë û

( )

+ × = × + =

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; ;