LEAN 类型理论之注解(Annotations of LEAN Type Theory)—— 定义上相等(Definitional Equality)

本文主要是介绍LEAN 类型理论之注解(Annotations of LEAN Type Theory)—— 定义上相等(Definitional Equality),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

        定义上相等(Definitional Equality)指的是意义上相等,即同义,包括了,定义的缩写(Abbreviatory Definition),alpha转换,相同替代(substituting equals for equals)等。下面是LEAN给定的何谓 定义上相等。 

        注:罗列的推演规则中,如自明其义的,则不多加解析其前提、结果、或特定注解。

         一、表达式的定义上相等(Definitional Equality of Expressions)(Γ ⊢ e₁ ≡ e₂)

1. 定义上相等的自反性(Reflexive)

前提(Premises):

        a. 在 Γ  的假设,表达式 e 的类型是 α。

结果(Conclusion):

        在 Γ  的假设,表达式 e 定义上等于表达式 e 自己。

2. 定义上相等的互换性(Commutive)

3. 定义上相等的传递性(Transitive)

4. 类型宇宙的定义上相等(Definitional Equality for Universes)

5. 函数应用的同义替换(Substituting equals for equals in Application Typing Rule)

6. 抽象化的同义替换(Substituting equals for equals in Abstraction Typing Rule)

7. 依赖函数类型的同义替换(Substituting equals for equals in Dependent Function Type)

8. Beta 简化 (Beta Reduction)

        注解:

                该推演规则定义了,LEAN的Beta简化,即,函数应用(Function application, or application in short) 在定义上相等于(Definitional equals)函数体的表达式 e 中,将所有输入变量替换成调用时输入的表达式 e'。

9. Eta 简化(Eta Reduction)

        注解:

                该推演规则定义了,LEAN的 Eta简化,即,对已有的函数 e 再抽象化,定义上相等于(Definitional equals)其自己 e (itself)。

10. 证明无关性(Proof Irrelevance)

前提(Premises):

        a. 在 Γ  的假设,类型表达式 p 存在于类型宇宙 ℙ,即 p 是一个命题,ℙ 为命题类型宇宙。

        b. 在 Γ  的假设,表达式 h 的类型为 类型表达式 p,即 h 证明了 p。

        c. 在 Γ  的假设,表达式 h' 的类型为 类型表达式 p,即 h' 证明了 p。

结果(Conclusion):

        在 Γ  的假设,表达式 h 定义上等于表达式 h' 。

注解:

        该推演规则定义了,如果两个不同的证据(proof),h 和 h',证明了同样的命题 p,那么这两个证据在定义上相等(Definitional equals)。

二、宇宙层次的定义上相等(Definitional Equality of Levels)

        宇宙层次的定义上相等通过不等式来定义,即 𝑙 ≤ 𝑙' + n, n ∈ ℤ,当 n = 0时,𝑙 ≤ 𝑙'。另外在其论文有简要的说明,如何理解这个宇宙层次,这里就直接引用了。

        然后,再分别对每条推演规则进行注解。

1. 宇宙层次的定义上相等 (Definitional Equality of Levels)(𝑙 ≡ 𝑙')

2. 宇宙层次必须大于等0

3. 宇宙层次大于等于自身

4. 定义不等式左边的下一级的宇宙层次

        注解:当前宇宙层次 𝑙 ,另一宇宙层次 𝑙‘,有 𝑙 ≤ 𝑙‘ + (n - 1),那么,当前宇宙层次 𝑙  的下一级宇宙层次 S𝑙 ,会有 S𝑙 ≤ 𝑙‘ + (n - 1) + 1,即 S𝑙  ≤ 𝑙‘ + n 。也就是说,S𝑙 是 𝑙 层次的递进 1 级(+1)。

5. 定义不等式右边的下一级的宇宙层次

        注解:定义在不等式右边的,S𝑙'  ≡ 𝑙' + 1

6. 定义 作用在宇宙层次的 max函数 和 imax 函数

        注解:当  𝑙₁ + n  或  𝑙₂ + n 大于等于  𝑙,不管 𝑙₁ 和 𝑙₂ 谁的值大,其 max(𝑙₁, 𝑙₂) 都是获取其中的最大值,因此, max(𝑙₁, 𝑙₂) + n 必然 大于等于 𝑙。上面两个推演规则说明了,max函数内的左右输入的位置不影响其输出的结果。

        注解:当max函数的左右输入都小于等于  𝑙 + n 时,那么其结果也小于等于  𝑙 + n,即 max 只获取左右输入的较大值,而不增减其宇宙层次。

        注解:当 imax函数的右输入为层次 0 时,其输出亦为 0 。即,imax 函数的左右输入需要严格区分,会影响其输出的结果。

        注解:当 imax函数的右输入不等于 0 时,即 S𝑙₂,必大于0,其等价于max函数。

        注解:由于imax函数对其右输入是否为0敏感,因此,分析上面两条推演规则,即不等式左右两边的max函数与imax函数的关系,时,可按情况分别分析 𝑙₃ 是否等于 0。

        注释:这里突出了 𝑙 是宇宙层次表达式,其中可含有宇宙层次变量 u,在实际使用的过程中,其变量会被替换成实际的自然数值。

这篇关于LEAN 类型理论之注解(Annotations of LEAN Type Theory)—— 定义上相等(Definitional Equality)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1137097

相关文章

2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题

题库来源:安全生产模拟考试一点通公众号小程序 2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题是由安全生产模拟考试一点通提供,流动式起重机司机证模拟考试题库是根据流动式起重机司机最新版教材,流动式起重机司机大纲整理而成(含2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题参考答案和部分工种参考解析),掌握本资料和学校方法,考试容易。流动式起重机司机考试技

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合,内部除了存储元素外,还会存储一个score,存储在zset中的元素会按照score的大小升序排列,不同元素的score可以重复,score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]

