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...