Purpose
To improve your understanding of propositional and first-order predicate logic, including their use in mechanized reasoning. To develop skills in analysis and formal reasoning about complex concepts, and to practise writing down formal arguments.
Five challenges
Challenge 1
On the Island of Knights and Knaves, everyone is a knight or knave. Knights always tell the truth. Knaves always lie. You meet three people, let us call them A, B and C. A says to you: "If I am a knight then my two friends here are knaves." Use propositional logic to determine whether this statement gives you any real information. What, if anything, can be deduced about A, B, and C?
Challenge 2
Let ? and ψ be these propositional formulas:
- ? : ((P ⇒ S) ∧ (Q ⇒ R) ∧ (R ⇒ P )) ⇒ S.
- ψ : (((P ∨ Q) ⇒ S) ∧ (¬P ⇒ (R ⇒ Q)) ∧ (R ∨ S)) ⇒ S.
1. Negate ? and transform the resulting formula to CNF.
2. Either use resolution on the resulting set of clauses and prove that ? is valid by deriving ⊥, or show that ? is in fact non-valid.
3. Negate ψ and transform the resulting formula to CNF.
4. Either use resolution on the resulting set of clauses and prove that ψ is valid by deriving ⊥, or show that ψ is in fact non-valid.
Challenge 3
Show that the closed formula
[∀x∀y(P (x, y) ⇒ P (h(x), h(h(y))))] ⇒ ∀x(P (x, h(x)) ∧ P (h(h(x)), x)) is non-valid but satisfiable.
Challenge 4
For this question use the following predicates:
- S(x), which stands for "x is a surgeon"
- P (x, y), which stands for "x is a patient of y"
- R(x), which stands for "x recovers"
- H(x), which stands for "x is happy"
1. Express, as a formula in first-order predicate logic (not clausal form), this statement S1: "A surgeon with no patients is happy." (Be careful to get this right; most of the following depends on this.)
2. Express, as a formula in first-order predicate logic (not clausal form), this statement
S2: "A surgeon is happy if all her patients recover." (Be even more careful here.)
3. Translate S2 to clausal form (remaining careful).
4. Translate the negation of S1 to clausal form (still taking care.)
5. Give a proof by resolution to show that S1 follows from S2.
Challenge 5
Consider a single-digit display able to show the eight digits 0-7. The display has seven LEDs (labelled a-g), as shown on the right. For example, to display the digit 3, all segments except b and e should light a up. Each of the seven segments a-g can be considered a propositional function of three propositional variables X, Y and Z, with input XYZ b c specifying the desired digit in binary notation. For example, for input XYZ = 011 (that is, X being false and Y and Z being true) the outputs e f b and e should be 0 (False) while the rest should be 1 (True). In fact, the truth tables for all the functions a-g are as follows:
|
X
|
Y
|
Z
|
a
|
b
|
c
|
d
|
e
|
f
|
g
|
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
|
0
|
0
|
1
|
0
|
0
|
1
|
0
|
0
|
1
|
0
|
|
0
|
1
|
0
|
1
|
0
|
1
|
1
|
1
|
0
|
1
|
|
0
|
1
|
1
|
1
|
0
|
1
|
1
|
0
|
1
|
1
|
|
1
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
1
|
0
|
|
1
|
0
|
1
|
1
|
1
|
0
|
1
|
0
|
1
|
1
|
|
1
|
1
|
0
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
|
1
|
1
|
1
|
1
|
0
|
1
|
0
|
0
|
1
|
0
|
The single-digit display must be implemented with logic circuitry. Here we assume that only three types of logic gates are available. An and-gate takes two inputs and produces, as output, the conjunction (∧) of the inputs. Similarly, an or-gate implements disjunction (∨).
Finally, an inverter takes a single input and negates it.
The task here is to design a circuit for all of a-g using as few gates as possible. We can specify the circuit by writing down the Boolean equations for each of the outputs a-g. For example, we can define f = X ∨ ¬Y ∨ Z, which shows that f can be implemented with three gates. Since we want to use as few gates as possible, it is important to look for cases where outputs can be shared, or reused. For example, if we already have implemented b then we could define f = b ∨ Z, using just one gate. Note that any sub-circuit that you want to share (that is, you want to direct its output to different places), the output must have a name. You can define as many "helper" functions as you please, to create the smallest possible solution.
The answer to this question must be submitted separately on Grok (details below). You are to submit a text file consisting of one line per definition (so not Haskell code; this is not a Haskell programming exercise). This file will be tested automatically, so it is important that you follow the notational conventions exactly. We write ¬ as - and ∨ as +. We write ∧ as ., or, simpler, we just leave it out, so that concatenation of expressions denotes their conjunction. Here is an example set of equations (for a different problem):
# An example of a set of equations in the correct format:
a = -Y Z + Y -Z + X -Y -Z b = u + X (Y + Z)
c = X + -(Y Z)
d = u + X a u = -X -Y
# u is an auxiliary function introduced to simplify b and d
Empty lines, and lines that start with ‘#', are ignored. Input variables are in upper case. Negation binds tighter than conjunction, which in turn binds tighter than disjunction.
So the equation for a says that a = (¬Y ∧ Z) ∨ (Y ∧ ¬Z) ∨ (X ∧ ¬Y ∧ ¬Z). Note the use of a helper function u, allowing b and d to share some circuitry. Also note that we do not allow any feedback loops in the circuit. In the example above, d depends on a, so a is not allowed to depend, directly or indirectly, on d (and indeed it does not).