Prove that $(P \leftrightarrow Q) \wedge (R \leftrightarrow S) \implies (P \vee R) \leftrightarrow (Q \vee S).$

Question

Let $P, Q, R$ and $S$ be statements. Prove that

$$(P \leftrightarrow Q) \wedge (R \leftrightarrow S) \implies (P \vee R) \leftrightarrow (Q \vee S).$$

My attempt:

I already check that this logical implication is true, by showing that the conditional statement $(P \leftrightarrow Q) \wedge (R \leftrightarrow S) \to (P \vee R) \leftrightarrow (Q \vee S)$ is a tautology.

Although, I am trying to come up with a derivation of this implication. Here is what I have

$$(P \leftrightarrow Q) \wedge (R \leftrightarrow S) \implies (P \to Q) \wedge (Q \to P) \wedge (R \to S) \wedge (S \to R).$$

Using the Material Implication, I deduce that

$$(P \to Q) \wedge (Q \to P) \wedge (R \to S) \wedge (S \to R) \implies (\neg P \vee Q) \wedge (\neg Q \vee P) \wedge (\neg R \vee S) \wedge (\neg S \vee R).$$

I thought that maybe I could use the Distributive Law to continue to simplifying this expression. By doing this, I had to rotate my sheet, because the expression was really big.

I can continue this until I got something, but the expression is becoming extremely length.

Is there any hint of what I should do in order to prove this logical implication?

Or any simpler idea of what to do?

Thank you for your attention!

Answer 1

Let $P, Q, R$ and $S$ be statements, and consider the following statement

$$(P \leftrightarrow Q) \wedge (R \leftrightarrow S) \tag{1}$$

Using the rule of inference that states that for any statements $P$ and $Q$ $P \leftrightarrow Q \iff (P \to Q) \wedge (Q \to P),$ we get the following

$$(P \to Q) \wedge (Q \to P) \wedge (R \to S) \wedge (S \to R) \tag{2}$$

Applying the Material Implication to each conditional statement in $(2)$ yields the following expression

$$(\neg P \vee Q) \wedge (\neg Q \vee P) \wedge (\neg R \vee S) \wedge (\neg S \vee R) \tag{3}$$

Using the Rule of inference of Simplification, we get the following four disjunctions

$$\neg P \vee Q \tag{4}$$ $$\neg Q \vee P \tag{5}$$ $$\neg R \vee S \tag{6}$$ $$\neg S \vee R \tag{7}$$

Next, we apply the rule of Addition to each of the previous expressions. Namely, we will add $S$ to $(4),$ $R$ to $(5),$ $Q$ to $(6)$ and $P$ to $(7).$

$$\neg P \vee Q \vee S \tag{8}$$ $$\neg Q \vee P \vee R \tag{9}$$ $$\neg R \vee S \vee Q \tag{10}$$ $$\neg S \vee R \vee P \tag{11}$$

By Adjunction, we get the following expression

$$(\neg P \vee Q \vee S) \wedge (\neg Q \vee P \vee R) \wedge (\neg R \vee S \vee Q) \wedge (\neg S \vee R \vee P) \tag{12}$$

Using the Distributive Law yields that

$$\big( (\neg P \wedge \neg R) \vee (Q \vee S) \big) \wedge \big( (\neg Q \wedge \neg S) \vee (P \vee R) \big) \tag{13}$$

Which, by the De Morgan’s Law, is equivalent to

$$\big( \neg(P \vee R) \vee (Q \vee S) \big) \wedge \big( \neg(Q \vee S) \vee (P \vee R) \big) \tag{14}$$

Using, again, the Material Implication we write our previous expression as

$$\big( (P \vee R) \to (Q \vee S) \big) \wedge \big( (Q \vee S) \to (P \vee R)\big) \tag{15}$$

Finally, using the first rule of inference used here to deduce $(2)$ from $(1),$ we get

$$(P \vee R) \leftrightarrow (Q \vee S) \tag{16}$$

Hence, we have proved that $(1) \implies (16),$ i.e.

$$(P \leftrightarrow Q) \wedge (R \leftrightarrow S) \implies (P \vee R) \leftrightarrow (Q \vee S) \ \text{. } \text{ } \text{ }\square$$