| Copyright | (c) Artem Mavrin 2021 |
|---|---|
| License | BSD3 |
| Maintainer | artemvmavrin@gmail.com |
| Stability | experimental |
| Portability | POSIX |
| Safe Haskell | Safe |
| Language | Haskell2010 |
AutoProof.Internal.Proof
Description
Proofs in propositional logic.
Synopsis
- data Proof a where
- pattern Axiom :: Judgement a -> Proof a
- pattern FalseElim :: Judgement a -> Proof a -> Proof a
- pattern TrueIntr :: Judgement a -> Proof a
- pattern NotElim :: Judgement a -> Proof a -> Proof a -> Proof a
- pattern NotIntr :: Judgement a -> Proof a -> Proof a
- pattern ImpElim :: Judgement a -> Proof a -> Proof a -> Proof a
- pattern ImpIntr :: Judgement a -> Proof a -> Proof a
- pattern OrElim :: Judgement a -> Proof a -> Proof a -> Proof a -> Proof a
- pattern OrIntrL :: Judgement a -> Proof a -> Proof a
- pattern OrIntrR :: Judgement a -> Proof a -> Proof a
- pattern AndElimL :: Judgement a -> Proof a -> Proof a
- pattern AndElimR :: Judgement a -> Proof a -> Proof a
- pattern AndIntr :: Judgement a -> Proof a -> Proof a -> Proof a
- pattern IffElimL :: Judgement a -> Proof a -> Proof a
- pattern IffElimR :: Judgement a -> Proof a -> Proof a
- pattern IffIntr :: Judgement a -> Proof a -> Proof a -> Proof a
- weakenProof :: Ord a => Proof a -> Formula a -> Proof a
- strengthenProof :: Ord a => Proof a -> Proof a
- prettyProof :: PrettyPrintable a => Proof a -> String
Proof type
A proof tree for propositional logic.
Bundled Patterns
| pattern Axiom :: Judgement a -> Proof a | An axiom \[ \frac{}{ g \vdash a } \, (\text{Axiom}) \] |
| pattern FalseElim :: Judgement a -> Proof a -> Proof a | Falsity elimination (principle of explosion).
\[ \frac{ \displaystyle\frac{ p }{ g \vdash \bot } }{ g \vdash a } \, ({\bot}\text{E}) \] |
| pattern TrueIntr :: Judgement a -> Proof a | Truth introduction.
\[ \frac{}{ g \vdash \top } \, (\top\text{I}) \] |
| pattern NotElim :: Judgement a -> Proof a -> Proof a -> Proof a | Negation elimination.
\[ \frac{ \displaystyle\frac{ p }{ g_1 \vdash \lnot a } \qquad \displaystyle\frac{ q }{ g_2 \vdash a } }{ g \vdash \bot } \, ({\lnot}\text{E}) \] |
| pattern NotIntr :: Judgement a -> Proof a -> Proof a | Negation introduction.
\[ \frac{ \displaystyle\frac{ p }{ g, a \vdash \bot } }{ g \vdash \lnot a } \, ({\lnot}\text{I}) \] |
| pattern ImpElim :: Judgement a -> Proof a -> Proof a -> Proof a | Implication elimination (modus ponens).
\[ \frac{ \displaystyle\frac{ p }{ g_1 \vdash a \rightarrow b } \qquad \displaystyle\frac{ q }{ g_2 \vdash a } }{ g \vdash b } \, ({\rightarrow}\text{E}) \] |
| pattern ImpIntr :: Judgement a -> Proof a -> Proof a | Implication introduction.
\[ \frac{ \displaystyle\frac{ p }{ g, a \vdash b } }{ g \vdash a \rightarrow b } \, ({\rightarrow}\text{I}) \] |
| pattern OrElim :: Judgement a -> Proof a -> Proof a -> Proof a -> Proof a | Disjunction elimination.
\[ \frac{ \displaystyle\frac{ p }{ g_1 \vdash a \lor b } \qquad \displaystyle\frac{ q }{ g_2, a \vdash c } \qquad \displaystyle\frac{ r }{ g_3, b \vdash c } }{ g \vdash c } \, ({\lor}\text{E}) \] |
| pattern OrIntrL :: Judgement a -> Proof a -> Proof a | Left disjunction introduction.
\[ \frac{ \displaystyle\frac{ p }{ g \vdash a } }{ g \vdash a \lor b } \, ({\lor}\text{IL}) \] |
| pattern OrIntrR :: Judgement a -> Proof a -> Proof a | Right disjunction introduction.
\[ \frac{ \displaystyle\frac{ p }{ g \vdash b } }{ g \vdash a \lor b } \, ({\lor}\text{IR}) \] |
| pattern AndElimL :: Judgement a -> Proof a -> Proof a | Left conjunction elimination.
\[ \frac{ \displaystyle\frac{ p }{ g \vdash a \land b } }{ g \vdash a } \, ({\land}\text{EL}) \] |
| pattern AndElimR :: Judgement a -> Proof a -> Proof a | Right conjunction elimination.
\[ \frac{ \displaystyle\frac{ p }{ g \vdash a \land b } }{ g \vdash b } \, ({\land}\text{ER}) \] |
| pattern AndIntr :: Judgement a -> Proof a -> Proof a -> Proof a | Conjunction introduction.
\[ \frac{ \displaystyle\frac{ p }{ g_1 \vdash a } \qquad \displaystyle\frac{ q }{ g_2 \vdash b } }{ g \vdash a \land b } \, ({\land}\text{I}) \] |
| pattern IffElimL :: Judgement a -> Proof a -> Proof a | Left equivalence elimination.
\[ \frac{ \displaystyle\frac{ p }{ g \vdash a \leftrightarrow b } }{ g \vdash a \rightarrow b } \, ({\leftrightarrow}\text{EL}) \] |
| pattern IffElimR :: Judgement a -> Proof a -> Proof a | Right equivalence elimination.
\[ \frac{ \displaystyle\frac{ p }{ g \vdash a \leftrightarrow b } }{ g \vdash b \rightarrow a } \, ({\leftrightarrow}\text{ER}) \] |
| pattern IffIntr :: Judgement a -> Proof a -> Proof a -> Proof a | Equivalence introduction.
\[ \frac{ \displaystyle\frac{ p }{ g_1 \vdash a \rightarrow b } \qquad \displaystyle\frac{ q }{ g_2 \vdash b \rightarrow a } }{ g \vdash a \leftrightarrow b } \, ({\leftrightarrow}\text{I}) \] |
Instances
| Eq a => Eq (Proof a) Source # | |
| Ord a => Ord (Proof a) Source # | |
Defined in AutoProof.Internal.Proof.Types | |
| (Ord a, Read a) => Read (Proof a) Source # | |
| Show a => Show (Proof a) Source # | |
| AST (Proof a) Source # | |
| PrettyPrintable a => PrettyPrintable (Proof a) Source # | |
| type Root (Proof a) Source # | |
Defined in AutoProof.Internal.Proof.Types | |
Operations on proofs
weakenProof :: Ord a => Proof a -> Formula a -> Proof a Source #
The weakening structural rule. ( modifies the proof
weakenProof p a)p to include a as an additional hypothesis.
strengthenProof :: Ord a => Proof a -> Proof a Source #
Strengthen a proof by preserving its structure but removing redundant hypotheses where possible.
Pretty-printing
prettyProof :: PrettyPrintable a => Proof a -> String Source #
Get a pretty-printed representation of a proof.