proposition: Lemma poly_of_formula_valid_compat : forall f, exists n, valid n (poly_of_formula f).
proof: Proof. intros f; induction f; simpl. + exists (Pos.succ p); constructor; intuition; inversion H. + exists 1%positive; auto. + exists 1%positive; auto. + destruct IHf1 as [n1 Hn1]; destruct IHf2 as [n2 Hn2]; exists (Pos.max n1 n2); auto. + destruct IHf1 as [n1 Hn1]; destruct IHf2 as [n2 Hn2]; exists (Pos.max (Pos.max n1 n2) (Pos.max n1 n2)); auto. + destruct IHf as [n Hn]; exists (Pos.max 1 n); auto. + destruct IHf1 as [n1 Hn1]; destruct IHf2 as [n2 Hn2]; exists (Pos.max n1 n2); auto. + destruct IHf1 as [n1 Hn1]; destruct IHf2 as [n2 Hn2]; destruct IHf3 as [n3 Hn3]; eexists; eauto. Qed.
imports: Bool DecidableClass Algebra Ring PArith Lia