16/09/12  

1  

Prof.  Emanuele  Papo5o  

Algebra  di  BOOLE  �  L’algebra di Boole è un sistema algebrico sviluppato a metà

dell’‘800 dal matematico e logico inglese George Boole, per formalizzare la sillogistica aristotelica mediante una logica delle classi.  

�  Essa fu interpretata dallo stesso autore anche come una struttura di relazioni logiche tra proposizioni, mostrando così le affinità profonde esistenti tra la logica e l’usuale algebra.

16/09/12  

2  

Algebra  di  BOOLE  �  L’algebra di Boole è rimasta pressoché ignorata per oltre 80 anni,

cioè fino al 1937, quando lo scienziato americano Claude Elwood Shannon propose per primo di applicarla all’analisi e alla sintesi di circuiti a relè, che sono caratterizzati dai due stati di funzionamento “aperto” e “chiuso”.

�  Da allora l’algebra di Boole viene impiegata per la progettazione dei circuiti elettronici di tutti i computer.

Proposizioni  e  valori  di  verità  �  In  informaDca  spesso  si  ricorre  ai  principi  della  logica  degli  enunciaD,  una  branca  della  matemaDca  che  studia  l’algebra  delle  proposizioni  che  prende  il  nome  di  algebra  booleana  

�  Quando   esprimiamo   il   nostro   pensiero,   lo   facciamo   parlando,  pronunciando  dei  discorsi.  Ogni  discorso,   semplice  o   complesso,   si  compone  di  un  insieme  di  frasi,  le  proposizioni:  frase  o  espressione  autonoma  di  senso  compiuto  formata  almeno  da  un  sogge5o  e  da  un  predicato.  

�  L’enunciato  è  una  proposizione  della  quale  si  può  dire  con  certezza  se  è  vera  o  è  falsa  

�  Sono  esempi  di  proposizioni:  �   il  25  dicembre  è  Natale  �  la  Sicilia  è  un’isola  �  il  numero  7  è  divisibile  per  2  �  Milano  è  una  ci5à  del  Piemonte  

16/09/12  

3  

Proposizioni  e  valori  di  verità  �  La   verità   (V   oppure   1)   o   la   falsità   (F   oppure   0)   di   un  enunciato  sono  de5e  valori  di  verità.  

� Un   enunciato   può   essere   o   vero   o   falso,   ma   non  entrambe  le  cose  �  il  25  dicembre  è  Natale  �  la  Sicilia  è  un’isola  �  il  numero  7  è  divisibile  per  2  � Milano  è  una  ci5à  del  Piemonte  

 La  prima  e  la  seconda  sono  proposizioni  vere  (V  ),  la  terza  e  la  quarta  sono  false  (F  ).    

EnunciaD  semplici    � Noi   ci   occuperemo   solo   di   proposizioni   e   gli   argomenD  tra5aD  rientrano  nello  studio  della   logica  a  due  valori   (o  binaria…0   1   sempre   loro   ;-­‐))   )   proprio   perché,   come  vedremo,   ogni   proposizione   sarà   vera   o   falsa   e   il  verificarsi  di  uno  dei  due  casi  esclude  l’altro.  

�  Indicheremo   le   proposizioni   con   le5ere   minuscole  dell’alfabeto,  per  esempio:  p,  q,  r,  …  

16/09/12  

4  

EnunciaD  semplici  �  per  esempio:  

p:    il  25  dicembre  è  Natale  q:  il  numero  7  è  divisibile  per  2  

   �  Se  una  proposizione,  come  la  p,  è  vera  scriveremo:  p=V  

�  se  è  falsa,  come  la  q,  scriveremo:    q=F    �  è  possibile  anche   idenDficare   il  valore  V  con   la  cifra  1  e   il  valore  F  con   la  

cifra  0;      in  tal  modo,  per  le  proposizioni  precedenD  potremo  scrivere:  

 p=1                q=0  

EnunciaD  composD  � Alcuni  enunciaD  posso  essere  composB,  cioè  formaD  da  so5oenunciaD  collegaD  tra  loro  dai  conneCvi:  Operazioni  logiche  

ConneCvo  logico  

ConneCvo  Lingua  italiana  

ConneCvo  Lingua  inglese  

Negazione   ¬   non   not  

Congiunzione   e   and  

Disgiunzione   o   Or  

Disgiunzione  esclusiva   xor   O  esclusivo   xor  

∧

∨

16/09/12  

5  

EnunciaD  composD  �  ecco  alcuni  esempi:  

piove  e  il  mare  è  calmo  non  piove  e  il  mare  è  calmo  piove  e  il  mare  non  è  calmo  

non  piove  e  il  mare  non  è  calmo  piove  o  il  mare  è  calmo  

EnunciaD  composD  �  Consideriamo  ora  una  delle  proposizioni  precedenD:  

r  =  p  and  q  r  =  piove  e  il  mare  è  calmo  

�  Il  problema  che  ci  poniamo  è  stabilire  quando  r  è  vera  o  falsa,    

 �  Per  dare  una  risposta  occorre:  

�  conoscere  il  valore  di  verità  delle  proposizioni  semplici  p,  q  �  conoscere  il  significato  della  parola  “and”  che  collega  p  con  q.  

16/09/12  

6  

Tabella  di  verità  and  p q p and q V V V V F F F V F F F F

La   congiunzione   di   due   proposizioni   è  vera   solo   quando   le   due  proposizioni  componenB  sono  entrambe  vere    E’  falsa  in  tud  gli  altri  casi  

