Debian Codegraph @

examples/ordinals/FAN/positive.scm

raw
1
2 ; positive.scm
3
4 ; (load "~/minlog/init.scm")
5
6 (display"
7 Begin of positive.scm
8
9 ")
10
11
12 (display"
13 First some boolean RW-rules and THMS:
14
15 ")
16
17
18
19
20 (mload "abbrev.scm")
21
22
23
24 (begin
25
26 (define (boole? term)
27 (equal? (term-to-type term) '(alg "boole")))
28
29 ;; CONSTANTS
30
31 (add-token "⊥" 'const (make-term-in-const-form false-const))
32
33 ;; BOOLEAN FUNCTIONS
34
35
36 ; Conjunction ∧
37 ; already define in src/boole.scm
38
39 (define (andboole bl1 bl2)
40 (mk-term-in-app-form
41 (make-term-in-const-form (pconst-name-to-pconst "AndConst")) bl1 bl2))
42
43 (add-token
44 "∧"
45 'and-op
46 (lambda (x y) (andboole x y)))
47
48 (define (and-boole? term)
49 (if (term-in-app-form? term)
50 (let ((op (term-in-app-form-to-final-op term))
51 (args (term-in-app-form-to-args term)))
52 (and (term-in-const-form? op)
53 (string=? "AndConst" (const-to-name (term-in-const-form-to-const op)))
54 (= 2 (length args))))
55 #f))
56
57 (define (and-boole-to-kernel term)
58 (cond ((and-boole? term)
59 (make-term-in-pair-form
60 (term-in-app-form-to-arg (term-in-app-form-to-op term))
61 (term-in-app-form-to-arg term)))
62 (else term)))
63
64 (define (ANDB . booles)
65 (letrec ((andboole (lambda (bt)
66 (cond ((= (length bt) 0) "T")
67 ((= (length bt) 1) (car bt))
68 (else (string-append (car bt) " and " (andboole (cdr bt))))))))
69 (andboole booles)))
70
71
72
73
74 ; Negation ¬
75
76
77 (add-program-constant "¬" (py "boole=>boole") 1)
78
79 (acrs "¬True" "False")
80 (acrs "¬False" "True")
81
82 (set! OLD-COMMENT-FLAG COMMENT-FLAG)
83 (set! COMMENT-FLAG #t)
84 (display-program-constants "¬")
85 (set! COMMENT-FLAG OLD-COMMENT-FLAG)
86
87 (define (negboole x)
88 (mk-term-in-app-form
89 (make-term-in-const-form (pconst-name-to-pconst "¬")) x ))
90
91 (define (neg-boole? term)
92 (and (term-in-app-form? term)
93 (let ((op (term-in-app-form-to-final-op term))
94 (args (term-in-app-form-to-args term)))
95 (and (= 1 (length args))
96 (term-in-const-form? op)
97 (string=? "¬" (const-to-name (term-in-const-form-to-const op)))))))
98
99 (define (neg-boole-to-kernel term)
100 (cond ((neg-boole? term) (car(term-in-app-form-to-args term)))
101 (else term)))
102
103
104
105
106 ; Disjunction p∨q :≡ ¬(¬q ∧ ¬p)
107
108 (define (orboole bl1 bl2)
109 (negboole
110 (mk-term-in-app-form
111 (mk-term-in-app-form
112 (make-term-in-const-form(pconst-name-to-pconst "AndConst"))
113 (negboole bl1)
114 (negboole bl2)))))
115
116 (add-token
117 "∨"
118 'or-op
119 (lambda (x y) (orboole x y)))
120
121 (define (or-boole? term)
122 (and (neg-boole? term)
123 (term-in-app-form? (neg-boole-to-kernel term))
124 (let ((op (term-in-app-form-to-op (neg-boole-to-kernel term))))
125 (and (term-in-app-form? op)
126 (string=? (term-to-string(term-in-app-form-to-op op))
127 "AndConst")
128 (neg-boole? (term-in-app-form-to-arg op))
129 (neg-boole? (term-in-app-form-to-arg (neg-boole-to-kernel term)))))))
130
131 (define (or-boole-to-kernel term)
132 (cond ((or-boole? term)
133 (let ((conjunct (neg-boole-to-kernel term)))
134 (make-term-in-pair-form
135 (neg-boole-to-kernel
136 (term-in-app-form-to-arg
137 (term-in-app-form-to-op conjunct)))
138 (neg-boole-to-kernel(term-in-app-form-to-arg conjunct)))))
139 (else term)))
140
141
142
143 ; ORB: boolean disjunction
144
145 (define (ORB . booles)
146 (letrec ((disjunction (lambda (bt)
147 (cond ((= (length bt) 0) "False")
148 ((= (length bt) 1) (car bt))
149 (else (string-append "( " (car bt) " ) ∨ ( " (disjunction (cdr bt)) " ) "))))))
150 (disjunction booles)))
151
152
153
154
155
156 ; Implication p→q :≡ ¬(p ∧ ¬q)
157
158 (define (impboole bl1 bl2)
159 (negboole
160 (mk-term-in-app-form
161 (mk-term-in-app-form
162 (make-term-in-const-form(pconst-name-to-pconst "AndConst"))
163 bl1 (negboole bl2)))))
164
165 (add-token
166 "→"
167 'or-op
168 (lambda (x y) (impboole x y)))
169
170 (define (imp-boole? term)
171 (and (neg-boole? term)
172 (and-boole? (neg-boole-to-kernel term))
173 (neg-boole? (term-in-pair-form-to-right(and-boole-to-kernel (neg-boole-to-kernel term))))))
174
175
176 (define (imp-boole-to-kernel term)
177 (cond ((imp-boole? term)
178 (let ((conjunct (and-boole-to-kernel(neg-boole-to-kernel term))))
179 (make-term-in-pair-form
180 (term-in-pair-form-to-left conjunct)
181 (neg-boole-to-kernel(term-in-pair-form-to-right conjunct)))))
182 (else term)))
183
184
185
186
187 ; DISPLAY
188
189 (add-display
190 (py "boole")
191 (lambda (x)
192 (cond ((or-boole? x)
193 (let* ((args (or-boole-to-kernel x)))
194 (list 'or-op "∨"
195 (term-to-token-tree (term-in-pair-form-to-left args))
196 (term-to-token-tree (term-in-pair-form-to-right args)))))
197 ((imp-boole? x)
198 (let* ((args (imp-boole-to-kernel x)))
199 (list 'imp-op "→"
200 (term-to-token-tree (term-in-pair-form-to-left args))
201 (term-to-token-tree (term-in-pair-form-to-right args)))))
202 ((and-boole? x)
203 (let* ((args (term-in-app-form-to-args x)))
204 (list 'and-op "∧"
205 (term-to-token-tree (car args))
206 (term-to-token-tree (cadr args)))))
207 (else #f))))
208
209
210
211 ; TO ADD RW-RULES
212
213 (define (trw string)
214 (if (boole? (pt string))
215 (arw string "True")
216 (myerror "trw: Boolean term expected !")))
217
218
219 (define (nrw string)
220 (let ((term (pt string))
221 (free-avar (proof-to-free-avars(pproof-state-to-proof))))
222 (cond ((null? PPROOF-STATE)
223 (myerror "arw" "proof under construction expected"))
224 ((not(null? free-avar))
225 (myerror (cons "unexpected free assumptions" free-avar)))
226 ((not (neg-boole? term))
227 (myerror "nrw: Negated boole expected !"))
228 (else
229 (add-rewrite-rule (neg-boole-to-kernel term) (pt "False"))))))
230
231 )
232
233
234
235
236 (set! OLD-COMMENT-FLAG COMMENT-FLAG)
237 (set! COMMENT-FLAG #f)
238
239 ; Trivial but important
240
241 (begin
242
243 ; True=boole = boole
244 (sg "(True=boole)=boole")
245 (cases)
246 (auto)
247 ; Proof finished.
248 (save "BooleTrueLeft")
249 (display-theorems "BooleTrueLeft")
250
251
252 ; boole=True = boole
253 (sg "(boole=True)=boole")
254 (cases)
255 (auto)
256 ; Proof finished.
257 (save "BooleTrueRight")
258 (display-theorems "BooleTrueRight")
259
260
261 ; boole=False = ¬boole
262 (sg "(boole=False)=(¬boole)")
263 (cases)
264 (auto)
265 ; Proof finished.
266 (save "BooleFalseRight")
267 (display-theorems "BooleFalseRight")
268
269 ; ¬boole = boole=False
270 (sg "(False=boole)=(¬boole)")
271 (cases)
272 (auto)
273 ; Proof finished.
274 (save "BooleFalseLeft")
275 (display-theorems "BooleFalseLeft")
276
277
278 ; (p -> False) -> ¬p
279 (sg "(boole->False)->(¬boole)")
280 (cases)
281 (auto)
282 ; Proof finished.
283 (save "BooleNegationTwo")
284 (display-theorems "BooleNegationTwo")
285
286 ; p ∧ q = q ∧ p
287 (sg "(boole1∧boole2)=(boole2∧boole1)")
288 (cases)
289 (auto)
290 ; Proof finished.
291 (save "ANDcomm")
292 (display-theorems "ANDcomm")
293
294
295 ; Efq-Boole: ¬p -> p -> q
296
297 (sg "¬boole1 -> boole1 -> boole2")
298 (cases)
299 (cases)
300 (auto)
301 (assume "boole2" "Verum")
302 (use "Efq-Atom")
303 ; Proof finished.
304 (save "Efq-Boole")
305 (display-theorems "Efq-Boole")
306
307 )
308
309
310 (display "
311
312 Some boolean RW-RULES
313
314 ")
315
316 (begin
317
318 (sg "boole=False∨boole=True")
319 (cases)
320 (auto)
321 ; Proof finished.
322 (nrw "boole=False∨boole=True")
323
324 (sg "boole=True∨boole=False")
325 (cases)
326 (auto)
327 ; Proof finished.
328 (nrw "boole=True∨boole=False")
329
330 ; ¬¬boole → boole
331
332 (sg "¬(¬boole) = boole")
333 (cases)
334 (auto)
335 ; Proof finished.
336 (arw "¬(¬boole)" "boole")
337
338
339
340
341 ; p ∨ p=False
342 (sg "boole∨boole=False")
343 (cases)
344 (auto)
345 ; Proof finished.
346 (nrw "boole∨boole=False")
347
348
349
350 ; ¬ ( p ∧ ¬p)
351 (sg "¬(boole ∧ ¬boole)")
352 (cases)
353 (auto)
354 ; Proof finished.
355 (nrw "¬(boole ∧ ¬boole)")
356
357 (sg "¬(¬boole ∧ boole)")
358 (cases)
359 (auto)
360 ; Proof finished.
361 (nrw "¬(¬boole ∧ boole)")
362
363 ; ¬(¬p ∧ q ∧ p)
364 (sg "¬(¬boole1∧boole2∧boole1)")
365 (cases)
366 (auto)
367 ; Proof finished.
368 (nrw "¬(¬boole1∧boole2∧boole1)")
369
370
371
372
373 ; iff
374 (sg "((boole1→boole2) ∧ (boole2→boole1))=(boole1=boole2)")
375 (cases)
376 (cases)
377 (auto)
378 (cases)
379 (auto)
380 ; Proof finished.
381 (arw "(boole1→boole2) ∧ (boole2→boole1)"
382 "boole1=boole2")
383
384
385
386 ; (p ∧ q) ∧ q = p ∧ q
387 (sg "(boole1 ∧ boole2 ∧ boole2)=(boole1 ∧ boole2)")
388 (cases)
389 (auto)
390 ;Proof finished.
391 (arw "boole1 ∧ boole2 ∧ boole2" "boole1 ∧ boole2")
392
393
394
395 ; p∧(q∧r) = p∧q∧r
396 (sg "all boole1,boole2,boole3.(boole1∧(boole2∧boole3))=(boole1∧boole2∧boole3)")
397 (cases)
398 (auto)
399 ; Proof finished.
400 (arw "boole1∧(boole2∧boole3)"
401 "boole1∧boole2∧boole3")
402
403
404
405
406
407 ; ¬( p ∧ ¬q ∧ q )
408 (sg "all boole1.¬(boole1 ∧ ¬boole2 ∧ boole2)")
409 (cases)
410 (auto)
411 ; Proof finished.
412 (nrw "¬(boole1 ∧ ¬boole2 ∧ boole2)")
413
414
415
416
417
418 ; p∨(q∨r) = p∨q∨r
419 (sg "all boole1,boole2,boole3.(boole1∨(boole2∨boole3))=(boole1∨boole2∨boole3)")
420 (cases)
421 (auto)
422 ; Proof finished.
423 (arw "boole1∨(boole2∨boole3)"
424 "boole1∨boole2∨boole3")
425
426
427
428
429
430 ; (p→q)∧q = q
431 (sg "((boole1→boole2)∧boole2)=boole2")
432 (cases)
433 (auto)
434 ; Proof finished.
435 (arw "(boole1→boole2)∧boole2"
436 "boole2")
437
438
439
440 ; q∧(p→q) = q
441 (sg "(boole2∧(boole1→boole2))=boole2")
442 (cases)
443 (auto)
444 ; Proof finished.
445 (arw "boole2∧(boole1→boole2)" "boole2")
446
447
448
449
450
451
452 ; ((p→q)∧p) = p∧q
453 (sg "((boole1→boole2)∧boole1)=(boole2∧boole1)")
454 (cases)
455 (auto)
456 ; Proof finished.
457 (arw "(boole1→boole2)∧boole1" "boole2∧boole1")
458
459
460
461
462
463 ; (p∧(p→q))→q
464 (sg "(boole1 ∧ (boole1→boole2)) = (boole1∧boole2)")
465 (cases)
466 (auto)
467 ; Proof finished.
468 (arw "boole1∧(boole1→boole2)" "boole1∧boole2")
469
470
471 ; (p ∧ q) → p
472 (sg "(boole1∧boole2)→boole1")
473 (cases)
474 (auto)
475 ; Proof finished.
476 (nrw "(boole1∧boole2)→boole1")
477
478
479
480 ; (p ∧ q) → q
481 (sg "(boole1∧boole2)→boole2")
482 (cases)
483 (auto)
484 ; Proof finished.
485 (nrw "(boole1∧boole2)→boole2")
486
487
488 ; (p ∧ q ∧ r) → p
489 (sg "(boole1∧boole2∧boole3)→boole1")
490 (cases)
491 (auto)
492 ; Proof finished.
493 (nrw "(boole1∧boole2∧boole3)→boole1")
494
495
496
497
498 ; ( (p→q) ∧ (q→r) ∧ p ) → r
499 (sg "(boole1→boole2)∧(boole2→boole3)∧boole1→boole3")
500 (cases)
501 (auto)
502 ; Proof finished.
503 (nrw "(boole1→boole2)∧(boole2→boole3)∧boole1→boole3")
504
505
506 ; ∧-transitivity follows from:
507 (sg "all boole1,boole3.boole1∧boole2∧boole3→boole1∧boole3")
508 (cases)
509 (auto)
510 ; Proof finished.
511 (nrw "boole1∧boole2∧boole3→boole1∧boole3")
512
513
514 ; (p → q) → ((p∧r)→ q)
515 (sg "all boole2,boole3.(boole2→boole3)∧boole1∧boole2→boole3")
516 (cases)
517 (auto)
518 ; Proof finished.
519 (nrw "(boole2→boole3)∧boole1∧boole2→boole3")
520
521
522 (sg "boole=True→boole")
523 (cases)
524 (auto)
525 ; Proof finished.
526 (nrw "boole=True→boole")
527
528
529 (sg "¬(¬boole=boole)")
530 (cases)
531 (auto)
532 ; Proof finished.
533 (trw "¬(¬boole=boole)")
534
535
536 ; (¬p ∧ q) ∨ p = p ∨ q
537 (sg "((¬boole1∧boole2)∨boole1)=(boole1∨boole2)")
538 (cases)
539 (auto)
540 ; Proof finished.
541 (arw "(¬boole1∧boole2)∨boole1" "boole1∨boole2")
542
543
544 (sg "(¬(¬boole1∧boole2))=boole2→boole1")
545 (cases)
546 (auto)
547 ; Proof finished.
548 ; (arw "¬(¬boole1∧boole2)" "boole2→boole1")
549
550
551 (sg "all boole1.[if boole1 boole2 False]→boole1")
552 (cases)
553 (auto)
554 ; Proof finished.
555 (nrw "[if boole1 boole2 False]→boole1")
556
557
558 (sg "all boole1.[if boole1 boole2 False]→boole2")
559 (cases)
560 (auto)
561 ; Proof finished.
562 (nrw "[if boole1 boole2 False]→boole2")
563
564
565
566
567
568 (sg "boole2∧boole1→boole1∧boole2")
569 (cases)
570 (auto)
571 ; Proof finished.
572 (nrw "boole2∧boole1→boole1∧boole2")
573
574
575 (display "
576
577 End of RW -RULES
578
579 ")
580 )
581
582
583
584 ; FROM BOOLES TO FORMULAE
585
586 (begin
587
588 ; BooleImp: ( p→q ) -> p -> q
589
590 (sg "all boole1,boole2.
591 ((boole1→boole2)->boole1->boole2)
592 & ((boole1->boole2)->(boole1→boole2))")
593 (cases)
594 (auto)
595 (cases)
596 (auto)
597 ; Proof finished.
598 (save "BooleImp")
599 (display-theorems "BooleImp")
600
601 (define (booleimp termstring)
602 (use "BooleImp" (pt termstring)))
603
604
605
606 (define (ass hypstring)
607 (let* ((err "ass: Goal formula must be a boolean implication !!!")
608 (gf (goal-to-formula(current-goal))))
609 (if (atom-form? gf)
610 (let* ((gb (atom-form-to-kernel gf)))
611 (if (imp-boole? gb)
612 (begin (set! OLD-COMMENT-FLAG COMMENT-FLAG)
613 (set! COMMENT-FLAG #f)
614 (use "BooleImp" 'right)
615 (set! COMMENT-FLAG OLD-COMMENT-FLAG)
616 (newline)
617 (assume hypstring))
618 (myerror err)))
619 (myerror err))))
620
621
622
623
624 ; BooleImp2: ( (p∧q)→r ) -> p -> q -> r
625
626 (sg "all boole3,boole2,boole1.
627 (((boole1∧boole2)→boole3)->boole1->boole2->boole3)
628 & ((boole1->boole2->boole3) -> (boole1∧boole2)→boole3)")
629 (cases)
630 (auto)
631 (cases)
632 (cases)
633 (auto)
634 ; Proof finished.
635 (save "BooleImp2")
636 (display-theorems "BooleImp2")
637
638
639
640 ; booleimptrans: ( (p→q) ∧ (q→r) ∧ p ) → r
641
642 (sg "(boole1→boole2) -> (boole2→boole3) -> (boole1→boole3)")
643 (assume "boole1" "boole2" "boole3")
644 (cut(pf"(boole1→boole2)∧(boole2→boole3)→(boole1→boole3)"))
645 (use-with "BooleImp2" (pt"boole1→boole3") (pt"boole2→boole3") (pt"boole1→boole2") 'left)
646 (use "Truth-Axiom")
647 ; Proof finished.
648 (save "booleimptrans")
649 (display-theorems "booleimptrans")
650
651
652 ; p ∧ q -> p
653 (set-goal (pf"all boole2,boole1.(boole1 ∧ boole2) -> boole1"))
654 (cases)
655 (search)
656 (cases)
657 (auto)
658 ; Proof finished.
659 (save "AndElimLeft")
660 (display-theorems "AndElimLeft")
661
662
663
664 ; p ∧ q -> q
665 (set-goal (pf"all boole1,boole2.(boole1 ∧ boole2) -> boole2"))
666 (cases)
667 (search)
668 (cases)
669 (auto)
670 ; Proof finished.
671 (save "AndElimRight")
672 (display-theorems "AndElimRight")
673
674
675
676
677 (sg "[if boole1 boole2 False] = (boole1∧boole2)")
678 (cases)
679 (auto)
680 ; Proof finished.
681 (save "booleIfAnd")
682 (display-theorems "booleIfAnd")
683
684
685
686
687
688 (define (trans termstring)
689 (let ((gf (goal-to-formula(current-goal))))
690 (cond ((atom-form? gf)
691 (let ((term (pt termstring)))
692 (cond ((or-boole? (atom-form-to-kernel gf))
693 (let* ((bt (neg-boole-to-kernel(atom-form-to-kernel gf)))
694 (args (term-in-app-form-to-args bt))
695 (lcon (orboole (neg-boole-to-kernel(car args)) term))
696 (rcon (orboole term (neg-boole-to-kernel(cadr args))))
697 (newgoal (andboole lcon rcon)))
698 (use "BooleImp" newgoal)
699 (use "Truth-Axiom")))
700 ((imp-boole? (atom-form-to-kernel gf))
701 (let* ((bt (neg-boole-to-kernel(atom-form-to-kernel gf)))
702 (args (term-in-app-form-to-args bt))
703 (lcon (impboole (car args) term))
704 (rcon (impboole term (neg-boole-to-kernel(cadr args))))
705 (newgoal (andboole lcon rcon)))
706 (use "BooleImp" newgoal)
707 (use "Truth-Axiom")))
708 ((and-boole? (atom-form-to-kernel gf))
709 (let* ((bt (atom-form-to-kernel gf))
710 (args (term-in-app-form-to-args bt))
711 (lcon (andboole (car args) term))
712 (rcon (andboole term (cadr args)))
713 (newgoal (andboole lcon rcon)))
714 (use "BooleImp" newgoal)
715 (use "Truth-Axiom")))
716 ((boole? term) (myerror (string-append "trans: " termstring " is of type boole.")
717 "trans: This is NOT supported (yet)."))
718 (else (if (neg-boole? (atom-form-to-kernel gf))
719 (let* ((bt (neg-boole-to-kernel(atom-form-to-kernel gf)))
720 (args (term-in-app-form-to-args bt))
721 (op (term-in-app-form-to-final-op bt))
722 (rcon (negboole(mk-term-in-app-form op (car args) term)))
723 (lcon (negboole(mk-term-in-app-form op term(cadr args))))
724 (newgoal
725 (mk-term-in-app-form
726 (make-term-in-const-form
727 (pconst-name-to-pconst "AndConst"))
728 lcon rcon)))
729 (use "BooleImp" newgoal)
730 (use "Truth-Axiom"))
731 (let* ((bt (atom-form-to-kernel gf))
732 (args (term-in-app-form-to-args bt))
733 (op (term-in-app-form-to-final-op bt))
734 (lcon (mk-term-in-app-form op (car args) term))
735 (rcon (mk-term-in-app-form op term (cadr args)))
736 (newgoal
737 (mk-term-in-app-form
738 (make-term-in-const-form
739 (pconst-name-to-pconst "AndConst"))
740 lcon rcon)))
741 (use "BooleImp" newgoal)
742 (use "Truth-Axiom")))))))
743 (else (myerror "trans: Goal formula must be an atom !!!")))))
744
745
746 )
747
748
749 (set! COMMENT-FLAG OLD-COMMENT-FLAG)
750
751
752 (begin
753
754 (add-alg "pos"
755 '("One" "pos")
756 '("SZero" "pos=>pos")
757 '("SOne" "pos=>pos"))
758 (display-constructors "pos")
759
760 ; M A K E - N U M E R I C - T E R M
761
762 (define (make-numeric-term k)
763 (cond ((= k 1)
764 (pt "One"))
765 ((even? k)
766 (make-term-in-app-form
767 (pt "SZero")
768 (make-numeric-term (/ k 2))))
769 ((odd? k)
770 (make-term-in-app-form
771 (pt "SOne")
772 (make-numeric-term (/ (- k 1) 2))))
773 (else
774 (myerror "make-numeric-term"
775 "positive integer expected"
776 k))))
777
778
779 (display"
780 Test of (make-numeric-term)
781
782 ")
783 (display " 42 = ")
784 (pp (pt"42"))
785 (display "1024 = ")
786 (pp (pt"1024"))
787
788
789 (define (is-numeric-term? term)
790 (or
791 (and (term-in-const-form? term)
792 (string=? "One"
793 (const-to-name
794 (term-in-const-form-to-const term))))
795 (and (term-in-app-form? term)
796 (let ((op (term-in-app-form-to-op term)))
797 (and (term-in-const-form? op)
798 (let ((name (const-to-name (term-in-const-form-to-const op))))
799 (or (string=? "SZero" name) (string=? "SOne" name)))
800 (is-numeric-term? (term-in-app-form-to-arg term)))))))
801
802 (define (numeric-term-to-number term)
803 (if (equal? term (pt "One"))
804 1
805 (let* ((op (term-in-app-form-to-op term))
806 (arg (term-in-app-form-to-arg term))
807 (name (const-to-name (term-in-const-form-to-const op))))
808 (if (string=? "SZero" name)
809 (* 2 (numeric-term-to-number arg))
810 (+ 1 (* 2 (numeric-term-to-number arg)))))))
811
812
813
814 (display"
815 Test of (numeric-term-to-number)
816
817 ")
818 (display(string-append" 42 = "
819 (number-to-string(numeric-term-to-number(pt "42")))))
820 (display(string-append"
821 1024 = "
822 (number-to-string(numeric-term-to-number (pt "1024")))"
823
824 "))
825 )
826
827
828 (begin
829
830 (sg "(pos1=pos2)=(pos2=pos1)")
831 (assume "pos1" "pos2")
832 (cases (pt"pos1=pos2"))
833 (assume "1=2")
834 (simp "1=2")
835 (auto)
836 (assume "1≠2")
837 (simp(pf"pos2=pos1->F"))
838 (auto)
839 (assume "2=1")
840 (use "1≠2")
841 (simp "2=1")
842 (auto)
843 ; Proof finished.
844 (save "posEQsym")
845 (display-theorems "posEQsym")
846 )
847
848
849
850 (begin
851
852 (add-program-constant
853 "posLESS"
854 (mk-arrow (py "pos") (py "pos") (py "boole"))
855 1 'const 2)
856
857 (add-token
858 "<"
859 'rel-op
860 (lambda (x y)
861 (mk-term-in-app-form
862 (make-term-in-const-form
863 (pconst-name-to-pconst "posLESS")) x y)))
864
865 (add-token
866 "≤"
867 'rel-op
868 (lambda (x y)
869 (negboole
870 (mk-term-in-app-form
871 (make-term-in-const-form
872 (pconst-name-to-pconst "posLESS")) y x))))
873
874 (add-display
875 (py "boole")
876 (lambda (x)
877 (cond ((neg-boole? x)
878 (let* ((op (term-in-app-form-to-final-op(neg-boole-to-kernel x)))
879 (args (term-in-app-form-to-args(neg-boole-to-kernel x))))
880 (if (and (term-in-const-form? op)
881 (string=? "posLESS"
882 (const-to-name (term-in-const-form-to-const op)))
883 (= 2 (length args)))
884 (list 'rel-op "≤"
885 (term-to-token-tree (cadr args))
886 (term-to-token-tree (car args)))
887 #f)))
888 (else
889 (let* ((op (term-in-app-form-to-final-op x))
890 (args (term-in-app-form-to-args x)))
891 (if (and (term-in-const-form? op)
892 (string=? "posLESS"
893 (const-to-name (term-in-const-form-to-const op)))
894 (= 2 (length args)))
895 (list 'rel-op "<"
896 (term-to-token-tree (car args))
897 (term-to-token-tree (cadr args)))
898 #f))))))
899
900 ; Computation Rules For posLESS
901
902 (acrs "pos < 1" "False")
903
904 (acrs "1 < SZero pos" "True" )
905 (acrs "SZero pos1 < SZero pos2" "pos1<pos2")
906 (acrs "SOne pos1 < SZero pos2" "pos1<pos2")
907
908 (acrs "1 < SOne pos" "True")
909 (acrs "SZero pos1 < SOne pos2" "pos1≤pos2")
910 (acrs "SOne pos1 < SOne pos2" "pos1<pos2")
911
912 (display-program-constants "posLESS")
913
914 (display "
915 NOTA BENE ! pos1 ≤ pos2 :≡ ¬(pos2<pos1)
916 ")
917 )
918
919
920 (display "
921
922 Some RW-rules for < and ≤
923
924 ")
925
926 (begin
927
928 (sg "1<pos ∨ 1=pos")
929 (cases)
930 (auto)
931 ; Proof finished.
932 (nrw "1<pos ∨ 1=pos")
933
934
935
936 (display "
937 < is irrflexsive
938 ≤ is reflexsive
939
940 ")
941
942
943 (sg "pos≤pos")
944 (ind)
945 (auto)
946 ; Proof finished.
947 (nrw "pos ≤ pos")
948
949
950 (display "
951 < is antisymmetric
952
953 ")
954 (sg "¬(pos1<pos2 ∧ pos2<pos1)")
955
956 (ind)
957 (search)
958 (assume "pos1" "IH1")
959 (cases)
960 (auto)
961 (assume "pos1" "IH1")
962 (cases)
963 (auto)
964 ; Proof finished.
965 (nrw "¬(pos1<pos2 ∧ pos2<pos1)")
966
967
968 (sg "pos1<pos2→(pos2<pos1)=False")
969 (assume "pos1" "pos2")
970 (cd "pos1<pos2" "1k2")
971 (simp(pf "False=(pos1<pos2 ∧ pos2<pos1)"))
972 (simp "1k2")
973 (use "Truth-Axiom")
974 (simp "BooleFalseLeft")
975 (auto)
976 ; Proof finished.
977 (nrw "pos1<pos2→(pos2<pos1)=False")
978
979
980 (sg "(pos2≤pos1∧pos1≤pos2)→pos1=pos2")
981 (ind)
982 (cases)
983 (auto)
984 (assume "pos1" "IH1")
985 (cases)
986 (auto)
987 (assume "pos1" "IH1")
988 (cases)
989 (auto)
990 ; Proof finished.
991 (nrw "(pos2≤pos1∧pos1≤pos2)→pos1=pos2")
992
993
994 (display "
995 COROLLARY < is linear:
996
997 (pos1<pos2) ∨ (pos2<pos1) ∨ (pos1=pos2) ")
998 (pp(nt(pt"(pos1<pos2) ∨ (pos2<pos1) ∨ (pos1=pos2)")))
999
1000
1001 )
1002
1003
1004
1005
1006
1007
1008
1009 (display "
1010
1011 Extraction of cposMAX: pos@pos -> pos
1012
1013 ")
1014
1015 (begin
1016
1017 (sg "ex pos.pos1≤pos ∧ ((pos2<pos ∧ pos1=pos) ∨ (pos=pos2))")
1018 (assume "pos1" "pos2")
1019 (cases(pt"pos1<pos2"))
1020 (assume "1<2")
1021 (ex-intro(pt"pos2"))
1022 (ng #t)
1023 (booleimp "pos1<pos2")
1024 (auto)
1025 (assume "2≤1")
1026 (ex-intro(pt"pos1"))
1027 (ng #t)
1028 (booleimp "pos2≤pos1")
1029 (use "Truth-Axiom")
1030 (simp "2≤1")
1031 (auto)
1032 ; Proof finished.
1033 (save "posMAX")
1034 (display-theorems "posMAX")
1035
1036
1037 (set! OLD-COMMENT-FLAG COMMENT-FLAG)
1038 (set! COMMENT-FLAG #t)
1039 (animate "posMAX")
1040 (display"
1041
1042 Test of cposMAX:
1043
1044 ")
1045 (display "cposMAX 3 1 : ")
1046 (pp(nt(pt"cposMAX 3 1")))
1047 (display "cposMAX 42 42 : ")
1048 (pp(nt(pt"cposMAX 42 42")))
1049 (display "cposMAX 1023 1024 : ")
1050 (pp(nt(pt"cposMAX 1023 1024")))
1051 (set! COMMENT-FLAG OLD-COMMENT-FLAG)
1052 (deanimate "posMAX")
1053 )
1054
1055
1056 (display "
1057
1058 Some Theorems concerning cposMAX :
1059
1060 ")
1061
1062 (begin
1063
1064 (animate"posMAX")
1065 (sg "cposMAX 1 pos = pos")
1066 (cases)
1067 (auto)
1068 ; Proof finished.
1069 (save "posMAX1n")
1070 (display-theorems "posMAX1n")
1071
1072
1073 (sg "cposMAX pos1 pos2 = cposMAX pos2 pos1")
1074 (assume "pos1" "pos2")
1075 (ng)
1076 (cd "pos1<pos2" "1k2")
1077 (simp (pf"(pos2<pos1)=F"))
1078 (use "Truth-Axiom")
1079 (booleimp "pos1<pos2")
1080 (auto)
1081 (assume "1≮2")
1082 (cd "pos2<pos1" "2k1")
1083 (use "Truth-Axiom")
1084 (assume "2≮1")
1085 (booleimp "(pos1<pos2) ∨ (pos2<pos1) ∨ (pos1=pos2)")
1086 (simp "1≮2")
1087 (simp "2≮1")
1088 (auto)
1089 ; Proof finished.
1090 (save "posMAXcomm")
1091 (deanimate"posMAX")
1092 (display-theorems "posMAXcomm")
1093
1094
1095 (sg "cposMAX pos 1 = pos")
1096 (strip)
1097 (simp "posMAXcomm")
1098 (simp "posMAX1n")
1099 (use "Truth-Axiom")
1100 ; Proof finished.
1101 (save "posMAXn1")
1102 (display-theorems "posMAXn1")
1103 )
1104
1105
1106
1107 (display "
1108
1109 posLE_LESSorEQUAL: (pos1≤pos2)=((pos1<pos2)∨(pos1=pos2))
1110
1111 ")
1112
1113 (begin
1114 (sg "(pos1≤pos2)=((pos1<pos2)∨(pos1=pos2))")
1115 (ind)
1116 (cases)
1117 (auto)
1118 (assume "pos2" "IH2")
1119 (cases)
1120 (auto)
1121 (assume "pos2" "IH2")
1122 (cases)
1123 (auto)
1124 ; Proof finished.
1125 (save "posLE_LESSorEQUAL")
1126 (display-theorems "posLE_LESSorEQUAL")
1127 )
1128
1129
1130
1131 (display "
1132
1133 < is transitive:
1134
1135 (pos1<pos2 ∧ pos2<pos3) → pos1<pos3
1136
1137 ")
1138
1139 (begin
1140
1141 (sg "all pos2,pos1.(pos1<pos2)→(1<pos2)")
1142 (cases)
1143 (auto)
1144 ; Proof finished.
1145 (nrw"(pos1<pos2)→(1<pos2)")
1146
1147
1148 (sg "all pos3,pos1,pos2.((pos1<pos2) ∧ (pos2<pos3)) → (pos1<pos3)")
1149 (ind)
1150 (auto)
1151 (assume "pos3" "IH3")
1152 (cases)
1153 (auto)
1154 (assume "pos1")
1155 (cases)
1156 (auto)
1157 (assume "pos2")
1158 (ng)
1159 (simp "posLE_LESSorEQUAL")
1160 (cd "pos1=pos2" "1=2")
1161 (simp "1=2")
1162 (auto)
1163 (assume "pos1")
1164 (cases)
1165 (auto)
1166 (assume "pos3" "IH3")
1167 (assert(pf"all pos1,pos2.¬(pos1<pos2∧pos2<pos3∧pos3<pos1)"))
1168 (begin
1169 (assume "pos1" "pos2")
1170 (simp (pf"(¬(pos1<pos2∧pos2<pos3∧pos3<pos1))=((pos1<pos2∧pos2<pos3)→(pos1≤pos3))"))
1171 (simp "posLE_LESSorEQUAL")
1172 (cases(pt"pos1=pos3"))
1173 (auto))
1174 (assume "IH3'")
1175 (cases)
1176 (auto)
1177 (assume "pos1")
1178 (cases)
1179 (auto)
1180 (assume "pos2")
1181 (ng)
1182 (simp "posLE_LESSorEQUAL")
1183 (cd "pos2=pos3" "2=3")
1184 (simp "2=3")
1185 (auto)
1186 (assume "pos2")
1187 (ng)
1188 (simp "posLE_LESSorEQUAL")
1189 (cd "pos1=pos2" "1=2")
1190 (simp "1=2")
1191 (auto)
1192 (assume "pos1")
1193 (cases)
1194 (auto)
1195 (assume "pos2")
1196 (ng)
1197 (simp "posLE_LESSorEQUAL")
1198 (cd "pos2=pos3" "2=3")
1199 (simp "2=3")
1200 (auto)
1201 ; Proof finished.
1202 (nrw"((pos1<pos2) ∧ ((pos2<pos3)) → (pos1<pos3))")
1203 )
1204
1205
1206
1207 (display"
1208 Extraction of Successor function
1209
1210 cposS: pos -> pos .
1211
1212 ")
1213
1214 (begin
1215 (sg "all pos1.ex pos.all pos2.(pos1<pos) ∧ (pos1<pos2 → pos≤pos2)")
1216 (ind)
1217 (ex-intro(pt"2"))
1218 (cases)
1219 (auto)
1220 ; n -> 2n
1221 (assume "pos1" "IH")
1222 (drop "IH")
1223 (ex-intro(pt"SOne pos1"))
1224 (cases)
1225 (auto)
1226
1227 ; n -> 2n+1
1228 (assume "pos1" "IH")
1229 (by-assume-with "IH" "pos0" "IH_pos0")
1230 (ex-intro(pt"SZero pos0"))
1231 (cases)
1232 (use-with "IH_pos0" (pt"pos0"))
1233 (auto)
1234 ; Proof finished.
1235 (save "posS")
1236 (display-theorems "posS")
1237
1238 (set! OLD-COMMENT-FLAG COMMENT-FLAG)
1239 (set! COMMENT-FLAG #t)
1240 (animate "posS")
1241 (display"
1242
1243 Test of cposS:
1244
1245 ")
1246 (display "cposS 1 = ")
1247 (pp(nt(pt"cposS 1")))
1248 (display "cposS 42 = ")
1249 (pp(nt(pt"cposS 42")))
1250 (display "cposS 1023 = ")
1251 (pp(nt(pt"cposS 1023")))
1252 (display "cposS 123456789098765432123456789 = ")
1253 (pp(nt(pt"cposS 123456789098765432123456789")))
1254 (set! COMMENT-FLAG OLD-COMMENT-FLAG)
1255 (deanimate "posS")
1256 )
1257
1258
1259
1260 (begin
1261
1262 (animate "posS")
1263
1264 (sg "cposS 1=2")
1265 (use"Truth-Axiom")
1266 (save"S1")
1267 (display-theorems"S1")
1268
1269
1270 (sg "¬(cposS pos=1)")
1271 (cases)
1272 (auto)
1273 ; Proof finished
1274 (deanimate "posS")
1275 (trw "¬(cposS pos = 1)")
1276 (trw"¬((Rec pos=>pos)2([pos0,pos1]SOne pos0)([pos0]SZero)pos=1)")
1277
1278 )
1279
1280 (animate "posS")
1281
1282 (display"
1283 Extraction of Predecessor function
1284
1285 cposP: pos -> pos
1286
1287 ")
1288
1289 (begin
1290
1291 (sg "ex pos2. (pos1=1 ∧ pos2=1) ∨ (pos1=cposS pos2)")
1292 (ind)
1293 (ex-intro(pt"1"))
1294 (auto)
1295 (assume "pos1" "IH1")
1296 (cd "pos1=1" "1=1")
1297 (simp "1=1")
1298 (drop "IH1")
1299 (ex-intro(pt"1"))
1300 (auto)
1301 (assume "1≠1")
1302 (by-assume-with "IH1" "pos" "IH")
1303 (ex-intro(pt"SOne pos"))
1304 (booleimp "(pos1=1∧pos=1)∨(pos1=cposS pos)")
1305 (ng)
1306 (simp "1≠1")
1307 (auto)
1308 (assume "pos1" "IH1")
1309 (drop "IH1")
1310 (ex-intro(pt"SZero pos1"))
1311 (auto)
1312 ; Proof finished.
1313 (save "posP")
1314 (display-theorems "posP")
1315
1316 (display "
1317 PROBLEM WITH (proof-to-soundness-proof ) !!!
1318 ")
1319
1320
1321 (add-theorem "posP_Soundness"
1322 (np(proof-to-soundness-proof
1323 (theorem-name-to-proof "posP"))))
1324 (deanimate "posS")
1325
1326
1327 (deanimate "posP")
1328 (set! OLD-COMMENT-FLAG COMMENT-FLAG)
1329 (set! COMMENT-FLAG #t)
1330 (animate "posP")
1331
1332 (display"
1333
1334 Test of cposP:
1335
1336 ")
1337
1338 (display "cposP 1 = ")
1339 (pp(nt(pt"cposP 1")))
1340 (display "cposP 42 = ")
1341 (pp(nt(pt"cposP 42")))
1342 (display "cposP 1023 = ")
1343 (pp(nt(pt"cposP 1023")))
1344 (display "cposP 123456789098765432123456789 = ")
1345 (pp(nt(pt"cposP 123456789098765432123456789")))
1346 (set! COMMENT-FLAG OLD-COMMENT-FLAG)
1347 (deanimate "posP")
1348 )
1349
1350 (deanimate "posS")
1351 (animate "posS")
1352 (animate "posP")
1353
1354 (display "
1355
1356 Some Theorems concerning cposP :
1357
1358 ")
1359
1360 (begin
1361
1362 (sg "SZero pos=cposS(cposP(SZero pos))")
1363 (assume "pos")
1364 (ng)
1365 (use-with "posP_Soundness" (pt"SZero pos"))
1366 ; Proof finished.
1367 (save "SP2n")
1368 (display-theorems "SP2n")
1369
1370
1371 (sg "SOne pos=cposS(cposP(SOne pos))")
1372 (auto)
1373 ; Proof finished.
1374 (save "SP2n+1")
1375 (display-theorems "SP2n+1")
1376
1377
1378 (sg "all pos.cposP(cposS pos)=pos")
1379 (ind)
1380 (auto)
1381 (cases)
1382 (auto)
1383 ; Proof finished.
1384 (save"posPS")
1385 (deanimate"posS")
1386 (deanimate"posP")
1387 (display-theorems "posPS")
1388
1389 )
1390
1391
1392 (display"
1393
1394 ADDITION
1395
1396 ")
1397
1398
1399 (add-ids
1400 (list
1401 (list "posADD"
1402 (make-arity (py "pos") (py "pos") (py "pos"))))
1403 '("allnc pos.posADD pos 1 (cposS pos)")
1404 '("allnc pos1,pos2,pos3.
1405 posADD pos1 pos2 pos3
1406 -> posADD pos1 (cposS pos2) (cposS pos3)"))
1407
1408
1409 (begin
1410
1411 (add-program-constant
1412 "posPlus"
1413 (mk-arrow (py "pos") (py "pos") (py "pos"))
1414 1 'const 2
1415 )
1416
1417 (add-token
1418 "+"
1419 'add-op
1420 (lambda (x y)
1421 (mk-term-in-app-form
1422 (make-term-in-const-form
1423 (pconst-name-to-pconst "posPlus")) x y)))
1424
1425 (add-display
1426 (py "pos")
1427 (lambda (x)
1428 (let* ((op (term-in-app-form-to-final-op x))
1429 (args (term-in-app-form-to-args x)))
1430 (if (and (term-in-const-form? op)
1431 (string=? "posPlus"
1432 (const-to-name (term-in-const-form-to-const op)))
1433 (= 2 (length args)))
1434 (list 'add-op "+"
1435 (term-to-token-tree (car args))
1436 (term-to-token-tree (cadr args)))
1437 #f))))
1438
1439 ; Computation Rules For posPlus
1440
1441 (acrs "1+1" "2")
1442 (acrs "(SZero pos) + 1" "SOne pos")
1443 (acrs "(SOne pos) + 1" "SZero (pos + 1)")
1444
1445 (acrs "1+(SZero pos2)" "SOne pos2")
1446 (acrs "(SZero pos1) + (SZero pos2)" "SZero(pos1 + pos2)")
1447 (acrs "(SOne pos1) + (SZero pos2)" "SOne(pos1 + pos2)")
1448
1449 (acrs "1 + (SOne pos2)" "SZero (pos2 + 1)")
1450 (acrs "(SZero pos1) + (SOne pos2)" "SOne(pos1 + pos2)")
1451 (acrs "(SOne pos1) + (SOne pos2)" "SZero((pos1 + pos2) + 1)")
1452
1453 (set! OLD-COMMENT-FLAG COMMENT-FLAG)
1454 (set! COMMENT-FLAG #t)
1455
1456 (display-program-constants "posPlus")
1457
1458 (display"
1459
1460 Test of posPlus +
1461
1462 ")
1463
1464 (display " 3 + 1 = ")
1465 (pp(nt(pt"3+1")))
1466 (display " 42 + 42 = ")
1467 (pp(nt(pt"42+42")))
1468 (display " 1024 + 1023 = ")
1469 (pp(nt(pt"1024+1023")))
1470 (set! COMMENT-FLAG OLD-COMMENT-FLAG)
1471 )
1472
1473
1474 (display "
1475 Some RW-rules concerning posPlus +
1476
1477 ")
1478
1479 (begin
1480
1481 (display"
1482 1 < pos+1
1483 ")
1484 (sg "1<(pos+1)")
1485 (cases)
1486 (auto)
1487 ; Proof finished.
1488 (trw "1<(pos+1)")
1489
1490
1491
1492 (sg "¬(pos1+pos2=1)")
1493 (cases)
1494 (cases)
1495 (auto)
1496 (assume "pos1")
1497 (cases)
1498 (auto)
1499 (assume "pos1")
1500 (cases)
1501 (auto)
1502 ; Proof finished.
1503 (trw "¬(pos1+pos2=1)")
1504
1505
1506 (sg "(pos1<pos2+1)=(pos1≤pos2)")
1507 (ind)
1508 (auto)
1509 (assume "pos1" "IH1")
1510 (cases)
1511 (auto)
1512 (assume "pos1" "IH1")
1513 (cases)
1514 (auto)
1515 ; Proof finished.
1516 (arw "pos1<pos2+1" "pos1≤pos2")
1517 )
1518
1519
1520
1521 (animate "posS")
1522
1523 (begin
1524
1525 (display"
1526 Sn = 1+n
1527 ")
1528
1529 (sg "cposS pos=1+pos")
1530 (ind)
1531 (auto)
1532 (cases)
1533 (auto)
1534 ; Proof finished.
1535 (save "1+pos")
1536 (display-theorems "1+pos")
1537
1538
1539
1540 (sg "cposS pos=pos+1")
1541 (ind)
1542 (auto)
1543 ; Proof finished.
1544 (save "pos+1")
1545 (deanimate "posS")
1546 (display-theorems "pos+1")
1547
1548 )
1549
1550
1551 (display"
1552
1553 n=1 ∨ n=1+Pn
1554 ")
1555
1556 (begin
1557
1558 (sg " pos=1 ∨ pos=1+(cposP pos)")
1559 (cases)
1560 (auto)
1561 (assume "pos")
1562 (simp "<-" "1+pos")
1563 (ng #t)
1564 (simp "SP2n")
1565 (use "Truth-Axiom")
1566
1567 (assume "pos")
1568 (simp "<-" "1+pos")
1569 (ng #t)
1570 (simp "SP2n+1")
1571 (use "Truth-Axiom")
1572 ; Proof finished.
1573 (nrw "pos=1 ∨ pos=1+(cposP pos)")
1574 (nrw "pos=1 ∨ pos=1+((Rec pos=>pos)1([pos0,pos1][if (pos0=1) 1 (SOne pos1)]) ([pos0,pos1]SZero pos0) pos)")
1575 )
1576
1577
1578
1579 (display"
1580
1581 posPLUScomm: k+n = n+k
1582 ")
1583
1584 (begin
1585
1586 (sg "pos1+pos2=pos2+pos1")
1587 (ind)
1588 (ind)
1589 (auto)
1590 (assume "pos1" "IH")
1591 (ind)
1592 (auto)
1593 (assume "pos1" "IH")
1594 (ind)
1595 (auto)
1596 (assume "pos2")
1597 (ng #t)
1598 (simp(pf"pos1+pos2=pos2+pos1"))
1599 (auto)
1600 ; Proof finished.
1601 (save "posPLUScomm")
1602 (display-theorems "posPLUScomm")
1603 )
1604
1605
1606 (display"
1607
1608 posPLUS is associative:
1609 pos1+(pos2+pos3)=pos1+pos2+pos3
1610
1611 ")
1612
1613 (begin
1614 (sg "1+(pos2+pos3)=1+pos2+pos3")
1615 (ind)
1616 (cases)
1617 (auto)
1618 (assume "pos3")
1619 (ng)
1620 (simp-with "posPLUScomm" (pt"1") (pt"pos3"))
1621 (auto)
1622 (assume "pos3")
1623 (ng)
1624 (simp-with "posPLUScomm" (pt"1") (pt"pos3"))
1625 (auto)
1626 (assume "pos2" "IH2")
1627 (cases)
1628 (auto)
1629 (assume "pos2" "IH2")
1630 (cases)
1631 (auto)
1632 (ng)
1633 (assume "pos3")
1634 (simp-with "<-" "posPLUScomm" (pt"1") (pt"pos2"))
1635 (simp "<-" (pf"1+(pos2+pos3)=1+pos2+pos3"))
1636 (simp-with "posPLUScomm" (pt"1") (pt"pos2+pos3"))
1637 (auto)
1638 (assume "pos3")
1639 (ng)
1640 (simp-with "<-" "posPLUScomm" (pt"1") (pt"pos2"))
1641 (simp "<-" (pf"1+(pos2+pos3)=1+pos2+pos3"))
1642 (simp-with "posPLUScomm" (pt"1") (pt"pos2+pos3"))
1643 (auto)
1644 ; Proof finished.
1645 (arw "1+(pos2+pos3)" "1+pos2+pos3")
1646
1647
1648
1649 (sg "pos1+(pos2+pos3)=pos1+pos2+pos3")
1650 (ind)
1651 (auto)
1652 (assume "pos1" "IH1")
1653 (ind)
1654 (cases)
1655 (auto)
1656 (assume "pos2" "IH2")
1657 (cases)
1658 (auto)
1659 (assume "pos2" "IH2")
1660 (cases)
1661 (auto)
1662 (ng)
1663 (assume "pos3")
1664 (simp-with "IH1" (pt"pos2+pos3") (pt"1"))
1665 (simp-with "IH1" (pt"pos2") (pt"pos3"))
1666 (auto)
1667
1668 (assume "pos1" "IH1")
1669 (ind)
1670 (cases)
1671 (auto)
1672 (ng)
1673 (assume "pos3")
1674 (simp-with "<-" "IH1" (pt"pos3") (pt"1"))
1675 (simp-with "<-" "posPLUScomm" (pt"1") (pt"pos3"))
1676 (auto)
1677 (assume "pos3")
1678 (ng #t)
1679 (simp-with "<-" "posPLUScomm" (pt"1") (pt"pos3"))
1680 (auto)
1681 (assume "pos2" "IH2")
1682 (cases)
1683 (auto)
1684 (assume "pos3")
1685 (ng #t)
1686 (simp "IH1")
1687 (auto)
1688 (assume "pos2" "IH2")
1689 (cases)
1690 (auto)
1691 (assume "pos3")
1692 (ng)
1693 (simp "IH1")
1694 (simp-with "posPLUScomm" (pt"pos1+pos2+pos3") (pt"1"))
1695 (simp-with "posPLUScomm" (pt"pos1+pos2") (pt"1"))
1696 (auto)
1697 (assume "pos3")
1698 (ng)
1699 (simp-with "posPLUScomm" (pt"pos2+pos3") (pt"1"))
1700 (simp-with "<-" "IH1" (pt"pos2") (pt"1"))
1701 (simp-with "posPLUScomm" (pt"pos2") (pt"1"))
1702 (auto)
1703 ; Proof finished.
1704 (arw "pos1+(pos2+pos3)" "pos1+pos2+pos3")
1705
1706 )
1707
1708
1709 (display"
1710 k < k+l and k < l+k
1711 ")
1712
1713
1714 (begin
1715
1716 (sg "pos1<(pos1+pos2)")
1717 (ind)
1718 (cases)
1719 (auto)
1720 (assume "pos1" "IH1")
1721 (cases)
1722 (auto)
1723 (assume "pos2")
1724 (booleimp "pos1<pos1+pos2")
1725 (auto)
1726 (assume "pos1" "IH1")
1727 (cases)
1728 (auto)
1729 (assume "pos2")
1730 (ng #t)
1731 (simp(pf"(pos1≤pos1+pos2)=(pos1<pos1+pos2+1)"))
1732 (simp(pf"pos1+pos2+1=pos1+(pos2+1)"))
1733 (use "IH1")
1734 (auto)
1735 ; Proof finished.
1736 (trw "pos1<(pos1+pos2)")
1737
1738
1739 (sg "pos1<(pos2+pos1)")
1740 (assume "pos1" "pos2")
1741 (simp "posPLUScomm")
1742 (use "Truth-Axiom")
1743 ; Proof finished.
1744 (trw "pos1<(pos2+pos1)")
1745
1746 )
1747
1748
1749 ; (sg "(pos1≤pos2)=(pos1<pos2 ∨ pos1=pos2)")
1750 ; ;(begin
1751 ; (cases)
1752 ; (auto)
1753 ; (assume "pos1")
1754 ; (cases)
1755 ; (auto)
1756 ; (assume "pos2")
1757 ; (use "posLE_LESSorEQUAL")
1758 ; (auto)
1759 ; (assume "pos1")
1760 ; (cases)
1761 ; (auto)
1762 ; (assume "pos2")
1763 ; (use "posLE_LESSorEQUAL"))
1764 ; ; Proof finished.
1765 ; (save "poslessS1")
1766 ; (display-theorems "poslessS1")
1767
1768
1769
1770 (display "
1771
1772 We add the algebra upos
1773 of unary postive numbers
1774 in order to simplify
1775 the successor induction
1776 on the binary represention.
1777
1778 ")
1779
1780
1781 (add-alg "upos"
1782 '("Unum" "upos")
1783 '("SUCC" "upos=>upos"))
1784 (display-constructors "upos")
1785
1786 (begin
1787
1788 (add-program-constant
1789 "uposP"
1790 (mk-arrow (py "upos") (py "upos"))
1791 1 'const 1
1792 )
1793 (acrs "uposP Unum" "Unum")
1794 (acrs "uposP (SUCC upos)" "upos")
1795
1796 (display-program-constants "uposP")
1797 )
1798
1799
1800
1801 (begin
1802
1803 (add-program-constant
1804 "Upostopos"
1805 (mk-arrow (py "upos") (py "pos"))
1806 1 'const 1
1807 )
1808
1809 ; Computation Rules For Upostopos
1810
1811 (acrs "Upostopos Unum" "1")
1812 (acrs "Upostopos (SUCC upos)" "(Upostopos upos)+1")
1813
1814 (display-program-constants "Upostopos")
1815
1816 (display"
1817
1818 Test of Upostopos:
1819
1820 ")
1821
1822 (display "
1823 Upostopos Unum = ")
1824 (pp(nt(pt"Upostopos Unum")))
1825 (display "
1826 Upostopos SUCC(SUCC Unum) = ")
1827 (pp(nt(pt"Upostopos (SUCC(SUCC Unum))")))
1828 )
1829
1830
1831
1832 (begin
1833
1834 (add-program-constant
1835 "uposPLUS"
1836 (mk-arrow (py "upos") (py "upos") (py "upos"))
1837 1 'const 2
1838 )
1839
1840 ; Computation Rules For uposPLUS
1841
1842 (acrs "uposPLUS upos Unum" "SUCC upos")
1843 (acrs "uposPLUS upos1 (SUCC upos2)" "SUCC (uposPLUS upos1 upos2)")
1844
1845 (display-program-constants "uposPLUS")
1846 )
1847
1848
1849 (display "
1850 Some RW-rules .
1851 ")
1852
1853 (begin
1854
1855 (sg "¬(uposPLUS upos1 upos2 = Unum)")
1856 (assume "upos1")
1857 (cases)
1858 (auto)
1859 ; Proof finished.
1860 (trw "¬(uposPLUS upos1 upos2 = Unum)")
1861
1862
1863 (sg "all upos2,upos1.uposPLUS(SUCC upos1)upos2=SUCC(uposPLUS upos1 upos2)")
1864 (ind)
1865 (auto)
1866 ; Proof finished.
1867 (arw "uposPLUS(SUCC upos1)upos2" "SUCC(uposPLUS upos1 upos2)")
1868
1869
1870 (sg "Upostopos(uposPLUS upos upos)=SZero(Upostopos upos)")
1871 (ind)
1872 (prop)
1873 (assume "upos" "IH")
1874 (ng #t)
1875 (simp "IH")
1876 (auto)
1877 ; Proof finished.
1878 (arw "Upostopos(uposPLUS upos upos)" "SZero(Upostopos upos)")
1879
1880 )
1881
1882
1883 (display"
1884 Upostopos is surjective
1885 exnc upos.pos=Upostopos upos
1886
1887 ")
1888
1889 (begin
1890
1891 (sg "ex upos.pos=Upostopos upos")
1892 (ind)
1893 (ex-intro(pt "Unum"))
1894 (use "Truth-Axiom")
1895 (assume "pos" "IH")
1896 (by-assume-with "IH" "upos" "IHn")
1897 (ex-intro(pt "uposPLUS upos upos"))
1898 (simp "IHn")
1899 (use "Truth-Axiom")
1900
1901 (assume "pos" "IH")
1902 (by-assume-with "IH" "upos" "IHn")
1903 (ex-intro(pt "SUCC(uposPLUS upos upos)"))
1904 (simp "IHn")
1905 (use "Truth-Axiom")
1906 ; Proof finished.
1907 (save "Upostopossurjective")
1908 (display-theorems "Upostopossurjective")
1909
1910 (set! OLD-COMMENT-FLAG COMMENT-FLAG)
1911 (set! COMMENT-FLAG #t)
1912 (animate "Upostopossurjective")
1913
1914 (display"
1915
1916 Test of cUpostopossurjective:
1917
1918 ")
1919
1920 (display "cUpostopossurjective 1 = ")
1921 (pp(nt(pt"cUpostopossurjective 1")))
1922 (display "cUpostopossurjective 4 = ")
1923 (pp(nt(pt"cUpostopossurjective 4")))
1924 (display "cUpostopossurjective 13 = ")
1925 (pp(nt(pt"cUpostopossurjective 13")))
1926 (deanimate "Upostopossurjective")
1927 (set! COMMENT-FLAG OLD-COMMENT-FLAG)
1928 )
1929
1930
1931
1932 (begin
1933
1934 (sg "(all upos (Pvar pos)^(Upostopos upos)) -> all pos.(Pvar pos)^ pos")
1935
1936 (assume "Aupos" "pos")
1937 (inst-with-to "Upostopossurjective" (pt"pos") "preimg")
1938 (by-assume-with "preimg" "upos2" "equ")
1939 (simp "equ")
1940 (inst-with-to "Aupos" (pt"upos2") "Aupos2")
1941 (use "Aupos2")
1942 ; Proof finished.
1943 (save"FromUpostopos")
1944 (display-theorems"FromUpostopos")
1945
1946
1947 (define (uposind varstring formulastring)
1948 (inst-with-to "FromUpostopos"
1949 (make-cterm (pv varstring)
1950 (pf formulastring))
1951 "upos2pos")
1952 (use "upos2pos")
1953 (drop "upos2pos")
1954 (ind))
1955
1956 )
1957
1958 (display"
1959
1960 posPLUSposADD: posADD pos1 pos2 (pos1+pos2)
1961
1962 ")
1963
1964 (begin
1965
1966 (sg "all pos1,pos2.posADD pos1 pos2 (pos1+pos2)")
1967 (assume "pos1")
1968 (uposind "pos2" "posADD pos1 pos2 (pos1+pos2)")
1969 (ng #t)
1970 (simp "<-" "pos+1")
1971 (intro 0)
1972 (assume "upos" "IH")
1973 (ng #t)
1974 (simp "<-" "pos+1")
1975 (simp "<-" "pos+1")
1976 (intro 1)
1977 (auto)
1978 ; Proof finished.
1979 (save"posPLUSposADD")
1980 (display-theorems"posPLUSposADD")
1981 )
1982
1983
1984 (display"
1985
1986 posADDposPLUS: posADD pos1 pos2 pos3 -> (pos1+pos2=pos3)
1987
1988 ")
1989
1990 (begin
1991
1992 (sg "posADD pos1 pos2 pos3 -> (pos1+pos2=pos3)")
1993 (assume "pos1" "pos2" "pos3")
1994 (elim)
1995 (assume "pos")
1996 (simp "pos+1")
1997 (auto)
1998 (assume "pos4" "pos5" "pos6" "add" "4+5=6")
1999 (simp "pos+1")
2000 (simp "pos+1")
2001 (auto)
2002 (simp "<-" "4+5=6")
2003 (auto)
2004 ; Proof finished.
2005 (save"posADDposPLUS")
2006 (display-theorems"posADDposPLUS")
2007
2008 )
2009
2010
2011 ; (display"
2012 ; n+1=k -> k=Sn
2013
2014 ; PROOF:
2015 ; ")
2016
2017 ; (animate "posS")
2018 ; (set-goal
2019 ; (pf"posADD pos1 pos2 pos3 -> pos2=1 -> pos3=cposS pos1"))
2020 ; (begin
2021 ; (assume "pos2" "pos1" "pos3")
2022 ; (elim)
2023 ; (auto)
2024 ; (assume "pos4" "pos5" "pos6" "+" "IH")
2025 ; (simp "OneNonSucS")
2026 ; (use "Efq-Atom")
2027 ; ; ok, ?_6 is proved. Proof finished.
2028 ; )
2029 ; (save "posPlusOne")
2030 ; (display-theorems "posPlusOne")
2031 ; (deanimate "posS")
2032
2033
2034
2035
2036
2037 ; (display"
2038 ; n+k=1 -> F
2039
2040 ; ")
2041
2042 ; (set-goal
2043 ; (pf"posADD pos1 pos2 pos3->pos3=1->F"))
2044 ; (begin
2045 ; (assume "pos1" "pos2" "pos3")
2046 ; (elim)
2047 ; (assume "pos4")
2048 ; (simp "OneNonSucS")
2049 ; (auto)
2050 ; (strip 5)
2051 ; (simp "OneNonSucS")
2052 ; (auto)
2053
2054 ; ; Proof finished.
2055 ; )
2056 ; (save "PosOneNoSum")
2057 ; (display-theorems "PosOneNoSum")
2058
2059
2060
2061
2062 ; (sg "posADD pos1 pos2 1->F")
2063 ; (begin
2064 ; (assume "pos1" "pos2")
2065 ; (inst-with-to "PosOneNoSum"
2066 ; (pt"pos1")
2067 ; (pt"pos2")
2068 ; (pt "1") "PosOneNoSum121")
2069 ; (auto)
2070
2071 ; ; Proof finished.
2072 ; )
2073 ; (save "PosOneNoSum1")
2074 ; (display-theorems "PosOneNoSum1")
2075
2076
2077
2078
2079
2080 ; (display"
2081 ; k+l=m -> m+l=n -> k+2l=n
2082
2083 ; PROOF:
2084 ; ")
2085
2086 ; (begin
2087
2088 ; (display "
2089 ; Left as an exercise
2090 ; for the MiNLOG newcomer.
2091 ; ")
2092
2093 ; (aga "posPlusDouble" (pf "all pos1,pos2,pos3,pos4.
2094 ; posADD pos1 pos2 pos3
2095 ; -> posADD pos3 pos2 pos4
2096 ; -> posADD pos1 (SZero pos2) pos4"))
2097 ; (display-global-assumptions "posPlusDouble")
2098
2099 ;(set-goal
2100 ; (pf"all pos1.posADD pos1 pos2 pos3
2101 ; -> posADD pos3 pos2 pos4
2102 ; -> posADD pos1 (SZero pos2) pos4"))
2103 ; (cases)
2104 ; (simp(pf"2=cposS 1"))
2105 ; (assume "pos3" "pos4" "pos1")
2106 ; (assume "S1" "SS1")
2107 ; (simp(pf"pos4=cposS pos3"))
2108 ; (intro 1)
2109 ; (auto)
2110 ; (use "posPlusOne" (pt"1"))
2111 ; (use "SS1")
2112 ; (auto)
2113
2114 ; (assume "pos2" "pos3" "pos4" "pos1" "1+2*2=3" "3+2*2=4")
2115
2116
2117 ; (display"
2118
2119 ; Until here !!!
2120 ; ")
2121
2122
2123 ; (simp
2124 ; (pf"SZero (SZero pos2)
2125 ; = cposS(cposP (SZero (SZero pos2)))"))
2126 ; (simp(pf"pos4=cposS(cposP pos4)"))
2127 ; (intro 1)
2128 ; (ng #t)
2129 ; (cases(pt"pos2=1"))
2130 ; (assume "2=1")
2131 ; (ng #t)
2132 ; (simp (pf"3=cposS 2"))
2133 ;)
2134
2135
2136 ; (display"
2137 ; n = k+2l -> Sn = k+(2l+1)
2138
2139 ; PROOF"
2140 ; )
2141 ; (animate "posS")
2142 ; (set-goal
2143 ; (pf"posADD pos1 (SZero pos2) pos3
2144 ; -> posADD pos1 (SOne pos2) (cposS pos3)"))
2145 ; (begin
2146 ; (assume "pos1" "pos2" "pos3" "3=1+2*2")
2147 ; (simp (pf"SOne pos2 = cposS(SZero pos2)"))
2148 ; (intro 1)
2149 ; (auto)
2150
2151 ; ; Proof finished.
2152 ; )
2153 ; (save"posPlusDoubleToDouble1")
2154 ; (display-theorems"posPlusDoubleToDouble1")
2155 ; (deanimate "posS")
2156
2157
2158
2159
2160
2161
2162
2163
2164
2165 ; (define(PROG var function Predicate)
2166 ; (string-append "(all "var"."Predicate"("var") -> "
2167 ; Predicate"("function"))"))
2168
2169
2170 ; (begin
2171 ; (display"
2172
2173 ; Three more global assumptions to be shown:
2174 ; ")
2175 ; (aga "k+2n"
2176 ; (pf"all pos1,pos2.
2177 ; pos1+SZero pos2 = (pos1+pos2)+pos2"))
2178 ; (display-global-assumptions "k+2n")
2179 ; (aga "S(k+2n)"
2180 ; (pf"all pos1,pos2.
2181 ; pos1+SOne pos2 = cposS(pos1+SZero pos2)"))
2182 ; (display-global-assumptions "S(k+2n)")
2183 ; (aga "k+2n+1"
2184 ; (pf"all pos1,pos2.
2185 ; pos1+SOne pos2 = (pos1+SZero pos2)+1"))
2186 ; (display-global-assumptions "k+2n+1")
2187 ; )
2188
2189 ; (display"
2190
2191
2192 ; A(k) -> Prog(n,n+1,A) -> A(k+n)
2193
2194 ; PROOF:
2195 ; ")
2196
2197 ; (set-goal
2198 ; (pf
2199 ; (string-append
2200 ; "all pos0.A^ pos0 -> "
2201 ; (PROG "pos" "pos+1" "A^") "-> A^(pos0+pos1)" )))
2202 ; (time(begin
2203 ; (cut
2204 ; (pf"all pos0.A^pos0
2205 ; -> (all pos.A^pos -> A^(pos+1)) -> A^(pos0+1)"))
2206 ; (assume "IH1base")
2207 ; (cut
2208 ; (pf"all pos1.
2209 ; (all pos0.A^pos0
2210 ; -> (all pos.A^pos -> A^(pos+1))
2211 ; -> A^(pos0+pos1))
2212 ; -> all pos0. A^pos0
2213 ; -> (all pos.A^pos -> A^(pos+1))
2214 ; -> A^(pos0+SZero pos1)"))
2215 ; (assume "IH1step0")
2216 ; (ind)
2217 ; (auto)
2218
2219 ; ; IH1step1
2220 ; (assume "pos1" "IH1" "pos0" "A0" "PROG")
2221 ; (simp "k+2n+1")
2222 ; (auto)
2223
2224 ; ; IHstep0
2225
2226 ; (assume "pos1" "IH1" "pos0" "A0" "PROG")
2227 ; (simp "k+2n")
2228 ; (auto)
2229
2230 ; ; Proof finished.
2231 ; ))
2232 ; (save "posIndAdd")
2233 ; (display-theorems "posIndAdd")
2234
2235
2236
2237
2238
2239
2240
2241 ; (display"
2242 ; INDUCTION on pos
2243 ; A(1) -> Prog(n,n+1,A) -> A(n)
2244
2245 ; PROOF:
2246 ; ")
2247
2248 ; (set-goal
2249 ; (pf
2250 ; (string-append
2251 ; "A^ 1 -> " (PROG "pos" "pos+1" "A^") "-> A^ pos" )))
2252 ; (time(begin
2253 ; (assume "pos")
2254 ; (cases (pt"pos=1"))
2255 ; (assume "1")
2256 ; (simp "1")
2257 ; (search)
2258 ; (assume "not1")
2259 ; (simp (pf"pos = 1+(cposP pos)"))
2260 ; (use "posIndAdd")
2261 ; (cut
2262 ; (pf"((pos=1)=False and (pos=1+(cposP pos))=False)=False"))
2263 ; (simp"not1")
2264 ; (ng #t)
2265 ; (simp"BooleStab")
2266 ; (auto)
2267
2268 ; ; Proof finished.
2269 ; ))
2270 ; (save "posInd")
2271 ; (display-theorems "posInd")
2272
2273
2274
2275
2276
2277
2278 (begin
2279
2280 (add-program-constant
2281 "uposLESS"
2282 (mk-arrow (py "upos") (py "upos") (py "boole"))
2283 1 'const 2
2284 )
2285
2286 (add-token
2287 "◁"
2288 'rel-op
2289 (lambda (x y)
2290 (mk-term-in-app-form
2291 (make-term-in-const-form
2292 (pconst-name-to-pconst "uposLESS")) x y)))
2293
2294 (add-display
2295 (py "boole")
2296 (lambda (x)
2297 (let* ((op (term-in-app-form-to-final-op x))
2298 (args (term-in-app-form-to-args x)))
2299 (if (and (term-in-const-form? op)
2300 (string=? "uposLESS"
2301 (const-to-name (term-in-const-form-to-const op)))
2302 (= 2 (length args)))
2303 (list 'rel-op "◁"
2304 (term-to-token-tree (car args))
2305 (term-to-token-tree (cadr args)))
2306 #f))))
2307
2308 ; Computation Rules For uposLESS
2309
2310 (acrs "upos ◁ Unum" "False")
2311
2312 (acrs "Unum ◁ SUCC upos" "True")
2313 (acrs "SUCC upos1 ◁ SUCC upos2" "upos1◁upos2")
2314
2315 (display-program-constants "uposLESS")
2316
2317 )
2318
2319
2320 (begin
2321
2322 (sg "upos◁SUCC upos")
2323 (ind)
2324 (auto)
2325 ; Proof finished.
2326 (trw "upos◁SUCC upos")
2327
2328 (sg "¬(upos◁ upos)")
2329 (ind)
2330 (auto)
2331 ; Proof finished.
2332 (nrw "¬(upos◁ upos)")
2333
2334
2335 (sg "(upos1◁SUCC upos2)=(upos1◁upos2 ∨ upos1=upos2)")
2336 (ind)
2337 (cases)
2338 (auto)
2339 (assume "upos1" "IH1")
2340 (cases)
2341 (auto)
2342 ; Proof finished.
2343 (save "uposlessS1")
2344 (display-theorems "uposlessS1")
2345
2346 )
2347
2348 (begin
2349
2350 (add-program-constant
2351 "Postoupos"
2352 (mk-arrow (py "pos") (py "upos"))
2353 1 'const 1
2354 )
2355
2356 ; Computation Rules For Postoupos
2357
2358 (acrs "Postoupos 1" "Unum")
2359
2360 (acrs "Postoupos (SZero pos)"
2361 "uposPLUS(Postoupos pos)(Postoupos pos)")
2362
2363 (acrs "Postoupos (SOne pos)"
2364 "SUCC(uposPLUS(Postoupos pos)(Postoupos pos))")
2365
2366 (display-program-constants "Postoupos")
2367
2368 (display"
2369
2370 Test of Postoupos:
2371
2372 ")
2373
2374 (display "Postoupos 1 = ")
2375 (pp(nt(pt"Postoupos 1")))
2376 (display "Postoupos 13 = ")
2377 (pp(nt(pt"Postoupos 13")))
2378 )
2379
2380
2381 (sg "Upostopos(Postoupos pos)=pos")
2382 (ind)
2383 (auto)
2384 ; Proof finished.
2385 (arw "Upostopos(Postoupos pos)" "pos")
2386
2387
2388 ; (set-goal
2389 ; (pf"Upostopos(uposPLUS Unum (Postoupos pos))=pos+1"))
2390 ; (ind)
2391 ; (auto)
2392 ; (assume "pos" "IH")
2393 ; (ng #t)
2394
2395
2396 ; (set-goal
2397 ; (pf"all pos1.Upostopos(uposPLUS (Postoupos pos1) (Postoupos pos2))=pos1+pos2"))
2398 ; (ind)
2399 ; (cases)
2400 ; (auto)
2401 ; (assume "pos2" "IH2")
2402 ; (cases)
2403 ; (auto)
2404 ; (ng #t)
2405
2406 ; (auto)
2407
2408
2409 ; (sg "Postoupos(pos+1)=SUCC(Postoupos pos)")
2410 ; (cases)
2411 ; (auto)
2412 ; (assume "pos")
2413 ; (ng #t)
2414
2415 ; (arw "Postoupos(pos+1)" "SUCC(Postoupos pos)")
2416
2417
2418
2419
2420 ; (sg "Postoupos(Upostopos upos)=upos")
2421 ; (ind)
2422 ; (auto)
2423 ; (assume "upos" "IH")
2424 ; (ng #t)
2425
2426 ; ; Proof finished.
2427 ; (arw "Upostopos(Postoupos pos)" "pos")
2428
2429
2430
2431 (display "
2432 Postoupos(k+1) = SUCC(Postoupos k)
2433
2434 ")
2435
2436 (begin
2437
2438 (sg "Postoupos(pos+1)=SUCC(Postoupos pos)")
2439 (ind)
2440 (auto)
2441 (assume "pos1" "IH")
2442 (ng)
2443 (simp "IH")
2444 (use "Truth-Axiom")
2445 ; Proof finished.
2446 (arw "Postoupos(pos+1)" "SUCC(Postoupos pos)")
2447 )
2448
2449
2450 ; (display"
2451 ; Postoupos is surjective
2452 ; exnc pos.upos=Postoupos pos
2453
2454 ; PROOF:
2455 ; ")
2456 ; (sg "ex pos.upos=Postoupos pos")
2457 ; (begin
2458 ; (ind)
2459 ; (ex-intro(pt "1"))
2460 ; (use "Truth-Axiom")
2461 ; (assume "upos" "IH")
2462 ; (ex-elim "IH")
2463 ; (drop "IH")
2464 ; (assume "pos" "IHn")
2465 ; (ex-intro(pt "pos+1"))
2466 ; (simp "IHn")
2467 ; (use "Truth-Axiom")
2468 ; ; Proof finished.
2469 ; )
2470 ; (save "Postoupossurjective")
2471 ; (display-theorems "Postoupossurjective")
2472
2473
2474 (display "
2475 Some more RW-rules and THMs .
2476
2477 ")
2478
2479 (begin
2480
2481 (deanimate "Upostopossurjective")
2482 (animate "Upostopossurjective")
2483
2484 (sg "cUpostopossurjective pos = Postoupos pos")
2485 (ind)
2486 (auto)
2487 (assume "pos" "hyp")
2488 (ng #t)
2489 (simp "hyp")
2490 (auto)
2491 (assume "pos" "hyp")
2492 (ng #t)
2493 (simp "hyp")
2494 (auto)
2495 ; Proof finished.
2496 (save "UpostoposPreimg")
2497 (deanimate "Upostopossurjective")
2498 (display-theorems "UpostoposPreimg")
2499
2500
2501 (sg "(¬(upos1◁upos2) ∧ upos1◁SUCC upos2)=(upos1=upos2)")
2502 (ind)
2503 (ind)
2504 (auto)
2505 (assume "upos1" "IH1")
2506 (ind)
2507 (auto)
2508 ; Proof finished.
2509 (arw "¬(upos1◁upos2) ∧ upos1◁SUCC upos2" "upos1=upos2")
2510
2511
2512 )
2513
2514
2515
2516
2517 ; (add-pvar-name "B" (make-arity (py "upos")))
2518
2519
2520 ; (sg "(all pos B^(Postoupos pos)) -> all upos.B^ upos")
2521 ; (begin
2522 ; (assume "Bupos" "upos")
2523 ; (inst-with-to "Postoupossurjective" (pt"upos") "preimg")
2524 ; (ex-elim "preimg")
2525 ; (assume "pos2" "equ")
2526 ; (simp "equ")
2527 ; (use "Bupos")
2528 ; ; Proof finished.
2529 ; )
2530 ; (save"FromPostoupos")
2531 ; (display-theorems"FromPostoupos")
2532
2533
2534
2535
2536 ; (begin
2537 ; (display "
2538 ; Remains to be shown
2539 ; Upostopos(Postoupos k) = k
2540
2541 ; ")
2542 ; (arw "Upostopos(Postoupos pos)" "pos")
2543 ; )
2544
2545
2546
2547 ; (display"
2548 ; INDUCTION on pos
2549 ; A(1) -> Prog(n,n+1,A) -> A(n)
2550
2551 ; PROOF:
2552 ; ")
2553
2554 ; (set-goal
2555 ; (pf
2556 ; (string-append
2557 ; "A^ 1 -> " (PROG "pos" "pos+1" "A^") "-> A^ pos" )))
2558 ; (begin
2559 ; (assume "pos" "A1" "prog")
2560 ; (use "FromUpostopos")
2561 ; (ind)
2562 ; (use "A1")
2563 ; (cut(pf"all pos.A^(Upostopos(Postoupos pos)) -> A^(Upostopos(SUCC(Postoupos pos)))"))
2564 ; (use-with "FromPostoupos" (make-cterm (pv "upos") (pf "A^(Upostopos upos) -> A^(Upostopos(SUCC upos))")))
2565 ; (use "prog")
2566 ; ; Proof finished.
2567 ; )
2568 ; (save "posuposInd")
2569 ; (display-theorems "posuposInd")
2570
2571
2572 ; (define (animate-posuposind)
2573 ; (begin
2574 ; (deanimate-posuposind)
2575 ; (animate "Postoupossurjective")
2576 ; (animate "Upostopossurjective")
2577 ; (animate "FromPostoupos")
2578 ; (animate "FromUpostopos")
2579 ; (animate "posuposInd")))
2580
2581
2582 ; (define (deanimate-posuposind)
2583 ; (begin
2584 ; (deanimate "Postoupossurjective")
2585 ; (deanimate "Upostopossurjective")
2586 ; (deanimate "FromPostoupos")
2587 ; (deanimate "FromUpostopos")
2588 ; (deanimate "posuposInd")))
2589
2590
2591 ; (begin
2592 ; (animate-posuposind)
2593 ; (deanimate "posuposInd")
2594 ; (animate "posP")
2595 ; (animate "posIndAdd")
2596
2597 ; (display "
2598 ; _______________
2599
2600 ; Comparing posInd with posSuccind .
2601
2602 ; posInd:
2603 ; ")
2604 ; (animate "posInd")
2605 ; (display "
2606 ; _______________
2607
2608 ; posuposInd:
2609 ; ")
2610
2611 ; (animate "posuposInd")
2612 ; (newline)
2613 ; (display "_______________
2614
2615 ; ")
2616 ; (deanimate-posuposind)
2617 ; (deanimate "posInd")
2618 ; (deanimate "posIndAdd")
2619 ; (deanimate "posP")
2620 ; )
2621
2622
2623
2624
2625
2626
2627 ; (arw "upos◁upos" "False")
2628 ; (arw "Upostopos(uposPLUS (Postoupos pos1) (Postoupos pos2))" "pos1+pos2")
2629
2630 ; (aga "SmallerposPlusOne"
2631 ; (pf"all pos1,pos2.(pos1<pos2+1)=(¬(pos2<pos1))"))
2632 ; (display-global-assumptions "SmallerposPlusOne")
2633 ; (aga "LargerposPlusOne"
2634 ; (pf"all pos1,pos2.(pos2+1<pos1)=(pos2<pos1 and (pos1=pos2+1)=False)"))
2635 ; (display-global-assumptions "LargerposPlusOne")
2636 ; (aga "uposlessS1"
2637 ; (pf "all upos1,upos2.(upos1◁SUCC upos2)=(((upos1◁upos2)=False and (upos1=upos2)=False)=False)"))
2638 ; (display-global-assumptions "uposlessS1")
2639 ; (aga "uposlessS2"
2640 ; (pf "all upos1,upos2.(upos1◁SUCC upos2)=(((upos1◁upos2)=False and (upos1=upos2)=False)=False)"))
2641 ; (display-global-assumptions "uposlessS2")
2642 ; (aga "poslessS1"
2643 ; (pf "all pos1,pos2.(pos1<pos2+1)=(((pos1<pos2)=False and (pos1=pos2)=False)=False)"))
2644 ; (display-global-assumptions "poslessS1")
2645 ; (aga "poslessS2"
2646 ; (pf "all pos1,pos2.(pos1<pos2+1)=(((pos1<pos2)=False and (pos2=pos1)=False)=False)"))
2647 ; (display-global-assumptions "poslessS2")
2648 ; (aga "n-1+1"
2649 ; (pf"all upos. Unum◁upos -> upos = SUCC(uposP upos)"))
2650 ; (display-global-assumptions "n-1+1")
2651
2652
2653
2654
2655
2656
2657 ; (display"
2658 ; CV-Induction
2659 ; A^ One -> (all pos.(all pos1.pos1<pos -> A^pos1) -> A^pos) -> all pos A^pos
2660 ; PROOF:
2661 ; ")
2662
2663 ; (set-goal
2664 ; (pf "A^ One -> (all pos.(all pos1.pos1<pos -> A^pos1) -> A^pos) -> all pos A^pos"))
2665 ; (begin
2666 ; (assume "A1" "prog" "pos")
2667 ; (use (pf "all pos1,pos2.(pos1<pos2)=False -> A^ pos2") (pt"pos"))
2668 ; (assume "pos1")
2669 ; (cut(pf"all pos.(all pos2.(pos<pos2)=False -> A^pos2) -> all pos2.(pos+1<pos2)=False -> A^pos2"))
2670 ; (cut(pf"all pos2.(1<pos2)=False -> A^pos2"))
2671 ; (use-with "posuposInd" (make-cterm (pv "pos1") (pf "all pos2.(pos1<pos2)=False -> A^pos2")) (pt "pos1"))
2672
2673 ; (cases)
2674 ; (auto)
2675 ; (assume "pos3")
2676 ; (prop)
2677 ; (assume "pos3")
2678 ; (prop)
2679
2680 ; (assume "pos2" "A<2" "pos3")
2681 ; (simp "LargerposPlusOne")
2682 ; (cases(pt"pos3=pos2+1"))
2683 ; (ng #t)
2684 ; (assume "2=3+1" "T")
2685 ; (simp "2=3+1")
2686 ; (use "prog")
2687 ; (assume "pos4")
2688 ; (simp "SmallerposPlusOne")
2689 ; (use "A<2")
2690 ; (assume "not3=2+1")
2691 ; (use "A<2")
2692 ; (auto)
2693 ; ; Proof finished.
2694 ; )
2695
2696 ; (save "posuposCVind")
2697 ; (display-theorems "posuposCVind")
2698
2699
2700
2701
2702
2703 ; (set-goal
2704 ; (pf "A^ One -> (all pos.(all pos1.pos1<pos -> A^pos1) -> A^pos) -> all pos A^pos"))
2705 ; (begin
2706 ; (assume "A1" "prog" "pos")
2707 ; (use (pf "all pos1,pos2.(pos1<pos2)=False -> A^ pos2") (pt"pos"))
2708 ; (assume "pos1")
2709 ; (cut(pf"all pos.(all pos2.(pos<pos2)=False -> A^pos2) -> all pos2.(pos+1<pos2)=False -> A^pos2"))
2710 ; (cut(pf"all pos2.(1<pos2)=False -> A^pos2"))
2711 ; (use-with "posInd" (make-cterm (pv "pos1") (pf "all pos2.(pos1<pos2)=False -> A^pos2")) (pt "pos1"))
2712
2713 ; (cases)
2714 ; (auto)
2715 ; (assume "pos3")
2716 ; (prop)
2717 ; (assume "pos3")
2718 ; (prop)
2719
2720 ; (assume "pos2" "A<2" "pos3")
2721 ; (simp "LargerposPlusOne")
2722 ; (cases(pt"pos3=pos2+1"))
2723 ; (ng #t)
2724 ; (assume "2=3+1" "T")
2725 ; (simp "2=3+1")
2726 ; (use "prog")
2727 ; (assume "pos4")
2728 ; (simp "SmallerposPlusOne")
2729 ; (use "A<2")
2730 ; (assume "not3=2+1")
2731 ; (use "A<2")
2732 ; (auto)
2733 ; ; Proof finished.
2734 ; )
2735
2736 ; (save "posCVind")
2737 ; (display-theorems "posCVind")
2738
2739
2740
2741
2742 (begin
2743
2744 (add-program-constant
2745 "PosMult"
2746 (mk-arrow (py "pos") (py "pos") (py "pos"))
2747 1 'const 2
2748 )
2749
2750 (add-token
2751 "*"
2752 'add-op
2753 (lambda (x y)
2754 (mk-term-in-app-form
2755 (make-term-in-const-form
2756 (pconst-name-to-pconst "PosMult")) x y)))
2757
2758 (add-display
2759 (py "pos")
2760 (lambda (x)
2761 (let* ((op (term-in-app-form-to-final-op x))
2762 (args (term-in-app-form-to-args x)))
2763 (if (and (term-in-const-form? op)
2764 (string=? "PosMult"
2765 (const-to-name (term-in-const-form-to-const op)))
2766 (= 2 (length args)))
2767 (list 'add-op "*"
2768 (term-to-token-tree (car args))
2769 (term-to-token-tree (cadr args)))
2770 #f))))
2771
2772 (acrs "pos*1" "pos")
2773 (acrs "pos1 * (SZero pos2)" "SZero (pos1 * pos2)")
2774 (acrs "pos1 * (SOne pos2)" "(pos1 * (SZero pos2)) + pos1")
2775
2776 (set! OLD-COMMENT-FLAG COMMENT-FLAG)
2777 (set! COMMENT-FLAG #t)
2778 (display-program-constants "PosMult")
2779
2780 (display"
2781
2782 Test of PosMult:
2783
2784 ")
2785
2786 (display "PosMult 3 1 ")
2787 (pp(nt(pt"PosMult 3 1")))
2788 (display "PosMult 42 42 ")
2789 (pp(nt(pt"PosMult 42 42")))
2790 (display "PosMult 1024 1023 ")
2791 (pp(nt(pt"PosMult 1024 1023")))
2792 (set! COMMENT-FLAG OLD-COMMENT-FLAG)
2793
2794 )
2795
2796
2797
2798 (begin
2799
2800 (display "
2801
2802 uposposTwoexp ₂: upos -> pos
2803
2804 ")
2805
2806 (add-program-constant
2807 "uposposTwoexp"
2808 (mk-arrow (py "upos") (py "pos"))
2809 1 'const 1
2810 )
2811
2812 (add-token
2813 "₂"
2814 'prefix-op
2815 (lambda (x)
2816 (mk-term-in-app-form
2817 (make-term-in-const-form
2818 (pconst-name-to-pconst "uposposTwoexp")) x)))
2819
2820 (add-display
2821 (py "pos")
2822 (lambda (x)
2823 (let* ((op (term-in-app-form-to-final-op x))
2824 (args (term-in-app-form-to-args x)))
2825 (if (and (term-in-const-form? op)
2826 (string=? "uposposTwoexp"
2827 (const-to-name (term-in-const-form-to-const op)))
2828 (= 1 (length args)))
2829 (list 'prefix-op "₂" (term-to-token-tree (car args)))
2830 #f))))
2831
2832 (acrs "₂Unum" "2")
2833 (acrs "₂(SUCC upos)" "SZero(₂upos)")
2834
2835 (display-program-constants "uposposTwoexp")
2836
2837 (display"
2838
2839 Test of ₂ :
2840 ")
2841
2842 (display "₂Unum ")
2843 (pp(nt(pt"₂Unum")))
2844
2845 )
2846
2847
2848 (display "
2849
2850 Some RW-rules involving uposposTwoexp ₂
2851
2852 ")
2853
2854 (begin
2855
2856 (sg "1< ₂upos")
2857 (cases)
2858 (auto)
2859 ; Proof finished.
2860 (trw "1< ₂upos")
2861
2862
2863 (sg "(SOne pos< ₂upos) = (SZero pos< ₂upos)")
2864 (assume "pos")
2865 (ind)
2866 (auto)
2867 ; Proof finished.
2868 (arw "SOne pos< ₂upos" "SZero pos< ₂upos")
2869 )
2870
2871
2872
2873
2874
2875 ;;; F O R M U L A E
2876
2877
2878 ; neg-form? tests wether a formula
2879 ; is a negation of some other
2880
2881 (define(neg-form? formula)
2882 (and (imp-form? formula)
2883 (formula=? (imp-form-to-conclusion formula) (make-atomic-formula (pt "F")))))
2884
2885
2886
2887
2888
2889 ; Equivalence ⇔
2890
2891 (add-token
2892 "⇔"
2893 'and-jct
2894 (lambda (x y)
2895 (make-and (make-imp x y) (make-imp y x))))
2896
2897
2898 (define(equiv-form? formula)
2899 (and (and-form? formula)
2900 (imp-form? (and-form-to-left formula))
2901 (imp-form? (and-form-to-right formula))
2902 (formula=? (imp-form-to-premise (and-form-to-left formula))
2903 (imp-form-to-conclusion (and-form-to-right formula)))
2904 (formula=? (imp-form-to-premise (and-form-to-right formula))
2905 (imp-form-to-conclusion (and-form-to-left formula)))))
2906
2907
2908
2909 ; Disjunction |
2910
2911 (av "p" "q" (py "boole"))
2912
2913 (add-token
2914 "|"
2915 'or-jct
2916 (lambda (x y) (make-ex (pv "q") (mk-and (mk-imp (pf "¬q") x) (mk-imp (pf "q") y)))))
2917
2918
2919
2920 (define(or-form? formula)
2921 (and (ex-form? formula)
2922 (string=? "boole" (type-to-string(cadr (ex-form? (pf "ex q.q")))))
2923 (and-form? (ex-form-to-kernel formula))
2924 (imp-form? (and-form-to-left (ex-form-to-kernel formula)))
2925 (imp-form? (and-form-to-right (ex-form-to-kernel formula)))
2926 (formula=? (imp-form-to-premise (and-form-to-left (ex-form-to-kernel formula)))
2927 (make-atomic-formula (negboole (make-term-in-var-form(ex-form-to-var formula)))))
2928 (formula=? (imp-form-to-premise (and-form-to-right (ex-form-to-kernel formula)))
2929 (make-atomic-formula (make-term-in-var-form(ex-form-to-var formula))))))
2930
2931
2932
2933
2934 ; F O R M U L A - T O - S T R I N G
2935
2936 (define (formula-to-string formula)
2937 (case (tag formula)
2938 ((atom)
2939 (let* ((kernel (atom-form-to-kernel formula))
2940 (string (term-to-string kernel)))
2941 (cond ((string=? "True" string) "T")
2942 ((string=? "False" string) "F")
2943 (else string))))
2944 ((predicate)
2945 (predicate-form-to-string formula))
2946 ((imp)
2947 (let* ((prem (imp-form-to-premise formula))
2948 (concl (imp-form-to-conclusion formula))
2949 (string1 (formula-to-string prem))
2950 (string2 (formula-to-string concl)))
2951 (string-append
2952 (if (or (quant-prime-form? prem) (and-form? prem))
2953 string1
2954 (string-append "(" string1 ")"))
2955 " -> " string2)))
2956 ((and)
2957 (if (equiv-form? formula)
2958 (let*
2959 ((lf (and-form-to-left formula))
2960 (larg (imp-form-to-premise lf))
2961 (rarg (imp-form-to-conclusion lf)))
2962 (string-append "(" (formula-to-string larg) " ⇔ " (formula-to-string rarg) ")" ))
2963 (let* ((left (and-form-to-left formula))
2964 (right (and-form-to-right formula))
2965 (string1 (formula-to-string left))
2966 (string2 (formula-to-string right)))
2967 (string-append
2968 (if (or (quant-prime-form? left) (and-form? left))
2969 string1
2970 (string-append "(" string1 ")"))
2971 " & "
2972 (if (quant-prime-form? right)
2973 string2
2974 (string-append "(" string2 ")"))))))
2975 ((tensor)
2976 (let* ((left (tensor-form-to-left formula))
2977 (right (tensor-form-to-right formula))
2978 (string1 (formula-to-string left))
2979 (string2 (formula-to-string right)))
2980 (string-append
2981 (if (or (quant-prime-form? left) (and-form? left))
2982 string1
2983 (string-append "(" string1 ")"))
2984 " ! "
2985 (if (quant-prime-form? right)
2986 string2
2987 (string-append "(" string2 ")")))))
2988 ((all)
2989 (let ((var (all-form-to-var formula))
2990 (kernel (all-form-to-kernel formula)))
2991 (if (all-form? kernel)
2992 (string-append (symbol->string 'all) " " (var-to-string var)
2993 ","
2994 (let ((string (formula-to-string kernel)))
2995 (substring string
2996 (string-length "all ")
2997 (string-length string))))
2998 (string-append (symbol->string 'all) " " (var-to-string var)
2999 (if (or (prime-form? kernel) (quant-form? kernel))
3000 " " ".")
3001 (formula-to-string kernel)))))
3002 ((ex)
3003 (if (or-form? formula)
3004 (let*
3005 ((form (ex-form-to-kernel formula))
3006 (larg (imp-form-to-conclusion (and-form-to-left form)))
3007 (rarg (imp-form-to-conclusion (and-form-to-right form))))
3008 (string-append "(" (formula-to-string larg) " | " (formula-to-string rarg) ")" ))
3009 (let ((var (ex-form-to-var formula))
3010 (kernel (ex-form-to-kernel formula)))
3011 (if (ex-form? kernel)
3012 (string-append (symbol->string 'ex) " " (var-to-string var)
3013 ","
3014 (let ((string (formula-to-string kernel)))
3015 (substring string
3016 (string-length "ex ")
3017 (string-length string))))
3018 (string-append (symbol->string 'ex) " " (var-to-string var)
3019 (if (or (prime-form? kernel) (quant-form? kernel))
3020 " " ".")
3021 (formula-to-string kernel))))))
3022 ((allnc)
3023 (let ((var (allnc-form-to-var formula))
3024 (kernel (allnc-form-to-kernel formula)))
3025 (if (allnc-form? kernel)
3026 (string-append (symbol->string 'allnc) " " (var-to-string var)
3027 ","
3028 (let ((string (formula-to-string kernel)))
3029 (substring string
3030 (string-length "allnc ")
3031 (string-length string))))
3032 (string-append (symbol->string 'allnc) " " (var-to-string var)
3033 (if (or (prime-form? kernel) (quant-form? kernel))
3034 " " ".")
3035 (formula-to-string kernel)))))
3036 ((exnc)
3037 (let ((var (exnc-form-to-var formula))
3038 (kernel (exnc-form-to-kernel formula)))
3039 (if (exnc-form? kernel)
3040 (string-append (symbol->string 'exnc) " " (var-to-string var)
3041 ","
3042 (let ((string (formula-to-string kernel)))
3043 (substring string
3044 (string-length "exnc ")
3045 (string-length string))))
3046 (string-append (symbol->string 'exnc) " " (var-to-string var)
3047 (if (or (prime-form? kernel) (quant-form? kernel))
3048 " " ".")
3049 (formula-to-string kernel)))))
3050 ((exca)
3051 (let* ((vars (exca-form-to-vars formula))
3052 (kernel (exca-form-to-kernel formula))
3053 (comma-string
3054 (do ((l (cdr vars) (cdr l))
3055 (res (var-to-string (car vars))
3056 (string-append res "," (var-to-string (car l)))))
3057 ((null? l) res))))
3058 (string-append (symbol->string 'exca) " " comma-string
3059 (if (or (prime-form? kernel) (quant-form? kernel))
3060 " " ".")
3061 (formula-to-string kernel))))
3062 ((excl)
3063 (let* ((vars (excl-form-to-vars formula))
3064 (kernel (excl-form-to-kernel formula))
3065 (comma-string
3066 (do ((l (cdr vars) (cdr l))
3067 (res (var-to-string (car vars))
3068 (string-append res "," (var-to-string (car l)))))
3069 ((null? l) res))))
3070 (string-append (symbol->string 'excl) " " comma-string
3071 (if (or (prime-form? kernel) (quant-form? kernel))
3072 " " ".")
3073 (formula-to-string kernel))))
3074 (else (myerror "formula-to-string: formula expected" formula))))
3075
3076
3077
3078
3079 (display"
3080
3081 End of positive.scm
3082
3083 ")