Canale B · Lezione 07 · Libro, parte 2, §1.3

«Se… allora», «se e solo se» ed equivalenza logica

«Se vinciamo, offro la pizza» è una promessa: quando è stata infranta? Da questa domanda nasce la tavola del «se… allora», il connettivo più importante della logica. Poi il «se e solo se», e il modo di capire quando due frasi diverse dicono la stessa cosa.

Libro: Johnsonbaugh, Brookshear, Brylow, Fondamenti dell'Informatica, parte 2 (Johnsonbaugh, cap. 1), §1.3
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

«Se… allora…» si scrive con una freccia, $p \to q$ . È falsa in un solo caso: quando la prima parte, l'ipotesi, è vera e la seconda, la conclusione, è falsa. Come una promessa, infranta solo se la condizione si avvera e la promessa non è mantenuta.
Quando l'ipotesi è falsa, la frase è vera, qualunque cosa dica la conclusione: è vera a vuoto.
L'ipotesi è una condizione sufficiente, la conclusione una condizione necessaria. Nelle frasi con «solo se», quello che segue «solo se» è la conclusione.
Scambiare ipotesi e conclusione cambia il senso. La contronominale, «se non $q$ allora non $p$ », invece dice la stessa cosa.
«Se e solo se», scritto con la doppia freccia $\leftrightarrow$ , è vero quando le due parti hanno lo stesso valore.
Due formule sono logicamente equivalenti quando hanno la stessa tavola di verità. Le più usate sono le leggi di De Morgan: negare un «e» dà un «o» di negazioni, e viceversa.
All'esame: la simulazione 1 del 2023/24 chiede il valore di $(A \to B) \leftrightarrow (B \to A)$ riga per riga.

Canali A, B e C

Nel canale B è la lezione di giovedì 15/10, dalle 9 alle 11. Per il docente è la lezione 8, perché la prima è stata un'introduzione: qui è la 07. Il diario del canale B la annuncia così: «Capitolo 1.3 (Parte 2). Proposizioni condizionali e equivalenza logica.» Ho scritto questi appunti prima della lezione, sul §1.3 del libro, con le sue domande di ripasso e le soluzioni degli esercizi pubblicate sul Moodle del canale A (id 3851, aperto agli ospiti). Il diario del docente non dice altro su che cosa è stato fatto in aula. Si parte dalla lezione 06: proposizioni, connettivi e tavole di verità. Nel canale A gli stessi argomenti sono nelle dispense di Felice Cardone; nel canale C nei lucidi del docente.

§1

Una promessa: «se… allora»

libro, §1.3

Prima della partita il capitano dice alla squadra: «Se vinciamo, allora offro la pizza a tutti». Dopo la partita, quando si può dire che ha mentito?

Vinciamo?	Offre la pizza?	Ha mantenuto la promessa?
sì	sì	sì
sì	no	no
no	sì	sì
no	no	sì

C'è un solo caso in cui la promessa è infranta: la squadra vince e la pizza non arriva. Se la squadra perde, il capitano non ha promesso niente: può offrire la pizza lo stesso per consolare tutti, o non offrirla. In tutti e due i casi non ha mentito.

L'idea

«Se… allora…» non dice che la prima cosa succede, e non dice che succede la seconda. Dice soltanto una cosa: non può capitare che la prima sia vera e la seconda falsa.

Con le lettere: $p$ è «vinciamo», $q$ è «offro la pizza». La promessa si scrive $p \to q$ . Si legge «se pi allora cu», oppure «pi implica cu».

Definizione · Proposizione condizionale (libro, §1.3)

Se $p$ e $q$ sono proposizioni, la proposizione «se $p$ allora $q$ » si chiama proposizione condizionale e si scrive $p \to q$ . La proposizione $p$ è l'ipotesi (o antecedente) e $q$ è la conclusione (o conseguente). La proposizione $p \to q$ è falsa quando $p$ è vera e $q$ è falsa; è vera in tutti gli altri casi.

Come si legge. La tavola è quella della promessa, con V e F:

$p$	$q$	$p \to q$
V	V	V
V	F	F
F	V	V
F	F	V

La riga da ricordare è la seconda: ipotesi vera e conclusione falsa. È l'unica F.

Le righe con l'ipotesi falsa

Le righe 3 e 4 sorprendono sempre. «Se $2 + 2 = 5$ , allora la Luna è di formaggio» è vera: l'ipotesi è falsa, e una promessa con la condizione che non si avvera non si può smentire. In questo caso l'implicazione è vera a vuoto.

In matematica serve proprio così. Pensa alla frase «per ogni numero, se è maggiore di 2 ed è primo, allora è dispari». Per il numero 4 l'ipotesi è falsa: la frase non dice niente su 4, e non deve diventare falsa per colpa sua.

Trappola · «Se… allora» non vuol dire «perché»

