Example-Exam “Logic and Computability”

June 10, 2022

Name: Matriculation number:

Rules
• Questions/Tasks are in English. Your answers may be either in German or in English, as
you prefer.
• If terms are unknown to you, please ask the exam supervisor to translate them to German.
• You must work alone. Do not confer with your neighbors, or anybody else.

• You must not use any utilities, like pocket calculators, laptops, smart phones, etc.
• You must not use any documents, books, notes, scripts, etc.
• You must not use any red pen/pencil for your answers.

• Write clearly and legibly. Illegible parts will not be awarded any points.
• You must not use any of your own paper. Paper will be provided by the exam supervisor.
• Please read all tasks carefully. Also note that the exam is printed double-sided.
• If a task, or a part of a task, is not completely clear to you, please ask the exam supervisor
for clarification.
• Please try to give concise, but complete answers.
• For “practical tasks” (proving something, computing something, …), write down intermediate
steps to make your answer comprehensible.

• Write your name and matriculation number on the cover page. Please do not write your
name and matriculation number on any other page, as the exam will be reviewed blindly.
• All your answers must be written on the printed and numbered pages. Other paper is for
your notes/drafts only and will not be graded.

• You have to turn in all printed and numbered pages, even if you did not answer the questions
on particular pages. You may keep the scratch paper, though.
• Concerning multiple-choice questions, be advised that for each question zero, one, several,
or all answers might be correct. In general, points will only be awarded if exactly the correct
answers are ticked (no more, no less).

• If you erroneously tick a multiple-choice answer and wish to “untick” it, draw a circle around
the ticked box and write “No” next to it. Should you change your mind again, strike out the
“No” and write “Yes” instead. Repeat, if necessary. (Try to keep corrections to a minimum,
though.)
• Do not use a pencil for your final answers. Use a “permanent” pen.

• Failure to comply with any of these rules will result in appropriate consequences, e.g., a
negative grade.
Example-Exam “Logic and Computability” June 10, 2022

1. Model the following sentences as detailed as possible in propositional logic.

(a) If a formula is unsat, it cannot be valid.
(b) It can be proven that there exists an infinite number of primes.
(c) A sentence is called declarative, if and only if it can be assigned a truth value.

(a)

p . . . A formula is unsat
q . . . A formula is valid

p → ¬q
(b)

p . . . It can be proven that there exists an infinite number of primes

p
(c)

p . . . A sentence is called declarative

q . . . A sentence can be assigned a truth value

p↔ q

2. Consider the propositional formulas ϕ = (p ∨ q) → r, and ψ = r ∨ (¬p ∧ ¬q).

(a) Fill out the truth table for ϕ and ψ (and their subformulas).
p q r ¬p ¬q p ∨ q ¬p ∧ ¬q ϕ ψ
F F F T T F T T T
F F T T T F T T T
F T F T F T F F F
F T T T F T F T T
T F F F T T F F F
T F T F T T F T T
T T F F F T F F F
T T T F F T F T T

(b) Which of the formulas is satisfiable? Both

(c) Which of the formulas is valid? None
(d) Is ϕ equivalent to ψ? Yes
(e) Does ϕ semantically entail ψ? Yes
(f) Does ψ semantically entail ϕ? Yes

Page 1 of 9
Example-Exam “Logic and Computability” June 10, 2022

3. For the following sequent, either provide a natural deduction proof, or a counter-example
that proves the sequent invalid.
For proofs, clearly indicate which rule, and what assumptions and premises are used. Fur-
thermore, clearly indicate the scope of any boxes you use. For counterexamples, give a
complete model and clearly show which formulas are satisfied and which ones are not.

¬q ∨ p ` q → (p ∨ r)

1. ¬q ∨ p prem.
2. ¬q ass.
3. q ass.
4. ⊥ ¬e 2, 3
5. p ⊥e 4
6. p∨r ∨i 5
7. q → (p ∨ r) →i 3 − 6
8. p ass.
9. q ass.
10. p∨r ∨i 5
11. q → (p ∨ r) →i 3 − 6
12. q → (p ∨ r) ∨e 1, 2 − 7, 8 − 11

4. For the following sequent, either provide a natural deduction proof, or a counter-example
that proves the sequent invalid.
For proofs, clearly indicate which rule, and what assumptions and premises are used. Fur-
thermore, clearly indicate the scope of any boxes you use. For counterexamples, give a
complete model and clearly show which formulas are satisfied and which ones are not.

` (p → q) ∨ (q → r)

