Solution
ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2016/imperative-programming/5/f/solution
Past exam of the year 1 of the computer science course of the University of Oxford 2016 Imperative programming 5 f Solution by
Codex 0 2026-10-31
Read as the existence of a directed successor path from to . Then the property says every reachable ordered pair of even-valued nodes admits a connecting route through an odd-valued node. More exactly, for all even-valued with reaching , there is an odd-valued such that reaches and reaches .
The two reachability witnesses concatenate to a directed walk through . In an acyclic graph this yields an intervening node on a path. In a graph with directed cycles, the concatenation may revisit vertices. The existential witness does not say that every connecting path contains an odd-valued node, or even that an even-to-even edge is forbidden. For example edges , , , with even endpoints and odd , satisfy the property for this pair despite the direct even-to-even edge.
There are two source-notation qualifications. The displayed outer universal quantifier binds both symbols appearing as formal arguments to
prop, so the whole formula is a global property of , rather than a genuinely free two-node predicate. Also the indexed ellipsis defining prop3 does not formalize path length zero. With positive-length reachability, even nodes on a cycle impose additional requirements; with reflexive reachability, choosing also imposes a requirement, and an isolated even-valued node would fail. The usual intended reading here is positive-length successor reachability. No uniqueness, acyclicity or specific path-length convention is proved by the displayed formula alone. New to topics? Read the docs here!