Computing EN Exam

Logic for Computer Science

1,010 cards 0 Version 1, updated November 19, 2026

By downloading or studying this deck you agree to the deck directory terms, including the deck's licence.

Logic flashcards for computer science students: propositional and predicate logic, from truth tables and normal forms to natural deduction, resolution, SAT solving, the metatheorems and logic at work, with 18 exam-style exercises.

What's inside

  • Propositional Logic — formulas and truth tables, semantic notions and the standard laws, normal forms and the Tseitin encoding, functional completeness, natural deduction, resolution, DPLL and CDCL, soundness, completeness and compactness.
  • Predicate Logic — syntax and substitution, structures and truth, formalising requirements, natural deduction with quantifiers and equality, prenex and Skolem forms, unification and resolution, the metatheorems, Prolog and Datalog, SAT and SMT solvers as tools.
  • Practice — 18 exam-style exercises: formalisations, normal forms, Fitch proofs, DPLL and CDCL, unification and refutations, counter-models and a Prolog program.

Every card is written in our own words with our own examples, and every worked example, trace and model answer is checked by script. The Practice deck is an exam: it draws three exercises at random, and you grade your answers against each marking scheme. Proofs use the Fitch system and rule names of forall x: Calgary by P. D. Magnus, Tim Button and others (CC BY 4.0); scope and checks also draw on the Open Logic Project's Open Logic Text (CC BY 4.0).

1,010 cards in total.

What's inside

  • 1 Propositional Logic 485 cards
  • 2 Predicate Logic 507 cards
  • Practice Exam 18 cards

A few cards

1 Propositional Logic

485 cards

Front

Proposition (declarative sentence): definition

Back

A sentence that is either true or false, such as "the build passed". Whether anyone knows its truth value, or how it would be found out, plays no role. That every proposition has exactly one of the two truth values is the principle of bivalence.

core · Also called a statement. Many-valued and fuzzy logics drop bivalence; this deck keeps it.

Front

"The build passed", "Did the build pass?" and "Run the build!": which are propositions

Back

Only the first: it is true or false. A question asks for a truth value and a command asks for an action, so neither has one. The answer "yes, it passed" is a proposition again.

core

Front

Atom (propositional logic): definition

Back

A proposition that the formalisation does not break down further, written as a letter pp, qq, rr, … The logic sees nothing inside an atom: it only assumes that each atom is true or false, and that any combination of values for different atoms is possible.

core · Also called an atomic formula, a propositional variable, a sentence letter or, in programs, a Boolean variable.

Front

"The deploy failed because the disk was full": why "because" is not a truth-functional connective

Back

A connective is truth-functional if the truth values of the parts fix the truth value of the whole. Here both parts can be true while the whole is true (the full disk caused the failure) or false (a bad configuration did), so "because" has no truth table.

core · Neither do "before", "it is known that" or "necessarily". Propositional logic, or sentential logic, has truth-functional connectives only.

Front

Connectives of propositional logic: names and notation

Back

Negation ¬φ\lnot\varphi ("not"), conjunction φ∧ψ\varphi \land \psi ("and"), disjunction φ∨ψ\varphi \lor \psi ("or"), conditional φ→ψ\varphi \to \psi ("if … then") and biconditional φ↔ψ\varphi \leftrightarrow \psi ("if and only if"); ⊤\top and ⊥\bot are constants for true and false.

core · Books also write ∼\sim for ¬\lnot, &\& for ∧\land, ⊃\supset for →\to and ≡\equiv for ↔\leftrightarrow; programs write !, &&, ||.

Front

¬φ\lnot\varphi is true exactly when φ\varphi is  ; φ∧ψ\varphi \land \psi is true exactly when both parts are true; φ∨ψ\varphi \lor \psi is false exactly when both parts are false.

Back

¬φ\lnot\varphi is true exactly when φ\varphi is false; φ∧ψ\varphi \land \psi is true exactly when both parts are true; φ∨ψ\varphi \lor \psi is false exactly when both parts are false.

core · The parts of a conjunction are its conjuncts, those of a disjunction its disjuncts.

2 Predicate Logic

507 cards

Front

Predicate logic: what it adds to propositional logic

Back

Names for objects, predicates for their properties and relations, and two quantifiers: the universal ∀\forall ("for all") and the existential ∃\exists ("there is", meaning at least one). An atom is no longer an unanalysed letter pp but a statement about objects, such as Admin(d)\mathit{Admin}(d).

core · Also called first-order logic or quantificational logic. Frege 1879 and, independently, Peirce 1885.

Front

"Every merged commit was reviewed; commit 41 is merged; so commit 41 was reviewed": why propositional logic calls it invalid

Back

Its three sentences contain no connective, so they become three unrelated atoms pp, qq, rr, and the valuation with pp and qq true and rr false refutes p,q⊨rp, q \models r. What links them lies inside the sentences: "merged", "reviewed" and "commit 41" each occur twice.

core · With predicates: ∀x (Merged(x)→Reviewed(x))\forall x\, (\mathit{Merged}(x) \to \mathit{Reviewed}(x)) and Merged(c)\mathit{Merged}(c) entail Reviewed(c)\mathit{Reviewed}(c).

Front

Down(a)∨Down(b)\mathit{Down}(a) \lor \mathit{Down}(b) as a way to say "some replica is down": what goes wrong

Back

It speaks only of the two replicas that have names. If a third replica is down, or one without a name, the disjunction is false although the sentence is true, and it must be rewritten whenever a replica is added. ∃x Down(x)\exists x\, \mathit{Down}(x) covers every object of the domain, named or not.

core

Front

First-order logic: what "first-order" means

Back

Its quantifiers range over the objects of the domain only: ∀x\forall x and ∃x\exists x bind variables that stand for individuals. Quantifying over predicates, sets or functions, as in "every property of xx", is second-order logic and outside this deck.

core · Abbreviated FOL. Second-order logic can say more, but no proof system captures all its valid sentences.

Front

