# Through the Looking Glass, and what Horn Clause Programs Found There

arXiv: https://arxiv.org/abs/2407.20413 · HTML: https://mlsanity.com/paper/2407.20413/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 20 references that are in the map.
- First posted on arXiv 29 Jul 2024.

## Builds on (most cited first, 5 of 5)

- [Constraint Answer Set Programming without Grounding](https://mlsanity.com/paper/1804.11162/) (2018)
- [Learning Invariants through Soft Unification](https://mlsanity.com/paper/1909.07328/) (2019)
- [Abductive Reasoning in Intuitionistic Propositional Logic via Theorem Synthesis](https://mlsanity.com/paper/2205.05728/) (2022)
- [Full Automation of Goal-driven LLM Dialog Threads with And-Or Recursors and Refiner Oracles](https://mlsanity.com/paper/2306.14077/) (2023)
- [A Survey of the Proof-Theoretic Foundations of Logic Programming](https://mlsanity.com/paper/2109.01483/) (2021)

## Abstract (arXiv)

Dual Horn clauses mirror key properties of Horn clauses. This paper explores the ``other side of the looking glass'' to reveal some expected and unexpected symmetries and their practical uses. We revisit Dual Horn clauses as enablers of a form of constructive negation that supports goal-driven forward reasoning and is valid both intuitionistically and classically. In particular, we explore the ability to falsify a counterfactual hypothesis in the context of a background theory expressed as a Dual Horn clause program. With Dual Horn clause programs, by contrast to negation as failure, the variable bindings in their computed answers provide explanations for the reasons why a statement is successfully falsified. Moreover, in the propositional case, by contrast to negation as failure as implemented with stable models semantics in ASP systems, and similarly to Horn clause programs, Dual Horn clause programs have polynomial complexity. After specifying their execution model with a metainterpreter, we devise a compilation scheme from Dual Horn clause programs to Horn clause programs, ensuring their execution with no performance penalty and we design the embedded SymLP language to support combined Horn clause and Dual Horn clause programs. As a (motivating) application, we cast LLM reasoning chains into propositional Horn and Dual Horn clauses that work together to constructively prove and disprove goals and enhance Generative AI with explainability of reasoning chains.