1. q ∨ ¬q LEM
2. q ass.
3. p ass.
4. q copy
5. p→q →i 3 − 4
6. (p → q) ∨ (q → r) ∨i 5
7. ¬q ass.
8. q ass.
9. ⊥ ¬e 7, 8
10. r ⊥e 9
11. q→r →i 8 − 10
12. (p → q) ∨ (q → r) ∨i 11
13. (p → q) ∨ (q → r) ∨e 1, 2 − 6, 7 − 12

Page 2 of 9
Example-Exam “Logic and Computability” June 10, 2022

5. Consider the propositional formula ϕ = (¬(¬a ∧ b) ∧ ¬c). Fill out the truth table for ϕ and
its subformulas. Compute a CNF as well as a DNF for ϕ from the truth table.
a b c ¬a ¬a ∧ b ¬(¬a ∧ b) ¬c ϕ = (¬(¬a ∧ b) ∧ ¬c)
F F F T F T T T
F F T T F T F F
F T F T T F T F
F T T T T F F F
T F F F F T T T
T F T F F T F F
T T F F F T T T
T T T F F T F F

CNF : (a ∨ b ∨ ¬c)∧
(a ∨ ¬b ∨ c)∧
DNF : (¬a ∧ ¬b ∧ ¬c)∨
(a ∨ ¬b ∨ ¬c)∧
(a ∧ ¬b ∧ ¬c)∨
(¬a ∨ b ∨ ¬c)∧
(a ∧ b ∧ ¬c)
(¬a ∨ ¬b ∨ ¬c)

6. Apply Tseitin’s encoding to the following formula: ϕ = (q ∧ ¬r) ∨ ¬(q ∧ ¬r). For each
variable you introduce, clearly indicate which subformula of ϕ it represents. Use the following
equivalences:

χ ↔ (ϕ ∨ ψ) ⇔ (¬ϕ ∨ χ) ∧ (¬ψ ∨ χ) ∧ (¬χ ∨ ϕ ∨ ψ)

χ ↔ (ϕ ∧ ψ) ⇔ (¬χ ∨ ϕ) ∧ (¬χ ∨ ψ) ∧ (¬ϕ ∨ ¬ψ ∨ χ)
χ ↔ ¬ϕ ⇔ (¬χ ∨ ¬ϕ) ∧ (ϕ ∨ χ)

(q ∧ ¬r) ∨ ¬ (q ∧ ¬r)
x1 x1
x2 x2
x3
xϕ

CN F (ϕ) = xϕ ∧
(¬x2 ∨ xϕ ) ∧ (¬x3 ∨ xϕ ) ∧ (¬xϕ ∨ x2 ∨ x3 )∧
(¬x3 ∨ ¬x2 ) ∧ (x3 ∨ x2 )∧
(¬x2 ∨ q) ∧ (¬x2 ∨ x1 ) ∧ (¬q ∨ ¬x1 ∨ x2 )∧
(¬x1 ∨ ¬r) ∧ (x1 ∨ r)

Page 3 of 9
Example-Exam “Logic and Computability” June 10, 2022

7. Consider the domain A = {Spain, F rance, Italy, Germany} and the two different symbolic
encodings for A given below. Which one gives a shorter symbolic representation for the set
B = {F rance, Italy}? Illustrate your answer by giving the representing formulas for B in
both encodings.

Encoding 1 Encoding 2
Element v1 v0 Element v1 v0
Spain 0 0 Spain 0 0
France 1 0 France 1 0
Italy 0 1 Italy 1 1
Germany 1 1 Germany 0 1
We give a symbolic representation for B using v1 and v0 and compare the lengths of the
formulas.

Encoding 1: b = (v1 ∧ ¬v0 ) ∨ (¬v1 ∧ v0 ) Encoding 2: b = v1

Comparing these two encodings shows that ’Encoding 2’ yields a shorter representation for
B.

8. Find a symbolic encoding for the set of initial states and the transition relation of the following
transition system and simplify your formulas. Use a binary encoding to encode the states,
e.g., encode the state s2 with the formula v1 ∧ ¬v0 .

