Questions tagged [coq-tactic]

Tactics are programs written in Ltac, the untyped language used in the Coq proof assistant to transform goals and terms. This tag should be used on questions related to the issues in using Coq tactics to derive proofs using the Coq proof assistant.

Tactics are programs written in Ltac, the untyped language used in the Coq proof assistant to transform goals and terms. In general, the aim of using tactics is to construct a proof or proof object for the theorem in question. Initially, the proof object contains a hole corresponding to the goal of the theorem in question. As the proof proceeds, tactics transform the current goal/sub-goal and hypotheses in the local proof context using established theorems in the global context as well as hypotheses in the local context. Some tactics can introduce new sub-goals corresponding to new holes in the proof object. For example, if the goal is a conjunction P /\ Q, can be decomposed into two sub-goals P and Q using the split tactic. Certain tactics can also reduce the number of sub-goals (or holes in the proof object). The theorem is proved when there is no more sub-goals to prove (i.e. no more holes to fill in the proof object).

Strictly speaking, tactics are not necessary to prove theorems in Coq. It is possible to construct a proof object directly. However, tactics provide an interactive way of constructing a proof, which are closer to the manner proofs are developed manually.

For a comprehensive documentation of tactics, see the Coq reference manual: https://coq.inria.fr/refman/tactic-index.html

383 questions
17
votes
2 answers

How to switch the current goal in Coq?

Is it possible to switch the current goal or subgoal to prove in Coq? For example, I have a goal like this (from an eexists): ______________________________________(1/1) ?s > 0 /\ r1 * (r1 + s1) + ?s = r3 * (r3 + s2) What I want to do is to split…
thor
  • 21,418
  • 31
  • 87
  • 173
11
votes
3 answers

Non-empty list append theorem in Coq

I am trying to prove the following lemma in Coq: Require Import Lists.List. Import ListNotations. Lemma not_empty : forall (A : Type) (a b : list A), (a <> [] \/ b <> []) -> a ++ b <> []. Right now my current strategy was to destruct on a, and…
11
votes
1 answer

How to prove excluded middle is irrefutable in Coq?

I was trying to prove the following simple theorem from an online course that excluded middle is irrefutable, but got stuck pretty much at step 1: Theorem excluded_middle_irrefutable: forall (P:Prop), ~~(P \/ ~ P). Proof. intros P. unfold not.…
thor
  • 21,418
  • 31
  • 87
  • 173
9
votes
1 answer

How can I rewrite "+ 1" (plus one) to "S" (succ) in Coq?

I have the following Lemma with an incomplete proof: Lemma s_is_plus_one : forall n:nat, S n = n + 1. Proof. intros. reflexivity. Qed. This proof fails with Unable to unify "n + 1" with "S n". It seems like eq_S would be the way to prove this,…
Langston
  • 1,083
  • 10
  • 26
9
votes
2 answers

What's the difference between revert and generalize tactics in Coq?

From the Coq reference manual (8.5p1), my impression is that revert is the inverse of intro, but so is generalize to a certain extent. For example, revert and generalize dependent below seem to be the same. Goal forall x y: nat, 1 + x = 2 + y -> 1 +…
thor
  • 21,418
  • 31
  • 87
  • 173
9
votes
1 answer

Coq execution difference between semicolon ";" and period "."

Given a valid Coq proof using the ; tactical, is there a general formula for converting it to a valid equivalent proof with . substituted for ;? Many Coq proofs use the ; or tactic sequencing tactical. As a beginner, I want to watch the individual…
8
votes
0 answers

Definitional vs propositional equality in Coq lemma statements

When writing highly automated proofs in Coq (CPDT-style) proofs, building on extensive use of eauto N, I must often modify my lemma statements to allow eauto to use them easily. In particular, I must replace statements of form (1) forall vars, P (f…
Blaisorblade
  • 6,438
  • 1
  • 43
  • 76
8
votes
1 answer

Is there a minimal complete set of tactics in Coq?

I have seen a lot of Coq tactics that are overlapping each other in function. For example, when you have the exact conclusion in the hypothesis, you can use assumption, apply, exact, trivial, and maybe others. Other examples include destruct and…
thor
  • 21,418
  • 31
  • 87
  • 173
7
votes
1 answer

Is it possible to turn unification errors into goals in Coq?

I've been working on a formalization for a process calculus in Coq (repository here), and constantly find myself trying to apply a function which fails because of equivalent, but syntactically different, subterms. This often happens because of…
paulotorrens
  • 2,286
  • 20
  • 30
7
votes
2 answers

How does one inspect what more complicated tactics do in Coq step-by-step?

I was trying to go through the famous and wonderful software foundations book but I got to an example where simpl. and reflexivity. just do to much under the covers and are hindering my learning & understanding. I was going through the following…
Charlie Parker
  • 5,884
  • 57
  • 198
  • 323
7
votes
2 answers

Coq: why do I need to manually unfold a value even though it has a `Hint Unfold` on it?

I've come up with the following toy proof script: Inductive myType : Type := | c : unit -> myType. Inductive myProp : myType -> Type := | d : forall t, myProp (c t). Hint Constructors myProp. Definition myValue : myType := c tt. Hint Unfold…
Carl Patenaude Poulin
  • 6,238
  • 5
  • 24
  • 46
7
votes
2 answers

How does the discriminate tactic work?

I was curious about how the discriminate tactic works behind the curtain. Therefore I did some experiments. First a simple Inductive definition: Inductive AB:=A|B. Then a simple lemma which can be proved by the discriminate tactic: Lemma l1: A=B ->…
Cryptostasis
  • 1,166
  • 6
  • 15
7
votes
2 answers

How to use a custom induction principle in Coq?

I read that the induction principle for a type is just a theorem about a proposition P. So I constructed an induction principle for List based on the right (or reverse) list constructor . Definition rcons {X:Type} (l:list X) (x:X) : list X := l…
thor
  • 21,418
  • 31
  • 87
  • 173
7
votes
1 answer

Coq tactic for record equality?

In Coq, when attempting to prove equality of records, is there a tactic that will decompose that into equality of all of its fields? For example, Record R := {x:nat;y:nat}. Variables a b c d : nat. Lemma eqr : {|x:=a;y:=b|} = {|x:=c;y:=d|}. Is…
Ashley Yakeley
  • 664
  • 4
  • 11
6
votes
2 answers

Induction on evidence for the "less than" relation in coq

I am working on the proof of the following theorem Sn_le_Sm__n_le_m in IndProp.v of Software Foundations (Vol 1: Logical Foundations). Theorem Sn_le_Sm__n_le_m : ∀n m, S n ≤ S m → n ≤ m. Proof. intros n m HS. induction HS as [ | m' Hm' IHm']. …
hengxin
  • 1,867
  • 2
  • 21
  • 42
1
2 3
25 26