La Logica di Base (superiori)

Proposizioni

La logica è una disciplina che si occupa del modo corretto di ragionare, ossia del modo corretto di passare da certe premesse a certe conclusioni. La logica matematica è una branca della logica, che utilizza un linguaggio simbolico e un sistema di calcolo di tipo algebrico. Questo tipo di logica, detta anche formale, fornisce uno strumento per formalizzare il linguaggio naturale. La logica proposizionale considera come unità base dello studio le proposizioni. Assumiamo come primitivo, cioè senza darne una definizione, il concetto di proposizione: chiamiamo proposizione una frase (affermativa o negativa) a cui abbia senso associare un valore di verità: vero, V, oppure falso, F (si usano anche i simboli 0 per falso e 1 per vero). Per esempio, sono proposizioni logiche affermazioni del tipo:

• A. «Roma è la capitale d'Italia».
• B. «2+3=10».
• C. «5 è un numero dispari».
• D. «Un triangolo ha quattro angoli».

Le frasi a) e c) sono vere mentre le frasi b) e d) sono false. Tutte quante sono pertanto delle proposizioni nel senso della logica matematica. Non sono proposizioni logiche, invece, le frasi:

• A. «1 000 è un numero grande».
• B. «Il quadrato è una figura semplice».
• C. «Roma è una bella città».
• D. «Mi piacerebbe essere promosso».
• E. «Studia!».

Queste frasi esprimono affermazioni non valutabili oggettivamente, di esse non si può dire se sono vere o false. Non sono proposizioni logiche le domande, le esclamazioni, i comandi. Le proposizioni possono essere semplici affermazioni (proposizioni atomiche) oppure possono essere ottenute da una o più proposizioni elementari legate tra di loro attraverso connettivi logici (elementi linguistici del tipo “non”, “e”, “o”, “se . . . allora”, “se e solo se”). In questo caso si parla di proposizioni composte o molecolari. Per esempio, la proposizione «un triangolo ha tre lati e tre angoli» è composta dalle proposizioni «un triangolo ha tre lati» e «un triangolo ha tre angoli» unite dal connettivo “e”. La valutazione della verità o falsità di una proposizione composta dipende dalla verità di ogni singola proposizione che la compone e da come esse sono collegate tra di loro.

Algebra delle proposizioni

