Canale B · Lezione 06 · Libro, parte 2, §1.2

Proposizioni, connettivi e tavole di verità

Comincia la logica. Una proposizione è una frase che è vera o falsa; con «e», «o» e «non» se ne costruiscono di più lunghe, e la tavola di verità dice quando sono vere. È la stessa cosa delle porte logiche della lezione 01, scritta con le parole.

Libro: Johnsonbaugh, Brookshear, Brylow, Fondamenti dell'Informatica, parte 2 (Johnsonbaugh, cap. 1), §1.2
Docente: Stefano Berardi · canale B · A.A. 2026/27
Tempo di studio: 2–3 ore, anche in più volte

Definizione o risultato da sapere
Trappola / errore tipico
Conta all'esame
Oltre il libro
Esempio svolto
L'idea e il metodo, passo per passo
Da ricordare

La lezione in 7 punti

Una proposizione è una frase che è vera o falsa, non tutte e due. «Torino è in Piemonte» lo è; una domanda, un ordine o «x è maggiore di 3» no.
Con tre parole si costruiscono frasi più lunghe: «e», «o» e «non». Si chiamano connettivi: la congiunzione, la disgiunzione e la negazione.
La frase con «e» è vera solo se sono vere tutte e due le parti. Quella con «o» è vera se ne è vera almeno una. «Non» scambia vero e falso.
L'«o» della logica è inclusivo: è vero anche quando sono vere tutte e due le parti. L'«o» esclusivo, «o l'una o l'altra ma non tutte e due», ha un simbolo suo, $\oplus$ .
La tavola di verità di una formula prova tutte le combinazioni di vero e falso delle lettere: con 2 lettere sono 4 righe, con 3 lettere 8.
Senza parentesi si calcola prima «non», poi «e», poi «o». Ma nel dubbio si mettono le parentesi.
Sono le porte logiche della lezione 01: AND, OR, NOT e XOR, con V al posto di 1 e F al posto di 0.

Canali A, B e C

Nel canale B è la lezione di lunedì 12/10, dalle 9 alle 11. Per il docente è la lezione 7, perché la prima è stata un'introduzione: qui è la 06. Il diario del canale B la riassume così: «Capitolo 1.2 (Parte 2) Logica Proposizionale. Posposto: capitolo 1.1 su insiemi.» Comincia quindi la parte 2 del libro, che è il libro di Johnsonbaugh sulla matematica discreta; il primo paragrafo, sugli insiemi, il docente lo farà più avanti. Gli insiemi sono anche in Matematica Discreta, nelle lezioni D01 e D02. Non ho i lucidi del docente: ho seguito il §1.2 del libro, con le sue domande di ripasso e le soluzioni degli esercizi pubblicate sul Moodle del canale A (id 3851, aperto agli ospiti). Nel canale A la logica è nelle dispense di Felice Cardone sullo stesso Moodle. Nel canale C è nei lucidi del docente.

§1

Frasi che sono vere o false

libro, §1.2

All'ingresso di un concerto il controllore fa domande precise: «Hai il biglietto?», «Hai un documento?». Ogni risposta è sì o no. Allo stesso modo, alcune frasi si possono giudicare: o sono vere, o sono false.

Guarda queste sei frasi.

Torino è il capoluogo del Piemonte.
$2 + 5 = 19$ .
Che ore sono?
Chiudi la porta.
$x + 2 = 5$ .
Il biglietto del concerto costa 40 euro.

La 1 è vera. La 2 è falsa, ma è comunque una frase che si può giudicare. La 3 è una domanda e la 4 un ordine: non sono né vere né false. La 5 dipende da chi è $x$ : vera se $x$ vale 3, falsa altrimenti, e finché non lo sai non ha un valore. La 6 si può controllare: è vera o falsa, anche se non sai quale delle due.

L'idea

Una proposizione è una frase a cui si può rispondere «vero» o «falso». Non serve sapere quale delle due: basta che sia una delle due, e una sola.

Definizione · Proposizione (libro, §1.2)

Una proposizione è una frase che è vera oppure falsa, ma non entrambe le cose.

Come si legge. Una proposizione ha un valore di verità: vero o falso. Il libro, che è in inglese, li scrive T (true) e F (false); qui uso V e F. Nei circuiti della lezione 01 gli stessi valori erano 1 e 0. Domande, ordini e frasi con una lettera che non si sa quanto vale non sono proposizioni.

Le frasi come la 5, che diventano proposizioni quando scegli il valore di $x$ , hanno un nome loro: le vedrai nel §1.5 del libro, con «per ogni» ed «esiste».

Esempio · Dalle soluzioni del libro

Le soluzioni degli esercizi del §1.2 dicono così, per le frasi che il libro propone:

« $2 + 5 = 19$ » è una proposizione, falsa. La sua negazione è « $2 + 5 \neq = 19$ ».
una domanda non è una proposizione;
un ordine non è una proposizione;
« $p - q$ , dove $p$ e $q$ sono numeri primi» non è una proposizione: descrive un numero, non dice niente di vero o di falso.

Le lettere al posto delle frasi

Alla logica non interessa di che cosa parla una frase, ma solo se è vera o falsa. Per questo si sostituiscono le frasi con delle lettere: $p$ , $q$ , $r$ nel libro; $A$ , $B$ , $C$ nelle dispense del canale A. Per esempio:

$p$ : «ho il biglietto»;
$q$ : «ho un documento».

Ogni lettera sta per una proposizione qualunque, che può essere vera o falsa.

Prova tu

Quali sono proposizioni? (a) «7 è un numero primo.» (b) «Apri la finestra.» (c) «

y < 10

.» (d) «Il 31/12/2026 è un giovedì.»

(a) Sì, vera. (b) No: è un ordine. (c) No: dipende da $y$ . (d) Sì: basta un calendario per controllarla, ed è vera.

Da ricordare

Proposizione: una frase vera o falsa, non tutte e due.
Domande, ordini e frasi con una variabile libera non sono proposizioni.

§2

Unire le frasi: «e», «o», «non»

libro, §1.2

Il controllore del concerto ha una regola: «Entri se hai il biglietto e un documento». Con due proposizioni ne ha costruita una terza, più lunga. Le parole che uniscono le frasi si chiamano connettivi. I tre principali sono «e», «o» e «non».

«E»: tutte e due

Quando entri al concerto con la regola «biglietto e documento»? Proviamo tutti i casi:

Hai il biglietto?	Hai il documento?	Entri?
sì	sì	sì
sì	no	no
no	sì	no
no	no	no

Entri solo nel primo caso: devono essere vere tutte e due le cose.

Definizione · Congiunzione (libro, §1.2)

La congiunzione delle proposizioni $p$ e $q$ è la proposizione « $p$ e $q$ », che si scrive $p \land q$ . È vera quando $p$ e $q$ sono tutte e due vere, e falsa in tutti gli altri casi.

Come si legge. Il simbolo $\land$ si legge «e». È una specie di A senza trattino: ricorda AND. Basta che una parte sia falsa perché tutta la frase sia falsa.

«O»: almeno una

Al bar del concerto si paga «in contanti o con la carta». Se hai tutte e due le cose, puoi pagare lo stesso. Non puoi pagare solo se non hai né l'una né l'altra.

Hai contanti?	Hai la carta?	Puoi pagare?
sì	sì	sì
sì	no	sì
no	sì	sì
no	no	no

Definizione · Disgiunzione (libro, §1.2)

La disgiunzione delle proposizioni $p$ e $q$ è la proposizione « $p$ o $q$ », che si scrive $p \lor q$ . È vera quando almeno una tra $p$ e $q$ è vera, e falsa solo quando sono tutte e due false.

Come si legge. Il simbolo $\lor$ si legge «o», e viene dal latino vel. È il contrario di $\land$ : basta una parte vera perché tutta la frase sia vera.

Trappola · L'«o» della logica comprende il caso «tutte e due»

Nell'italiano di tutti i giorni «o» a volte vuol dire «o l'uno o l'altro, ma non tutti e due»: «a pranzo pasta o riso». In logica $p \lor q$ è vera anche quando $p$ e $q$ sono vere tutte e due. Si chiama «o» inclusivo.

«Non»: il contrario

La negazione di una proposizione è vera quando la proposizione è falsa, e falsa quando è vera.

Definizione · Negazione (libro, §1.2)

La negazione della proposizione $p$ è la proposizione «non $p$ », che si scrive $\neg p$ . È vera quando $p$ è falsa, e falsa quando $p$ è vera.

Come si legge. $\neg p$ si legge «non $p$ ». Il simbolo $\neg$ è un trattino con la coda, attaccato davanti alla lettera.

Le tavole dei connettivi

Le tre regole si mettono in una tabella, la tavola di verità: una riga per ogni combinazione di valori.

$p$	$q$	$p \land q$	$p \lor q$	$\neg p$
V	V	V	V	F
V	F	F	V	F
F	V	F	V	V
F	F	F	F	V

Nota · Sono le porte logiche della lezione 01

La porta AND della lezione 01 dà 1 solo se tutti e due gli ingressi sono 1: è la tavola di $\land$ , con 1 al posto di V e 0 al posto di F. La porta OR è $\lor$ , la porta NOT è $\neg$ . In C, nella condizione di un if, gli stessi connettivi si scrivono &&, || e !.

Prova tu

Con

p

vera e

q

falsa, quanto valgono

p \land q

p \lor q

\neg p

\neg q

$p \land q$ è F, perché $q$ è falsa. $p \lor q$ è V, perché $p$ è vera. $\neg p$ è F e $\neg q$ è V.

Da ricordare

$\land$ , «e»: vera solo con tutte e due le parti vere.
$\lor$ , «o»: falsa solo con tutte e due le parti false.
$\neg$ , «non»: scambia V e F.

§3

L'«o» esclusivo

libro, §1.2, esercizi

A volte «o» vuol dire davvero «uno solo dei due». Al concerto: «Con il biglietto ridotto ricevi la maglietta o il poster». Non ti danno tutti e due. Questo «o» si chiama esclusivo.

$p$	$q$	$p \oplus q$
V	V	F
V	F	V
F	V	V
F	F	F

L'«o» esclusivo si scrive $p \oplus q$ e si legge « $p$ xor $q$ »: XOR sta per exclusive or. È vero quando le due parti hanno valori diversi. È la porta XOR della lezione 01.

