Riassunti per esame di logica + esercizi, prof. Abrusci, Università Roma tre,

Capitolo 1

Cos'è una proposizione?

Le proposizioni sono anche chiamate enunciati, asserzioni o affermazioni. Possono essere semplici o composte in base al numero di predicati al loro interno. Possono contenere componenti che esprimono concetti logici; quando sono costituite solamente da quest'ultimi sono dette proposizioni logiche.

Cos'è una dimostrazione?

Le dimostrazioni servono a stabilire, accettare proposizioni. Una proposizione è dimostrabile attraverso calcoli, osservazioni, ragionamenti o constatazioni. Scriviamo x:├ A per dire che una cosa x è una dimostrazione di una proposizione A; per dire semplicemente che una proposizione A è dimostrabile possiamo scrivere ├ A.

Cos'è una refutazione?

Le refutazioni servono a rigettare proposizioni. Una proposizione è refutabile attraverso calcoli, osservazioni, ragionamenti o constatazioni. Scriviamo x: A├ per dire che una cosa x è una refutazione di una proposizione A; per dire semplicemente che una proposizione A è refutabile possiamo scrivere A├.

Cos'è una dimostrazione da ipotesi?

Si chiama dimostrazione di una tesi A da un’ipotesi o premessa B ciò che permette di trasformare ogni dimostrazione di B in una dimostrazione di A (x: B├B) e ogni refutazione della conclusione A nella refutazione della premessa B (x: A├ B). La presentazione di una dimostrazione di A da B è detta presentazione dall’alto verso il basso (lettura top-down), invece la riconduzione dalla conclusione A all’ipotesi B è detta presentazione dal basso verso l’alto (o lettura bottom-up).

Cos'è un dibattito?

Ci devono essere almeno due soggetti, l’uno nel ruolo di proponente e l’altro nel ruolo di opponente. Il primo avvia il dibattito proponendo una proposizione A che vuole sostenere, mentre l’opponente risponde con una proposizione B che intende contrapporre ad A e che è detta contraddittoria di A. Il ruolo di proponente e opponente può scambiare durante il dibattito. Il dibattito procede attraverso mosse alternate e contrapposte. I partecipanti seguiranno una strategia che permetterà di anticipare le mosse dell’avversario e che porterà conseguentemente alla vittoria.

Concetto di dualità

La dualità richiede la presenza di due punti di vista alternativi fra loro. Ad esempio le figure del cliente / commerciante, di input / output o di vero / falso. Due proposizioni sono logicamente duali quando le dimostrazioni di una sono le refutazioni dell'altra e le refutazioni di una sono le dimostrazioni dell'altra; data una proposizione A, c'è una sola proposizione che è logicamente duale ad A, e questa proposizione viene chiamata "il duale logico di A" o "la negazione di A" o "la contraddittoria di A". Indichiamo con la notazione A il duale logico di una proposizione ~A.

Cosa sono le classi

Le classi sono aggregati di oggetti o enti. Indichiamo le classi generiche con X, Y, Z e con a, b, c gli enti generici appartenenti alle classi. Le classi possono essere finite o infinite. Le classi finite con nessun elemento sono dette vuote; con un solo elemento singoletti, con due elementi coppie e in generale una classe con n elementi è detta n-pla. I concetti logici di una classe sono quelli di appartenenza (la cosa a appartiene alla classe X), di uguaglianza (X è uguale a Y), di condivisione (dove due classi condividono qualcosa) e di separazione (dove X e Y sono separate).

Classi ordinate

Le classi ordinate sono quelle classi in cui gli enti sono disposti in un preciso ordine. Esistono coppie ordinate, triple ordinate ed n-pla ordinate. L’ordine di tali classi può essere totale quando c’è interazione tra tutti i componenti o parziale quando non ci sta. Esempio di classi ordinate parziali sono gli alberi genealogici.

Cosa sono le operazioni

