对于软件基础的练习,我想证明以下定理:
Theorem rev_pal {X:Type} : forall (l:list X), l = rev l -> pal l.
pal的定义如下:
Inductive pal {X:Type} : list X -> Prop :=
| pal_nil : pal []
| pal_one : forall x, pal [x]
| pal_rec : forall x l, pal l -> pal (snoc(x:: l) x).
然而,为了实现这一点,我想使用一个使用exists的引理来举例如下:
foral (l l'
用归纳法证明了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
你如何解释归纳谓词?它们是用来干什么的?他们背后的理论是什么?它们只存在于依赖型系统中,还是在其他系统中?它们在某种程度上与GADT有关吗?在Coq中,为什么默认情况下它们是真的?
这是Coq的一个例子:
Inductive even : nat -> Prop :=
| even0 : even 0
| evens : forall p:nat, even p -> even (S (S P))
你将如何使用这个定义?这是一种数据类型还是一个命题?
我是Coq的新手,为了好玩和学习,我在CodeWars上做了一些Katas。 我被他们中的一个卡住了,想听听你的一些想法。 所以,我有: Record iso (A B : Set) : Set :=
bijection {
A_to_B : A -> B;
B_to_A : B -> A;
A_B_A : forall a : A, B_to_A (A_to_B a) = a;
B_A_B : forall b : B, A_to_B (B_to_A b) = b
}.
(* nat_plus_nat : a set having size(nat) more
我想定义一个归纳类型Foo,构造函数接受一些属性作为参数。我希望这些属性依赖于我当前定义的类型的归纳参数。我希望能够使用一些接受Foo类型对象的递归函数bar从这些属性中收集一些数据。但是,我不知道有什么方法可以声明这两个,这样Coq就会接受它们的定义。我希望能够写出这样的代码: Inductive Foo : Set (* or Type *) :=
| Foo1 : forall f : Foo, bar f = 1 -> Foo
| Foo2 : forall f : Foo, bar f = 2 -> Foo
| Foon : nat -> Foo
with ba
我对Coq中归纳定义的关系eq有一个查询。考虑Coq中eq的以下定义:
Inductive eq (A : Type) (x : A) : A -> Prop := eq_refl : x = x
这是一个归纳定义的关系,就像le (<=)。因此,我应该能够对任何这类证据进行案例分析。然而,当我试图证明以下结果时,我无法成功。
Lemma true_num: forall m :nat, forall x y: m=m, x=y.
Proof. intros. destruct x.
(// Error: Abstracting over the terms "m&
我正在尝试使用Omega在Coq中进行证明。我花了很多时间在上面,但什么也没想到。我不得不说,我是Coq的新手,所以我对这种语言并不自在,也没有太多的经验。但我正在努力。
下面是我要证明的代码:
Require Import Arith Omega.
Fixpoint div2 (n : nat) :=
match n with
S (S p) => S (div2 p)
| _ => 0
end.
Fixpoint mod2 (n : nat) :=
match n with
S (S p) => mod2 p
| x => x
end.
char * buf = new char[sizeof(T)];
new (buf) T;
T * t = (T *)buf;
//code...
//here I should destruct *t but as it is argument of template and can be
//instantiated via basic types as well (say int) so such code
/*t->~T();*/
//is incorrect (maybe correct? Strange, but it works on VS 2005 for basic
我在Coq中做了一个练习,试图证明如果一个列表等于它的相反,它是一个回文。下面是我如何定义回文的方法:
Inductive pal {X : Type} : list X -> Prop :=
| emptypal : pal []
| singlpal : forall x, pal [x]
| inducpal : forall x l, pal l -> pal (x :: l ++ [x]).
下面是定理:
Theorem palindrome3 : forall {X : Type} (l : list X),
l = rev l -> pal l.
我刚开始学习Coq,学习形式语义学,我正在学习“软件基础”( Software )一书。目前,我在这一章:。其中,它为简单的命令式语言定义命令。作为练习,我尝试在定义如下的语言中添加一个重复命令:
Inductive ceval : com -> state -> state -> Prop :=
(* ...same as in the book *)
| E_RepeatTrue : forall st st' b c,
[ c, st ] ~> st' ->
beval st' b = true -&g
我是Coq认证系统的初学者(大约4天)。我已经尽力了,但我无法证明以下几点。
forall a b c : nat, S (S (a + b)) = S (S (a + c)) -> b = c.
据我所知,我们需要证明+的双射性,以便我们可以以某种方式使用f(b) = f(c) -> b = c。我该怎么做?
为了给出一个简单的例子,我一直遇到这个问题,假设我想证明forall f : nat -> bool, exists i j, i<>j /\ f i = f j.,显然要做的事情是检查f 0, f 1, f 2,的值并进行相应的处理。但是,如果我简单地说destruct (f 0),Coq不会修改目标,因为f 0不是作为一个子项出现的。因此,对于f 0当前的价值,我没有想要的信息。理想情况下,我希望Coq向上下文中添加一个见证H : f 0 = false,这样我就可以跟踪它。
为了解决这些问题,我所做的就是证明一个辅助引理bool_destruct : forall b
我试图用Coq来处理一些简单的哲学谓词逻辑。例如,假设我想在Coq中表达“如果一个人是人,它是不完美的”这句话。我首先要定义什么是“存在”、“人”和“完美”。自然的方法,似乎是将第一个定义为一个类型,而其他定义为该类型的一元谓词。
Inductive being : Type :=
| b : nat -> being.
Inductive human : being -> Prop :=
| h : forall ( b : being ), human b.
Inductive perfect : being -> Prop :=
| p : forall ( b
我在学校学习Coq,而且我有一个作业要做。我有一个引理要证明:如果一个列表的元素中包含一个零,那么它的元素的乘积是0。我开始我的代码,我被困在一个点上,我不知道如何继续下去。我不知道Coq的所有命令,我做了很多研究,但我不能设法找到我的方法来证明。这是我的代码:需要导入列表ZArith。
Open Scope Z_scope.
Fixpoint contains_zero (l : list Z) :=
match l with
nil => false
| a::tl => if Zeq_bool a 0 then true else contains_zero
所以我一直在学习使用Coq,到目前为止,我一直在使用我自己定义的自然类型,所以我不是100%清楚使用默认的自然类型可以做什么。然而,程序固定点需要它,并且我最终需要利用(对人类来说显而易见的)事实,即(n > m) -> (S >S)。我似乎不能证明这一点-我运行类似这样的东西 Theorem gt_triv : forall n m : nat, n > m -> (S n) > (S m).
intros. 然后我有一个假设n > m和一个目标证明(S n) > (S m),但我似乎不能对它做任何事情(除了将它展开到S (S m) <
在我的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识别出两种类型,每种类型都是从使用相同参数从模块函子创建的模块中导入的,但出现在不同的模块中,它们实际上是相同的类型?
极小例子
Module Type S.
End S.
Module F (s : S).
Inductive foo : Type := a.
End F.
Module G (s : S).
Include F s.
End G.
Module H (s : S).
Include F.
End H.
Module I (s : S).
Module G := G s.
Module H := H s.
(* This is a type error
我在试图证明Coq中的鸽子洞问题。因此,我要证明以下引理:
Lemma pigeon_hole :
forall m n, m < n ->
forall f, (forall i, i < n -> f i < m) ->
exists i, i < n /\
exists j, j < n /\ i <> j /\ f i = f j.
我从老师那里得到的提示是,自动证明自然数之间的等式和不等式的一种有用的策略是
omega.
但我怀疑这是否与此有关。
我认为可以用归纳来完成,就像在中一样。
如果我尝试在n上进行归纳,我就得到了n
我现在正在学习Coq,在一个更大的证明中,我被下面的子证明所困扰:
Theorem sub : ∀ n m : nat, n ≤ m → n ≠ m → n < m.
或者,一旦展开:
Theorem sub : ∀ n m : nat, n ≤ m → n ≠ m → S n ≤ m.
这里,"n≤m“的归纳定义如下:
Inductive le : nat → nat → Prop :=
| le_n : ∀ n : nat, le n n
| le_S : ∀ n m : nat, (le n m) → (le n (S m)).
我没有走多远,但我的尝试
我注意到Coq对支持和类型的平等性综合了不同的归纳原则。有人对此有什么解释吗?
平等被定义为
Inductive eq (A : Type) (x : A) : A -> Prop := eq_refl : x = x
相关的归纳原则有以下几种类型:
eq_ind
: forall (A : Type) (x : A) (P : A -> Prop),
P x -> forall y : A, x = y -> P y
现在,让我们定义一个eq的Type吊坠:
Inductive eqT {A:Type}(x:A):A->Type:= eqT_refl:
我很难让induction n, m为n和m创建归纳假说,但经过一些尝试,情况似乎并非如此。顺便说一句,我假设是forall (n m : nat)。
那么,induction n, m induction n. induction m和induction n; induction m的区别是什么呢?
以下是我目前的理解:
我知道;是一个组合子,所以a; b可以在a生成的每个子目标上回放b,所以induction n; induction m会为induction n的每个子目标生成m的诱导低幂,对吗?
从同样的意义上说,induction n. induction m只会为当前的目标产生感应
我注意到,我一直在为嵌套(有时相互)的归纳类型重新定义非常相似的归纳原则,因为Coq自动生成的归纳原则太弱了。下面是一个非常简单的示例:
Require Import Coq.Lists.List.
Inductive T : Set :=
| C1 : T
| C2 : list T -> T.
Section T_nested_ind.
Variable P : T -> Prop.
Hypothesis C1_case : P C1.
Hypothesis C2_case : forall l : list T, Forall P l -> P (C2
为了理解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.
这给了我
下面的U归纳定义被Coq接受,因为它可以看到U在M.T U -> U中的出现次数是严格为正的。
Module M.
Definition T (A : Type) : Type := unit -> A.
End M.
Module N.
Inductive U : Type :=
| c : M.T U -> U.
End N.
另一方面,Coq不接受以下U的归纳定义,因为根据M.T的定义,它可能具有非严格正的出现。
Module Type S.
Parameter T : Type -> Type.
End S.
Module N (M : S).
我想证明在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 =