Il libro lo usa negli esercizi del §1.2: per ogni frase chiede se l'«o» è inclusivo o esclusivo. Le soluzioni ufficiali mostrano che dipende dal senso della frase. Ecco tre esempi nello stesso stile, con la risposta:

«Il portabicchieri dell'auto riscalda o raffredda la bevanda»: esclusivo, perché non può fare tutte e due le cose insieme.
«L'incontro è annullato se si iscrivono meno di 10 persone o se nevica»: inclusivo, perché con tutte e due le cose l'incontro è annullato lo stesso.
«Per entrare devi mostrare la carta d'identità o il passaporto»: le soluzioni del libro, per una frase così, dicono che il senso voluto è quello esclusivo. In pratica nessuno ti respinge se li mostri tutti e due: le frasi d'uso comune sono spesso ambigue.

Nota · Un regolamento ambiguo, davvero

Il libro racconta un regolamento comunale: «È vietato tenere più di tre cani e più di tre gatti nella propria proprietà». Chi ha quattro cani e due gatti viola la regola? Letta alla lettera, no: serve tenere più di tre cani e più di tre gatti. Un giudice ha dichiarato la regola «vaga»: probabilmente si voleva scrivere «o». Il libro suggerisce che il senso voluto fosse «più di tre cani o più di tre gatti».

Prova tu

Con

p

vera e

q

vera, quanto valgono

p \lor q

p \oplus q

$p \lor q$ è V: l'«o» inclusivo accetta il caso «tutte e due». $p \oplus q$ è F: l'«o» esclusivo lo esclude.

Da ricordare

$p \oplus q$ , «o esclusivo»: vera quando le due parti hanno valori diversi.
In logica, senza altre indicazioni, «o» è sempre inclusivo: $\lor$ .

§4

Negare una frase senza sbagliare

libro, §1.2

La negazione sembra la parte più facile, ma in italiano è facile sbagliarla. Negare vuol dire dire esattamente il contrario: la negazione è vera in tutti i casi in cui la frase è falsa, e solo in quelli.

Esempio · Dieci lanci di una moneta (soluzioni del libro, §1.2)

Lanci una moneta 10 volte. La frase è «sono uscite 10 teste».

La negazione è «non sono uscite 10 teste», cioè «è uscita almeno una croce».
Non è «sono uscite 10 croci»: con 5 teste e 5 croci la frase di partenza è falsa, ma anche questa.

Con la frase «non è uscita nessuna testa», la negazione è «è uscita almeno una testa», non «sono uscite 10 teste».

Lo stesso succede con i numeri. Le dispense del canale A lo fanno notare: la negazione di « $2 < 5$ » è « $2 \geq 5$ », non « $2 > 5$ ». C'è anche il caso dell'uguaglianza, che non va dimenticato.

Trappola · Il contrario non è l'opposto

La negazione di «tutti i biglietti sono venduti» non è «nessun biglietto è venduto», ma «almeno un biglietto non è venduto». La negazione deve coprire tutti i casi in cui la frase di partenza è falsa.

La negazione di «Torino è in Piemonte» è «Torino non è in Piemonte», o anche «non è vero che Torino è in Piemonte». Non è «Torino è in Lombardia»: quella è un'altra frase, che non copre tutti i casi.

Prova tu

Scrivi la negazione di: (a) «Il concerto comincia alle 21.» (b) «Ho almeno 18 anni.» (c) «Tutti hanno il biglietto.»

(a) «Il concerto non comincia alle 21.» (b) «Ho meno di 18 anni.» (c) «Almeno una persona non ha il biglietto.»

Da ricordare

La negazione è vera esattamente quando la frase di partenza è falsa.
«Non tutti» vuol dire «almeno uno no», non «nessuno».

§5

Formule e parentesi

libro, §1.2

Con i connettivi si costruiscono frasi lunghe quanto vuoi. Al concerto, per esempio: «Entri se hai il biglietto e un documento, oppure se sei nella lista degli ospiti». Con le lettere:

$p$ : «hai il biglietto»;
$q$ : «hai un documento»;
$r$ : «sei nella lista degli ospiti».

La regola è $(p \land q) \lor r$ . Un'espressione così, fatta di lettere, connettivi e parentesi, si chiama formula, o proposizione composta.

Le parentesi cambiano il senso

Senza parentesi, la regola si potrebbe leggere in due modi:

$(p \land q) \lor r$ : «biglietto e documento», oppure «in lista»;
$p \land (q \lor r)$ : «biglietto», e in più «documento o lista».

Sono due regole diverse. Un ospite in lista senza biglietto entra con la prima, ma non con la seconda.

L'ordine dei connettivi

Per non scrivere troppe parentesi, il libro fissa un ordine, come in aritmetica si fanno le moltiplicazioni prima delle somme:

prima $\neg$ ;
poi $\land$ ;
poi $\lor$ .

Quindi $p \lor q \land r$ vuol dire $p \lor (q \land r)$ , e $\neg p \land q$ vuol dire $(\neg p) \land q$ .

Trappola · Il «non» si attacca solo a quello che segue

