Exercise session 1 — Solutions
Try to solve the following exercises by using the tactics shown in class:
intro, apply, destruct, split, left, right, exfalso, simpl, reflexivity,
f_equal, induction, assumption.
When a lemma ends with the keyword Admitted, it means the lemma is
accepted and can be used without a proof.
When solving exercises, replace Admitted with Qed once you have completed
the proofs.
There are more exercises than what can be done in the exercise session during the lecture. Proving is like programming: You will have to practice at home. It is fine not to do all the exercises, but you should feel like you could do the exercises. We will help you with this assessment at the start of every lecture.
We will begin with the exercises you have seen already.
Set Default Goal Selector "!".Exercise: Implication
P: PropP -> PP: PropP -> Papply h. Qed.P: Prop
h: PP
Exercise: Conjunction
P, Q: PropP /\ Q -> Q /\ PP, Q: PropP /\ Q -> Q /\ PP, Q: Prop
h: P /\ QQ /\ PP, Q: Prop
hP: P
hQ: QQ /\ PP, Q: Prop
hP: P
hQ: QQP, Q: Prop
hP: P
hQ: QPapply hQ.P, Q: Prop
hP: P
hQ: QQapply hP. Qed.P, Q: Prop
hP: P
hQ: QP
Exercise: Disjunction
P, Q: PropP \/ Q -> Q \/ PP, Q: PropP \/ Q -> Q \/ PP, Q: Prop
h: P \/ QQ \/ PP, Q: Prop
hP: PQ \/ PP, Q: Prop
hQ: QQ \/ PP, Q: Prop
hP: PQ \/ Papply hP.P, Q: Prop
hP: PPP, Q: Prop
hQ: QQ \/ Papply hQ. Qed.P, Q: Prop
hQ: QQ
Exercise: Truth
split. Qed.True
Exercise: Ex falso
P: PropFalse -> PP: PropFalse -> Pdestruct h. Qed.P: Prop
h: FalseP
Exercise: Negation
~ A (negation) is a notation for A -> False below.
~ False~ Falseapply h. Qed.h: FalseFalse
Exercise: Propositional logic
Now some new exercises about propositional logic.
P, Q, R: Prop(P -> Q) -> (Q -> R) -> P -> RP, Q, R: Prop(P -> Q) -> (Q -> R) -> P -> RP, Q, R: Prop
hPQ: P -> Q(Q -> R) -> P -> RP, Q, R: Prop
hPQ: P -> Q
hQR: Q -> RP -> RP, Q, R: Prop
hPQ: P -> Q
hQR: Q -> R
hP: PRP, Q, R: Prop
hPQ: P -> Q
hQR: Q -> R
hP: PQapply hP. Qed.P, Q, R: Prop
hPQ: P -> Q
hQR: Q -> R
hP: PPP: PropP -> ~ ~ PP: PropP -> ~ ~ PP: Prop
hP: P~ ~ PP: Prop
hP: P
hnP: ~ PFalseapply hP. Qed.P: Prop
hP: P
hnP: ~ PP
For this one, note that if you already separated a case distinction
with dashes (-) then you can use + at the next level.
The following level is marked with *.
P, Q, R: Prop(P \/ Q) /\ R -> P /\ R \/ Q /\ RP, Q, R: Prop(P \/ Q) /\ R -> P /\ R \/ Q /\ RP, Q, R: Prop
h: (P \/ Q) /\ RP /\ R \/ Q /\ RP, Q, R: Prop
hPQ: P \/ Q
hR: RP /\ R \/ Q /\ RP, Q, R: Prop
hP: P
hR: RP /\ R \/ Q /\ RP, Q, R: Prop
hQ: Q
hR: RP /\ R \/ Q /\ RP, Q, R: Prop
hP: P
hR: RP /\ R \/ Q /\ RP, Q, R: Prop
hP: P
hR: RP /\ RP, Q, R: Prop
hP: P
hR: RPP, Q, R: Prop
hP: P
hR: RRapply hP.P, Q, R: Prop
hP: P
hR: RPapply hR.P, Q, R: Prop
hP: P
hR: RRP, Q, R: Prop
hQ: Q
hR: RP /\ R \/ Q /\ RP, Q, R: Prop
hQ: Q
hR: RQ /\ RP, Q, R: Prop
hQ: Q
hR: RQP, Q, R: Prop
hQ: Q
hR: RRapply hQ.P, Q, R: Prop
hQ: Q
hR: RQapply hR. Qed.P, Q, R: Prop
hQ: Q
hR: RRP: PropP /\ ~ P -> FalseP: PropP /\ ~ P -> FalseP: Prop
h: P /\ ~ PFalseP: Prop
hP: P
hnP: ~ PFalseapply hP. Qed.P: Prop
hP: P
hnP: ~ PPP, Q: PropP \/ ~ P -> ((P -> Q) -> P) -> PP, Q: PropP \/ ~ P -> ((P -> Q) -> P) -> PP, Q: Prop
lem: P \/ ~ P((P -> Q) -> P) -> PP, Q: Prop
lem: P \/ ~ P
h: (P -> Q) -> PPP, Q: Prop
hP: P
h: (P -> Q) -> PPP, Q: Prop
hnP: ~ P
h: (P -> Q) -> PPapply hP.P, Q: Prop
hP: P
h: (P -> Q) -> PPP, Q: Prop
hnP: ~ P
h: (P -> Q) -> PPP, Q: Prop
hnP: ~ P
h: (P -> Q) -> PP -> QP, Q: Prop
hnP: ~ P
h: (P -> Q) -> P
hP: PQP, Q: Prop
hnP: ~ P
h: (P -> Q) -> P
hP: PFalseapply hP. Qed.P, Q: Prop
hnP: ~ P
h: (P -> Q) -> P
hP: PPP: PropP \/ ~ P -> ~ ~ P -> PP: PropP \/ ~ P -> ~ ~ P -> PP: Prop
lem: P \/ ~ P~ ~ P -> PP: Prop
lem: P \/ ~ P
hnnP: ~ ~ PPP: Prop
hP: P
hnnP: ~ ~ PPP: Prop
hnP: ~ P
hnnP: ~ ~ PPassumption.P: Prop
hP: P
hnnP: ~ ~ PPP: Prop
hnP: ~ P
hnnP: ~ ~ PPP: Prop
hnP: ~ P
hnnP: ~ ~ PFalseapply hnP. Qed.P: Prop
hnP: ~ P
hnnP: ~ ~ P~ P
To introduce several variables at once, you can use the intros tactic.
P, Q: Prop(P -> Q) -> ~ ~ P -> ~ ~ QP, Q: Prop(P -> Q) -> ~ ~ P -> ~ ~ QP, Q: Prop
hPQ: P -> Q
hnnP: ~ ~ P~ ~ QP, Q: Prop
hPQ: P -> Q
hnnP: ~ ~ P
hnQ: ~ QFalseP, Q: Prop
hPQ: P -> Q
hnnP: ~ ~ P
hnQ: ~ Q~ PP, Q: Prop
hPQ: P -> Q
hnnP: ~ ~ P
hnQ: ~ Q
hP: PFalseP, Q: Prop
hPQ: P -> Q
hnnP: ~ ~ P
hnQ: ~ Q
hP: PQapply hP. Qed.P, Q: Prop
hPQ: P -> Q
hnnP: ~ ~ P
hnQ: ~ Q
hP: PP
Exercise: Booleans
Let us switch to Booleans again.
andb is conjunction, orb is disjunction, negb is negation.
Both andb and orb look at the first Boolean before simplifying.
b1, b2, b3: bool(b1 && (b2 || b3))%bool = (b1 && b2 || b1 && b3)%boolb1, b2, b3: bool(b1 && (b2 || b3))%bool = (b1 && b2 || b1 && b3)%boolb2, b3: bool(true && (b2 || b3))%bool = (true && b2 || true && b3)%boolb2, b3: bool(false && (b2 || b3))%bool = (false && b2 || false && b3)%boolb2, b3: bool(true && (b2 || b3))%bool = (true && b2 || true && b3)%boolreflexivity.b2, b3: bool(b2 || b3)%bool = (b2 || b3)%boolb2, b3: bool(false && (b2 || b3))%bool = (false && b2 || false && b3)%boolreflexivity. Qed.b2, b3: boolfalse = falseb1, b2: boolnegb (b1 && b2) = (negb b1 || negb b2)%boolb1, b2: boolnegb (b1 && b2) = (negb b1 || negb b2)%boolb2: boolnegb (true && b2) = (negb true || negb b2)%boolb2: boolnegb (false && b2) = (negb false || negb b2)%boolb2: boolnegb (true && b2) = (negb true || negb b2)%boolreflexivity.b2: boolnegb b2 = negb b2b2: boolnegb (false && b2) = (negb false || negb b2)%boolreflexivity. Qed.b2: booltrue = true
Exercise: Computation
Let us switch to natural numbers.
12 + 3 = 1512 + 3 = 15reflexivity. Qed.15 = 15
Exercise: Addition
Let us make a lemma out of the n + 0 = n property.
You can then apply this lemma by using apply n_plus_0 like for hypotheses!
n: natn + 0 = nn: natn + 0 = n0 + 0 = 0n: nat
IHn: n + 0 = nS n + 0 = S n0 + 0 = 0reflexivity.0 = 0n: nat
IHn: n + 0 = nS n + 0 = S nn: nat
IHn: n + 0 = nS (n + 0) = S nassumption. Qed.n: nat
IHn: n + 0 = nn + 0 = nn: natn + n = 2 * nn: natn + n = 2 * nn: natn + n = n + (n + 0)n: natn = n + 0reflexivity. Qed.n: natn = nn, m: natn + S m = S n + mn, m: natn + S m = S n + mm: nat0 + S m = 1 + mn, m: nat
ih: n + S m = S n + mS n + S m = S (S n) + mm: nat0 + S m = 1 + mreflexivity.m: natS m = S mn, m: nat
ih: n + S m = S n + mS n + S m = S (S n) + mn, m: nat
ih: n + S m = S n + mS (n + S m) = S (S (n + m))apply ih. Qed.n, m: nat
ih: n + S m = S n + mn + S m = S (n + m)n, m: natn + m = m + nn, m: natn + m = m + nm: nat0 + m = m + 0n, m: nat
IHn: n + m = m + nS n + m = m + S nm: nat0 + m = m + 0m: natm = m + 0reflexivity.m: natm = mn, m: nat
IHn: n + m = m + nS n + m = m + S nn, m: nat
IHn: n + m = m + nS (n + m) = m + S nn, m: nat
IHn: n + m = m + nS (n + m) = S m + nn, m: nat
IHn: n + m = m + nS (n + m) = S (m + n)assumption. Qed.n, m: nat
IHn: n + m = m + nn + m = m + n
Show associativity of addition.
k, n, m: natk + n + m = k + (n + m)k, n, m: natk + n + m = k + (n + m)n, m: nat0 + n + m = 0 + (n + m)k, n, m: nat
IHk: k + n + m = k + (n + m)S k + n + m = S k + (n + m)n, m: nat0 + n + m = 0 + (n + m)reflexivity.n, m: natn + m = n + mk, n, m: nat
IHk: k + n + m = k + (n + m)S k + n + m = S k + (n + m)k, n, m: nat
IHk: k + n + m = k + (n + m)S (k + n + m) = S (k + (n + m))assumption. Qed.k, n, m: nat
IHk: k + n + m = k + (n + m)k + n + m = k + (n + m)
We can also show commutativity of multiplication.
Try to come up with the lemmas yourself.
Note that you can also use rewrite in the opposite direction by using:
rewrite <- n_plus_0
for instance.
You can also use rewrite with hypotheses you have.
If you ever find yourself with x = y to prove, when you think you can
prove y = x, you can also use the symmetry tactic.
Exercise: Minimum
Fill in the cases for the following function.
We use a placeholder REPLACE_ME that you need to replace.
Fixpoint min (n m : nat) :=
match n, m with
| 0, _ => 0
| _, 0 => 0
| S n, S m => S (min n m)
end.Exercise: Minimum (continued)
forall n m : nat, min n m = min m nforall n m : nat, min n m = min m nn: natforall m : nat, min n m = min m n
Hint: start the induction before introducing m.
You can also use induction ... in.
forall m : nat, min 0 m = min m 0n: nat
ih: forall m : nat, min n m = min m nforall m : nat, min (S n) m = min m (S n)forall m : nat, min 0 m = min m 0m: natmin 0 m = min m 0min 0 0 = min 0 0m: natmin 0 (S m) = min (S m) 0min 0 0 = min 0 0reflexivity.0 = 0m: natmin 0 (S m) = min (S m) 0reflexivity.m: nat0 = 0n: nat
ih: forall m : nat, min n m = min m nforall m : nat, min (S n) m = min m (S n)n: nat
ih: forall m : nat, min n m = min m n
m: natmin (S n) m = min m (S n)n: nat
ih: forall m : nat, min n m = min m nmin (S n) 0 = min 0 (S n)n: nat
ih: forall m : nat, min n m = min m n
m: natmin (S n) (S m) = min (S m) (S n)n: nat
ih: forall m : nat, min n m = min m nmin (S n) 0 = min 0 (S n)reflexivity.n: nat
ih: forall m : nat, min n m = min m n0 = 0n: nat
ih: forall m : nat, min n m = min m n
m: natmin (S n) (S m) = min (S m) (S n)n: nat
ih: forall m : nat, min n m = min m n
m: natS (min n m) = S (min m n)apply ih. Qed.n: nat
ih: forall m : nat, min n m = min m n
m: natmin n m = min m n
Exercise: Equivalence and forward reasoning (advanced)
If you have already used Rocq before or you are done with the exercises, give the advanced exercises a try. They hopefully teach you things you have not seen before.
If they are too hard, don't worry too much about it for the exam.
Section Advanced. Context (P Q R : Prop).
We introduce a new notation P <-> Q meaning P is equivalent to Q.
It is essentially a notation for (P -> Q) /\ (Q -> P) so you can use the
tactics split and destruct to prove it and use it.
Here is a trivial example to understand it.
P, Q, R: PropP <-> PP, Q, R: PropP <-> PP, Q, R: PropP -> PP, Q, R: PropP -> PP, Q, R: PropP -> Passumption.P, Q, R: Prop
H: PPP, Q, R: PropP -> Passumption. Qed.P, Q, R: Prop
H: PP
And here is a new tactic that is going to be useful: assert.
When you write assert (h : P) you are telling Rocq that you want to prove
P and that then you are going to use this as a hypothesis named h.
This is sometimes called forward reasoning.
See how it works below.
P, Q, R: Prop(Q -> P) /\ (R -> P) -> Q \/ R -> ~ ~ PP, Q, R: Prop(Q -> P) /\ (R -> P) -> Q \/ R -> ~ ~ PP, Q, R: Prop
h1: (Q -> P) /\ (R -> P)
h2: Q \/ R~ ~ PP, Q, R: Prop
h1: (Q -> P) /\ (R -> P)
h2: Q \/ RPP, Q, R: Prop
h1: (Q -> P) /\ (R -> P)
h2: Q \/ R
hP: P~ ~ PP, Q, R: Prop
h1: (Q -> P) /\ (R -> P)
h2: Q \/ RPP, Q, R: Prop
hQP: Q -> P
hRP: R -> P
h2: Q \/ RPP, Q, R: Prop
hQP: Q -> P
hRP: R -> P
hQ: QPP, Q, R: Prop
hQP: Q -> P
hRP: R -> P
hR: RPP, Q, R: Prop
hQP: Q -> P
hRP: R -> P
hQ: QPapply hQ.P, Q, R: Prop
hQP: Q -> P
hRP: R -> P
hQ: QQP, Q, R: Prop
hQP: Q -> P
hRP: R -> P
hR: RPapply hR.P, Q, R: Prop
hQP: Q -> P
hRP: R -> P
hR: RRP, Q, R: Prop
h1: (Q -> P) /\ (R -> P)
h2: Q \/ R
hP: P~ ~ Papply hP. Qed.P, Q, R: Prop
h1: (Q -> P) /\ (R -> P)
h2: Q \/ R
hP: PPP, Q, R: Prop~ (P <-> ~ P)P, Q, R: Prop~ (P <-> ~ P)P, Q, R: Prop
h: P <-> ~ PFalseP, Q, R: Prop
h1: P -> ~ P
h2: ~ P -> PFalseP, Q, R: Prop
h1: P -> ~ P
h2: ~ P -> PPP, Q, R: Prop
h1: P -> ~ P
h2: ~ P -> P
hP: PFalseP, Q, R: Prop
h1: P -> ~ P
h2: ~ P -> PPP, Q, R: Prop
h1: P -> ~ P
h2: ~ P -> P~ PP, Q, R: Prop
h1: P -> ~ P
h2: ~ P -> P
hP: PFalseP, Q, R: Prop
h1: P -> ~ P
h2: ~ P -> P
hP: PPP, Q, R: Prop
h1: P -> ~ P
h2: ~ P -> P
hP: PPapply hP.P, Q, R: Prop
h1: P -> ~ P
h2: ~ P -> P
hP: PPapply hP.P, Q, R: Prop
h1: P -> ~ P
h2: ~ P -> P
hP: PPP, Q, R: Prop
h1: P -> ~ P
h2: ~ P -> P
hP: PFalseP, Q, R: Prop
h1: P -> ~ P
h2: ~ P -> P
hP: P~ PP, Q, R: Prop
h1: P -> ~ P
h2: ~ P -> P
hP: P
hnP: ~ PFalseP, Q, R: Prop
h1: P -> ~ P
h2: ~ P -> P
hP: P~ Papply hP.P, Q, R: Prop
h1: P -> ~ P
h2: ~ P -> P
hP: PPP, Q, R: Prop
h1: P -> ~ P
h2: ~ P -> P
hP: P
hnP: ~ PFalseapply hP. Qed. End Advanced.P, Q, R: Prop
h1: P -> ~ P
h2: ~ P -> P
hP: P
hnP: ~ PP
Exercise: Quantifying over propositions (advanced)
For even more advanced stuff we are going to use quantifiers on propositions too. It's basically the same as with natural numbers.
If you have some hypothesis of the form:
h : forall x, P x
then know that you can use specialize (h y) to obtain h : P y.
See the following example.
(forall P : Prop, P) -> False(forall P : Prop, P) -> Falseh: forall P : Prop, PFalseassumption. Qed.h: FalseFalse
Note that it would work with apply directly in this case.
(forall P : Prop, P) -> False(forall P : Prop, P) -> Falseapply h. Qed.h: forall P : Prop, PFalse
Prove the converse now.
False -> forall P : Prop, PFalse -> forall P : Prop, Pdestruct h. Qed.h: Falseforall P : Prop, P
Exercise: Excluded middle (advanced)
Rocq is, at its basis, a system that has nothing but elimination and introduction rules for disjunctions:
In particular, these rules do not allow proving
In other words, Rocq implements intuitionistic logic. This allows
assuming classical laws of reasoning like the law of excluded middle and doing classical math
not assuming the law of excluded middle, thus being able to have interesting proofs of the form
A -> LEMfor a statementA.
We will prove A <-> LEM for two statements now:
Law of Excluded Middle
Definition theLEM := forall P, P \/ ~ P.Double Negation Elimination
Definition theDNE := forall P, ~~ P -> P.Peirce's law
Definition thePL := forall P Q : Prop, ((P -> Q) -> P) -> P.We can now prove the other direction from before.
theLEM -> theDNEtheLEM -> theDNE
You can use unfold to replace a name by its definition.
(forall P : Prop, P \/ ~ P) -> forall P : Prop, ~ ~ P -> Plem: forall P : Prop, P \/ ~ P
P: Prop
h: ~ ~ PPlem: forall P : Prop, P \/ ~ P
P: Prop
h: ~ ~ P
hP: PPlem: forall P : Prop, P \/ ~ P
P: Prop
h: ~ ~ P
hnP: ~ PPassumption.lem: forall P : Prop, P \/ ~ P
P: Prop
h: ~ ~ P
hP: PPcontradiction. Qed.lem: forall P : Prop, P \/ ~ P
P: Prop
h: ~ ~ P
hnP: ~ PPtheLEM -> thePLtheLEM -> thePL(forall P : Prop, P \/ ~ P) -> forall P Q : Prop, ((P -> Q) -> P) -> Plem: forall P : Prop, P \/ ~ P
P, Q: Prop
h: (P -> Q) -> PPlem: forall P : Prop, P \/ ~ P
P, Q: Prop
h: (P -> Q) -> P
hP: PPlem: forall P : Prop, P \/ ~ P
P, Q: Prop
h: (P -> Q) -> P
hnP: ~ PPassumption.lem: forall P : Prop, P \/ ~ P
P, Q: Prop
h: (P -> Q) -> P
hP: PPlem: forall P : Prop, P \/ ~ P
P, Q: Prop
h: (P -> Q) -> P
hnP: ~ PPcontradiction. Qed.lem: forall P : Prop, P \/ ~ P
P, Q: Prop
h: (P -> Q) -> P
hnP: ~ PP -> QtheDNE -> theLEMtheDNE -> theLEM(forall P : Prop, ~ ~ P -> P) -> forall P : Prop, P \/ ~ Pdns: forall P : Prop, ~ ~ P -> P
P: PropP \/ ~ Pdns: forall P : Prop, ~ ~ P -> P
P: Prop~ ~ (P \/ ~ P)dns: forall P : Prop, ~ ~ P -> P
P: Prop
hn: ~ (P \/ ~ P)Falsedns: forall P : Prop, ~ ~ P -> P
P: Prop
hn: ~ (P \/ ~ P)~ Pdns: forall P : Prop, ~ ~ P -> P
P: Prop
hn: ~ (P \/ ~ P)
hnP: ~ PFalsedns: forall P : Prop, ~ ~ P -> P
P: Prop
hn: ~ (P \/ ~ P)~ Pdns: forall P : Prop, ~ ~ P -> P
P: Prop
hn: ~ (P \/ ~ P)
hP: PFalsedns: forall P : Prop, ~ ~ P -> P
P: Prop
hn: ~ (P \/ ~ P)
hP: PP \/ ~ Passumption.dns: forall P : Prop, ~ ~ P -> P
P: Prop
hn: ~ (P \/ ~ P)
hP: PPdns: forall P : Prop, ~ ~ P -> P
P: Prop
hn: ~ (P \/ ~ P)
hnP: ~ PFalsedns: forall P : Prop, ~ ~ P -> P
P: Prop
hn: ~ (P \/ ~ P)
hnP: ~ PP \/ ~ Passumption. Qed.dns: forall P : Prop, ~ ~ P -> P
P: Prop
hn: ~ (P \/ ~ P)
hnP: ~ P~ PthePL -> theLEMthePL -> theLEM(forall P Q : Prop, ((P -> Q) -> P) -> P) -> theLEMpl: forall P Q : Prop, ((P -> Q) -> P) -> PtheLEMpl: forall P Q : Prop, ((P -> Q) -> P) -> PtheDNEpl: forall P Q : Prop, ((P -> Q) -> P) -> Pforall P : Prop, ~ ~ P -> Ppl: forall P Q : Prop, ((P -> Q) -> P) -> P
P: Prop~ ~ P -> PP: Prop
pl: forall Q : Prop, ((P -> Q) -> P) -> P~ ~ P -> PP: Prop
pl: ((P -> False) -> P) -> P~ ~ P -> PP: Prop
pl: ((P -> False) -> P) -> P
hnnP: ~ ~ PPP: Prop
pl: ((P -> False) -> P) -> P
hnnP: ~ ~ P(P -> False) -> Pcontradiction. Qed.P: Prop
pl: ((P -> False) -> P) -> P
hnnP: ~ ~ P
hnP: P -> FalseP
Exercise: Advanced advanced exercise
Come up with more natural statements equivalent to
LEM.Come up with a statement
Ssuch thatLEM -> S, you cannot proveS -> LEM, butSis also not provable without any assumptions in Rocq.Found one? Great! Now find a statement
S'such thatS -> S', you cannot proveS' -> S, butS'is also not provable without any assumptions in Rocq.If you force
theDNEandtheLEMto talk about the same propositionP, the implicationtheDNE -> theLEMdoesn't work any more, why?Can you come up with a hierarchy
S_iof such statements such thatS_0is the strongest and they get subsequently weaker?Can you come up with a hierarchy
S_iof such statements such thatS_0is the weakest and they get subsequently stronger?
🗣️ Talk to us if you want to know more about the solution.
Exercise: Commuting forall and \/ (advanced)
An example of commuting forall and \/.
forall (P : nat -> Prop) (Q : Prop), Q \/ ~ Q -> (forall x : nat, P x \/ Q) -> (forall x : nat, P x) \/ Qforall (P : nat -> Prop) (Q : Prop), Q \/ ~ Q -> (forall x : nat, P x \/ Q) -> (forall x : nat, P x) \/ QP: nat -> Prop
Q: Prop
lemQ: Q \/ ~ Q
h: forall x : nat, P x \/ Q(forall x : nat, P x) \/ QP: nat -> Prop
Q: Prop
hQ: Q
h: forall x : nat, P x \/ Q(forall x : nat, P x) \/ QP: nat -> Prop
Q: Prop
hnQ: ~ Q
h: forall x : nat, P x \/ Q(forall x : nat, P x) \/ QP: nat -> Prop
Q: Prop
hQ: Q
h: forall x : nat, P x \/ Q(forall x : nat, P x) \/ Qassumption.P: nat -> Prop
Q: Prop
hQ: Q
h: forall x : nat, P x \/ QQP: nat -> Prop
Q: Prop
hnQ: ~ Q
h: forall x : nat, P x \/ Q(forall x : nat, P x) \/ QP: nat -> Prop
Q: Prop
hnQ: ~ Q
h: forall x : nat, P x \/ Qforall x : nat, P xP: nat -> Prop
Q: Prop
hnQ: ~ Q
h: forall x : nat, P x \/ Q
x: natP xP: nat -> Prop
Q: Prop
hnQ: ~ Q
x: nat
h: P x \/ QP xP: nat -> Prop
Q: Prop
hnQ: ~ Q
x: nat
hPx: P xP xP: nat -> Prop
Q: Prop
hnQ: ~ Q
x: nat
hQ: QP xassumption.P: nat -> Prop
Q: Prop
hnQ: ~ Q
x: nat
hPx: P xP xP: nat -> Prop
Q: Prop
hnQ: ~ Q
x: nat
hQ: QP xP: nat -> Prop
Q: Prop
hnQ: ~ Q
x: nat
hQ: QFalseassumption. Qed.P: nat -> Prop
Q: Prop
hnQ: ~ Q
x: nat
hQ: QQ
Exercise: More classical reasoning
theLEM -> forall P Q : Prop, (~ Q -> P) -> P \/ QtheLEM -> forall P Q : Prop, (~ Q -> P) -> P \/ Qlem: theLEM
P, Q: Prop
h: ~ Q -> PP \/ QQ: Prop
lem: Q \/ ~ Q
P: Prop
h: ~ Q -> PP \/ QQ: Prop
hQ: Q
P: Prop
h: ~ Q -> PP \/ QQ: Prop
hnQ: ~ Q
P: Prop
h: ~ Q -> PP \/ QQ: Prop
hQ: Q
P: Prop
h: ~ Q -> PP \/ Qassumption.Q: Prop
hQ: Q
P: Prop
h: ~ Q -> PQQ: Prop
hnQ: ~ Q
P: Prop
h: ~ Q -> PP \/ QQ: Prop
hnQ: ~ Q
P: Prop
h: ~ Q -> PPassumption. Qed.Q: Prop
hnQ: ~ Q
P: Prop
h: ~ Q -> P~ Q
For the following do you need LEM for both directions?
theLEM -> forall P Q : Prop, (P -> Q) <-> ~ P \/ QtheLEM -> forall P Q : Prop, (P -> Q) <-> ~ P \/ Qlem: theLEM
P, Q: Prop(P -> Q) <-> ~ P \/ Qlem: theLEM
P, Q: Prop(P -> Q) -> ~ P \/ Qlem: theLEM
P, Q: Prop~ P \/ Q -> P -> Qlem: theLEM
P, Q: Prop(P -> Q) -> ~ P \/ Qlem: theLEM
P, Q: Prop
h: P -> Q~ P \/ QP: Prop
lem: P \/ ~ P
Q: Prop
h: P -> Q~ P \/ QP: Prop
H: P
Q: Prop
h: P -> Q~ P \/ QP: Prop
H: ~ P
Q: Prop
h: P -> Q~ P \/ QP: Prop
H: P
Q: Prop
h: P -> Q~ P \/ QP: Prop
H: P
Q: Prop
h: P -> QQassumption.P: Prop
H: P
Q: Prop
h: P -> QPP: Prop
H: ~ P
Q: Prop
h: P -> Q~ P \/ Qassumption.P: Prop
H: ~ P
Q: Prop
h: P -> Q~ Plem: theLEM
P, Q: Prop~ P \/ Q -> P -> Qlem: theLEM
P, Q: Prop
h: ~ P \/ Q
hP: PQlem: theLEM
P, Q: Prop
hnP: ~ P
hP: PQlem: theLEM
P, Q: Prop
hQ: Q
hP: PQlem: theLEM
P, Q: Prop
hnP: ~ P
hP: PQlem: theLEM
P, Q: Prop
hnP: ~ P
hP: PFalseapply hP.lem: theLEM
P, Q: Prop
hnP: ~ P
hP: PPassumption. Qed.lem: theLEM
P, Q: Prop
hQ: Q
hP: PQtheLEM -> forall P Q : Prop, (~ Q -> ~ P) -> P -> QtheLEM -> forall P Q : Prop, (~ Q -> ~ P) -> P -> Qlem: theLEM
P, Q: Prop
h: ~ Q -> ~ P
hP: PQQ: Prop
lem: Q \/ ~ Q
P: Prop
h: ~ Q -> ~ P
hP: PQQ: Prop
hQ: Q
P: Prop
h: ~ Q -> ~ P
hP: PQQ: Prop
hnQ: ~ Q
P: Prop
h: ~ Q -> ~ P
hP: PQassumption.Q: Prop
hQ: Q
P: Prop
h: ~ Q -> ~ P
hP: PQQ: Prop
hnQ: ~ Q
P: Prop
h: ~ Q -> ~ P
hP: PQQ: Prop
hnQ: ~ Q
P: Prop
h: ~ Q -> ~ P
hP: PFalseQ: Prop
hnQ: ~ Q
P: Prop
h: ~ Q -> ~ P
hP: P~ QQ: Prop
hnQ: ~ Q
P: Prop
h: ~ Q -> ~ P
hP: PP
Notice we get two goals! Because h : ~ Q -> P -> False.
assumption.Q: Prop
hnQ: ~ Q
P: Prop
h: ~ Q -> ~ P
hP: P~ Qassumption. Qed.Q: Prop
hnQ: ~ Q
P: Prop
h: ~ Q -> ~ P
hP: PP
theLEM -> forall P Q : Prop, ((P -> Q) -> Q) -> (Q -> P) -> PtheLEM -> forall P Q : Prop, ((P -> Q) -> Q) -> (Q -> P) -> Plem: theLEM
P, Q: Prop
h: (P -> Q) -> Q
h': Q -> PPlem: theLEM
P, Q: Prop
h: (P -> Q) -> Q
h': Q -> P
lemP: P \/ ~ PPlem: theLEM
P, Q: Prop
h: (P -> Q) -> Q
h': Q -> P
hP: PPlem: theLEM
P, Q: Prop
h: (P -> Q) -> Q
h': Q -> P
hnP: ~ PPassumption.lem: theLEM
P, Q: Prop
h: (P -> Q) -> Q
h': Q -> P
hP: PPlem: theLEM
P, Q: Prop
h: (P -> Q) -> Q
h': Q -> P
hnP: ~ PPlem: theLEM
P, Q: Prop
h: (P -> Q) -> Q
h': Q -> P
hnP: ~ P
lemQ: Q \/ ~ QPlem: theLEM
P, Q: Prop
h: (P -> Q) -> Q
h': Q -> P
hnP: ~ P
hQ: QPlem: theLEM
P, Q: Prop
h: (P -> Q) -> Q
h': Q -> P
hnP: ~ P
hnQ: ~ QPlem: theLEM
P, Q: Prop
h: (P -> Q) -> Q
h': Q -> P
hnP: ~ P
hQ: QPassumption.lem: theLEM
P, Q: Prop
h: (P -> Q) -> Q
h': Q -> P
hnP: ~ P
hQ: QQlem: theLEM
P, Q: Prop
h: (P -> Q) -> Q
h': Q -> P
hnP: ~ P
hnQ: ~ QPlem: theLEM
P, Q: Prop
h: (P -> Q) -> Q
h': Q -> P
hnP: ~ P
hnQ: ~ QFalselem: theLEM
P, Q: Prop
h: (P -> Q) -> Q
h': Q -> P
hnP: ~ P
hnQ: ~ QQlem: theLEM
P, Q: Prop
h: (P -> Q) -> Q
h': Q -> P
hnP: ~ P
hnQ: ~ QP -> Qlem: theLEM
P, Q: Prop
h: (P -> Q) -> Q
h': Q -> P
hnP: ~ P
hnQ: ~ Q
hP: PQlem: theLEM
P, Q: Prop
h: (P -> Q) -> Q
h': Q -> P
hnP: ~ P
hnQ: ~ Q
hP: PFalseapply hP. Qed.lem: theLEM
P, Q: Prop
h: (P -> Q) -> Q
h': Q -> P
hnP: ~ P
hnQ: ~ Q
hP: PP
Exercise: More natural numbers
forall n m k : nat, k * (n + m) = k * n + k * mforall n m k : nat, k * (n + m) = k * n + k * mn, m, k: natk * (n + m) = k * n + k * mn, m: nat0 * (n + m) = 0 * n + 0 * mn, m, k: nat
ihk: forall n m : nat, k * (n + m) = k * n + k * mS k * (n + m) = S k * n + S k * mn, m: nat0 * (n + m) = 0 * n + 0 * mreflexivity.n, m: nat0 = 0n, m, k: nat
ihk: forall n m : nat, k * (n + m) = k * n + k * mS k * (n + m) = S k * n + S k * mn, m, k: nat
ihk: forall n m : nat, k * (n + m) = k * n + k * mn + m + k * (n + m) = n + k * n + (m + k * m)n, m, k: nat
ihk: forall n m : nat, k * (n + m) = k * n + k * mn + m + (k * n + k * m) = n + k * n + (m + k * m)n, m, k: nat
ihk: forall n m : nat, k * (n + m) = k * n + k * mn + m + k * n + k * m = n + k * n + (m + k * m)n, m, k: nat
ihk: forall n m : nat, k * (n + m) = k * n + k * mn + k * n + (m + k * m) = n + m + k * n + k * mn, m, k: nat
ihk: forall n m : nat, k * (n + m) = k * n + k * mn + k * n + m + k * m = n + m + k * n + k * mn, m, k: nat
ihk: forall n m : nat, k * (n + m) = k * n + k * mn + k * n + m = n + m + k * nn, m, k: nat
ihk: forall n m : nat, k * (n + m) = k * n + k * mn + m + k * n = n + k * n + mn, m, k: nat
ihk: forall n m : nat, k * (n + m) = k * n + k * mk * n + (n + m) = n + k * n + mn, m, k: nat
ihk: forall n m : nat, k * (n + m) = k * n + k * mk * n + n + m = n + k * n + mn, m, k: nat
ihk: forall n m : nat, k * (n + m) = k * n + k * mk * n + n = n + k * nreflexivity. Qed.n, m, k: nat
ihk: forall n m : nat, k * (n + m) = k * n + k * mn + k * n = n + k * n
If you thought this kind of proof is extremely annoying, rest assured, most would agree and in practice you don't have to do them by hand. We torture you so you understand better how things work.
In practice Rocq users will use the lia tactic to solve a lot of integer
arithmetic problems.
From Stdlib Require Import Lia.forall n m k : nat, k * (n + m) = k * n + k * mlia. Qed.forall n m k : nat, k * (n + m) = k * n + k * m
See? Much better. 😊
Exercise: Defining addition
As always, when you see REPLACE_ME, replace it with the relevant
value. Again try to solve the exercises without looking at the live coding
file. Even if it seems easy when you see us doing it, it might not be so easy
to do on your own, so try to do it!
Exercises all start with an "Exercise" heading. When it is written before a lemma, just prove it. :)
Module define_nat.Inductive types can be defined using the Inductive keyword
Inductive nat := | O : nat | S : nat -> nat.
Define addition.
Fixpoint add (n m : nat) {struct n} : nat := match n with | O => m | S n => S (add n m) end.
Exercise: Subtraction
Define subtraction on natural numbers, truncating at 0.
In other words, when n < m then sub n m = 0.
Fixpoint sub (n m : nat) : nat := match n, m with | O, _ => O | S n', O => n | S n', S m' => sub n' m' end.
Exercise: Addition with zero
Prove the following lemma.
You will replace Admitted with Qed once it is done.
What Admitted does should be obvious: it admits a lemma without proof or
with a partial proof, it can be used in subsequent proofs as if it were
proven.
forall n : nat, add n O = nforall n : nat, add n O = nn: natadd n O = nadd O O = On: nat
ih: add n O = nadd (S n) O = S nreflexivity.add O O = On: nat
ih: add n O = nadd (S n) O = S nn: nat
ih: add n O = nS (add n O) = S nreflexivity. Qed.n: nat
ih: add n O = nS n = S n
Exercise: Addition with successor
forall n m : nat, add n (S m) = S (add n m)forall n m : nat, add n (S m) = S (add n m)n, m: natadd n (S m) = S (add n m)m: natadd O (S m) = S (add O m)n, m: nat
ih: add n (S m) = S (add n m)add (S n) (S m) = S (add (S n) m)reflexivity.m: natadd O (S m) = S (add O m)n, m: nat
ih: add n (S m) = S (add n m)add (S n) (S m) = S (add (S n) m)n, m: nat
ih: add n (S m) = S (add n m)S (add n (S m)) = S (S (add n m))reflexivity. Qed.n, m: nat
ih: add n (S m) = S (add n m)S (S (add n m)) = S (S (add n m))
Exercise: Addition and subtraction
With the following commands we declare notations for add and sub.
Infix "+" := add. Infix "-" := sub.forall n m : nat, n + m - m = nforall n m : nat, n + m - m = nn, m: natn + m - m = nn: natn + O - O = nn, m: nat
ih: n + m - m = nn + S m - S m = nn: natn + O - O = nn: natn - O = nall: reflexivity.O - O = On: natS n - O = S nn, m: nat
ih: n + m - m = nn + S m - S m = nn, m: nat
ih: n + m - m = nS (n + m) - S m = nassumption. Qed.n, m: nat
ih: n + m - m = nn + m - m = n
Note the proof can look nicer if we also prove n - O = n.
forall n : nat, n - O = nforall n : nat, n - O = nn: natn - O = nall: reflexivity. Qed.O - O = On: natS n - O = S nforall n m : nat, n + m - m = nforall n m : nat, n + m - m = nn, m: natn + m - m = nn: natn + O - O = nn, m: nat
ih: n + m - m = nn + S m - S m = nn: natn + O - O = napply sub_O.n: natn - O = nn, m: nat
ih: n + m - m = nn + S m - S m = nn, m: nat
ih: n + m - m = nS (n + m) - S m = nassumption. Qed. End define_nat.n, m: nat
ih: n + m - m = nn + m - m = n
Exercise: Equality of natural numbers
Define a Boolean predicate deciding equality of natural numbers.
Fixpoint eq_nat (x y : nat) : bool :=
match x, y with
| 0, 0 => true
| 0, S _ => false
| S _, 0 => false
| S x', S y' => eq_nat x' y'
end.Exercise: Specification of equality
forall n m : nat, eq_nat n m = true <-> n = mforall n m : nat, eq_nat n m = true <-> n = mn, m: nateq_nat n m = true <-> n = mm: nateq_nat 0 m = true <-> 0 = mn, m: nat
ih: forall m : nat, eq_nat n m = true <-> n = meq_nat (S n) m = true <-> S n = mm: nateq_nat 0 m = true <-> 0 = meq_nat 0 0 = true <-> 0 = 0m: nateq_nat 0 (S m) = true <-> 0 = S meq_nat 0 0 = true <-> 0 = 0true = true <-> 0 = 0all: reflexivity.true = true -> 0 = 00 = 0 -> true = truem: nateq_nat 0 (S m) = true <-> 0 = S mm: natfalse = true <-> 0 = S mall: discriminate.m: natfalse = true -> 0 = S mm: nat0 = S m -> false = truen, m: nat
ih: forall m : nat, eq_nat n m = true <-> n = meq_nat (S n) m = true <-> S n = mn: nat
ih: forall m : nat, eq_nat n m = true <-> n = meq_nat (S n) 0 = true <-> S n = 0n, m: nat
ih: forall m : nat, eq_nat n m = true <-> n = meq_nat (S n) (S m) = true <-> S n = S mn: nat
ih: forall m : nat, eq_nat n m = true <-> n = meq_nat (S n) 0 = true <-> S n = 0n: nat
ih: forall m : nat, eq_nat n m = true <-> n = mfalse = true <-> S n = 0all: discriminate.n: nat
ih: forall m : nat, eq_nat n m = true <-> n = mfalse = true -> S n = 0n: nat
ih: forall m : nat, eq_nat n m = true <-> n = mS n = 0 -> false = truen, m: nat
ih: forall m : nat, eq_nat n m = true <-> n = meq_nat (S n) (S m) = true <-> S n = S mn, m: nat
ih: forall m : nat, eq_nat n m = true <-> n = meq_nat n m = true <-> S n = S mn, m: nat
ih: forall m : nat, eq_nat n m = true <-> n = meq_nat n m = true -> S n = S mn, m: nat
ih: forall m : nat, eq_nat n m = true <-> n = mS n = S m -> eq_nat n m = truen, m: nat
ih: forall m : nat, eq_nat n m = true <-> n = meq_nat n m = true -> S n = S mn, m: nat
ih: forall m : nat, eq_nat n m = true <-> n = m
h: eq_nat n m = trueS n = S mn, m: nat
ih: forall m : nat, eq_nat n m = true <-> n = m
h: eq_nat n m = truen = massumption.n, m: nat
ih: forall m : nat, eq_nat n m = true <-> n = m
h: eq_nat n m = trueeq_nat n m = truen, m: nat
ih: forall m : nat, eq_nat n m = true <-> n = mS n = S m -> eq_nat n m = truen, m: nat
ih: forall m : nat, eq_nat n m = true <-> n = m
h: S n = S meq_nat n m = truen, m: nat
ih: forall m : nat, eq_nat n m = true <-> n = m
h: S n = S mn = mreflexivity. Qed.n, m: nat
ih: forall m : nat, eq_nat n m = true <-> n = m
h: S n = S m
H0: n = mm = m
Exercise: Currying
Definition cur {X Y Z} (f : X * Y -> Z) : X -> Y -> Z :=
fun x y => f (x, y).Exercise: Uncurrying
Definition car {X Y Z} (f : X -> Y -> Z) : X * Y -> Z :=
fun p =>
match p with
| (x, y) => f x y
end.Note, we can take a shortcut because there is only one constructor so we have a so-called "irrefutable pattern".
Definition car' {X Y Z} (f : X -> Y -> Z) : X * Y -> Z :=
fun '(x,y) => f x y.We could also use fst and snd.
Definition car'' {X Y Z} (f : X -> Y -> Z) : X * Y -> Z :=
fun p => f (fst p) (snd p).Exercise: Uncurrying after currying
forall (X Y Z : Type) (f : X * Y -> Z) (p : X * Y), car (cur f) p = f pforall (X Y Z : Type) (f : X * Y -> Z) (p : X * Y), car (cur f) p = f pX, Y, Z: Type
f: X * Y -> Z
p: X * Ycar (cur f) p = f preflexivity. Qed.X, Y, Z: Type
f: X * Y -> Z
x: X
y: Ycar (cur f) (x, y) = f (x, y)
Exercise: Currying after uncurrying
forall (X Y Z : Type) (f : X -> Y -> Z) (x : X) (y : Y), cur (car f) x y = f x yforall (X Y Z : Type) (f : X -> Y -> Z) (x : X) (y : Y), cur (car f) x y = f x y
No intros needed, reflexivity does it for us.
reflexivity. Qed.
Exercise: Swap
Definition swap {X Y} (p : X * Y) : Y * X :=Irrefutable patterns also work with let.
let '(x, y) := p in
(y, x).Exercise: Swap is involutive
forall (X Y : Type) (p : X * Y), swap (swap p) = pforall (X Y : Type) (p : X * Y), swap (swap p) = pX, Y: Type
p: X * Yswap (swap p) = preflexivity. Qed.X, Y: Type
x: X
y: Yswap (swap (x, y)) = (x, y)
Exercise: True is not false
Prove true <> false without the tactics inversion or discriminate.
true <> falsetrue <> falsee: true = falseFalsee: true = falseif true then False else Trueconstructor. Qed.e: true = falseTrue