Argomento di Programmazione 1. Fatto a lezione a settembre, deck 3.1 intero: slide 2-10 (perché serve, NOT AND OR, proprietà, tavole di verità, notazioni), slide 11-21 (precedenza ed esempi di tavole), slide 22-27 (equivalenza, De Morgan, implicazione, dalla tavola alla formula, tautologia). Prima: Espressioni, operatori e costanti (precedenze del C, lazy evaluation). Dopo: Istruzioni condizionali.
Il filo del deck:
calcolare la verità un programma deve decidere: SE LuceRossa ALLORA Stop
|
valori solo due: 1 = VERO, 0 = FALSO
|
operatori NOT (unario), AND, OR (binari) e le loro tavole di verità
|
precedenza NOT, poi AND, poi OR; le parentesi cambiano l'ordine
|
tavole di verità una riga per ogni combinazione: 2^n righe con n variabili
|
equivalenza stessa tavola -> De Morgan, distributive, semplificazioni
|
altri operatori equivalenza ⇔, implicazione ⇒
dalla tavola alla OR delle righe a 1, ognuna come AND di variabili
formula
tautologia, contraddizione sempre vera, sempre falsa
1Definizioni
Perché serve (slide 2-3). Un programma deve “calcolare la verità” per decidere cosa fare: un sensore che esegue SE LuceRossa ALLORA Stop ALTRIMENTI Procedi ha bisogno di sapere se LuceRossa è vera. Quasi sempre la domanda è composta (“luce rossa e nessuna ambulanza”, “pioggia oppure neve”): l’algebra di Boole è il calcolo con cui si combinano queste risposte sì/no.
Algebra di Boole (slide 4-5). Opera su variabili che assumono valori binari: 0 e 1, VERO e FALSO, bianco e nero. Come tutte le algebre ha delle operazioni per manipolarli, e sono tre: NOT, AND, OR. Si applicano a operandi che possono assumere solo valori binari: VERO è il bit 1, FALSO il bit 0.
A parole, prima delle tavole:
- NOT è il “non” dell’italiano: rovescia. “Non piove” è vero quando “piove” è falso.
- AND è un “e” esigente: “ho le chiavi e il portafoglio” è vero solo se ho tutte e due le cose.
- OR è un “o” largo: “piove o nevica” è vero se succede almeno una delle due, anche entrambe. Non è l‘“o… o…” esclusivo dell’italiano (“o mangi la minestra o salti dalla finestra”): quello è un altro operatore, lo XOR (esercizio 5).
| Operatore | Tipo | Definizione (slide 6) |
|---|---|---|
| NOT | unario (un operando) | NOT A è l’opposto del valore di A |
| AND | binario (due operandi) | A AND B è VERO se entrambi gli operandi sono VERO |
| OR | binario | A OR B è VERO se almeno uno degli operandi è VERO |
Tavola di verità (slide 8-9). Nelle tavole di verità si compilano i valori del risultato di un’operazione in funzione dei valori degli operandi, per ogni combinazione possibile (VERO → 1, FALSO → 0). Con variabili le combinazioni sono , perché ogni variabile raddoppia i casi: 2 righe per una variabile, 4 per due, 8 per tre, 16 per quattro.
A | NOT A A B | A AND B A B | A OR B
---+------ -----+-------- -----+-------
0 | 1 0 0 | 0 0 0 | 0
1 | 0 0 1 | 0 0 1 | 1
1 0 | 0 1 0 | 1
1 1 | 1 1 1 | 1
Per ricordarle: AND è 1 in una sola riga (tutti 1), OR è 0 in una sola riga (tutti 0).
Un modo di vederle con un disegno, che non è nelle slide ma aiuta con De Morgan: il rettangolo sono tutti i casi possibili, il cerchio A i casi in cui A è vera, il cerchio B quelli in cui B è vera. La parte colorata è dove l’espressione vale 1.
NOT A è tutto il fuori del cerchio A; A AND B è la parte comune ai due cerchi; A OR B è tutto quello che sta in almeno un cerchio.
Notazioni (slide 10). Lo stesso operatore si scrive in modi diversi a seconda del contesto:
| parola | C | algebra | |
|---|---|---|---|
| NOT | NOT A | !A | |
| AND | A AND B | A && B | (o ) |
| OR | A OR B | A || B |
La notazione algebrica spiega le tavole: AND si comporta come il prodotto di 0 e 1 (, ogni altro prodotto è 0), OR come una somma in cui resta 1 (non c’è un valore 2).
Proprietà (slide 7).
- Commutativa:
A OR B = B OR A,A AND B = B AND A. L’ordine degli operandi non conta. - Distributiva di uno verso l’altro, in entrambi i versi:
A AND (B OR C) = (A AND B) OR (A AND C), come con i numeri;- ma anche
A OR (B AND C) = (A OR B) AND (A OR C), che con i numeri non vale ( in generale) e qui sì.
La seconda distributiva è quella che sorprende, quindi va controllata. Tre variabili, otto righe, una colonna per ogni pezzo:
| A | B | C | B AND C | A OR (B AND C) | A OR B | A OR C | (A OR B) AND (A OR C) |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
La quinta e l’ultima colonna coincidono riga per riga. L’intuizione: quando entrambi i lati valgono 1 (un OR con un 1 dentro è 1); quando entrambi si riducono a B AND C.
Altre identità che non sono sulle slide ma si verificano con una tavola da due o quattro righe, e servono per semplificare:
A AND 1 = A A OR 0 = A elemento neutro
A AND 0 = 0 A OR 1 = 1 elemento assorbente
A AND A = A A OR A = A idempotenza
A AND NOT A = 0 A OR NOT A = 1 complemento
NOT (NOT A) = A doppia negazione
A OR (A AND B) = A A AND (A OR B) = A assorbimento
L’assorbimento a parole: “A, oppure A e B insieme” è vero esattamente quando A è vero, perché il secondo caso è già dentro il primo.
Precedenza (slide 11-13). Calcolare un’espressione logica vuol dire trovarne il valore (1 o 0) a partire dai valori dei singoli operandi. Senza parentesi si valuta:
- prima NOT;
- poi AND;
- per ultimo OR.
Le parentesi possono modificare questa sequenza. È la stessa idea di prima di : AND è il “prodotto”, OR la “somma”, e A OR B AND C si legge A OR (B AND C) come si legge . In C vale lo stesso ordine: ! lega più di &&, che lega più di ||.
Esempio: con , , , A OR B AND C vale 1 OR (0 AND 0) cioè 1. Controesempio: chi lo legge da sinistra a destra calcola (1 OR 0) AND 0, cioè 0, e sbaglia.
Equivalenza (slide 22). Due espressioni booleane sono equivalenti se e solo se hanno la medesima tavola di verità. Il “se e solo se” lavora in due versi:
- per dire che sono equivalenti bisogna controllare tutte le righe;
- per dire che non lo sono basta una riga in cui differiscono.
Esempio: NOT Y AND (Y OR NOT X) e NOT X AND NOT Y sono equivalenti (si vede sotto, negli esempi del prof). Controesempio: NOT (A AND B) e NOT A AND NOT B non lo sono, basta la riga , : la prima vale NOT 0 cioè 1, la seconda 0 AND 1 cioè 0.
Altri operatori (slide 25).
equivalenza implicazione
A B | A ⇔ B A B | A ⇒ B
-----+------ -----+------
0 0 | 1 0 0 | 1
0 1 | 0 0 1 | 1
1 0 | 0 1 0 | 0
1 1 | 1 1 1 | 1
A ⇔ Bè vera quando A e B hanno lo stesso valore.A ⇒ B(“se A allora B”) è falsa solo quando A è vera e B falsa. L’intuizione è una promessa: “se piove, prendo l’ombrello”. La promessa è rotta solo se piove e non prendo l’ombrello. Se non piove, qualunque cosa io faccia la promessa non è violata, quindi l’implicazione è vera. Si può scrivere comeNOT A OR B(esercizio 4).- Controesempio da tenere a mente:
A ⇒ Bnon è equivalente aB ⇒ A. Nella riga , la prima vale 1 e la seconda 0 (“se prendo l’ombrello allora piove” è un’altra frase).
Tautologia e contraddizione (slide 27).
- Contraddizione: espressione che è sempre falsa, qualunque valore abbiano le variabili. Esempio:
A AND (NOT A), perché A non può essere vera e falsa insieme. - Tautologia: espressione che è sempre vera. Esempio:
A OR (NOT A), perché una delle due è vera di sicuro.
Nella tavola: l’ultima colonna è tutta 0 (contraddizione) o tutta 1 (tautologia). Un’espressione che ha almeno un 1 e almeno uno 0, come A AND B, non è né l’una né l’altra. In un programma una condizione che è una contraddizione rende il ramo irraggiungibile (esercizio 11), una tautologia in un while dà un ciclo infinito.
2Concetti
2.1Vero e falso in C
Il deck parla di 0 e 1; il C è più largo, come già visto in Espressioni, operatori e costanti:
- un valore 0 è falso, qualunque valore diverso da 0 (anche negativo) è vero;
!,&&,||e i confronti (x < y,x == y, …) restituiscono sempre unintche vale 0 o 1.
Due esempi, il secondo con numeri che non sono 0 e 1:
#include <stdio.h>
int main(void)
{
printf("%d %d %d\n", !0, !7, !-3);
printf("%d %d %d\n", 5 && -2, 0 || 0, 4 || 0);
printf("%d %d\n", 3 > 2, (3 > 2) + (4 > 1));
return 0;
}
Output (verificato):
1 0 0
1 0 1
1 2
| espressione | perché | valore |
|---|---|---|
!0 | 0 è falso, il NOT dà vero | 1 |
!7 | 7 è vero, il NOT dà falso | 0 |
!-3 | -3 è vero (diverso da 0) | 0 |
5 && -2 | entrambi diversi da 0 | 1 |
0 || 0 | nessuno vero | 0 |
4 || 0 | almeno uno vero | 1 |
3 > 2 | il confronto è vero | 1 |
(3 > 2) + (4 > 1) | i confronti sono int, | 2 |
Controesempio: 3 < x < 10 non dice “x fra 3 e 10”. Si valuta da sinistra: 3 < x dà 0 o 1, e 0 o 1 è sempre minore di 10. Con vale 1:
#include <stdio.h>
int main(void)
{
int x = 20;
printf("%d\n", 3 < x < 10);
printf("%d\n", 3 < x && x < 10);
return 0;
}
Stampa 1 e poi 0 (verificato). Il blocco non è marcato c perché con -Wall gcc avvisa: comparisons like 'X<=Y<=Z' do not have their mathematical meaning. La forma giusta è la seconda, con &&.
2.2Precedenza in C, con i confronti
Nelle condizioni del C ci sono anche i confronti e l’aritmetica. Dalla tabella delle precedenze di Espressioni, operatori e costanti, dal più forte al più debole:
! ++ -- -(unario) unari
* / %
+ -
< <= > >= confronti
== !=
&&
||
Quindi x > 0 && x < 10 || y <mark> 0 si legge ((x > 0) && (x < 10)) || (y </mark> 0): prima i confronti, poi &&, per ultimo ||. Come in algebra di Boole.
L’insidia è il !, che lega più dei confronti. Con a che vale 0 e b che vale 5:
#include <stdio.h>
int main(void)
{
int a = 0;
int b = 5;
printf("%d\n", !a > b);
printf("%d\n", !(a > b));
return 0;
}
Stampa 0 e poi 1 (verificato; gcc avvisa logical not is only applied to the left hand side of comparison). !a > b è (!a) > b, cioè 1 > 5, cioè 0. Per negare il confronto servono le parentesi: !(a > b), cioè !0, cioè 1. Meglio ancora scrivere a <= b.
Ricordare anche la lazy evaluation (Espressioni, operatori e costanti, slide 62 del deck 2.2): && e || si valutano da sinistra e si fermano appena il risultato è deciso. In A && B con A falso, B non si valuta; in A || B con A vero, nemmeno. Se B contiene un ++, l’incremento non avviene (esercizio 13).
2.3Leggi di De Morgan
(slide 22-24) Le leggi come le scrive il prof:
1. A AND B = NOT ((NOT A) OR (NOT B))
2. A OR B = NOT ((NOT A) AND (NOT B))
La forma che si usa di più, equivalente (si nega tutto da entrambe le parti e si usa la doppia negazione), è quella che nega una condizione intera:
NOT (A AND B) = (NOT A) OR (NOT B)
NOT (A OR B) = (NOT A) AND (NOT B)
L’intuizione. “Non è vero che ho chiavi e portafoglio” vuol dire “mi manca almeno una delle due”: non ho le chiavi oppure non ho il portafoglio. “Non è vero che piove o nevica” vuol dire che non piove e non nevica. Con le regioni:
In alto: il fuori della parte comune (NOT (A AND B)) è lo stesso che “fuori da A, oppure fuori da B”. In basso: il fuori di tutti e due i cerchi (NOT (A OR B)) è la parte che sta fuori da A e fuori da B.
Regola pratica: il NOT entra nella parentesi, nega ogni pezzo, e AND e OR si scambiano.
Esempi in C, dal più facile:
!(a && b)equivale a!a || !b;!(x > 0 && x < 10)equivale a!(x > 0) || !(x < 10), cioèx <= 0 || x >= 10. La negazione di>è<=, non<;!(c <mark> 'a' || c </mark> 'b')equivale ac != 'a' && c != 'b'.
Controesempio: dimenticare lo scambio. NOT (A AND B) non è NOT A AND NOT B: con , la prima vale 1 e la seconda 0 (esercizio 3).
Dimostrazione della legge 1 con la tavola (slide 23-24)
Si compila una colonna per ogni sotto-espressione, poi si confronta l’ultima con A AND B.
| A | B | NOT A | NOT B | (NOT B) OR (NOT A) | NOT ((NOT B) OR (NOT A)) | A AND B |
|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 | 1 | 1 |
Le ultime due colonne coincidono in tutte e quattro le righe, quindi le espressioni sono equivalenti. La slide scrive (NOT B) OR (NOT A) invece di (NOT A) OR (NOT B): è lo stesso per la commutativa.
Dimostrazione della legge 2 con la tavola (esercizio della slide 22)
| A | B | NOT A | NOT B | (NOT A) AND (NOT B) | NOT ((NOT A) AND (NOT B)) | A OR B |
|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 | 1 | 1 |
Le ultime due colonne coincidono: equivalenti.
Entrambe verificate anche in C, stampando le colonne con due cicli annidati (il while arriva in Ciclo while ed esempi: qui basta leggere l’output):
#include <stdio.h>
int main(void)
{
int a = 0;
printf("A B | A&&B !(!A||!B) | A||B !(!A&&!B)\n");
while (a <= 1) {
int b = 0;
while (b <= 1) {
printf("%d %d | %d %d | %d %d\n",
a, b, a && b, !(!a || !b), a || b, !(!a && !b));
b++;
}
a++;
}
return 0;
}
Output:
A B | A&&B !(!A||!B) | A||B !(!A&&!B)
0 0 | 0 0 | 0 0
0 1 | 0 0 | 1 1
1 0 | 0 0 | 1 1
1 1 | 1 1 | 1 1
2.4Negare una condizione con un intervallo
Il caso che esce di più: “x non è fra 4 e 9”. La condizione “x fra 4 e 9” è x > 3 && x < 10; la sua negazione con De Morgan è x <= 3 || x >= 10.
I punti pieni sono i valori di x per cui la condizione è vera. La negazione prende esattamente i punti vuoti della riga sopra: nessun buco, nessun punto in comune. Si vede anche perché la negazione di un “dentro” (con &&) è un “fuori” (con ||): il fuori sono due pezzi separati, e un numero non può stare in tutti e due.
Controesempio: negare x > 3 con x < 3 dimentica il 3, e negare x < 10 con x > 10 dimentica il 10. Verifica sui due bordi:
#include <stdio.h>
int main(void)
{
int x = 3;
printf("%d %d %d\n", !(x > 3 && x < 10), x <= 3 || x >= 10, x < 3 || x > 10);
x = 10;
printf("%d %d %d\n", !(x > 3 && x < 10), x <= 3 || x >= 10, x < 3 || x > 10);
return 0;
}
Output (verificato):
1 1 0
1 1 0
La terza colonna, quella sbagliata, vale 0 proprio sui bordi.
2.5Equivalenza e implicazione in C
Non ci sono operatori ⇔ e ⇒ in C. Si scrivono con quelli che ci sono:
A ⇒ Bè!a || b(esercizio 4), oppure, per De Morgan,!(a && !b): “non succede che a sia vera e b falsa”;A ⇔ Bfra valori 0/1 èa == b, e lo XOR (diversi) èa != b.
Attenzione all’ultimo punto: a == b e a != b confrontano i numeri, non i valori di verità. Con a che vale 2 e b che vale 5 sono entrambi veri, quindi lo XOR dovrebbe dare 0, ma a != b dà 1. Si risolve portando prima tutto a 0/1 con il !:
#include <stdio.h>
int main(void)
{
int a = 2;
int b = 5;
printf("%d %d\n", a != b, !a != !b);
printf("%d %d\n", !a || b, !(a && !b));
return 0;
}
Output (verificato):
1 0
1 1
!a e !b valgono 0 tutti e due, quindi !a != !b è 0, il risultato giusto. La seconda riga: le due forme dell’implicazione danno lo stesso valore, come deve essere.
2.6Dalla tavola alla formula
(slide 26) Data una tavola di verità è sempre possibile calcolare l’espressione logica:
- prendi le righe in cui il risultato è 1;
- per ogni riga scrivi l’AND delle variabili, negando quelle che valgono 0 (la riga
A=0, B=1diventaNOT A AND B); - metti in OR tutti questi pezzi.
Perché funziona: ogni pezzo è un AND, quindi è vero in una sola riga, quella da cui l’hai costruito (NOT A AND B è 1 solo per , ). L’OR dei pezzi è vero dove è vero almeno un pezzo, cioè esattamente nelle righe scelte. Si chiama somma di prodotti (OR di AND). Se la tavola non ha nessun 1, l’espressione è una contraddizione e la formula è semplicemente 0.
Il risultato è corretto ma spesso lungo: dopo si semplifica con le identità (esempio della slide 26 sotto, esercizi 6 e 14).
3Metodo
Compilare una tavola di verità.
- Conta le variabili e scrivi le righe in ordine binario (000, 001, 010, … 111): così non ne salti nessuna. L’ultima variabile alterna 0 1 0 1, quella prima alterna a coppie, la prima a blocchi di metà.
- Metti le parentesi implicite con la precedenza NOT > AND > OR.
- Aggiungi una colonna per ogni sotto-espressione, dalle più interne verso l’esterno.
- Calcola colonna per colonna, usando solo le colonne già fatte.
- L’ultima colonna è l’espressione completa. Controllo: se l’espressione è un AND fuori, gli 1 devono essere pochi; se è un OR, gli 0.
Dimostrare un’equivalenza. Tavola delle due espressioni sulle stesse righe, confronto dell’ultima colonna riga per riga. Per dimostrare che non sono equivalenti basta una riga diversa: scrivila con i valori delle variabili e i due risultati.
Semplificare un’espressione.
- Cerca coppie di pezzi che differiscono per una sola variabile negata, come
A AND BeA AND NOT B: raccogli (distributiva al contrario) e usa il complemento, restaA. - Cerca un pezzo e la sua negazione in OR:
A OR (NOT A AND X)diventaA OR X(distributiva dell’OR, complemento, neutro). - Usa assorbimento, neutro e idempotenza per togliere i pezzi inutili.
- Controlla il risultato con la tavola: deve avere la stessa ultima colonna dell’originale.
Negare una condizione C (serve per scrivere la condizione di uscita di un while, o il ramo else).
- De Morgan: il
!entra,&&diventa||e viceversa. - Ogni confronto si inverte:
<diventa>=,>diventa<=,x == ydiventax != ye viceversa. - Controlla un valore dentro e i valori sui bordi.
Calcolare un’espressione C a mano.
- Metti le parentesi implicite: unari, aritmetica, confronti, uguaglianze (
a == b,a != b),&&,||. - Valuta da sinistra
&&e||, fermandoti appena il risultato è deciso: la parte non valutata non esegue i suoi++e--. - Ogni
!, confronto,&&e||produce 0 o 1; nei conti successivi si usa quel numero.
4Esempi svolti a lezione
4.1Precedenza su NOT Y AND Y OR NOT X
(slide 11-12) Si mettono le parentesi un livello alla volta, applicando le regole di precedenza:
NOT Y AND Y OR NOT X
(NOT Y) AND Y OR (NOT X) prima i NOT
((NOT Y) AND Y) OR (NOT X) poi l'AND
(((NOT Y) AND Y) OR (NOT X)) infine l'OR
La slide si ferma qui. Vale la pena finire il conto: (NOT Y) AND Y è una contraddizione, sempre 0, e 0 OR (NOT X) è NOT X (elemento neutro dell’OR). Tutta l’espressione equivale a NOT X. Controllo con la tavola:
| X | Y | NOT X | NOT Y | (NOT Y) AND Y | ((NOT Y) AND Y) OR (NOT X) |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 | 0 |
L’ultima colonna è uguale a NOT X.
4.2Tavola di NOT Y AND (Y OR NOT X)
(slide 13-19) Stessa espressione con una parentesi in più: le parentesi modificano la sequenza di precedenza, e l’OR adesso si fa prima dell’AND. Il disegno con gli alberi mostra la differenza: l’operatore in cima è quello che si calcola per ultimo.
Il prof costruisce la tavola una colonna alla volta, con l’ordine di righe 10, 01, 00, 11:
| X | Y | NOT X | NOT Y | Y OR NOT X | NOT Y AND (Y OR NOT X) |
|---|---|---|---|---|---|
| 1 | 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 | 0 |
Passo per passo, come nelle slide 14-19:
- colonne
NOT XeNOT Y: si rovesciano X e Y; - colonna
Y OR NOT X: 0 solo nella prima riga, dove sia siaNOT Xvalgono 0; - ultima colonna: AND fra
NOT YeY OR NOT X, 1 solo dove entrambe sono 1, cioè la terza riga.
È vera solo per , : equivale a NOT X AND NOT Y. Le parentesi hanno cambiato il risultato: senza, l’espressione era NOT X, vera anche per , .
Verifica in C, con !, && e || (anche qui il while serve solo a stampare tutte le righe):
#include <stdio.h>
int main(void)
{
int x = 0;
printf("X Y | NOT Y AND (Y OR NOT X)\n");
while (x <= 1) {
int y = 0;
while (y <= 1) {
printf("%d %d | %d\n", x, y, !y && (y || !x));
y++;
}
x++;
}
return 0;
}
Output (verificato):
X Y | NOT Y AND (Y OR NOT X)
0 0 | 1
0 1 | 0
1 0 | 0
1 1 | 0
4.3Tavola di D = A AND NOT (B OR C)
(slide 20-21) Tre variabili, otto righe in ordine binario. Colonne: prima la parentesi interna B OR C, poi il suo NOT, poi l’AND con A.
| A | B | C | B OR C | NOT (B OR C) | D |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 |
D è vera solo quando A è vera e B e C sono entrambe false. Per De Morgan NOT (B OR C) è NOT B AND NOT C, quindi D = A AND NOT B AND NOT C, che si legge direttamente dalla riga 100. Controllo di buon senso: le prime quattro righe hanno e l’AND con 0 dà 0, quindi bastava guardare le ultime quattro.
4.4Dalla tavola alla formula, e la “forma più compatta”
(slide 26)
A B | C
-----+---
0 0 | 0
0 1 | 1 NOT A AND B
1 0 | 1 A AND NOT B
1 1 | 1 A AND B
Somma di prodotti: C = (NOT A AND B) OR (A AND NOT B) OR (A AND B).
La slide chiede se si conosce una forma più compatta. Guardando la tavola, C è 0 solo quando A e B sono entrambe 0: è la tavola dell’OR. Quindi C = A OR B. Con l’algebra, un passo per riga:
(A AND NOT B) OR (A AND B) = A AND (NOT B OR B) distributiva al contrario
= A AND 1 complemento
= A elemento neutro
C = (NOT A AND B) OR A
= A OR (NOT A AND B) commutativa
= (A OR NOT A) AND (A OR B) distributiva dell'OR sull'AND
= 1 AND (A OR B) complemento
= A OR B elemento neutro
5Esercizi tipo esame
In una pagina a parte, dal più facile al livello del 30: Algebra di Boole (esercizi).
6Errori tipici
- Dimenticare righe: con 3 variabili sono 8, non 6. Scriverle in ordine binario evita il problema.
- Leggere
NOT Y AND Y OR NOT XcomeNOT (Y AND Y OR NOT X): il NOT si applica solo a ciò che segue subito. - Calcolare
A OR B AND Cda sinistra a destra: l’AND si fa prima, come la moltiplicazione. - Applicare De Morgan senza scambiare AND e OR:
NOT (A AND B)non èNOT A AND NOT B. - Negare
x > 3conx < 3: la negazione èx <= 3. - Scrivere “fuori dall’intervallo” con
&&(x < 1 && x > 10): è una contraddizione, sempre 0. Serve||. - Pensare che
A ⇒ Bsia falsa quando A è falsa: è vera. E scambiareA ⇒ BconB ⇒ A. - Dire che due espressioni sono equivalenti dopo aver controllato solo qualche riga: servono tutte.
- In C, pensare che
!5valga -5 o 4: vale 0. E!0vale 1. - In C, scrivere
3 < x < 10o!a > bpensando alla matematica: il primo vale sempre 1, il secondo nega soloa. - In C, usare
a != bcome XOR con valori che non sono 0/1: serve!a != !b. - Contare su un
++nella parte destra di&&o||: con la lazy evaluation può non essere eseguito. - Confondere
&&e||logici con&e|, che operano sui singoli bit (si vedranno più avanti).
7Domande
-
Su che valori opera l’algebra di Boole e quali sono le sue tre operazioni?
-
Scrivi le tavole di verità di NOT, AND e OR.
-
Quante righe ha la tavola di verità di un’espressione con 4 variabili?
-
Qual è l’ordine di precedenza fra NOT, AND e OR? E fra
!,&&,||in C? -
Enuncia le due proprietà distributive.
-
Quando due espressioni booleane sono equivalenti?
-
Enuncia le leggi di De Morgan.
-
Riscrivi
!(a >= 0 && a < n)senza il!. -
Quando è falsa l’implicazione
A ⇒ B? -
Cosa sono una tautologia e una contraddizione? Dai un esempio di ciascuna.
-
Come si ricava una formula da una tavola di verità?
-
A cosa si semplifica
(NOT A AND B) OR (A AND NOT B) OR (A AND B)? -
Quanto vale in C
!3 || (0 && 5)? -
A cosa equivale
NOT Y AND Y OR NOT X, e perché? -
Per dimostrare che due espressioni non sono equivalenti, cosa basta?
-
In C quali valori sono considerati veri, e che valori restituiscono
!,&&,||e i confronti? -
Perché in C
3 < x < 10non controlla chexsia fra 3 e 10? Come si scrive? -
Enuncia le due leggi di assorbimento.
-
A ⇒ Bè equivalente aB ⇒ A? Quale riga lo decide? -
Come si scrive in C lo XOR fra due
intqualunque, e perchéa != bnon basta? -
Perché
x < 1 && x > 10è sempre falsa, e come si scrive “x fuori dall’intervallo da 1 a 10”?