Dovadă condiționată - Conditional proof
O dovadă condițională este o dovadă care ia forma afirmării unui condițional și care demonstrează că antecedentul condiționalului conduce în mod necesar la consecința .
Prezentare generală
Antecedentul presupus al unei dovezi condiționale se numește presupunerea dovezii condiționate ( CPA ). Astfel, scopul unei dovezi condiționate este de a demonstra că dacă CPA ar fi adevărat, atunci urmează în mod necesar concluzia dorită . Valabilitatea unei dovezi condiționate nu impune ca CPA să fie adevărat, doar că, dacă ar fi adevărată , ar duce la consecința.
Dovezile condiționate au o mare importanță în matematică . Există dovezi condiționale care leagă mai multe conjecturi altfel nedovedite , astfel încât o dovadă a unei conjecturi poate implica imediat validitatea altor câteva. Poate fi mult mai ușor să arăți adevărul unei propuneri de urmat dintr-o altă propunere decât să îl demonstrezi independent.
O renumită rețea de dovezi condiționale este clasa teoriei complexității NP-completă . Există un număr mare de sarcini interesante (a se vedea Lista problemelor NP-complete ) și, deși nu se știe dacă există o soluție de timp polinomial pentru oricare dintre ele, se știe că dacă o astfel de soluție există pentru unele dintre ele, unul există pentru toți. În mod similar, ipoteza Riemann are multe consecințe deja dovedite.
Logica simbolică
Ca exemplu de dovadă condițională în logica simbolică , să presupunem că vrem să dovedim A → C (dacă A, atunci C) din primele două premise de mai jos:
| 1. | A → B | („Dacă A, atunci B”) |
| 2. | B → C | („Dacă B, atunci C”) |
|
|
||
| 3. | A | (presupunerea dovezilor condiționate, „Să presupunem că A este adevărat”) |
| 4. | B | (urmează din liniile 1 și 3, modus ponens ; "Dacă A atunci B; A, deci B") |
| 5. | C | (urmează din liniile 2 și 4, modus ponens ; „Dacă B atunci C; B, deci C”) |
| 6. | A → C | (urmează de la rândurile 3-5, dovadă condiționată; „Dacă A, atunci C”) |
Vezi si
Referințe
- Robert L. Causey, Logic, seturi și recursivitate , Jones și Barlett, 2006.
- Dov M. Gabbay, Franz Guenthner (eds.), Manual de logică filosofică , volumul 8, Springer, 2002.