CS Paper Radar

On the Reconstruction of Orthomodular Logic via Restricted Negation

Tomoaki Kawano, Ryo Kashima

cs.LO ·submitted 2026-10-29 18:02 UTC · v1
published

Abstract

Orthomodular logic has long been studied as a fundamental logical framework within quantum logic. In addition to its lattice-theoretic foundations, various formulations have been proposed that incorporate specialized implication connectives and more complex logical connectives. In this study, we reconstruct orthomodular logic by introducing a connective referred to as restricted negation, which has received comparatively little attention in the existing literature. We demonstrate that this connective provides a natural and expressive basis for formulating the core principles of orthomodular logic. Furthermore, as a main result, we construct a new proof system for orthomodular logic founded on this connective.

Comment
In Proceedings NCL'26, arXiv:2610.34489
Journal ref
EPTCS 455, 2026, pp. 47-61
DOI
10.4204/EPTCS.455.5

Closest papers

Nearest neighbours by meaning across the whole index.

A Lambda Calculus Based on Quantum Logic

cs.LO math.LO ·2026-10-25 ·Kenji Tokuo
theory similarity 0.66
Abstract

We propose a typed lambda calculus based on quantum logic. We first present a natural deduction system for quantum logic with the Sasaki hook as its implication operation and then formulate a typed lambda calculus connected to this system through the Curry-Howard correspondence. We prove soundness and completeness of the former with respect to orthomodular lattices and strong normalization of the latter. The resulting lambda calculus has the characteristic feature that only one assumption is available in the typing derivation that serves as the premise of $λ$-abstraction. Under this restriction, ordinary currying is not available in general, but it is still possible to perform $λ$-abstraction by combining multiple assumptions into a single argument of product type and to construct a term corresponding to a deduction using the Sasaki projection.

0.24

Intuitionistic Unitary Linear Logic: A Proof-Theoretical Approach to Purely Quantum Higher-Order

cs.LO ·2026-09-02 ·Julien Lamiroy, Benoît Valiron, Renaud Vilmart
theory similarity 0.64
Abstract · 15 pages, submitted to CSL 2027

Although the circuit model for quantum computation is well established, it is incapable of representing non-causal higher-order quantum processes such as the quantum switch. If several models of non-causal quantum computation have been considered in the literature, the approaches have so far only been focusing on the physicality of such processes, using matrices and other techniques from linear algebra. If these approaches are expressive, they however only provide a static and monolithic understanding of these processes. In this article, we propose a new formalism for non-causal, higher-order quantum processes. Based on a Curry-Howard interpetation, our proposal offers a computational interpretation that is both compositional and modular. In particular, we present Intuitionistic Unitary Linear Logic (IULL), a logic based on linear logic focusing on conservation of unitarity for higher order terms. We prove the coherence of IULLL, its completeness with regard to unitaries, and the admissibility of its cut rules. We finally discuss the validity of our approach by revisiting known non-causal quantum processes with IULL.

0.42

Restricted Peirce's Law and Natural Deduction

cs.LO ·2026-10-29 ·Satoru Niki
publishedtheoryhot direction similarity 0.63
Abstract · In Proceedings NCL'26, arXiv:2610.34489

The constructive logic JP' is known to be the weakest logic between intuitionistic and minimal logic that satisfies Glivenko's theorem. In spite of this natural and desirable formal property, the motivation for its notion of negation remains rather elusive: it can be characterised by a restriction of Peirce's law or by the double negation of ex falso quodlibet, neither of which is very intuitive. In order to have an alternative perspective on this negation, we study in this paper a couple of natural deduction systems for JP'. We first present a system that is normalisable and satisfies a restricted form of the subformula property. Then a modification of this system is introduced, whose rules satisfy the separation of connectives and the full subformula property. Afterwards we turn our attention to a typed lambda-calculus, with respect to which our natural deduction enjoys the Curry-Howard correspondence, followed by a concluding discussion.

0.40

New Proofs of Weak Normalization for Propositional Logic

cs.LO ·2026-09-13 ·S P Suresh
similarity 0.61
Abstract

We present new proofs of weak normalization for intuitionistic and classical propositional logics (with the full set of operators -- falsum, implication, conjunction and disjunction). These proofs work with cuts rather than cut segments, and they provide explicit ``local'' rules for determining whether to contract a whole proof or reduce one of its subproofs, and in the latter case, which subproof to reduce. Interestingly, much of the complication in the case of intuitionistic logic is due to the disjunction elimination rule, while our version of the same rule for classical logic has falsum as conclusion always, and so is much easier to handle. All the complication in the case of classical logic shifts to cuts involving the reductio ad absurdum rule. We also discuss a formalization of the entire proof in Lean, and present a deterministic algorithm for weak normalization.

0.20

Tracking relevance syntactically: A nested approach to weak relevant logic

cs.LO ·2026-11-12 ·Fabio De Martin Polo, Han Gao
theory similarity 0.61
Abstract

