Is this a valid re-write rule? In my job (SQL developer) I frequently need to change search conditions (WHERE clauses, database constraints) from disjunctive normal form to conjunctive normal form (CNF). I confess I usually resort to truth tables in all but the simplest cases, so I need to learn to improve.
This seemingly simple case flummoxed me:
$$( P \land Q ) \lor ( R \land S ) \lor ( P \land S )$$
Again, I resorted to truth tables to resolve to CNF, then tried to work out how it 'should' be done applying re-write rules and came up with the following:
Re-write rule: distribution of conjunction over disjunction:
$$( S \land ( P \lor R ) ) \lor ( P \land Q )$$
Re-write rule: ??:
$$( P \lor R ) \land ( S \lor ( P \land Q ) )$$
Re-write rule: Distribution of disjunction over conjunction:
$$( P \lor R ) \land ( P \lor S ) \land ( Q \lor S )$$
As you can see, I don't know what the second rule would be called, is this indeed is a valid progression.
Is the above valid and if so what is the rule?
Alternatively, is there is a simpler approach using re-write rules?
 A: You want to distribute $\mathtt{OR}$'s ($\vee$) inwards over $\mathtt{AND}$'s ($\wedge$).  In general, you have
$$
\begin{eqnarray}
(a\wedge b)\vee(c \wedge d)\vee(e \wedge f) &\equiv& (a\vee c \vee e)\wedge(a\vee c \vee f)\wedge(a\vee d \vee e)\wedge(a\vee d \vee f) \\
&& \wedge (b\vee c \vee e)\wedge(b\vee c \vee f)\wedge(b\vee d \vee e)\wedge(b\vee d \vee f):
&&
\end{eqnarray}
$$
each term chooses one element from each of the conjunctions being $\mathtt{OR}$-ed together.  This simplifies when the conjunctions have terms in common (since $a\vee a\equiv a$), or when some terms are negations of other terms (since $a\vee\neg a\equiv\mathtt{true}$).  In your case, you have
$$
\begin{eqnarray}
(P\wedge Q) \vee (R\wedge S) \vee (P \wedge S) &\equiv& (P\vee R)\wedge(P\vee R \vee S)\wedge(P \vee S)\wedge (P\vee S) \\
&& \wedge (Q\vee R\vee P) \wedge(Q\vee R\vee S)\wedge(Q\vee S \vee P)\wedge(Q\vee S).
\end{eqnarray}
$$
At this point you can absorb some larger terms into smaller ones, since $a\wedge(a\vee b)\equiv a$; this gives
$$
\begin{eqnarray}
(P\wedge Q) \vee (R\wedge S) \vee (P \wedge S) &\equiv& (P\vee R)\wedge (P\vee S) \wedge(Q\vee S),
\end{eqnarray}
$$
as desired.
