Package natural-fibonacci: Fibonacci numbers
Information
| name | natural-fibonacci |
| version | 1.3 |
| description | Fibonacci numbers |
| author | Joe Hurd <joe@gilith.com> |
| license | MIT |
| requires | base |
| show | Data.Bool Data.List Data.Pair Function Number.Natural Number.Natural.Fibonacci Relation |
Files
- Package tarball natural-fibonacci-1.3.tgz
- Theory file natural-fibonacci.thy (included in the package tarball)
Defined Constants
- Number
- Natural
- fibonacci
- Fibonacci
- decode
- decode.dest
- encode
- encode.find
- encode.mk
- decode
- Natural
Theorems
⊦ fibonacci 0 = 0
⊦ fibonacci 1 = 1
⊦ ∀n. decode (encode n) = n
⊦ ∀n. ∃k. n ≤ fibonacci k
⊦ ∀f p. decode.dest f p [] = 0
⊦ ∀n. encode n = encode.find n 1 0
⊦ ∀k. fibonacci k = 0 ⇔ k = 0
⊦ ∀l. decode l = decode.dest 1 0 l
⊦ ∀j k. j ≤ k ⇒ fibonacci j ≤ fibonacci k
⊦ ∀k. fibonacci (suc (suc k)) = fibonacci (suc k) + fibonacci k
⊦ ∀j. ¬(j = 1) ⇒ fibonacci j < fibonacci (suc j)
⊦ ∀n. fibonacci (n + 2) = fibonacci (n + 1) + fibonacci n
⊦ ∀n k.
decode.dest 1 0 (encode.find n (fibonacci (k + 1)) (fibonacci k)) = n
⊦ ∀j k. ¬(j = 1 ∧ k = 2) ∧ j < k ⇒ fibonacci j < fibonacci k
⊦ ∀n f p.
encode.find n f p =
let s ← f + p in
if n < s then encode.mk [] n f p else encode.find n s f
⊦ ∀f p h t.
decode.dest f p (h :: t) =
let s ← f + p in let n ← decode.dest s f t in if h then s + n else n
⊦ ∀p. p 0 ∧ p 1 ∧ (∀n. p n ∧ p (n + 1) ⇒ p (n + 2)) ⇒ ∀n. p n
⊦ ∃f. f 0 = 0 ∧ f 1 = 1 ∧ ∀n. f (n + 2) = f (n + 1) + f n
⊦ ∀n k l.
n < fibonacci (k + 2) ⇒
decode.dest 1 0 (encode.mk l n (fibonacci (k + 1)) (fibonacci k)) =
n + decode.dest (fibonacci (k + 1)) (fibonacci k) l
⊦ ∀l n f p.
encode.mk l n f p =
if p = 0 then l
else if f ≤ n then encode.mk (⊤ :: l) (n - f) p (f - p)
else encode.mk (⊥ :: l) n p (f - p)
⊦ ∀h.
(∀f g n. (∀m. m + 1 = n ∨ m + 2 = n ⇒ f m = g m) ⇒ h f n = h g n) ⇒
∃f. ∀n. f n = h f n
Input Type Operators
- →
- bool
- Data
- List
- list
- Pair
- ×
- List
- Number
- Natural
- natural
- Natural
Input Constants
- =
- select
- Data
- Bool
- ∀
- ∧
- ⇒
- ∃
- ∃!
- ∨
- ¬
- cond
- ⊥
- ⊤
- List
- ::
- []
- Pair
- ,
- Bool
- Function
- id
- Number
- Natural
- *
- +
- -
- <
- ≤
- bit0
- bit1
- even
- suc
- zero
- Natural
- Relation
- subrelation
- wellFounded
Assumptions
⊦ ⊤
⊦ wellFounded (<)
⊦ ¬⊥ ⇔ ⊤
⊦ ¬⊤ ⇔ ⊥
⊦ bit0 0 = 0
⊦ ∀t. t ⇒ t
⊦ ∀n. 0 ≤ n
⊦ ∀n. n ≤ n
⊦ ⊥ ⇔ ∀p. p
⊦ ∀x. id x = x
⊦ ∀n. n < suc n
⊦ ∀n. n ≤ suc n
⊦ (¬) = λp. p ⇒ ⊥
⊦ (∃) = λp. p ((select) p)
⊦ ∀t. (∀x. t) ⇔ t
⊦ ∀t. (∃x. t) ⇔ t
⊦ ∀t. (λx. t x) = t
⊦ (∀) = λp. p = λx. ⊤
⊦ ∀t. ¬¬t ⇔ t
⊦ ∀t. (⊤ ⇔ t) ⇔ t
⊦ ∀t. (t ⇔ ⊤) ⇔ t
⊦ ∀t. ⊥ ∧ t ⇔ ⊥
⊦ ∀t. ⊤ ∧ t ⇔ t
⊦ ∀t. t ∧ ⊥ ⇔ ⊥
⊦ ∀t. t ∧ ⊤ ⇔ t
⊦ ∀t. ⊥ ⇒ t ⇔ ⊤
⊦ ∀t. ⊤ ⇒ t ⇔ t
⊦ ∀t. t ⇒ ⊤ ⇔ ⊤
⊦ ∀t. ⊥ ∨ t ⇔ t
⊦ ∀t. ⊤ ∨ t ⇔ ⊤
⊦ ∀t. t ∨ ⊥ ⇔ t
⊦ ∀t. t ∨ ⊤ ⇔ ⊤
⊦ ∀n. ¬(suc n = 0)
⊦ ∀n. 0 + n = n
⊦ ∀m. m + 0 = m
⊦ ∀t. (⊥ ⇔ t) ⇔ ¬t
⊦ ∀t. (t ⇔ ⊥) ⇔ ¬t
⊦ ∀t. t ⇒ ⊥ ⇔ ¬t
⊦ ∀n. bit1 n = suc (bit0 n)
⊦ ∀m n. m ≤ m + n
⊦ ∀m n. n ≤ m + n
⊦ (⇒) = λp q. p ∧ q ⇔ p
⊦ ∀t. (t ⇔ ⊤) ∨ (t ⇔ ⊥)
⊦ ∀m. suc m = m + 1
⊦ ∀n. even (suc n) ⇔ ¬even n
⊦ ∀m. m ≤ 0 ⇔ m = 0
⊦ ∀t1 t2. (if ⊥ then t1 else t2) = t2
⊦ ∀t1 t2. (if ⊤ then t1 else t2) = t1
⊦ ∀p x. p x ⇒ p ((select) p)
⊦ ∀n. 0 < n ⇔ ¬(n = 0)
⊦ ∀n. bit0 (suc n) = suc (suc (bit0 n))
⊦ ∀f y. (let x ← y in f x) = f y
⊦ ∀x y. x = y ⇔ y = x
⊦ ∀t1 t2. t1 ∨ t2 ⇔ t2 ∨ t1
⊦ ∀m n. m + n = n + m
⊦ ∀m n. m + n - m = n
⊦ ∀m n. m + n - n = m
⊦ ∀n. 2 * n = n + n
⊦ ∀m n. ¬(m < n ∧ n ≤ m)
⊦ ∀m n. ¬(m ≤ n ∧ n < m)
⊦ ∀m n. ¬(m < n) ⇔ n ≤ m
⊦ ∀m n. ¬(m ≤ n) ⇔ n < m
⊦ ∀m n. suc m ≤ n ⇔ m < n
⊦ ∀m. m = 0 ∨ ∃n. m = suc n
⊦ ∀p. (∀b. p b) ⇔ p ⊤ ∧ p ⊥
⊦ (∧) = λp q. (λf. f p q) = λf. f ⊤ ⊤
⊦ ∀p. ¬(∀x. p x) ⇔ ∃x. ¬p x
⊦ ∀p. ¬(∃x. p x) ⇔ ∀x. ¬p x
⊦ (∃) = λp. ∀q. (∀x. p x ⇒ q) ⇒ q
⊦ ∀t1 t2. ¬(t1 ⇒ t2) ⇔ t1 ∧ ¬t2
⊦ ∀m n. m + suc n = suc (m + n)
⊦ ∀m n. suc m + n = suc (m + n)
⊦ ∀m n. m < m + n ⇔ 0 < n
⊦ ∀m n. n < m + n ⇔ 0 < m
⊦ ∀m n. suc m = suc n ⇔ m = n
⊦ ∀m n. suc m ≤ suc n ⇔ m ≤ n
⊦ ∀r s. subrelation r s ∧ wellFounded s ⇒ wellFounded r
⊦ ∀t1 t2. ¬(t1 ∧ t2) ⇔ ¬t1 ∨ ¬t2
⊦ ∀m n. even (m * n) ⇔ even m ∨ even n
⊦ ∀m n. even (m + n) ⇔ even m ⇔ even n
⊦ ∀m n. m ≤ n ⇔ ∃d. n = m + d
⊦ (∨) = λp q. ∀r. (p ⇒ r) ⇒ (q ⇒ r) ⇒ r
⊦ ∀m n. m ≤ n ⇔ m < n ∨ m = n
⊦ ∀m n. n ≤ m ⇒ m - n + n = m
⊦ ∀m n. m ≤ n ∧ n ≤ m ⇔ m = n
⊦ ∀PAIR'. ∃fn. ∀a0 a1. fn (a0, a1) = PAIR' a0 a1
⊦ ∀m n. m < n ⇔ ∃d. n = m + suc d
⊦ ∀p q. (∀x. p ∨ q x) ⇔ p ∨ ∀x. q x
⊦ ∀p q. (∃x. p ∧ q x) ⇔ p ∧ ∃x. q x
⊦ ∀p q. p ∧ (∀x. q x) ⇔ ∀x. p ∧ q x
⊦ ∀p q. p ∧ (∃x. q x) ⇔ ∃x. p ∧ q x
⊦ ∀p q. p ∨ (∀x. q x) ⇔ ∀x. p ∨ q x
⊦ ∀p q. p ∨ (∃x. q x) ⇔ ∃x. p ∨ q x
⊦ ∀p q. (∃x. p x) ∧ q ⇔ ∃x. p x ∧ q
⊦ ∀p q. (∃x. p x) ∨ q ⇔ ∃x. p x ∨ q
⊦ ∀t1 t2 t3. (t1 ∧ t2) ∧ t3 ⇔ t1 ∧ t2 ∧ t3
⊦ ∀t1 t2 t3. (t1 ∨ t2) ∨ t3 ⇔ t1 ∨ t2 ∨ t3
⊦ ∀m n p. m + (n + p) = m + n + p
⊦ ∀m n p. m + p = n + p ⇔ m = n
⊦ ∀m n p. m + n < m + p ⇔ n < p
⊦ ∀m n p. m + n ≤ m + p ⇔ n ≤ p
⊦ ∀m n p. m + p ≤ n + p ⇔ m ≤ n
⊦ ∀m n p. m < n ∧ n < p ⇒ m < p
⊦ ∀m n p. m < n ∧ n ≤ p ⇒ m < p
⊦ ∀m n p. m ≤ n ∧ n < p ⇒ m < p
⊦ ∀m n p. m ≤ n ∧ n ≤ p ⇒ m ≤ p
⊦ ∀p. (∀x. ∃y. p x y) ⇔ ∃y. ∀x. p x (y x)
⊦ ∀m n. m ≤ suc n ⇔ m = suc n ∨ m ≤ n
⊦ ∀m n. m * n = 0 ⇔ m = 0 ∨ n = 0
⊦ ∀m n. m + n = 0 ⇔ m = 0 ∧ n = 0
⊦ ∀P. P 0 ∧ (∀n. P n ⇒ P (suc n)) ⇒ ∀n. P n
⊦ ∀r s. subrelation r s ⇔ ∀x y. r x y ⇒ s x y
⊦ (∃!) = λp. (∃) p ∧ ∀x y. p x ∧ p y ⇒ x = y
⊦ ∀b f x y. f (if b then x else y) = if b then f x else f y
⊦ ∀P. (∀n. (∀m. m < n ⇒ P m) ⇒ P n) ⇒ ∀n. P n
⊦ ∀p g h. ∃f. ∀x. f x = if p x then f (g x) else h x
⊦ ∀p q. (∀x. p x ∧ q x) ⇔ (∀x. p x) ∧ ∀x. q x
⊦ ∀p q. (∀x. p x ⇒ q x) ⇒ (∀x. p x) ⇒ ∀x. q x
⊦ ∀p q. (∀x. p x ⇒ q x) ⇒ (∃x. p x) ⇒ ∃x. q x
⊦ ∀p q. (∃x. p x) ∨ (∃x. q x) ⇔ ∃x. p x ∨ q x
⊦ ∀m n p. m * n = m * p ⇔ m = 0 ∨ n = p
⊦ ∀m n p. m * n ≤ m * p ⇔ m = 0 ∨ n ≤ p
⊦ ∀m n p. m * n < m * p ⇔ ¬(m = 0) ∧ n < p
⊦ ∀p1 p2 q1 q2. (p1 ⇒ p2) ∧ (q1 ⇒ q2) ⇒ p1 ∧ q1 ⇒ p2 ∧ q2
⊦ ∀p1 p2 q1 q2. (p2 ⇒ p1) ∧ (q1 ⇒ q2) ⇒ (p1 ⇒ q1) ⇒ p2 ⇒ q2
⊦ ∀p c x y. p (if c then x else y) ⇔ (c ⇒ p x) ∧ (¬c ⇒ p y)
⊦ ∀NIL' CONS'.
∃fn. fn [] = NIL' ∧ ∀a0 a1. fn (a0 :: a1) = CONS' a0 a1 (fn a1)
⊦ ∀r. wellFounded r ⇔ ∀p. (∀x. (∀y. r y x ⇒ p y) ⇒ p x) ⇒ ∀x. p x