Prove: (p ∧ q) ∨ (q ∧ r) ∨ (r ∧ p) ≡ (p ∨ q) ∧ (q ∨ r) ∧ (r ∨ p)

Question

I tried reversing absorption on the RHS to expand all terms then group the individual element but I end up getting the LHS and the RHS.I was thinking maybe I can expand the LHS reversing using the same method and show that each sides can be expanded to the same form. However I feel there is a better way to prove this using only the laws where one side becomes the other.Thoughts?

Answer 1

You know FOIL from basic arithmetic, right?

$(a+b)(c+d)=ac+ad+bc+bd$

Well, it turns out you can generalize it in several ways. For example, you can have more than two terms in the sums:

$(a+b)(c+d+e)=ac+ad+ae+bc+bd+be$

The basic principle is the same though: you combine each element from the first sum with each element from the second sum.

You can also have more than two sums, e.g:

$(a+b)(c+d)(e+f)=ace+acf+ade+adf+bce+bcf+bde+bdf$

Again, it's the same general idea though: you produce all combinations of terms, where each terms picks exactly one element from each sum.

Now, it turns out that the same kind of distributive principles hold for logic. Indeed, the last one is very much like what you have, and so you get:

$(p \land q) \lor (q \land r) \lor (r \land p) \equiv (p \lor q \lor r) \land (p \lor q \lor p) \land (p \lor r \lor r) \land (p \lor r \lor p) \land (q \lor q \lor r) \land (q \lor q \lor p) \land (q \lor r \lor r) \land (q \lor r \lor p)$

OK, but now we can simplify. First, by Idempotence, we can remove duplicates of the disjuncts:

$\equiv (p \lor q \lor r) \land (p \lor q) \land (p \lor r) \land (p \lor r) \land (q \lor r) \land (q \lor p) \land (q \lor r) \land (q \lor r \lor p)$

and also of the conjuncts:

$\equiv (p \lor q \lor r) \land (p \lor q) \land (p \lor r) \land (q \lor r) $

Finally, we can use Absorption, which states that $A \land (A \lor B) \equiv A$. Wih that, we can get rid of the $(p \lor q \lor r)$ term, leaving us with:

$\equiv (p \lor q) \land (p \lor r) \land (q \lor r) $

Answer 2

Using the law of distribution the RHS can be simplified.

I am using a notation I learned in my computer engineering classes.

Unions can be substituted for ORs and Intersects can be substituted for ANDs

The RHS reads

$$(P + Q)(Q + R)(R + P)$$

Simplifies:

$$ PQR + PQ + QR + RP $$

Factor out an expression from PQR:

$$ PQ ( 1 + R ) + QR + RP $$

1 + R evaluates to 1:

$$ PQ (1) + QR + RP $$

Finally,

$$ PQ + QR + RP $$