✦ LIBER ✦
Simulating non-prenex cuts in quantified propositional calculus
✍ Scribed by Emil Jeřábek; Phuong Nguyen
- Publisher
- John Wiley and Sons
- Year
- 2011
- Tongue
- English
- Weight
- 105 KB
- Volume
- 57
- Category
- Article
- ISSN
- 0044-3050
No coin nor oath required. For personal study only.
✦ Synopsis
MSC (2010) 03F20
We show that the quantified propositional proof systems Gi are polynomially equivalent to their restricted versions that require all cut formulas to be prenex Σ q i or prenex Π q i . Previously this was known only for the treelike systems G * i .