In italiano «se… allora» fa pensare a una causa. In logica conta solo il valore di verità delle due parti. «Se Torino è in Piemonte, allora $2 + 2 = 4$ » è vera: le due frasi sono vere, anche se non hanno niente a che fare l'una con l'altra.

Un modo di scriverla con «o» e «non»

Guarda di nuovo la tavola: la promessa è vera quando la squadra perde, oppure quando la pizza arriva. Quindi $p \to q$ ha la stessa tavola di $\neg p \lor q$ . In C non c'è un operatore per «se… allora» tra due condizioni: si scrive !p || q.

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

È l'esercizio 80 del §1.3, nelle soluzioni del libro, e nell'esercizio d'esame della lezione 06 l'avevi già incontrata con un'altra forma.

Prova tu

Quanto valgono queste implicazioni? (a) «Se 7 è pari, allora 7 è primo.» (b) «Se 7 è primo, allora 7 è pari.» (c) «Se

3 < 5

, allora

5 > 3

.»

(a) Vera a vuoto: l'ipotesi «7 è pari» è falsa. (b) Falsa: ipotesi vera, conclusione falsa. (c) Vera: ipotesi e conclusione sono tutte e due vere.

Da ricordare

Il «se… allora» è falso solo con l'ipotesi vera e la conclusione falsa.
Con l'ipotesi falsa l'implicazione è vera, a vuoto.
$p \to q$ ha la stessa tavola di $\neg p \lor q$ .

§2

Tanti modi di dire «se… allora»

libro, §1.3

In italiano la stessa promessa si può dire in molti modi. Il libro dedica a questo diversi esercizi, ed è una delle cose su cui si sbaglia di più.

Condizione sufficiente e condizione necessaria

Nella promessa del capitano, vincere basta per avere la pizza: è una condizione sufficiente. Al contrario, la pizza è una conseguenza obbligata della vittoria: se manca la pizza, la squadra non ha vinto. Per questo la pizza è una condizione necessaria per la vittoria.

L'idea

In un «se… allora», l'ipotesi è sufficiente per la conclusione: se c'è l'ipotesi, c'è anche la conclusione. La conclusione è necessaria per l'ipotesi: senza la conclusione, niente ipotesi.

Le domande di ripasso del libro lo dicono proprio così: nella frase $p \to q$ , la conclusione è una condizione necessaria e l'ipotesi è una condizione sufficiente.

La tabella delle traduzioni

In italiano	Formula
se $p$ allora $q$	$p \to q$
$q$ se $p$	$p \to q$
$p$ solo se $q$	$p \to q$
$p$ è condizione sufficiente per $q$	$p \to q$
$q$ è condizione necessaria per $p$	$p \to q$
$q$ ogni volta che $p$	$p \to q$

Trappola · «Solo se» mette la freccia nel verso che non ti aspetti

«Passi l'esame solo se studi» non promette che chi studia passa. Dice che chi passa ha studiato: passi $\to$ studi. La frase è smentita solo da chi passa senza aver studiato. Il «solo se» introduce la condizione necessaria, che va a destra della freccia.

Esempio · Frasi con «solo se», tradotte

Le soluzioni degli esercizi del libro traducono frasi di questo tipo così:

«Puoi ispezionare l'aereo solo se hai l'autorizzazione»: se ispezioni l'aereo, allora hai l'autorizzazione.
«Il programma è leggibile solo se è ben strutturato»: se il programma è leggibile, allora è ben strutturato.

In tutte e due la frase dopo «solo se» va dopo l'«allora».

Prova tu

Con

p

: «piove» e

q

: «prendo l'ombrello», traduci: (a) «Prendo l'ombrello se piove.» (b) «Prendo l'ombrello solo se piove.» (c) «Che piova è condizione sufficiente perché prenda l'ombrello.»

(a) $p \to q$ : «se piove, prendo l'ombrello». (b) $q \to p$ : se prendo l'ombrello, allora piove. (c) $p \to q$ : la condizione sufficiente è l'ipotesi.

Da ricordare

Condizione sufficiente: l'ipotesi, a sinistra della freccia. Condizione necessaria: la conclusione, a destra.
«Solo se» introduce la conclusione: «passo solo se studio» è «se passo, allora ho studiato».

§3

Girare la promessa: inversa e contronominale

libro, §1.3

Dalla promessa «se vinciamo, offro la pizza» se ne possono costruire altre tre, girandola o negandola. Una sola dice la stessa cosa.

Nome	Formula	La promessa diventa
la promessa	$p \to q$	se vinciamo, offro la pizza
inversa	$q \to p$	se offro la pizza, abbiamo vinto
contraria	$\neg p \to \neg q$	se non vinciamo, non offro la pizza
contronominale	$\neg q \to \neg p$	se non offro la pizza, non abbiamo vinto

