Coqでリストのreverse関数を書いてください。2回reverseすると元に戻る性質を証明してください。
- User
Coqでリストのreverse関数を書いてください。2回reverseすると元に戻る性質を証明してください。
Assistant
Coqでリストのreverse関数と、2回reverseすると元に戻る性質の証明を書きます。
Require Import List. Import ListNotations. (* リストのreverse関数を定義 *) Fixpoint reverse {A : Type} (l : list A) : list A := match l with | [] => [] | x :: xs => reverse xs ++ [x] end. (* 補助定理: reverseとappendの関係 *) Lemma reverse_app : forall {A : Type} (l1 l2 : list A), reverse (l1 ++ l2) = reverse l2 ++ reverse l1. Proof. intros A l1 l2. induction l1 as [| x xs IH]. - simpl. rewrite app_nil_r. reflexivity. - simpl. rewrite IH. rewrite app_assoc. reflexivity. Qed. (* 補助定理: 単一要素のリストのreverse *) Lemma reverse_singleton : forall {A : Type} (x : A), reverse [x] = [x]. Proof. intros A x. simpl. reflexivity. Qed. (* メインの定理: 2回reverseすると元に戻る *) Theorem reverse_involutive : forall {A : Type} (l : list A), reverse (reverse l) = l. Proof. intros A l. induction l as [| x xs IH]. - (* 空リストの場合 *) simpl. reflexivity. - (* x :: xs の場合 *) simpl. rewrite reverse_app. rewrite reverse_singleton. rewrite IH. reflexivity. Qed.この証明では以下の手順を踏んでいます:
-
reverse関数の定義: 再帰的に定義し、各要素を末尾に追加していく方式です。
-
補助定理の証明:
reverse_app: リストの連結とreverseの関係を示しますreverse_singleton: 単一要素リストのreverseは自分自身であることを示します
-
メインの定理: リストに対する帰納法を使って証明します
- 空リストの場合は自明
x :: xsの場合は、補助定理と帰納法の仮定を使って証明
この証明により、任意の型のリストに対して
reverse (reverse l) = lが成り立つことが形式的に証明されます。-
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.
Identical first prompt
claude-sonnet-4-20250514Compare side by side →
qwen3-30b-a3bCompare side by side →
command-a-03-2025Compare side by side →
gemma-3-27b-itCompare side by side →
gemini-2.5-flash-preview-04-17Compare side by side →
- o3-2025-04-16Compare side by side →
gemma-3-27b-itCompare side by side →
gemini-2.5-pro-preview-05-06Compare side by side →
claude-3-7-sonnet-20250219-thinking-32kCompare side by side →
llama-4-maverick-17b-128e-instructCompare side by side →
claude-opus-4-20250514Compare side by side →