Riassunto esame Informatica, Prof. Leporini Roberto, libro consigliato Laboratorio di informatica: Excel, Vittorio Moriggia, Sebastiano Vitali

Informatica: Algebra booleana

George Boole e l'algebra booleana

George Boole (1815-1864) era un matematico. Obiettivo: io ho una formula composta molto grande o un libro di testo, voglio sapere se questo libro di testo è vero o falso, cioè se dice il vero o dice il falso, e avendo tutte le informazioni su quelle che sono le sue componenti. Dieci anni prima di morire, quindi nel 1854, ha pubblicato un articolo sui fondamenti dal punto di vista della logica.

Obiettivi dell'algebra booleana

• Capacità di estrarre tutte e sole le informazioni utili a risolvere un dato problema. L'input sono tutte le informazioni che ho, l'output è la risoluzione del nostro problema. Dalle unità di misura posso sapere quale algoritmo devo utilizzare.
• Essere in grado di formalizzare e risolvere un problema analizzando tutti i casi possibili in modo esaustivo.
• Saper ricavare il valore di verità delle formule (atomiche e molecolari) a partire da valori di verità noti.

Assiomi dell'algebra booleana

<B,+,•,-,0,1>

• Consistenza 0, 1
• Chiusura ∀, +
• Identità: ∀ ∈ , + 0 =
• Inversione ∀, + (- ) = 1
• Commutatività ∀, ∈ , + = +
• Distributività: , , ∈ , + ( • ) = ( + ) • ( + )

Principio di dualità

Se T è un teorema dell'algebra booleana, allora lo è anche il duale ottenuto da T rimpiazzando + con •, 0 con 1 e viceversa.

Proprietà degli operatori

• Associativa: + ( + ) = ( + ) +, • ( • ) = ( • ) •
• Idempotenza: + = , • =
• Involuzione: -- =
• Assorbimento: + ( • ) = , • ( + ) =

Logica classica del primo ordine

In filosofia, lo studio delle leggi e delle funzioni che caratterizzano la struttura del pensiero in sé (logica formale), oppure dei procedimenti seguiti dal pensiero in riferimento ai diversi contenuti cui può applicarsi (logica materiale).

Logica matematica (o simbolica): lo studio della formalizzazione dei procedimenti e delle operazioni logiche in linguaggio matematico.

Formula dell'algebra booleana

È un'espressione ben formata del linguaggio alla quale può essere attribuito un valore di verità: vero o falso. Esempio: oggi c'è il sole → è scritto secondo le regole della grammatica italiana quindi il primo requisito è soddisfatto (ossia espressione ben formata del linguaggio), il valore di verità deve essere sempre lo stesso, quindi in questo caso non è vero che c'è il sole perché magari domani piove devo precisare. In questo caso questa frase non è una formula. Le frasi che riguardano il futuro non fanno parte dell'algebra booleana.

Funzioni e proposizioni

Le funzioni possono contenere delle variabili, e per ogni variabile bisogna indicare il dominio di definizione della stessa, esempio: x è un numero pari, devo definire il dominio, sono i numeri interi positivi incluso lo 0, a questo punto assegnando a x qualsiasi valore, come ad esempio 3, posso valutare la formula → x=3 sarà falsa.

Se non contengono delle variabili si chiamano proposizioni o asserzioni. Se non contengono dei connettivi si chiamano atomiche. Se contengono connettivi si chiamano composte o molecolari. Si utilizzano le lettere in maiuscolo per rappresentare le formule dell'algebra booleana.

Esempi di proposizioni atomiche

A = "la frase successiva è falsa" → è una proposizione ed è atomica

B = "la frase precedente è vera" → è una proposizione atomica

Le possibili combinazioni sono 2, perché due sono i valori di verità (vero o falso), elevato al numero di lettere presenti, che sono 2 (A e B). → 2² = 4 → ci sono 4 possibili combinazioni.

La prima combinazione non può esistere, elimino la prima riga. La seconda combinazione non può esistere, elimino la seconda riga. Non va bene neanche la terza combinazione e neanche la quarta non posso assegnare un valore di verità a tutte le formule quando c'è questa circolarità.

Connettivi logici

Proposizioni atomiche → Valori di verità a cui possono essere espresse in due modi:

• Vero → V, True, T, 1
• Falso → F, False, 0

I connettivi sono

• Negazione: NOT, NON, - NOT A
• Congiunzione: A AND B, AND, E, ∧, •, ∩
• Disgiunzione inclusiva: A OR B, OR, O, ∨, +, ∪
• Disgiunzione esclusiva: A XOR B, XOR, ⊕
• Implicazione: IF..THEN, SE..ALLORA, IF A THEN B →
• Coimplicazione: A IFF B, IFF, SSE, ≡

Esempio di uso dei connettivi

Bergamo è una città e i Caniana erano intarsiatori, scultori e architetti tra i più celebri nell'Italia settentrionale. A and B and C → Bergamo è una città → diventa una proposizione atomica. Diventa AE → AND i Caniana erano intarsiatori, scultori → diventa BE → AND architetti tra i più celebri nell’Italia settentrionale → diventa C. “Partecipate al corso!” è una proposizione atomica? NO, perché devo poterle assegnare un valore di verità.

I connettivi che utilizziamo sono delle operazioni vero-funzionali, cioè significa che l’applicazione delle operazioni modifica la falsità o la verità delle proposizioni coinvolte. Ogni operazione è una funzione che può essere rappresentata mediante una tabella. Una formula composta che viene interpretata sempre come vera viene detta tautologia (dal greco, che dice lo stesso). Ad esempio: A , (A B) ≡ ( ¬B ¬A).

Una formula sempre falsa invece è detta contraddizione.

Esempi di proposizioni e non-proposizioni

Sono proposizioni:

1. "A Bergamo l’1/1/14 abitano solo due persone" → falsa perché il numero di abitanti di Bergamo a quella data è diverso da due. (atomica)
2. "A Bergamo l’1/1/14 abitano x persone" → determinato x, è vera se le persone nella data indicata è x e falsa se in quella data il numero di persone è diverso da x. (atomica)
3. "Il numero 5 è dispari e 2 è primo" → vera perché entrambe le proposizioni sono vere in base alle definizioni di numero dispari e di numero primo. (2 prep atomiche)
4. "Il numero 6 è pari o 4 è primo" → vera perché, anche se la seconda è falsa, la prima proposizione è vera. (2 prep atomiche)
5. "5+4*2=12" → falsa. (atomica), mentre "2x -3=-1" → vera se x=1 e falsa altrimenti. (atomica)
6. "L'azienda x produce scarpe" → determinato x, è o vera o falsa quindi il valore di verità dipende da quale azienda si considera ma una volta fissata l’azienda. (atomica)

Non sono proposizioni:

1. "A Bergamo oggi abitano 115.000 persone" → non ha un valore di verità perché può essere o vera o falsa a seconda del giorno in cui si legge.
2. "Viva la nazionale italiana!" → è una esclamazione, quindi, non ha un valore di verità.
3. "Oggi piove" → non ha un valore di verità; infatti, la sua verità dipende dal momento in cui viene espressa.
4. "Il mondo è cattivo" → non ha un valore di verità; infatti esprime un'opinione soggettiva.
5. "5+4*2" → non è una proposizione perché non ha un valore di verità; infatti è un’espressione di cui non si verifica il valore.

Esercizio: Tre esploratori

Tre esploratori vengono catturati. Il capo tribù decide di graziarli se si dimostrano intelligenti. Mostra loro 3 cappelli neri e 2 bianchi, quindi li benda e mette su ciascuno un cappello. Chiede poi a ogni esploratore il colore del cappello che ha in testa. L’esploratore può rispondere guardando solo il colore del cappello dei suoi compagni tranne l’ultimo che rimane bendato. Come possono salvarsi?

Si risolve applicando l’algebra booleana. I cappelli sono bianco o nero due possibilità. Le possibili combinazioni sono 2³ = 8.

A = “il colore del cappello del primo esploratore è nero”

B = “il colore del cappello del secondo esploratore è nero”

C = “il colore del cappello del terzo esploratore è nero”

1 = vero (è come se rappresentasse il nero), 0 = falso (è come se rappresentasse il bianco)