Pensa al caso in cui la squadra perde e il capitano offre lo stesso la pizza. La promessa resta vera. L'inversa no: c'è la pizza ma non la vittoria. Anche la contraria è falsa: non abbiamo vinto, e la pizza c'è. La contronominale invece resta vera, perché la pizza è arrivata.

Trappola · I nomi cambiano da libro a libro

Il libro, in inglese, chiama converse la formula $q \to p$ e contrapositive la formula $\neg q \to \neg p$ . In italiano $q \to p$ si trova chiamata «inversa» o «conversa», e $\neg q \to \neg p$ «contronominale» o «contrapposta». Ricorda le formule: l'unica che dice la stessa cosa di $p \to q$ è $\neg q \to \neg p$ .

La tavola lo conferma: la colonna di $p \to q$ e quella di $\neg q \to \neg p$ sono uguali, le altre due no.

$p$	$q$	$p \to q$	$q \to p$	$\neg p \to \neg q$	$\neg q \to \neg p$
V	V	V	V	V	V
V	F	F	V	V	F
F	V	V	F	F	V
F	F	V	V	V	V

Esempio · Con i numeri (esercizio 59 del libro, dalle soluzioni)

Prendi $p$ : « $4 < 6$ », che è vera, e $q$ : « $9 > 12$ », che è falsa.

La frase $p \to q$ , «se $4 < 6$ allora $9 > 12$ », è falsa: ipotesi vera, conclusione falsa.
L'inversa $q \to p$ , «se $9 > 12$ allora $4 < 6$ », è vera: l'ipotesi è falsa.
La contronominale $\neg q \to \neg p$ , «se $9 \leq 12$ allora $4 \geq 6$ », è falsa, come la frase di partenza.

Nella prossima parte del libro questa equivalenza diventa un modo di dimostrare: invece di una frase, a volte è più facile dimostrare la sua contronominale. Si chiama dimostrazione per contrapposizione.

Prova tu

Scrivi l'inversa e la contronominale di «se un numero è divisibile per 4, allora è pari». Quale delle due è vera?

Inversa: «se un numero è pari, allora è divisibile per 4». È falsa: 6 è pari ma non divisibile per 4. Contronominale: «se un numero non è pari, allora non è divisibile per 4». È vera, come la frase di partenza.

Da ricordare

La contronominale $\neg q \to \neg p$ dice la stessa cosa di $p \to q$ .
L'inversa $q \to p$ no: è l'errore più comune.

§4

«Se e solo se»

libro, §1.3

A volte la promessa vale nei due versi. Il regolamento del torneo dice: «Una squadra va in finale se e solo se vince la semifinale». Chi vince va in finale, e chi va in finale ha vinto. Le due frasi sono sempre insieme: tutte e due vere, o tutte e due false.

Definizione · Proposizione bicondizionale (libro, §1.3)

Se $p$ e $q$ sono proposizioni, la proposizione « $p$ se e solo se $q$ » si chiama proposizione bicondizionale e si scrive $p \leftrightarrow q$ . È vera quando $p$ e $q$ sono tutte e due vere o tutte e due false, e falsa negli altri casi.

Come si legge. Il «se e solo se» è vero quando le due parti hanno lo stesso valore.

$p$	$q$	$p \leftrightarrow q$
V	V	V
V	F	F
F	V	F
F	F	V

Il nome dice già come è fatta: «se» è una freccia in un verso, «solo se» è la freccia nell'altro verso. Insieme, $p \leftrightarrow q$ ha la stessa tavola di $(p \to q) \land (q \to p)$ . In matematica si scrive spesso «sse».

Rispetto all'«o» esclusivo della lezione 06 è il contrario: $p \oplus q$ è vera quando i valori sono diversi, $p \leftrightarrow q$ quando sono uguali.

Prova tu

Quanto valgono «

2 + 2 = 4

se e solo se

3

è dispari» e «

2 + 2 = 5

se e solo se

3

è pari»?

La prima è vera: tutte e due le parti sono vere. Anche la seconda è vera: tutte e due le parti sono false.

Da ricordare

Il «se e solo se» è vero quando le due parti hanno lo stesso valore.
«Se e solo se» sono due implicazioni insieme, nei due versi.

§5

Quando due frasi dicono la stessa cosa

libro, §1.3

«Se non offro la pizza, non abbiamo vinto» e «se vinciamo, offro la pizza» sono scritte in modo diverso, ma in ogni situazione sono vere o false insieme. Sono logicamente equivalenti.

Definizione · Equivalenza logica (libro, §1.3)

Siano $P$ e $Q$ proposizioni composte dalle stesse proposizioni $p_{1}, \dots, p_{n}$ . $P$ e $Q$ sono logicamente equivalenti se, per ogni scelta dei valori di verità di $p_{1}, \dots, p_{n}$ , sono tutte e due vere o tutte e due false. Si scrive $P \equiv Q$ .

