I connettivi della logica proposizionale

Quali e quanti sono i connettivi logici? Sono tutti o ne manca qualcuno? Dipendono dalla nostra lingua? Bastano per fare tutto? In questo post voglio affrontare qualche domanda generale ma senza entrare troppo nel dettaglio.

Nota: il posta è stato pubblicato il 15 febbraio 2023 ma non ne ero soddisfatto e quindi l’ho rimaneggiato e lo ripubblico oggi che è il 10 maggio 2023.

Aristotele ed il linguaggio naturale.

Il filosofo Aristotele vissuto 4 secoli prima della nascita di Cristo quindi 2400 anni fa scrisse il primo trattato di logica: l’Organon. Aristotele voleva scrivere le regole del ragionamento e per farlo partì dal linguaggio naturale (la propria lingua madre), che è il modo in cui noi tutti ragioniamo, cercando di ricavarne qualche regola; ovviamente tutto ciò è un riassuntone senza arte ne parte ma che ci serve per dare un minimo di contesto all’idea.

La logica moderna si è astratta dal contenuto delle proposizioni andando solo a studiare le relazioni tra le proposizioni. Le proposizioni si indicano con lettere dell’alfabeto mentre le connessioni tra le proposizioni che corrispondono in molti casi a connettivi del linguaggio naturale si esprimono con simboli appositi: i connettivi logici. I connettivi che usiamo tutti nel nostro linguaggio sono ‘e’ ed ‘o’ ma anche ‘non’ che si scrivono per convenzione con i seguenti simboli:

\text{p e q} = q \land q \newline
\text{p o q} = q \lor q \newline
\text{ non p} = \lnot p

a sinistra c’è l’espressione nel linguaggio naturale e a destra il corrispettivo in logica formale.

Ho scritto questi tre connettivi logici ma ce ne sono altri anche se non vengono istantanei alla mente. Esiste in particolare un connettivo chiamato connettivo di Sheffer:

\text{né p né q} = p\mid q

vi era venuto in mente? Non è il più intuitivo. Quindi sorgono dlle domandone: quali sono i connettivi logici? Quanti sono?

Se voglio fondare la logica e voglio trovare il modo per ragionare in modo corretto non posso solo riferirmi a come ragiono io, ho bisogno di qualche cosa di più oggettivo. Inoltre la domanda ne nasconde un’altra ancora più importante: se nella mia lingua uso questi connettivi logici è possibile che in altre lingue se ne usino altri? Esiste una lingua più adatta al ragionamento logico?

Per rispondere a queste domande dobbiamo fare un passo in avanti.

Vero o falso? Giusto o sbagliato? Oppure 1 o 0?

Le proposizioni possono essere o vere o false. Questo è un principio della logica, si chiama principio del terzo escluso cioè non sono attribuibili altri valori ad una proposizione.

Nella logica moderna dire che una proposizioni assume solo due valori è una semplice scelta, è possibile costruire logiche a più valori, in numero arbitrario o anche infiniti dove tra vero e falso ci sono molte sfumature (Fuzzy in inglese). In pratica anche i concetti di Vero e Falso si sfumano. L’insieme dei valori di verità che una proposizione può assumere è detto dominio di interpretazione.

Detto ciò in matematica e nei nostri ragionamenti di tutti i giorni ci fermiamo alla logica a due valori detta anche dicotomica che è una parola che significa semplicemente: a due valori.

Nella logica moderna diciamo semplicemente a due valori senza dare importanza a quali valori facciamo riferimento. Tradizionalmente e storicamente ai due valori si associano le parole Vero e Falso o semplicemente le lettere V ed F, in inglese T, F che stanno per True e False ma, non è necessario. Potremmo anche associare concetti come Giusto e Sbagliato. Nell’informatica è normale utilizzare i simboli 1 e 0 che fisicamente corrispondono a circuiti elettrici dove un interruttore, un transistor oggi una valvola ieri, è chiuso o aperto insomma ha due stati fisici.

Il secondo principio su cui si fonda la logica è che una proposizione può assumere i due valori ma non contemporaneamente. Se una proposizione è nello stato V allora non può essere anche nello stato F e viceversa. Questo si chiama principio di non contraddizione.

