The exam question was as follows: Given boolean variables a,b,c, and d, construct a propositional logic formula φ that holds if and only if at most two of them are true.

Hint: This means that the formula φ evaluates to true if zero, one, or two of the variables {a,b,c,d} are assigned true. The formula φ evaluates to false if three or four of them are assigned true.

There are four cases where three of the four variables are true, namely:

{ b,c,d}
{a, c,d}
{a,b, d}
{a,b,c }

and obviously one where all four variables are true. Hence, we have

¬φ =
¬a ∧ b ∧ c ∧ d ∨
a ∧ ¬b ∧ c ∧ d ∨
a ∧ b ∧ ¬c ∧ d ∨
a ∧ b ∧ c ∧ ¬d ∨
a ∧ b ∧ c ∧ d

which can be simplified to

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

and further to

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