$\neg p \land q$ vuol dire «non $p$ , e $q$ ». Per negare tutta la congiunzione servono le parentesi: $\neg (p \land q)$ . In italiano la differenza è tra «non ho il biglietto e ho il documento» e «non è vero che ho il biglietto e il documento».

All'esame e negli esercizi conviene comunque mettere sempre le parentesi: non costano niente, ed evitano gli errori.

Prova tu

Metti le parentesi secondo l'ordine del libro: (a)

\neg p \lor q

; (b)

p \land q \lor r

; (c)

p \lor \neg q \land r

(a) $(\neg p) \lor q$ . (b) $(p \land q) \lor r$ . (c) $p \lor ((\neg q) \land r)$ .

Da ricordare

Una formula è fatta di lettere, connettivi e parentesi.
Ordine: prima $\neg$ , poi $\land$ , poi $\lor$ . Nel dubbio, parentesi.

§6

La tavola di verità di una formula

libro, §1.2

Per sapere quando una formula è vera si provano tutti i casi possibili: tutte le combinazioni di V e F delle lettere. Ogni combinazione è una riga della tavola.

Quante righe

Ogni lettera può essere V o F. Con una lettera i casi sono 2; ogni lettera in più raddoppia i casi, come gli ingressi di un circuito nella lezione 01.

Lettere	Righe
1	2
2	4
3	8
4	16

Con $n$ lettere le righe sono $2^{n}$ .

L'ordine delle righe

Per non dimenticare righe si usa sempre lo stesso schema, quello del libro:

la prima lettera ha la prima metà delle righe V e la seconda metà F;
la seconda alterna a gruppi più piccoli, della metà;
l'ultima alterna una riga sì e una no: V, F, V, F.

È come contare in base 2 della lezione 02, ma all'indietro e con V al posto di 0.

Metodo · Costruire la tavola di una formula

Conta le lettere: se sono $n$ , le righe sono $2^{n}$ . Scrivi le combinazioni con lo schema qui sopra.
Spezza la formula nei suoi pezzi, dal più piccolo al più grande. Ogni pezzo è una colonna.
Riempi le colonne da sinistra a destra, usando le tavole dei connettivi e le colonne già pronte.
L'ultima colonna è la formula intera.

Esempio · La regola «biglietto e documento, oppure in lista»

La formula è $(p \land q) \lor r$ . Tre lettere, quindi 8 righe. I pezzi: prima $p \land q$ , poi la formula intera.

$p$	$q$	$r$	$p \land q$	$(p \land q) \lor r$
V	V	V	V	V
V	V	F	V	V
V	F	V	F	V
V	F	F	F	F
F	V	V	F	V
F	V	F	F	F
F	F	V	F	V
F	F	F	F	F

Entri in 5 casi su 8: quando hai biglietto e documento (righe 1 e 2), e quando sei in lista (righe 1, 3, 5, 7).

Esempio · Una formula con la negazione: $(p \lor q) \land \neg r$

I pezzi sono $p \lor q$ , $\neg r$ e la formula intera.

$p$	$q$	$r$	$p \lor q$	$\neg r$	$(p \lor q) \land \neg r$
V	V	V	V	F	F
V	V	F	V	V	V
V	F	V	V	F	F
V	F	F	V	V	V
F	V	V	V	F	F
F	V	F	V	V	V
F	F	V	F	F	F
F	F	F	F	V	F

È vera in 3 righe: quando $r$ è falsa e almeno una tra $p$ e $q$ è vera.

Prova tu con lo strumento

Scrivi una formula: lo strumento fa la tavola, con una colonna per ogni pezzo, nello stesso ordine del libro. Prova a cambiare le parentesi della regola del concerto e guarda come cambiano le righe.

Formule sempre vere e sempre false

Alcune formule hanno la stessa colonna finale in tutte le righe.

$p \lor \neg p$ , «piove o non piove», è vera in tutte le righe. Una formula così si chiama tautologia.
$p \land \neg p$ , «piove e non piove», è falsa in tutte le righe. Si chiama contraddizione.

Il libro, negli esercizi del §1.2, ne fa costruire due più lunghe. Le soluzioni ufficiali danno queste tavole:

$p$	$q$	$p \land \neg q$	$(p \land q) \land \neg q$
V	V	F	F
V	F	V	F
F	V	F	F
F	F	F	F

La seconda è sempre falsa: chiede che $q$ sia vera, dentro $p \land q$ , e falsa, con $\neg q$ , nello stesso momento. Anche la formula $(p \lor q) \land (\neg p \lor q) \land (p \lor \neg q) \land (\neg p \lor \neg q)$ dell'esercizio successivo è sempre falsa: ogni riga rende falso uno dei quattro pezzi. Prova a scriverla nello strumento.

Prova tu

Quante righe ha la tavola di

(p \lor q) \land (r \lor s)

? E in quante righe è falsa

p \lor q \lor r

4 lettere: 16 righe. $p \lor q \lor r$ è falsa solo quando sono false tutte e tre: una riga sola, l'ultima.

Da ricordare

Con $n$ lettere, $2^{n}$ righe: la prima lettera cambia più lentamente, l'ultima a ogni riga.
Una colonna per ogni pezzo della formula, dal più piccolo al più grande.
Tautologia: sempre vera. Contraddizione: sempre falsa.

§7

Il valore in una sola riga

