Parte III
Dimostrazioni, sintassi e semantica in LP
âHa preso un poâ di tavole di veritĂ , ha messo insieme qualche teorema e senza neanche accorgermene mi sono convinta a comprare la vernice a prova di ruggine.â
In questa parteâŚ
Le dimostrazioni sono il cuore della logica. Per qualche studente, forse, sono invece sinonimo di infarto. Ma non abbiate paura, le dimostrazioni non sono cosĂŹ difficili, basta sapere da dove prenderle.
In questa parte imparerete a dominare le dimostrazioni in LP. Il Capitolo 9 mostra come è fatta una dimostrazione e come costruirne una. Scoprirete anche le prime otto regole di inferenza, che costituiscono lâinsieme delle regole delle implicazioni. Nel Capitolo 10 analizzo le altre dieci regole di inferenza, lâinsieme delle regole di equivalenza. I Capitoli 9 e 10 si concentrano sui metodi diretti di dimostrazione, mentre nel Capitolo 11 introduco altri due metodi: le dimostrazioni condizionali e quelle indirette. Nel Capitolo 12 mostro come e quando usare questi strumenti e analizzo le strategie di dimostrazione.
Avrete anche il quadro generale di LP: nel Capitolo 13 vedremo che i cinque connettivi sono sufficienti per produrre qualsiasi funzione logica in LP. Nel Capitolo 14 analizzeremo vari argomenti relativi alla sintassi e alla semantica di LP. LÏ vedremo anche come stabilire se una successione di simboli in LP è una formula ben formata. Infine, chiuderemo con un assaggio di algebra booleana.
Capitolo 9
Che cosâavete da dimostrare?
In questo capitolo
Introduzione alle dimostrazioni formali
Costruire dimostrazioni con le regole di inferenza
Forse avete giĂ qualche esperienza di dimostrazioni, quei problemi che erano parte importante della geometria della scuola superiore. Nelle dimostrazioni geometriche, si parte da un insieme di assiomi semplici (detti anche postulati), come âTutti gli angoli retti sono ugualiâ e si costruiscono proposizioni piĂš complesse, i teoremi.
Anche la programmazione informatica, in cui si usano enunciati semplici per creare software complessi, ricorda il metodo della dimostrazione. Lâidea della complessitĂ che si sviluppa a partire dalle cose semplici è comune anche alle dimostrazioni della logica proposizionale (LP).
In un certo senso, costruire una dimostrazione è come gettare un ponte da una riva allâaltra di un fiume. Il punto di partenza è lâinsieme delle premesse date, il punto dâarrivo la conclusione che si vuole raggiungere. E i pezzi che si usano per costruire il ponte sono le regole di inferenza, un insieme di 18 modi per trasformare proposizioni in altre proposizioni.
In questo capitolo, vedremo le prime otto regole di inferenza, lâinsieme delle regole di implicazione. Lungo la strada, scoprirete un poâ come sono fatte le dimostrazioni.
Anche se queste regole sono chiare e prive di ambiguitĂ , non sempre è ovvio come usarle in casi particolari. Câè unâarte della dimostrazione che può rendere il processo interessante e soddisfacente, se la si padroneggia, ma può essere invece frustrante in caso contrario. La buona notizia è che esistono molti ottimi trucchi e, conoscendoli, si hanno a disposizione diverse munizioni da usare quando il gioco si fa duro.
Tra premesse e...