Simplifying the boolean expression for leap year

Question

Suppose I have

p = year divisible by 4
q = year divisible by 100
r = year divisible by 400

and by constructing the truth table I get

 p | q | r | is_leap_year
---+---+---+--------------
 0 | * | * | 0
 1 | 0 | 0 | 1
 1 | 0 | 1 | 0
 1 | 1 | 0 | 0
 1 | 1 | 1 | 1

yield the following boolean expression

$$ \begin{align} & (\, p \land \neg q \land \neg r )\, \lor (\, p \land q \land r )\, \\ & \equiv p \land (\, (\, \neg q \land \neg r )\, \lor (\, q \land r )\, )\, & \text{(distributive law)} \\ & \equiv p \land (\, (\, (\, \neg q \land \neg r )\, \lor q )\, \land (\, (\, \neg q \land \neg r )\, \lor r )\, )\, & \text{(distributive law)} \\ & \equiv p \land (\, (\, q \lor (\, \neg q \land \neg r )\, )\, \land (\, r \lor (\, \neg q \land \neg r )\, )\, )\, & \text{(commutative law)} \\ & \equiv p \land (\, (\, (\, q \lor \neg q )\, \land (\, q \lor \neg r )\, )\, \land (\, (\, r \lor \neg q )\, \land (\, r \lor \neg r )\, )\, )\, & \text{(distributive law)} \\ & \equiv p \land (\, (\, \top \land (\, q \lor \neg r )\, )\, \land (\, (\, r \lor \neg q )\, \land \top )\, )\, & \text{(complemence law)} \\ & \equiv p \land (\, (\, q \lor \neg r )\, \land (\, r \lor \neg q )\, )\, & \text{(identity law)} \end{align} $$

it should be able to further simplified to simply

$$ r \lor \neg q \land p $$

however I couldn't proceed further from what I have now, am I missing something in between?

Your last expression $p \vee \neg q \wedge r$ should be wrong, because if $p = 0$, $q = 0$, $r = 1$, the expression is True (is_leap_year = 1). However, in your truth table, is_leap_year = 0. — Zhengqun Koo, Jul 27 '17 at 05:36
$r \to q$ so there are no cases where $r=1$ and $q=0$, these are impossible by definition. @KooZhengqun — Henno Brandsma, Jul 27 '17 at 05:46
@HennoBrandsma Ah yes that makes sense. So the third row in the truth table should be wrong as well. — Zhengqun Koo, Jul 27 '17 at 06:07

score 2 · Accepted Answer · 2017-07-27T06:16:10.567

The truth table is:

 p | q | r | is_leap_year
---+---+---+--------------
 0 | 0 | 0 | 0
 1 | 0 | 0 | 1
 1 | 1 | 0 | 0
 1 | 1 | 1 | 1

which gives us the expression $$(p \land \lnot q \land \lnot r) \lor (p \land q \land r) $$

There is a much easier way to simplify it.

We can reduce $p \land \lnot q \land \lnot r$ to $p \land \lnot q $ as $100 \nmid a \implies 400 \nmid a $.

Also, we can reduce $p \land q \land r$ to just $r$ as $400 \mid a \implies 100 \mid a \implies 4 \mid a$.

Therefore, the expression simplifies to:

\begin{align} & (\, p \land \neg q \land \lnot r)\, \lor (\, p \land q \land r )\, \\ & \equiv (\, p \land \neg q )\, \lor (\, p \land q \land r )\, \\ & \equiv (\ p \land \lnot q )\ \lor (\ r )\, \\ & \equiv p \land \lnot q \lor r \end{align}

Simplifying the boolean expression for leap year

1 Answers1