Spesso non serve tutta la tavola: un quiz dà i valori delle lettere e chiede quanto vale la formula. Si fa come un'espressione dell'aritmetica: si sostituiscono i valori e si calcola da dentro verso fuori.

Esempio · $(p \land \neg q) \lor (\neg p \land r)$ con $p$ = V, $q$ = V, $r$ = F

$\neg q$ = F, quindi $p \land \neg q$ = V $\land$ F = F.
$\neg p$ = F, quindi $\neg p \land r$ = F $\land$ F = F.
F $\lor$ F = F.

La formula è falsa.

Un trucco fa risparmiare tempo: con «e» basta trovare una parte falsa, con «o» basta trovare una parte vera. Il resto non serve calcolarlo.

Prova tu

Quanto vale

\neg (p \lor q) \lor (q \land r)

con

p

= F,

q

= V,

r

= V?

$p \lor q$ = V, quindi $\neg (p \lor q)$ = F. $q \land r$ = V. F $\lor$ V = V: la formula è vera.

Da ricordare

Per una riga sola: sostituisci i valori e calcola da dentro verso fuori.
Con «e» cerca una parte falsa, con «o» una parte vera: spesso basta.

§8

Dall'italiano alle formule

libro, §1.2

Molti esercizi del libro chiedono di tradurre: dalle frasi alle formule, e dalle formule alle frasi. Ci sono alcune parole a cui fare attenzione.

Frase in italiano	Formula	Attenzione
ho il biglietto e il documento	$p \land q$
ho il biglietto ma non il documento	$p \land \neg q$	«ma», «però», «eppure» sono «e»
ho il biglietto o il documento	$p \lor q$	inclusivo, se non c'è scritto altro
o il biglietto o il documento, non tutti e due	$p \oplus q$	esclusivo, quando lo dice il testo
né il biglietto né il documento	$\neg p \land \neg q$	sono false tutte e due
non ho il biglietto e ho il documento	$\neg p \land q$	il «non» riguarda solo il biglietto
non è vero che ho il biglietto e il documento	$\neg (p \land q)$	il «non» riguarda tutta la frase

Trappola · «Né… né» vuol dire «nessuna delle due»

«Né il biglietto né il documento» dice che mancano tutti e due: $\neg p \land \neg q$ . La formula $\neg p \lor \neg q$ dice un'altra cosa: che ne manca almeno uno. Nella tavola qui sotto le due colonne sono diverse nelle righe 2 e 3.

$p$	$q$	$\neg p \land \neg q$	$\neg p \lor \neg q$	$\neg (p \land q)$
V	V	F	F	F
V	F	F	V	V
F	V	F	V	V
F	F	V	V	V

Le ultime due colonne sono uguali: «non è vero che ho tutti e due» è lo stesso che «me ne manca almeno uno». È una delle leggi di De Morgan, che il libro presenta nel §1.3, la prossima lezione.

Esempio · Traduzioni nello stile del libro

Il libro usa due proposizioni su uno studente: $p$ , «Lea segue informatica», e $q$ , «Lea segue matematica». Nelle soluzioni le traduzioni sono così:

$\neg p$ : «Lea non segue informatica»;
$p \lor \neg q$ : «Lea segue informatica o non segue matematica»;
$\neg p \land \neg q$ : «Lea non segue né informatica né matematica».

Con tre proposizioni, $p$ «oggi è lunedì», $q$ «piove», $r$ «fa caldo»: la formula $(p \land q) \land \neg (r \lor p)$ si legge «oggi è lunedì e piove, e non è vero che fa caldo o è lunedì». È una contraddizione: chiede che sia lunedì e che non sia lunedì.

Prova tu

Con

p

: «piove» e

q

: «fa freddo», traduci: (a) «Piove ma non fa freddo.» (b) «Né piove né fa freddo.» (c) «Non è vero che piove e fa freddo.»

(a) $p \land \neg q$ . (b) $\neg p \land \neg q$ . (c) $\neg (p \land q)$ .

Da ricordare

«Ma» è un «e»; «né… né» è $\neg p \land \neg q$ .
Guarda fin dove arriva il «non»: su una parte sola, o su tutta la frase.

§9

I simboli di questa lezione

Simbolo	Si legge	Vuol dire	Esempio
V, F	«vero», «falso»	i due valori di verità; nel libro T e F
$p$ , $q$ , $r$	«pi», «cu», «erre»	proposizioni qualsiasi	$p$ : «ho il biglietto»
$p \land q$	« $p$ e $q$ »	congiunzione: vera solo se tutte e due vere	V $\land$ F = F
$p \lor q$	« $p$ o $q$ »	disgiunzione inclusiva: vera se almeno una è vera	V $\lor$ F = V
$p \oplus q$	« $p$ xor $q$ »	o esclusivo: vera se i valori sono diversi	V $\oplus$ V = F
$\neg p$	«non $p$ »	negazione: il valore opposto	$\neg$ V = F
$2^{n}$	«due alla enne»	il numero di righe con $n$ lettere	$2^{3} = 8$
`&&`, `\\|\\|`, `!`	«and», «or», «not»	gli stessi connettivi in C	`x > 0 && x < 10`

§10

Verso l'esame

esame

