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))