Vediamo ora il calcolo algebrico con le proposizioni. Si usa indicare le proposizioni con lettere minuscole, tipo p, q, r, ... La congiunzione di due proposizioni si ottiene con il connettivo “e” (et, and, ∧): la proposizione r ottenuta dalla congiunzione delle proposizioni p e q, in simboli si usa scrivere r = p ∧ q, è vera se entrambe le proposizioni p e q sono contestualmente vere, mentre è falsa quando anche una sola delle due proposizioni è falsa. Per esempio, «Ho avuto 7 in italiano e matematica» è un'affermazione vera solo quando ho avuto 7 in entrambe le materie. Oppure, «Per guidare il motorino occorre aver compiuto 14 anni e possedere il patentino» significa che posso guidare il motorino solo se ho entrambi i requisisti: aver compiuto 14 anni e avere il patentino. Per esprimere in maniera sintetica tutte le possibilità del valore di verità di una proposizione composta, si usa una tabella a doppia entrata, detta tavola di verità' (TABELLA 1). La disgiunzione (inclusiva) di due proposizioni si ottiene con il connettivo “o” (vel, or, ∨): la proposizione s ottenuta dalla disgiunzione di due proposizioni p e q, in simboli s = p ∨ q, è vera quando almeno una delle due proposizioni è vera ed è falsa solo se entrambe le proposizioni sono false. Ad esempio, la proposizione «100 è minore di 1 o maggiore di 10» è vera perché è vera una delle due affermazioni, precisamente 100 è maggiore di 10. Anche nell'affermazione «L'autobus si ferma quando qualche persona deve scendere o salire» la “o” è usata in senso inclusivo. La disgiunzione esclusiva di due proposizioni si ottiene con il connettivo (o congiunzione) “o ... o” (aut, xor, ⊻): la proposizione t ottenuta dalla disgiunzione esclusiva di due proposizioni p e q, in simboli t = p ⊻ q, è vera quando soltanto una delle due proposizioni è vera ed è invece falsa quando le due proposizioni sono entrambe vere o entrambe false. Per esempio, nell'affermazione «oggi il Milan vince o pareggia» la congiunzione “o” ha valore esclusivo. La negazione, che si ottiene con il connettivo “non” (non, not, ¬), è un operatore che, a differenza dei precedenti, non lega più proposizioni ma agisce su un'unica proposizione (per questo si dice che è un operatore unario, in analogia all'operazione insiemistica di complementazione). La negazione di una proposizione p è una proposizione che si indica con il simbolo ¬p che risulta vera se p è falsa, viceversa è falsa se p è vera. La doppia negazione equivale ad un'affermazione, cioè ¬(¬p) è equivalente a p.

---

ESEMPIO 1. Date le seguenti proposizioni p = «un triangolo ha tre lati» (Vera), q = «un triangolo ha tre vertici» (Vera), r = «un triangolo ha quattro angoli» (Falsa), s = «un triangolo ha tre dimensioni» (Falsa), allora:

• p ∧ q è vera, q ∧ r è falsa, r ∧ s è falsa.
• p ∨ q è vera, q ∨ r è vera, r ∨ s è falsa.
• p ⊻ q è falsa, q ⊻ r è vera, r ⊻ s è falsa.

---

È piuttosto semplice capire il meccanismo della negazione se applicata a proposizioni atomiche, spesso è meno intuitivo il valore di verità della negazione di una proposizione più complessa. Ad esempio, la negazione di p ∧ q non è ¬p ∧ ¬q bensì ¬p ∨ ¬q, mentre la negazione di p ∨ q è ¬p ∧ ¬q. Per esempio, «Non è vero che Marco e Luca sono stati bocciati» può voler dire che entrambi non sono stati bocciati o solo uno di loro non è stato bocciato. In formule si hanno le seguenti equivalenze (leggi di De Morgan):

¬(p ∧ q) = ¬p ∨ ¬q e ¬(p ∨ q) = ¬p ∧ ¬q.

La verifica si può effettuare mediante la seguente tavola di verità. La quinta colonna è infatti l'opposto (negazione) della sesta e anche la settima è l'opposto (negazione) dell'ottava.

Due espressioni logiche si dicono equivalenti se hanno gli stessi valori per la relativa colonna della tavola di verità. Come per le operazioni aritmetiche anche per gli operatori logici è possibile analizzarne le proprietà. Ne indichiamo qualcuna a titolo di esempio:

• (p ∧ q) ∧ r = p ∧ (q ∧ r) proprietà associativa della congiunzione.
• p ∧ q = q ∧ p proprietà commutativa della congiunzione.
• p ∧ (q ∨ r) = (p ∧ q) ∨ (p ∧ r) proprietà distributiva della congiunzione rispetto alla disgiunzione.

Una proposizione che è sempre vera, indipendentemente dalla verità degli elementi che la compongono, è detta tautologia. Un banale esempio di tautologia è una frase del tipo «Quest'anno la Juve vince il campionato oppure non lo vince». Una proposizione che è sempre falsa, indipendentemente dalla verità dei suoi elementi, è detta contraddizione. Un esempio banale di contraddizione è l'affermazione «un numero è multiplo di 2 ed è dispari».

---

ESEMPIO 2. La proposizione p ∧ ¬p è una contraddizione in quanto è sempre falsa. La proposizione p ∨ ¬p è una tautologia in quanto è sempre vera.

---

Predicati e quantificatori

Una proposizione che fa riferimento a una proprietà o caratteristica di alcuni elementi di un insieme si chiama predicato (o enunciato). Le frasi formate da un predicato che ha alcuni argomenti incogniti si dicono enunciati aperti. Per esempio, p = «x è un numero intero maggiore di 10» è un enunciato aperto. Consideriamo ora le seguenti affermazioni:

• «Tutti gli uomini sono mortali» si riferisce a un qualsiasi essere umano.
• «Tutti i multipli di 6 sono anche multipli di 2» è vera per tutti i numeri multipli di 6.
• «Ogni numero negativo è minore di ogni numero positivo».

I predicati precedenti non riguardano un elemento specifico ma una certa quantità di elementi. I termini “tutti” e “ogni”, detti quantificatori universali, indicano che una proprietà è vera per tutti gli elementi di un certo insieme. In logica matematica si usa il simbolo ɣ (che si legge “per ogni”) per indicare il quantificatore universale. Vediamo ora i seguenti predicati:

• «Esiste un numero che elevato al quadrato dà 16».
• «Alcuni numeri pari sono anche multipli di 3».

Queste affermazioni esprimono proprietà che sono vere per almeno un elemento dell'insieme di riferimento: la prima frase è vera per i numeri +4 e -4, la seconda frase è vera per i numeri 6, 12, 18, ... I termini “c'è almeno”, “alcuni”, “esiste almeno uno” si dicono quantificatori esistenziali e si indicano con il simbolo ɜ (che si legge “esiste”). Bisogna prestare particolare attenzione quando si negano frasi in cui compaiono i quantificatori. Per esempio, la negazione di «Tutti i gatti fanno le fusa» non è «Nessun gatto fa le fusa» bensì «Non tutti i gatti fanno le fusa» che si può esprimere anche con il quantificatore esistenziale «C'è almeno un gatto che non fa le fusa». La negazione della frase «L'anno scorso siamo stati tutti promossi» non è «L'anno scorso siamo stati tutti bocciati» ma «L'anno scorso c'è stato almeno uno di noi che non è stato promosso». La negazione della proposizione p = «Tutti i quadrati hanno due diagonali» è la proposizione -p = «Non tutti i quadrati hanno due diagonali». Il linguaggio comune ci potrebbe portare a considerare come negazione di p la proposizione «Nessun quadrato ha due diagonali», ma in realtà per avere la negazione della proposizione p basta che esista almeno un quadrato che non abbia due diagonali.

L'implicazione

Nel linguaggio matematico sono comuni proposizioni del tipo «Se p allora q». Ad esempio «Se un numero è multiplo di 12 allora è multiplo di 3». La frase precedente può essere espressa dicendo: «Essere multiplo di 12 implica essere multiplo di 3». In logica frasi del tipo «Se p allora q» vengono tradotte utilizzando l'operatore detto implicazione. La scrittura «se p allora q» si traduce con la scrittura p ===> q, che si legge “p implica q”. La proposizione p è detta antecedente, (o ipotesi) e la proposizione q è detta conseguente (o tesi). Il significato logico della proposizione p ===> q è «tutte le volte che la proposizione p è vera allora risulta vera anche la proposizione q». Ovvero non si dice niente sula caso in cui p sia falsa. Per esempio, l'affermazione «Se c'è il sole andiamo al mare» è falsa solo quando c'è il sole e non andiamo al mare; l'affermazione, infatti, non dice nulla se il sole non c'è: quindi se non c'è il sole si è liberi di andare o non andare al mare. Anche l'affermazione «Se studi sarai promosso» dice solo che se studi sarai promosso, non dice nulla per il caso in cui tu non studi, in questo caso infatti potrai essere ugualmente promosso. La sua tavola di verità è la seguente:

Uno degli errori logici più comuni è quello di pensare che da p ===> q si possa dedurre -p ===> -q. Ad esempio dall'affermazione «Se piove prendo l'ombrello» qualcuno può pensare che si possa dedurre «Se non piove non prendo l'ombrello». Riflettendoci, si intuisce che le due frasi non sono affatto consequenziali. Basta pensare che chi pronuncia la prima frase sta affermando soltanto che tutte le volte che piove prende naturalmente l'ombrello, ma non esclude la possibilità di prenderlo anche quando non piove (in effetti è saggio farlo se il cielo è coperto da nuvoloni neri!). Così la frase (a) «Se x è multiplo di 12 allora è multiplo di 3» non vuol dire (b) «Se x non è multiplo di 12 allora non è multiplo di 3», infatti la (a) è vera, mentre la (b) è falsa (si pensi ad esempio al numero 6 che non è multiplo di 12 ma è comunque multiplo di 3). Ciò che ragionevolmente si può dedurre da p ===> q è -q ===> -p. Ad esempio da «Se x è multiplo di 12 allora è multiplo di 3» si può dedurre «Se x non è multiplo di 3 allora non è multiplo di 12». Data l'implicazione p ===> q la proposizione p viene detta condizione sufficiente per q, mentre la proposizione q viene detta condizione necessaria per p. Per esempio, studiare è condizione necessaria per essere promossi ma non è sufficiente. Quest'ultima espressione fa appunto riferimento al fatto che da p ===> q si può dedurre -q ===> -p. Ossia q è necessaria per p in quanto se non è vera q non è vera neanche p. Calcoliamo la tavola di verità di p ===> q e di -q ===> -p.

Come si vede, le due proposizioni hanno gli stessi valori di verità. In generale, data un'implicazione p ===> q (proposizione diretta):

• L'implicazione -p ===> -q si dice contraria di p ===> q.
• L'implicazione q ===> p si dice inversa di p ===> q.
• L'implicazione -q ===> -p si dice contronominale (o controinversa) di p ===> q.

La doppia implicazione, o equivalenza logica, di due proposizioni p e q dà luogo a una proposizione che in simboli si rappresenta p <===> q (leggasi “p se e solo se q”) che è vera se p e q sono entrambe vere o entrambe false. La tavola di verità è la seguente:

L'operatore <===> è detto di doppia implicazione perché se vale p <===> q significa che valgono sia p ===> q che q ===> p (e viceversa). Nella tabella precedente, infatti, è stata messa in evidenza l'equivalenza logica tra la proposizione p <===> q e la proposizione (p ===> q) /\ (q ) p). L'equivalenza logica è un relazione di equivalenza, infatti verifica le seguenti proprietà:

• p <===> p riflessiva.
• Se p <===> q allora vale anche q <===> p simmetrica.
• Se p <===> q e q , r allora vale anche p <===> r transitiva.

In matematica si usa spesso l'espressione «p è condizione necessaria e sufficiente per q». Per esempio «Condizione necessaria e sufficiente affinché un numero sia divisibile per 3 è che la somma delle sue cifre sia divisibile per 3». Il significato della frase è che «p è sufficiente per q» e inoltre «p è necessario per q». In altre parole significa dire che p ===> q e q ===> p. Nel caso dell'esempio, «se un numero è divisibile per 3 allora la somma delle sue cifre è divisibile per 3», vale quindi anche l'implicazione inversa «se la somma delle cifre di un numero è divisibile per 3 allora il numero stesso è divisibile per 3». In maniera analoga a quanto avviene per le espressioni numeriche, le espressioni logiche possono contenere varie proposizioni legate tra loro dagli operatori appena descritti ed eventualmente le parentesi che indicano la precedenza di applicazione degli operatori stessi. In linea di principio gli operatori vengono applicati nell'ordine nel quale si trovano nell'espressione da sinistra verso destra, tenendo però a mente che tra essi vige la seguente regola di precedenza: l'operatore - ha la precedenza sugli altri, seguito dall'operatore /\ ed infine da V. Da ciò ne deriva un sistema di calcolo simbolico noto anche come algebra di Boole (matematico e logico britannico [1815 - 1864]).