Le regole dell'esame, uguali per i tre canali, sono nella lezione 01 e nella scheda del corso: 9 quiz in 45 minuti al computer, con Safe Exam Browser, da 3 punti l'uno; servono almeno 18 punti.

Che cosa serve di questa lezione

Valutare una formula riga per riga. Nella simulazione 1 del 2023/24 un quiz dà una formula e quattro righe di valori, e chiede il valore della formula in ogni riga. Quella formula usa anche $\to$ e $\leftrightarrow$ , che sono la lezione 07; il metodo è quello di qui.
Dalla tabella alla formula, e i circuiti. I quiz sui circuiti (simulazione 1, domande 5 e 6) chiedono quali formule hanno una certa tavola. Si risolvono con le tavole di questa lezione: sono svolti nella lezione 05.
Tradurre e negare. Le negazioni di frasi, con «tutti», «nessuno», «almeno uno», tornano nella simulazione 2 del 2023/24, con i quantificatori del §1.5 del libro.

Una domanda nello stile del quiz, letta insieme

Il testo: «Considera la formula $(A \lor B) \land \neg (A \land B)$ . Seleziona il valore della formula in ogni riga della tabella: $A$ = V, $B$ = V; $A$ = V, $B$ = F; $A$ = F, $B$ = F; $A$ = F, $B$ = V.» È costruita come il quiz 3 della simulazione 1, ma con i connettivi di questa lezione.

In pratica chiede: quattro valori, uno per riga. Le righe non sono nell'ordine solito.

Esempio · la soluzione, passo per passo

Per ogni riga calcolo i due pezzi, $A \lor B$ e $\neg (A \land B)$ , e poi li unisco con «e».

$A$	$B$	$A \lor B$	$A \land B$	$\neg (A \land B)$	formula
V	V	V	V	F	F
V	F	V	F	V	V
F	F	F	F	V	F
F	V	V	F	V	V

Le risposte sono F, V, F, V. A parole: «almeno uno, ma non tutti e due», cioè l'«o» esclusivo. La formula ha la stessa tavola di $A \oplus B$ .

Metodo · I quiz «valore in ogni riga»

Leggi i valori di ogni riga: nei quiz l'ordine delle righe cambia.
Calcola i pezzi da dentro verso fuori, scrivendo ogni valore.
Usa le scorciatoie: «e» con una parte falsa è falso, «o» con una parte vera è vero.
Alla fine guarda la colonna: se ha sempre lo stesso valore, ricontrolla; può essere una tautologia o una contraddizione, ma può anche essere un errore.

Errori da evitare

Leggere l'«o» come esclusivo: V $\lor$ V è V.
Dimenticare righe: con 3 lettere sono 8, non 6.
Applicare il «non» a tutta la formula quando riguarda una lettera sola.
Negare «tutti» con «nessuno».
Considerare proposizioni le frasi con una variabile libera.

§12

Esercizi

con soluzioni

1 · Riscaldamento: proposizione o no? base

Dì quali frasi sono proposizioni e, per quelle che lo sono, se sono vere o false: (a) « $3 \cdot 4 = 12$ .» (b) «Ricordati di comprare il latte.» (c) «Il numero $x^{2}$ è positivo.» (d) «Roma è più a nord di Milano.» (e) «Che bello questo esercizio!»

Soluzione

(a) Proposizione vera. (b) Non è una proposizione: è un ordine. (c) Non è una proposizione: dipende da $x$ , e con $x = 0$ sarebbe falsa. (d) Proposizione falsa. (e) Non è una proposizione: è un'esclamazione.

2 · Riscaldamento: i tre connettivi base

Con $p$ = V, $q$ = F e $r$ = V, calcola: (a) $p \land r$ ; (b) $q \lor r$ ; (c) $\neg p \lor q$ ; (d) $\neg (q \land r)$ ; (e) $p \oplus r$ .

Soluzione

(a) V $\land$ V = V. (b) F $\lor$ V = V. (c) $\neg p$ = F, e F $\lor$ F = F. (d) $q \land r$ = F, quindi la negazione è V. (e) V $\oplus$ V = F: valori uguali.

3 · Riscaldamento: quante righe base

Quante righe hanno le tavole di (a) $\neg p$ ; (b) $p \land q$ ; (c) $(p \lor q) \land \neg p$ ; (d) $(p \land q) \lor (r \land s) \lor t$ ?

Soluzione

Contano le lettere diverse, non quante volte compaiono. (a) 1 lettera: 2 righe. (b) 2 lettere: 4 righe. (c) 2 lettere, perché $p$ compare due volte: 4 righe. (d) 5 lettere: $2^{5} = 32$ righe.

4 · Riscaldamento: negare bene base

Scrivi la negazione di queste frasi: (a) «Ho almeno 18 anni.» (b) «Sono uscite 10 teste su 10 lanci.» (c) «Nessuno è arrivato in ritardo.» (d) « $x < 7$ .»

Soluzione

(a) «Ho meno di 18 anni.» (b) «È uscita almeno una croce.» (c) «Almeno una persona è arrivata in ritardo.» (d) « $x \geq 7$ »: non va dimenticato il caso $x = 7$ .

5 · Tavole dagli esercizi del libro medio

