Coq: Как да докажем a=b -› nat_compare a b = Eq.?

В опит да разбера какво представлява Coq, се озовах в ситуация, в която по същество трябва да докажа, че a=b -> nat_compare a b = Eq.

Мога да започна удобно, като направя:

Coq < Theorem foo: forall (a:nat) (b:nat), a=b->nat_compare a b=Eq.
1 subgoal

============================
forall a b : nat, a = b -> nat_compare a b = Eq

foo < intros. rewrite H. destruct b.

което ми дава:

2 subgoals
a : nat
H : a = 0
============================
nat_compare 0 0 = Eq

subgoal 2 is:
nat_compare (S b) (S b) = Eq

Първият е тривиален:

foo < simpl. reflexivity.

Но следващата цел ме спъва:

1 subgoal

a : nat
b : nat
H : a = S b
============================
nat_compare (S b) (S b) = Eq

аз мога да направя

foo < rewrite <- H.

което дава:

1 subgoal

a : nat
b : nat
H : a = S b
============================
nat_compare a a = Eq

(Мога също да стигна до тази точна точка до simpl, което изглежда има повече смисъл.)

Сега, с писалка и хартия, просто бих твърдял, че ето моето доказателство чрез индукция.

Подхождам ли изобщо към това по правилен начин? Къде най-добре мога да науча как да правя това правилно?


theorem-proving coq
person aleator    schedule 30.10.2013    source източник
comment

TextBlock може да има повече от текст като съдържание, това може да са други контроли. Във вашата нова версия съдържанието на TextBlock е System.Windows.Documents.Run със своя Text свойството е зададено на ^.

Това вероятно е направено от Expression Blend, тъй като ^ може да се счита за контролен знак в някои случаи. Чрез поставянето на текста вътре в Run се премахва всяка неяснота, че ^ е текст, а не някакъв контролен знак. Когато работите със сложен дизайнер, винаги е най-добре да премахнете възможно най-много неясноти, така че Blend вероятно просто го е направил, за да улесни собствения си механизъм за анализиране.

  -  person aleator    schedule 30.10.2013

Отговори (1)


arrow_upward
2
arrow_downward

Успях да докажа това с

Theorem triv : forall a b, a = b -> nat_compare a b = Eq.
  intros; subst; induction b; auto.
Qed.

Номерът тук е да оставите индуктивната хипотеза наоколо. destruct е по-слаба форма на induction, която не ви дава индуктивна хипотеза, от която се нуждаете за това доказателство.

person Daniel Gratzer    schedule 30.10.2013
comment
Благодаря! Опитах induction по-рано, но това се провали, когато използвах rewrite H вместо subst. Ако допълнително clear хипотезата и препратката към a, induction работи с rewrite. Защо първо трябва да изчистя хипотезата? - person aleator; 30.10.2013