"xx and yy have the same permissions" written as ∀P (P(x)↔P(y))\forall P\, (P(x) \leftrightarrow P(y)): why it is not a first-order formula

Back

The quantifier ∀P\forall P binds a predicate, and first-order quantifiers bind only variables for objects. A first-order version has to go through the predicates of the signature one by one: (Reads(x)↔Reads(y))∧(Writes(x)↔Writes(y))(\mathit{Reads}(x) \leftrightarrow \mathit{Reads}(y)) \land (\mathit{Writes}(x) \leftrightarrow \mathit{Writes}(y)).

core

Front

Signature of a first-order language: definition

Back

The set of its non-logical symbols: constant symbols, function symbols and predicate symbols, each function and predicate symbol with a fixed arity. It is chosen for the application, as {d,owner,Admin,Owns}\{d, \mathit{owner}, \mathit{Admin}, \mathit{Owns}\} might be for access rules.

core · Also called the vocabulary or the language.

Practice

18 cards

Front

Exercise 1: A release gate

A CI pipeline decides whether a change is released. The symbolisation key:

  • tt: the change's test suite passes;
  • ss: its security scan passes;
  • hh: the change is a hotfix;
  • aa: a second engineer has approved it;
  • rr: the change is released.

The release policy:

  • (R1) A change is released only if its tests pass.
  • (R2) A change that is not a hotfix is released only if its security scan passes and a second engineer has approved it.
  • (R3) A hotfix whose tests pass is released.
  • (R4) Without a second approval, a change is released only if it is a hotfix.

A colleague formalised R4 as ¬a∧h→r\lnot a \land h \to r.

1.

1.1 Formalise the release-gate requirements R1, R2 and R3 with the atoms tt, ss, hh, aa and rr. (3 points)

2.

1.2 What does the colleague's formula ¬a∧h→r\lnot a \land h \to r for the release-gate requirement R4, "without a second approval, a change is released only if it is a hotfix", say, and on which valuations does it differ from R4? (2 points)

3.

1.3 For which of the 16 combinations of hh, tt, ss and aa do the release-gate requirements R1, R2 and R3 force the release, forbid it, or leave it open? (3 points)

4.

1.4 Does the release-gate requirement R4, "without a second approval, a change is released only if it is a hotfix", follow from R1, R2 and R3, and does "every hotfix is released"? (2 points)

Back

1.

1.1 Formalise the release-gate requirements R1, R2 and R3 with the atoms tt, ss, hh, aa and rr. (3 points)

3 points: R1 as r → t (1) · R2 as r → h ∨ (s ∧ a), or an equivalent such as ¬h ∧ r → s ∧ a or ¬h → (r → s ∧ a); a formula that makes s ∧ a sufficient for the release instead of necessary earns nothing (1) · R3 as h ∧ t → r, or h → (t → r); any formula with the same truth table as these counts (1)

Model answer: R1 is r→tr \to t: "only if" marks the necessary condition, which goes on the right. R2 is ¬h∧r→s∧a\lnot h \land r \to s \land a, equivalently r→h∨(s∧a)r \to h \lor (s \land a): for a change that is not a hotfix, a release needs both checks. R3 is h∧t→rh \land t \to r; here "a hotfix whose tests pass" is the sufficient condition. A formula that is equivalent to one of these, as a truth table shows, is just as right.

2.

1.2 What does the colleague's formula ¬a∧h→r\lnot a \land h \to r for the release-gate requirement R4, "without a second approval, a change is released only if it is a hotfix", say, and on which valuations does it differ from R4? (2 points)

2 points: it says that every hotfix without a second approval is released, while R4 is r ∧ ¬a → h, equivalently ¬a → (r → h): an unapproved release must be a hotfix; the colleague has swapped what R4 makes necessary with what it allows (1) · they differ when a is false and either r is true with h false, where R4 fails and the colleague's formula holds, or h is true with r false, where R4 holds and the colleague's formula fails; one valuation of each kind is enough, such as a and h false with r true, and a false, h true, r false (1)

Model answer: The colleague's formula says "every hotfix without a second approval is released". R4 says that a release without an approval must be a hotfix: r∧¬a→hr \land \lnot a \to h. The two come apart in two ways, both with aa false. With rr true and hh false, an unapproved non-hotfix is released: R4 is broken, while the colleague's formula holds, since its antecedent fails. With hh true and rr false, an unapproved hotfix is held back: R4 holds, the colleague's formula fails. The values of tt and ss don't matter, so each case covers four valuations.

3.

1.3 For which of the 16 combinations of hh, tt, ss and aa do the release-gate requirements R1, R2 and R3 force the release, forbid it, or leave it open? (3 points)

3 points: forced exactly when h and t are true, in 4 combinations: R3 demands r, and R1 and R2 allow it, R2 because the change is a hotfix (1) · forbidden in 11: the 8 with t false, by R1, and the 3 with t true, h false and not both s and a, by R2 (1) · open in 1, h false with t, s and a true, where every requirement holds whatever r is; no combination makes the three requirements clash, so 4 + 11 + 1 = 16 (1)

Model answer: For each valuation of hh, tt, ss, aa, try both values of rr.

  • Forced: hh and tt true. R3 needs rr true, R1 is satisfied by tt, and R2 says nothing about hotfixes. 4 combinations, as ss and aa are free.
  • Forbidden: tt false, where R1 rules out rr: 8 combinations. And tt true, hh false and not both ss and aa, where R2 rules it out: 3 more. 11 in all.
  • Open: hh false with tt, ss, aa true. Every requirement holds with rr true and with rr false, so the policy leaves the decision to someone else.

No combination is left without a value of rr that meets all three requirements: 4+11+1=164 + 11 + 1 = 16.

4.

1.4 Does the release-gate requirement R4, "without a second approval, a change is released only if it is a hotfix", follow from R1, R2 and R3, and does "every hotfix is released"? (2 points)

