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*}$$

  • 1
    $\begingroup$ What exactly does the problem ask you to do? $\endgroup$ Oct 25 '11 at 19:51
  • $\begingroup$ @Brian M. Scott - Prove the following propositional logic statement using algebra. the statement is the top line here. $\endgroup$
    – Latency
    Oct 25 '11 at 20:12
  • $\begingroup$ "Hay is what cows eat". $\endgroup$ Oct 25 '11 at 20:17
  • $\begingroup$ @Arturo: "Thaw tea says how ca". $\endgroup$
    – Asaf Karagila
    Oct 25 '11 at 20:42

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?

  • $\begingroup$ that is perfect, thank you very much! $\endgroup$
    – Latency
    Oct 25 '11 at 22:20

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


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


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


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


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


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.