标签: proof

我有一个计算机程序,读取一个字符数组,操作数和运算符用后缀表示法编写.然后程序扫描数组,通过使用堆栈计算结果,如下所示:

get next char in array until there are no more
if char is operand
    push operand into stack
if char is operator 
    a = pop from stack
    b = pop from stack
    perform operation using a and b as arguments
    push result
result = pop from stack

如何通过归纳证明此程序正确评估任何后缀表达式？(摘自练习4.16 Java中的算法(Sedgewick 2003))

我正在尝试对依赖函数进行证明,而且我遇到了障碍.

所以我们假设我们有一个f-相等的定理

f-equal : ? {A B} {f : A ? B} {x y : A} ? x ? y ? f x ? f y
f-equal refl = refl

我试图证明一个关于依赖函数的平等保存的更普遍的概念,并遇到障碍.即,类型

?-equal : ? {A} {B : A ? Set} {f : {a : A} ? B a} {x y : A} ?
            x ? y ? f x ? f y

让编译器不高兴,因为它无法弄清楚fx和fy属于同一类型.这似乎是一个可以修复的问题.是吗？

注意; 使用的等价关系定义如下:

data _?_ {A : Set}(x : A) : A ? Set where
  refl : x …

如何证明以下每个列表xs都是如此:

undefined ++ xs = undefined

读完这个问题后:功能证明(Haskell)

在查看forall xs ys. length (xs ++ ys) = length xs + length ys了Haskell音乐学院的归纳证明之后(第164页).

在我看来,函数应用程序分布在列表串联上.

因此,更普遍的法律可能就是这样forall f xs ys. f (xs ++ ys) = f xs ++ f ys.

但是,如何证明/反驳这样的谓词呢？

- 编辑 -

我写了一个错字:forall f xs ys. f (xs ++ ys) = f xs + f ys它与上一个问题和Haskell SoM使用的内容相匹配.话虽如此,由于这个错字,它不再是"分配"财产.然而,@ leftaroundabout为我原来的错字问题做出了正确答案.至于我的预期问题,法律仍然不正确,因为功能不需要保留结构价值.将f可能给依赖于它应用到列表的长度完全不同的答案.

我在网上看到，求最长路径问题是NP完全问题。

出于某种原因，我的老师告诉我这不是一个 NP 完全问题。所以现在我正在寻找一个示例，该示例显示获得最长路径所需的计算量大于多项式时间。

目前，我只看到了具有多项式复杂度时间的例子。

任何人都可以给我证明这个问题是NP完全的吗？

证明助手的主要功能是什么？

我只是想知道证明检查的内部逻辑。例如，有关此类助手的图形用户界面的主题使我不感兴趣。

对于编译器，我也提出了类似的问题：https : //softwareengineering.stackexchange.com/questions/165543/how-to-write-a-very-basic-compiler

我的担心是一样的，但对于校对系统。

遵循Haskell逻辑，数学和编程之路，您可以找到第48页定理2.12.1 ¬ ? ? ?及其反义词¬ ? ? ?

该书使用Haskell并假设

1. ? = False
2. ? = True

这将产生Agda类型theorem : (p q : Bool) ? not p ? q，可以通过轻松证明refl。

但是，在不假设1和2的情况下可以证明原始定理吗？

试

-- from software foundations (https://plfa.github.io/Negation/)
postulate
  excluded-middle : ? {A : Set} ? A ? ¬ A

theorem : ¬ ? ? ?
theorem x = {!!}

当然，由于我们无法构建?，因此不会产生任何解决方案，所以我想需要矛盾的证明吗？另外，我是否假设这假设了排除中间的定律，因此这是附加的假设？

阿格达（Agda）说：

我不确定是否应该使用构造函数refl，因为在尝试解决以下统一问题（推断索引？预期索引）时，我陷入了困境。？？在检查表达式时？有类型吗？

谢谢！

我坚持要证明以下公认的引理。请帮助我如何继续。

函数sumoneseq以相反的顺序添加并返回“true”的重复列表。鉴于 [真;假; 真;真;假; true;true;true ]，它返回 [3;2;1]。该功能sumones在NAT表增加值。给定 [3;2;1]，它返回 6。

Notation "x :: l" := (cons x l) (at level 60, right associativity).
Notation "[ ]" := nil.
Notation "[ x ; .. ; y ]" := (cons x .. (cons y nil) ..).


Fixpoint sumoneseq (lb: list bool) (ln: list nat) : list nat :=
 match lb, ln with
 | nil, 0::tl'' => tl''
 | nil, _ => ln
 | true::tl', nil => …

我目前正在阅读算法的书,并遇到了稳定的匹配问题.一个问题浮现在脑海里,我很好奇,但这本书没有回答.在每个SMP中,总是可以有一对,每个最喜欢另一个？就像在经典的婚姻例子中一样.是否总有一对有一个女人和一个男人在哪里都排在彼此的首选？

如果其中一个是偶数而另一个是奇数,则采用"两个自然之和很奇怪"的非常简单的证明:

Require Import Arith.
Require Import Coq.omega.Omega.

Definition even (n: nat) := exists k, n = 2 * k.
Definition odd  (n: nat) := exists k, n = 2 * k + 1.

Lemma sum_odd_even : forall n m, odd (n + m) -> odd n /\ even m \/ even n /\ odd m.
Proof.
  intros n. intros m. left.
  destruct H. firstorder.

这段代码末尾的状态是:

2 subgoals
n, m, x : nat
H : n + m = 2 * …