Come si legge. $P \equiv Q$ vuol dire: stessa tavola di verità, riga per riga. Per controllarlo si fanno le due tavole e si confrontano le colonne finali. Per smentirlo basta una riga in cui le due formule hanno valori diversi.

Trappola · $\equiv$ e $\leftrightarrow$ non sono la stessa cosa

$\leftrightarrow$ è un connettivo: $p \leftrightarrow q$ è una formula, che in certe righe è vera e in altre falsa. $\equiv$ non sta dentro una formula: è una frase che dici su due formule, «hanno la stessa tavola». Il legame tra i due: $P \equiv Q$ esattamente quando $P \leftrightarrow Q$ è vera in tutte le righe, cioè è una tautologia.

Lo strumento qui sotto confronta due formule e colora in rosso le righe in cui sono diverse. Prova con la promessa e la sua inversa, poi con la contronominale.

Prova tu

Senza tavola:

p \to q

q \to p

sono equivalenti? Trova una riga che lo decida.

No. Con $p$ = V e $q$ = F la prima è falsa e la seconda è vera. Basta questa riga.

Da ricordare

$P \equiv Q$ : stessa tavola di verità.
Per dire che non sono equivalenti basta una riga diversa.

§6

Le leggi di De Morgan

libro, §1.3

Il capitano dice: «Offro la pizza e il gelato». Quando non ha mantenuto la parola? Quando manca la pizza, oppure quando manca il gelato, o tutti e due. Negare un «e» dà un «o» di negazioni.

Al contrario: «Vado al mare o in montagna». Quando è falso? Solo se non vado né al mare né in montagna. Negare un «o» dà un «e» di negazioni.

Teorema · Leggi di De Morgan (libro, §1.3)

\neg (p \lor q) \equiv \neg p \land \neg q e \neg (p \land q) \equiv \neg p \lor \neg q .

Come si legge. Per negare una frase con «e» o con «o»: si nega ogni pezzo, e si scambia il connettivo. La negazione di un «o» è un «e», la negazione di un «e» è un «o».

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

Esempio · Negare in italiano (esercizi 73 e 76 del libro, dalle soluzioni)

La negazione di «Pat userà il tapis roulant o solleverà pesi» è «Pat non userà il tapis roulant e non solleverà pesi».
La negazione di «per il chili servono il peperoncino e la cipolla» è «per il chili non serve il peperoncino o non serve la cipolla».

Trappola · De Morgan a metà

L'errore tipico è negare i pezzi e dimenticare di scambiare il connettivo. $\neg (p \land q)$ non è $\neg p \land \neg q$ . «Non è vero che ho la pizza e il gelato» non vuol dire «non ho né la pizza né il gelato»: basta che manchi uno dei due.

Negare un «se… allora»

Quando è falsa la promessa «se vinciamo, offro la pizza»? Solo quando vinciamo e la pizza non c'è. Quindi la negazione di un'implicazione non è un'implicazione:

\neg (p \to q) \equiv p \land \neg q .

La negazione di «se studi, passi l'esame» è «studi e non passi l'esame». Non è «se non studi, passi», e non è «se studi, non passi». Le dispense del canale A lo fanno dimostrare come esercizio.

Prova tu

Scrivi la negazione senza usare «non è vero che»: (a) «Piove e fa freddo.» (b) «Vado al cinema o a teatro.» (c) «Se piove, resto a casa.»

(a) «Non piove oppure non fa freddo.» (b) «Non vado né al cinema né a teatro.» (c) «Piove e non resto a casa.»

Da ricordare

De Morgan: negando, si negano i pezzi e si scambia «e» con «o».
La negazione di $p \to q$ è $p \land \neg q$ .

§7

Le equivalenze da sapere

Le equivalenze servono come le regole dell'algebra: permettono di trasformare una formula in un'altra più comoda, un passo alla volta, senza fare la tavola. Eccole tutte; ognuna si controlla con una tavola o con lo strumento.

Nome	Equivalenza
doppia negazione	$\neg\neg p \equiv p$
De Morgan	$\neg (p \land q) \equiv \neg p \lor \neg q$ e $\neg (p \lor q) \equiv \neg p \land \neg q$
commutative	$p \land q \equiv q \land p$ e $p \lor q \equiv q \lor p$
associative	$(p \land q) \land r \equiv p \land (q \land r)$ , e lo stesso con $\lor$
distributive	$p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$ e $p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$
«se» come «o»	$p \to q \equiv \neg p \lor q$
negare un «se»	$\neg (p \to q) \equiv p \land \neg q$
contronominale	$p \to q \equiv \neg q \to \neg p$
«se e solo se»	$p \leftrightarrow q \equiv (p \to q) \land (q \to p)$

L'ordine dei connettivi

Alla regola della lezione 06 si aggiungono le due frecce, che vengono per ultime. Senza parentesi si calcola:

prima $\neg$ ;
poi $\land$ ;
poi $\lor$ ;
poi $\to$ ;
per ultimo $\leftrightarrow$ .

Quindi $p \land q \to r$ vuol dire $(p \land q) \to r$ . Anche qui, nel dubbio, si mettono le parentesi.

Esempio · Una formula trasformata passo per passo

$\neg (p \to \neg q)$ è equivalente a che cosa?

Negare un «se»: $\neg (p \to \neg q) \equiv p \land \neg\neg q$ .
Doppia negazione: $p \land \neg\neg q \equiv p \land q$ .

Quindi $\neg (p \to \neg q) \equiv p \land q$ . A parole: «non è vero che, se $p$ , allora non $q$ » vuol dire « $p$ e $q$ ».

Tautologie con le frecce

Una tautologia è una formula vera in tutte le righe (lezione 06). Con le frecce ce ne sono di molto utili.

Formula	Che cosa dice
$(p \land (p \to q)) \to q$	se $p$ è vera e $p$ implica $q$ , allora $q$ è vera
$((p \to q) \land (q \to r)) \to (p \to r)$	le implicazioni si possono mettere in fila
$p \to (p \lor q)$	da $p$ segue « $p$ o qualunque cosa»
$(p \to q) \lor (q \to p)$	tra due frasi, una implica l'altra

Le prime due saranno le regole di inferenza della prossima lezione. Una formula che sembra una tautologia ma non lo è: $(p \to q) \to (q \to p)$ . Con $p$ = F e $q$ = V è falsa. Dall'implicazione non segue la sua inversa.

Prova tu

Con lo strumento qui sopra, controlla se

(p \to q) \to (q \to p)

è una tautologia. In quale riga è falsa?

Non è una tautologia: è falsa nella riga $p$ = F, $q$ = V. Lì $p \to q$ è vera, a vuoto, e $q \to p$ è falsa.

Da ricordare

Le equivalenze trasformano una formula in un'altra con la stessa tavola, come le regole dell'algebra.
Ordine senza parentesi: prima «non», poi «e», poi «o», poi le due frecce.

§8

I simboli di questa lezione

Simbolo	Si legge	Vuol dire	Esempio
$p \to q$	«se $p$ allora $q$ », « $p$ implica $q$ »	falsa solo con $p$ vera e $q$ falsa	V $\to$ F = F
$p \leftrightarrow q$	« $p$ se e solo se $q$ »	vera quando i valori sono uguali	F $\leftrightarrow$ F = V
$P \equiv Q$	« $P$ è equivalente a $Q$ »	$P$ e $Q$ hanno la stessa tavola	$p \to q \equiv \neg p \lor q$
$q \to p$	«inversa»	girare la freccia: non equivalente
$\neg q \to \neg p$	«contronominale»	equivalente a $p \to q$
sse	«se e solo se»	abbreviazione di $\leftrightarrow$
`!p \\|\\| q`	«not p or q»	l'implicazione scritta in C

§9

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

Il valore di una formula con le frecce, riga per riga. È il quiz 3 della simulazione 1 del 2023/24, svolto qui sotto.
Riconoscere formule equivalenti. Nel quiz 6 della stessa simulazione bisogna capire che due formule di un circuito hanno la stessa tavola: con De Morgan bastano due passi.
Tradurre e negare: «solo se», «condizione necessaria», la negazione di un «se… allora». Torneranno con i quantificatori, nella simulazione 2.

Una domanda vera, letta insieme

Simulazione d'esame 1 del 2023/24, domanda 3. Il testo: «Considera la formula $(A \to B) \leftrightarrow (B \to A)$ . Seleziona il valore della formula in ogni riga della tabella.» Le righe sono, in quest'ordine: $A$ = T, $B$ = T; $A$ = T, $B$ = F; $A$ = F, $B$ = F; $A$ = F, $B$ = T. Nel quiz T sta per vero.

In pratica chiede: quattro valori, uno per riga. Le righe non sono nell'ordine solito: l'ultima è $A$ falsa e $B$ vera.

Esempio · la soluzione, passo per passo

Passo 1: i due pezzi. In ogni riga calcolo $A \to B$ e $B \to A$ . Ognuno è falso solo con l'ipotesi vera e la conclusione falsa.

$A$	$B$	$A \to B$	$B \to A$	formula
V	V	V	V	V
V	F	F	V	F
F	F	V	V	V
F	V	V	F	F

Passo 2: il «se e solo se». È vero quando i due pezzi hanno lo stesso valore: righe 1 e 3.

Passo 3: la risposta. Nell'ordine del quiz: T, F, T, F. Le risposte scritte a mano nella simulazione svolta che circola tra gli studenti sono le stesse.

Osservazione: la formula è vera esattamente quando $A$ e $B$ hanno lo stesso valore. È equivalente ad $A \leftrightarrow B$ .

