Logica proposizionale

La logica proposizionale (o logica matematica) è uno strumento espressivo della matematica che si incontra con terminologie diverse e in ogni sorta di teoremi matematici.

A che cosa serve la logica

La logica è la scienza che si occupa del ragionamento, della verità, della dimostrabilità e della confutabilità. In tutto ciò alla logica interessa solo la forma dell’enunciato: non ci interessa che cosa si dica in concreto, così come non ci interessano le varie interpretazioni psicologiche e cose simili.

Se abbiamo, per esempio, la frase «il numero 2 è pari e allo stesso tempo è dispari», possiamo concludere che la frase intera non è vera, perché il numero 2 non è dispari. Sono questioni di cui si occupa in generale la logica.

Proposizione

La base della logica proposizionale è, com’è ovvio, la proposizione. Una proposizione è ogni frase dichiarativa di cui possiamo stabilire il valore di verità. Esempi di proposizioni semplici:

• Roma è la capitale d’Italia.
• Il numero naturale cinque è dispari.
• HTML è un linguaggio di programmazione.
• Due più tre fa sei.

Queste sono tutte proposizioni, siano vere (le prime due) o false (le ultime due). Non è una proposizione, per esempio, una frase interrogativa né una frase di cui non possiamo stabilire con chiarezza il valore di verità. Di nuovo un esempio:

• Anche l’anno prossimo Roma sarà la città più grande d’Italia?
• Il verde è il colore più bello.

La prima frase non può essere una proposizione perché è interrogativa; della seconda, invece, non possiamo decidere se sia una proposizione vera o falsa. Una frase del genere si chiama ipotesi (congettura).

La logica matematica classica non se la cava molto bene con le frasi vaghe come «Marco è alto» o «Sofia canta bene». Queste proposizioni si trattano meglio, per esempio, nella logica fuzzy, che è fatta apposta per la vaghezza.

Proposizione atomica

Nel primo paragrafo avevamo l’esempio della proposizione «il numero 2 è pari e allo stesso tempo è dispari». Una proposizione così si può chiamare composta, perché in realtà unisce due proposizioni più brevi: «il numero 2 è pari» e «il numero 2 è dispari». Queste due proposizioni sono unite dal connettivo logico «e» o anche «e allo stesso tempo».

Una proposizione atomica è quindi una proposizione che non possiamo dividere ulteriormente: in un certo senso è l’affermazione più semplice. Le proposizioni degli esempi precedenti erano in realtà proposizioni atomiche:

• Roma è la capitale d’Italia.
• Il numero naturale cinque è dispari.
• HTML è un linguaggio di programmazione.
• Due più tre fa sei.

D’ora in poi indicheremo le proposizioni atomiche con le lettere minuscole dell’alfabeto, di solito p, q, r, …, e le chiameremo variabili proposizionali.

Connettivi logici

La logica matematica opera di norma con un certo insieme di connettivi logici. Tra quelli fondamentali ci sono quattro connettivi binari:

• p ∧ q è la congiunzione di proposizioni, si legge «la proposizione p e (allo stesso tempo) la proposizione q»
• p ∨ q è la disgiunzione di proposizioni, si legge «la proposizione p o la proposizione q»
• p ⇒ q è l’implicazione, si legge «se la proposizione p, allora la proposizione q»
• p ⇔ q è l’equivalenza, si legge «la proposizione p se e solo se la proposizione q»

Esempi concreti di connettivi logici:

• Nel centro di Bologna piove e allo stesso tempo c’è il sole. (congiunzione)
• Nel centro di Bologna piove oppure c’è il sole. (disgiunzione)
• Marco è il più simpatico della classe e Sofia è la più intelligente. (congiunzione)
• Se prendi un lassativo, allora presto dovrai correre in bagno. (implicazione)
• Se il numero x è divisibile per quattro, allora è divisibile anche per due. (implicazione)
• Giulia è bella e allo stesso tempo intelligente. (congiunzione)
• Le cantanti hanno successo se e solo se sono belle. (equivalenza)
• Se non piove, non ci bagneremo. (implicazione)
• Se Marco sa cantare, allora i maiali volano. (implicazione)

Conosciamo ancora un altro connettivo logico comune: la negazione. La negazione si indica con un apice, p′, oppure con il simbolo ¬p.

Formula

Con le variabili proposizionali (proposizioni atomiche) e i connettivi logici possiamo comporre una proposizione più complessa, che chiameremo formula. Tutti gli esempi dell’elenco di frasi precedente erano in realtà formule, perché avevamo due formule atomiche, per esempio «nel centro di Bologna piove» e «c’è il sole», e le abbiamo unite mediante connettivi logici. Nel primo caso le abbiamo unite con il connettivo «e allo stesso tempo» e abbiamo ottenuto la formula «nel centro di Bologna piove e allo stesso tempo c’è il sole», nel secondo caso abbiamo usato «oppure» e abbiamo ottenuto la formula «nel centro di Bologna piove oppure c’è il sole».

Definiamo formalmente una formula così:

• Ogni variabile proposizionale (proposizione atomica) è una formula (più precisamente, si tratta di una formula atomica).
• Se A e B sono formule, allora lo sono anche ¬A, (A ∧ B), (A ∨ B), (A ⇒ B), (A ⇔ B).

La definizione ha senso: nel primo punto diciamo che ogni proposizione atomica è allo stesso tempo una formula. Quindi, se abbiamo due proposizioni atomiche, per esempio «nel centro di Bologna piove» e «c’è il sole», abbiamo allo stesso tempo due formule. A questo punto possiamo applicare il secondo punto e costruire una formula più complessa, per esempio così:

• Nel centro di Bologna piove e allo stesso tempo c’è il sole.
• Nel centro di Bologna piove oppure c’è il sole.
• Se nel centro di Bologna c’è il sole, allora piove.
• Nel centro di Bologna c’è il sole se e solo se piove.

Le formule, naturalmente, non sono per forza vere. Ora abbiamo ottenuto un altro insieme di formule, quindi possiamo comporre formule ancora più complesse. Se indichiamo con A=«Nel centro di Bologna c’è il sole oppure piove.» (sappiamo già che è una formula) e con B=«si vede l’arcobaleno» (supponiamo che sia sempre nel centro di Bologna, per non ripeterlo di continuo), possiamo creare altre formule. Le parentesi nelle frasi servono solo a indicare a quali parti si riferisce il connettivo.

• A ∧ B: (Nel centro di Bologna c’è il sole oppure piove) e allo stesso tempo (si vede l’arcobaleno).
• A ∨ B: (Nel centro di Bologna c’è il sole oppure piove) oppure (si vede l’arcobaleno).
• A ⇒ B: (Se nel centro di Bologna c’è il sole oppure piove), allora (si vede l’arcobaleno).
• A ⇔ B: (Nel centro di Bologna c’è il sole oppure piove) se e solo se (si vede l’arcobaleno).

Queste sono tutte formule. Quindi possiamo di nuovo prendere una di queste formule e aggiungerle un’altra formula. Possiamo creare così, per esempio, il mostriciattolo «Se nel centro di Bologna c’è il sole oppure piove oppure si vede l’arcobaleno, allora c’è il sole oppure piove se e solo se si vede l’arcobaleno».

Nella parte successiva studieremo il valore di verità delle formule.