coq-library-undecidability icon indicating copy to clipboard operation
coq-library-undecidability copied to clipboard

Inversion lemma for formulas

Open Janis-Bai opened this issue 9 months ago • 2 comments

In the current version of the library, inversion on formulas is not working as expected. In some cases, for instance, congruence falls short of closing a goal s = t given the assumption q → s = q → t with s,t,q: form.

@yforster suggested to fix this by adding the following lemma to the library (formulation and proof are due to him):

Inductive aand (P Q R : Prop) :=
      cconj : P -> Q -> R -> aand P Q R.

Lemma form_inv {Σ_funcs : funcs_signature} {Σ_preds : preds_signature} {ops : operators} {flag : falsity_flag} phi1 phi2 :
      phi1 = phi2 ->
      match phi1, phi2 with
      | falsity, falsity => True
      | atom _ P1 args1, atom _ P2 args2 => True
      | bin falsity_on o1 phi1' phi2', bin falsity_on o2 phi1'' phi2'' =>
            aand (o1 = o2) (phi1' = phi1'') (phi2' = phi2'')
      | bin falsity_off o1 phi1' phi2', bin falsity_off o2 phi1'' phi2'' =>
          aand (o1 = o2) (phi1' = phi1'') (phi2' = phi2'')
      | quant falsity_on o1 phi, quant falsity_on o2 phi' =>
            o1 = o2 /\ phi = phi'
      | quant falsity_off o1 phi, quant falsity_off o2 phi' =>
          o1 = o2 /\ phi = phi'
      | _, _ => False
      end.
Proof.
      intros H. destruct phi1; subst; eauto.
      all: destruct b; econstructor; eauto.
Qed.

Janis-Bai avatar May 11 '24 10:05 Janis-Bai