Eliminare la prima riga perché non possono avere tutti e tre il cappello bianco. → diventano 7 i casi possibili. All’inizio, prima di togliere la benda, al primo converrà dire di avere il cappello nero perché ha più possibilità, ha 4 possibilità su 7 → ha il 57,14% che sia nero, mentre ha il 42,86% che sia bianco. Al primo esploratore viene tolta la benda. Riga 5: gli altri due esploratori hanno il cappello bianco → lui con certezza può dire di avere il cappello nero → vengono liberati. Nascondo il caso favorevole → nascondo la riga 5 → i casi possibili diventano 6. Adesso la probabilità a posteriori diventa 50% per il cappello nero e 50% per quello bianco. → non risponde → Nascondi colonna A. Alla seconda esploratrice, prima che le venga tolta la benda, le conviene rispondere nero perché ha il 66,6% di averlo. → quando le viene tolta la benda, se vede che l’ultimo esploratore ha il cappello bianco, lei con certezza può dire di avere il cappello nero (casi che sono nella riga 3 e riga 7) → vengono liberati. Nascondo i casi favorevoli → nascondo le righe 3 e 7 → i casi possibili diventano 4. Adesso la probabilità a posteriori diventa 50% per il cappello nero e 50% per quello bianco. → non risponde → Nascondi colonna B. → Il terzo esploratore non ha nessuna informazione, però sono rimasti solo 4 possibili casi in cui il cappello è comunque nero → vengono liberati tutti. → scopro tutte le celle. È una tautologia perché è sempre vero.

Esercizio: Dichiarazioni di Alice, Bianca, Camilla e Davide

Alice dice: “Bianca ha copiato”

Bianca dice: “Camilla ha copiato”

Camilla dice: “Non ho copiato”

Davide dice: “Non ho copiato”

Uno solo dice la verità. Uno solo ha copiato.

Il primo scenario non è possibile, quindi elimino la prima combinazione. Anche la seconda non va bene. La terza va bene → Camilla non ha copiato, ma ha copiato Davide. L'ultima non va bene. La tabella diventa:

Esercizio: Interruttori e lampadina

Ci troviamo di fronte a una stanza chiusa ermeticamente e a fianco 4 interruttori. Uno solo di questi accende la luce della stanza. Abbiamo la possibilità di entrare una sola volta per stabilire l'interruttore funzionante. Come è possibile individuare l'interruttore?

A: “il primo interruttore accende la lampadina”

B: “il secondo interruttore accende la lampadina”

C: “il terzo interruttore accende la lampadina”

D: “il quarto interruttore accende la lampadina”

E: “la lampadina è accesa”

F: “la lampadina è spenta”

Le combinazioni sono 2⁴ però ne rimangono solo 4 perché solo un interruttore accende la lampadina.

Operatori logici

Operatore NOT (Negazione)

Tavola di verità

Operatore AND (Congiunzione)

Tavola di verità

A AND B = A1*B1 = MIN(A1;B1) → è un altro modo per scrivere A and B

Operatore OR (Disgiunzione)

Tavola di verità

A OR B = A1;B1 = MAX(A1;B1) - 5 + 2 • 3 → faccio prima il • e poi il +. Con le parentesi posso cambiare l’ordine delle operazioni. OR corrisponde all’unione.

Esercizi "On The Fly"

Se A = Vero, B = Falso, C = Vero, qual è il valore di verità delle seguenti espressioni?

• A or (not B and C) → la formula è vera. Prima faccio il not di B; B diventa vera, poi faccio AND e poi OR. C e A sono vere; la formula è vera.
• A and Falso → la formula è falsa
• B or Vero → la formula è vera
• A and B and C → la formula è falsa

Esercitazione sulle tavole di verità

• A OR 1 = MAX(A1;1)

A	A OR 1
0	1
1	1

• A AND 1 = A1*1

A	A AND 1
0	0
1	1

• NOT (NOT A) = 1-(1-A1)

A	NOT(NOT A)
0	0
1	1

• NOT (A AND B) = 1-(A1*B1)

Al posto del not metto il - e al posto di and metto * -(A*B)

A	B	NOT (A AND B)
0	0	1
0	1	1
1	0	1
1	1	0

• NOT A OR NOT B -A*-B = MAX(1-A1;1-B1)

A	B	(NOT A) OR (NOT B)
0	0	1
0	1	1
1	0	1
1	1	0

• NOT (A OR B) = 1-MAX(A1;B1)