2 points: R4 follows, from R2 alone: a valuation with r true, a false and h false makes R2 demand s ∧ a, which a false breaks, so every model of R2 satisfies r ∧ ¬a → h (1) · h → r does not follow: h true, t false and r false, with any s and a, satisfy R1, R2 and R3 and falsify it; a hotfix whose tests fail is not released (1)

Model answer: R4 follows. Work backwards: to falsify r∧¬a→hr \land \lnot a \to h, a valuation needs rr true, aa false and hh false. Then R2, ¬h∧r→s∧a\lnot h \land r \to s \land a, has a true antecedent and a false consequent. So no valuation satisfies R2 and falsifies R4; R4 is the contrapositive part of R2. "Every hotfix is released" does not follow: hh true, tt false, rr false satisfies R1 (no release), R2 (a hotfix) and R3 (the tests fail), whatever ss and aa are, and it falsifies h→rh \to r.

Front

Exercise 2: Refactoring a write guard

A file service guards writes with the condition !(locked && !admin) && (admin || owner). With ll for locked, aa for admin and oo for owner, the guard is
G1=¬(l∧¬a)∧(a∨o).G_1 = \lnot(l \land \lnot a) \land (a \lor o).
Two refactorings are proposed: G2=a∨(o∧¬l)G_2 = a \lor (o \land \lnot l), from admin || (owner && !locked), and G3=(a∨o)∧¬lG_3 = (a \lor o) \land \lnot l, from (admin || owner) && !locked.

1.

2.1 Show by a chain of named equivalence laws that the write guard G1=¬(l∧¬a)∧(a∨o)G_1 = \lnot(l \land \lnot a) \land (a \lor o) is equivalent to its refactoring G2=a∨(o∧¬l)G_2 = a \lor (o \land \lnot l). (3 points)

2.

2.2 On which valuations do the write guard G1=¬(l∧¬a)∧(a∨o)G_1 = \lnot(l \land \lnot a) \land (a \lor o) and the refactoring G3=(a∨o)∧¬lG_3 = (a \lor o) \land \lnot l differ, and which of the two entails the other? (2 points)

3.

2.3 Write the refactored write guard G2=a∨(o∧¬l)G_2 = a \lor (o \land \lnot l) with →\to as its only connective. (2 points)

4.

2.4 The write guard G1=¬(l∧¬a)∧(a∨o)G_1 = \lnot(l \land \lnot a) \land (a \lor o) has passed. Does it follow that the user owns the file if the file is locked, and that the file is unlocked and owned if the user is not an admin? (2 points)

Back

1.

2.1 Show by a chain of named equivalence laws that the write guard G1=¬(l∧¬a)∧(a∨o)G_1 = \lnot(l \land \lnot a) \land (a \lor o) is equivalent to its refactoring G2=a∨(o∧¬l)G_2 = a \lor (o \land \lnot l). (3 points)

3 points: De Morgan turns ¬(l ∧ ¬a) into ¬l ∨ ¬¬a and double negation into ¬l ∨ a; the negated conditional and the conditional law, by way of l → a, get there too (1) · commutativity lines up (a ∨ ¬l) ∧ (a ∨ o), with a as the common disjunct (1) · distributivity, read from right to left, gives a ∨ (¬l ∧ o), and commutativity a ∨ (o ∧ ¬l); any chain in which each step applies one named law counts, while a truth table alone earns 1 point (1)

Model answer:

  ¬(l ∧ ¬a) ∧ (a ∨ o)
≡ (¬l ∨ ¬¬a) ∧ (a ∨ o)    De Morgan
≡ (¬l ∨ a) ∧ (a ∨ o)      double negation
≡ (a ∨ ¬l) ∧ (a ∨ o)      commutativity
≡ a ∨ (¬l ∧ o)            distributivity
≡ a ∨ (o ∧ ¬l)            commutativity

The key step factors the common disjunct aa out of two clauses, the distributive law of ∨\lor over ∧\land read backwards. By the replacement theorem each step may rewrite a part of the formula. The first two steps can also go through ¬(l∧¬a)≡¬¬(l→a)≡l→a≡¬l∨a\lnot(l \land \lnot a) \equiv \lnot\lnot(l \to a) \equiv l \to a \equiv \lnot l \lor a.

2.

2.2 On which valuations do the write guard G1=¬(l∧¬a)∧(a∨o)G_1 = \lnot(l \land \lnot a) \land (a \lor o) and the refactoring G3=(a∨o)∧¬lG_3 = (a \lor o) \land \lnot l differ, and which of the two entails the other? (2 points)

2 points: they differ exactly when a and l are both true, with o either way: G₁ lets an admin write to a locked file and G₃ does not (1) · G₃ ⊨ G₁ but not G₁ ⊨ G₃: whenever G₃ holds, l is false and a ∨ o is true, which makes G₁ true; the two valuations above refute the other direction (1)

Model answer: G1G_1 is equivalent to a∨(o∧¬l)a \lor (o \land \lnot l), so it is true for every admin and for an owner of an unlocked file. G3G_3 demands an unlocked file from everyone. They differ exactly when aa and ll are true, with oo true or false: there G1G_1 is true and G3G_3 false. In every other valuation they agree, so G3⊨G1G_3 \models G_1, and G1⊭G3G_1 \not\models G_3. The refactoring is stricter: it locks admins out of locked files.

3.

2.3 Write the refactored write guard G2=a∨(o∧¬l)G_2 = a \lor (o \land \lnot l) with →\to as its only connective. (2 points)

2 points: (o → l) → a; any formula with → alone that is equivalent to G₂ counts, such as (o → (o → l)) → a (1) · the reason: by the conditional law (o → l) → a is ¬(o → l) ∨ a, and by the negated conditional ¬(o → l) is o ∧ ¬l, which gives G₂ up to commutativity; an equivalent formula that still uses ¬, such as ¬a → ¬(o → l), earns 1 point in all (1)

