Věta o dedukci - Deduction theorem
![]() | tento článek potřebuje pozornost odborníka na matematiku.Srpna 2016) ( |
v matematická logika, a teorém o dedukci je metateorem to ospravedlňuje dělat podmíněné důkazy - dokázat implikaci A → B, předpokládejme A jako hypotéza a poté přistoupit k odvození B - v systémech, které nemají explicitní pravidlo odvození pro tohle. Věty o dedukci existují pro oba výroková logika a logika prvního řádu.[1] Věta o dedukci je důležitým nástrojem v Hilbertovy dedukční systémy protože to umožňuje psát srozumitelnější a obvykle mnohem kratší důkazy, než by bylo možné bez něj. V některých jiných formálních důkazních systémech je stejná výhoda poskytována výslovným odvozovacím pravidlem; například přirozený odpočet volá to implikace úvod.
Podrobněji věta o výroku o logické dedukci uvádí, že pokud je to vzorec je odvoditelný ze souboru předpokladů pak implikace je odvoditelný z ; v symbolech, naznačuje . Ve zvláštním případě, kdy je prázdná sada, tvrzení o dedukční větě lze kompaktněji zapsat jako: naznačuje . Věta o dedukci pro predikátovou logiku je podobná, ale přichází s některými dalšími omezeními (které by byly například splněny, pokud je uzavřený vzorec ). Obecně dedukční věta musí brát v úvahu všechny logické detaily uvažované teorie, takže každý logický systém technicky potřebuje svou vlastní dedukční teorém, i když rozdíly jsou obvykle malé.
Věta o dedukci platí pro všechny teorie prvního řádu s obvyklými[vágní ] deduktivní systémy pro logiku prvního řádu.[2] Existují však systémy prvního řádu, ve kterých jsou přidána nová pravidla odvození, u nichž selže věta o dedukci.[3] Nejpozoruhodnější je, že věta o dedukci v Birkhoff-von Neumannovi neplatí kvantová logika, protože lineární podprostory a Hilbertův prostor tvoří a nedistribuční mříž.
Příklady odpočtu
- „Prokázat“ axiom 1:
- P 1. hypotéza
- Q 2. hypotéza
- P 3. opakování 1
- Q→P 4. odpočet od 2 do 3
- P→(Q→P) 5. odpočet od 1 do 4 QED
- „Dokázat“ axiom 2:
- P→(Q→R) 1. hypotéza
- P→Q 2. hypotéza
- P 3. hypotéza
- Q 4. modus ponens 3,2
- Q→R 5. modus ponens 3,1
- R 6. modus ponens 4,5
- P→R 7. odpočet od 3 do 6
- P→Q 2. hypotéza
- (P→Q)→(P→R) 8. odpočet od 2 do 7
- P→(Q→R) 1. hypotéza
- (P→(Q→R))→((P→Q)→(P→R)) 9. odpočet od 1 do 8 QED
- Použití axiomu 1 k zobrazení ((P→(Q→P))→R)→R:
- (P→(Q→P))→R 1. hypotéza
- P→(Q→P) 2. axiom 1
- R 3. modus ponens 2,1
- ((P→(Q→P))→R)→R 4. odpočet od 1 do 3 QED
Virtuální pravidla odvození
Z příkladů můžete vidět, že jsme přidali tři virtuální (nebo extra a dočasná) pravidla odvození do naší normální axiomatické logiky. Jedná se o „hypotézu“, „opakování“ a „dedukci“. Běžná pravidla odvození (tj. „Modus ponens“ a různé axiomy) zůstávají k dispozici.
1. Hypotéza je krok, při kterém se přidá další předpoklad k těm, které jsou již k dispozici. Takže pokud váš předchozí krok S bylo odvozeno jako:
pak jeden přidá další premisu H a dostane:
To je symbolizováno přesunem z n-té úrovně odsazení na n + 1-tu úroveň a vyslovením
- S předchozí krok
- H hypotéza
- S předchozí krok
2. Opakování je krok, při kterém se znovu použije předchozí krok. V praxi je to nutné pouze tehdy, když chceme vytvořit hypotézu, která není nejnovější hypotézou, a použít ji jako poslední krok před krokem dedukce.
3. Dedukce je krok, při kterém se odstraní nejnovější hypotéza (stále dostupná) a předpona předchozího kroku. To se projeví uvolněním jedné úrovně následujícím způsobem:
- H hypotéza
- ......... (další kroky)
- C (závěr vyvozen z H)
- H→C dedukce
Konverze z důkazu pomocí meta-věty o dedukci na axiomatický důkaz
V axiomatických verzích výrokové logiky se obvykle nachází mezi schémata axiomu (kde P, Q, a R jsou nahrazeny jakýmkoli návrhem):
- Axiom 1 je: P→(Q→P)
- Axiom 2 je: (P→(Q→R))→((P→Q)→(P→R))
- Modus ponens je: od P a P→Q usoudit Q
Tato schémata axiomu jsou vybrána tak, aby z nich bylo možné snadno odvodit teorém o dedukci. Mohlo by se tedy zdát, že si klademe otázku. Lze je však ospravedlnit kontrolou toho, zda jsou tautologie pomocí pravdivostních tabulek a že modus ponens zachovává pravdu.
Z těchto schémat axiomu lze rychle odvodit schéma věty P→P (reflexivita implikace), která se používá níže:
- (P→((Q→P)→P))→((P→(Q→P))→(P→P)) ze schématu axiomu 2 s P, (Q→P), P
- P→((Q→P)→P) ze schématu axiomu 1 s P, (Q→P)
- (P→(Q→P))→(P→P) od modus ponens aplikovaných na krok 2 a krok 1
- P→(Q→P) ze schématu axiomu 1 s P, Q
- P→P z modus ponens aplikovaných na krok 4 a krok 3
Předpokládejme, že to máme Γ a H dokázat C, a my bychom chtěli ukázat, že es to dokazuje H→C. Pro každý krok S v dedukci, která je premisou v Γ (krok opakování) nebo axiomem, můžeme na axiom 1 použít modus ponens, S→(H→S), dostat H→S. Pokud je krok H sám (krok hypotézy), použijeme schéma věty, abychom dostali H→H. Pokud je krok výsledkem aplikace modus ponens na A a A→S, nejprve se ujistíme, že byly převedeny na H→A a H→(A→S) a pak vezmeme axiom 2, (H→(A→S))→((H→A)→(H→S)), a použít modus ponens získat (H→A)→(H→S) a pak znovu získat H→S. Na konci důkazu budeme mít H→C podle potřeby, až na to, že nyní záleží jen na Γ, ne na H. Krok dedukce tedy zmizí konsolidovaný do předchozího kroku, z něhož byl odvozen závěr H.
Aby se minimalizovala složitost výsledného důkazu, je třeba před převodem provést nějaké předběžné zpracování. Jakékoli kroky (jiné než závěr), na kterých ve skutečnosti nezávisí H by měl být posunut nahoru před krokem hypotézy a uvolnit jednu úroveň. A všechny další zbytečné kroky (které se nepoužívají k získání závěru nebo je lze obejít), jako jsou opakování, která nejsou závěrem, by měly být odstraněny.
Během převodu může být užitečné umístit všechny aplikace modus ponens do axiomu 1 na začátku dedukce (hned po H→H krok).
Při převodu modus ponens, pokud A je mimo rozsah H, pak bude nutné použít axiom 1, A→(H→A), a modus ponens dostat H→A. Podobně, pokud A→S je mimo rozsah H, použít axiom 1, (A→S)→(H→(A→S)), a modus ponens dostat H→(A→S). Nemělo by být nutné dělat obojí, pokud krok modus ponens není závěrem, protože pokud jsou oba mimo rozsah, pak by modus ponens měl být dříve přesunut nahoru H a být tedy mimo rozsah také.
Pod Curry – Howardova korespondence, výše uvedený proces převodu pro odpočet meta-věta je analogický s proces převodu z lambda kalkul podmínky k podmínkám kombinační logika, kde axiom 1 odpovídá K kombinátoru a axiom 2 odpovídá S kombinátoru. Všimněte si, že I kombinátor odpovídá schématu věty P→P.
Užitečné věty
Pokud máte v úmyslu převést složitý důkaz pomocí věty o dedukci na přímý důkaz bez věty o dedukci, pak by bylo pravděpodobně užitečné tyto věty na začátku jednou provždy dokázat a poté je použít jako pomoc při převodu :
pomáhá převést kroky hypotézy.
pomáhá převádět modus ponens, když hlavní předpoklad nezávisí na hypotéze, nahrazuje axiom 2 a vyhýbá se použití axiomu 1.
pomáhá převádět modus ponens, když vedlejší předpoklad nezávisí na hypotéze, nahrazuje axiom 2 a vyhýbá se použití axiomu 1.
Tyto dvě věty lze společně použít namísto axiomu 2, ačkoli převedený důkaz by byl komplikovanější:
Peirceův zákon není důsledkem věty o dedukci, ale lze ji použít s teorémem o dedukci k prokázání věcí, které by člověk jinak nedokázal dokázat.
Lze jej také použít k získání druhé ze dvou vět, které lze použít namísto axiomu 2.
Důkaz o teorému o dedukci
Dokazujeme teorém o dedukci V Hilbertově deduktivním systému výrokového počtu.[4]
Nechat být soubor vzorců a a vzorce, takové, že . Chceme to dokázat .
Od té doby , existuje důkaz o z . Větu dokazujeme indukcí délky důkazu n; indukční hypotéza je tedy pro kteroukoli , a tak, že existuje důkaz o z délky až n, drží.
Li n = 1 tedy je členem sady vzorců . Tedy buď , v jakém případě je prostě který je derivovatelný substitucí z p → p, který je derivovatelný z axiomů, tedy také ; nebo je v , v jakém případě ; vyplývá z axiomu p → (q → p) se substitucí a tedy modus ponens, že .
Nyní předpokládejme indukční hypotézu pro důkazy o délce až na nechte být vzorec prokazatelný z s dokladem o délce n+1. Pak existují tři možnosti:
- je členem sady vzorců ; v tomto případě postupujeme jako pro n=0.
- je dosažen substitucí ve vzorci φ. Pak φ je prokázáno z maximálně n kroky, tedy indukční hypotézou , kde můžeme psát A a φ s různými proměnnými. Ale pak můžeme přijet z na stejnou substitucí, která se používá k odvození od φ; tím pádem .
- je dosažen pomocí modus ponens. Pak existuje vzorec C takhle dokazuje a , a modus ponens se poté použije k prokázání . Důkazy o a jsou maximálně n kroky a podle indukční hypotézy, kterou máme a . Z axiomu (p → (q → r)) → ((p → q) → (p → r)) se substitucí vyplývá, že a dvakrát používáme modus ponens .
Věta tedy platí ve všech případech také pro n+1 a indukcí je prokázána věta o dedukci.
Věta o dedukci v predikátové logice
Věta o dedukci platí také v logika prvního řádu v následující podobě:
Tady symbol znamená „je syntaktickým důsledkem.“ Níže naznačíme, jak se důkaz této věty o dedukci liší od důkazu věty o dedukci v propozičním počtu.
V nejběžnějších verzích pojmu formální důkaz existují kromě schémat axiomu výrokového počtu (nebo pochopení, že všechny tautologie výrokového počtu jsou považovány za schémata axiomu sama o sobě), kvantifikovatelné axiomy, a navíc k modus ponens, jeden další pravidlo závěru, známý jako pravidlo zobecnění: "Z K., odvodit ∀vK."
Aby bylo možné převést důkaz o G z T∪{F} jednomu z F→G z T, jeden se zabývá kroky důkazu G které jsou axiomy nebo jsou výsledkem aplikace modus ponens stejným způsobem jako u důkazů ve výrokové logice. Kroky, které vyplývají z použití pravidla generalizace, jsou řešeny prostřednictvím následujícího axiomu kvantifikátoru (platí vždy, když je proměnnáproti není ve vzorci zdarma H):
- (∀proti(H→K.))→(H→∀vK).
Protože v našem případě F se předpokládá, že je uzavřen, můžeme vzít H být F. Tento axiom umožňuje každému odvodit F→∀vK z F→K. a zobecnění, což je právě to, co je potřeba, když se na některé použije pravidlo zobecnění K. v dokladu o G.
V logice prvního řádu může být omezení tohoto F jako uzavřeného vzorce uvolněno vzhledem k tomu, že volné proměnné v F se při odpočtu G od nemění . V případě, že se volná proměnná v ve F změnila v dedukci, napíšeme (horní index v turnstyle naznačující, že v bylo měněno) a odpovídající forma věty o dedukci je .[5]
Příklad převodu
Abychom ilustrovali, jak lze převést přirozenou dedukci na axiomatickou formu důkazu, aplikujeme ji na tautologii Q→((Q→R)→R). V praxi obvykle stačí vědět, že bychom to mohli udělat. Normálně používáme přirozeně deduktivní formu místo mnohem delšího axiomatického důkazu.
Nejprve napíšeme důkaz pomocí metody podobné přirozenému odpočtu:
- Q 1. hypotéza
- Q→R 2. hypotéza
- R 3. modus ponens 1,2
- (Q→R)→R 4. odpočet od 2 do 3
- Q 1. hypotéza
- Q→((Q→R)→R) 5. odpočet od 1 do 4 QED
Zadruhé převedeme vnitřní dedukci na axiomatický důkaz:
- (Q→R)→(Q→R) 1. schéma věty (A→A)
- ((Q→R)→(Q→R))→(((Q→R)→Q)→((Q→R)→R)) 2. axiom 2
- ((Q→R)→Q)→((Q→R)→R) 3. modus ponens 1,2
- Q→((Q→R)→Q) 4. axiom 1
- Q 5. hypotéza
- (Q→R)→Q 6. modus ponens 5,4
- (Q→R)→R 7. modus ponens 6,3
- Q→((Q→R)→R) 8. odpočet od 5 do 7 QED
Za třetí převádíme vnější dedukci na axiomatický důkaz:
- (Q→R)→(Q→R) 1. schéma věty (A→A)
- ((Q→R)→(Q→R))→(((Q→R)→Q)→((Q→R)→R)) 2. axiom 2
- ((Q→R)→Q)→((Q→R)→R) 3. modus ponens 1,2
- Q→((Q→R)→Q) 4. axiom 1
- [((Q→R)→Q)→((Q→R)→R)]→[Q→(((Q→R)→Q)→((Q→R)→R))] 5. axiom 1
- Q→(((Q→R)→Q)→((Q→R)→R)) 6. modus ponens 3,5
- [Q→(((Q→R)→Q)→((Q→R)→R))]→([Q→((Q→R)→Q)]→[Q→((Q→R)→R))]) 7. axiom 2
- [Q→((Q→R)→Q)]→[Q→((Q→R)→R))] 8. modus ponens 6,7
- Q→((Q→R)→R)) 9. modus ponens 4,8 QED
Tyto tři kroky lze stručně určit pomocí Curry – Howardova korespondence:
- za prvé, v lambda kalkulu funkce f = λa. λb. b a má typ q → (q → r) → r
- zadruhé eliminace lambda na b, f = λa. s i (k a)
- za třetí, eliminací lambda na a, f = s (k (s i)) k
Viz také
Poznámky
- ^ Kleene 1967, str. 39, 112; Shoenfield 1967, str. 33
- ^ Výslovné ověření tohoto výsledku lze nalézt v https://github.com/georgydunaev/VerifiedMathFoundations/blob/master/SHEN.v
- ^ Kohlenbach 2008, s. 148
- ^ Věta o dedukci, od Curtise Frankse z University of Notre Dame, vyvoláno 2020-07-21
- ^ Kleene, Stephen (1980). Úvod do meta-matematiky. Severní Holandsko. 102–106. ISBN 9780720421033.
Reference
- Carl Hewitt (2008), „ORGs for Scalable, Robust, Privacy-Friendly Client Cloud Computing“, IEEE Internet Computing, 12 (5): 96–99, doi:10.1109 / MIC.2008.107. Září / říjen 2008
- Kohlenbach, Ulrich (2008), Aplikovaná teorie důkazů: interpretace důkazů a jejich použití v matematiceSpringer Monografie z matematiky, Berlín, New York: Springer-Verlag, ISBN 978-3-540-77532-4, PAN 2445721
- Kleene, Stephen Cole (2002) [1967], Matematická logika, New York: Dover Publications, ISBN 978-0-486-42533-7, PAN 1950307
- Rautenberg, Wolfgang (2010), Stručný úvod do matematické logiky (3. vyd.), New York: Springer Science + Business Media, doi:10.1007/978-1-4419-1221-3, ISBN 978-1-4419-1220-6.
- Shoenfield, Joseph R. (2001) [1967], Matematická logika (2. vyd.), K Peters, ISBN 978-1-56881-135-2
externí odkazy
- Úvod do matematické logiky Vilnis Detlovs a Karlis Podnieks Podnieks je komplexní výukový program. Viz část 1.5.
- "Věta o dedukci"