Logica matematica

Il concetto di regola di deduzione

In generale, potremo chiamare deduzione, un qualunque processo che da certe premesse P permette di ricavare, mediante determinate regole di deduzione, una conclusione C.

Le premesse P possono comprendere una o più proposizioni collegate tra loro da connettivi locigi, mentre le regole di deduzione sono procedure generalmente basate sui principi e sulle leggi della logica, la conclusione è anch'essa costituita da una o più proposizioni. Il cardine del processo di deduzione è rappresentato dalla casella centrale dello schema precedente, la conoscenza e la corretta utilizzazione delle regole di deduzione sono alla base di un qualunque ragionamento valido.

Regola di inferenza induttiva (modus ponens)

Questa regola di ragionamento si può rappresentare mediante lo schema presente nella seguente tabella:

La regola modus ponens si può così enunciare: se l'implicazione P₁→P₂ è vera e l'antecedente P₁ è vera allora anche la conseguente P₂ è vera. La correttezza di questa regola di ragionamento deriva dalla constatazione che la funzione proposizionale equivalente f(P₁,P₂)=[(P₁→P₂)∧P₁]→P₂ è sempre vera e quindi in base alla verità delle premesse anche la conclusione è vera.

Esempio

Regola d'inferenza della controinversa (modus tollens)

Questa regola di ragionamento si può sintetizzare mediante lo schema presente nella seguente tabella:

La regola modus tollens si può così enunciare: se l'implicazione A₁→A₂ è vera e la negazione di A₂ è vera allora anche la negazione di A₁ è vera. La correttezza di questa regola di ragionamento deriva dalla constatazione che la funzione proposizionale ad essa equivalente: f(A₁,A₂)=[(A₁→A₂)∧Ã₂]→Ã₁ è sempre vera e quindi in base alla verità delle premesse anche la conclusione è vera.

Esempio:

Il sillogismo ipotetico

Il sillogismo rappresenta il tipo fondamentale di ragionamento deduttivo della logica aristotelica, esso è composto da tre proposizioni, le prime due costituiscono le premesse, e si suppongono vere, mentre la terza è la conclusione la cui verità discende necessariamente dalle premesse. La regola di deduzione, detta sillogismo ipotetico, si può sintetizzare mediante lo schema presente nella seguente tabella:

Il sillogismo ipotetico si può così enunciare: se l'implicazione P₁→P₂ è vera e l'implicazione P₂→P₃ è vera, allora anche l'implicazione P₁→P₃ è vera. La correttezza di questa regola di ragionamento deriva dalla constatazione che la funzione proposizionale ad essa equivalente: f(P₁,P₂,P₃)=[(P₁→P₂)∧(P₂→P₃)]→(P₁→P₃) è sempre vera e quindi in base alla verità delle premesse anche la conclusione P₁→P₃ risulta vera.

Esempio:

Il sillogismo disgiuntivo

Questa regola di deduzione si può sintetizzare mediante lo schema presente nella seguente tabella:

Il sillogismo disgiuntivo si può così enunciare: se l'implicazione A₁∨A₂ è vera e l'implicazione Ã₂ è vera, allora anche l'implicazione A₁ è vera. La correttezza di questa regola di ragionamento deriva dalla constatazione che la funzione proposizionale ad essa equivalente: f(A₁,A₂)=[(A₁∨A₂)∧(Ã₂)]→(A₁ ) è sempre vera e quindi in base alla verità delle premesse anche la conclusione A₁ risulta vera.

Esempio:

Il problema della decisione

Nel caso della logica proposizionale, il metododelle tabelle di verità, costituisce un procedimento di decisione. Data una qualunque peoposizione, si può stabilire, con un numero finito di passaggi, se essa assume sempre e solo il valore vero, oppure se in qualche caso assume il valore falso. Nel primo caso diciamo che si tratta di una tautologia o legge logica.Siamo quindi in grado di verificare se, una certa espressione è una legge logica o no,ma non possiamo, cosa molto più interessante, generare l'insieme delle leggi logiche, cioè generare un procedimento che ci permetta di dedurre tali leggi da altre assunte come vere. Al fine di risolvere il problema precedente, cioèdi dedurre in una teoria scientifica, in modo corretto, le proposizioni sempre vere, si utilizzano i sistemi formali di deduzione in cui si può dimostrare la validità di un'affermazione senza ricorrere alle tabelle di verità. In un sistema formale di deduzione, partendo da determinate premesse, si deducono certe conclusioni, senza considerae il significato dei termini che in esse compaiono. Vediamo come si procede per costruire in un sistema formale di deduzione:

1. Si introduce un linguaggio preciso e rigoroso.

2. Si scelgono, tra le frasi del linguaggio, alcune proposizioni da porre alla base della teoria, delle quali si accetta la verità per convenzione, senza alcuna dimostrazione. Tali frasi vengono dette assiomi.

3. Si formulano alcune regole dette regole di deduzione o inferenza, in virtù delle quali si deducono le altre proposizioni.

Il numero delle regole dev'essere minimo ed il loro contenuto semplice.

In un primo momento si applicano le regole di deduzione agli assiomi ottenendo nuove proposizioni, dette teoremi, quindi si applicano le solite regole al nuovo insiemedi proposizioni così ottenute e si ottengono altre proposizioni.

Un semplice sistema formale

Il gioco delle stelle e delle barre.

Consideriamo un gioco che usa quattro simboli: le lettere A e B, le stelle e le barre.

A B ★ /

Questi simboli possono essere combinati in diversi modi, utilizzando un numero arbitrrio di copie di ciascun simbolo. Ad esempio:

A★BA    //★★A   /A★B/

Sono tutte stringhe costruite con questi simboli. Stabiliamo che alcune delle stringhe possibili siano vincenti e le altre perdenti. Ovviamente, come in qualsiasi gioco devono esserci delle regole, nel nostro caso servono regole che specifichino quali stringhe siano vincenti e quali perdenti. Adotteremo le tre seguenti regole:

1. Il simbolo A da solo è stringa vincente

2. Il simbolo B da solo è stringa vincente

3. Se S₁ e S₂ sono striscie vincenti allora anche /S₁★S₂/ è striscia vincente

E' sottointeso che nessun altra stringa, al di fuori di quelle ottenute mediante queste tre regole, è vincente. Per chiarire il significato di queste regole, iniziamo a giocare. In base alle prime due regole la stringa A e la stringa B sono vincenti. Ora che abbiamo due srtinghe vincenti, possiamo applicare la regola tre, assumendo S₁="A" e S₂="B", otteniamo /A★B/. Applichiamo di nuovo la regola 3, assumendo stavolta S₁="B" e S₂="A" otteniamo cosi la striscia vincente /B★A/. Abbiamo ora a disposizione quattro stringhe vincenti ed è chiaro che possiamo ottenerne molte altre, continuando ad applicare la regola 3. Ad esempio posto S₁="A" e S₂="/B★A/", otteniamo la stringa vincente /A★/B★A//. La striga /A★/B★A/ è invece perdente poichè non può essere ottenuta mediante le tre regole viste.

Sistemi formali

Il gioco delle stelle e delle barre evidenzia le componenti fondamentali del tipo più semplice di sistema formale. Un sistema formale è costituito da tre elementi caratteristici:

1. Un insieme di simboli con cui formare stringhe ed un insieme di regole che specificano che cos'è una stringa ben formata. Nel nostro gioco i simboli sono A B ★ / ogni stringa si considera ben formata, purchè sia costruita da questi simboli.

2. Un elenco di stringhe vincenti, detto insieme degli assiomi. Nel nostro gioco gli assiomi sono definiti da 1. e 2.

3. Un insieme di metodi per costruire nuove stringhe vincenti, detto insieme delle regole di inferenza. Il nostro gioco ha una sola regola di questo tipo: la 3.

Una stringa vincente è una particolare stringa ben formata, costituita da un esemplare di assioma oppure costruita apartire da stringhe vincenti già note, mediante applicazioni delle regole di inferenza. In logica e in matematica le stringhe vincenti sono dette teoremi. Nel nostro gioco /A★B/ è un teorema, è infatti una stringa vincente, in virtù delle regole 1. e 2. e di un'applicazione della regola 3.

Gli enti primitivi

