proof

1热度

1回答

我知道从顶点覆盖减少到支配集合。但是，我看到是否可以从最大独立集问题直接减少到支配集问题，以证明后一个NP完全。有谁知道这是否已经完成？我无法在网上找到任何东西。我希望能找到像沿证明的东西线：如果有一个支配集大小为k - >还有一个最大独立集大小为k。 AND 如果有一个最大独立集大小为k的 - >然后有一个控制集大小为k。

14热度

3回答

n个不同元素上的二叉搜索树的数量

可以从n个不同元素构建多少个二叉搜索树？我们如何找到一个数学证明的公式呢？示例：如果我们有3个不同的元件，比如说1，2，3，有是5二个叉搜索树。

-1热度

2回答

与誉系统逻辑扣

我是通过一些逻辑工作，我发现了一个困难我解决不了，如何从前提p证明=> Q，即¬q=>¬p？谢谢

0热度

2回答

证明log（n！）是Ω（n log（n））

我们的操作总成本是：Σ（i = 1到n）log（i）。证明这个和是Ω（n log（n））。我有点卡在如何去证明这一点。由于log（1）+ log（2）+ log（3）= log（3！）（等等等等），我知道总结出来是log（n！）但是然后我'米卡在哪里去正式证明。任何帮助，将不胜感激！

-1热度

1回答

证明最大（O（f（n）），O（g（n）））= O（max（f（n），g（n））

Prove max(O(f(n)), O(g(n)))=O(max(f(n), g(n)) 它确实有道理，但到目前为止我不“T有任何想法如何真正证明这一点。任何投入，将不胜感激。

1热度

3回答

在Coq的

证明无限电感值的不存在假设我有一个很简单的感应型： Inductive ind : Set := | ind0 : ind | ind1 : ind -> ind. ，我想证明某些值可以不存在。具体来说，不可能有非正当的价值观：~exists i, i = ind1 i。我环顾四周互联网上的位，并与一无所获。我能写： Fixpoint depth (i : ind)

1热度

1回答

循环不变量和算法的证明

我将如何获得一个循环不变量并为以下算法证明它。 power(x,y): z = 1 m = 0 while m < y: z = z*x m = m+1 return z

1热度

1回答

将命题逻辑参数转换为Prolog

如何将以下参数转换为Prolog？它似乎不需要谓词。（注：我使用&用于结合和|要析取。） ģ - >（H & j）（H | j） - >取值 S | [R Ⱶ摹 - > [R 另外，我想请教如何在Prolog的数据库，以确定（G - > R）是假的参数是因此是无效的？这已经有一段时间。（是的，这是家庭作业的教授问我们要证明的说法，但它是不是有效的，如果G，H，J，和S是真实和R是假的。）编

3热度

1回答

二叉树的数学证明

我并没有隐藏这是我功课的一部分，但我已经尝试过，然后发布在这里。所以... 我需要证明一个二叉树，节点k有2k + 1位置上的2k和右子节点。我通过归纳证明了这一点。现在我需要证明一个二叉树，一个节点k在(floor)(k/2)的位置上有其父。我拿了两个案子。试用诱导也是如此。对于3个节点的树是真的。如果它是节点k真正的我会证明为节点k + 1 如果节点k + 1股的父与节点k这显然是正确

-1热度

1回答

线性内存使用

我试图找到其使用的内存线性空间的算法最长公共子。