
Logic for Computer Science
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 , , , … 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 ("not"), conjunction ("and"), disjunction ("or"), conditional ("if … then") and biconditional ("if and only if"); and are constants for true and false.
core · Books also write for , for , for and for ; programs write !, &&, ||.
Front
is true exactly when is ; is true exactly when both parts are true; is false exactly when both parts are false.
Back
is true exactly when is false; is true exactly when both parts are true; 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 ("for all") and the existential ("there is", meaning at least one). An atom is no longer an unanalysed letter but a statement about objects, such as .
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 , , , and the valuation with and true and false refutes . What links them lies inside the sentences: "merged", "reviewed" and "commit 41" each occur twice.
core · With predicates: and entail .
Front
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. 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: and bind variables that stand for individuals. Quantifying over predicates, sets or functions, as in "every property of ", 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
" and have the same permissions" written as : why it is not a first-order formula
Back
The quantifier 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: .
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 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:
- : the change's test suite passes;
- : its security scan passes;
- : the change is a hotfix;
- : a second engineer has approved it;
- : 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 .
1.1 Formalise the release-gate requirements R1, R2 and R3 with the atoms , , , and . (3 points)
1.2 What does the colleague's formula 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)
1.3 For which of the 16 combinations of , , and do the release-gate requirements R1, R2 and R3 force the release, forbid it, or leave it open? (3 points)
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 Formalise the release-gate requirements R1, R2 and R3 with the atoms , , , and . (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 : "only if" marks the necessary condition, which goes on the right. R2 is , equivalently : for a change that is not a hotfix, a release needs both checks. R3 is ; 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.
1.2 What does the colleague's formula 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: . The two come apart in two ways, both with false. With true and false, an unapproved non-hotfix is released: R4 is broken, while the colleague's formula holds, since its antecedent fails. With true and false, an unapproved hotfix is held back: R4 holds, the colleague's formula fails. The values of and don't matter, so each case covers four valuations.
1.3 For which of the 16 combinations of , , and 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 , , , , try both values of .
- Forced: and true. R3 needs true, R1 is satisfied by , and R2 says nothing about hotfixes. 4 combinations, as and are free.
- Forbidden: false, where R1 rules out : 8 combinations. And true, false and not both and , where R2 rules it out: 3 more. 11 in all.
- Open: false with , , true. Every requirement holds with true and with false, so the policy leaves the decision to someone else.
No combination is left without a value of that meets all three requirements: .
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 , a valuation needs true, false and false. Then R2, , 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: true, false, false satisfies R1 (no release), R2 (a hotfix) and R3 (the tests fail), whatever and are, and it falsifies .
Front
Exercise 2: Refactoring a write guard
A file service guards writes with the condition !(locked && !admin) && (admin || owner). With for locked, for admin and for owner, the guard is
Two refactorings are proposed: , from admin || (owner && !locked), and , from (admin || owner) && !locked.
2.1 Show by a chain of named equivalence laws that the write guard is equivalent to its refactoring . (3 points)
2.2 On which valuations do the write guard and the refactoring differ, and which of the two entails the other? (2 points)
2.3 Write the refactored write guard with as its only connective. (2 points)
2.4 The write guard 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
2.1 Show by a chain of named equivalence laws that the write guard is equivalent to its refactoring . (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 out of two clauses, the distributive law of over read backwards. By the replacement theorem each step may rewrite a part of the formula. The first two steps can also go through .
2.2 On which valuations do the write guard and the refactoring 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: is equivalent to , so it is true for every admin and for an owner of an unlocked file. demands an unlocked file from everyone. They differ exactly when and are true, with true or false: there is true and false. In every other valuation they agree, so , and . The refactoring is stricter: it locks admins out of locked files.
2.3 Write the refactored write guard with 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: . By the conditional law it is , and by the negated conditional , so it is , which is . 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 , , , and one arrow can't mention three atoms.
2.4 The write guard 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 and true and false makes true, as holds through and through , and true, yet is false: an admin who doesn't own the file may write to it although it is locked. The second follows. With false, reduces to and to , so every valuation that makes and true makes true.
Front
Exercise 3: A dark-launch rule
A feature-flag service checks the dark-launch rule : for a request from a beta user () or from an internal tester (), the experiment flag () is on exactly when the user is a beta user. Its monitor looks for the requests that violate the rule, those that satisfy . Truth tables list the atoms in the order , , . 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.
3.1 Bring the dark-launch violation into negation normal form, naming the law used at each step. (2 points)
3.2 Convert the dark-launch rule itself to CNF by laws, and simplify it to as few clauses as you can. (2 points)
3.3 Read the canonical DNF of the dark-launch violation off its truth table, and shorten it. (2 points)
3.4 Give the Tseitin encoding of the dark-launch violation : the definitions, the number of clauses and of models, and how the encoding settles whether the rule itself is valid. (3 points)
Back
3.1 Bring the dark-launch violation 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 and are left. A violation is a request from a beta user or a tester in which beta and experiment disagree.
3.2 Convert the dark-launch rule 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: is false in three of the eight rows, and a clause over , and is false in one, two or four.
3.3 Read the canonical DNF of the dark-launch violation 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 . The first two merge by distributivity, excluded middle and identity into , so . One term can't do: TFF and FTT differ in every atom.
3.4 Give the Tseitin encoding of the dark-launch violation : the definitions, the number of clauses and of models, and how the encoding settles whether the rule 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 to the value of its subformula, so every model of extends in exactly one way and the encoding has 3 models; for TFF they are true, false, false. To decide whether is valid, ask whether is satisfiable: this encoding is, so is not valid, and each model the solver returns is a violating request. The encoding of shares the ten definition clauses and ends with ; 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 . A formula is self-dual if negating all its atoms negates its value: whenever the valuation gives every atom the opposite value of . The majority function is true when at least two of its inputs are. Two functions and of , , , and 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
4.1 Express and the majority function with the quorum monitor's operator alone. (2 points)
4.2 Prove by structural induction that every formula built from atoms with the quorum monitor's operator alone is self-dual. (3 points)
4.3 Which of the functions and given by their truth tables can the quorum monitor express with alone? Give a formula for one and a reason for the other. (2 points)
4.4 Show that the quorum monitor's operator together with the constant , an input wired to false, is functionally complete, and say which of Post's five classes alone lies in. (2 points)
Back
4.1 Express and the majority function with the quorum monitor's operator 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: : if is true, all three inputs are; if it is false, none is. With that negation, for . A shorter tree uses that exactly one of and is true, so is true exactly when is false: .
4.2 Prove by structural induction that every formula built from atoms with the quorum monitor's operator 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, is how is defined. The operator: at most one of is true exactly when at most one of is false, that is when at least two of them are true; so . Step: let , where each is self-dual by the induction hypothesis. Then
So no rule of the monitor can express a function that isn't self-dual, such as , or : is not functionally complete.
4.3 Which of the functions and given by their truth tables can the quorum monitor express with 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: : its true rows are those in which at least two of , , hold, so . At least two of these three are true exactly when at most one of their negations , , is, which gives . : it agrees with except in row FFF, where it is true. Then is true in TTT and in its opposite FFF, so negating all atoms doesn't negate its value: is not self-dual and no formula built with alone has its truth table.
4.4 Show that the quorum monitor's operator together with the constant , an input wired to false, is functionally complete, and say which of Post's five classes 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, is true exactly when at most one of , is true: it is , and NAND alone can express every Boolean function. By Post's criterion: 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 , 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: , the incident is handled by automatic failover; , it is handled by a manual switch; , the service is restarted; , a log entry is written; , the on-call engineer is notified; , a request is authenticated; , it is billed; , it raises an audit alert; , 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
5.1 Give a Fitch proof of from the runbook premises , and . (4 points)
5.2 Give a Fitch proof of , "the request was billed", from the runbook premises , , and . (3 points)
5.3 Find the line of the colleague's runbook proof of from , and that breaks a rule, and show by a valuation that no correct proof of from these premises exists. (3 points)
Back
5.1 Give a Fitch proof of from the runbook premises , and . (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 does not follow.
5.2 Give a Fitch proof of , "the request was billed", from the runbook premises , , and . (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 is an atom that no premise gives directly, so the proof assumes and aims at . Inside, an authenticated request would raise an alert, by line 1 and DS, and so be escalated, which line 4 denies; hence , 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 .
5.3 Find the line of the colleague's runbook proof of from , and that breaks a rule, and show by a valuation that no correct proof of 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. on needs two subproofs, assuming and assuming , and the second subproof assumes instead. Lines 1 to 7 are all correct. No proof exists: take false, true, false. Then is true through , through false, and because is false, but is false. The premises don't entail , 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 (the dashboard), (the command-line tool), (an HTTP library), (a TLS layer), (a JSON library), (OpenSSL), (a keyring) and (GnuTLS). The user requests and :
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 (the east region is used), (the west region is used), (spot instances are used) and (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.
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)
6.2 Run the marking algorithm on the installer's Horn clauses again without the request , clause 2: the least model, and whether the keyring follows. (2 points)
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)
6.4 Refute the installer's region clauses 1 to 6 by resolution. (3 points)
Back
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 and , the rules fire as their bodies become true: (clause 3), (4), (5), (6), (7, which needs both and ) and (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 to , clauses 2 and 7 with to , clause 8 to , and clause 9 forbids with ; dropping any of these eight makes the set satisfiable. The JSON library, clause 5, is marked but plays no part.
6.2 Run the marking algorithm on the installer's Horn clauses again without the request , clause 2: the least model, and whether the keyring 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 alone the rules give , and . Clause 7 needs and never fires, so and stay false, and clause 9 is not violated: satisfiable. The least model makes exactly , , , true. An atom follows from the clauses exactly when the least model makes it true, so does not follow, while does: the dashboard alone needs OpenSSL and no keyring.
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 and 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.
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…