我想在Coq中证明这个引理:
a : Type
b : Type
f : a -> b
g : a -> b
h : a -> b
______________________________________(1/1)
(forall x : a, f x = g x) ->
(forall x : a, g x = h x) -> forall x : a, f x = h x
我知道Coq.Relations.Relation_Definitions定义了关系的传递性:
Definition transitive : Prop := forall x y z:
我如何在coq中写一个类似于这个开关状态的开关状态(在铁锈中)?特别是,我很好奇如何合并coq中的分支以产生相同的输出,并通过一些默认实现耗尽其余的分支。
type Voltages = u32; // in coq is similar to Definition Voltages := R.
type Timestamp = u32; // in coq is similar to Definition Timestamp := R.
const TD: Timestamp = 2; // dummy value cuz rust, in coq would be Variable TD
我正在从软件基金会提供的资源中学习coq。在证明鸽子洞原理的过程中,我试图定义一个函数,从列表中提取子序列,这样里面就没有重复的元素。以下是我的定义:
Fixpoint norepeat_subseq {X : Type} (l : list X) : list X :=
match l with
| [] => []
| n :: t => match (In n t) with
| False => n :: norepeat_subseq t
| _ => norepeat_subseq t
我正在使用opam 安装coq,并收到了错误消息。
`No solution for coq: The following dependencies couldn't be met:
- coq → ocaml < 4.10
base of this switch (use '--unlock-base' to force)
我继续使用以下命令切换到ocaml 4.05.0
opam switch create with-coq 4.05.0
并且可以成功地安装Coq,但是我更愿意使用最新版本的ocaml。这是Coq
考虑以下大小列表的类型定义:
Inductive listn: nat -> Type -> Type :=
| nil: forall {A: Set}, listn 0 A
| cons: forall {n: nat} {A: Set}, A -> listn n A -> listn (S n) A.
这本质上是Idris中的类型。
我试图为init定义listn函数,它删除了最后一个元素。
我尝试的实现实际上与Idris中init的定义完全相同。这是在伊德里斯:
init : Vect (S len) elem -> Vect len elem
init
我有一个函数的目标,它的主体我想重写,但是一些函数参数阻碍了重写。我用身份函数重新创造了这种情况。
如果函数是Defined,那么它可以工作,但是当函数是一个参数,并且我有一个公理来说明如何重写时,我无法重写。
我只能假设函数的可扩展性才能让它工作。是否有可能在不假设功能扩展的情况下重写?
Axiom functional_extensionality: forall {A B} (f g:A->B) , (forall x, f x = g x) -> f = g.
Variables A B : Type.
Variable f : A -> B.
Definitio
我有以下问题,请看代码。
(* Suppose we have type A *)
Variable A: Type.
(* Also we have a function that returns the type (option A) *)
Definition f_opt x: option A := ...
(* Then, I can prove that this function always returns something: *)
Theorem always_some: forall x, exists y, f_opt x = Some y.
我正在尝试开发一种基于尽快防止错误输入的编程风格。例如,而不是以下关于自然数的前置函数的合理定义:
Definition pred1 n :=
match n with
| O => None
| S n => Some n
end.
我想把它写成:
Theorem nope n (p : n = O) (q : n <> O) : False.
contradict q.
exact p.
Qed.
Definition pred2 n (q : n <> O) :=
match n with
| S n
当我在下面运行Coq脚本时(对原始脚本的简化):
Inductive w (g: nat): nat -> Prop:=
| z: w g 0.
Lemma x:
forall (i j: nat), w i j -> (forall k: nat, k <= k).
Proof.
Admitted.
Lemma y:
forall (m n: nat),
w m n -> w m n.
Proof.
intros m n H.
apply x in H.
在最后一行中,我得到以下错误消息:
错误:找不到变量k的实例。
有人能向我解释
我试图检查类型检查器如何处理以下函数,但无法理解类型检查器在第二个(嵌套的) match子句中是如何工作的:
Definition plus_O_2 :=
(fix F (m : mynat) : m == plus m O :=
match m as m0 with
| O as m2 => myeq_refl O : m2 == plus m2 O
| S x as m2 => ((match F x in (m0 == m1) return (S m0 == S m1) with
| myeq_
在我的Coq研究中经常会出现这样的证明状态:
1 goal
n : nat
IHn : fib_v1 n <= fib_v1 (S n)
______________________________________(1/1)
fib_v1 (S n) <= fib_v1 (S (S n))
Coq抱怨说它不能把n和S n统一起来,S n和S (S n)不能统一。在纸和笔中,很容易在目标中引入象征性的操作,比如t = S n,甚至n = S n,那么归纳假设就会变得适用。在Coq看来不是这样的。在这样的情况下,一个人是如何前进的?
我对Coq类型系统在下面h的定义中证明术语的匹配部分的行为感到困惑:
Set Implicit Arguments.
Definition h := fun (a b : nat) (e : a = b) =>
(fun (x y : nat)(HC : b = y)(H : x = y) =>
(match H in (_ = y0) return (b = y0 -> b = x) with
| @eq_refl _ _ => fun HC0 : b = x => HC0
end HC)) a b (eq_refl b) e.
Check h告诉我们,整个类型
Coq正在使用类似于OCaml的模块系统。在OCaml中,我们可以应用像Module_A.Module_B.Func这样的函数,并使用Module_A.Module_B来查找到Func的路径。
然而,我不能在Coq中做类似的事情。例如,如果我只运行Print Coq.Arith.Minus.minus_n_O.,Coq报告Coq.Arith.Minus.minus_n_O is not a defined object.
我必须先加载库,然后才能打印对象。在下面的例子中,它是成功的。
From Coq Require Export Arith.Minus.
Print Coq.Arith.Mi
我目前正在使用最新的Kami的repo文件,但是当我尝试运行Makefile时,还没能克服一个问题。我发现另一个帖子有类似的请求at this link,但没有回应。我在WSL Ubuntu 20.04操作系统上使用Coq proof assistant v8.11.0和OCaml v4.08.1 错误信息如下所示 Warning: no common logical root
Warning: in such case INSTALLDEFAULTROOT must be defined
Warning: the install-doc target is going to install
具有简单归纳定义的A类型
Inductive A: Set := mkA : nat-> A.
(*get ID of A*)
Function getId (a: A) : nat := match a with mkA n => n end.
以及一个亚型定义:
(* filter that test ID of *A* is 0 *)
Function filter (a: A) : bool := if (beq_nat (getId a) 0) then true else false.
(* cast bool to Prop *)
Definition Istr
我正在尝试计算Coq中的v元素在natlist/bag中出现的#。我试过:
Fixpoint count (v:nat) (s:bag) : nat :=
match s with
| nil => 0
| h :: tl => match h with
| v => 1 + (count v tl)
end
end.
然而,我的证据行不通:
Example test_count1: count 1 [1;2;3;1;4;1] = 3.
Proof. simpl. refle
我使用了从Coq到OCaml的提取,其中有Z、N、positive类型。
我不需要在int of OCaml中提取它。
那么提取后的类型是:
type positive =
| Coq_xI of positive
| Coq_xO of positive
| Coq_xH
type coq_N =
| N0
| Npos of positive
type coq_Z =
| Z0
| Zpos of positive
| Zneg of positive
我在OCaml中有一个程序,其中一些函数使用OCaml类型的string。
在我的OCaml程序中,我需要编写一些转换类型的函数:st
在证明了命题和谓词演算中的数十个引理(有些比另一些更具有挑战性,但通常仍然可以在intro-apply-destruct自动驾驶仪上证明)之后,我碰到了一个起始w/ ~forall的引理,并立即陷入困境。显然,我对Coq缺乏理解和知识。所以,我要求用一种低级的Coq技术来证明一般形式的语句。
~forall A [B].., C -> D.
exists A [B].., ~(C -> D).
总之,我希望有一个通用的Coq配方来建立和激发反例。(对上述函数进行量化的主要原因是,它是Coq中的(或)原始连接性。)如果你想要例子,我建议你。
~forall P Q: Prop,
我想用coq编写一个安全的zip函数,它接受参数长度相等作为参数。
Fixpoint zip {b a:Type} (proof : length l1 = length l2) (l1 : list a) (l2 : list b) : list (a * b) :=
match l1,l2 with
| nil,nil => nil
| cons a a',cons b b' => cons (a,b) (zip a' b')
| _,_ => (* never reached *)
end.
解决这类问题的一般方法是什
我想扩展Coq‘’Art中的练习6.10,增加一个定理,对于不是一月的所有月份,is_January将等于false。
我对月份的定义如下:
Inductive month : Set :=
| January : month
| February : month
| March : month
| April : month
| May : month
| June : month
| July : month
| August : month
| September : month
| October : month
|
我试图用Coq证明一个简单的引理,但我在排除一个不可行的情况时遇到了一些麻烦。下面是我的引理: Theorem helper : forall (a b : bool),
((negb a) = (negb b)) -> (a = b).
Proof.
intros a b.
intros H.
destruct a.
- destruct b.
+ reflexivity.
+ (** this case is trivially true *) 相关子目标是微不足道的,因为假设H是假的。我怎么把这个告诉Coq? 1 subgoal
H : neg
我想证明在Coq中减法不通勤,但我被卡住了。我相信我想在Coq里证明的声明是写在forall a b : nat, a <> b -> a - b <> b - a上的
到目前为止,这是我的证据。
Theorem subtraction_does_not_commute :
forall a b : nat, a <> b -> a - b <> b - a.
Proof.
intros a b C.
unfold not; intro H.
apply C.
我想我可以用C : a <> b来反驳a =
我想要定义一个函数app_1,它将一个n-ary函数f : X ^^ n --> Y转换为一个新的函数f' : (Z -> X) ^^ n --> Y,条件是有一个z : Z要对其所有参数应用一次。例如,
Example ex1 : app_1 plus 2 S pred = 4.
trivial. Qed.
app_1 plus 2能够将一元函数S和pred作为参数,因为它首先将这两个函数应用于2,然后将结果应用于plus。
以下是我对app_1的尝试定义
Fixpoint app_1 {X Y Z : Type} {n : nat}
(f : X ^^ n --
关于如何在Coq中重新排列术语,我有一个一般性的问题。例如,如果我们有一个术语m + p + n + p,人类可以快速地将这些术语重新排列为类似于m + n + p + p (隐式使用plus_comm和plus_assoc)的术语。我们如何在Coq中有效地做到这一点?
举个愚蠢的例子,
Require Import Coq.Arith.Plus.
Require Import Coq.Setoids.Setoid.
Theorem plus_comm_test: forall n m p: nat,
m + p + (n + p) = m + n + 2 * p.
Proof. int
用归纳法证明了Coq中的两个阶乘函数是等价的。
大小写n = 0比较简单,但归纳情况比较复杂。我明白了,如果我能把(visit_fac_v2 n' (n * a))重写成n * (visit_fac_v2 n' a),我就完事了。然而,将这一想法转化为Coq会给我带来麻烦。
如何在Coq中证明这一点呢?
Fixpoint fac_v1 (n : nat) : nat :=
match n with
| 0 => 1
| S n' => n * (fac_v1 n')
end.
Fixpoint visit_fac_v2 (n a
我试图用Coq编写一个计算自然除法的函数,而且我在定义它时遇到了一些困难,因为它不是结构递归。
我的代码是:
Inductive N : Set :=
| O : N
| S : N -> N.
Inductive Bool : Set :=
| True : Bool
| False : Bool.
Fixpoint sum (m :N) (n : N) : N :=
match m with
| O => n
| S x => S ( sum x n)
end.
Notation "m + n" := (sum m n) (a
我正在编写我自己的第一个Coq文件,但是我在导出另一个用户定义的文件(由图书软件基金会定义)时遇到了困难。
问题是我当前的Coq文件有路径Coq/NWA.v,而我想导入的文件有路径Coq/SoftwareFoundations/lf/Rel.v。我尝试了以下语法:
From Coq/SoftwareFoundations/lf Require Import Rel.v
&
From Coq.SoftwareFoundations.lf Require Import Rel.v
&
From ./../SoftwareFoundations/lf Require Import R
我对Coq非常陌生,现在我只能用一个简单的定理来理解Coq的“理由”:
Theorem andb_true_elim2 : forall b c : bool,
andb b c = true -> c = true.
我想证据应该是:
Proof.
intros b c.
destruct c.
- destruct b.
+ reflexivity.
+ reflexivity.
- destruct b.
+ reflexivity.
+ reflexivity.
Qed.
但它失败了,因为:
In envir
我试图用Coq编写以下Agda片段。
open import Data.Fin using (Fin; suc; zero)
open import Data.Nat using (ℕ; suc; zero)
thin : {n : ℕ} -> Fin (suc n) -> Fin n -> Fin (suc n)
thin zero y = suc y
thin (suc x) zero = zero
thin (suc x) (suc y) = suc (thin x y)
我认为这可以直截了当地翻译为:
Inductive Fin : nat