The variable-sharing property (VSP) is regarded as a key feature of relevant logics, while the Craig interpolation property (CIP), formulated with respect to relevant implication, implies the VSP in constant-free propositional languages. However, to the best of our knowledge, no constant-free distributive relevant logic has previously been shown to enjoy the CIP. This absence of positive results has contributed to a widespread impression among relevant logicians that relevance and Craig interpolation are incompatible. In this work, we address this tension by proving that the negation-free fragment of base relevant logic B, denoted B+, enjoys both properties. Our proof is purely syntactic and is based on a novel nested sequent calculus featuring binary relevant blocks as primitive structural constructs. Unlike conventional nested sequent calculi, where unary nesting reflects the binary accessibility relation of Kripke semantics, our calculus employs a binary nesting operator that directly reflects the ternary relational structure of Routley-Meyer semantics for relevant logics. After establishing soundness and cut-free completeness of the calculus, we prove several meta-logical properties for the logic. Most notably, we provide the first syntactic proof of the VSP (along with a variety of its stronger variants) and the first proof of the CIP for B+, both derived directly from the cut-free system using a structural notion internalized within nested sequents.

0.27

A generalised and modular proof-theoretic semantics for sequent systems

cs.LO math.LO ·2026-10-16 ·Victor Barroso-Nascimento, Arghya Chakrabarty, Elaine Pimentel
similarity 0.61
Abstract

Base-extension semantics explains logical consequence via derivability in atomic systems. Extending this approach across logics requires careful control of structural principles and contexts. We present a modular sequent-based framework in which support is indexed by multisets of atomic resources and the semantic clauses for connectives are guided by their left introduction rules. The framework separates additive from multiplicative behaviour and makes explicit the contributions of structural rules and restrictions on sequents. We establish soundness and completeness for classical and intuitionistic propositional logic and for multiplicative-additive fragments of classical and intuitionistic linear logic. We then investigate axiomatic extensions of intuitionistic logic through Jankov logic. Two classes of atomic bases yield sound and complete semantics. Completeness is proven using two novel and modular methods using simulation bases, one of which is constructive. These results provide a common semantic treatment of several logical systems while identifying the additional conditions needed to extend the framework beyond structural variations.

0.16

Paraclassical Logics with Two Negations

cs.LO ·2026-10-29 ·Pawel Pawlowski, Pietro Vigiani
publishedhot direction similarity 0.59
Abstract · In Proceedings NCL'26, arXiv:2610.34489

We study three paraclassical propositional logics with two negations, CLoaN, CLouN, and CLauN, obtained by pairwise combining the one-negation systems CLuN, CLaN, and CLoN. CLuN's negation is glut-tolerant and paraconsistent, CLaN's negationis gap-tolerant and paracomplete, and CLoN's negation is both paraconsistent and paracomplete. We provide sound and complete two-valued non-deterministic semantics for each of the two-negations systems. We then focus on CLauN, the system containing the primitive dual pair of CLaN and CLuN negations. In this setting, we show deductive relationships between different negations expressible in CLauN; we show two diferent ways to recapture classical logic by means of translations, locally and globally; and we show a duality results for the multiple conclusion consequence relation of the logic.

0.48

Containment of Conjunctive Queries with Negative Information over Semirings

cs.LO cs.DB ·2026-10-20 ·Guillermo Badia, Carles Noguera, Gaia Petreni, Alice Portone, Val Tannen
similarity 0.59
Abstract

We study the containment problem for (unions of) conjunctive queries ((U)CQs) with negative information on semiring-annotated databases. Our approach to negative information follows the treatment of negation proposed by Grädel and Tannen (2017, 2019, 2021 and 2024) for first-order logic and fixed point logic which applies productively to large classes of semirings, including bounded distributive lattices, as well as the important provenance semirings studied for positive CQ containment by Green (2009). Negation features in (U)CQs along two dimensions: negated equalities (disequations), and negated relational atoms. We study complexity for each of them separately, as well as jointly. For disequations, we extend a methodology that proves the same complexity bounds as the ones already known for the standard Boolean semiring (in the second level of the polynomial hierarchy) for most semirings of interest. Two prominent exceptions are $\mathbb{N}[X]$ and Trio(X) where the complexity bound for containment is in the second level of the counting hierarchy. For CQs with negated relational atoms we show that the complexity, surprisingly, is the same as that of the containment of CQs without negation when one considers model-defining and provenance-tracking interpretations (namely, nondeterministic polynomial time). Interestingly, among bounded distributive lattices, the Boolean two-element case is the only one where the complexity of the problem continues to be hard for the second level of the polynomial hierarchy for model-defining interpretations. Furthermore, we show that the complexity increases again for distributive lattices if we focus on other classes of interpretations. Finally, we consider queries that have both negated equalities and negated relational atoms and show that the complexity of containment continues to be that of the case with just negated equalities.

0.18