Algebra 1/Insiemi Logica Relazioni/Logica di base: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Riga 388:
=== I teoremi ===
Un ''teorema'' è una proposizione composta del tipo <math>I\Rightarrow T</math>, cioè una implicazione tra due proposizioni, dette ''ipotesi'' (<math>I</math>) e ''tesi'' (<math>T</math>). Dimostrare un teorema significa fare un ragionamento logico che permetta di concludere che la tesi è vera avendo supposto che l’ipotesi è vera.
In generale incontreremo molti teoremi che vengono denominati genericamente ''proposizioni'', perché il nome di “teorema” viene tradizionalmente attribuito solo ai teoremi più importanti. Inoltre si usa chiamare ''lemma'' una proposizione che non ha una grande importanza di per sé, ma che è particolarmente utile per la dimostrazione di altri teoremi. Si chiama invece ''corollario'' un teorema che è una conseguenza immediata di un altro teorema.
All’interno di una teoria matematica non è possibile dimostrare tutte le proposizioni, alcune devono essere assunte come vere senza dimostrarle, esse costituiscono la base della teoria sulle quali si fondano le dimostrazioni dei teoremi. Queste proposizioni si chiamano ''postulati'' o ''assiomi''. Risulta evidente che cambiando sia pure uno solo degli assiomi cambiano anche i teoremi dimostrabili e quindi la teoria.
=== La deduzione ===
Nel paragrafo precedente abbiamo parlato in modo generico di implicazione, deduzione, dimostrazione. Facciamo ora un po’ di chiarezza sull’uso di questi termini. L’''implicazione'' è un’operazione tra proposizioni, mentre la ''deduzione'' è il ragionamento logico che costituisce la base della dimostrazione di un teorema. Per l’''implicazione materiale'' si usa il simbolo <math>\rightarrow</math> mentre per la ''deduzione logica'' si usa il simbolo <math>\Rightarrow</math>.
La frase <<Se 5 è un numero pari, allora il triangolo ha 4 lati>> è perfettamente valida da un punto di vista della logica matematica ed anzi è vera, poiché la premessa (proposizione antecedente) è falsa, per cui l’implicazione è vera anche se la proposizione conseguente è falsa (si tenga presente la tavola di verità di <math>p\Rightarrow q</math>). Si noti però che la definizione di implicazione ha senso solamente se la premessa è vera, il suo ampliamento al caso in cui la premessa è falsa è motivata da ragioni di completezza della trattazione. Bisogna quindi fare attenzione ad usare l’implicazione logica quando la premessa è falsa. Teniamo comunque conto che se <math>p</math> è falsa allora <math>(p\Rightarrow q)\wedge (p\Rightarrow \neg q)</math> cioè <math>p\Rightarrow (q\wedge \neg q)</math> è vera. Ma <math>q\wedge\neg q</math> è una contraddizione, quindi una premessa falsa implica sempre una contraddizione.
In realtà, la dimostrazione di un teorema non è la verifica della validità dell’implicazione, anzi è un procedimento che fa uso della validità dell’implicazione stessa. In un teorema si parte dal supporre vera l’ipotesi e si dimostra, seguendo un ragionamento logico che si basa sugli assiomi e altri teoremi già dimostrati in precedenza, che anche la tesi è vera (questo se si segue il ''procedimento diretto''). Se si segue invece il ''procedimento indiretto'' (o ''per assurdo''), si suppone che la tesi sia falsa e, sempre mediante assiomi e altri teoremi già dimostrati, si arriva, tramite passaggi logici, ad affermare che l’ipotesi è falsa (cosa che non si deve accettare).
Le principali regole del corretto ragionamento seguono alcuni schemi particolari (detti ''sillogismi'', dal nome ad essi attribuito da Aristotele<ref>filosofo, scienziato e logico della grecia antica (383 o 384 – 322 ).
</ref>). Presentiamo qui i quattro principali sillogismi: il ''modus ponens'', il ''modus tollens'', il ''sillogismo disgiuntivo'' e il ''sillogismo ipotetico''.
{| style="margin:auto; border-top: 1px solid #000; border-bottom: 1px solid #000; width: 70%; text-align: center;"
|align="center"|
|align="center"|Modus
|align="center"|Modus
|align="center"|
|align="center"|Sillogismo
|align="center"|
|-
|align="center"|
|align="center"|ponens
|align="center"|tollens
|align="center"|
|align="center"|ipotetico
|align="center"|
|-
|align="center"|1<sup>a</sup> premessa
|align="center"|<math>p\Rightarrow q</math>
|align="center"|<math>p\Rightarrow q</math>
|align="center"|<math>p\vee q</math>
|align="center"|<math>p\vee q</math>
|align="center"|<math>p\Rightarrow q</math>
|-
|align="center"|2<sup>a</sup> premessa
|align="center"|<math> p </math>
|align="center"|<math> \neg q </math>
|align="center"|<math> \neg p </math>
|align="center"|<math> \neg q </math>
|align="center"|<math>q\Rightarrow r</math>
|-
|align="center"|conclusione
|align="center"|<math> q </math>
|align="center"|<math> \neg p </math>
|align="center"|<math> q </math>
|align="center"|<math> p </math>
|align="center"|<math>p\Rightarrow r</math>
|}
Suggeriamo una lettura degli schemi appena esposti:
* ''modus ponens'': se sappiamo che <math>p</math> implica <math>q</math> e che <math>p</math> è vera, allora possiamo concludere che anche <math>q</math> è vera (metodo diretto di dimostrazione);
* ''modus tollens'': se sappiamo che <math>p</math> implica <math>q</math> e che <math>q</math> è falsa, allora possiamo concludere che anche <math>p</math> è falsa (metodo indiretto di dimostrazione);
* ''sillogismo disgiuntivo'': se sappiamo che, tra <math>p</math> e <math>q</math>, almeno una delle due è vera, e sappiamo che <math>p</math> (rispettivamente <math>q</math>) è falsa, allora possiamo concludere che <math>q</math> (rispettivamente <math>p</math>) è vera;
* ''sillogismo ipotetico'': se sappiamo che <math>p</math> implica <math>q</math> e che <math>q</math> implica <math>r</math>, allora possiamo concludere che <math>p</math> implica <math>r</math> (proprietà transitiva dell’implicazione).
Altre regole (note come i ''giudizi'' di Aristotele) fanno uso dei predicati e dei quantificatori. Riprendiamo un esempio precedente traducendo la frase <<tutti i quadrati hanno due diagonali>> e la sua negazione <<non tutti i quadrati hanno due diagonali>> in formule che fanno uso anche del linguaggio degli insiemi. Se chiamiamo <math>Q</math> l’insieme di tutti i quadrati e <math>P</math> la proprietà dell’avere due diagonali, se <math>x</math> è il generico quadrato (elemento di <math>Q</math>), <math>P(x)</math> è il predicato <<<math>x</math> gode della proprietà <math>P</math>>>, cioè <<<math>x</math> ha due diagonali>>, la frase <<tutti i quadrati hanno due diagonali>> si traduce in simboli: <math>{\forall}x\in Q</math>, <math>P(x)</math>.
La sua negazione è: <<esiste almeno un quadrato che non ha due diagonali>>, cioè che non gode della proprietà <math>P</math>, e si traduce in simboli così: <math>\exists x\in Q</math>, <math>\neg P(x)</math>. In quest’ultimo caso, la virgola può anche essere sostituita da una barra verticale (“”) o da “<math>:</math>” e si legge “tale che”.
Analogamente, una frase del tipo <<esiste almeno un numero naturale che sia divisore di <math>10</math>>> può scriversi come: <math>\exists n\in\mathbb{N}\mid D(n)</math>, dove <math>D</math> è la proprietà dell’essere divisore di <math>10</math> e <math>D(n)</math> significa che <math>n</math> verifica la proprietà <math>D</math>, cioè che <math>n</math> è un divisore di <math>10</math>. La sua negazione è <<nessun numero naturale è divisore di 10>>, ovvero <<preso un qualsiasi numero naturale <math>n</math>, questo non gode della proprietà <math>D</math>>>, la traduzione in simboli di tale frase è: <math>\forall n\in\mathbb{N}</math>, <math>{\neg}D(n)</math>.
Mettiamo in tabella le quattro proposizioni, che corrispondono ai giudizi di Aristotele:
{| class="wikitable" style="margin:auto; width: 70%; text-align: center;"
|align="center"|
|align="center"|<math>\forall x\in Q</math>, <math>P(x)</math>
|align="center"|
|align="center"|<math>\exists n\in\mathbb{N}\mid D(n)</math>
|-
|align="center"|
|align="center"|*<span><math>P</math> è vera per ogni <math>x</math></span>
|align="center"|
|align="center"|*<span><math>D</math> è vera per almeno un <math>n</math></span>
|-
|align="center"|
|align="center"|
|align="center"|
|align="center"|
|-
|align="center"|
|align="center"|<math>\forall n\in\mathbb{N}</math>, <math>\neg D(n)</math>
|align="center"|
|align="center"|<math>\exists x\in Q\mid\neg P(x)</math>
|-
|align="center"|
|align="center"|*<span><math>D</math> è falsa per ogni <math>n</math></span>
|align="center"|
|align="center"|*<span><math>P</math> è falsa per almeno un <math>x</math></span>
|-
|align="center"|
|align="center"|
|align="center"|
|align="center"|
|}
Se chiamiamo <math>R</math> l’insieme degli elementi che verificano la proprietà <math>P</math>, e <math>S</math> quello degli elementi che verificano la proprietà <math>D</math>, i quattro giudizi si possono rappresentare graficamente come nella figura [fig:1.1].
=== La dimostrazione ===
| |||