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

The nonempty simple graphs having an independent vertex cover of size at most two. The witnesses $x,y$ select the cover. The clause $\neg E(x,y)$ makes the selected vertices nonadjacent; the universal clause forbids every edge whose two endpoints both lie outside the selected set.

The witnesses need not be distinct, so a one-vertex cover is permitted by choosing $x=y$. A nonempty edgeless graph also satisfies the formula. The empty graph does not, because the existential quantifiers have no witnesses. Here independent vertex cover has its standard vertex cover meaning; 8(b)'s differing parenthetical definition is addressed separately below.

The source's explicit parenthetical condition is domination: every unselected vertex has a neighbour in the selected set. Together with independence this defines an independent dominating set. A first-order sentence expressing that definition with size at most three isThe finite conjunctions and disjunctions abbreviate three explicitly fixed terms, so this is a first-order formula. Repeated witnesses allow one- or two-element choices; the first conjunction enforces independence only between distinct selected vertices. The last clause says that every vertex is selected or adjacent to a selected vertex. With the usual nonempty-domain convention, any such choice has size at least one, so repeated witnesses cover all possibilities of size at most three.

For the standard meaning of independent vertex cover, replace the domination clause byThis instead demands that every edge has a selected endpoint. These interpretations differ: in a triangle in a graph, any singleton is an independent dominating set, but no independent vertex cover exists. Giving both clauses avoids silently treating the source's two definitions as equivalent.

Read the initial universal quantifiers as governing the conjunction of irreflexivity and transitivity. Explicitly, the intended first-order sentence assertsThus $Q$ is an irreflexive relation, a transitive relation, and a serial relation.

Suppose a first-order model had a finite nonempty domain of cardinality $N$. Choose $a_0$. Seriality supplies successive elements $a_1,\dots ,a_N$ with $Q(a_i,a_{i+1})$. By the pigeonhole principle, $a_i=a_j$ for some $i<j$. Repeated transitivity along that part of the chain gives $Q(a_i,a_j)=Q(a_i,a_i)$, contradicting irreflexivity. Hence there is no finite nonempty model. This is the infinite-model property of a serial strict partial order.

An infinite model exists: take domain $\mathbb{N}$ and $Q(x,y)$ to mean $x<y$. It is irreflexive and transitive, and $y=x+1$ witnesses seriality for every $x$.

The quantifier-scope convention matters: giving each printed universal quantifier only the immediately following atomic scope would leave the transitivity implication with free variables and would not express the claimed theorem. The explicit parenthesisation above records the reading under which the source's requested assertion is valid.

Use broad scope up to the enclosing parenthesis, consistent with (c). Thus the first conjunct is read as$f(u,t)$ is not free for substitution for $z$. The free occurrence of $z$ in $Q(z,t)$ lies under $\exists t$; inserting $f(u,t)$ there would capture its $t$. Rename that bound variable to a fresh $s$ first, using alpha equivalence. The capture-avoiding first-order substitution is thenEvery occurrence of $z$ in the original formula is free, so all four are replaced. The variable $t$ introduced by the term remains free, and the final $\exists yQ(y,y)$ is unchanged.

Under the same scope convention, $g(t,z)$ is not free for substitution for $y$. The occurrence of $y$ inside $Q(f(x,y),f(z,z))$ is free but lies under $\exists t$, so its replacement would capture the new $t$. Rename this binder to fresh $s$. Substitute only for the free $y$ occurrences in the first conjunct:The two occurrences of $y$ in the final conjunct are bound variables and remain unchanged. The inserted $t,z$ remain free.

If instead one gives the printed $\exists t$ only the scope $Q(z,t)$, this part's free-for-substitution answer becomes yes, because neither free $y$ occurrence then lies under that binder. Under that alternative parsing, the result is explicitlyThe narrower reading does not change the negative answer in (1): its occurrence of $z$ inside $Q(z,t)$ still requires renaming that binder before substitution. The broad-scope answers above give a single consistent parsing across the paper.

Push the outer negation inward using De Morgan's laws and the duality of universal and existential quantifiers. Negating the outer universal quantifier first gives an existential $x$. Negating its conjunction produces either $\forall y\neg P(x,y)$ or a witness $z$ for failure of the other conjunct. The implication fails precisely when $\neg Q(z)$ holds but its consequent fails. Therefore a negation normal form isAll negations now apply directly to atomic formulas. In particular, the $\neg Q(z)$ remains negative: failure of an implication requires its antecedent to be true.