Debian Codegraph @

examples/ordinals/FAN/bar.scm

raw
1
2 ; (load "~/minlog/init.scm")
3
4
5 (display "
6 Begin of bar.scm
7
8 In this file we define notions like (decidable) tree, path, bar etc.
9
10 We load first positive.scm
11 ")
12
13
14 (exload "FAN/positive.scm")
15
16 (begin
17 (display "
18
19 In positive.scm we defined:
20
21 ")
22 (display-constructors "pos")
23
24 (display-constructors "upos")
25
26 (display"
27
28 Binary relation < on pos
29
30 Binary relation ◁ on upos
31
32
33 ₂ : upos -> pos
34
35 ")
36 (display-program-constants "uposposTwoexp")
37 )
38
39
40
41 (begin
42 (display "
43
44 Above k ≼ n states that node k is above node n
45
46 ")
47 (add-program-constant
48 "Above"
49 (mk-arrow (py "pos") (py "pos") (py "boole"))
50 1 'const 2
51 )
52 (add-token
53 "≼"
54 'rel-op
55 (lambda (x y)
56 (mk-term-in-app-form
57 (make-term-in-const-form (pconst-name-to-pconst "Above")) x y)))
58 (add-display
59 (py "boole")
60 (lambda (x)
61 (let* ((op (term-in-app-form-to-final-op x))
62 (args (term-in-app-form-to-args x)))
63 (if (and (term-in-const-form? op)
64 (string=? "Above"
65 (const-to-name (term-in-const-form-to-const op)))
66 (= 2 (length args)))
67 (list 'rel-op "≼"
68 (term-to-token-tree (car args))
69 (term-to-token-tree (cadr args)))
70 #f))))
71 ; Computation Rules For Above
72 (add-computation-rule (pt "1≼pos")(pt "True"))
73
74 (add-computation-rule (pt "SZero pos≼1")(pt "False"))
75 (add-computation-rule (pt "SZero pos1≼SZero pos2")(pt "pos1=pos2 ∨ SZero pos1≼pos2"))
76 (add-computation-rule (pt "SZero pos1≼SOne pos2")(pt "SZero pos1≼pos2"))
77
78 (add-computation-rule (pt "SOne pos≼1")(pt "False"))
79 (add-computation-rule (pt "SOne pos1≼SZero pos2")(pt "SOne pos1≼pos2"))
80 (add-computation-rule (pt "SOne pos1≼SOne pos2")(pt "pos1=pos2 ∨ SOne pos1≼pos2"))
81
82 (display-program-constants "Above")
83
84 (display"
85
86 Test of Above ≼:
87
88 ")
89 (display "Above 5 11 ")
90 (pnt"Above 5 11")
91 (display "Above 10 23 ")
92 (pnt"Above 10 23")
93 (display "Above 11 21 ")
94 (pnt"Above 11 21")
95 (display "Above 42 42 ")
96 (pnt"Above 42 42")
97 (display "Above 1024 1023 ")
98 (pnt"Above 1024 1023"))
99
100
101
102 (begin
103
104 (display "
105
106 ℓ k is the length of the sequence at node k.
107
108 ")
109
110
111 (add-program-constant
112 "ℓ"
113 (mk-arrow (py "pos") (py "upos"))
114 1 'const 1
115 )
116
117
118
119 ; Computation Rules For ℓ
120
121 (add-computation-rule (pt "ℓ 1")(pt "Unum"))
122 (add-computation-rule (pt "ℓ (SZero pos)")(pt "SUCC(ℓ pos)"))
123 (add-computation-rule (pt "ℓ (SOne pos)")(pt "SUCC(ℓ pos)"))
124
125 (display-program-constants "ℓ")
126
127
128 (display"
129
130 Test of length ℓ:
131
132 ")
133
134 (display "ℓ 5 ")
135 (pnt"Upostopos(ℓ 5)")
136 (display "ℓ 10 ")
137 (pnt"Upostopos(ℓ 10)")
138 (display "ℓ 11 ")
139 (pnt"Upostopos(ℓ 11)")
140 (display "ℓ 42 ")
141 (pnt"Upostopos(ℓ 42)")
142 (display "ℓ 1024 ")
143 (pnt"Upostopos(ℓ 1024)")
144
145 )
146
147
148
149 (display "
150
151 ∀n. ℓn = 1 -> n = 1
152
153
154 PROOF:
155 ")
156 (sg "ℓ pos=Unum → pos=1")
157 (cases)
158 (auto)
159 ; Proof finished.
160 (nrw "ℓ pos=Unum → pos=1")
161
162
163
164
165 (display "
166
167 ∀n. ℓ(2ⁿ) = n+1
168
169 ")
170 (sg "ℓ(₂ upos)=SUCC upos")
171 (ind)
172 (auto)
173 ; Proof finished.
174 (add-rewrite-rule(pt"ℓ(₂ upos)")(pt"SUCC upos"))
175
176
177
178
179 (display "
180
181 ∀n,k. ℓn ◁ ℓk → n < k
182
183 ")
184 (sg "(ℓ pos1 ◁ ℓ pos2) → (pos1<pos2)")
185 (begin
186 (ind)
187 (cases)
188 (auto)
189 (assume "pos1" "IH1")
190 (cases)
191 (auto)
192 (assume "pos2")
193 (ng #t)
194 (cd "ℓpos1◁ ℓpos2" "l1<l2")
195 (use "BooleImp" (pt"pos1<pos2"))
196 (auto)
197 (use "BooleImp" (pt"ℓpos1◁ ℓpos2"))
198 (auto)
199 (assume "pos1" "IH1")
200 (cases)
201 (auto))
202 ; Proof finished.
203 (nrw "(ℓ pos1 ◁ ℓ pos2) → (pos1<pos2)")
204
205
206 (display "
207
208 ∀n ℓn ◁ k ⇔ 2n < 2^k
209
210 ")
211 (sg "(ℓpos◁upos)=(SZero pos< ₂upos)")
212 (begin
213 (ind)
214 (cases)
215 (auto)
216 (assume "pos" "IH")
217 (cases)
218 (auto)
219 (assume "pos" "IH")
220 (cases)
221 (auto))
222 ; Proof finished.
223 (add-rewrite-rule(pt"ℓpos◁upos")(pt"SZero pos< ₂upos"))
224
225
226 (display "
227
228 ∀n ℓn = k ⇔ 2^k ≤ 2n < 2^(k+1))
229
230 ")
231 (sg "all upos,pos.(ℓpos=upos)=(₂upos ≤ SZero pos ∧ SZero pos< ₂(SUCC upos))")
232 (assume "upos" "pos")
233 (simp (pf"all upos1,upos2.(upos1=upos2)=(¬(upos1◁upos2) ∧ upos1◁SUCC upos2)"))
234 (auto)
235 ; Proof finished.
236 (save "lengthequal")
237 (display-theorems "lengthequal")
238
239
240
241 (begin
242 (av "f" "g" "h" "b" (mk-arrow (py "pos") (py "boole")))
243
244 (display "
245 We define the subsetrelation ⊆(f,g):
246
247 ")
248 (define(⊆ function1 function2)
249 (string-append "all pos.(" function1 " pos) → (" function2 " pos)"))
250 (pp(pf(⊆ "f" "g")))
251 (display "
252
253
254 We define ∞(f) as follows:
255
256 ")
257 (define(∞ function)
258 (string-append "all upos.ex pos.( ℓ(pos) = upos ∧ (" function " pos))"))
259
260 (pp(pf(∞ "f")))
261 (display "
262
263
264 We define TREE(f) as follows:
265
266 ")
267 (define(TREE function)
268 (string-append "all pos.(" function "(SZero pos) → " function " pos) ∧ ("
269 function "(SOne pos) → " function " pos)"))
270 (pp(pf(TREE "f")))
271 (display "
272
273
274 We define PATH(f) as follows:
275
276 ")
277 (define(PATH function)
278 (string-append "all pos1,pos2.(" function " 1) ∧ ((("
279 function " pos1) ∧ (" function " pos2)) → (pos1≼pos2 ∨ pos2≼pos1))"))
280 (pp(pf(PATH "f")))
281 (display "
282
283
284 We define BAR(f) as follows:
285
286 ")
287 (define(BAR function) (string-append
288 "(all pos.(" function " pos) → ( (" function " (SZero pos)) ∧ (" function " (SOne pos)) )) & (all g. ("
289 (PATH "g") ") -> (" (∞ "g") ")-> ex pos. (g pos) ∧ (" function " pos))"))
290
291 (pp(pf(BAR "f"))))
292
293
294
295 (begin
296 (display "
297
298 The Complement f∖g
299
300 ")
301 (add-program-constant
302 "Setminus"
303 (mk-arrow
304 (mk-arrow (py "pos") (py "boole"))
305 (mk-arrow (py "pos") (py "boole"))
306 (mk-arrow (py "pos") (py "boole")))
307 1 'const 2)
308 (add-token
309 "∖"
310 'rel-op
311 (lambda (x y)
312 (mk-term-in-app-form
313 (make-term-in-const-form (pconst-name-to-pconst "Setminus")) x y)))
314 (add-display
315 (mk-arrow (py "pos") (py "boole"))
316 (lambda (x)
317 (let* ((op (term-in-app-form-to-final-op x))
318 (args (term-in-app-form-to-args x)))
319 (if (and (term-in-const-form? op)
320 (string=? "Setminus"
321 (const-to-name (term-in-const-form-to-const op)))
322 (= 2 (length args)))
323 (list 'rel-op "∖"
324 (term-to-token-tree (car args))
325 (term-to-token-tree (cadr args)))
326 #f))))
327 ; Computation Rules For Setminus
328 (add-computation-rule (pt "f ∖ g")(pt "[pos] f pos ∧ ¬(g pos)"))
329
330 (display-program-constants "Setminus"))
331
332
333
334 (begin
335 (display "
336
337 The Union f∪g
338
339 ")
340 (add-program-constant
341 "Union"
342 (mk-arrow
343 (mk-arrow (py "pos") (py "boole"))
344 (mk-arrow (py "pos") (py "boole"))
345 (mk-arrow (py "pos") (py "boole")))
346 1 'const 2)
347 (add-token
348 "∪"
349 'rel-op
350 (lambda (x y)
351 (mk-term-in-app-form
352 (make-term-in-const-form (pconst-name-to-pconst "Union")) x y)))
353 (add-display
354 (mk-arrow (py "pos") (py "boole"))
355 (lambda (x)
356 (let* ((op (term-in-app-form-to-final-op x))
357 (args (term-in-app-form-to-args x)))
358 (if (and (term-in-const-form? op)
359 (string=? "Union"
360 (const-to-name (term-in-const-form-to-const op)))
361 (= 2 (length args)))
362 (list 'rel-op "∪"
363 (term-to-token-tree (car args))
364 (term-to-token-tree (cadr args)))
365 #f))))
366 ; Computation Rules For Union
367 (add-computation-rule (pt "f ∪ g")(pt "[pos] f pos ∨ g pos"))
368 (display-program-constants "Union"))
369
370
371
372
373 (sg "(pos<(₂(SUCC upos)) ∧ ¬((f∪([pos]ℓpos◁SUCC upos)) pos)) = (([pos]ℓpos=SUCC upos)∖f)pos")
374 (begin
375 (assume "pos" "upos" "f")
376 (ng)
377 (cd "ℓpos=SUCC upos" "ln=k+1")
378 (ng #t)
379 (cd "f pos" "fn")
380 (use "Truth-Axiom")
381 (assume "¬fn")
382 (ng)
383 (simp "<-" (pf"(ℓpos ◁ (SUCC (SUCC upos))) = (pos< SZero(₂ upos))"))
384 (simp "ln=k+1")
385 (simp "<-" (pf"(ℓpos ◁ SUCC upos) = (pos< (₂ upos))"))
386 (simp "ln=k+1")
387 (auto)
388 (assume "ln≠k+1")
389 (ng #t)
390 (cd "f pos" "fn")
391 (use "Truth-Axiom")
392 (assume "¬fn")
393 (ng)
394 (simp "<-" (pf"(ℓpos ◁ (SUCC (SUCC upos))) = (pos< SZero(₂ upos))"))
395 (simp "<-" (pf"(ℓpos ◁ SUCC upos) = (pos< (₂ upos))"))
396 (simp (pf "all upos1,upos2.(upos1◁SUCC upos2)=( (upos1◁upos2) ∨ (upos1=upos2) )"))
397 (simp "ln≠k+1")
398 (use "Truth-Axiom")
399 (use "uposlessS1")
400 (auto))
401 ; Proof finished.
402 (add-rewrite-rule
403 (pt "pos<(₂(SUCC upos)) ∧ ¬((f∪([pos]ℓpos◁SUCC upos)) pos)")
404 (pt "(([pos]ℓpos=SUCC upos)∖f)pos"))
405
406
407 (begin
408
409 (display "
410
411 TOT (f,n) = True iff f contains all nodes below n.
412
413 ")
414 (add-program-constant
415 "TOT"
416 (mk-arrow (mk-arrow (py "pos") (py "boole")) (py "upos") (py "boole"))
417 1 'const 2)
418 ; Computation Rules For TOT
419 (add-computation-rule (pt "TOT f Unum")(pt "True"))
420 (add-computation-rule (pt "TOT f (SUCC upos)")(pt "TOT f upos ∧ f(Upostopos upos)"))
421
422 (display-program-constants "TOT")
423
424 (display "TOT f Unum ")
425 (pnt "TOT f Unum")
426 (display "TOT f (SUCC Unum) ")
427 (pnt "TOT f (SUCC Unum)")
428 (display "TOT f (Postoupos 10) ")
429 (pnt "TOT f (Postoupos 10)"))
430
431
432
433 (sg "all f,upos.( f(Upostopos upos) ∧ TOT f upos ) → (TOT f (SUCC upos))")
434 (begin
435 (assume "f")
436 (ind)
437 (use "Truth-Axiom")
438 (assume "upos")
439 (ng)
440 (cases (pt"f(Upostopos upos+1)"))
441 (auto))
442 ; Proof finished
443 (nrw "( f(Upostopos upos) ∧ TOT f upos ) → (TOT f (SUCC upos))")
444 (nrw "( TOT f upos ∧ f(Upostopos upos)) → (TOT f (SUCC upos))")
445
446
447
448 (display "
449 (TOT f upos ∧ pos<Upostopos upos) → f pos
450
451 ")
452 (sg "all f,upos,pos. (TOT f upos ∧ pos<Upostopos upos) → f pos")
453 (begin
454 (assume"f")
455 (ind)
456 (search)
457 (assume "upos" "IH" "pos")
458 (ng #t)
459 (cds "Upostopos upos=pos" "n=k")
460 (cases(pt "f pos"))
461 (auto)
462 (assume "n≠k")
463 (cd "f (Upostopos upos)" "fn")
464 (ng #t)
465 (simp "posLE_LESSorEQUAL")
466 (simp "posEQsym" (pt"pos"))
467 (simp "n≠k")
468 (auto))
469 ; Proof finished.
470 (nrw "(TOT f upos ∧ pos<Upostopos upos) → f pos")
471 (nrw "(pos<Upostopos upos ∧ TOT f upos) → f pos")
472
473 (display"
474
475 End of bar.scm
476
477 ")
478
479
480