Operazioni nell'insieme delle proposizioni

Ci si propone di definire, nell'insieme di tutte le proposizioni logiche, opportune operazioni di composizioni binarie ed interne che, applicate ad una coppia ordinata di proposizioni (P₁, P₂), diano come risultato una nuova proposizione del tipo seguente P=P₁*P₂, ottenibile con le modalità prescritte dall'operatore * chiamato operatore logico o connettivo logico.

Le operazioni che si possono definire nell'insieme delle proposizioni sono le seguenti:

1. La congiunzione logica "AND" ... e

2. La disgiunzione inclusiva "OR" ... o

3. La disgiunzione esclusiva "EOR" ... aut

4. La negazione logica "NOT" ... non

5. L'implicazione logica "se ... allora" che si indica con →

6. La coimplicazione logica "... se e solo se ..." che si indica con ↔

Tutte queste operazioni sono binarie ad eccezione della negazione logica che è unitaria, nel senso che si applica ad una sola proposizione anzichè a due. Di questi operatori, tre sono particolarmente importanti e cioè e, o, non, poichè ogni altro connettivo può essere derivato da loro e per questo si chiamano connettivi logici fondamentali. Si rappresentano con una delle modalità indicate nella tabella. Il primo deriva dal latino, il secondo è dovuto al matematico Hilbert, il terzo è tratto dalla lingua inglese ed è utilizzato nei linguaggi informatici di programmazione. Quello che utilizzeremo più frequentemente sarà il simbolismo di Hilbert.

Per rendersi conto dell'opportunità di questo simbolismo, teniamo presente che lo scopo è quello di ridurre la complessità del linguaggio comune. Si introducono quindi pochi connettivi logici che permettono di esprimere qualsiasi proposizione composta. Questo modo di procedere, ci fa perdere alcune sfumature di significato, ma ci permetterà di raggiungere una formalizzazione non ambigua dei modi di collegare le proposizioni.

Esempio:

1. Giorgio mangia il gelato mentre legge il giornale

2. Giorgio mangia il gelato ma legge anche il giornale

3. Giorgio mangia il gelato e legge il giornale

Queste tre frasi hanno lo stesso significato, le tre congiunzioni mentre, ma, e hanno il ruolo di connettivi, servono cioè a collegare due frasi. Da un punto di vista logico considereremo l'unico connettivo di congiunzione "e" che indicheremo con il simbolo ∧ (AND).

La congiunzione logica AND

E' una operazione di composizione binaria interna che, applicata alla coppia ordinata P₁, P₂ di proposizioni, dà come risultato una proposizione composta P, ottenuta collegando P₁ con P₂ mediante la congiunzione e. Il risultato è quindi P=P₁∧P₂. Ci si chiede ora come varia il valore di verità della proposizione composta P=P₁∧P₂ in funzione dei valori di verità che possono assumere le proposizioni atomiche P₁, P₂. Per definizione si ha che la proposizione molecolare P=P₁∧P₂ risulti vera se e solo se le proposizioni P₁, P₂, sono contemporaneamente vere. La tavola di verità dell'operatore AND si presenta, come nella tabella di fianco.

Il connettivo AND e l'intersezione insiemistica

Esiste una stretta relazione tratra l'intersezione insiemistica e il connettivo logico AND. Partiamo da un esempio. Sia A l'insieme dei divisoridi 30 e B l'insieme dei divisori di 24.

Si noti che l'affermazione

10 ∈ A

significa che la proposizione 10 è un divisore di 30 è vera e l'affermazione

4 ∈ A

significa ch la proposizione 4 è un divisore di 24 è vera. Infine

3 ∈ A ∩ B

significa che la proposizione

3 è un divisore di 30 ∧ 3 è un divisore di 24 è vera

Possiamo allora concludere che l'operazione di intersezione di insiemi è corrispondente all'operazione logica di congiunzione

Il connettivo logico OR

Un altro modo di collegare proposizioni atomiche consiste nell'uso del connettivo OR (∨). OR applicato alla coppia ordinata di proposizioni P₁, P₂ dà come risultato una nuova proposizione composta P = P₁ ∨ P₂.

Ci si domanda come varia il valore di verità di P in funzione dei valori di verità che si possono attribuire alle proposizioni atomiche P₁, P₂. Per definizione, si ha che la proposizione composta P = P₁ ∨ P₂ risulta vera se e solo se almeno una delle proposizioni atomiche P = P₁, P₂ è vera.

