Trouble with boolean algebra as used in logic

Question

I'm having trouble knowing how to continue on with this problem, I don't know what to turn the equivalent sign into and I cant really continue with that side, can anyone help me out?

Do I just say that the left side is R, were P and Q are equiv to R? or is there a special way to handle this

$$\begin{align*} \Bigl[ (P\land Q)\equiv R\Bigr] &\to \Bigl[ (P\to R)\lor (Q\to R)\Bigr]\\ \Bigl[ (P\land Q)\equiv R\Bigr] &\to \Bigl[ \neg(P\land\neg R)\lor \neg(Q\land \neg R)\Bigr]\\ &\to \Bigl[ (\neg P\lor R)\lor (\neg Q\lor R)\Bigr]\\ &\to P' + R + Q' + R\\ &\to P' + R + Q' \end{align*}$$

Answer 1

You want to show that if $(P\land Q)$ is equivalent to $R$, then either $P$ implies $R$ or $Q$ implies $R$.

First, let us convert the left hand side into a boolean algebra statement.

$(P\land Q)\equiv R$ is the same as $$(P\land Q\land R) \lor (\neg(P\land Q)\land \neg R)$$ That is, $$ PQR + (PQ)'R' = PQR + (P'+Q')R' = PQR + P'R' + Q'R'.$$ What you want to show is that from this you can deduce $(P\to R)\lor (Q\to R)$, which is the same as $P'+R + Q'+R = P'+Q'+R$.

In other words, you want to show that $$\Bigl( PQR + P'R' + Q'R'\Bigr)' + (P'+R+Q') = 1.$$ (Since $A\to B$ is equivalent to $\neg A \lor B$, which is $A'+B$).

Now, $$(PQR + P'R' + Q'R')' = (P'+Q'+R')(P+R)(Q+R);$$ and $$(P+R)(Q+R) = PQ + PR + QR + R = PQ + (P+Q+1)R = PQ+R$$ so $$\begin{align*} (PQR + P'R' + Q'R')' &= (P'+Q'+R')(P+R)(Q+R)\\ &= (P'+Q'+R')(PQ+R)\\ &= P'PQ + P'R + Q'PQ + Q'R + PQR' + R'R\\ &= 0 + P'R + 0 + Q'R + PQR' + 0\\ &= (P'+Q')R + PQR'\\ &= (PQ)'R + (PQ)R'. \end{align*}$$ So what we want to show is that $$(PQ)'R + (PQ)R' + P' + Q' +R = 1$$ Notice that $(PQ)'R + R = ((PQ)'+1)R = R$. So $$(PQ)'R + (PQ)R' + P' + Q' + R = PQR' + P' + Q' + R.$$

Okay, I've done about five sixths of the problem for you now. Can you finish it off?

Answer 2

Since "implication" in Boolean Algebra means "the complement of the union" (or C==AN if you know Polish notation) you want to show

([(P∧Q)≡R]'V[(P→R)∨(Q→R)]) as an identity for any Boolean Algebra. Boolean Algebra has a very powerful metatheorem which states that if an identity holds for the two-element Boolean Algebra ({0, 1}, V, ∧, ') it will hold as an identity for any Boolean Algebra. So, if we can show that (([(P∧Q)≡R]'V[(P→R)∨(Q→R)])≡1) for {0, 1}, then we'll have shown ([(P∧Q)≡R]'V[(P→R)∨(Q→R)]) as a theorem for any Boolean Algebra.

Case 1: Suppose P=0. Then we have ([(0∧Q)≡R]'V[(0→R)∨(Q→R)]). Since ((0→R)≡1) [equivalently, (0'∨R)=1] we have that

([(0∧Q)≡R]'V[(0→R)∨(Q→R)])=([(0∧Q)≡R]'V[1∨(Q→R)])=([(0∧Q)≡R]'V1)=1

Case 2: Suppose P=1. Since (1∧Q)=Q, and (1→R)=R [equivalently, (1'∨R)=R] we have that

([(1∧Q)≡R]'V[(1→R)∨(Q→R)])=([Q≡R]'V[R∨(Q→R)])

Suppose Q=0 (case 2.1). We then have that

([0≡R]'V[R∨(0→R)])=([0≡R]'V[R∨1])=([0≡R]'V1)=1.

Suppose Q=1 (case 2.2). We then have that

([1≡R]'V[R∨(1→R)])=([1≡R]'V[R∨R])=([1≡R]'VR)

Since (1≡R)=R, we then obtain

([1≡R]'VR)=(R'VR)=1

Since P either equals 0, or 1 in the two-element Boolean Algebra {0, 1}, it follows that ([(P∧Q)≡R]'V[(P→R)∨(Q→R)]) equals 1 in the two-element Boolean Algebra. By the metatheorem mentioned above, it follows that ([(P∧Q)≡R]'V[(P→R)∨(Q→R)]) or equivalently ([(P∧Q)≡R]→[(P→R)∨(Q→R)]) holds for any Boolean Algebra.