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

Template:Logica matematica 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\to B)\to (\mathrm{\neg }B\to \mathrm{\neg }A)$	espressione della regola di contrapposizione
2	$\mathrm{\neg }(A\to B)\vee (\mathrm{\neg }B\to \mathrm{\neg }A)$	trasformata l' implicazione centrale in disgiunzione
3	$\mathrm{\neg }(\mathrm{\neg }A\vee B)\vee (\mathrm{\neg }\mathrm{\neg }B\vee \mathrm{\neg }A)$	trasformate le due implicazioni in disgiunzioni
4	$(\mathrm{\neg }\mathrm{\neg }A\wedge \mathrm{\neg }B)\vee (\mathrm{\neg }\mathrm{\neg }B\vee \mathrm{\neg }A)$	applicata deMorgan alla prima subformula
5	$(A\wedge \mathrm{\neg }B)\vee B\vee \mathrm{\neg }A$	eliminate le doppie negazioni
6	$((A\vee B)\wedge (\mathrm{\neg }B\vee B))\vee \mathrm{\neg }A$	distribuita la prima disgiunzione
7	$((A\vee B)\wedge \mathrm{\top })\vee \mathrm{\neg }A$	sostituita la disgiunzione di B e -B con T
8	$(A\vee B)\vee \mathrm{\neg }A$	eliminata la congiunzione con T
9	$(A\vee \mathrm{\neg }A)\vee B$	riordinata e associata A con -A
10	$\mathrm{\top }\vee B$	semplificata la disgiunzione tra A e -A
11	$\mathrm{\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=\underset{i=0}{\overset{n}{\bigvee }}(\underset{j=0}{\overset{m}{\bigwedge }}{A}_{i,j}\wedge \underset{k=0}{\overset{p}{\bigwedge }}(\mathrm{\neg }{B}_{i,k}))$

È 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