Se associamo solo due possibili stati ad una proposizione allora ci dobbiamo chiedere a quale stato corrisponde la nuova proposizione che si ottiene connettendo le due proposizioni con un connettivo logico: ecco che così nascono le tabelle di verità nome un po’ biblico che nasconde il fatto che nella logica moderna potrebbero anche chiamarsi in altro modo ma che per convenzione si chiamano così, in effetti anche tabelle di falsità andrebbe bene come nome. Vediamo in pratica: ecco la tabella della verità del connettore ‘e’:

\def\arraystretch{1.5}
   \begin{array}{c:c:c}
   p & q & p\land q \\ 
   \hline
   F & F & F \\
   \hline
   F & V & F  \\
  \hline
   V & F & F  \\
  \hline
   V & V & V  \\
\end{array}

ed ecco la tabella della verità del connettore ‘o’

\def\arraystretch{1.5}
   \begin{array}{c:c:c}
   p & q & p\lor q \\ 
   \hline
   F & F & F \\
   \hline
   F & V & V  \\
  \hline
   V & F & V  \\
  \hline
   V & V & V  \\
\end{array}

scriviamo anche la negazione:

\def\arraystretch{1.5}
   \begin{array}{c:c}
   p & \lnot p \\ 
   \hline
   F  & V \\
   \hline
   V  & F  \\
\end{array}

infine, per completezza scriviamo anche la tabella della verità per il connettore di Sheffer:

\def\arraystretch{1.5}
   \begin{array}{c:c:c}
   p & q & p\mid q \\ 
   \hline
   F & F & V \\
   \hline
   F & V & V  \\
  \hline
   V & F & V  \\
  \hline
   V & V & F  \\
\end{array}

Per essere sicuri che quello che scriviamo corrisponde alla nostra idea di ‘e’ ed ‘o’ e ‘non’ è meglio fare una veloce verifica. La ‘e’ è sempre falsa ad eccezione di quando entrambe le proposizioni sono vere. Quindi la ‘e’ ci dice che entrambe le proposizioni devono essere vere, ne basta una per dire che la proposizione nel suo insieme, congiunta possiamo dire, è falsa.

La ‘o’ invece dice che la proposizione congiunta è falsa solo quando entrambe le proposizioni sono false altrimenti ne basta una per dire che è vera.

La negazione invece semplicemente scambia i valori di verità e rende chiaro il principio di non contraddizione: se nego una proposizione il suo stato deve per forza cambiare.

Se leggete bene le tavole vi rendete conto che esprimono esattamente ciò che esprimiamo nel linguaggio naturale…non è vero. Infatti a volte la congiunzione ‘o’ viene usata in modo esclusivo cioè la usiamo in modo che anche l’ultima riga della tabella sia falsa. Ad esempio i genitori ai figli chiedono di scegliere in modo esclusivo, ai miei tempi, andati, si diceva: ‘o mangi la minestra o salti dalla finestra’ ed andava inteso in modo esclusivo le opzioni erano due e non si poteva sceglierle entrambe; in effetti sono mutuamente esclusive.

Come si spiega questa ambiguità? Semplice, la ‘o’ esclusiva è un altro operatore che nel linguaggio comune confondiamo perché utilizziamo la stessa congiunzione per esprimerla. In altre lingue non è sempre così.

Il mondo dell’elettronica

Nel mondo dell’elettronica oltre a considerare i valori 0=Falso, 1=Vero anche i connettivi logici hanno un nome letterale evitando cosi tanti nuovi simboli. Per i connettivi logici appena visti si usa:

NOT = \lnot \newline
AND = \land \newline
OR = \lor \newline
NAND = \mid \newline
XOR = \text{exclusive } OR

ce ne sono altri ma non voglio confondere le idee.

Quali sono tutti i connettori?

Ora che abbiamo ridotto a tabelle alcuni connettori logici possiamo tranquillamente generalizzare l’idea e scriverli tutti.

In pratica possiamo dire che un connettore è una funzione di due variabili, la p e la q, che variano entrambe su un insieme di due valori a valori nello stesso insieme. Tanto per formalizzare scriviamo:

D:=\{ V, F \} \newline
C: D\times D \to D

ora la prima variabile varia su 2 valori e la seconda anche quindi in tutto la funzione è definita su 2×2=4 coppie di valori: questo corrisponde con le tavole di verità già viste. Ora pensiamo all’immagine. per ogni coppia del dominio posso scegliere due valori nel codominio. Allora le combinazioni sono 2x2x2x2=16.

Ecco, in tutto ci sono 16 possibili connettori logici e li posso scrivere come tabelle di verità.