Model answer: (o→l)→a(o \to l) \to a. By the conditional law it is ¬(o→l)∨a\lnot(o \to l) \lor a, and by the negated conditional ¬(o→l)≡o∧¬l\lnot(o \to l) \equiv o \land \lnot l, so it is (o∧¬l)∨a(o \land \lnot l) \lor a, which is G2G_2. Read as code: if owner implies locked, which fails only for an owner of an unlocked file, the write needs admin. With two arrows this is the only such formula over aa, oo, ll, and one arrow can't mention three atoms.

4.

2.4 The write guard G1=¬(l∧¬a)∧(a∨o)G_1 = \lnot(l \land \lnot a) \land (a \lor o) has passed. Does it follow that the user owns the file if the file is locked, and that the file is unlocked and owned if the user is not an admin? (2 points)

2 points: G₁, l ⊭ o: a and l true with o false make G₁ and l true and o false, since an admin may write to a locked file (1) · G₁, ¬a ⊨ ¬l ∧ o: with a false, ¬(l ∧ ¬a) forces l false and a ∨ o forces o true; the only valuation that satisfies G₁ with a false has l false and o true (1)

Model answer: The first does not follow. The valuation with aa and ll true and oo false makes G1G_1 true, as ¬(l∧¬a)\lnot(l \land \lnot a) holds through aa and a∨oa \lor o through aa, and ll true, yet oo is false: an admin who doesn't own the file may write to it although it is locked. The second follows. With aa false, ¬(l∧¬a)\lnot(l \land \lnot a) reduces to ¬l\lnot l and a∨oa \lor o to oo, so every valuation that makes G1G_1 and ¬a\lnot a true makes ¬l∧o\lnot l \land o true.

Front

Exercise 3: A dark-launch rule

A feature-flag service checks the dark-launch rule ρ=(b∨i)→(b↔e)\rho = (b \lor i) \to (b \leftrightarrow e): for a request from a beta user (bb) or from an internal tester (ii), the experiment flag (ee) is on exactly when the user is a beta user. Its monitor looks for the requests that violate the rule, those that satisfy ¬ρ\lnot\rho. Truth tables list the atoms in the order bb, ii, ee. The Tseitin encoding follows the knowledge deck: a new variable for each subformula built by a binary connective, numbered from the inside out, the clauses of its definition, and a unit clause for the whole formula, in which a negation becomes a negated literal.

1.

3.1 Bring the dark-launch violation ¬((b∨i)→(b↔e))\lnot((b \lor i) \to (b \leftrightarrow e)) into negation normal form, naming the law used at each step. (2 points)

2.

3.2 Convert the dark-launch rule ρ=(b∨i)→(b↔e)\rho = (b \lor i) \to (b \leftrightarrow e) itself to CNF by laws, and simplify it to as few clauses as you can. (2 points)

3.

3.3 Read the canonical DNF of the dark-launch violation ¬((b∨i)→(b↔e))\lnot((b \lor i) \to (b \leftrightarrow e)) off its truth table, and shorten it. (2 points)

4.

3.4 Give the Tseitin encoding of the dark-launch violation ¬((b∨i)→(b↔e))\lnot((b \lor i) \to (b \leftrightarrow e)): the definitions, the number of clauses and of models, and how the encoding settles whether the rule ρ\rho itself is valid. (3 points)

Back

1.

3.1 Bring the dark-launch violation ¬((b∨i)→(b↔e))\lnot((b \lor i) \to (b \leftrightarrow e)) into negation normal form, naming the law used at each step. (2 points)

2 points: the negated conditional gives (b ∨ i) ∧ ¬(b ↔ e) (1) · the negated biconditional gives (b ∧ ¬e) ∨ (¬b ∧ e), so an NNF is (b ∨ i) ∧ ((b ∧ ¬e) ∨ (¬b ∧ e)); the route through b ↔ ¬e and the biconditional law counts, and so does any equivalent formula in NNF, such as a CNF (1)

Model answer:

  ¬((b ∨ i) → (b ↔ e))
≡ (b ∨ i) ∧ ¬(b ↔ e)              negated conditional
≡ (b ∨ i) ∧ ((b ∧ ¬e) ∨ (¬b ∧ e))  negated biconditional

Negations now stand only on atoms, and only ∧\land and ∨\lor are left. A violation is a request from a beta user or a tester in which beta and experiment disagree.

2.

3.2 Convert the dark-launch rule ρ=(b∨i)→(b↔e)\rho = (b \lor i) \to (b \leftrightarrow e) itself to CNF by laws, and simplify it to as few clauses as you can. (2 points)

2 points: the conditional law and De Morgan give (¬b ∧ ¬i) ∨ (b ↔ e), the biconditional and conditional laws (¬b ∧ ¬i) ∨ ((¬b ∨ e) ∧ (b ∨ ¬e)), and distributing gives (¬b ∨ e) ∧ (¬b ∨ b ∨ ¬e) ∧ (¬i ∨ ¬b ∨ e) ∧ (¬i ∨ b ∨ ¬e), with ¬b ∨ ¬b ∨ e shortened by idempotence; any equivalent CNF earns this point (1) · the clause ¬b ∨ b ∨ ¬e goes by excluded middle, domination and identity, and ¬b ∨ e absorbs ¬i ∨ ¬b ∨ e, which leaves (¬b ∨ e) ∧ (b ∨ ¬i ∨ ¬e), the only CNF with two clauses; that no CNF has fewer needn't be shown (1)

Model answer:

  (b ∨ i) → (b ↔ e)
≡ ¬(b ∨ i) ∨ (b ↔ e)                          conditional law
≡ (¬b ∧ ¬i) ∨ ((¬b ∨ e) ∧ (b ∨ ¬e))           De Morgan, biconditional and conditional laws
≡ (¬b ∨ e) ∧ (¬b ∨ b ∨ ¬e)
    ∧ (¬i ∨ ¬b ∨ e) ∧ (¬i ∨ b ∨ ¬e)           distributivity, idempotence
≡ (¬b ∨ e) ∧ (¬i ∨ ¬b ∨ e) ∧ (¬i ∨ b ∨ ¬e)    excluded middle, domination, identity
≡ (¬b ∨ e) ∧ (b ∨ ¬i ∨ ¬e)                    absorption, commutativity

