Package natural-distance: Natural number distance function
Information
| name | natural-distance |
| version | 1.6 |
| description | Natural number distance function |
| author | Joe Hurd <joe@gilith.com> |
| license | MIT |
| show | Data.Bool Number.Natural |
Files
- Package tarball natural-distance-1.6.tgz
- Theory file natural-distance.thy (included in the package tarball)
Defined Constant
- Number
- Natural
- distance
- Natural
Theorems
⊦ ∀n. distance 0 n = n
⊦ ∀n. distance n 0 = n
⊦ ∀n. distance n n = 0
⊦ ∀m n. distance m n = distance n m
⊦ ∀m n. distance m n ≤ m + n
⊦ ∀m n. distance m (m + n) = n
⊦ ∀m n. distance (m + n) m = n
⊦ ∀m n. distance m n = 0 ⇔ m = n
⊦ ∀m n p. distance m p ≤ distance m n + distance n p
⊦ ∀m n p. distance (m + n) (m + p) = distance n p
⊦ ∀p m n. distance (m + p) (n + p) = distance m n
⊦ ∀m n. distance m n = if m ≤ n then n - m else m - n
⊦ ∀m n p. m * distance n p = distance (m * n) (m * p)
⊦ ∀p m n. distance m n * p = distance (m * p) (n * p)
⊦ ∀m n p q. distance m p ≤ distance (m + n) (p + q) + distance n q
⊦ ∀m n p q. distance (m + n) (p + q) ≤ distance m p + distance n q
⊦ ∀m n p q. distance m n + distance n p ≤ q ⇒ distance m p ≤ q
⊦ ∀m n p. distance m n ≤ p ⇔ m ≤ n + p ∧ n ≤ m + p
⊦ ∀P x y. P (distance x y) ⇔ ∀d. (x = y + d ⇒ P d) ∧ (y = x + d ⇒ P d)
⊦ ∀m n p q r s.
distance m n ≤ r ∧ distance p q ≤ s ⇒
distance m p ≤ distance n q + (r + s)
Input Type Operators
- →
- bool
- Number
- Natural
- natural
- Natural
Input Constants
- =
- Data
- Bool
- ∀
- ∧
- ⇒
- ∃
- ∨
- ¬
- cond
- F
- T
- Bool
- Number
- Natural
- *
- +
- -
- <
- ≤
- suc
- zero
- Natural
Assumptions
⊦ T
⊦ ∀n. 0 ≤ n
⊦ ∀n. n ≤ n
⊦ F ⇔ ∀p. p
⊦ ∀t. t ∨ ¬t
⊦ (¬) = λp. p ⇒ F
⊦ ∀t. (∀x. t) ⇔ t
⊦ (∀) = λp. p = λx. T
⊦ ∀x. x = x ⇔ T
⊦ ∀n. ¬(suc n = 0)
⊦ ∀m. m - 0 = m
⊦ ∀n. n - n = 0
⊦ ∀m n. m ≤ m + n
⊦ ∀m n. n ≤ m + n
⊦ (⇒) = λp q. p ∧ q ⇔ p
⊦ (¬T ⇔ F) ∧ (¬F ⇔ T)
⊦ ∀x y. x = y ⇔ y = x
⊦ ∀m n. m * n = n * m
⊦ ∀m n. m + n = n + m
⊦ ∀m n. m ≤ n ∨ n ≤ m
⊦ ∀m n. m + n - m = n
⊦ ∀m n. ¬(m < n) ⇔ n ≤ m
⊦ (∧) = λp q. (λf. f p q) = λf. f T T
⊦ ∀P. ¬(∃x. P x) ⇔ ∀x. ¬P x
⊦ (∃) = λP. ∀q. (∀x. P x ⇒ q) ⇒ q
⊦ ∀m n. m + n = m ⇔ n = 0
⊦ ∀m n. m ≤ n ⇔ ∃d. n = m + d
⊦ ∀P a. (∀x. x = a ⇒ P x) ⇔ P a
⊦ (∨) = λp q. ∀r. (p ⇒ r) ⇒ (q ⇒ r) ⇒ r
⊦ ∀m n. m ≤ n ∧ n ≤ m ⇔ m = n
⊦ ∀m n. m < n ⇔ ∃d. n = m + suc d
⊦ ∀m n p. m + (n + p) = m + n + p
⊦ ∀m n p. m + n = m + p ⇔ n = p
⊦ ∀m n p. m + n ≤ m + p ⇔ n ≤ p
⊦ ∀m n p. m ≤ n ∧ n ≤ p ⇒ m ≤ p
⊦ ∀t1 t2. (if T then t1 else t2) = t1 ∧ (if F then t1 else t2) = t2
⊦ ∀m n. n ≤ m ⇒ (m - n = 0 ⇔ m = n)
⊦ ∀m n p. p ≤ n ⇒ m + n - (m + p) = n - p
⊦ ∀m n p. m * n ≤ m * p ⇔ m = 0 ∨ n ≤ p
⊦ (∀n. 0 * n = 0) ∧ ∀m n. suc m * n = m * n + n
⊦ ∀m n p q. m ≤ p ∧ n ≤ q ⇒ m + n ≤ p + q
⊦ ∀m n p. p ≤ n ⇒ m * (n - p) = m * n - m * p
⊦ ∀P c x y. P (if c then x else y) ⇔ (c ⇒ P x) ∧ (¬c ⇒ P y)
⊦ ∀t. ((T ⇔ t) ⇔ t) ∧ ((t ⇔ T) ⇔ t) ∧ ((F ⇔ t) ⇔ ¬t) ∧ ((t ⇔ F) ⇔ ¬t)
⊦ ∀t. (T ∧ t ⇔ t) ∧ (t ∧ T ⇔ t) ∧ (F ∧ t ⇔ F) ∧ (t ∧ F ⇔ F) ∧ (t ∧ t ⇔ t)
⊦ ∀t. (T ∨ t ⇔ T) ∧ (t ∨ T ⇔ T) ∧ (F ∨ t ⇔ t) ∧ (t ∨ F ⇔ t) ∧ (t ∨ t ⇔ t)
⊦ ∀t. (T ⇒ t ⇔ t) ∧ (t ⇒ T ⇔ T) ∧ (F ⇒ t ⇔ T) ∧ (t ⇒ t ⇔ T) ∧ (t ⇒ F ⇔ ¬t)
⊦ ∀m n p.
m + n = n + m ∧ m + n + p = m + (n + p) ∧ m + (n + p) = n + (m + p)
⊦ (∀n. 0 + n = n) ∧ (∀m. m + 0 = m) ∧ (∀m n. suc m + n = suc (m + n)) ∧
∀m n. m + suc n = suc (m + n)