Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Digital systems, linear algebra, introduction to formal proof resit / 8 / c

Describe a branching vertex by the first-order logic sentenceand the existence of a sink by $\delta =\exists x\forall y\neg E(x,y)$. The directed path has sinks but no branching vertex; the directed cycle has neither sinks nor branching vertices; the directed arborescence has a branching vertex. Thus the following three sentences distinguish the named structures in order:Here $\beta ,\delta$ are abbreviations for the displayed formulas; replacing them gives sentences in the single-relation first-order signature $\{E\}$. Explicitly, ${\phi }_1$ says that some vertex has no successor and that no vertex has two distinct successors. The truth table across the three structures is:

The conditions distinguish these three finite structures; they are not claimed to characterize all directed paths, cycles or trees among arbitrary directed graphs. Only local out-degrees and the presence of a sink are needed, without quantifying over paths of unbounded length.