The first clause says that a beta user gets the experiment, the second that a tester who is not a beta user doesn't. One clause can't do: ρ\rho is false in three of the eight rows, and a clause over bb, ii and ee is false in one, two or four.

3.

3.3 Read the canonical DNF of the dark-launch violation ¬((b∨i)→(b↔e))\lnot((b \lor i) \to (b \leftrightarrow e)) off its truth table, and shorten it. (2 points)

2 points: the violation is true in the rows TTF, TFF and FTT, so the canonical DNF is (b ∧ i ∧ ¬e) ∨ (b ∧ ¬i ∧ ¬e) ∨ (¬b ∧ i ∧ e) (1) · the first two terms differ only in i and merge into b ∧ ¬e, which gives (b ∧ ¬e) ∨ (¬b ∧ i ∧ e): a beta user without the experiment, or a tester who is not a beta user with it; any equivalent DNF with two terms counts (1)

Model answer:

b i e   ¬ρ
T T T   F
T T F   T
T F T   F
T F F   T
F T T   T
F T F   F
F F T   F
F F F   F

One minterm per true row gives (b∧i∧¬e)∨(b∧¬i∧¬e)∨(¬b∧i∧e)(b \land i \land \lnot e) \lor (b \land \lnot i \land \lnot e) \lor (\lnot b \land i \land e). The first two merge by distributivity, excluded middle and identity into b∧¬eb \land \lnot e, so ¬ρ≡(b∧¬e)∨(¬b∧i∧e)\lnot\rho \equiv (b \land \lnot e) \lor (\lnot b \land i \land e). One term can't do: TFF and FTT differ in every atom.

4.

3.4 Give the Tseitin encoding of the dark-launch violation ¬((b∨i)→(b↔e))\lnot((b \lor i) \to (b \leftrightarrow e)): the definitions, the number of clauses and of models, and how the encoding settles whether the rule ρ\rho itself is valid. (3 points)

3 points: x₁ ↔ (b ∨ i) with 3 clauses, x₂ ↔ (b ↔ e) with 4, x₃ ↔ (x₁ → x₂) with 3, and the unit clause ¬x₃ for the outer negation: 11 clauses with 3 new variables; other numbering of the variables counts (1) · 3 models, one for each violation TTF, TFF and FTT, since each new variable must take the value of its subformula, for TFF x₁ true, x₂ false, x₃ false (1) · ρ is valid exactly when ¬ρ is unsatisfiable, so a SAT solver gets this encoding: it is satisfiable, so ρ is not valid, and its models are the violations; that the encoding is only equisatisfiable with ¬ρ, and that the encoding of ρ has 5 models, needn't be said (1)

Model answer:

x₁ ↔ (b ∨ i)       {¬x₁, b, i}, {x₁, ¬b}, {x₁, ¬i}
x₂ ↔ (b ↔ e)       {¬x₂, ¬b, e}, {¬x₂, b, ¬e}, {x₂, b, e}, {x₂, ¬b, ¬e}
x₃ ↔ (x₁ → x₂)     {¬x₃, ¬x₁, x₂}, {x₃, x₁}, {x₃, ¬x₂}
¬x₃                 the outer negation, as a literal

11 clauses, 3 new variables. The definitions force each xkx_k to the value of its subformula, so every model of ¬ρ\lnot\rho extends in exactly one way and the encoding has 3 models; for TFF they are x1x_1 true, x2x_2 false, x3x_3 false. To decide whether ρ\rho is valid, ask whether ¬ρ\lnot\rho is satisfiable: this encoding is, so ρ\rho is not valid, and each model the solver returns is a violating request. The encoding of ρ\rho shares the ten definition clauses and ends with x3x_3; it has 5 models.

Front

Exercise 4: A quorum monitor's single operator

A cluster monitor's rule language has a single operator, lost(x, y, z), which is true when at most one of its three inputs is true: fed with three replicas' heartbeats, it raises the alarm when the quorum is lost. Rules may nest it and repeat inputs. In formulas it is written lost(φ,ψ,χ)\mathrm{lost}(\varphi, \psi, \chi). A formula is self-dual if negating all its atoms negates its value: v′(φ)=¬v(φ)v'(\varphi) = \lnot v(\varphi) whenever the valuation v′v' gives every atom the opposite value of vv. The majority function maj(p,q,r)\mathrm{maj}(p, q, r) is true when at least two of its inputs are. Two functions gg and hh of pp, qq, rr, and lost\mathrm{lost} itself:

p q r   lost(p, q, r)   g   h
T T T   F               T   T
T T F   F               T   T
T F T   F               F   F
T F F   T               T   T
F T T   F               F   F
F T F   T               T   T
F F T   T               F   F
F F F   T               F   T
1.

4.1 Express ¬p\lnot p and the majority function maj(p,q,r)\mathrm{maj}(p, q, r) with the quorum monitor's operator lost\mathrm{lost} alone. (2 points)

2.

4.2 Prove by structural induction that every formula built from atoms with the quorum monitor's operator lost\mathrm{lost} alone is self-dual. (3 points)

3.

4.3 Which of the functions gg and hh given by their truth tables can the quorum monitor express with lost\mathrm{lost} alone? Give a formula for one and a reason for the other. (2 points)

4.

4.4 Show that the quorum monitor's operator lost\mathrm{lost} together with the constant ⊥\bot, an input wired to false, is functionally complete, and say which of Post's five classes lost\mathrm{lost} alone lies in. (2 points)

Back

1.

4.1 Express ¬p\lnot p and the majority function maj(p,q,r)\mathrm{maj}(p, q, r) with the quorum monitor's operator lost\mathrm{lost} alone. (2 points)

2 points: ¬p = lost(p, p, p), since three copies of p have at most one true input exactly when p is false (1) · maj(p, q, r) = lost(m, m, m) with m = lost(p, q, r), as "at least two true" is the negation of "at most one true"; lost(p, lost(p, p, p), lost(p, q, r)) also works, and so does any other correct formula with lost alone (1)

