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?
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.