Tabella  di  verità  and  p q p and q V V V V F F F V F F F F

Si  osservi  che  solo  il  primo  enunciato  p  and  q  è  VERO  gli  altri  sono  falsi    

p=  14  è  divisibile  per  2                                                                  q=  2+2=4  p=  14  è  divisibile  per  2                                                                  q=  2+2=5  p=  14  è  divisibile  per  3                                                                  q=  2+2=4  p=  14  è  divisibile  per  3                                                                  q=  2+2=5  

16/09/12  

7  

Tabella  di  verità  or  p q p or q V V V V F V F V V F F F

La  disgiunzione  di  due  proposizioni  è  vera  solo  quando  almeno  una  delle    due  proposizioni  componenB  è  vera    E’  falsa  quando  entrambe  le  proposizioni  componenD  sono  false  

Tabella  di  verità  or  p q p or q V V V V F V F V V F F F

Si  osservi  che  solo  l’ulBmo  enunciato  p  or  q  è  FALSO  gli  altri  sono  veri    

p=  14  è  divisibile  per  2                                                                  q=  2+2=4  p=  14  è  divisibile  per  2                                                                  q=  2+2=5  p=  14  è  divisibile  per  3                                                                  q=  2+2=4  p=  14  è  divisibile  per  3                                                                  q=  2+2=5  

16/09/12  

8  

Tabella  di  verità  not  p not p V F F V

Data  una  proposizione  p,  preme5endo  il  connedvo  “not”,  si  odene  :    not  p  significa  inverDre  il  valore  di  verità  di  p:        

se  p  è  vera  not  p  è  falsa,  se  p  è  falsa  not  p  è  vera      Esempio:  p:  “6  è  divisibile  per  3”                                          (  p  =  V)  not  p:  “6  non  è  divisibile  per  3”                (not  p  =  F)  

Tabella  di  verità  xor  p q p xor q V V F V F V F V V F F F

Si  osservi  che  quando  le  proposizioni  p  xor  q  sono  entrambe  vere  o  false  l’enunciato  risulterà  FALSO  

 p=  14  è  divisibile  per  2                                                                  q=  2+2=4  p=  14  è  divisibile  per  2                                                                  q=  2+2=5  p=  14  è  divisibile  per  3                                                                  q=  2+2=4  p=  14  è  divisibile  per  3                                                                  q=  2+2=5  

16/09/12  

9  

Forme  enunciaDve  �  not  (p  and  not  q)  �   Nella  costruzione  della  tabella  dobbiamo  sempre  tener  presente:  �  Nelle  prime  colonne  me5ere  tu5e  le  combinazioni  dei  valori  che  possono  assumere  le  variabili    

�  Se  ho  n  variabili:  Righe  della  tabella  =  2  n  

�  Ordine  esecuzione  operazioni:  not,  and,  or  

p   q   not  q   p  and  not  q   not  (p  and  not  q)  

V   V   F   F   V  

V   F   V   V   F  

F   V   F   F   V  

F   F   V   F   V  

not  (p  and  not  q)  and  (p  or  r)  p   q   r   not  q   p  and  not  q   not  (p  and  not  q)     p  or  r   not  (p  and  not  q)  

and  (p  or  r)  

V   V   V   F   F   V   V   V  

V   V   F   F   F   V   V   V  

V   F   V   V   V   F   V   F  

V   F   F   V   V   F   V   F  

F   V   V   F   F   V   V   V  

F   V   F   F   F   V   F   F  

F   F   V   V   F   V   V   V  

F   F   F   V   F   V   F   F  

16/09/12  

10  

Esercizi  (p  and  q)  or  (p  or  q)  

(p  or  q)  and  r  (p  or  q)  and  (p  or  z)  not  (  (p  or  q)  and  r)  

   

Proprietà  dei  connedvi  logici  � Analogamente  alle  operazioni  aritmeDche,  anche  i  connedvi  logici  godono  di  alcune  proprietà  e  precisamente:    

�  commutaBva:    A  AND  B  =  B  AND  A  A  OR  B  =  B  OR  A  

�  associaBva:  A  AND  B  AND  C  =  (A  AND  B)  AND  C  =  A  AND  (B  AND  C)  A  OR  B  OR  C  =  (A  OR  B)  OR  C  =  A  OR  (B  AND  C)  

16/09/12  

11  

Proprietà  dei  connedvi  logici  �  idempotenza:  A  AND  A  =A  A  OR  A  =A    

�  distribuBva:  dell'OR  rispe5o  all'AND  (A  AND  B)  OR  C  =  (A  OR  C)  AND  (B  OR  C)    dell'AND  rispe5o  all'OR  (A  OR  B)  AND  C  =  (A  AND  C)  OR  (B  AND  C)  

�  doppia  negazione  (involuzione):  NOT  (NOT  A)  =  A  

Proprietà  dei  connedvi  logici  � Oltre  alle  proprietà  appena  enunciate  che  possono  essere  facilmente  dimostrate  uDlizzando  le  tavole  di  verità,  rivestono  grande  importanza  altre  due  proprietà  meglio  note  come  le  leggi  di  De  Morgan:    Prima  legge:    NOT(A  OR  B)=  (NOT  A)  AND  (NOT  B)  Seconda  legge:    NOT  (A  AND  B)  =  (NOT  A)  OR  (NOT  B)  

16/09/12  

12  

Esercizio  �  Verifica  alcune  proprietà  dei  connedvi  logici  creando  le  relaDve  tavole  di  verità