logic - How to prove the mutual equivalence of peirce, classic, excluded_middle, de_morgan_not_and_not and implies_to_or without using intuition in coq -

i simplified proof procedure of mutual equivalence of peirce, classic, excluded_middle, de_morgan_not_and_not , implies_to_or written in git@github.com:b-rich/sf.git following.

theorem excluded_middle_irrefutable:  forall (p:prop), ~ ~ (p \/ ~ p). proof.   intros. unfold not. intros.   apply h. right. intros. apply h. left. apply h0. qed.  definition peirce                := forall p q: prop, ((p->q)->p)->p. definition classic               := forall p :  prop, ~~p -> p. definition excluded_middle       := forall p :  prop, p \/ ~p. definition de_morgan_not_and_not := forall p q: prop, ~(~p /\ ~q) -> p\/q. definition implies_to_or         := forall p q: prop, (p->q) -> (~p\/q).  theorem peirce_classic : peirce -> classic. proof.   compute. intros.   specialize (h p false).   apply h. intros.   apply h. contradiction h0. qed.  theorem classic_excluded_middle : classic -> excluded_middle. proof.   compute. intros.   apply h. intros.   apply h0.   right.   intros.   assert (p \/ (p->false)) h2.     apply (or_introl h1).   apply (h0 h2). qed.  theorem false_dist_1 : forall {p q : prop}, (p \/ q -> false) -> (p -> false) /\ (q -> false). proof.   intros.   split.   intros.   apply (h (or_introl h0)).   intros.   apply (h (or_intror h0)). qed.  theorem false_dist_2 : forall {p q : prop}, (p -> false) /\ (q -> false) -> (p \/ q -> false). proof.   intros.   inversion h.   inversion h0.   apply (h1 h3).   apply (h2 h3). qed.  theorem em_de_morgan : excluded_middle -> de_morgan_not_and_not. proof.   compute. intros.   specialize (h (p \/ q)).   inversion h.   apply h1.   apply (false_ind (p \/ q) (h0 (false_dist_1 h1))). qed.  theorem double_neg : forall p : prop,   p -> ((p->false)->false). proof.   (* worked in class *)   intros p h. intros g. apply g. apply h.  qed.  theorem de_morgan_to_or : de_morgan_not_and_not -> implies_to_or. proof.   compute. intros.   specialize (h (p -> false) q).   intuition. qed.  theorem to_or_peirce: implies_to_or -> peirce. proof.   compute. intros.   specialize (h p p).   intuition. qed. 

i remove intuition tactics successfully, except last two.

my question is:

• how prove to_or_peirce , de_morgan_to_or without using intuition tactic?
• what intuition tactic do?
• is there way extract concrete procedures might generated intuition tactic?

(first off, know part of benjamin c. pierce's software foundations. these used university classes, not give solutions these exercises , spoil fun else. if you're doing these on own (like did), i'm sorry hope can understand – don't want "reward" effort put these materials out in open work coming new exercises.)

---

is there way extract concrete procedures might generated intuition tactic?

well, defined thing, can print thing. definition. things have been manually defined, looks pretty wrote. things generated tactics, can unreadable (and contain unnecessary long-winded indirections.) practice, you'll able read , re-construct (in more readable way) proofs of these.

what may or may not work saying info <tactic>, should output list/tree of applied tactics – seems broken (for years now…), in new versions of coq there may specialized tactics info_trivial, info_auto, or info_eauto might you.

---

what intuition tactic do?

the documentation of intuition rather cryptic, contains helpful snippets

[…] in fact, tauto intuition fail.

[…]

variants:

1. intuition
   equivalent intuition auto *.

(that last part means try intuition info_auto , see if gives useful info. unfortunately, it'll print long list of (* info auto : *) idtac. because these theorems tautologies , auto doesn't anything.)

so, on documentation of tauto:

this tactic implements decision procedure intuitionistic propositional calculus based on contraction-free sequent calculi ljt* of roy dyckhoff [54]. note tauto succeeds on instance of intuitionistic tautological proposition. tauto unfolds negations , logical equivalence not unfold other definition.

that should clear now, right? right? ;-)

(at point, try looking @ the definition of tauto that's not clearer.)

putting pieces , giving examples:

as documentation says, tauto (and hence intuition) "implement decision procedure intuitionistic propositional calculus". is, that's "reordering of stuff" in conjunctions (/\), disjunctions (\/), (bi)implications (<->/->) , cases of negation (~) should solved this.

variables b c d : prop. lemma foo : (a /\ b) -> a.  tauto.  qed.            (* solves *) lemma bar : (a /\ b) -> a.  auto. (* fails *) auto 9999 *. (* fails *) lemma baz : ((b /\ c) /\ d) -> ((a /\ c) -> (d /\ b /\ (a /\ a))).             tauto.  qed.  (* solves *) lemma qux : (a \/ b) /\ (c \/ (a -> b)) /\ ~b -> c.  tauto.  qed. (* solves *) (* etc. *) 

for of these, auto nothing tauto ("tautology") solve them. intuition try more things when basic taking-apart , throwing-together of tauto done , didn't solve yet.

(does help?)

---

how prove to_or_peirce , de_morgan_to_or without using intuition tactic?

a hint: h has form … -> (… \/ …), can destruct or case analyze it, you'd disjunction (but in "sea of symbols" may hard see possible). rest should easy.