Model answer: ¬p=lost(p,p,p)\lnot p = \mathrm{lost}(p, p, p): if pp is true, all three inputs are; if it is false, none is. With that negation, maj(p,q,r)=¬lost(p,q,r)=lost(m,m,m)\mathrm{maj}(p, q, r) = \lnot\mathrm{lost}(p, q, r) = \mathrm{lost}(m, m, m) for m=lost(p,q,r)m = \mathrm{lost}(p, q, r). A shorter tree uses that exactly one of pp and ¬p\lnot p is true, so lost(p,¬p,m)\mathrm{lost}(p, \lnot p, m) is true exactly when mm is false: maj(p,q,r)=lost(p,lost(p,p,p),lost(p,q,r))\mathrm{maj}(p, q, r) = \mathrm{lost}(p, \mathrm{lost}(p, p, p), \mathrm{lost}(p, q, r)).

2.

4.2 Prove by structural induction that every formula built from atoms with the quorum monitor's operator lost\mathrm{lost} alone is self-dual. (3 points)

3 points: base case: an atom p is self-dual, since v′(p) = ¬v(p) by the definition of v′ (1) · the operator itself: lost(¬x, ¬y, ¬z) = ¬lost(x, y, z), because at most one of ¬x, ¬y, ¬z is true exactly when at least two of x, y, z are true; checking the four pairs of opposite rows of the table also shows it (1) · induction step: for φ = lost(φ₁, φ₂, φ₃) with self-dual φ₁, φ₂, φ₃, v′(φ) = lost(¬v(φ₁), ¬v(φ₂), ¬v(φ₃)) = ¬lost(v(φ₁), v(φ₂), v(φ₃)) = ¬v(φ); an induction on the number of lost occurrences counts the same (1)

Model answer: By induction on the formula. Base: for an atom, v′(p)=¬v(p)v'(p) = \lnot v(p) is how v′v' is defined. The operator: at most one of ¬x,¬y,¬z\lnot x, \lnot y, \lnot z is true exactly when at most one of x,y,zx, y, z is false, that is when at least two of them are true; so lost(¬x,¬y,¬z)=¬lost(x,y,z)\mathrm{lost}(\lnot x, \lnot y, \lnot z) = \lnot\mathrm{lost}(x, y, z). Step: let φ=lost(φ1,φ2,φ3)\varphi = \mathrm{lost}(\varphi_1, \varphi_2, \varphi_3), where each φk\varphi_k is self-dual by the induction hypothesis. Then
v′(φ)=lost(v′(φ1),v′(φ2),v′(φ3))=lost(¬v(φ1),¬v(φ2),¬v(φ3))=¬v(φ).v'(\varphi) = \mathrm{lost}(v'(\varphi_1), v'(\varphi_2), v'(\varphi_3)) = \mathrm{lost}(\lnot v(\varphi_1), \lnot v(\varphi_2), \lnot v(\varphi_3)) = \lnot v(\varphi).
So no rule of the monitor can express a function that isn't self-dual, such as ⊤\top, ⊥\bot or p∧qp \land q: {lost}\{\mathrm{lost}\} is not functionally complete.

3.

4.3 Which of the functions gg and hh given by their truth tables can the quorum monitor express with lost\mathrm{lost} alone? Give a formula for one and a reason for the other. (2 points)

2 points: g can: it is true when at least two of p, q, ¬r are true, that is when at most one of ¬p, ¬q, r is true, so g = lost(lost(p, p, p), lost(q, q, q), r); maj(p, q, ¬r) built from 4.1's formulas, or any other correct formula with lost alone, counts (1) · h can't: it is true in both TTT and FFF, two opposite rows, so it is not self-dual, while every formula with lost alone is (1)

Model answer: gg: its true rows are those in which at least two of pp, qq, ¬r\lnot r hold, so g=maj(p,q,¬r)g = \mathrm{maj}(p, q, \lnot r). At least two of these three are true exactly when at most one of their negations ¬p\lnot p, ¬q\lnot q, rr is, which gives g=lost(lost(p,p,p),lost(q,q,q),r)g = \mathrm{lost}(\mathrm{lost}(p, p, p), \mathrm{lost}(q, q, q), r). hh: it agrees with gg except in row FFF, where it is true. Then hh is true in TTT and in its opposite FFF, so negating all atoms doesn't negate its value: hh is not self-dual and no formula built with lost\mathrm{lost} alone has its truth table.

4.

4.4 Show that the quorum monitor's operator lost\mathrm{lost} together with the constant ⊥\bot, an input wired to false, is functionally complete, and say which of Post's five classes lost\mathrm{lost} alone lies in. (2 points)

2 points: lost(p, q, ⊥) is true unless p and q are both true, so it is p ↑ q, and NAND alone is functionally complete; with ⊤ instead, lost(p, q, ⊤) is p ↓ q, complete as well (1) · lost lies only in the class of self-dual functions: lost(T, T, T) is F and lost(F, F, F) is T, so it preserves neither value; FFF ≤ TTF but lost goes from T to F, so it is not monotone; and whether x changes the value depends on y and z, so it is not affine; ⊥ is not self-dual, so lost with ⊥ leaves all five classes (1)

Model answer: With one input false, lost(p,q,⊥)\mathrm{lost}(p, q, \bot) is true exactly when at most one of pp, qq is true: it is p↑qp \uparrow q, and NAND alone can express every Boolean function. By Post's criterion: lost\mathrm{lost} maps TTT to F and FFF to T, so it is neither truth-preserving nor falsity-preserving; it drops from T to F between FFF and TTF, so it isn't monotone; and changing its first input changes the value in row FTF but not in row FFF, so it isn't affine. It lies in the self-dual class only, and ⊥\bot, which isn't self-dual, takes the pair out of that one too.

Front

Exercise 5: An incident runbook in natural deduction

