如何在 Isabelle 中对 "booleans" 进行归纳定义
How to do an inductive definition over "booleans" in Isabelle
在 Isabelle 中，我想定义采用谓词 'a => bool 的运算符并根据 "inductive structure of predicates" 修改它们。例如，人们可能想要计算这些谓词的 Disjunctive Normal Form (DNF)，例如D (λ x. P x --> Q x) = (λ x. ¬ P x \/ Q x).
这里的问题是 bool 不是归纳数据类型。我想到了两种可能的解决方案：
- 创建一个归纳数据类型，允许我在它们上定义我的运算符。为该数据类型提供谓词 (
P::'a => bool) 语义，然后用它来证明我要检查的引理。
- 为每一种可能的归纳情形证明定理。然后显示一个使用所有先前规则的一般情况。
作为第三种选择，我（一厢情愿地）希望更有经验的 Isabelle 用户可以用绕过此 "inductive issue" 的秘密 function/typedef 启发我的方法。所以这里的问题是：
还有其他更简单的选择吗？如果有，是哪些？如果不是，我的方法是否有缺陷或注定失败？
警告：我举了一个例子，DNF，然而，我更感兴趣的是运算符不一定保留谓词真值的一般情况，例如D 可以这样做：D (λ x. P x /\ Q x) = (λ x. P x \/ Q x).
HOL 函数无法查看其参数的语法表示。原因是替换公理，即逻辑上相等的项可以在任何上下文中替换。否则，可以定义满足 D (λ x. P x) = True 和 D (λ x. P x & True) = False 的函数 D，从而得出 False.
的证明
对于像转换为DNF这样的函数，其在HOL中的语义不依赖于参数的语法，仍然可以定义这样的转换。对于 DNF 转换，语义操作是恒等式，即
definition DNF :: "('a => bool) => ('a => bool)" where "D = id"
然后，您可以导出实际执行转换的重写规则。例如，
lemma DNF_imp: "DNF (λx. P x --> Q x) = DNF (λx. ~ P x | Q x)"
如果您使用这样一套专用规则调用 Isabelle 的简化器，您可以有效地转换为 DNF（尽管您永远无法在 HOL 中正式表达您的规则集在所有情况下都有效）。
很多时候，像DNF_imp这样的规则不足以实现这样的功能。在这种情况下，您可以在 Isabelle/ML 中编写一个 simproc，它在 DNF _ 项上触发并执行转换。由于您正在退出逻辑，因此 simproc 可以 查看参数的 HOL 语法并针对逻辑上相等的项表现不同。
相反，如果您确实想在逻辑中表达和推理转换函数 D，则无法像您建议的数据类型那样引入要处理的语法。
在 Isabelle 中，我想定义采用谓词 'a => bool 的运算符并根据 "inductive structure of predicates" 修改它们。例如，人们可能想要计算这些谓词的 Disjunctive Normal Form (DNF)，例如D (λ x. P x --> Q x) = (λ x. ¬ P x \/ Q x).
这里的问题是 bool 不是归纳数据类型。我想到了两种可能的解决方案：
- 创建一个归纳数据类型，允许我在它们上定义我的运算符。为该数据类型提供谓词 (
P::'a => bool) 语义，然后用它来证明我要检查的引理。 - 为每一种可能的归纳情形证明定理。然后显示一个使用所有先前规则的一般情况。
作为第三种选择，我（一厢情愿地）希望更有经验的 Isabelle 用户可以用绕过此 "inductive issue" 的秘密 function/typedef 启发我的方法。所以这里的问题是：
还有其他更简单的选择吗？如果有，是哪些？如果不是，我的方法是否有缺陷或注定失败？
警告：我举了一个例子，DNF，然而，我更感兴趣的是运算符不一定保留谓词真值的一般情况，例如D 可以这样做：D (λ x. P x /\ Q x) = (λ x. P x \/ Q x).
HOL 函数无法查看其参数的语法表示。原因是替换公理，即逻辑上相等的项可以在任何上下文中替换。否则，可以定义满足 D (λ x. P x) = True 和 D (λ x. P x & True) = False 的函数 D，从而得出 False.
对于像转换为DNF这样的函数，其在HOL中的语义不依赖于参数的语法，仍然可以定义这样的转换。对于 DNF 转换，语义操作是恒等式，即
definition DNF :: "('a => bool) => ('a => bool)" where "D = id"
然后，您可以导出实际执行转换的重写规则。例如，
lemma DNF_imp: "DNF (λx. P x --> Q x) = DNF (λx. ~ P x | Q x)"
如果您使用这样一套专用规则调用 Isabelle 的简化器，您可以有效地转换为 DNF（尽管您永远无法在 HOL 中正式表达您的规则集在所有情况下都有效）。
很多时候，像DNF_imp这样的规则不足以实现这样的功能。在这种情况下，您可以在 Isabelle/ML 中编写一个 simproc，它在 DNF _ 项上触发并执行转换。由于您正在退出逻辑，因此 simproc 可以 查看参数的 HOL 语法并针对逻辑上相等的项表现不同。
相反，如果您确实想在逻辑中表达和推理转换函数 D，则无法像您建议的数据类型那样引入要处理的语法。