如何删除 Isabelle 中出现的所有子多重集？

Question

所以我想定义一个函数（我们称它为 applied），它会删除另一个多重集中出现的所有子多重集，并用单个元素替换每个出现的地方。例如，

applied {#a,a,c,a,a,c#} ({#a,a,c#}, f) = {#f,f#}

所以一开始我尝试了一个定义：

definition applied :: "['a multiset, ('a multiset × 'a)] ⇒ 'a multiset" where
"applied ms t = (if (fst t) ⊆# ms then plus (ms - (fst t)) {#snd t#} else ms)"

但是，我很快意识到这只会删除一个子集。所以如果我们按照前面的例子，我们会有

applied {#a,a,c,a,a,c#} ({#a,a,c#}, f) = {#f,a,a,c#}

这并不理想。

然后我尝试使用一个函数（我最初尝试了 primrec 和 fun，但前者不喜欢输入的结构并且 fun 无法证明函数终止。）

function applied :: "['a multiset, ('a multiset × 'a)] ⇒ 'a multiset" where
"applied ms t = (if (fst t) ⊆# ms then applied (plus (ms - (fst t)) {#snd t#}) t else ms)"
  by auto
termination by (*Not sure what to put here...*)

不幸的是，我似乎无法证明这个函数的终止。我试过使用“终止”、auto、fastforce、force 等，甚至 sledgehammer，但我似乎无法找到证明该功能有效的证据。

我可以帮忙解决这个问题吗？

Answer 1

像这样递归定义它确实有点棘手，因为不能保证终止。如果 fst t = {# snd t #}，或者更一般地说 snd t ∈# fst t 怎么办？然后你的函数保持运行循环并且永不终止。

在我看来，最简单的方法是进行“一次性”替换的非递归定义：

definition applied :: "'a multiset ⇒ 'a multiset ⇒ 'a ⇒ 'a multiset" where
  "applied ms xs y =
     (let n = Inf ((λx. count ms x div count xs x) ` set_mset xs)
      in ms - repeat_mset n xs + replicate_mset n y)"

我将元组参数更改为柯里化参数，因为根据我的经验，这在实践中更有用——但元组当然也可以。

n 是 xs 在 ms 中出现的次数。您可以通过检查它们的定义来查看其他函数的作用。

关于 n 也可以更明确一点，这样写：

definition applied :: "'a multiset ⇒ 'a multiset ⇒ 'a ⇒ 'a multiset" where
  "applied ms xs y =
     (let n = Sup {n. repeat_mset n xs ⊆# ms}
      in ms - repeat_mset n xs + replicate_mset n y)"

缺点是这个定义不再可执行——但两者应该很容易证明等价。

如何删除 Isabelle 中出现的所有子多重集？

How can I remove all occurrences of a sub-multiset in Isabelle?

function

proof

multiset

isabelle