Harropův vzorec - Harrop formula
v intuicionistická logika, Harropovy vzorce, pojmenoval podle Ronald Harrop, jsou třídou vzorců indukčně definované jak následuje:[1][2][3]
- Atomové vzorce jsou Harrop, včetně falešnosti (⊥);
- je poskytována Harrop a jsou;
- je Harrop pro jakýkoli dobře formulovaný vzorec ;
- je poskytována Harrop Je a je jakýkoli dobře formulovaný vzorec;
- je poskytována Harrop je.
Vyloučením disjunkce a existenční kvantifikace (s výjimkou předchůdce implikace), nekonstruktivní vyhneme se predikátům, což má výhody pro počítačovou implementaci Z konstruktivistického hlediska jsou Harropovy vzorce „dobře vychované“. Například v Heyting aritmetic „Harropovy vzorce uspokojují klasickou ekvivalenci, kterou obvykle konstruktivní logika nesplňuje:[1]
Harropovy vzorce byly představeny kolem roku 1956 Ronaldem Harropem a nezávisle na nich Helena Rasiowa.[2] Variace základního konceptu se používají v různých odvětvích konstruktivní matematika a logické programování.
Dědičné Harropovy vzorce a logické programování
Složitější definice dědičných Harropových vzorců se používá v logické programování jako zobecnění Horn klauzule a tvoří základ jazyka λProlog. Dědičné Harropovy vzorce jsou definovány pomocí dvou (někdy tří) rekurzivních sad vzorců. V jedné formulaci:[4]
- Tuhé atomové vzorce, tj. Konstanty nebo vzorce , jsou dědičné Harrop;
- je poskytována dědičná Harrop a jsou;
- je poskytována dědičná Harrop je;
- je poskytována dědičná Harrop je přísně atomová a je G-vzorec.
G-formulae jsou definovány takto:[4]
- Atomové vzorce jsou G-formulae, včetně pravdy (⊤);
- je G-formule k dispozici a jsou;
- je G-formule k dispozici a jsou;
- je G-formule k dispozici je;
- je G-formule k dispozici je;
- je G-formule k dispozici Je a je dědičná Harrop.
Viz také
Reference
- ^ A b Dummett, Michael (2000). Prvky intuicionismu (2. vyd.). Oxford University Press. p. 227. ISBN 0-19-850524-8.
- ^ A b A. S. Troelstra, H. Schwichtenberg. Základní teorie důkazu. Cambridge University Press. ISBN 0-521-77911-1.CS1 maint: používá parametr autoři (odkaz)
- ^ Ronald Harrop (1956). „O disjunkacích a existenciálních tvrzeních v intuitivních logických systémech“. Mathematische Annalen. 132 (4): 347. doi:10.1007 / BF01360048.
- ^ A b Dov M. Gabbay, Christopher John Hogger, John Alan Robinson, Příručka logiky v umělé inteligenci a logickém programování: Logické programování, Oxford University Press, 1998, s. 575, ISBN 0-19-853792-1