Post on 18-Jun-2020
transcript
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à