Costruisci le tavole di $p \land \neg q$ e di $(p \land q) \land \neg q$ . Che cosa noti nella seconda?

Soluzione

$p$	$q$	$\neg q$	$p \land \neg q$	$p \land q$	$(p \land q) \land \neg q$
V	V	F	F	V	F
V	F	V	V	F	F
F	V	F	F	F	F
F	F	V	F	F	F

La prima è vera solo nella riga $p$ = V, $q$ = F. La seconda è falsa in tutte le righe: è una contraddizione. Quando $p \land q$ è vera, $q$ è vera e quindi $\neg q$ è falsa. Sono le stesse tavole delle soluzioni del libro.

6 · Le parentesi contano medio

Costruisci le tavole di $p \lor (q \land r)$ e di $(p \lor q) \land r$ . In quali righe sono diverse?

Soluzione

$p$	$q$	$r$	$q \land r$	$p \lor (q \land r)$	$p \lor q$	$(p \lor q) \land r$
V	V	V	V	V	V	V
V	V	F	F	V	V	F
V	F	V	F	V	V	V
V	F	F	F	V	V	F
F	V	V	V	V	V	V
F	V	F	F	F	V	F
F	F	V	F	F	F	F
F	F	F	F	F	F	F

Sono diverse nella riga 2 ( $p$ = V, $q$ = V, $r$ = F) e nella riga 4 ( $p$ = V, $q$ = F, $r$ = F). In tutte e due $p$ è vera e $r$ è falsa: la prima formula si accontenta di $p$ , la seconda chiede anche $r$ .

7 · Dalle formule alle frasi medio

Con $p$ : «oggi è lunedì», $q$ : «piove», $r$ : «fa caldo», scrivi in italiano: (a) $p \lor q$ ; (b) $\neg p \land (q \lor r)$ ; (c) $\neg (p \lor q) \lor r$ .

Soluzione

(a) «Oggi è lunedì o piove.»

(b) «Oggi non è lunedì, e piove o fa caldo.»

(c) «Non è vero che oggi è lunedì o piove, oppure fa caldo.» Si può anche dire: «oggi non è lunedì e non piove, oppure fa caldo».

8 · Dalle frasi alle formule medio

Con $p$ : «gioco a calcio», $q$ : «salto l'esame di metà corso», $r$ : «passo l'esame», traduci: (a) «Gioco a calcio e salto l'esame di metà corso.» (b) «Non gioco a calcio ma passo l'esame.» (c) «Né gioco a calcio né salto l'esame di metà corso.» (d) «Gioco a calcio o salto l'esame di metà corso, e non passo l'esame.»

Soluzione

(a) $p \land q$ . (b) $\neg p \land r$ . (c) $\neg p \land \neg q$ . (d) $(p \lor q) \land \neg r$ : qui la virgola dice che «e non passo» vale per tutta la prima parte.

9 · Valore in ogni riga tipo esame

Considera la formula $\neg (A \land \neg B) \lor (A \land B)$ . Dai il suo valore nelle righe: $A$ = V, $B$ = V; $A$ = V, $B$ = F; $A$ = F, $B$ = F; $A$ = F, $B$ = V.

Soluzione

$A$	$B$	$A \land \neg B$	$\neg (A \land \neg B)$	$A \land B$	formula
V	V	F	V	V	V
V	F	V	F	F	F
F	F	F	V	F	V
F	V	F	V	F	V

Le risposte sono V, F, V, V. La formula è falsa solo quando $A$ è vera e $B$ è falsa. Nella prossima lezione vedrai che questa è proprio la tavola di «se $A$ allora $B$ ».

10 · Una formula sempre falsa tipo esame

Mostra che $(p \lor q) \land (\neg p \lor q) \land (p \lor \neg q) \land (\neg p \lor \neg q)$ è falsa in tutte le righe. Prova a spiegarlo senza la tavola.

Soluzione

Con la tavola: in ogni riga uno dei quattro pezzi è falso. Con $p$ = V, $q$ = V è falso $\neg p \lor \neg q$ ; con V, F è falso $\neg p \lor q$ ; con F, V è falso $p \lor \neg q$ ; con F, F è falso $p \lor q$ .

A parole: i quattro pezzi escludono ciascuno una delle quattro righe. Ogni pezzo è falso solo quando sono false tutte e due le sue parti, e i quattro pezzi coprono le quattro combinazioni. La congiunzione chiede che nessuna riga sia esclusa: impossibile. È la soluzione del libro, che dà questa tavola tutta falsa.

11 · L'«o» esclusivo con «e», «o» e «non» difficile

Trova due formule che usano solo $\land$ , $\lor$ e $\neg$ e hanno la stessa tavola di $p \oplus q$ . Controllale con lo strumento in modalità equivalenza.

Soluzione

$p \oplus q$ è vera nelle righe ( $p$ = V, $q$ = F) e ( $p$ = F, $q$ = V).

La prima riga è descritta da $p \land \neg q$ , la seconda da $\neg p \land q$ . Unendole con «o»: $(p \land \neg q) \lor (\neg p \land q)$ .
A parole, «almeno uno, ma non tutti e due»: $(p \lor q) \land \neg (p \land q)$ .