Il circuito con De Morgan

Nella domanda 6 della stessa simulazione il circuito calcola $(\neg C \land A) \lor (\neg C \land B)$ , e una delle risposte giuste è la formula $\neg ((C \lor \neg A) \land (C \lor \neg B))$ . Nella lezione 05 l'ho controllata riga per riga. Con De Morgan bastano due passi:

$\neg ((C \lor \neg A) \land (C \lor \neg B)) \equiv \neg (C \lor \neg A) \lor \neg (C \lor \neg B)$ , negando un «e»;
ciascun pezzo è la negazione di un «o»: $\neg (C \lor \neg A) \equiv \neg C \land A$ , e allo stesso modo l'altro.

Si arriva a $(\neg C \land A) \lor (\neg C \land B)$ : è la formula del circuito.

Metodo · Le domande sulle frecce e sulle equivalenze

Valore in una riga: per ogni freccia guarda solo la combinazione «ipotesi V, conclusione F», che è l'unica falsa.
Equivalenti? Prima cerca una riga che le distingua: se la trovi, hai finito. Se non la trovi, fai la tavola o usa le equivalenze.
Negare: De Morgan scambia «e» e «o»; la negazione di $p \to q$ è $p \land \neg q$ .
Tradurre: chi viene dopo «solo se» va a destra della freccia.

Errori da evitare

Credere che $p \to q$ sia falsa quando $p$ è falsa: è vera.
Confondere $p \to q$ con l'inversa $q \to p$ .
Girare la freccia nelle frasi con «solo se».
Negare $p \to q$ con $\neg p \to \neg q$ .
Applicare De Morgan senza scambiare il connettivo.
Usare $\equiv$ dentro una formula al posto di $\leftrightarrow$ .

§11

Esercizi

con soluzioni

1 · Riscaldamento: il valore delle frecce base

Calcola $p \to q$ , $q \to p$ e $p \leftrightarrow q$ con: (a) $p$ : « $3 > 5$ », $q$ : « $2$ è pari»; (b) $p$ : « $7$ è primo», $q$ : « $7$ è pari»; (c) $p$ : « $1 > 2$ », $q$ : « $1 > 3$ ».

Soluzione

(a) $p$ = F, $q$ = V: $p \to q$ = V, $q \to p$ = F, $p \leftrightarrow q$ = F.

(b) $p$ = V, $q$ = F: $p \to q$ = F, $q \to p$ = V, $p \leftrightarrow q$ = F.

2 · Riscaldamento: tradurre con «se» base

Con $p$ : «Giada studia» e $q$ : «Giada passa l'esame», traduci: (a) «Se Giada studia, passa l'esame.» (b) «Giada passa l'esame solo se studia.» (c) «Studiare è condizione necessaria perché Giada passi l'esame.» (d) «Giada passa l'esame se e solo se studia.»

Soluzione

(a) $p \to q$ . (b) $q \to p$ : chi passa ha studiato. (c) $q \to p$ : la condizione necessaria va a destra. (d) $p \leftrightarrow q$ .

3 · Riscaldamento: inversa, contraria, contronominale base

Scrivi l'inversa, la contraria e la contronominale di «se un quadrilatero è un quadrato, allora ha quattro lati uguali». Quali sono vere?

Soluzione

La frase: vera.
Inversa: «se un quadrilatero ha quattro lati uguali, allora è un quadrato». Falsa: un rombo non quadrato ha quattro lati uguali.
Contraria: «se un quadrilatero non è un quadrato, allora non ha quattro lati uguali». Falsa, per lo stesso rombo.
Contronominale: «se un quadrilatero non ha quattro lati uguali, allora non è un quadrato». Vera, come la frase.

4 · Riscaldamento: negare base

Scrivi la negazione di queste frasi senza «non è vero che»: (a) «Gioco e vinco.» (b) «Esco o studio.» (c) «Se c'è il sole, vado al mare.» (d) «Passo solo se studio.»

Soluzione

(a) «Non gioco oppure non vinco.» (b) «Non esco e non studio.» (c) «C'è il sole e non vado al mare.» (d) La frase è «se passo, allora ho studiato»; la negazione è «passo e non ho studiato».

5 · L'esportazione con la tavola medio

Mostra con una tavola di verità che $(p \land q) \to r \equiv p \to (q \to r)$ .

Soluzione

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

La quinta e la settima colonna sono uguali. Tutte e due sono false solo nella riga $p$ = V, $q$ = V, $r$ = F. A parole: «se ho il biglietto e il documento, entro» è lo stesso che «se ho il biglietto, allora, se ho il documento, entro».

6 · Tautologie o no medio

Quali sono tautologie? Per quelle che non lo sono, dai una riga in cui sono false. (a) $(p \to q) \lor (q \to p)$ ; (b) $p \to (p \lor q)$ ; (c) $(p \lor q) \to p$ ; (d) $((p \to q) \land (q \to r)) \to (p \to r)$ .

