Homework Sheet 1
Exercise � (� points) Let A, B, C be propositional variables. Determine (with proof) whether there
exists a formula φ such that the formula A → φ is equivalent to
(a) φ → A;
(b) φ → B;
(c) B → φ.
In a second step, determine whether we can choose the formula φ such that it depends on the
variable C (i.e., there exist two variable assignments v, v′
that agree on all variables different from C
and such that v(φ) ≠ v′
(φ)).
Solution
(a) We can obviously choose φ = A. In fact, this is the only possibility (up to logical equivalence).
If v is a variable assignment with v(A) = , we have
v(A → φ) =  and v(φ → A) =  − v(φ) .
Hence, if A → φ ≈ φ → A, we must have v(φ) = .
Similarly, if v is a variable assignment with v(A) = , we have
v(φ → A) =  and v(A → φ) = v(φ) .
Hence, A → φ ≈ φ → A implies v(φ) = .
It follows that φ ≈ A. In particular, it cannot depend on C.
(b) Such a formula does not exist. Let v be the variable assignment with v(A) =  and v(X) =  for
all other variables. Then
v(A → φ) = v(φ) ≠  − v(φ) = v(φ → B) .
A contradiction.
(c) Any tautology works. Another solution is the formula φ = A∨ B ∨C, which does depend on C.
To show that this formula is indeed a solution, we can use a truth table, or we can argue as follows.
The formula A → (A ∨ B ∨ C) is true if v(A) =  and if v(A) = . Similarly, B → (A ∨ B ∨ C) is true
if v(B) =  and if v(B) = . Hence, both formulae are tautologies.
Exercise � (� points) Let N = {, , , . . . } be the set of natural numbers. Suppose that we have a
propositional variable An, for every n ∈ N. We call a variable assignment v an n-assignment if
v(Ak) =  , for all k ≥ n .
(There therefore exist exactly n
n-assignments.) We call a formula φ an n-formula if it only contains
implications → and (some of) the variables A, . . . , An−.
(a) (� point) Find a -formula that is true for exactly  -assignments.
(b) (� points) Prove (preferably by induction) that there is no -formula that is true for exactly 
-assignment.
(c)* (� point) Find a -formula that is true for exactly  -assignments.
(d)* (� points) Determine (with proof) for which numbers n, k ∈ N there exists an n-formula that is
true for exactly k n-assignments.
Solution
(a) for example, A → (A → A)
(b) See the first part of (d) below.
(c) (A → ((((A → A) → A) → A) → A)) → A
(d) There is obviously no -formula. Hence, suppose that n ∈ N+
. First, we prove that every nformula
φ is true for at least n−
n-assignments. We proceed by induction on φ.
If φ = Ak, every n-assignment v with v(Ak) =  satisfies φ. There are n−
such assignments.
Next, suppose that φ = ψ → ξ. Then φ is true for every assignment satisfying ξ. By inductive
hypothesis, there are at least n−
of these.
Since −
= ,itfollows inparticularthat thereisno -formula thatis true forexactly  -assignment.
Next we show by induction on n that, for every n−
≤ k ≤ n
, there is some n-formula that is true
for exactly k n-assignments.
For n =  and k = , we can take φ = A. For n =  and k = , we can take φ = A → A.
Suppose that n ≥ . We distinguish two cases. If k <  ⋅ n−
, we use the inductive hypothesis
to find an (n − )-formula φ that is true for n
− k (n − )-assignments. We consider the formula
ψ = φ → An−. This formula is false if, and only if, φ is true and An− is false. There are n
− k such
assignments. Consequently, there are n
− (n
− k) = k n-assignments that make ψ true.
Similarly, if k ≥  ⋅ n−
, we take an (n − )-formula φ that is true for exactly k − n−
(n − )assignments.
We consider the formula ψ = An− → φ. This formula is false if, and only if, An− is
true and φ is false. There are n−
− (k − n−
) = n
− k such assignments. Consequently, there are
n
− (n
− k) = k n-assignments that make ψ true.
It follows that there exists an n-formula that is true for at least k n-assignments if,and only if, n > 
and n−
≤ k ≤ n
.