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′
(φ)).
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.