|
|
Proof Systems: A Study on Form and Complexity
Jalali Keshavarz, Raheleh ; Pudlák, Pavel (vedoucí práce) ; Metcalfe, George (oponent) ; Ramanayake, Revantha (oponent)
Důkazové systémy: forma a složitost Tato disertační práce obsahuje tři části. První dvě části spolu souvisí. V [1] a [2], Iemhoff objevila souvislost mezi existencí terminujícího sekvenčního kalkulu určitého druhu a uniformní interpolační vlastností superintuicioni- stické logiky, kterou tento kalkulus zachycuje. Ve druhé části budeme tento vztah zobecňovat tak, aby pokrýval také substrukturální nastavení na jedné straně a silnější typ systémů nazývaných semi-analytické kalkuly na straně druhé. Abychom byli přesnější, ukážeme, že jakákoli dostatečně silná sub- strukturální logika se semi-analytickým kalkulem má Craigovu interpolační vlastnost a v případě, že je kalkulus terminující, má uniformní interpo- laci. Tento vztah pak vede k některým konkrétním aplikacím. Pozitivním výsledkem je, že poskytuje jednotnou metodu k prokázání uniformní in- terpolační vlastnosti pro logiky FLe, FLew, CFLe, CFLew, IPC, CPC a některá z jejich modálních rozšíření K a KD. Další aplikací je nega- tivní výsledek, že mnohé substrukturální logiky, včetně Ln, Gn, BL, R a RMe , téměř všechny superintuicionistické logiky (kromě nejvýše sedmi z nich) a téměř všechna rozšíření S4 (kromě třiceti sedmi z nich)...
|
host ::
RSS.