我如何证明 elem z (xs ++ ys) == elem z xs ||元素z ys？
How can I prove that elem z (xs ++ ys) == elem z xs || elem z ys?
我有以下内容：
elem :: Eq a => a -> [a] -> Bool
elem _ [] = False
elem x (y:ys) = x == y || elem x ys
我如何证明对于所有 x 的 y 和 z...
elem z (xs ++ ys) == elem z xs || elem z ys
我试图让左侧等同于右侧，但是 none 我的尝试是富有成效的。
L.S elem z (x:xs ++ y:ys) = z==x || z==y || elem xs || elem ys
R.S elem z (x:xs) || elem z (y:ys) = z==x || z==y || elem xs || elem ys
有人可以帮我吗？
这里有一个提示。
++ 运算符是通过对 第一个 参数的归纳法定义的：
[] ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)
你想证明
elem z (xs ++ ys) == elem z xs || elem z ys
这是 z、xs 和 ys 的 属性。我们称它为 p(z,xs,ys)。
此外，++ 的第一个参数是 xs，因此这建议通过对 xs.
的归纳来进行
我们需要证明：
- 基本情况：
p(z,[],ys).
- 归纳案例：
p(z,x:xs,ys)假设归纳假设p(z,xs,ys)
您有时还需要利用 elem 的定义。
等式推理很有趣！如果你自己做一些证明，你会很快掌握它的诀窍。我热烈推荐 ch。 Haskell 中 Graham Hutton 的 Programming 的第 13 篇进行了简要介绍。
无论如何，你可以证明，对于所有等价的和有限（见）xs，ys和z,
elem z (xs ++ ys) == elem z xs || elem z ys
通过归纳列表 xs。为此，您需要使用 ++、|| 和 elem 的定义，并使用 || 是关联的事实：
[] ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)
False || b = b
True || _ = True
elem _ [] = False
elem x (y:ys) = x == y || elem x ys
基本案例
设ys为Eq a => [a]类型的值，z为Eq a => a类型的值；那么我们有
elem z ([] ++ ys)
= {applying ++}
elem z ys
= {unapplying ||}
False || elem z ys
= {unapplying elem}
elem z [] || elem z ys
电感案例
设 xs、ys 为 Eq a => [a] 类型的值，x、z 为 Eq a => a 类型的值。假设（归纳假设）
elem z (xs ++ ys) == elem z xs || elem z ys
然后我们有
elem z ((x:xs) ++ ys)
= {applying ++)
elem z (x : (xs ++ ys))
= {applying elem}
z == x || elem (xs ++ ys)
= {induction hypothesis}
z == x || (elem z xs || elem z ys)
= {associativity of ||}
(z == x || elem z xs) || elem z ys
= {unapplying elem}
elem z (x:xs) || elem z ys
(QED)
Haskell中的列表不满足归纳原则，因为Haskell是惰性语言，列表可能是无限的。相反，我认为您应该以相同的形式编写两个表达式以表明它们是等价的。所需的形式是
f [] = z
f (x:xs) = g x (f xs)
要使用这种方法来证明所需的结果，需要
f xs = elem z (xs ++ ys)
f' xs = elem z xs || elem z ys
请注意，通过 xs 上的模式匹配并使用 (++) 和 elem 的定义，这些等同于
f [] = elem z ys
f (x:xs) = x == z || elem z (xs ++ ys)
f' [] = elem z ys
f' (x:xs) = x == z || elem z xs || elem z ys
我们可以将递归调用重写为
f [] = elem z ys
f (x:xs) = x == z || f xs
f' [] = elem z ys
f' (x:xs) = x == z || f' xs
如果我们定义g x rest = x == z || rest那么
f [] = elem z ys
f (x:xs) = g x (f xs)
f' [] = elem z ys
f' (x:xs) = g x (f' xs)
然后注意 f 和 f' 的表达式是相等的。
我之前的回答是错误的：
这不是真的。考虑
xs = 重复 0
伊斯 = [1]
z = 1
然后
元素 z ys = 元素 1 [1] = 真
所以
元素 z xs || elem ys = 真
但
elem z (xs ++ ys) = elem 1 (repeat 0 ++ [1]) = False
因为在 `repeat 0` 中搜索 `1` 永远不会终止。
这是一个典型的例子，说明为什么惰性语言的等式理论不如严格语言丰富。
正如其他答案所建议的那样，您可以通过结构归纳法证明 *finite* `xs` 的定理。但这有点回避问题。什么是*有限*列表？
为了扩展已接受的答案，当 xs 为无限时，此等式也成立。如果 elem z xs = True，则 elem z (xs ++ ys) = True = elem z xs || elem z ys。否则，elem z (xs ++ ys) = ⊥ = elem z xs || elem z ys，可以在ghci中轻松验证。
我有以下内容：
elem :: Eq a => a -> [a] -> Bool
elem _ [] = False
elem x (y:ys) = x == y || elem x ys
我如何证明对于所有 x 的 y 和 z...
elem z (xs ++ ys) == elem z xs || elem z ys
我试图让左侧等同于右侧，但是 none 我的尝试是富有成效的。
L.S elem z (x:xs ++ y:ys) = z==x || z==y || elem xs || elem ys
R.S elem z (x:xs) || elem z (y:ys) = z==x || z==y || elem xs || elem ys
有人可以帮我吗？
这里有一个提示。
++ 运算符是通过对 第一个 参数的归纳法定义的：
[] ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)
你想证明
elem z (xs ++ ys) == elem z xs || elem z ys
这是 z、xs 和 ys 的 属性。我们称它为 p(z,xs,ys)。
此外，++ 的第一个参数是 xs，因此这建议通过对 xs.
我们需要证明：
- 基本情况：
p(z,[],ys). - 归纳案例：
p(z,x:xs,ys)假设归纳假设p(z,xs,ys)
您有时还需要利用 elem 的定义。
等式推理很有趣！如果你自己做一些证明，你会很快掌握它的诀窍。我热烈推荐 ch。 Haskell 中 Graham Hutton 的 Programming 的第 13 篇进行了简要介绍。
无论如何，你可以证明，对于所有等价的和有限（见xs，ys和z,
elem z (xs ++ ys) == elem z xs || elem z ys
通过归纳列表 xs。为此，您需要使用 ++、|| 和 elem 的定义，并使用 || 是关联的事实：
[] ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)
False || b = b
True || _ = True
elem _ [] = False
elem x (y:ys) = x == y || elem x ys
基本案例
设ys为Eq a => [a]类型的值，z为Eq a => a类型的值；那么我们有
elem z ([] ++ ys)
= {applying ++}
elem z ys
= {unapplying ||}
False || elem z ys
= {unapplying elem}
elem z [] || elem z ys
电感案例
设 xs、ys 为 Eq a => [a] 类型的值，x、z 为 Eq a => a 类型的值。假设（归纳假设）
elem z (xs ++ ys) == elem z xs || elem z ys
然后我们有
elem z ((x:xs) ++ ys)
= {applying ++)
elem z (x : (xs ++ ys))
= {applying elem}
z == x || elem (xs ++ ys)
= {induction hypothesis}
z == x || (elem z xs || elem z ys)
= {associativity of ||}
(z == x || elem z xs) || elem z ys
= {unapplying elem}
elem z (x:xs) || elem z ys
(QED)
Haskell中的列表不满足归纳原则，因为Haskell是惰性语言，列表可能是无限的。相反，我认为您应该以相同的形式编写两个表达式以表明它们是等价的。所需的形式是
f [] = z
f (x:xs) = g x (f xs)
要使用这种方法来证明所需的结果，需要
f xs = elem z (xs ++ ys)
f' xs = elem z xs || elem z ys
请注意，通过 xs 上的模式匹配并使用 (++) 和 elem 的定义，这些等同于
f [] = elem z ys
f (x:xs) = x == z || elem z (xs ++ ys)
f' [] = elem z ys
f' (x:xs) = x == z || elem z xs || elem z ys
我们可以将递归调用重写为
f [] = elem z ys
f (x:xs) = x == z || f xs
f' [] = elem z ys
f' (x:xs) = x == z || f' xs
如果我们定义g x rest = x == z || rest那么
f [] = elem z ys
f (x:xs) = g x (f xs)
f' [] = elem z ys
f' (x:xs) = g x (f' xs)
然后注意 f 和 f' 的表达式是相等的。
我之前的回答是错误的：
为了扩展已接受的答案，当 xs 为无限时，此等式也成立。如果 elem z xs = True，则 elem z (xs ++ ys) = True = elem z xs || elem z ys。否则，elem z (xs ++ ys) = ⊥ = elem z xs || elem z ys，可以在ghci中轻松验证。