Dimostrazione condizionale
Una dimostrazione condizionale è una prova che assume come ipotesi l'antecedente di un condizionale per dimostrarne la validità. Perché l'ipotesi non sia arbitraria, la sua assunzione deve essere rilasciata durante la dimostrazione in modo tale da arrivare ala conclusione con il solo insieme di ipotesi inizialmente dato.
L'antecedente di una prova condizionale che si assume per ipotesi come vero, è chiamato assunzione di prova condizionale (CPA). L'obiettivo di una prova condizionale è dimostrare che se il CPA è vero, ne consegue necessariamente la conclusione desiderata. La validità di una prova condizionale non richiede che il CPA sia vero, ma solo che se è vero, è vero anche il conseguente. La verità dell'assunzione viene rilasciata e quindi rimossa come ipotesi prima o in corrispondenza della conclusione della dimostrazione.
Le dimostrazioni condizionali sono di grande importanza in matematica. Esistono prove condizionali all'interno di diverse congetture che non potrebbero essere altrimenti, in modo che una dimostrazione di una congettura possa implicare immediatamente la validità di molte altre. Può essere molto più facile mostrare la verità di una proposizione a seguito della dimostrazione della verità di un'altra proposizione (mediante modus ponens) piuttosto che dimostrarla in modo indipendente.
Una famosa rete di prove condizionali è la classe NP-completa della teoria della complessità. Esiste un numero elevato di problemi NP-completi di cui non è noto per nessuno se esista una soluzione calcolabile in un tempo di calcolo polinomiale; tuttavia, è noto che se tale soluzione esiste per almeno uno di essi, essa esiste per tutti loro. In modo analogo, sono già state provate numerose conseguenze dell'ipotesi di Riemann.
Esempio[modifica | modifica wikitesto]
Si consideri la seguente dimostrazione di logica matematica. Si supponga di voler dimostrare che A → C (se A è, allora è C) dalle seguenti due premesse:
| 1. | A → B | ("Se A è, allora è B") |
| 2. | B → C | ("Se B è, allora è C") |
| 3. | A | (assunzione della prova condizionale, "Si supponga che A sia vera") |
| 4. | B | (segue dalle linee (1) e (3) per modus ponens; "Se A è, allora è B; ma A è, dunque è B") |
| 5. | C | (segue dale linee (2) e (4) per modus ponens; "Se B è, allora è C; ma B è, dunque è C") |
| 6. | A → C | (segue dalle linee (3) e (5) per prova condizionale; "Se A è, allora è C") |
L'assunzione di A come vera per ipotesi nella linea (3) viene rilasciata ed eliminata in corrispondenza della linea (6), mediante la proposizione "Se A è, allora è C"; "C" è vero dalla (5) e non è assunto come ipotesi. Per ogni assunzione di una prova condizionale, deve poi esserci una prova condizionale che la elimina dall'insieme delle ipotesi.
Nella logica filosofica, è sistematico assumere come vero per ipotesi l'antecedente del primo di una catena di condizionali (ad esempio se si ha nell'ipotesi della dimostrazione e , e poi anche e , per costruzione è necessario assumere A e D vere come ipotesi; entrambe le ipotesi A e D dovranno poi essere rilasciate ed eliminate nel corso dei passaggi successivi della dimostrazione in modo tale da concludere con le sole ipotesi date inizialmente).
Bibliografia[modifica | modifica wikitesto]
- Robert L. Causey, Logic, sets, and recursion, Jones and Barlett, 2006.
- Dov M. Gabbay, Franz Guenthner (eds.), Handbook of philosophical logic, Volume 8, Springer, 2002.
