Nuprl - Proof: topsortl-properties 1 2 1 2

(47steps total) PrintForm Definitions Lemmas graph 1 3 Sections Graphs Doc

1. the_graph: Graph
2. the_obj: GraphObject(the_graph)
3. L: Vertices(the_graph) List
4. i:Vertices(the_graph). (i L)
5. paren(Vertices(the_graph);dfsl(the_obj;L))
6. no_repeats(Vertices(the_graph)+Vertices(the_graph);dfsl(the_obj;L))
7. dfsl-traversal(the_graph;L;dfsl(the_obj;L))
8. i:Vertices(the_graph). (i L) (inr(i) dfsl(the_obj;L)) & (inl(i) dfsl(the_obj;L))
9. non-trivial-loop-free(the_graph)
10. L1,L2:Vertices(the_graph) List. L = (L1 @ L2) (s1,s2:Vertices(the_graph) List. topsortl(the_obj;L) = (s2 @ s1) & (j:Vertices(the_graph). ((j s1) L1-the_graph- > *j) & ((j s2) L2-the_graph- > *j & L1-the_graph- > *j)))
11. depthfirst-traversal(the_graph;dfsl(the_obj;L))

i:Vertices(the_graph), s1,s2:Vertices(the_graph) List. topsortl(the_obj;L) = (s1 @ [i] @ s2) (j:Vertices(the_graph). j = i i-the_graph- > *j (j s2))

By: Unfold `depthfirst-traversal` -1 THEN Unfold `topsortl` 0 THEN RWO Thm* L:(A+B) List, l1,l2:A List. mapoutl(L) = (l1 @ l2) (L1,L2:(A+B) List. L = (L1 @ L2) & mapoutl(L1) = l1 & mapoutl(L2) = l2) -4 THEN ExRepD THEN RWO Thm* L:(A+B) List, l1,l2:A List. mapoutl(L) = (l1 @ l2) (L1,L2:(A+B) List. L = (L1 @ L2) & mapoutl(L1) = l1 & mapoutl(L2) = l2) -4 THEN ExRepD THEN RWO Thm* L:(A+B) List, a:A. mapoutl(L) = [a] (L1,L2:(A+B) List. L = (L1 @ [inl(a)] @ L2) & mapoutl(L1) = nil & mapoutl(L2) = nil) -5 THEN ExRepD

Generated subgoal:

1 11. i:Vertices(the_graph), s1,s2:traversal(the_graph). (j:Vertices(the_graph). i-the_graph- > *j non-trivial-loop(the_graph;j)) dfsl(the_obj;L) = (s1 @ [inl(i)] @ s2) (j:Vertices(the_graph). j = i i-the_graph- > *j (inl(j) s2))
12. i: Vertices(the_graph)
13. s1: Vertices(the_graph) List
14. s2: Vertices(the_graph) List
15. L1: (Vertices(the_graph)+Vertices(the_graph)) List
16. L2: (Vertices(the_graph)+Vertices(the_graph)) List
17. dfsl(the_obj;L) = (L1 @ L2) (Vertices(the_graph)+Vertices(the_graph)) List
18. mapoutl(L1) = s1
19. L3: (Vertices(the_graph)+Vertices(the_graph)) List
20. L3@0: (Vertices(the_graph)+Vertices(the_graph)) List
21. L2 = (L3 @ L3@0)
22. L4: (Vertices(the_graph)+Vertices(the_graph)) List
23. L5: (Vertices(the_graph)+Vertices(the_graph)) List
24. L3 = (L4 @ [inl(i)] @ L5)
25. mapoutl(L4) = nil
26. mapoutl(L5) = nil
27. mapoutl(L3@0) = s2
28. j: Vertices(the_graph)
29. j = i
30. i-the_graph- > *j
(j s2) 6 steps

About:

(47steps total) PrintForm Definitions Lemmas graph 1 3 Sections Graphs Doc