Soluzione

(a) Tautologia: se $q$ è vera è vera $p \to q$ ; se $q$ è falsa è vera $q \to p$ .

(b) Tautologia: se $p$ è vera, anche $p \lor q$ è vera; se $p$ è falsa, l'implicazione è vera a vuoto.

(d) Tautologia: è la regola delle implicazioni in fila. Controllata con un programma su tutte le 8 righe.

7 · Una formula trasformata medio

Usando solo le equivalenze della tabella, senza tavole, mostra che $(p \to q) \land (p \to r) \equiv p \to (q \land r)$ .

Soluzione

«Se» come «o», due volte: $(p \to q) \land (p \to r) \equiv (\neg p \lor q) \land (\neg p \lor r)$ .
Distributiva letta al contrario: $(\neg p \lor q) \land (\neg p \lor r) \equiv \neg p \lor (q \land r)$ .
«Se» come «o», al contrario: $\neg p \lor (q \land r) \equiv p \to (q \land r)$ .

A parole: «se piove prendo l'ombrello, e se piove metto gli stivali» è lo stesso che «se piove, prendo l'ombrello e metto gli stivali».

8 · Valore in ogni riga tipo esame

Considera la formula $(A \land B) \leftrightarrow (A \to B)$ . Dai il suo valore nelle righe $A$ = V, $B$ = V; $A$ = V, $B$ = F; $A$ = F, $B$ = F; $A$ = F, $B$ = V. A quale formula più corta è equivalente?

Soluzione

$A$	$B$	$A \land B$	$A \to B$	formula
V	V	V	V	V
V	F	F	F	V
F	F	F	V	F
F	V	F	V	F

Le risposte sono V, V, F, F. La formula è vera esattamente quando $A$ è vera: è equivalente ad $A$ .

9 · Vero o falso sulle equivalenze tipo esame

Vero o falso? (1) $\neg (A \to B) \equiv A \land \neg B$ . (2) $A \to B \equiv B \to A$ . (3) $\neg (A \lor B) \equiv \neg A \lor \neg B$ . (4) $A \leftrightarrow B \equiv (A \to B) \land (B \to A)$ . (5) Se $A$ è falsa, $A \to B$ è vera qualunque sia $B$ .

Soluzione

Vero: è la negazione di un «se».
Falso: è l'inversa; con $A$ = V e $B$ = F sono diverse.
Falso: per De Morgan è $\neg A \land \neg B$ .
Vero: «se e solo se» sono due implicazioni.
Vero: è vera a vuoto.

10 · Il quiz del circuito con le equivalenze difficile

Senza tavola, mostra che $(\neg C \lor A) \land (\neg C \lor B)$ non è equivalente a $(\neg C \land A) \lor (\neg C \land B)$ , e trova la riga che lo dimostra. È la risposta b sbagliata della domanda 6 della simulazione 1.

Soluzione

Trasformo la prima con la distributiva letta al contrario: $(\neg C \lor A) \land (\neg C \lor B) \equiv \neg C \lor (A \land B)$ . Trasformo la seconda allo stesso modo: $(\neg C \land A) \lor (\neg C \land B) \equiv \neg C \land (A \lor B)$ .

La prima è vera ogni volta che $C$ è falsa, anche con $A$ e $B$ false. La seconda, con $C$ falsa, chiede anche $A$ o $B$ . Quindi la riga $A$ = F, $B$ = F, $C$ = F le distingue: la prima vale V, la seconda F. È proprio la riga trovata nella lezione 05.

11 · Il contrario di «se e solo se» difficile

Mostra che $\neg (p \leftrightarrow q) \equiv p \oplus q$ , e poi che $p \leftrightarrow q \equiv (p \land q) \lor (\neg p \land \neg q)$ .

Soluzione

$p \leftrightarrow q$ è vera quando i valori sono uguali; la sua negazione è vera quando sono diversi, cioè proprio quando è vera $p \oplus q$ .
$p \leftrightarrow q$ è vera in due righe: tutte e due vere, descritta da $p \land q$ ; tutte e due false, descritta da $\neg p \land \neg q$ . Unendo le due righe con «o» si ottiene una formula vera esattamente in quelle due righe. È il metodo «una riga vera alla volta» della lezione 06.

§12

Domande di ripasso

autoverifica

Quando è falsa

p \to q

? Perché con

p

falsa è vera?

Solo quando $p$ è vera e $q$ è falsa. Con $p$ falsa è vera a vuoto: come una promessa con una condizione che non si avvera, non può essere smentita.

Che cosa sono la condizione necessaria e la condizione sufficiente in

p \to q

$p$ è sufficiente per $q$ : se c'è $p$ , c'è $q$ . $q$ è necessaria per $p$ : senza $q$ non c'è $p$ .