The atoms of an incident runbook: ff, the incident is handled by automatic failover; mm, it is handled by a manual switch; rr, the service is restarted; ll, a log entry is written; nn, the on-call engineer is notified; aa, a request is authenticated; bb, it is billed; cc, it raises an audit alert; dd, it is escalated to the security team. A colleague's proof:

1  f ∨ m     premise
2  f → r     premise
3  ¬m → r    premise
4  | f       assumption
5  | r       →E 2, 4
6  | ¬m      assumption
7  | r       →E 3, 6
8  r         ∨E 1, 4–5, 6–7
1.

5.1 Give a Fitch proof of r∧(l∨n)r \land (l \lor n) from the runbook premises f∨mf \lor m, f→r∧lf \to r \land l and m→r∧nm \to r \land n. (4 points)

2.

5.2 Give a Fitch proof of bb, "the request was billed", from the runbook premises a→b∨ca \to b \lor c, c→dc \to d, ¬a→d\lnot a \to d and ¬d\lnot d. (3 points)

3.

5.3 Find the line of the colleague's runbook proof of rr from f∨mf \lor m, f→rf \to r and ¬m→r\lnot m \to r that breaks a rule, and show by a valuation that no correct proof of rr from these premises exists. (3 points)

Back

1.

5.1 Give a Fitch proof of r∧(l∨n)r \land (l \lor n) from the runbook premises f∨mf \lor m, f→r∧lf \to r \land l and m→r∧nm \to r \land n. (4 points)

4 points: ∨E on f ∨ m with two subproofs, one assuming f and one assuming m, which end in the same formula (1) · in the f-branch →E and ∧E give r and l, and ∨I gives l ∨ n; in the m-branch r and n, and ∨I gives l ∨ n from n (1) · each branch ends with r ∧ (l ∨ n) by ∧I; running ∨E twice, once for r and once for l ∨ n, and joining the results by ∧I is just as good (1) · the ∨E line cites line 1 and both whole subproofs, and no line outside a subproof cites a line inside it; any correct proof in the deck's system counts (1)

Model answer:

 1  f ∨ m             premise
 2  f → r ∧ l         premise
 3  m → r ∧ n         premise
 4  | f               assumption
 5  | r ∧ l           →E 2, 4
 6  | r               ∧E 5
 7  | l               ∧E 5
 8  | l ∨ n           ∨I 7
 9  | r ∧ (l ∨ n)     ∧I 6, 8
10  | m               assumption
11  | r ∧ n           →E 3, 10
12  | r               ∧E 11
13  | n               ∧E 11
14  | l ∨ n           ∨I 13
15  | r ∧ (l ∨ n)     ∧I 12, 14
16  r ∧ (l ∨ n)       ∨E 1, 4–9, 10–15

Both cases restart the service, and each leaves a trace of its own, so the trace can only be stated as a disjunction. The stronger r∧l∧nr \land l \land n does not follow.

2.

5.2 Give a Fitch proof of bb, "the request was billed", from the runbook premises a→b∨ca \to b \lor c, c→dc \to d, ¬a→d\lnot a \to d and ¬d\lnot d. (3 points)

3 points: IP: assume ¬b and aim for ⊥; LEM on a, with b as the goal of both cases, is just as good (1) · the case a: →E gives b ∨ c, DS with ¬b gives c, and c → d gives d against ¬d, so ¬a by ¬I; in the LEM version, DS with ¬c, from MT on c → d and ¬d, gives b (1) · the case ¬a: ¬a → d gives d against ¬d, and IP closes with b, or X gives b and LEM closes; any correct proof in the deck's system counts, and one that uses none of IP, DNE, LEM and the De Morgan rule from ¬(φ ∧ ψ) to ¬φ ∨ ¬ψ contains a mistake; the direct proof, ¬c and ¬¬a by MT, a by DNE, b ∨ c by →E and b by DS, earns all 3 points (1)

Model answer:

 1  a → b ∨ c        premise
 2  c → d            premise
 3  ¬a → d           premise
 4  ¬d               premise
 5  | ¬b             assumption
 6  | | a           assumption
 7  | | b ∨ c       →E 1, 6
 8  | | c           DS 7, 5
 9  | | d           →E 2, 8
10  | | ⊥           ¬E 4, 9
11  | ¬a            ¬I 6–10
12  | d             →E 3, 11
13  | ⊥             ¬E 4, 12
14  b               IP 5–13

The goal bb is an atom that no premise gives directly, so the proof assumes ¬b\lnot b and aims at ⊥\bot. Inside, an authenticated request would raise an alert, by line 1 and DS, and so be escalated, which line 4 denies; hence ¬a\lnot a, and then line 3 escalates the request after all. In runbook terms: the request was not escalated, so it was authenticated and raised no alert, and such a request is billed. Without IP the subproof 5–13 would only give ¬¬b\lnot\lnot b.

3.

5.3 Find the line of the colleague's runbook proof of rr from f∨mf \lor m, f→rf \to r and ¬m→r\lnot m \to r that breaks a rule, and show by a valuation that no correct proof of rr from these premises exists. (3 points)

3 points: line 8: ∨E on f ∨ m needs a subproof for each disjunct, one assuming f and one assuming m, but the second assumes ¬m (1) · f false, m true and r false make f ∨ m, f → r and ¬m → r true and r false (1) · so r doesn't follow, and by soundness no correct proof of it exists; that with ¬f → r in place of ¬m → r it would follow, by LEM on f, needn't be said (1)

Model answer: Line 8. ∨E\lor\mathrm{E} on f∨mf \lor m needs two subproofs, assuming ff and assuming mm, and the second subproof assumes ¬m\lnot m instead. Lines 1 to 7 are all correct. No proof exists: take ff false, mm true, rr false. Then f∨mf \lor m is true through mm, f→rf \to r through ff false, and ¬m→r\lnot m \to r because ¬m\lnot m is false, but rr is false. The premises don't entail rr, and by soundness nothing proves what isn't entailed. The manual switch is exactly the case the premises leave open.

Front

Exercise 6: A package installer