s0 s1

s3 s2

S0 = ∅
R = ¬v1 ∧ ¬v0 ∧ (¬v10 ∧ ¬v00 ∨ v10 ∧ ¬v00 ) ∨
¬v1 ∧ v0 ∧ (¬v10 ∧ v00 ∨ v10 ∧ v00 ) ∨
v1 ∧ ¬v0 ∧ (v10 ∧ ¬v00 ∨ ¬v10 ∧ ¬v00 ) ∨
v1 ∧ v0 ∧ (v10 ∧ v00 ∨ ¬v10 ∧ v00 )

Page 4 of 9
Example-Exam “Logic and Computability” June 10, 2022

9. Given the Binary Decision Diagram (BDD) below. State the formula f that is represented
by the BDD.
Note: Else-edges are marked with circles. Filled circles represent the complemented attribute.
Dangling edges are assumed to point to the constant node true.

We state the formula as a DNF:

f = (a ∧ b ∧ c) ∨ (a ∧ ¬b ∧ ¬c ∧ d) ∨ (¬a ∧ ¬d)

10. Consider the following declarative sentence:

“For every natural number it holds that it is prime if and only if there is no smaller natural
number, except for 1, that divides it.”
Model this sentence with predicate logic, as detailed as possible. Clearly indicate the in-
tended meaning of all function, predicate, and constant symbols that you use.

A=N
P (n) . . . n is prime
D(m, n) . . . m divides n

∀n ((P (n) ↔ ¬∃m(m > 1) ∧ D(m, n)))

Page 5 of 9
Example-Exam “Logic and Computability” June 10, 2022

11. For the following sequent, either provide a natural deduction proof, or a counter-example
that proves the sequent invalid.
For proofs, clearly indicate which rule, and what assumptions and premises are used. Fur-
thermore, clearly indicate the scope of any boxes you use. For counterexamples, give a
complete model and clearly show which formulas are satisfied and which ones are not.

∀x(P (x) ∨ Q(x)), ∀x(P (x) → R(z)), ∀y(Q(y) → R(z)) ` R(z)

1. ∀x (P (x) ∨ Q(x)) prem.

2. ∀x (P (x) → R(z)) prem.
3. ∀x (Q(x) → R(z)) prem.
4. P (x0 ) ∨ Q(x0 ) ∀e 1
5. P (x0 ) → R(z) ∀e 2
6. Q(x0 ) → R(z) ∀e 3
7. P (x0 ) ass.
8. R(z) →e 5, 7
9. Q(x0 ) ass.
10. R(z) →e 6, 4
11. R(z) ∨e 4, 7 − 8, 9 − 10

12. For the following sequent, either provide a natural deduction proof, or a counter-example
that proves the sequent invalid.
For proofs, clearly indicate which rule, and what assumptions and premises are used. Fur-
thermore, clearly indicate the scope of any boxes you use. For counterexamples, give a
complete model and clearly show which formulas are satisfied and which ones are not.

∀x (Q(x) → R(x)), ∃x (P (x) ∧ Q(x)) ` ∃x (P (x) ∧ R(x))

1. ∀x (Q(x) → R(x)) prem.

2. ∃x (P (x) → Q(z)) prem.
3. x0 P (x0 ) ∧ Q(x0 ) ass.
4. P (x0 ) ∧e 3
5. Q(x0 ) ∧e 3
6. Q(x0 ) → R(x0 ) ∀e 1
7. R(x0 ) →e 5, 6
8. P (x0 ) ∧ R(x0 ) ∧i 4, 7
9. ∃x(P (x) ∧ R(x)) ∃i 8
10. ∃x(P (x) ∧ R(x)) ∃e 2, 3 − 9

Page 6 of 9
Example-Exam “Logic and Computability” June 10, 2022

13. Consider the following formula in TEU F .

ϕEU F := f (g(x), h(y)) = a ∨ b = f (u, v) → k(a, b) = u ∧ v = k(x, y)

Use Ackermann’s reduction to compute an equisatisfiable formula in TE .

f . . . fgh , fuv
g . . . gx
h . . . hy
k . . . kab , kxy

