Combining Derivations and Refutations for Cut-free Completeness in Bi-intuitionistic Logic
Bi-intuitionistic logic is the union of intuitionistic and dual intuitionistic logic, and was introduced by Rauszer as a Hilbert calculus with algebraic and Kripke semantics. But her subsequent ‘cut-free’ sequent calculus has recently been shown to fail cut-elimination. We present a new cut-free sequent calculus for bi-intuitionistic logic, and prove it sound and complete with respect to its Kripke semantics. Ensuring completeness is complicated by the interaction between intuitionistic implication and dual intuitionistic exclusion, similarly to future and past modalities in tense logic. Our calculus handles this interaction using derivations and refutations as first class citizens. We employ extended sequents which pass information from premises to conclusions using variables instantiated at the leaves of refutations, and rules which compose certain refutations and derivations to form derivations. Automated deduction using terminating backward search is also possible, although this is not our main purpose.
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
References found in this work BETA
No references found.
Citations of this work BETA
No citations found.
Similar books and articles
Cut-Elimination and Proof-Search for Bi-Intuitionistic Logic Using Nested Sequents.Rajeev Gore, Linda Postniece & Alwen Tiu - unknown
Cut-Elimination and a Permutation-Free Sequent Calculus for Intuitionistic Logic.Roy Dyckhoff & Luis Pinto - 1998 - Studia Logica 60 (1):107-118.
A Simple Proof of Completeness and Cut-Elimination for Propositional G¨ Odel Logic.Arnon Avron - unknown
A Free IPC is a Natural Logic: Strong Completeness for Some Intuitionistic Free Logics.Carl J. Posy - 1982 - Topoi 1 (1-2):30-43.
Cut-Free Tableau Calculi for Some Intuitionistic Modal Logics.Mauro Ferrari - 1997 - Studia Logica 59 (3):303-330.
Gentzen's Proof Systems: Byproducts in a Work of Genius.von Plato Jan - 2012 - Bulletin of Symbolic Logic 18 (3):313-367.
Admissibility of Structural Rules for Contraction-Free Systems of Intuitionistic Logic.Roy Dyckhoff & Sara Negri - 2000 - Journal of Symbolic Logic 65 (4):1499-1518.
Intuitionistic Autoepistemic Logic.Giambattista Amati, Luigia Carlucci-Aiello & Fiora Pirri - 1997 - Studia Logica 59 (1):103-120.
Completeness of the Propositions-as-Types Interpretation of Intuitionistic Logic Into Illative Combinatory Logic.Wil Dekkers, Martin Bunder & Henk Barendregt - 1998 - Journal of Symbolic Logic 63 (3):869-890.
Phase Semantics and Petri Net Interpretation for Resource-Sensitive Strong Negation.Norihiro Kamide - 2006 - Journal of Logic, Language and Information 15 (4):371-401.
Added to index2010-09-22
Total downloads9 ( #459,818 of 2,163,976 )
Recent downloads (6 months)1 ( #348,017 of 2,163,976 )
How can I increase my downloads?