Villkorligt bevis
Ett villkorligt bevis är ett bevis som tar formen av att hävda ett villkorligt , och bevisa att antecedenten till det villkorliga nödvändigtvis leder till det följande .
Översikt
Den antagna föregångaren till ett villkorligt bevis kallas antagandet om villkorat bevis ( CPA ). Målet med ett villkorligt bevis är alltså att visa att om CPA var sann, så följer nödvändigtvis den önskade slutsatsen . Giltigheten av ett villkorligt bevis kräver inte att CPA är sant, bara att om det vore sant skulle det leda till följden.
Villkorsbevis är av stor betydelse i matematik . Det finns villkorliga bevis som kopplar samman flera annars obevisade gissningar , så att ett bevis för en gissning omedelbart kan antyda giltigheten av flera andra. Det kan vara mycket lättare att visa en propositions sanning att följa från en annan proposition än att bevisa den självständigt.
Ett känt nätverk av villkorliga bevis är den NP-kompletta klassen av komplexitetsteori. Det finns ett stort antal intressanta uppgifter (se Lista över NP-fullständiga problem ), och även om det inte är känt om det finns en polynom-tidslösning för någon av dem, är det känt att om en sådan lösning finns för några av dem, en finns för dem alla. På samma sätt Riemann-hypotesen många konsekvenser som redan har bevisats.
Symbolisk logik
Som ett exempel på ett villkorligt bevis i symbolisk logik , anta att vi vill bevisa A → C (om A, då C) från de två första premisserna nedan:
| 1. | A → B | ("Om A, då B") |
| 2. | B → C | ("Om B, då C") |
|
|
||
| 3. | A | (villkorligt bevis antagande, "Anta att A är sant") |
| 4. | B | (följer av raderna 1 och 3, modus ponens ; "Om A då B; A, därför B") |
| 5. | C | (följer av raderna 2 och 4, modus ponens ; "Om B då C; B, alltså C") |
| 6. | A → C | (följer av raderna 3–5, villkorligt bevis; "Om A, då C") |
Se även
- Robert L. Causey, Logic, sets, and recursion , Jones och Barlett, 2006.
- Dov M. Gabbay, Franz Guenthner (red.), Handbook of philosophical logic , Volym 8, Springer, 2002.