ϕF C = ((g = u ∧ h = v) → fgh = fuv ∧

((a = x ∧ b = y) → kab = kxy
ϕ̂ = fgh = a ∨ b = fuv → kab = u ∧ v = kxy
ϕE = ϕF C ∧ ϕ̂

14. In the following text fill the blanks with the missing word(s).
The Ackermann’s reduction is used to reduce a formula ϕin in the theory of equality and
uninterpreted functions to a formula in the theory of equality that is equisatisfiable. Two
formulas are equisatisfiable if either both of them are satisfiable or both are not satisfiable.
The algorithm adds explicit constraints
V to the formula ϕin to enforce functional consistency.
These constraints say, that ∀x̄∀ȳ ( i xi = yi ) →f (x̄) = f (ȳ) . The resulting equisatisfiable
formula consists of two parts and is of the form: ϕout := ϕC ∧ ϕˆin . The right part of the for-
mula ϕˆin describes the flattening original formula in which we replace function applications
with fresh variables.

Page 7 of 9
Example-Exam “Logic and Computability” June 10, 2022

15. Use the DPLL algorithm with conflict-driven clause learning to determine whether or not
the set of clauses given is satisfiable. Decide variables in alphabetical order starting with
the negative phase. For conflicts, draw conflict graphs after the end of the table, and add
the learned clause to the table.
If the set of clauses resulted in SAT, give a satisfying model. If the set of clauses resulted in
UNSAT, give a resolution proof that shows that the conjunction of the clauses from the table
is unsatisfiable.

Clause 1: {b, d}
Clause 2: {b, c}
Clause 3: {¬b, ¬e}
Clause 4: {¬a, ¬c}
Clause 5: {¬c, ¬d}
Clause 6: {¬b, c}
Clause 7: {a, b}
Clause 8: {¬b, d, e}

Step 1 2 3 4 5 6
Decision Level 0 1 1 1 1 1
Assignment - ¬a ¬a,b ¬a,b,c ¬a,b,c,¬d ¬a,b,c,¬d, ¬e
Cl. 1: b, d b, d b, d 3 3 3 3
Cl. 2: b, c b, c b, c 3 3 3 3
Cl. 3: ¬b, ¬e ¬b, ¬e ¬b, ¬e ¬e ¬e ¬e ¬e
Cl. 4: ¬a, ¬c ¬a, ¬c 3 3 3 3 3
Cl. 5: ¬c, ¬d ¬c, ¬d ¬c, ¬d ¬c, ¬d ¬d 3 3
Cl. 6: ¬b, c ¬b, c ¬b, c c 3 3 3
Cl. 7: a, b a, b b 3 3 3 3
Cl. 8: ¬b, d, e ¬b, d, e ¬b, d, e d, e d, e e {} 7
BCP - b c ¬d ¬e -
PL - - - - - -
Decision ¬a - - - - -

5 8
c ¬d e
6
7 8
¬a b ⊥

¬e

8. ¬b ∨ d ∨ e 3. ¬b ∨ ¬e
¬b ∨ d 5. ¬c ∨ ¬d
¬b ∨ ¬c 6. ¬b ∨ c
¬b 7. a ∨ b
a

Page 8 of 9
Example-Exam “Logic and Computability” June 10, 2022

Step 7(0) 8 9 10
Decision Level 0 0 0 0
Assignment - a a, ¬c a, ¬c, ¬b
Cl. 1: b, d b, d b, d b, d d
Cl. 2: b, c b, c b, c b {} 7
Cl. 3: ¬b, ¬e ¬b, ¬e ¬b, ¬e ¬b, ¬e 3
Cl. 4: ¬a, ¬c ¬a, ¬c ¬c 3 3
Cl. 5: ¬c, ¬d ¬c, ¬d ¬c, ¬d 3 3
Cl. 6: ¬b, c ¬b, c ¬b, c ¬b 3
Cl. 7: a, b a, b 3 3 3
Cl. 8: ¬b, d, e ¬b, d, e ¬b, d, e ¬b, d, e 3
Cl. LC: 9: a a 3 3 3
BCP a ¬c ¬b -
PL - - - -
Decision - - - UNSAT

b
2
9 4
a ¬c ⊥
6

¬b

2. b ∨ c 6. ¬b ∨ c
c 4. ¬a ∨ ¬c
¬a 9. a
⊥

Page 9 of 9