基于比较的排序是nlog(n)的大o,因此我们知道mergesort不能是O(n).不过,我无法通过以下证据找到问题:
命题P(n):对于长度为n的列表,mergesort需要O(n)时间.
P(0):空列表上的合并排序只返回空列表.
强诱导:假设P(1),...,P(n-1)并试图证明P(n).我们知道在递归mergesort的每一步,两个大约"半列表"被合并,然后"压缩".每个半列表的合并排序通过归纳获得O(n/2)时间.拉紧需要O(n)时间.因此该算法具有M(n)= 2M(n/2)+ O(n)的递归关系,其为2O(n/2)+ O(n),其为O(n).
我的证明脚本给了我愚蠢的类型平等,nat = bool或者
nat = list unit我需要用来解决相互矛盾的目标.
在正常的数学中,这将是微不足道的.鉴于集合bool := { true, false },
nat := { 0, 1, 2, ... }我知道true ? bool,但是true ? nat,因此bool ? nat.在Coq,我甚至不知道如何陈述true :? nat.
有没有办法证明这些平等是错误的？或许,这不可能吗？
(编辑:删除了一长串失败的attemts,仍然可以在历史上看到.)
我不确定如何正式证明大O的总和规则,即:
f1(n) + f2(n) is O(max(g1(n)),g2(n))
到目前为止,我认为我的努力如下:
要有两个常量c1和c2这样c2 > c1.按大O定义:
f1(n) <= c1g1(n) and f2(n) <= c2g2(n)
我该怎么办？在这一步引入变量的数值替换来证明这种关系是否合理？不知道g或者f,这是我能想到的唯一方法.
我仍然试图围绕agda,所以我写了一个小小的tic-tac-toe游戏类型
data Game : Player -> Vec Square 9 -> Set where
start : Game x ( - ? - ? - ?
- ? - ? - ?
- ? - ? - ? [] )
xturn : {gs : Vec Square 9} -> (n : ?) -> Game x gs -> n < (#ofMoves gs) -> Game o (makeMove gs x n )
oturn : {gs : Vec Square 9} -> (n : ?) -> Game o gs …图形可以有许多不同的最小生成树(MST),但不同的MST可以有不同的边缘权重集吗？例如,如果MST使用边缘权重{2,3,4,5},则每个其他MST是否必须具有边缘权重{2,3,4,5},或者某些其他MST是否可以使用不同的权重集合？
给我这个想法的是,只有当边的权重不同时,图才没有唯一的MST.
我正在关注软件基金会这本书,我在名为"Imp"的章节.
作者公开了一种小语言,如下所示:
Inductive aexp : Type :=
| ANum : nat -> aexp
| APlus : aexp -> aexp -> aexp
| AMinus : aexp -> aexp -> aexp
| AMult : aexp -> aexp -> aexp.
以下是评估这些表达式的函数:
Fixpoint aeval (a : aexp) : nat :=
match a with
| ANum n ? n
| APlus a1 a2 ? (aeval a1) + (aeval a2)
| AMinus a1 a2 ? (aeval a1) - (aeval a2)
| AMult a1 a2 ? (aeval …我想知道,coq中是否有一个常用的矢量库,即它们的类型长度索引.
有些教程引用了Bvector,但是当我尝试导入它时却找不到它.
有Coq.Vectors.Vectordef,但是那里定义的类型只是命名t,这使我认为它是供内部使用的.
对于不想推出自己的图书馆的人来说,最好或最常见的做法是什么？我对标准库中的向量有误吗？还是有另一个我失踪的自由人？或者人们只是使用列表,并与他们的长度证明配对？
我已经能够创建一个证明,表明树中的最大总节点数等于n = 2 ^(h + 1) - 1,逻辑上我知道二叉树的高度是log n(可以绘制它出去看)但是我在构建一个正式的证据时遇到了麻烦,这个证据表明一棵有n片叶子的树至少有"log".我遇到或能够组合的每个证据总是处理完美的二叉树,但我需要适合任何情况的东西.有什么提示可以引导我朝着正确的方向前进
我是COQ的新手,我试图证明反例定理.
Variable A B:Prop.
Hypothesis R1: ~A->B.
Hypothesis R2: ~B.
Theorem ej: A.
当我们研究逻辑时,我们学习了RAA技术,但在COQ中,这并没有增加新的假设,现在我们陷入困境.
那么我们尝试:
Proof.
tauto.
Show Proof.
有了以下输出,但我们不知道它是什么意思.
(NNPP A
(fun H : ~ A => let H0 : B := R1 H in let H1 : False := R2 H0 in False_ind False H1))
有人可以帮我们理解COQ Show Proof输出吗？
我经历了理查德·伯德的"哈斯克尔功能的思考"一书,并且存在在那里他证明了滤波方法的属性我无法理解的部分.他证明的是:
filter p . map f = map f . filter (p . f)
在本书的前面,他将过滤器定义为:
filter p = concat . map (test p)
test p x = if p x then [x] else []
这就是他证明第一个等式的方法:
filter p . map f
= {second definition of filter} -- He's referring to the definition I gave above
concat . map (test p) . map f
= {functor property of map}
concat . map (test p . f)
= {since test p . f …