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

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