Come si traduce «

p

solo se

q

»?

Con $p \to q$ . Quello che segue «solo se» è la condizione necessaria e va a destra della freccia.

Quali tra inversa, contraria e contronominale sono equivalenti a

p \to q

Solo la contronominale $\neg q \to \neg p$ . L'inversa $q \to p$ e la contraria $\neg p \to \neg q$ non lo sono, ma sono equivalenti tra loro.

Quando è vera

p \leftrightarrow q

? A che cosa è equivalente?

Quando $p$ e $q$ hanno lo stesso valore. È equivalente a $(p \to q) \land (q \to p)$ .

Che cosa vuol dire

P \equiv Q

? Che differenza c'è con

P \leftrightarrow Q

$P \equiv Q$ vuol dire che $P$ e $Q$ hanno la stessa tavola di verità. $P \leftrightarrow Q$ è una formula, che può essere vera in certe righe e falsa in altre; $P \equiv Q$ vale esattamente quando $P \leftrightarrow Q$ è una tautologia.

Che cosa dicono le leggi di De Morgan?

$\neg (p \lor q) \equiv \neg p \land \neg q$ e $\neg (p \land q) \equiv \neg p \lor \neg q$ : per negare si negano i pezzi e si scambia «e» con «o».

Qual è la negazione di

p \to q

$p \land \neg q$ : l'ipotesi è vera e la conclusione è falsa. Non è un'implicazione.

§13

Glossario

termini

Proposizione condizionale: La proposizione $p \to q$ , «se $p$ allora $q$ »: falsa solo con $p$ vera e $q$ falsa.
Ipotesi: In $p \to q$ , la proposizione $p$ ; si chiama anche antecedente.
Conclusione: In $p \to q$ , la proposizione $q$ ; si chiama anche conseguente.
Vera a vuoto: Un'implicazione con l'ipotesi falsa: è vera qualunque sia la conclusione.
Condizione sufficiente: In $p \to q$ , la $p$ : se è vera, è vera anche $q$ .
Condizione necessaria: In $p \to q$ , la $q$ : se è falsa, è falsa anche $p$ .
Inversa: Di $p \to q$ , la formula $q \to p$ ; nel libro converse. Non è equivalente.
Contronominale: Di $p \to q$ , la formula $\neg q \to \neg p$ ; nel libro contrapositive. È equivalente.
Proposizione bicondizionale: La proposizione $p \leftrightarrow q$ , « $p$ se e solo se $q$ »: vera quando i valori sono uguali.
Equivalenza logica: $P \equiv Q$ : le due formule hanno la stessa tavola di verità.
Leggi di De Morgan: $\neg (p \lor q) \equiv \neg p \land \neg q$ e $\neg (p \land q) \equiv \neg p \lor \neg q$ .

§14

Checklist

0 su 9

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

So la tavola di $p \to q$ e so spiegare con la promessa perché è vera quando $p$ è falsa.
So distinguere ipotesi e conclusione, condizione sufficiente e condizione necessaria.
So tradurre «solo se», «se», «condizione necessaria» e «condizione sufficiente».
So scrivere inversa, contraria e contronominale, e so quale è equivalente.
So la tavola di $p \leftrightarrow q$ e so che equivale a due implicazioni.
So controllare se due formule sono equivalenti, e smentirlo con una riga.
So usare le leggi di De Morgan e negare un «se… allora».
So l'ordine dei connettivi: $\neg$ , $\land$ , $\lor$ , $\to$ , $\leftrightarrow$ .
So risolvere il quiz «valore in ogni riga» con le frecce.

La lezione in 7 punti

Una promessa: «se… allora»

Le righe con l'ipotesi falsa

Un modo di scriverla con «o» e «non»

Tanti modi di dire «se… allora»

Condizione sufficiente e condizione necessaria

La tabella delle traduzioni

Girare la promessa: inversa e contronominale

«Se e solo se»

Quando due frasi dicono la stessa cosa

Le leggi di De Morgan

Negare un «se… allora»

Le equivalenze da sapere

L'ordine dei connettivi

Tautologie con le frecce

I simboli di questa lezione

Verso l'esame

Una domanda vera, letta insieme

Il circuito con De Morgan

Quiz

Esercizi

1 · Riscaldamento: il valore delle frecce base

2 · Riscaldamento: tradurre con «se» base

3 · Riscaldamento: inversa, contraria, contronominale base

4 · Riscaldamento: negare base

5 · L'esportazione con la tavola medio

6 · Tautologie o no medio

7 · Una formula trasformata medio

8 · Valore in ogni riga tipo esame

9 · Vero o falso sulle equivalenze tipo esame

10 · Il quiz del circuito con le equivalenze difficile

11 · Il contrario di «se e solo se» difficile

Domande di ripasso

Glossario

Checklist