### Abstract

We formalize a range of proof systems for classical propositional logic (sequent calculus, natural deduction, Hilbert systems, resolution) and prove the most important meta-theoretic results about semantics and proofs: compactness, soundness, completeness, translations between proof systems, cut-elimination, interpolation and model existence.

### License

BSD License

### Topics

- Logic/Proof theory

### Related publications

- Michaelis, J., & Nipkow, T. (2019). Formalized Proof Systems for Propositional Logic (Version 1.0). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.TYPES.2017.5

### Session Propositional_Proof_Systems

- Formulas
- Sema
- Substitution
- Substitution_Sema
- CNF
- CNF_Formulas
- CNF_Sema
- CNF_Formulas_Sema
- CNF_To_Formula
- Tseytin
- Tseytin_Sema
- MiniFormulas
- MiniFormulas_Sema
- Consistency
- Compactness
- Compactness_Consistency
- Sema_Craig
- SC
- SC_Cut
- SC_Depth
- SC_Gentzen
- SC_Sema
- SC_Depth_Limit
- SC_Compl_Consistency
- ND
- ND_Sound
- ND_Compl_Truthtable
- ND_Compl_Truthtable_Compact
- HC
- HC_Compl_Consistency
- Resolution
- Resolution_Sound
- Resolution_Compl
- Resolution_Compl_Consistency
- HCSC
- SCND
- NDHC
- HCSCND
- LSC
- LSC_Resolution
- ND_FiniteAssms
- ND_Compl_SC
- Resolution_Compl_SC_Small
- Resolution_Compl_SC_Full
- MiniSC
- MiniSC_HC
- MiniSC_Craig

### Used by

- AI Planning Languages Semantics
- Verified SAT-Based AI Planning

## Cite

×

Propositional_Proof_Systems-AFP

    @article{Propositional_Proof_Systems-AFP,
      author  = {Julius Michaelis and Tobias Nipkow},
      title   = {Propositional Proof Systems},
      journal = {Archive of Formal Proofs},
      month   = {June},
      year    = {2017},
      note    = {\url{https://isa-afp.org/entries/Propositional_Proof_Systems.html},
                 Formal proof development},
      ISSN    = {2150-914x},
    }

Download

## Download

× Download latest

Older releases:

- Sep 13, 2023 : Isabelle2023
- Oct 27, 2022 : Isabelle2022
- Dec 14, 2021 : Isabelle2021-1
- Feb 23, 2021 : Isabelle2021
- Apr 20, 2020 : Isabelle2020
- Jun 11, 2019 : Isabelle2019
- Aug 16, 2018 : Isabelle2018
- Oct 10, 2017 : Isabelle2017
- Jun 22, 2017 : Isabelle2016-1