Coq: evaluating/simplifying `Prop` 重言式
Coq: evaluating/simplifying `Prop` tautologies
我正在用 Coq 证明一些关于超滤器的基本事实，我的许多证明最终都到了必须证明一个目标的阶段，例如
(False -> False) = True
或
False /\ P = False
或
True
或其他一些琐碎的同义反复。 simpl 和 auto 似乎都没有做任何事情，那么我该如何解决这些 Prop 目标？
我不确定你是如何编码超滤器的，但你的前两个目标无法证明。事实上，他们断言不同 类型 之间的相等性，这在 vanilla Coq 中无法证明。然而，有多种不同的方法可以解决这个问题。
最简单（也是我认为最好）的解决方案是在所有定义中用逻辑等价替换命题的等价。例如，在您的第一种情况下，您将获得 (False -> False) <-> True 这确实是同义反复。
或者，您可以完全用布尔值替换命题，即在超过滤器定义中使用 bool 而不是 Prop，并依赖布尔连接词而不是命题连接词。你的第二种情况会变成类似于 false && P = false，这又是可证明的，因为你处理的是归纳类型元素之间的相等性，而不是命题之间的相等性。但是这个变化比之前的变化要大得多，因为它意味着你的开发要有更多的变化，用布尔值而不是命题来推理。如果你走这条路，你可能想看看 MathComp，它在这种设置中经常使用布尔值。
最后一种可能性有点棘手，它依赖于所谓的命题外延性公理，即两个命题只要等价就等价。在Coq中，它对应于
prop_ext : forall P Q : Prop, (P <-> Q) -> P = Q.
使用这个公理，你可以将你的各种平等目标简化为等价，正如第一个解决方案中提到的那样。一个类似的公理出现在同伦类型论 (HoTT) 的上下文中，作为其中核心的单价公理的结果，尽管 Coq 和 HoTT 中的命题概念有些不同。如果您对相等性和等价性之间的区别感到好奇，您可能想检查一下，这就是我提到它的原因，但我建议改为使用第一个解决方案，因为它避免了必须依赖一个不需要的公理。
我正在用 Coq 证明一些关于超滤器的基本事实，我的许多证明最终都到了必须证明一个目标的阶段，例如
(False -> False) = True
或
False /\ P = False
或
True
或其他一些琐碎的同义反复。 simpl 和 auto 似乎都没有做任何事情，那么我该如何解决这些 Prop 目标？
我不确定你是如何编码超滤器的，但你的前两个目标无法证明。事实上，他们断言不同 类型 之间的相等性，这在 vanilla Coq 中无法证明。然而，有多种不同的方法可以解决这个问题。
最简单（也是我认为最好）的解决方案是在所有定义中用逻辑等价替换命题的等价。例如，在您的第一种情况下，您将获得 (False -> False) <-> True 这确实是同义反复。
或者，您可以完全用布尔值替换命题，即在超过滤器定义中使用 bool 而不是 Prop，并依赖布尔连接词而不是命题连接词。你的第二种情况会变成类似于 false && P = false，这又是可证明的，因为你处理的是归纳类型元素之间的相等性，而不是命题之间的相等性。但是这个变化比之前的变化要大得多，因为它意味着你的开发要有更多的变化，用布尔值而不是命题来推理。如果你走这条路，你可能想看看 MathComp，它在这种设置中经常使用布尔值。
最后一种可能性有点棘手，它依赖于所谓的命题外延性公理，即两个命题只要等价就等价。在Coq中，它对应于
prop_ext : forall P Q : Prop, (P <-> Q) -> P = Q.
使用这个公理，你可以将你的各种平等目标简化为等价，正如第一个解决方案中提到的那样。一个类似的公理出现在同伦类型论 (HoTT) 的上下文中，作为其中核心的单价公理的结果，尽管 Coq 和 HoTT 中的命题概念有些不同。如果您对相等性和等价性之间的区别感到好奇，您可能想检查一下，这就是我提到它的原因，但我建议改为使用第一个解决方案，因为它避免了必须依赖一个不需要的公理。