Il primo a rendersi conto di poter scrivere tutti i connettivi logici fu il filosofo e logico austriaco Ludwig Josef Johann Wittgenstein (Vienna, 26 aprile 1889 – Cambridge, 29 aprile 1951) nel suo Tractatus Logico-Philosophicus del 1921.

Questo risultato risponde alle due domande di partenza. Quali sono tutti i possibili connettori e quanti sono? Sono 16 e qui sotto c’è la tabella che li definisce completamente. Ci sono connettori in linguaggi diversi dal mio? Se ci sono sono comunque nella lista: abbiamo così astratto dal linguaggio naturale di partenza.

Facciamo una verifica, la ‘o’ esclusiva è presente? Sì, è la colonna con lo stesso simbolo della ‘o’ ma sottolineato; l’ultima in alto.

Ecco la tabella ottenuta con tutte le possibili combinazioni del codominio; ho dovuto spezzarla in due per ragioni di spazio ma anche per un’altra cosa che vediamo tra poco:

\def\arraystretch{1.5}
   \begin{array}{c:c:c:c:c:c:c:c:c:c}
   \bold{p} & \bold{q} & \tau  & p\lor q & p\larr q & p\rarr q & p\mid q & p & q & p \veebar q & \\ 
   \hline
   F & F & V & F & V & V & V & F & F & F \\
   \hline
   F & V & V & V & F & V & V & F & V & V   \\
  \hline
   V & F & V & V & V & F & V & V & F & V   \\
  \hline
   V & V & V & V & V & V & F & V & V & F  \\
\end{array} \newline
\def\arraystretch{1.5}
   \begin{array}{c:c:c:c:c:c:c:c:c:c}
   \bold{p} & \bold{q}  & c & p\darr q & p \nleftarrow q & p \nrightarrow  q & p\land q & \lnot p & \lnot q & p\lrarr q & \\ 
   \hline
   F & F & F & V  &F & F & F & V & V & V\\
   \hline
   F & V & F &F &V & F & F & V & F & F\\
  \hline
   V & F & F &F &  F &V &F & F & V & F\\
  \hline
  V & V & F & F &F &F &V &   F & F & V\\
\end{array}

Le prime due colonne con p e q in testa rappresentano i valori del dominio, ogni colonna successiva rappresenta un connettivo logico, lo stesso accade nel pezzo di tabella sottostante, tutti i connettivi hanno un nome anche se in molti testi si dice il contrario comunque li vediamo in dettaglio qui sotto. Si notino i simboli di implicazione, implicazione inversa e doppia implicazione rappresentati con delle frecce che rappresentano espressioni del tipo se p allora q, se q allora p e p se e solo se q.

La colonna ‘tau’ dove tutti i valori sono veri l’ho indicata così per introdurre il nome tautologia che significa espressione sempre vera. L’ultima colonna, quella indicata con ‘c’, indica una espressione sempre falsa comunemente chiamata contraddizione.

Ora vi spiego perché ho spezzato la tabella proprio in questo modo e ho sovrapposto le due semitabelle. La composizione di due proposizioni tramite un connettivo genera come risultato una nuova proposizione. Ad ogni proposizione deve corrispondere un’altra proposizione ottenuta per negazione. Se guardate bene ogni colonna negata ottenuta convertendo le F con le V e le V con le F sono messe una sopra l’altra. Questo rende più semplice la classificazione dei vari connettivi.

Ci sono 4 connettivi il cui risultato coincide con una delle variabili in ingresso e di conseguenza deve esistere anche il connettivo che coincide con la variabile negata. Possiamo vedere in effetti due colonne corrispondenti a p e q e sotto le colonne corrispondenti alle variabili negate.

La negazione di ‘e’ sarebbe un connettivo che potremmo chiama re ‘non e’ corrisponde al connettivo di Sheffer detto stroke. La negazione di ‘o’ corrisponde all’ antistroke.

Interessante anche la negazione dei connettivi di implicazione. Si ha:

p \nrightarrow q = \lnot(p \rarr q ) \newline
p \nleftarrow q = \lnot(p \larr q) \newline
p \nleftrightarrow q =\lnot(p \lrarr q ) = p \veebar q

Si noti come la negazione della doppia implicazione coincide con la ‘o esclusiva’.

Comunque ciò che si deve notare è che tutti i connettivi logici si possono esprimere con ‘non’, ‘e’ ed ‘o’. La cosa non è ovvia ma lo si può vedere dalle seguenti identità e dalle negazioni precedenti:

\begin{align}
\tau& = p\lor \lnot p \\
p\larr q& = p \lor \lnot q \\
p\rarr q& = \lnot p \lor q \\
p\mid q& =  \lnot( p \land q) \\
p\lrarr q& =(\lnot p \lor q) \land (p \lor \lnot q) \\
p\darr q& = \lnot( p \lor q) \\
c& = p \land \lnot p \\
\end{align}

Ma si può fare di meglio con il solo connettivo di Sheffer.

Il connettivo di Sheffer

Guardando le espressioni dei vari connettivi che si accoppiano tramite la negazione ci si chiede se sia possibile ridurre ‘e’ ad ‘o’ e viceversa. In effetti basta osservare le seguenti tautologie che si provano scrivendone le tavole di verità:

p \land q = \lnot(\lnot p \lor \lnot q) \newline
p \lor q =  \lnot(\lnot p \land \lnot q)

quindi se ogni volte che compare il connettivo ‘e’ sostituisco la sua espressione equivalente scritta con ‘non’ ed ‘o’ posso esprimere tutti i connettivi con solo ‘non’ ed ‘o’. Viceversa con l’espressione della seconda riga posso esprimere tutto con solo ‘non’ e ‘e’. Quindi il connettivo ‘non’ ed un connettivo ‘e’ oppure ‘o’ permette di scrivere tutti i connettivi. In realtà si possono utilizzare altri connettivi, la ‘e’ e la ‘o’ non hanno nulla di speciale tranne il fatto che sono molto comuni nel linguaggio naturale. Mostrare questo fatto però è dispendioso e il post andrebbe fuori strada quindi mi fermo.

Il connettivo di Sheffer invece ha qualche cosa in più. Permette anche di scrivere la negazione:

\lnot p = p \mid p

Accompagnato al fatto che:

p \lor q = (p \mid q) \mid (p \mid q)

ricordando che ‘o’ e la negazione permettono di scrivere tutti i connettivi si conclude che questo connettivo da solo permette di scrivere tutti gli altri. Ai tempi in cui Sheffer ottenne questo risultato (1913) era un tempo di rifondazione della matematica e della logica, si cercava di ridurre tutto ai minimi termini era stato accolto quindi come un risultato molto importante ma poi venne ridimensionato. Il fatto è che non tutte le preposizioni si possono esprimere con la logica proposizionale serve anche la logica predicativa che entra in parte nel significato delle preposizioni. All’inizio, abbiamo detto che non era importante e che ci si poteva astrarre la logica predicativa però non è parte di questo post anzi è già il momento di fermarsi.

Concludendo

Il linguaggio naturale ci fornisce esempi per parlare di connettivi logici. Il linguaggio naturale permette anche di associare alle preposizioni due possibili valori che tradizionalmente associamo a concetti come Vero e Falso qualunque cosa vogliano dire. Tutto ciò si può formalizzare e questa formalizzazione aiuta a rispondere a due domande che all’inizio sembrano impossibili. Nel linguaggio naturale posso esprimere delle connessioni logiche come ‘e’ ed ‘o’ ma poi ce ne sono altri: quanti possono essere? Per rispondere si potrebbe andare ad analizzare testi e testi di ragionamenti cercando tutti i connettivi logici che vi compaiono ma la formalizzazione permette di rispondere in modo facile: sono 16 e si può farne l’elenco. La seconda domanda è: potrebbero esistere connettivi logici che nella mia lingua non esistono ma magari esistono in altre lingue? Anche in questo caso la formalizzazione permette di elencare tutti i possibili connettivi logici indipendentemente dal fatto che esista o meno un corrispondente linguistico.

Abbiamo detto anche qualche cosa di più parlando del connettivo di Sheffer, lo scopo era anche mostrare che non ci sono connettivi migliori di altri, la scelta naturale di utilizzare ‘e’ ed ‘o’ assieme a ‘non’ è per il legame con il linguaggio naturale: dovremmo pur capire di cosa stiamo parlando.

Ho fatto dei buoni propositi. Alcuni diranno: ovvio è il post di gennaio. No. I buoni propositi si possono fare quando si vuole, non mettetevi limiti che non avete. Alla prossima.

P.S il post di gennaio viene pubblicato in febbraio perché sono stato malaticcio. Cercherò di scriverne un secondo sempre a febbraio per recuperare.

Bibliografia

Consulta la pagina a questo link