# Logica matematica/Calcolo delle proposizioni/Esercizi su algebra delle proposizioni

Logica matematica
Copertina Tutti i moduli · Sviluppo
* InsiemiLogica matematica/Insiemi
* Sistemi formaliLogica matematica/Sistemi formali
* Calcolo delle proposizioniLogica matematica/Calcolo delle proposizioni
** Il sistema di Frege-HilbertLogica matematica/Calcolo delle proposizioni/Sistema di Hilbert
** La deduzione naturaleLogica matematica/Calcolo delle proposizioni/La deduzione naturale
** Il calcolo dei sequenti
** I tableaux semanticiLogica matematica/Calcolo delle proposizioni/I tableaux semantici
** La risoluzioneLogica matematica/Calcolo delle proposizioni/La risoluzione
** Esercizi su tavole di veritàLogica matematica/Calcolo delle proposizioni/Esercizi su tavole di verità
* Calcolo dei predicatiLogica matematica/Calcolo dei predicati
* Teoria dei modelliLogica matematica/Teoria dei modelli
* Computabilità
* IncompletezzaLogica matematica/Incompletezza
** Teoremi di incompletezza di GödelLogica matematica/Incompletezza/Teoremi di incompletezza di Gödel
* Intermezzo: EuclideLogica matematica/Intermezzo Euclide
* Intermezzo: i paradossiLogica matematica/Intermezzo paradossi
* Risorse internetLogica matematica/Risorse internet
Modifica il sommario
In questo primo esempio utilizzeremo le regole di manipolazione algebrica per ridurre la regola di contrapposizione a Vero, dimostrando che si tratta di una tautologia manipolando i simboli e non applicando in modo esaustivo tutte le possibili interpretazioni della variabili atomiche come abbiamo fatto finora con il metodo delle tabelle di verità.
| 1 | $(A\rightarrow B)\rightarrow (\neg B\rightarrow \neg A)$ | espressione della regola di contrapposizione |
| 2 | $\neg (A\rightarrow B)\vee (\neg B\rightarrow \neg A)$ | trasformata l' implicazione centrale in disgiunzione |
| 3 | $\neg (\neg A\vee B)\vee (\neg \neg B\vee \neg A)$ | trasformate le due implicazioni in disgiunzioni |
| 4 | $(\neg \neg A\wedge \neg B)\vee (\neg \neg B\vee \neg A)$ | applicata deMorgan alla prima subformula |
| 5 | $(A\wedge \neg B)\vee B\vee \neg A$ | eliminate le doppie negazioni |
| 6 | $((A\vee B)\wedge (\neg B\vee B))\vee \neg A$ | distribuita la prima disgiunzione |
| 7 | $((A\vee B)\wedge \top )\vee \neg A$ | sostituita la disgiunzione di B e -B con T |
| 8 | $(A\vee B)\vee \neg A$ | eliminata la congiunzione con T |
| 9 | $(A\vee \neg A)\vee B$ | riordinata e associata A con -A |
| 10 | $\top \vee B$ | semplificata la disgiunzione tra A e -A |
| 11 | $\top$ | È una tautologia! |
Questo modo di operare sta anticipando quello che vedremo nella prossime sezioni: come dimostrare che una proposizione è vera o soddisfacibile per via sintattica e non semantica.
L'euristica che ci ha guidato nella trasformazione è stata quella di trasformare la sentenza in una serie di disgiunzioni tra congiunzioni. Questa configurazione prende il nome di forma normale disgiunta.
Forma normale disgiunta: $P=\bigvee _{i=0}^{n}\left(\bigwedge _{j=0}^{m}A_{i,j}\land \bigwedge _{k=0}^{p}(\neg B_{i,k})\right)$
È molto semplice verificare il valore di verità di una sentenza in forma normale disgiunta: la prima disgiunzione vera rende vera tutta la frase, quindi possiamo terminare l'analisi; le congiunzioni sono ugualmente di facile valutazione, devono avere tutte le loro componenti vere e falliscono se contengono una frase e la sua negazione.

## Voci correlate

* Dimostrazione di completezza di insiemi di connettivi