标签: theorem-proving

我想知道是否有人可以告诉我Z3和coq之间的区别？在我看来,coq是一个证明助手,因为它要求用户填写证明步骤,而Z3没有这个要求.但似乎coq也有类似于Z3的自动战术？或者也许coq中的证明搜索能力不如Z3强大？

我正在努力学习agda.但是,我遇到了问题.我在agda wiki上找到的所有教程对我来说都太复杂了,涵盖了编程的不同方面.在阅读了关于agda的3个教程之后,我能够编写简单的证明,但我仍然没有足够的知识将它用于真正的单词算法正确性.

你能推荐我关于这个主题的任何教程吗？类似于学习自己一个Haskell,但对于Agda.

当我编写算法时,我通常会在注释中写下不变量.

例如,一个函数可能返回一个有序列表,另一个函数则期望列出一个列表.
我知道定理证明存在,但我没有使用它们的经验.

我也相信智能编译器[sic!]可以利用它们来优化程序.
那么,是否有可能写下不变量并让编译器检查它们？

我正在尝试使用微软研究院开发的SMT求解器Z3检索所有可能的一阶理论模型.这是一个最小的工作示例:

(declare-const f Bool)
(assert (or (= f true) (= f false)))

在这个命题案例中,有两个令人满意的任务:f->true和f->false.因为Z3(以及一般的SMT求解器)只会尝试找到一个令人满意的模型,所以找不到所有解决方案是不可能的.在这里,我发现了一个有用的命令(next-sat),但似乎最新版本的Z3不再支持这一点.这对我来说有点不幸,总的来说我觉得这个命令非常有用.还有另一种方法吗？

我试图在Hilbert风格的系统中证明语句〜(a-> ~b)=> a .不幸的是,似乎不可能想出一个通用算法来找到证据,但我正在寻找一种强力型策略.关于如何攻击这个的任何想法都是受欢迎的.

传统上大多数使用计算逻辑的工作要么是命题,在这种情况下你使用了SAT(布尔可满足性)求解器,或者是一阶,在这种情况下你使用了一阶定理证明器.

近年来,SMT(可满足模理论)求解器取得了很大进展,基本上用算术等理论来增强命题逻辑.SRI International的John Rushby甚至称他们为颠覆性技术.

在一阶逻辑中可以处理但仍然无法由SMT处理的问题最重要的实际例子是什么？最特别的是,SMT在软件验证领域无法解决哪些问题？

我试着 通过形式化教自己Coq 形式化 我熟悉的数学定理:停止问题的不可判定性 可计算性理论中的各种定理.

由于我对形式化计算模型的细节不感兴趣(例如,图灵机,注册机,lambda calculi等),我试图通过 "教授Coq Church-Turing论文",即假设Axioms表示Coq认为可计算的函数的属性(即,可定义的类型函数nat -> nat).

例如,如果我想告诉Coq有部分可计算函数的有效枚举,我可以说

Definition partial := nat -> nat -> option nat.
Axiom Phi : nat -> partial.

这里,部分可计算函数被认为是(总)可计算函数,给定第一个参数s,模拟s许多步骤的原始部分可计算函数的计算.我还可以添加其他Axioms,如Padding Lemma,我可能能够证明停止问题的不可判定性,以及可计算性理论中的其他一些定理.

我的第一个问题是我到目前为止是否走在正确的轨道上.难道不是我正在尝试做的事情显然不可能出现不完整现象或Coq类型系统的性质吗？

我的第二个问题是关于相对化.如果我试图在可计算性理论中证明更严肃的事情,我会考虑在oracles中进行计算.由于oracles经常被构造为部分二值函数的极限,所以似乎(至少天真地)使oracles具有类型是自然的nat -> bool.同时,为了使神谕变得不平凡,它们必须是不可计算的.考虑到这一点,具有类型的oracle是否nat -> bool有意义？

这是关于oracles的另一个问题:如果对于每个oracle,存在相对于该特定oracle的部分可计算函数的类型,那将是非常好的.我可以通过在Coq中利用依赖类型系统来做到这一点吗？这种可能性是否取决于上文所述的一些形式化神谕的选择？

编辑:上面的方法肯定不能正常工作,因为我需要一个额外的公理:

Axiom Phi_inverse: partial -> nat.

这应该不会成为预言真的.有没有像我上面描述的方法(我的意思是,那个不涉及计算模型形式化的方法)？

编辑:为了澄清我的意图,我编辑了上面的问题陈述.另外,为了呈现我想到的形式化的风格,我提出了一个不完整的证据,证明这里停止问题的不可解决性:

Require Import Arith.
Require Import Classical.
Definition ext_eq (A B : Set) (f g : A -> …

我正在Idris中编写一个基本的monadic解析器,以熟悉Haskell的语法和差异.我有基本的工作正常,但我坚持尝试为解析器创建VerifiedSemigroup和VerifiedMonoid实例.

不用多说,这里是解析器类型,Semigroup和Monoid实例,以及VerifiedSemigroup实例的开始.

data ParserM a          = Parser (String -> List (a, String))
parse                   : ParserM a -> String -> List (a, String)
parse (Parser p)        = p
instance Semigroup (ParserM a) where
    p <+> q             = Parser (\s => parse p s ++ parse q s)
instance Monoid (ParserM a) where
    neutral             = Parser (const []) 
instance VerifiedSemigroup (ParserM a) where
    semigroupOpIsAssociative (Parser p) (Parser q) (Parser r) = ?whatGoesHere

我基本上被卡住了intros,具有以下证明状态:

-Parser.whatGoesHere> intros
----------              Other goals:              ----------
{hole3},{hole2},{hole1},{hole0} …

也许这是一个愚蠢的问题.下面是一个报价的Hasochism纸:

解决此问题的一种方法是将由参数化方程给出的引理编码为Haskell函数.通常,这种引理可以编码为类型的函数:

? x1 ... xn. Natty x1 ? ... ? Natty xn ? ((l ~ r) ? t) ? t

Run Code Online (Sandbox Code Playgroud)

我以为我理解了RankNTypes,但我无法理解这个命题的最后部分.我正在非正式地阅读它"给出一个需要的术语l ~ r,返回那个术语".我确信这种解释是错误的,因为它似乎导致了循环:我们l ~ r直到证明本身的结论才知道,那么我怎么能期望作为证据的假设提供一个需要的术语呢？

我本来期望一个等式证明有一个更像这样的类型:

Natty x1 ? ... ? Natty xn ? l :~: r

非正式地,"给定一堆Nattys,返回命题证明l并且r相等"(使用GHC的Data.Type.Equality).这对我来说更有意义,并且似乎与你在其他依赖类型系统中所说的一致.我猜它相当于论文中的版本,但我正在努力精神上消除这两个版本.

总之,我很困惑.我觉得我错过了一个关键的洞察力.我该怎么读这个类型((l ~ r) => t) -> t？

我已经听过一些关于使用自动化定理证明的尝试,以证明软件系统中不存在安全漏洞.总的来说,这是非常难以做到的.

我的问题是,是否有人使用类似工具来查找现有或建议系统中的漏洞？

Eidt:我不是要问证明软件系统是安全的.我问的是找到(理想情况下以前未知的)漏洞(甚至是它们的类).我在想这里(但不是)黑帽子:描述系统的形式语义,描述我想要攻击的内容,然后让计算机弄清楚我需要用什么行动来接管你的系统.