A	B	NOT (A OR B)
0	0	1
0	1	0
1	0	0
1	1	0

• NOT A AND NOT B = (1-A1)*(1-B1)

A	B	(NOT A) AND (NOT B)
0	0	1
0	1	0
1	0	0
1	1	0

Priorità dei connettivi

Imponiamo le seguenti priorità ai connettivi dalla più alta alla più bassa:

• 1. not
• 2. and
• 3. or
• 4. if..then, iff

Un esempio di cancellazione delle parentesi è dato dalla seguente formula ((if (A or (not B)) then C) iff A) che può essere scritta senza parentesi.

Leggi di De Morgan

NOT (A AND B) = NOT A OR NOT B

not = - and = *

Il not cambia sia A e B, che diventano not A e not B, sia l’AND che diventa OR diventa NOT A OR NOT B

NOT (A OR B) = (NOT A) AND (NOT B)

Le leggi di De Morgan sono utili per negare espressioni complesse: not ( x>5 or y<3 ) = not (x>5) and not (y<3). not (x>5 or y<3) → not di x>5 sarà uguale a x≤5 mentre il not di y<3 è y≥3 se faccio il sistema tra x≤5 e y≥3 ottengo l’insieme nullo.

Le leggi di De Morgan mostrano che i tre operatori AND OR NOT non sono indipendenti. È possibile esprimere AND tramite OR e NOT: A and B = not not (A and B) = not ((not A) or (not B)). È possibile esprimere OR tramite AND e NOT: A or B = not not (A or B) = not ((not A) and (not B)).

Esercizi di algebra booleana

• (A+ -A)*B = MAX(A1;1-A1)*B1
• A*-B+C = MAX(A1*(1-B1);C1)
• A+B*(C*-C) = MAX(A1;B1*C1*(1-C1))
• A*B+C*-C = MAX(A1*B1;C1*(1-C1))

Operatore XOR

Il simbolo è ⊕. Con lo XOR la formula è vera se e solo se una delle due formule componenti è vera.

Tavola di verità

A XOR B = RESTO(A1+B1;2). Lo XOR si può anche ricavare usando and, not e or: A AND NOT B OR NOT A AND B = MAX(A1*(1-B1);(1-A1)*B1).

Esercizi sull'operatore XOR

Se A = Vero, B = Vero, C = Falso, qual è il valore di verità di:

• A xor (B or C) → falso
• A xor B xor C → falso
• (A and B) xor C → vero

Costruire la tavola di verità di:

• A xor B xor A = RESTO(RESTO(A1+B1;2)+A1;2) → dipende solo da B, è come se i due A si elidessero.
• not (A xor B) = 1-RESTO(A1+B1;2)

Operatore IF THEN (Implicazione logica)

A implica B. A è condizione sufficiente per B, B è condizione necessaria per A. A è l’ipotesi e B è la tesi.

Può anche essere riscritto usando not e or → NOT A OR B = A → B = SE(A1>B1;0;1).

Esempio di implicazione

Essere lombardi è una condizione necessaria o sufficiente per essere bergamaschi? È una condizione necessaria. Essere nati in California è una condizione necessaria o sufficiente per essere Americani? Sufficientemente. L’insieme più piccolo è essere bergamaschi, quindi A, mentre essere lombardi è l’insieme più grande B. A ⊆ B → L’insieme più piccolo implica l’insieme più grande; l’insieme più grande è condizione necessaria per l'insieme più piccolo.

Operatore IFF (Doppia implicazione, equivalenza logica)

(A → B) • (B → A)

A > B = SE(A1>B1;0;1), A = B = SE(A1<>B1;0;1).

Connettivi NAND e NOR

A NAND B = NOT (A AND B), ossia 1-(A1*B1).

A NOR B è il NOT (A OR B)=1-MAX(A1;B1).

Esercizio di formalizzazione e valutazione

Formalizzare e valutare ciascuna proposizione in modo esaustivo con le tavole di verità.

• Né Alice né Bianca esce. → NOT A AND NOT B
• Alice e Bianca non escono. → NOT (A AND B)
• Alice non esce oppure Bianca non esce. → NOT A OR NOT B
• Alice esce o Bianca esce. → A OR B
• NOT (NOT A AND NOT B) è equivalente a una delle precedenti proposizioni.