Agda: 无法解决除法属性时出现的以下约束条件

huangapple go评论52阅读模式
英文:

Agda: Failed to solve the following constraints when solve divison property

问题

以下是您提供的Agda代码的翻译部分:

module div where

open import Data.Nat using (ℕ; zero; suc; _+_)
open import Data.Nat.Properties using (+-assoc)
open import Relation.Binary.PropositionalEquality
  using (_≡_; refl; cong; sym; trans)

data _∣_ : ℕ → ℕ → Set where
    0∣0 : zero ∣ zero
    m∣0 : ∀ {d} → suc d ∣ zero
    m∣n : ∀ {d m} → suc d ∣ m → suc d ∣ suc (m + d)

infix 4 _∣_

∣-refl : ∀ a → a ∣ a
∣-refl zero = 0∣0
∣-refl (suc a) = m∣n m∣0

+zero : ∀ m → m + zero ≡ m
+zero zero = refl
+zero (suc m) rewrite +zero m = refl

+n : ∀ {m n : ℕ} → m + suc n ≡ suc (m + n)
+n {zero} {n} = refl
+n {suc m} {n} = cong suc (+n)

d-suc : ∀ {m n : ℕ} → suc (m + suc n) ≡ suc (suc (m + n))
d-suc = cong suc (+n)

∣-plus : ∀ a b c → a ∣ b → a ∣ c → a ∣ b + c
∣-plus .zero .zero c 0∣0 r₂ = r₂
∣-plus .(suc _) .zero c m∣0 r₂ = r₂
∣-plus _ (suc w) .zero (m∣n r₁) m∣0 rewrite +zero w = m∣n r₁
∣-plus (suc d) .(suc (_ + _)) .(suc (_ + _)) (m∣n r₁) (m∣n r₂) = {!   !}

请注意,最后一行还存在一些问题,其中有一些约束没有解决。您希望将其改为:

∣-plus (suc d) (suc (m₁ + d)) (suc (m₂ + d)) (m∣n r₁) (m∣n r₂) = ?

这将使目标变为 ?0 : suc d ∣ suc (m₁ + d + suc (m₂ + d)),然后您可以使用 d-suc 得到新的目标 ?0 : suc (suc(m₁ + d + (m₂ + d)))。现在,要证明

suc (suc(m₁ + d + (m₂ + d))) ≡ suc (suc(m₁ + m₂ + d + d))

您可以尝试使用 +-comm+-assoc 等自然数性质,但是在这个具体情况下,要解决这个问题可能需要进一步的推理。这可能涉及到更多关于 Agda 的具体细节和证明策略,因此建议参考 Agda 的文档或向 Agda 社区寻求帮助,以找到解决此问题的最佳方法。

英文:

I have code below:

module div where

open import Data.Nat using (ℕ; zero; suc; _+_)
open import Data.Nat.Properties using (+-assoc)
open import Relation.Binary.PropositionalEquality
  using (_≡_; refl; cong; sym; trans)

data _∣_ : ℕ → ℕ → Set where
    0∣0 : zero ∣ zero
    m∣0 : ∀ {d} → suc d ∣ zero
    m∣n : ∀ {d m} → suc d ∣ m → suc d ∣ suc (m + d)

infix 4 _∣_

∣-refl : ∀ a → a ∣ a
∣-refl zero = 0∣0
∣-refl (suc a) = m∣n m∣0

+zero : ∀ m → m + zero ≡ m
+zero zero = refl
+zero (suc m) rewrite +zero m = refl

+n : ∀ {m n : ℕ} → m + suc n ≡ suc (m + n)
+n {zero} {n} = refl
+n {suc m} {n} = cong suc (+n)

d-suc : ∀ {m n : ℕ} → suc (m + suc n) ≡ suc (suc (m + n))
d-suc = cong suc (+n)


∣-plus : ∀ a b c → a ∣ b → a ∣ c → a ∣ b + c
∣-plus .zero .zero c 0∣0 r₂ = r₂
∣-plus .(suc _) .zero c m∣0 r₂ = r₂
∣-plus _ (suc w) .zero (m∣n r₁) m∣0 rewrite +zero w = m∣n r₁
∣-plus (suc d) .(suc (_ + _)) .(suc (_ + _)) (m∣n r₁) (m∣n r₂) = {!   !} 

Run agda and it shows errors for last line.

Failed to solve the following constraints:
  _63 + _64 = m + d : ℕ (blocked on _63)
  _61 + _62 = m₁ + d : ℕ (blocked on _61)

I try to make the last line look like this,

∣-plus (suc d) (suc (m₁ + d)) (suc (m₂ + d)) (m∣n r₁) (m∣n r₂) = ?

So the goal should be ?0 : suc d ∣ suc (m₁ + d + suc (m₂ + d)), then I can get new goal ?0 : suc (suc(m₁ + d + (m₂ + d))) by d-suc. Now if i can prove

suc (suc(m₁ + d + (m₂ + d))) ≡ suc (suc(m₁ + m₂ + d + d))

