TY - JOUR
T1 - Cut-elimination and deductive polarization in complementary classical logic
AU - Carnielli, Walter A.
AU - Pulcini, Gabriele
N1 - sem pdf conforme despacho.
FCT - PTDC/MHC-FIL/2583/2014
PY - 2017/1/1
Y1 - 2017/1/1
N2 - In this article, we consider LK, a cut-free sequent calculus able to faithfully characterize classical (propositional) nontheorems, in the sense that a formula φ is provable in LK if, and only if, φ is not provable in LK, i.e., φ is not a classical tautology. The LK calculus is here enriched with two admissible (unary) cut rules, which allow for a simple and efficient cut-elimination algorithm. We observe two facts: (i) complementary cut-elimination always returns the simplest proof for a given provable sequent, and (ii) provable complementary sequents turn out to be deductively polarized by the empty sequent.
AB - In this article, we consider LK, a cut-free sequent calculus able to faithfully characterize classical (propositional) nontheorems, in the sense that a formula φ is provable in LK if, and only if, φ is not provable in LK, i.e., φ is not a classical tautology. The LK calculus is here enriched with two admissible (unary) cut rules, which allow for a simple and efficient cut-elimination algorithm. We observe two facts: (i) complementary cut-elimination always returns the simplest proof for a given provable sequent, and (ii) provable complementary sequents turn out to be deductively polarized by the empty sequent.
KW - Complementary classical logic
KW - Cut-elimination theorem
KW - Refutation calculi
UR - http://www.scopus.com/inward/record.url?scp=85027404437&partnerID=8YFLogxK
U2 - 10.1093/jigpal/jzx006
DO - 10.1093/jigpal/jzx006
M3 - Article
AN - SCOPUS:85027404437
SN - 1367-0751
VL - 25
SP - 273
EP - 282
JO - Logic Journal of the IGPL
JF - Logic Journal of the IGPL
IS - 3
ER -