An installer turns package requirements into Horn clauses over the atoms dd (the dashboard), cc (the command-line tool), hh (an HTTP library), tt (a TLS layer), jj (a JSON library), oo (OpenSSL), kk (a keyring) and gg (GnuTLS). The user requests dd and cc:

1 {d}       2 {c}          3 {¬d, h}     4 {¬h, t}     5 {¬c, j}
6 {¬t, o}   7 {¬c, ¬t, k}  8 {¬k, g}     9 {¬o, ¬g}

Clause 7 says that the command-line tool with TLS needs the keyring, and clause 9 that OpenSSL and GnuTLS conflict. The marking algorithm makes the facts true, fires each rule whose body has become true until nothing changes, and then tests the goal clauses.

The installer also places services in regions, with the atoms ee (the east region is used), ww (the west region is used), ss (spot instances are used) and qq (queue workers are used):

1 {e, w}    2 {¬e, ¬s}    3 {¬w, ¬s}
4 {q, s}    5 {¬e, ¬q, w}  6 {¬q, ¬w, s}

At least one region; neither region offers spot instances; batch jobs run on queue workers or spot instances; queue workers in the east need a standby in the west; queue workers in the west need spot instances.

1.

6.1 Run the marking algorithm on the installer's Horn clauses 1 to 9: the atoms in the order they are marked, the verdict, and the clauses that take part in it. (3 points)

2.

6.2 Run the marking algorithm on the installer's Horn clauses again without the request cc, clause 2: the least model, and whether the keyring kk follows. (2 points)

3.

6.3 Why can't the marking algorithm decide the installer's region clauses 1 to 6, and which of them are Horn? (1 point)

4.

6.4 Refute the installer's region clauses 1 to 6 by resolution. (3 points)

Back

1.

6.1 Run the marking algorithm on the installer's Horn clauses 1 to 9: the atoms in the order they are marked, the verdict, and the clauses that take part in it. (3 points)

3 points: the facts d and c, then h by 3, t by 4, j by 5, o by 6, k by 7 and g by 8; any order counts in which each atom comes after the atoms of its rule's body, for example j right after c (1) · all eight atoms are marked, and the goal clause 9, {¬o, ¬g}, then has both atoms true, so the clauses are unsatisfiable: no installation meets the request (1) · the clauses that take part: 1, 3, 4 and 6 lead from d through h and t to o, 2 and 7 with t to k, 8 to g, and 9 forbids o with g; clause 5 plays no part, and dropping any other clause makes the set satisfiable (1)

Model answer: Starting from the facts dd and cc, the rules fire as their bodies become true: hh (clause 3), tt (4), jj (5), oo (6), kk (7, which needs both cc and tt) and gg (8). Then clause 9, the conflict between OpenSSL and GnuTLS, has both its atoms true: the set is unsatisfiable. In installer terms, the dashboard pulls in TLS and with it OpenSSL, the command-line tool together with TLS pulls in the keyring and with it GnuTLS, and the two can't be installed together. So clauses 1, 3, 4 and 6 lead from dd to oo, clauses 2 and 7 with tt to kk, clause 8 to gg, and clause 9 forbids oo with gg; dropping any of these eight makes the set satisfiable. The JSON library, clause 5, is marked but plays no part.

2.

6.2 Run the marking algorithm on the installer's Horn clauses again without the request cc, clause 2: the least model, and whether the keyring kk follows. (2 points)

2 points: marking gives d, h, t and o, and the goal clause 9 is not violated: the clauses are satisfiable, with the least model d, h, t, o true and c, j, k, g false (1) · k doesn't follow, since the least model is a model of the clauses with k false; o follows, as every model makes true all the atoms of the least model (1)

Model answer: From dd alone the rules give hh, tt and oo. Clause 7 needs cc and never fires, so kk and gg stay false, and clause 9 is not violated: satisfiable. The least model makes exactly dd, hh, tt, oo true. An atom follows from the clauses exactly when the least model makes it true, so kk does not follow, while oo does: the dashboard alone needs OpenSSL and no keyring.

3.

6.3 Why can't the marking algorithm decide the installer's region clauses 1 to 6, and which of them are Horn? (1 point)

1 point: clauses 1, {e, w}, and 4, {q, s}, have two positive literals and are not Horn; 2 and 3 are goal clauses and 5 and 6 rules; with no fact the algorithm marks nothing and would wrongly answer satisfiable, because a clause such as e ∨ w forces a choice, not a single atom

Model answer: The algorithm is correct only for Horn clauses, and {e,w}\{e, w\} and {q,s}\{q, s\} have two positive literals each. Clauses 2 and 3 are goals and 5 and 6 rules. On these clauses the algorithm finds no fact, marks nothing, sees no violated goal and answers "satisfiable". That is wrong: making every unmarked atom false breaks clause 1, and the six clauses have a resolution refutation.

4.

6.4 Refute the installer's region clauses 1 to 6 by resolution. (3 points)

3 points: a derivation of □ in which each new line resolves two earlier clauses on one atom, for example 7 {w, ¬s} from 1, 2 on e and 8 {¬s} from 3, 7 on w (1) · 9 {¬q, w} from 1, 5 on e, 10 {¬q, s} from 6, 9 on w and 11 {s} from 4, 10 on q (1) · 12 □ from 8, 11 on s; any other correct refutation counts, it needn't be a shortest one; resolving on two atoms at once is a mistake (1)

Model answer:

 7  {w, ¬s}    1, 2 on e
 8  {¬s}       3, 7 on w
 9  {¬q, w}    1, 5 on e
10  {¬q, s}    6, 9 on w
11  {s}        4, 10 on q
12  □          8, 11 on s

Lines 7 and 8 show that no spot instances can be used, whichever region is taken. Lines 9 to 11 show that queue workers would need them after all: in the east they need the west, and in the west they need spot instances. Then the batch jobs, clause 4, need spot instances too, and the plan is impossible. Six steps is the least any refutation of this set takes.

Licence: Personal use Report this deck

New Computer science decks by email

Hear when they arrive, or tell us which deck you need.

Comments

Loading comments…