系统架构师考试学习笔记第三篇——架构设计高级知识(20)通信系统架构设计理论与实践

本章知识考点:         第20课时主要学习通信系统架构设计的理论和工作中的实践。根据新版考试大纲,本课时知识点会涉及案例分析题(25分),而在历年考试中,案例题对该部分内容的考查并不多,虽在综合知识选择题目中经常考查,但分值也不高。本课时内容侧重于对知识点的记忆和理解,按照以往的出题规律,通信系统架构设计基础知识点多来源于教材内的基础网络设备、网络架构和教材外最新时事热点技术。本课时知识

自定义类型:结构体(续)

目录 一. 结构体的内存对齐 1.1 为什么存在内存对齐? 1.2 修改默认对齐数 二. 结构体传参 三. 结构体实现位段 一. 结构体的内存对齐 在前面的文章里我们已经讲过一部分的内存对齐的知识,并举出了两个例子,我们再举出两个例子继续说明: struct S3{double a;int b;char c;};int mian(){printf("%zd\n",s

【编程底层思考】垃圾收集机制,GC算法,垃圾收集器类型概述

Java的垃圾收集(Garbage Collection,GC)机制是Java语言的一大特色,它负责自动管理内存的回收,释放不再使用的对象所占用的内存。以下是对Java垃圾收集机制的详细介绍: 一、垃圾收集机制概述: 对象存活判断:垃圾收集器定期检查堆内存中的对象,判断哪些对象是“垃圾”,即不再被任何引用链直接或间接引用的对象。内存回收:将判断为垃圾的对象占用的内存进行回收,以便重新使用。

flume系列之:查看flume系统日志、查看统计flume日志类型、查看flume日志

遍历指定目录下多个文件查找指定内容 服务器系统日志会记录flume相关日志 cat /var/log/messages |grep -i oom 查找系统日志中关于flume的指定日志 import osdef search_string_in_files(directory, search_string):count = 0

Spring 源码解读:自定义实现Bean定义的注册与解析

引言 在Spring框架中,Bean的注册与解析是整个依赖注入流程的核心步骤。通过Bean定义,Spring容器知道如何创建、配置和管理每个Bean实例。本篇文章将通过实现一个简化版的Bean定义注册与解析机制,帮助你理解Spring框架背后的设计逻辑。我们还将对比Spring中的BeanDefinition和BeanDefinitionRegistry,以全面掌握Bean注册和解析的核心原理。

两个月冲刺软考——访问位与修改位的题型(淘汰哪一页);内聚的类型;关于码制的知识点;地址映射的相关内容

1.访问位与修改位的题型(淘汰哪一页) 访问位:为1时表示在内存期间被访问过,为0时表示未被访问;修改位:为1时表示该页面自从被装入内存后被修改过,为0时表示未修改过。 置换页面时,最先置换访问位和修改位为00的,其次是01(没被访问但被修改过)的,之后是10(被访问了但没被修改过),最后是11。 2.内聚的类型 功能内聚:完成一个单一功能,各个部分协同工作,缺一不可。 顺序内聚:

Mysql BLOB类型介绍

BLOB类型的字段用于存储二进制数据 在MySQL中,BLOB类型,包括:TinyBlob、Blob、MediumBlob、LongBlob,这几个类型之间的唯一区别是在存储的大小不同。 TinyBlob 最大 255 Blob 最大 65K MediumBlob 最大 16M LongBlob 最大 4G

Oracle type (自定义类型的使用)

oracle - type   type定义: oracle中自定义数据类型 oracle中有基本的数据类型,如number,varchar2,date,numeric,float....但有时候我们需要特殊的格式, 如将name定义为(firstname,lastname)的形式,我们想把这个作为一个表的一列看待,这时候就要我们自己定义一个数据类型 格式 :create or repla