I teoremi

Un teorema è una proposizione composta del tipo I ===> T, cioè una implicazione tra due proposizioni, dette ipotesi (I) e tesi (T). Dimostrare un teorema significa fare un ragionamento logico che permetta di concludere che la tesi è vera avendo supposto che l'ipotesi è vera. In generale incontreremo molti teoremi che vengono denominati genericamente proposizioni, perché il nome di “teorema” viene tradizionalmente attribuito solo ai teoremi più importanti. Inoltre si usa chiamare lemma una proposizione che non ha una grande importanza di per sé, ma che è particolarmente utile per la dimostrazione di altri teoremi. Si chiama invece corollario un teorema che è una conseguenza immediata di un altro teorema.

All'interno di una teoria matematica non è possibile dimostrare tutte le proposizioni, alcune devono essere assunte come vere senza dimostrarle, esse costituiscono la base della teoria sulle quali si fondano le dimostrazioni dei teoremi. Queste proposizioni si chiamano postulati o assiomi. Risulta evidente che cambiando sia pure uno solo degli assiomi cambiano anche i teoremi dimostrabili e quindi la teoria.

La deduzione

Nel paragrafo precedente abbiamo parlato in modo generico di implicazione, deduzione, dimostrazione. Facciamo ora un po' di chiarezza sull'uso di questi termini. L' implicazione è un'operazione tra proposizioni, mentre la deduzione è il ragionamento logico che costituisce la base della dimostrazione di un teorema. Per l' implicazione materiale si usa il simbolo ---> mentre per la deduzione logica si usa il simbolo ===>. La frase «Se 5 è un numero pari, allora il triangolo ha 4 lati» è perfettamente valida da un punto di vista della logica matematica ed anzi è vera, poiché la premessa (proposizione antecedente) è falsa, per cui l'implicazione è vera anche se la proposizione conseguente è falsa (si tenga presente la tavola di verità di p ===> q). Si noti però che la definizione di implicazione ha senso solamente se la premessa è vera, il suo ampliamento al caso in cui la premessa è falsa è motivata da ragioni di completezza della trattazione. Bisogna quindi fare attenzione ad usare l'implicazione logica quando la premessa è falsa. Teniamo comunque conto che se p è falsa allora (p ===> q) /\ (p ===> -q) cioè p ===> (q /\ -q) è vera. Ma q /\ -q è una contraddizione, quindi una premessa falsa implica sempre una contraddizione. In realtà, la dimostrazione di un teorema non è la verifica della validità dell'implicazione, anzi è un procedimento che fa uso della validità dell'implicazione stessa. In un teorema si parte dal supporre vera l'ipotesi e si dimostra, seguendo un ragionamento logico che si basa sugli assiomi e altri teoremi già dimostrati in precedenza, che anche la tesi è vera (questo se si segue il procedimento diretto). Se si segue invece il procedimento indiretto (o per assurdo), si suppone che la tesi sia falsa e, sempre mediante assiomi e altri teoremi già dimostrati, si arriva, tramite passaggi logici, ad affermare che l'ipotesi è falsa (cosa che non si deve accettare). Le principali regole del corretto ragionamento seguono alcuni schemi particolari (detti sillogismi, dal nome ad essi attribuito da Aristotele, filosofo, scienziato e logico della grecia antica [383 o 384 a.C. – 322 a.C.]). Presentiamo qui i quattro principali sillogismi: il modus ponens, il modus tollens, il sillogismo disgiuntivo e il sillogismo ipotetico.