Consideriamo l'insieme π={A,B,C,D....} che chiamiamo piano, chiamiamo punti gli elementi A,B,C,D... del piano. Nel piano π esistono sottoinsiemia,b,c,d... che chiamiamo rette. I punti, le rette, es il piano sono denominati enti primitivi, perchè di essi non viene data alcuna definizione esplicita in quanto costituiscono gli elementi base a partire dai quali si definiscono tutte le altre figure geometriche. Definire un certo oggetto X, significa determinare, in modo breve e preciso, le qualità essenziali che caratterizzano l'oggetto stesso, cosicchè sia possibile riconoscerlo, senza ombra di dubbio, tutte le volte che lo si incontra in un qualsiasi contesto. Ad esempio, "Si dice trapezio un quadrilatero avente due lati opposti paralleli che si chiamano basi". Come si può osservare, il concetto di trapezio è definito dai seguenti vocaboli: quadrilatero, lato, parallelo. Chi non conosce il significato di questi tre vocaboli nonè in grado di disegnare il trapezio. In generale, per definire un oggetto X occorre far riferimento ad altri oggetti a, b, c ... dei quali dev'essere noto il significato, questi ultimi pertanto, saranno stati "spiegati" ricorrendo ad altri oggetti: α, β, γ ... i quali a loro volta saranno stati spiegati facendo riferimento ad altri oggetti p, q, r ... e così via. Si pensi al vocabolario dove una parola è definita da altre parole, le quali, a loro volta sono definite a partire da altre parole e così doi seguito. Si comprende che è ingenuo pensare di procedere su questa via con l'intento di definire tutti gli oggetti, finiremmo sicuramente per compiere un giro vizioso che ci porterebbe nuovamente all'oggetto X, ossia a definire X facendo riferimento ad X stesso. Per evitare di cadere nel giro vizioso si può operare nel seguente modo:

1. Si abbandona il progetto divoler definire tutto.

2. Si scelgono alcuni oggetti, in generale, noti a tutti, dei quali non si dà alcuna definizione esplicita, denominati enti primitivi.

3. Si definiscono tutti gli altri oggettifacendo riferimento agli enti primitivi

Gli enti primitivi del piano sono il punto e la retta, di essi non si dà alcuna definizione esplicita, tuttavia risultano definiti implicitamente dai postulati, nel senso che si chiameranno punti e rette elementi di natura qualunque, purchè soddisfino alle proprietà chiaramente indicate dai postulati.

I postulati e le loro proprietà

Colui che costruisce una geometria, vi domanda di accettare, senza pretendere alcuna dimostrazione, un certo numero di proposizioni, di solito assai semplici,denominate postulati. I postulati non possono essere arbitrari, ma devono possedere tre notevoli proprietà:

1. La compatibilità: ciò significa che, nella famiglia dei postulati, deve valere il principio della non contraddizione, ossia, a partire dai postulati, non si deve mai poter dedurre la proposizione A e, contemporaneamente, la proposizione Ã.

2. L'indipendenza: ciò significa che nessun postulato deve potersi dedurre logicamente dai rimanenti. Qualora un certo postulato fosse deducibile dai rimanenti, verrebbe tolto dalla famiglia dei postulati ed incluso nella famiglia dei teoremi.

3. La completezza: ciò significa che il numero dei postulati non deve essere troppo esiguo cosicchè a partire da essi, si possa dimostrare un certo numero di teoremi.

Il concetto di teorema

Un teorema, è un enunciato che si presenta nella seguente forma:

"Se H allora T"

Ad esempio è un teorema appartenente al dominio della geometria euclidea è quello avente il seguente enunciato: "Se un quadrilatero ABCD è un rettangolo allora ABCD ha le diagonali uguali".

La prima proposizione H:= "Un quadrilatero ABCD è un rettangolo" è detta ipotesi e costituisce la premessa, ossia ciò che si suppone noto. La seconda proposizione "ABCD ha le diagonali uguali" è detta tesi e ne costituisce la conclusione, ossia la proposizione che si vuol dimostrare. La dimostrazione è il ragionamento deduttivo, in base al quale, a partire dalla verità dell'ipotesi, si giunge a concludere che anche la tesi è verà.

Proposizioni associate ad un teorema

Consideriamo una proposizione molecolare del tipo "Se H allora T", rappresenta l'enunciato di un teorema che chiameremo diretto, per distinguerlo da altre proposizioni che ne derivano. Ammettiamo che il teorema diretto sia vero, ossia che a partire dall'ipotesi H, si possa dedurre, tramite ragionamenti logicamente corretti, che anche la tesi è vera. In corrispondenza del suddetto teorema, si possono enunciare altre tre proposizioni, due delle quali sono genelalmente false, mentre la terza è sempre vera. Analizziamole in dettaglio:

La proposizione inversa - Si ottiene dal teorema diretto scambiando di posto le proposizioni H e T cosicchè risulta il nuovo enunciato: "Se T allora H". Questa proposizione risulta generalmente falsa, infatti dalla verità della premessa, non è possibile dedurre logicamente la verità della conclusione come dimostra il controesempio: "Se un quadrilatero ABCD ha le diagonali uguali allora ABCD è un rettangolo", che non è vera poichè ABCD può essere un trapezio isoscele.