where right side is m∣n (m∣n (∣-plus _ _ _ r₁ r₂)), then it is finished. But I can not get the m₁ and m₂ because above errors. How to solve it ? or my proof method is wrong ?

EDIT:
The proof can be simplifed


∣-plus : ∀ a b c → a ∣ b → a ∣ c → a ∣ b + c
∣-plus .zero .zero c 0∣0 r₂ = r₂
∣-plus .(suc _) .zero c m∣0 r₂ = r₂
∣-plus .(suc _) .(suc _) c (m∣n r₁) r₂ = ?

The goal is 0? : suc d ∣ suc (m + d + c), we can get suc d ∣ suc (m + c + d) by m∣n (∣-plus _ _ _ r₁ r₂). But it still requires d and m are available to give the equality m + d + c = m + c + d.

EDIT2:

I add a new equality

open import Data.Nat.Properties using (+-assoc; +-comm; +-identityʳ)

++ex : ∀ {a b c : ℕ} → a + b + c ≡ a + c + b
++ex {zero} {b} {c} rewrite +-comm b c = refl
++ex {suc a} {b} {c} = cong suc (++ex {a} {b} {c})

∣-plus : ∀ a b c → a ∣ b → a ∣ c → a ∣ b + c
∣-plus .zero .zero c 0∣0 r₂ = r₂
∣-plus .(suc _) .zero c m∣0 r₂ = r₂
∣-plus (suc d) .(suc _) c (m∣n r₁) r₂ with m∣n (∣-plus _ _ _ r₁ r₂)
... | s rewrite ++ex {_} {c} {d} = {!  !}

But I still can not get the m to apply this equality.

答案1

得分: 1

使用模式中的函数不支持从帖子"could-not-parse-the-left-hand-side"中。

因此,我通过refl来解决它,它确实很强大。以下是我的完整代码:

module div where

open import Data.Nat using (ℕ; zero; suc; _+_)
open import Data.Nat.Properties using (+-assoc; +-comm; +-identityʳ)
open import Relation.Binary.PropositionalEquality
  using (_≡_; refl; cong; sym; trans)

data _∣_ : ℕ → ℕ → Set where
    0∣0 : zero ∣ zero
    m∣0 : ∀ {d} → suc d ∣ zero
    m∣n : ∀ {d m} → suc d ∣ m → suc d ∣ suc (m + d)

infix 4 _∣_

++ex : ∀ {a b c : ℕ} → a + b + c ≡ a + c + b
++ex {zero} {b} {c} rewrite +-comm b c = refl
++ex {suc a} {b} {c} = cong suc (++ex {a} {b} {c})

++ex1 : ∀ {d m c w} → w ≡ m + d → w + c ≡ m + c + d
++ex1 {d} {m} {c} {.(m + d)} refl = ++ex {m} {d} {c}  

∣-plus : ∀ a b c → a ∣ b → a ∣ c → a ∣ b + c
∣-plus .zero .zero c 0∣0 r₂ = r₂
∣-plus .(suc _) .zero c m∣0 r₂ = r₂
∣-plus (suc d) (suc w) c (m∣n r₁) r₂ with m∣n (∣-plus _ _ _ r₁ r₂)
... | s rewrite ++ex1 {d} {_} {c} {w} refl = s
英文:

Using functions in patterns is not supported from the post "could-not-parse-the-left-hand-side"

Thus I solve it by refl, it is really powerful. Here is my full code

module div where

open import Data.Nat using (ℕ; zero; suc; _+_)
open import Data.Nat.Properties using (+-assoc; +-comm; +-identityʳ)
open import Relation.Binary.PropositionalEquality
  using (_≡_; refl; cong; sym; trans)

data _∣_ : ℕ → ℕ → Set where
    0∣0 : zero ∣ zero
    m∣0 : ∀ {d} → suc d ∣ zero
    m∣n : ∀ {d m} → suc d ∣ m → suc d ∣ suc (m + d)

infix 4 _∣_

++ex : ∀ {a b c : ℕ} → a + b + c ≡ a + c + b
++ex {zero} {b} {c} rewrite +-comm b c = refl
++ex {suc a} {b} {c} = cong suc (++ex {a} {b} {c})

++ex1 : ∀ {d m c w} → w ≡ m + d → w + c ≡ m + c + d
++ex1 {d} {m} {c} {.(m + d)} refl = ++ex {m} {d} {c}  

∣-plus : ∀ a b c → a ∣ b → a ∣ c → a ∣ b + c
∣-plus .zero .zero c 0∣0 r₂ = r₂
∣-plus .(suc _) .zero c m∣0 r₂ = r₂
∣-plus (suc d) (suc w) c (m∣n r₁) r₂ with m∣n (∣-plus _ _ _ r₁ r₂)
... | s rewrite ++ex1 {d} {_} {c} {w} refl = s

huangapple
  • 本文由 发表于 2023年3月3日 18:55:23
  • 转载请务必保留本文链接:https://go.coder-hub.com/75626154.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定