Il metodo della prima formula, una congiunzione per ogni riga vera e poi tutte unite con «o», funziona per qualunque tavola. È lo stesso dei quiz «dalla tabella alla formula» sui circuiti, nella lezione 05.

§13

Domande di ripasso

autoverifica

Che cos'è una proposizione? Fai un esempio e un controesempio.

Una frase che è vera o falsa, ma non tutte e due. «7 è primo» è una proposizione; «chiudi la porta» no, perché è un ordine.

Quando è vera

p \land q

? E

p \lor q

$p \land q$ è vera solo quando $p$ e $q$ sono vere tutte e due. $p \lor q$ è vera quando almeno una delle due è vera, anche tutte e due.

Che differenza c'è tra

p \lor q

p \oplus q

Differiscono solo quando $p$ e $q$ sono vere tutte e due: $p \lor q$ è vera, $p \oplus q$ è falsa. L'«o» esclusivo è vero quando i valori sono diversi.

Quante righe ha la tavola di una formula con 3 lettere? Come si ordinano?

$2^{3} = 8$ righe. La prima lettera è V nelle prime 4 righe e F nelle altre 4; la seconda alterna a coppie; la terza alterna a ogni riga.

In che ordine si calcolano i connettivi senza parentesi?

Prima $\neg$ , poi $\land$ , poi $\lor$ . Quindi $\neg p \lor q \land r$ si legge $(\neg p) \lor (q \land r)$ .

Come si traduce «né

p

né

q

»? È uguale a

\neg p \lor \neg q

Si traduce $\neg p \land \neg q$ : tutte e due false. Non è uguale a $\neg p \lor \neg q$ , che è vera anche quando una sola è falsa.

Che cosa sono una tautologia e una contraddizione?

Una tautologia è una formula vera in tutte le righe della tavola, come $p \lor \neg p$ . Una contraddizione è falsa in tutte le righe, come $p \land \neg p$ .

Qual è la negazione di «ho fatto tutti gli esercizi»?

«Almeno un esercizio non l'ho fatto.» Non «non ho fatto nessun esercizio».

§14

Glossario

termini

Proposizione: Una frase che è vera oppure falsa, ma non tutte e due.
Valore di verità: Vero o falso: V o F, nel libro T o F, nei circuiti 1 o 0.
Connettivo: Una parola che costruisce una proposizione da altre: «e», «o», «non», «o esclusivo».
Congiunzione: $p \land q$ , « $p$ e $q$ »: vera solo se tutte e due sono vere.
Disgiunzione: $p \lor q$ , « $p$ o $q$ »: vera se almeno una è vera; è l'«o» inclusivo.
O esclusivo: $p \oplus q$ : vera se esattamente una delle due è vera.
Negazione: $\neg p$ , «non $p$ »: vera quando $p$ è falsa.
Formula: Un'espressione fatta di lettere, connettivi e parentesi; si chiama anche proposizione composta.
Tavola di verità: La tabella dei valori di una formula in tutte le combinazioni dei valori delle lettere.
Tautologia: Una formula vera in tutte le righe della sua tavola.
Contraddizione: Una formula falsa in tutte le righe della sua tavola.

§15

Checklist

0 su 9

Spunta quando sai fare la cosa senza guardare gli appunti. Le spunte restano salvate in questo browser.

So dire se una frase è una proposizione, e perché domande, ordini e frasi con variabili non lo sono.
So le tavole di $\land$ , $\lor$ , $\neg$ e $\oplus$ , e so collegarle alle porte logiche della lezione 01.
So che l'«o» della logica è inclusivo, e quando una frase intende quello esclusivo.
So negare una frase senza confondere il contrario con l'opposto.
So in che ordine si calcolano $\neg$ , $\land$ e $\lor$ , e metto le parentesi nel dubbio.
So costruire la tavola di una formula con $2^{n}$ righe nell'ordine del libro.
So calcolare il valore di una formula in una riga, partendo da dentro.
So tradurre «ma», «né… né», «non è vero che» in formule.
So riconoscere una tautologia e una contraddizione.

La lezione in 7 punti

Frasi che sono vere o false

Le lettere al posto delle frasi

Unire le frasi: «e», «o», «non»

«E»: tutte e due

«O»: almeno una

«Non»: il contrario

Le tavole dei connettivi

L'«o» esclusivo

Negare una frase senza sbagliare

Formule e parentesi

Le parentesi cambiano il senso

L'ordine dei connettivi

La tavola di verità di una formula

Quante righe

L'ordine delle righe

Prova tu con lo strumento

Formule sempre vere e sempre false

Il valore in una sola riga

Dall'italiano alle formule

I simboli di questa lezione

Verso l'esame

Una domanda nello stile del quiz, letta insieme

Quiz

Esercizi

1 · Riscaldamento: proposizione o no? base

2 · Riscaldamento: i tre connettivi base

3 · Riscaldamento: quante righe base

4 · Riscaldamento: negare bene base

5 · Tavole dagli esercizi del libro medio

6 · Le parentesi contano medio

7 · Dalle formule alle frasi medio

8 · Dalle frasi alle formule medio

9 · Valore in ogni riga tipo esame

10 · Una formula sempre falsa tipo esame

11 · L'«o» esclusivo con «e», «o» e «non» difficile

Domande di ripasso

Glossario

Checklist