形式语义学
在计算理论中，形式语义学是关注计算的模式和程序设计语言的含义的严格的数学研究的领域。 语言的形式语义是用数学模型去表达该语言描述的可能的计算来给出的。 形式语义学（formal semantics），是程序设计理论的组成部分，以数学为工具，利用符号和公式，精确地定义和解释计算机程序设计语言的语义，使语义形式化的学科。 提供程序设计语言的形式语义的方法很多，其中主要类别有： 指称语义学，着重于语言的执行结果而非过程，包括域理论； 操作语义…
标签：#计算机逻辑
共 43 篇文章
自动推理
自动推理（）是计算机科学和数理逻辑的一个交叉领域，致力于理解推理的不同方面。自动推理的研究有助于开发能够让计算机完全或近乎完全自动地进行推理的计算机程序。虽然自动推理被视为人工智能的一个子领域，但它也与理论计算机科学和哲学有密切联系。 自动推理中发展最成熟的子领域包括自动定理证明（以及交互式定理证明）和。在类比推理、归纳推理和溯因推理方面也有大量研究工作。其他重要主题包括不确定性推理和非单调逻辑推理。自动推理的工具和技术包括经典逻辑和演…
霍尔逻辑
霍爾邏輯（），又稱弗洛伊德-霍爾邏輯（），是英国计算机科学家東尼·霍爾开发的形式系统，这个系统的用途是为了使用严格的数理逻辑推理來替计算机程序的正确性提供一组逻辑规则。 這個想法起源於罗伯特·弗洛伊德於較早的研究，他为流程图提供了类似的系统。東尼·霍爾於1969年首次發表，随后为其他研究者所精制。 霍爾三元組 霍爾邏輯的中心特征是霍爾三元組（Hoare triple）。这种三元组描述一段代码的执行如何改变计算的状态。Hoare三元组有如…
迪文森佐準則
迪文森佐準則（DiVincenzo's criteria）是建構量子電腦的必要條件，由理論物理學家（David P.DiVincenzo）於2000年提出。量子電腦是由數學家尤里·馬寧於1980年以及物理學家理查德·費曼於1982年首次提出，可作為有效模擬量子系統的工具，像是用於解決量子多體問題。 關於如何建構量子計算機的建議相當多，對於在建構量子元件時所遇到的種種挑戰，這些建議都取得了不同程度的成功。其中一些建議是使用超導量子位元、離…
模糊逻辑
模糊逻辑是处理部分真实概念的布林運算扩展。经典逻辑坚持所有事物（陈述）都可以用二元项（0或1，黑或白，是或否）来表达，而模糊逻辑用真实度替代了布尔真值。这些陈述表示实际上接近于日常人们的问题和語意陈述，因为“真实”和结果在多数时候是部分（非二元）的和/或不精确的（不准确的，不清晰的，模糊的）。 真实度经常混淆于機率。但是它们在概念上是不一样的；模糊真值表示在模糊定义的集合中的成员歸屬关系，而不是某事件或条件的可能度（likelihood…
逻辑优化
逻辑优化是指在一个或多个限制條件下，找到指定逻辑电路等效表示的过程，是数字电路与集成电路设计中逻辑综合的一部分。 电路一般来说會受到最小芯片面积和预定响应延迟的限制。对给定电路进行逻辑优化的目标是获得最小的逻辑电路，且其值与原始电路相同。 方法 逻辑电路简化方法同样适用于布尔表达式最小化。 分类 如今，逻辑优化分为多个类别： ;基于电路表示 : 两级逻辑优化 : 多级逻辑优化 基于电路特性 :时序逻辑优化 :组合逻辑优化 ;基于执行类型…
封闭世界假定
封闭世界假定是当前不是已知的事物都为假的假定。这个名字也称呼Ray Reiter对这个假定的逻辑形式化。与封闭世界假定相对立的使用开放世界假定，宣称知识的缺乏不蕴涵虚假。 否定为失败与封闭世界假定有关，因为它总体上相信不能被证明为真的所有命题都是假的。 封闭世界假定经常暗含在数据库中，因为所有没有明确的包换在表中记录都暗含的假定表示这是假（而不是未知）这个事实。例如，如果数据库包含下列表，报告写作给定文章的人的，关于没有编辑形式逻辑的文…
依值类型
在计算机科学和逻辑中，依值类型（旧译依赖-{}-类型，dependent type）是指依赖于值的类型，其理论同时包含了数学基础中的类型论和计算机编程中用以减少程序错误的类型系统两方面。在 Per Martin-Löf 的直觉类型论中，依值类型可对应于谓词逻辑中的全称量词和存在量词；在依值类型函数式编程语言如、Agda、、、F和Idris中，依值类型系统通过极其丰富的类型表达能力使得程序规范得以借助类型的形式被检查，从而有效减少程序错误…
柯里-霍华德对应
寫作的：在Coq軟件中自然數加法交換性的證明。nat_ind 代表數學归纳，eq_ind 代替等於，f_equal 代表在等式兩邊取同樣的函數。 前面的定理參照顯示 m = m + 0和S（m + y）= m + S y。]] 柯里-霍華德对应（）是在计算机程序和数学证明之间的紧密联系；这种对应也叫做柯里-霍華德同构、公式为类型对应或命题为类型对应。这是对形式逻辑系统和数学运算之间符号的相似性的推广。它被认为是由美国数学家哈斯凯尔·柯里…
操作语义学
操作语义学是计算机科学中的一个概念，它是使得计算机程序在数学上更加严谨的一种手段。其它类似的手段包括提供形式语义学，包括公理语义学和指称语义。 一个计算机语言的操作语义描述一段合理的程序是怎样被理解为一系列计算机步骤的。这些步骤就是这个程序的意义。在函數程式語言中一段终结性的序列在最后一步的返回程序的值。（由于一个程序可能是非非決定的，一般来说一个程序能够有许多不同的计算步骤和许多不同的返回值。） 操作语义最早被用来定义的语义。下面这句…
博弈语义
博弈语义是一种基于博弈论定义真或有效性等逻辑概念的形式语义，比如游戏者的赢策略。保尔·洛伦茨首先在1950年代晚期为逻辑引入了博弈语义。此后在逻辑中已经研究了很多不同的博弈语义。博弈语义也已经应用于编程语言的形式语义。 直觉主义逻辑，指称语义，线性逻辑 保罗·洛伦岑和Kuno Lorenz的主要动机是为直觉主义逻辑找到一种博弈论（他们的术语是"对话式" Dialogische Logik）语义。[http://www.math.lsa.…
抽象释义
在计算机科学中，抽象解释（abstract interpretation，在上下文明確時可簡稱AI）是基于在有序集合特别是格上的单调函数，计算机程序的语义的可靠逼近理论。它可以被看作对计算机程序的部分执行，获取关于它的语义信息（比如，控制结构、数据流）而不进行所有计算。 它的主要具体应用是静态分析，关于计算机程序的可能执行的信息的自动提取；这种分析有两个主要用途: 在编译器内部，分析程序来确定特定优化或变换是否是可适用的； 针对缺陷类的…
公理语义学
公理语义学（Axiomatic semantics）是使用数理逻辑来证明程序正确性。程序中的命令的意义描述是通过对程序状态的断言效果。断言是逻辑语句——带变量的谓词，而这些变量定义了程序的状态。 公理语义学的一个实例是霍尔逻辑。 参见 指称语义学 操作语义学 形式语义学 断言 (程式) 参考文献
合一
在逻辑和计算机科学中，合一（unification），是方程求解表达式之间方程的算法过程。例如，使用 x, y, z 作为变量，单元素集合解的方程{cons(x, cons(x, nil)) = cons(2, y)}是一个语法一阶合一问题，具有替换{x ↦ 2, y ↦ cons(2, nil)}作为其唯一解。 合一算法首先由雅克·埃尔布朗 ( 发现，而第一个正式研究可归因于 ，他使用一阶句法合一作为基本构建块他对一阶逻辑的归结过程的…
非单调逻辑
非单调逻辑（）是（在前提的集合和单一的句子之间的）推论关系不是单调递增的形式逻辑。 与单调推理（经典逻辑）相对，非单调推理是指知识库加入新知识后，原有的推论会被推翻的逻辑。也就是说，知识库的推论不随着知识增长而增长，即非单调递增。这时，必须使用某种正确的维持机制，确保推理继续进行。因此，非单调推理多是在知识不完全的情况下发生的。 多数形式逻辑都有单调性的推论关系，就是说，如果一个句子可以从前提的集合中推理出来，则它也可以从把这个前提集合…
斷言 (程式)
在程式設計中，斷言（assertion）是一種放在程式中的一階邏輯（如一個結果為真或是假的邏輯判斷式），目的是為了標示與驗證程式開發者預期的結果－當程式執行到斷言的位置時，對應的斷言應該為真。若斷言不為真時，程式會中止執行，並給出錯誤訊息。 例如，以下的程式包括二個斷言： x := 5; {x > 0} x := x + 1 {x > 1} x > 0及x > 1，當程式執行到二個斷言對應的位置時，斷言的內容均為真。 程式設計者可以用斷…
模型检测
在计算机科学领域，模型检测或属性检测是一种用于验证系统的有限状态模型是否满足给定规范（即正确性）的方法。这种方法通常应用于硬件或软件系统；在此类系统中，规范不仅包含安全性需求（例如避免导致系统崩溃的状态），同时也包含活性需求（例如避免活锁现象）。 为了能够通过算法解决此类问题，系统的模型及其规范均需使用精确的数学语言进行形式化表述。为此，该问题被转化为逻辑范畴下的任务，即验证某个特定的结构是否满足给定的逻辑公式。这一通用概念适用于多种逻…
邏輯編程
邏輯編程（逻辑程-{}-序设计）是種編程范式，它設定答案須符合的規則來解決問題，而非設定步驟來解決問題。過程是 :算法=邏輯+控制。 不同的方法，可以看。 邏輯編程的要點是將正規的邏輯風格帶入電腦程式設計之中。數學家和哲學家發現邏輯是有效的理論分析工具。很多問題可以自然地表示成一個理論。說需要解答一個問題，通常與解答一個新的假設是否跟現在的理論無衝突等價。邏輯提供了一個證明問題是真還是假的方法。建立證明的方法是人所皆知的，故邏輯是解答問…
同伦类型论
在数理逻辑与计算机科学中，同伦类型论（homotopy type theory，缩写 HoTT）是一套旨在于同伦论的大框架下构建内涵类型论语义的理论，尤指Quillen模型范畴和弱分解系统。反而言之，内涵类型论则为同伦理论提供了一套逻辑语言。类型论在绝大多数计算机证明辅助系统中被用作集合论的替代理论，因为集合论的语言难以转化成计算机证明辅助的形式语言。而英国哲学家和逻辑学家伯特兰·罗素则提出了类型论作为集合论的替代理论。 同伦理论在20…
高阶逻辑
在数学与逻辑中，高阶逻辑（缩写HOL）是谓词逻辑的一种形式，与一阶逻辑的主要区别在于增加了量词的作用元，命题变元和谓词变元也能作约束变元（受量词约束）且作谓词变元的主目，有时语义也更强。例如，可量化谓词的系统就是二阶逻辑。 高阶逻辑区别于一阶逻辑的其他方式是在构造中允许下层的类型论。高阶谓词是接受其他谓词作为参数的谓词。一般的，阶为 n 的高阶谓词接受一个或多个 (n-1) 阶的谓词作为参数，这里的 n > 1。对高阶函数类似的评述也成…