How would I prove that b = c if (andb b c = orb b c) in coq?

Question

I'm new to coq and I'm trying to prove this...

Theorem andb_eq_orb :
  forall (b c : bool),
  (andb b c = orb b c) -> (b = c).

Here is my proof, but I get stuck when I get to the goal (false = true -> false = true).

Proof.
intros b c.
induction c.
destruct b.
reflexivity.
simpl.
reflexivity.

I'm not sure how I would rewrite that expression so I can use reflexivity. But even if I do that, I'm not sure it will lead to the proof.

I was able to solve the prove if I started with the hypothesis b = c though. Namely...

Theorem andb_eq_orb_rev :
  forall (b c : bool),
  (b = c) -> (andb b c = orb b c).
Proof.
intros.
simpl.
rewrite H.
destruct c.
reflexivity.
reflexivity.
Qed.

But I can't figure out how to solve if I start with the hypothesis that has boolean functions.

Answer 1

You don't need induction, since bool is not a recursive data structure. Just go through the different cases for the values of b and c. Use destruct to do that. In two cases the hypothesis H will be of the type true = false, and you can finish the proof with inversion H. In the other two cases, the goal will be of the type true = true and it can be solved with reflexivity.

Theorem andb_eq_orb : forall b c, andb b c = orb b c -> b = c.
Proof. destruct b,c;  intro H; inversion H; reflexivity. Qed.

Answer 2

You'll want to use the intro tactic. This will move false = true into your proof context as an assumption which you can then use to rewrite.

Answer 3

This might not be the most efficient way to do it.

At the step induction c. (where it's stuck):

______________________________________(1/2)
b && true = b || true -> b = true
______________________________________(2/2)
b && false = b || false -> b = false

You can use rewrite and basic theorems in [bool][1] to simplify terms such as b && true to b, and b || true to true.

This can reduce it to two "trivial" sub goals:

b : bool
______________________________________(1/2)
b = true -> b = true
______________________________________(2/2)
false = b -> b = false

This is almost trivial proof using assumption, except it is one symmetry away. You can try if symmetry will make them match using:

try (symmetry;assumption); try assumption.

(Someone who really knows Coq may enlighten me how to try this more succinctly)

Putting it together:

Require Import Bool.
Theorem andb_eq_orb : forall b c, andb b c = orb b c -> b = c.
Proof. 
destruct c; 

try (rewrite andb_true_r);
try (rewrite orb_true_r);
try (rewrite andb_false_r);
try (rewrite orb_false_r);
intro H;
try (symmetry;assumption); try assumption.
Qed.

A second approach is to brute-force it and using the "Truth table" method. This means you can break down all variables to their truth values, and simplify: destruct b, c; simpl.. This again gives four trivial implications, up to one symmetry to try:

4 subgoal
______________________________________(1/4)
true = true -> true = true
______________________________________(2/4)
false = true -> true = false
______________________________________(3/4)
false = true -> false = true
______________________________________(4/4)
false = false -> false = false

Putting it together:

Theorem andb_eq_orb1 : forall b c, andb b c = orb b c -> b = c.
Proof. 
destruct b, c; simpl; intro; try (symmetry;assumption); try assumption.
Qed.

The first approach is more troublesome but it does not involve enumerating all truth table rows (I think).