Il connettivo logico OR e l'unione insiemistica

Anche tra il connettivo logico OR e l'oprazione di unione insiemistica esiste una stretta relazione. Partiamo da un esempio. Sia A l'insieme dei rettangoli e B l'insieme dei rombi. Siano inoltre f, g, h tre figure date. Si noti che l'affermazione f ∈ A significa che la proposizione "f è un rettangolo" è vera. D'altra parte g ∈ B, significa che la proposizione "g è un rombo" è vera. Infine h ∈ A ∨ B, significa che la proposizione "h è un rettangolo ∨ h è un rombo" è vera.

La disgiunzione esclusiva EOR (Exclusive OR)

E' un operazione di composizione binaria interna che, applicata alla coppia ordinata P₁, P₂ di proposizioni, dà come risultato una nuova proposizione composta ottenuta collegando P₁ con P₂.

Il risultato è quindi P = P₁ EOR P₂.

Il valore di verità di P per definizione risulta vera se e solo se una soltanto delle proposizioni P₁, P₂ risulta vera come descritto dalla tabella di verità riportata sotto.

Esempi:

P₁: l'anno prossimo mi iscrivo alla facoltà di matematica

P₁: l'anno prossimo mi iscrivo alla facoltà di fisica

P₁: Mario ha studiato l'inglese a scuola

P₁: Mario ha trascorso un lungo periodo in Inghilterra

P' = P₁ EOR P₂

P'' = P₃ OR P₄

Nella proposizione P' si è usato EOR in quanto P₁ esclude P₂. Nel comporre la proposizione P'' invece si è usato OR poichè la proposizione P₃ non esclude la P₄ ovvero Mario potrebbe parlare bene l'inglese in quanto lo ha studiato a scuola oppure perchè è stato un lungo periodo in Inghilterra, oppure perchè ha fatto tutte due queste cose.

Il connettivo EOR e la differenza simmetrica

L'oppure esclusivo EOR è gia stato considerato nella teoria degli insiemi, per definire l'operazione di differenza simmetrica. Esiste quindi una stretta analogia tra l'operatore logico EOR (aut), che si utilizza per comporre una coppia di proposizioni, e l'operazione di differenza simmetrica, usata per comporre due insiemi.

La negazione logica (NOT)

L'operazione di negazione logica NOT (non) è detta unitaria poichè si applica su una sola proposizione A₁ e dà come risultato una nuova proposizione A, A = Ã₁ (A = NOT A₁), così definita: il valore di verità di A è l'inverso del valore di verità di A₁. La tabella di verità è riportata di seguito.

A1	NOT A1
F	V
V	F

Esempio:

A₁: "Arezzo è il capoluogo della Toscana" proposizione il cui valore di verità è falso.

Ã₁: "Arezzo non è il capoluogo della Toscana", il cui valore di verità è vero, ossia l'inverso di quello di A₁

La negazione logica e l'insieme complementare

Sia A l'insieme dei numeri pari e N l'insieme universo. Il complementare di A è l'insieme dei numari dispari O. Si noti che 4 ∈ A, significa che la proposizione "4 è pari" è vera mentre 3 ∈ Ã significa che la proposizione "3 non è pari" è vera. Esiste quindi una stretta analogia tra l'operatore logico non che si applica ad una proposizione e il complementare di un insieme rispetto al suo ambiente.

L'implicazione materiale

E' un'operazione che, applicata alla coppia ordinata (P₁,P₂) di proposizioni dà per risultato una nuova proposizione P=P₁→P₂ i cui valori di verità dipendono unicamente da quelli assunti dagli operandi P₁,P₂ secondo una predefinita tavola di verità. Si osservi che le proposizioni P₁,P₂, in generale sono autonome una rispetto all'altra, nel senso che non si richiede alcuna correlazione tra l'argomento di cui tratta la P₁, e quello che interessa la P₂, inoltre P₁ e P₂, possono essere anche false. Consideriamo come esempio una proposizione tratta dal linguaggio comune:

"Se piove andiamo al cinema"

Assumendo come vera questa proposizione siamo portati a considerare come ammissibili tre situazioni:

1. Piove e quindi andiamo al cinema.

1. Non piove e non andiamo al cinema.

1. Non piove e andiamo al cinema.

La nostra affermazione ci lascia in effetti liberi di andare o non andare al cinema se non piove. Equivalentemente possiamo dire che l'affermazione "se piove andiamo al cinema" sarà falsa solo nel caso in cui piova e non si vada al cinema. Nella frase possiamo distinguere una prima proposizione, "se piove", che chiameremo antecedente e una seconda, "andiamo al cinema", che chiameremo conseguente. Date le osservazioni precedenti consideremo vera l'implicazione materiale se:

1. L'antecedente ed il conseguente sono falsi.

2. L'antecedente ed il conseguente sono veri.

3. L'antecedente è falso ed il conseguente è vero.

Il connettivo di implicazione materiale se ... allora ... lo indicheremo con il simbolo →. La proposizione p → q, sarà vera secondo la tavola di verità indicata sotto.

P1→P2		P2
		F	V
P1	F	V	V
	V	F	V

La deduzione logica

E' un ragionamento che costituisce la base della dimostrazione di un qualsiasi teorema. L'enunciato di un teorema si presena sempre nella forma seguente: se h allora t ovvero da h si deduce t ove le proposizioni h e t sono rispettivamente , ipotesi e tesi. Precisiamo che la deduzione logica è costituita dalla successione di ragionamenti, intuizioni, osservazioni e calcoli logicamente corretti che, a partire dalla verità dell'ipotesi h, conduce ad affermare che anche la tesi è vera, a differenza dell'implicazione materiale, in quanto non avrebbe alcun significato un teorema che avesse l'ipotesi falsa. Inoltre, in generale, gli argomenti trattati in h e t sono omogenei, cioè della stessa naturae correlati l'uno all'altro, in ogni caso l'implicazione materiale e la deduzione logica presentano analogie ad esempio sono entrambe non commutative e godono della proprietà transitiva ovvero:

se P₁ → P₂, e P₂ → P₃ allora P₁ → P₃

La deduzione logica e relazione di inclusione tra insiemi

Possiamo osservare che esiste un ben preciso collegamento tra la deduzione logica e la relazione di inclusione insiemistica. Si noti infatti che, se se A e B sono due insiemi, l'affermazione A ⊆ B equivale a dire che l'implicazione x ∈ A → x ∈ B è vera comunque si scelga un elemento x di A (∀ x ∈ A). E' bene sottolineare che in una implicazione è importante l'ordine in cui sono date le due proposizioni (non commutatività), infatti dalla veridicità dell'implicazione p → q non discende affatto che sia vera la q → p.

Esempio:

sia p: Mario è nato a Milano

sia p: Mario è lombardo

p → q è vera

q → p non è detto che sia vera

Ciò è evidente anche dal punto di vista insiemistico

Nel caso in cui due proposizioni si implichino a vicenda, cioè nel caso in cui siano vere sia p → q che q → p parleremo di doppia implicazione o equivalenza logica che indicheremo con il simbolo ∀. L'equivalenza logica corrispode alla coincidenza di insiemi, infatti A = B significa che la doppia implicazione x ∈ A ∀ x ∈ B è vera comunque si scelga un elemento x di A o di B.

La doppia deduzione logica

La doppia deduzione logica è una procedura in base alla quale, assegnate due proposizioni h e t, si può dimostrare che: Teorema 1 "da h, vera per ipotesi, si deduce, tramite ragionamenti logici, che anche la t è vera." Teorema 2 "da t, vera per ipotesi, si deduce, tramite ragionamenti logici, che anche la h è vera." Quest'ultimo è il teorema inverso del teorema 1, in quanto è stato ottenuto scambiando l'ordine delle proposizzioni h e t. Un teorema ed il suo inverso si possono unificare in un teorema complessivo il cui enunciato è del tipo seguente: " h è vera se e solo se t è vera" ove le proposizioni h e t sono dette logicamente equivalenti. Il teorema complessivo si enuncia, a volte secondo quest'altra formulazione: "Condizione necessaria e sufficiente affinchè h sia vera e che t sia vera." La condizione necessaria è espressa dal teorema diretto, "Da h vera si deduca t vera", la condizione sufficiente è rappresentata dal teorema inverso "Da t vera si deduca h vera".