Le operazioni, anche chiamate funzioni, fanno passare da enti di certe classi a enti di altre classi. Usiamo le lettere f, g, h per indicare generiche operazioni. Le operazioni sono determinate da due classi: la classe X, detta dominio o classe di partenza, in cui ci sono gli enti a cui si può applicare l’operazione e la classe Y, detta codominio o classe di arrivo, in cui ci sono i valori possibili che sono il risultato di un’operazione. F(a) = b indica l’applicazione di un’operazione in cui a rappresenta una cosa appartenente al suo dominio e b la cosa appartenente al codominio di f. Intendiamo operazioni logiche l’intersezione, che fa passare da due classi X e Y alla classe che contiene tutti gli elementi comuni alle due classi e nient’altro e l’unione.

Proprietà

Le proprietà su una classe X interpongono una relazione tra un soggetto e una sua proprietà. Intendiamo le proprietà come delle operazioni unarie perché associano ad ogni cosa di una certa classe X una proposizione P(a).

Relazione

Le relazioni sono operazioni n-arie da X alla classe delle proposizioni. Indicheremo con R(a,b) la proposizione ottenuta applicando la relazione R ad una coppia ordinata o con R(a … a₁) se ci troviamo in una relazione n-aria.

Strategia

Usiamo strategie per raggiungere un obiettivo. Intendiamo algoritmi o programmi quelle strategie che servono a calcolare operazioni, e test strategie che servono a stabilire il possesso di una proprietà o relazione. Sono costituite da prescrizioni o istruzioni e devono essere finite e concrete. Le strategie possono essere sequenziali o non sequenziali; le prime devono essere seguite passo dopo passo anche da una sola persona, le seconde invece hanno bisogno di essere svolte in passi simultanei e occorrono quindi più soggetti che collaborano.

Macchine e reti

Le macchine sono soggetti che seguono strategie sequenziali compiendo atti concreti e materiali. Le reti invece sono soggetti che seguono strategie non sequenziali e sono composte da più macchine che interagiscono fra loro. Internet è un’immensa rete di macchine calcolatrici.

Organizzazione delle conoscenze

Noi abitualmente tendiamo a mettere in ordine le nostre conoscenze attraverso un’organizzazione, chiamata organizzazione assiomatica. Troviamo un numero finito, il più piccolo possibile, di proposizioni, chiamate assiomi al cui interno compaiono solo e solamente concetti primitivi e logici. Così possiamo ottenere una conoscenza completa di ogni disciplina partendo da pochi assiomi. Grazie ad Euclide abbiamo un’organizzazione assiomatica della geometria, con Spinoza della filosofia, con Newton della fisica e con Peano dei numeri naturali.

Capitolo 2

Di cosa si occupa la logica classica?

La logica classica si occupa della parte teorica di ogni disciplina. Prescinde dal tempo e dallo spazio e dalla causalità. Riflette sulla veridicità o falsità di una proposizione in quell’istante immediato.

Che cos'è una proposizione?

Una proposizione in logica classica è un bit immutabile, cioè può avere solo due valori distinti di verità (1) e falsità (0). La classe dei possibili valori di una proposizione classica è indicata con {0,1}. La concezione delle proposizioni in logica classica è estensionale, ovvero si limita a considerare solo il suo valore, bivalente, poiché i valori possono essere solo vero o falso e aspaziale e atemporale, ovvero il valore delle proposizioni prescinde dal tempo e dallo spazio.

La negazione classica

Il duale logico di una proposizione in logica classica è chiamato negazione classica di quella proposizione. Indichiamo con A la negazione classica di A. Il valore di A dipende da A, dal momento che in logica classica una proposizione può avere uno e un solo valore in un dato istante. La negazione classica permette di stabilire una dualità tra dimostrazione e refutazione di una proposizione: se x:├ A allora x: A├.

I principi della logica classica

Esistono 4 principi fondamentali nella logica classica: il principio di interazione afferma che dalla refutazione di una delle due proposizioni si ottiene la dimostrazione dell’altra secondo la formula ├ A, A. Il principio del terzo escluso che non ammette una terza possibilità oltre al fatto che una proposizione debba essere imprescindibilmente vera o falsa. Il principio di non-contraddizione che A e A non possono essere entrambe vere e non possono essere entrambe false. Ed infine il principio di identità che afferma che dall’ipotesi che una delle due proposizioni è vera segue che l’altra è falsa.

