Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

2 Answers 2

up vote 2 down vote accepted

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?

share|improve this answer
    
that is perfect, thank you very much! –  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

([(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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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