 Digital systems, linear algebra and introduction to formal proof

Solutions to all eight questions of the Oxford Preliminary Examination held on 15 June 2023. Source release: released examination archive, member 2022/T/a10101w1.pdf. The cover identifies Trinity Term 2023. The three section headings and all question labels below follow this historical paper; its grouping is independent of subsequent course changes. Although candidates were asked to attempt at most five questions, every marked subpart is solved here.

In 8(b), the source's parenthetical definition describes a dominating set, while its name suggests a vertex cover. Both readings are treated explicitly. In 8(c)–(d), we make the scopes of the printed quantifiers explicit; in particular, the opening universal quantifiers in 8(c) govern both irreflexivity and transitivity. As usual in first-order logic, domains are nonempty, and graphs are finite simple graphs unless an infinite domain is specified.