Доказательство, включающее развертывание двух рекурсивных функций в COQ

Question

Я начал изучать Coq и пытаюсь доказать что-то, что кажется довольно простым: если список содержит x, то число экземпляров x в этом списке будет> 0.

Я определил функции contains и count следующим образом:

Fixpoint contains (n: nat) (l: list nat) : Prop :=
  match l with
  | nil => False
  | h :: t => if beq_nat h n then True else contains n t
  end.

Fixpoint count (n acc: nat) (l: list nat) : nat :=
  match l with
  | nil => acc
  | h :: t => if beq_nat h n then count n (acc + 1) t else count n acc t
  end.

Я пытаюсь доказать:

Lemma contains_count_ge1 : forall (n: nat) (l: list nat), contains n l -> (count n 0 l > 0).

Я понимаю, что доказательство будет заключаться в развертывании определений количества и содержимого, но я бы хотел сказать, что "список не может быть нулевым, поскольку параметр содержит значение true, поэтому должен присутствовать элемент x в l такой, что beq_nat h x это правда ", и я немного поиграл, но не могу понять, как использовать тактику, чтобы сделать это. Любое руководство будет с благодарностью.

Answer 1

Ну, вы задаете много вопросов о базовом Coq, помимо того, что ИМО можно решить здесь. Для этой конкретной проблемы я бы поступил следующим образом (на самом деле я бы использовал уже предоставленные леммы в MathComp):

From Coq Require Import PeanoNat Bool List.

Fixpoint contains (n: nat) (l: list nat) : bool :=
  match l with
  | nil    => false
  | h :: t => if Nat.eqb h n then true else contains n t
  end.

Fixpoint count (n : nat) (l: list nat) : nat :=
  match l with
  | nil => 0
  | h :: t => if Nat.eqb h n then S (count n t) else count n t
  end.

Lemma contains_count_ge1 n l : contains n l = true -> count n l > 0.
Proof.
induction l as [|x l IHl]; simpl; [now congruence|].
now destruct (Nat.eqb_spec x n); auto with arith.
Qed.

Мое "стандартное" решение:

Lemma test n (l : list nat) : n \in l -> 0 < count_mem n l.
Proof. by rewrite lt0n => /count_memPn/eqP. Qed.

и разные определения count а также contains это может оказаться полезным:

Fixpoint contains (n: nat) (l: list nat) : bool :=
  match l with
  | nil    => false
  | h :: t => Nat.eqb h n || contains n t
  end.

Fixpoint count (n : nat) (l: list nat) : nat :=
  match l with
  | nil    => 0
  | h :: t => Nat.b2n (Nat.eqb h n) + (count n t)
  end.

Answer 2

ejgallego уже дал отличное решение вашей проблемы в своем ответе. Я все еще хотел бы выделить важный момент, который он пропустил: в Coq вы всегда должны спорить с первыми принципами и быть очень педантичными и точными в своих доказательствах.

Вы утверждали, что доказательство должно быть следующим:

Список не может быть nil, как contains верно, поэтому должен быть элемент x в l такой, что beq_nat h x является true,

Хотя это имеет интуитивное значение для людей, оно не достаточно точно для понимания Coq. Проблема, как показывает ответ ejgallego, заключается в том, что ваши неформальные рассуждения скрывают использование индукции. Действительно, полезно попытаться расширить ваш аргумент более подробно, даже прежде чем перевести его в тактику. Мы могли бы поступить так, например:

Давайте докажем, что для каждого n : nat а также ns : list nat, contains n ns подразумевает count n 0 ns > 0, Действуем по индукции в списке ns, Если ns = nilопределение contains подразумевает, что False трюмы; противоречие. Таким образом, мы остались с делом ns = n' :: ns'где можно использовать следующую индукционную гипотезу: contains n ns' -> count n 0 ns' > 0, Есть два подслуча для рассмотрения: beq_nat n n' является true или нет.

• Если beq_nat n n' является trueпо определению countмы видим, что мы просто должны показать, что count n (0 + 1) ns' > 0, Обратите внимание, что здесь нет прямого способа продолжить. Это потому что ты написал count хвост-рекурсивно, используя аккумулятор. Хотя это вполне разумно в функциональном программировании, оно может придать count труднее. В этом случае нам понадобится следующая вспомогательная лемма, также доказанная по индукции: forall n acc ns, count n acc ns = acc + count n 0 ns, Я дам вам понять, как это доказать. Но если предположить, что мы это уже установили, цель сводится к тому, чтобы показать, что 1 + count n 0 ns' > 0, Это верно по простой арифметике. (Существует еще более простой способ, который не требует вспомогательной леммы, но для этого потребуется немного обобщить утверждение, которое вы доказываете.)

• Если beq_nat n n' является falseпо определениям contains а также countнам нужно показать, что contains n ns' подразумевает count n 0 ns' > 0, Это именно то, что дает нам индукционная гипотеза, и мы закончили.

Здесь есть два урока. Во-первых, формальные доказательства часто требуют перевода вашей интуиции в формальные термины, понятные системе. Мы интуитивно знаем, что значит иметь какой-то элемент внутри списка. Но если бы мы объяснили, что это значит более формально, мы бы прибегли к некоторому рекурсивному обходу списка, который, вероятно, оказался бы само определением count что вы написали в Coq. И чтобы рассуждать о рекурсии, нам нужна индукция. Второй урок заключается в том, что то, как вы определяете вещи в Coq, имеет важные последствия для написанных вами доказательств. Решение Эйгальего не требовало каких-либо вспомогательных лемм, кроме стандартных библиотек, именно потому, что его определение count не был хвост-рекурсивным.