Library Deduxit.Linear.Formulas
Formulas of classical linear logic in negation normal form
From Stdlib Require Import Bool List.
Import ListNotations.
Section Formulas.
Context {atom : Type}.
A formula: a literal, a unit, a binary connective or an exponential.
an atom a
its negation a⊥
1
⊥
⊤
0
A ⊗ B
A ⅋ B
A & B
A ⊕ B
!A
?A
Linear negation: it swaps each connective with its dual and var
with covar, and applied twice it gives the formula back.
Fixpoint dual (A : formula) : formula :=
match A with
| var a ⇒ covar a
| covar a ⇒ var a
| one ⇒ bot
| bot ⇒ one
| top ⇒ zero
| zero ⇒ top
| tens A B ⇒ parr (dual A) (dual B)
| parr A B ⇒ tens (dual A) (dual B)
| awith A B ⇒ aplus (dual A) (dual B)
| aplus A B ⇒ awith (dual A) (dual B)
| oc A ⇒ wn (dual A)
| wn A ⇒ oc (dual A)
end.
Lemma dual_dual : ∀ A, dual (dual A) = A.
Proof. induction A; cbn; congruence. Qed.
match A with
| var a ⇒ covar a
| covar a ⇒ var a
| one ⇒ bot
| bot ⇒ one
| top ⇒ zero
| zero ⇒ top
| tens A B ⇒ parr (dual A) (dual B)
| parr A B ⇒ tens (dual A) (dual B)
| awith A B ⇒ aplus (dual A) (dual B)
| aplus A B ⇒ awith (dual A) (dual B)
| oc A ⇒ wn (dual A)
| wn A ⇒ oc (dual A)
end.
Lemma dual_dual : ∀ A, dual (dual A) = A.
Proof. induction A; cbn; congruence. Qed.
Whether a formula starts with ?. Every calculus may weaken such
a formula.
Definition is_wn (A : formula) : bool :=
match A with
| wn _ ⇒ true
| _ ⇒ false
end.
Section Equality.
match A with
| wn _ ⇒ true
| _ ⇒ false
end.
Section Equality.
A Boolean equality on atoms; the checker compares literals with
it.
Structural equality of formulas, comparing atoms with atom_eqb.
Fixpoint formula_eqb (A B : formula) : bool :=
match A, B with
| var a, var b ⇒ atom_eqb a b
| covar a, covar b ⇒ atom_eqb a b
| one, one ⇒ true
| bot, bot ⇒ true
| top, top ⇒ true
| zero, zero ⇒ true
| tens A1 A2, tens B1 B2 ⇒ formula_eqb A1 B1 && formula_eqb A2 B2
| parr A1 A2, parr B1 B2 ⇒ formula_eqb A1 B1 && formula_eqb A2 B2
| awith A1 A2, awith B1 B2 ⇒ formula_eqb A1 B1 && formula_eqb A2 B2
| aplus A1 A2, aplus B1 B2 ⇒ formula_eqb A1 B1 && formula_eqb A2 B2
| oc A, oc B ⇒ formula_eqb A B
| wn A, wn B ⇒ formula_eqb A B
| _, _ ⇒ false
end.
match A, B with
| var a, var b ⇒ atom_eqb a b
| covar a, covar b ⇒ atom_eqb a b
| one, one ⇒ true
| bot, bot ⇒ true
| top, top ⇒ true
| zero, zero ⇒ true
| tens A1 A2, tens B1 B2 ⇒ formula_eqb A1 B1 && formula_eqb A2 B2
| parr A1 A2, parr B1 B2 ⇒ formula_eqb A1 B1 && formula_eqb A2 B2
| awith A1 A2, awith B1 B2 ⇒ formula_eqb A1 B1 && formula_eqb A2 B2
| aplus A1 A2, aplus B1 B2 ⇒ formula_eqb A1 B1 && formula_eqb A2 B2
| oc A, oc B ⇒ formula_eqb A B
| wn A, wn B ⇒ formula_eqb A B
| _, _ ⇒ false
end.
atom_eqb decides equality. The soundness theorems assume this,
and a certificate proves it of the equality it uses.
Hypothesis atom_eqb_spec : ∀ a b, reflect (a = b) (atom_eqb a b).
Lemma formula_eqb_spec : ∀ A B, reflect (A = B) (formula_eqb A B).
Proof.
induction A; destruct B; cbn; try (constructor; congruence).
all: repeat match goal with
| |- reflect _ (atom_eqb ?a ?b) ⇒ destruct (atom_eqb_spec a b)
| |- reflect _ (formula_eqb ?A ?B && _) ⇒
match goal with IH : ∀ B, reflect (A = B) _ |- _ ⇒ destruct (IH B) end
| |- reflect _ (formula_eqb ?A ?B) ⇒
match goal with IH : ∀ B, reflect (A = B) _ |- _ ⇒ destruct (IH B) end
| |- reflect _ (true && _) ⇒ cbn
| |- reflect _ (false && _) ⇒ cbn
end.
all: constructor; congruence.
Qed.
Lemma formula_eqb_spec : ∀ A B, reflect (A = B) (formula_eqb A B).
Proof.
induction A; destruct B; cbn; try (constructor; congruence).
all: repeat match goal with
| |- reflect _ (atom_eqb ?a ?b) ⇒ destruct (atom_eqb_spec a b)
| |- reflect _ (formula_eqb ?A ?B && _) ⇒
match goal with IH : ∀ B, reflect (A = B) _ |- _ ⇒ destruct (IH B) end
| |- reflect _ (formula_eqb ?A ?B) ⇒
match goal with IH : ∀ B, reflect (A = B) _ |- _ ⇒ destruct (IH B) end
| |- reflect _ (true && _) ⇒ cbn
| |- reflect _ (false && _) ⇒ cbn
end.
all: constructor; congruence.
Qed.
Equality of formulas as a decision, used in proofs; the checker
computes with formula_eqb.