Suggeriamo una lettura degli schemi appena esposti:

• Modus Ponens: Se sappiamo che p implica q e che p è vera, allora possiamo concludere che anche q è vera (metodo diretto di dimostrazione).
• Modus Tollens: Se sappiamo che p implica q e che q è falsa, allora possiamo concludere che anche p è falsa (metodo indiretto di dimostrazione).
• Sillogismo Disgiuntivo: Se sappiamo che, tra p e q, almeno una delle due è vera, e sappiamo che p (rispettivamente q) è falsa, allora possiamo concludere che q (rispettivamente p) è vera.
• Sillogismo Ipotetico: Se sappiamo che p implica q e che q implica r, allora possiamo concludere che p implica r (proprietà transitiva dell'implicazione).

Altre regole (note come i giudizi di Aristotele) fanno uso dei predicati e dei quantificatori. Riprendiamo un esempio precedente traducendo la frase «tutti i quadrati hanno due diagonali» e la sua negazione «non tutti i quadrati hanno due diagonali» in formule che fanno uso anche del linguaggio degli insiemi. Se chiamiamo Q l'insieme di tutti i quadrati e P la proprietà dell'avere due diagonali, se x è il generico quadrato (elemento di Q), P(x) è il predicato «x gode della proprietà P», cioè «x ha due diagonali», la frase «tutti i quadrati hanno due diagonali» si traduce in simboli: ɣx € Q, P(x). La sua negazione è: «esiste almeno un quadrato che non ha due diagonali», cioè che non gode della proprietà P, e si traduce in simboli così: ɜx € Q, -P(x). In quest'ultimo caso, la virgola può anche essere sostituita da una barra verticale (“|”) o da “:” e si legge “tale che”. Analogamente, una frase del tipo «esiste almeno un numero naturale che sia divisore di 10» può scriversi come: ɜn € N | D(n), dove D è la proprietà dell'essere divisore di 10 e D(n) significa che n verifica la proprietà D, cioè che n è un divisore di 10. La sua negazione è «nessun numero naturale è divisore di 10», ovvero «preso un qualsiasi numero naturale n, questo non gode della proprietà D», la traduzione in simboli di tale frase è: ɣn € N, -D(n). Mettiamo in tabella le quattro proposizioni, che corrispondono ai giudizi di Aristotele:

Se chiamiamo R l'insieme degli elementi che verificano la proprietà P, e S quello degli elementi che verificano la proprietà D, i quattro giudizi si possono rappresentare graficamente come nella FIGURA 1.

La dimostrazione

Tenendo conto di quanto detto precedentemente, dimostrare che I ===> T significa fare un ragionamento che permetta di concludere che la tesi T è vera avendo supposto che l'ipotesi I sia vera. Quando attraverso un ragionamento logico, e cioè attraverso una catena di implicazioni del tipo I ===> A ===> B ===> ... ===> T, si riesce a dedurre la verità di una proposizione T a partire dalla verità di una proposizione I, si dice che si è data una dimostrazione diretta del teorema I ===> T (attraverso le regole del modus ponens e del sillogismo ipotetico). Un teorema può anche essere dimostrato per assurdo, o con metodo indiretto. Questa dimostrazione consiste nel partire dalla negazione di T e, attraverso una catena di implicazioni, arrivare alla negazione di I o, in generale, ad una contraddizione. Esistono altri metodi di dimostrazione, di cui eventualmente si parlerà più diffusamente qualora si dovesse ricorrere ad essi. Per ora ci limitiamo a citarne un paio: dimostrazione per induzione e dimostrazione mediante esempio o controesempio. La dimostrazione per induzione si usa in particolare quando vogliamo dimostrare una proprietà generale che vale per molte categorie di figure ma che non si può esprimere in maniera unica per tutte le categorie (ad esempio una proprietà che vale per tutti i poligoni ma che dipende dal numero dei lati, come l'estensione dei criteri di congruenza dei triangoli a poligoni di più lati). Si usa invece un esempio quando bisogna dimostrare che una certa proprietà vale per almeno un oggetto del nostro studio o un controesempio per dimostrare che una proprietà non vale per tutti gli oggetti in esame. Per fornire alcuni esempi di dimostrazione, avremmo bisogno di fissare prima i concetti di base e gli assiomi da cui partire, per cui rinviamo la questione al prossimo paragrafo. Ma a cosa serve studiare la dimostrazione di un teorema? Perché non ci limitiamo ad elencare i teoremi? Per molte applicazioni basta in effetti conoscere il teorema e a volte anche soltanto la formula risolutiva. Tuttavia studiando le dimostrazioni si impara a dimostrare e quindi si impara a creare nuova matematica. Un altro importante vantaggio è che la dimostrazione spiega perché il teorema è vero e permette di scoprire la struttura nascosta nelle definizioni e nei teoremi. Quando si studia una dimostrazione non bisogna limitarsi a leggerla e a impararla a memoria, occorre leggerla attivamente, ponendo attenzione su cosa si fa e cercando di anticipare i passaggi. Se un passaggio non è chiaro bisogna prima tornare indietro per capire come ci si è arrivati e quindi cercare di capire il motivo per cui l'autore ha messo quel passaggio. In generale, una dimostrazione va letta più volte smettendo solo quando la si è compresa a fondo.