La proposizione contraria - Si ottiene dal teorema diretto, negando l'ipotesi e la tesi cosicchè risulta il nuovo enunciato: "SE non H allora non T". Nell'esempio precedente la proposizione contraria risulta: "Se un quadrilatero ABCD non è un rettangolo allora ABCD non ha le diagonali uguali" che non è vera in quanto un rombo, che non ha le diagonali uguali, non è un rettangolo.

La proposizione controinversa - Si ottiene dal teorema diretto prima scambiando di posto le proposizioni H e T poi negandole entrambe cosicchè risulta il nuovo enunciato: "Se non T allora non H". Questa proposizione risulta sempre vera, come si può notare dalla tavola di verità relativa. Nell'esempio precedente la proposizione controinvrsa risulta: "Se un quadrilatero ABCD non ha le diagonali uguali allora ABCD non è un rettangolo", che è sempre vera.

Nello stesso modo, se è vera la controinversa, allora è vera la diretta. Le due proposizioni, diretta e controiversa, risultano così logicamente euivalenti e quindi dimostrando la verità di una di esse, resta dimostrato per via indiretta, anche la verità dell'altra.

Come si dimostra un teorema

Per dimostrare un teorema si possono utilizzare due diversi ragionamenti deduttivi:

1. metodo diretto

2. metodo indiretto o per assurdo

La scelta dell'uno o dell'altro metodo è dettata, caso per caso, da motivi di convenienza. Il medodo diretto consiste nel partire dall'ipotesi e mediante una successione ordinata di ragionamenti logici, ciascuno conseguente del precedente, si giunge a concludere che anche la tesi è vera. Il medodo indiretto consiste in un ragionamento deduttivo basato sulla seguente considerazione: poichè la proposizione da dimostrare "Se H allora T" è logicamente equivalente alla sua controinversa "Se non T allora non H", qualora si dimostri la verità di quest'ultima, si può concludere che anche la proposizione "H → T" è vera. Il metodo indiretto può essere sinteticamente descritto dal seguente diagramma:

Per assurdità si deve intendere una affermazione che sia in contraddizione con almeno una delle seguenti proposizioni vere:

1. L'ipotesi

2. Un postulato

3. Un teorema precedentemente dimostrato

Lemmi e corollari

Si chiama lemma un teorema che si prefigge l'obiettivo di facilitare la dimostrazione di un successivo notevole teorema.

Si chiama corollario un teorema che sia l'immediata conseguenza di un altro teorema appena dimostrato, oppure di un postulato.

Esempi di teoremi

Supponiamo che Tizio affronti un esame per ottenere l'abilitazione a svolgere un determinato lavoro e che siano stabiliti i seguenti assiomi assunti come veri.

A1. Se Tizio risponde almeno a 6 domande su 10, Tizio supera l'esame.

A2. Se Tizio ha meritato la lode allora Tizio ha risposto esattamente a tutte le domande.

A3. Se Tizio è stato assunto dalla ditta X&Y, allora Tizio ha meritato la lode nell'esame.

A4. Se Tizio supera l'esame, allora Tizio lavora.

Dimostriamo ora i teorem1 Th1. e Th2.

Th1. Se Tizio è impiegato nella ditta X&Y, allora Tizio ha risposto a tutte le domande del test d'esame

Dimostrazione: La premessa, detta ipotesi, assunta come vera è che Tizio è un impiegato della ditta X&Y. Partendo da questo enunciato vero ed applicando la regola del modus ponens all'assioma A3 concludiamo che, essendo vera la premessa, è vera anche la conclusione: Tizio ha meritato la lode. Essendo vera la premessa dell'assioma A2, riapplicando il modus ponens all'assioma A2 otteniamo che è vera anche la conseguenza: Tizio ha risposto esattamente a tutte le domande.

Th2. Se Tizio non lavora, allora Tizio non ha risposto ad almeno 6 domande del test d'esame

Dimostrazione: L'ipotesi, assunta come vera è che Tizio non lavora. Applicando la regola del modus ponens all'assioma A4 concludiamo che, essendo falso il conseguente è falso anche l'antecedente, pertanto Tizio non ha superato l'esame. Applicando nuovamente la regola del modus ponens all'assioma A1, abbiamo che, essendo falso il conseguente è falso anche l'antecedente, pertanto la tesi risulta valida.