Доказательство if then else в Coq

Я новичок в Coq и пытаюсь доказать кое-что довольно простое

Лемма eq_if_eq: forall a1 a2, (если beq_nat a1 a2, то a2, иначе a1) = a1.

Я боролся с решением, опубликованным ниже, но я думаю, что должен быть способ получше. В идеале, я хотел бы чисто регистрировать beq_nat a1 a2, помещая значения case в список гипотез. Существует ли тактика t, при которой использование t (beq_nat a1 a2) дает два подслучая, один - где beq_nat a1 a2 = true, а другой - где beq_nat a1 a2 = false? Очевидно, induction очень близко, но теряет свою историю.

Вот доказательство, с которым я боролся:

Proof.
Hint Resolve beq_nat_refl.
Hint Resolve beq_nat_eq.
Hint Resolve beq_nat_true.
Hint Resolve beq_nat_false.
intros.
compare (beq_nat a1 a2) true.
intros. assert (a1 = a2). auto. 
replace (beq_nat a1 a2) with true. auto.
intros. assert (a1 <> a2). apply beq_nat_false.
apply not_true_is_false. auto.
assert (beq_nat a1 a2 = false). apply not_true_is_false. auto.
replace (beq_nat a1 a2) with false. auto.
Qed.

coq
person nitromaster101    schedule 15.05.2013    source источник

Ответы (3)


arrow_upward
3
arrow_downward

Обычно для такого рода вещей я использую eqn вариант destruct. Это выглядело бы так:

destruct (beq_nat a1 a2) as []_eqn. (* Coq <= 8.3 *)

destruct (beq_nat a1 a2) as []eqn:? (* Coq >= 8.4 *)

Это добавит равенство в качестве гипотезы. В варианте 8.4 вы можете заменить вопросительный знак названием гипотезы.

person Ptival    schedule 15.05.2013

arrow_upward
2
arrow_downward

Тактика, которая делает то, о чем вы просите, case_eq. Следующий сценарий доказывает лемму в 8.4pl3:

intros.
case_eq (beq_nat a1 a2).
intuition.
apply beq_nat_true_iff in H.
intuition.
intuition.
person Atsby    schedule 18.03.2015

arrow_upward
0
arrow_downward

Оказалось, что простая remember тактика была всем, что мне было нужно. Что-то вроде remember (beq_nat a1 a2) as e; induction e; etc.

person nitromaster101    schedule 03.06.2013