Regole fondamentali

Il modus ponens è una regola fondamentale nel nostro ragionamento. Questa afferma che dalla dimostrazione A e dalla dimostrazione da ipotesi di B da A si consegue che B è vera. In generale la regola del modus ponens preserva la verità dell’ipotesi alla conclusione. A ├ A ├ B B

Il modus tollens al contrario preserva la falsità della conclusione all’ipotesi. Avendo una dimostrazione di B e una dimostrazione di A da B allora abbiamo una dimostrazione di ￢A. ├ ￢B A ├ B.

La terza regola principale, chiamata regola della transitività o comunicazione input/output afferma che se abbiamo una dimostrazione di A da B e una dimostrazione di C da A allora abbiamo anche una dimostrazione di C da B. B ├ A A C ├ B C.

Queste tre regole possono essere generalizzate nella regola del taglio, dal momento che in ognuna di queste si "taglia" una proposizione che compare in una dimostrazione come conclusione e nell'altra come ipotesi.

A fortiori e consequentia mirabilis

La regola della conseguenza mirabile e la regola dell' "a fortiori" sono le regole caratteristiche della logica classica, nel senso che usare tali regole costringe ad accettare che le proposizioni siano BIT immutabili e dunque ad accettare la concezione della logica classica. La regola della contrazione o consequentia mirabilis afferma che avendo una dimostrazione di A da A allora abbiamo una dimostrazione di A, ovvero sappiamo che A è vera. La dimostrazione di A viene dimostrata attraverso la sua stessa refutazione. ￢A ├ A = A ├ A, A.

La regola dell'a fortiori o dell’indebolimento afferma che avendo una dimostrazione di B allora abbiamo anche una dimostrazione di B da A. Dunque la proposizione B discende da A ├ B.

Capitolo 3

Definizione dei connettivi classici

Date due proposizioni A e B possiamo formarne una nuova mediante l’uso dei connettivi proposizionali quali: congiunzione “e”, disgiunzione “o, oppure”, l’implicazione “se..allora” e l’equivalenza “…se e soltante se…”. La logica deve trovare la definizione di ogni connettivo, ovvero quale proposizione tale connettivo produce; deve fissare qual è e come si esprime la sua negazione e fissare quali sono le regole di dimostrazione per ogni connettivo. La concezione dei connettivi è una concezione estensionale, ovvero si basa solo sul valore delle proposizioni e vero-funzionale in quanto il valore di una proposizione derivata dipende unicamente dal valore delle due proposizioni. I casi possibili in cui possono stare due proposizioni o bit sono 4.

Congiunzione classica

La congiunzione è un connettivo principale. Il valore della congiunzione “e” è vero quando entrambe le proposizioni sono vere (A = B = 1). Denotiamo con il simbolo ˄ la congiunzione classica. Il comportamento della congiunzione classica è fissato dalla sua tabella. Un circuito che dati due bit di ingresso, produce in uscita un bit e che si comporta secondo la tabella della congiunzione classica è detto circuito AND. La negazione della congiunzione, ovvero il suo duale, è la disgiunzione. ￢(A˄B) = ￢A ˅ ￢B.

Per dimostrare la congiunzione bisogna effettuare due dimostrazioni separate, una per la proposizione A e una per la B. Dalla verità di A e dalla verità di B passiamo alla verità di A˄B e dalla falsità di A˄B possiamo concludere che una delle due proposizioni è falsa. Nelle dimostrazioni possiamo usare la congiunzione per scoprire che dalla verità di A˄B abbiamo la verità di A o B e dalla falsità di A o B possiamo concludere la falsità di A˄B.

Disgiunzione classica

La disgiunzione è un connettivo principale. Esistono due modi, in logica classica, per indicare la disgiunzione: nel senso latino di vel o di aut (alternativa classica). Nel primo caso il valore di “o” ...