Answer to Question #185565 in Discrete Mathematics for Leo

Question

verify each of the following equivalences using basic equivalences

1)((P∧Q∧R)→S∧(R→(P ∨ Q ∨ S))≡R∧(P↔Q)→S

2)((P∧Q)→R)∧(Q→(S∨R))≡Q∧(S→P)→R

Answer 1

1) Simplify the left side of the equivalence

$\left( {\left( {P \wedge Q \wedge R} \right) \to S \wedge \left( {R \to \left( {P \vee Q \vee S} \right)} \right)} \right) = \left( {\left( {\overline {\left( {P \wedge Q \wedge R} \right)} \vee S} \right) \wedge \left( {\overline R \vee \left( {P \vee Q \vee S} \right)} \right)} \right) = \left( {\overline P \vee \overline Q \vee \overline R \vee S} \right) \wedge \left( {\overline R \vee P \vee Q \vee S} \right) = \left( {\overline R \vee S} \right) \vee \left( {\left( {\overline P \vee \overline Q } \right) \wedge \left( {P \vee Q} \right)} \right) = \left( {\overline R \vee S} \right) \vee \left( {\overline P \wedge P \vee \overline Q \wedge P \vee \overline P \wedge Q \vee \overline Q \wedge Q} \right) = \left( {\overline R \vee S} \right) \vee \left( {0 \vee \overline Q \wedge P \vee \overline P \wedge Q \vee 0} \right) = \left( {\overline R \vee S} \right) \vee \left( {\overline Q \wedge P \vee \overline P \wedge Q} \right) = \overline R \vee S \vee (P \oplus Q)$

Simplify the right side of the equivalence:

$R \wedge \left( {P \leftrightarrow Q} \right) \to S = R \wedge \left( {P \to Q} \right) \wedge \left( {Q \to P} \right) \to S = R \wedge \left( {\overline P \vee Q} \right) \wedge \left( {\overline Q \vee P} \right) \to S = \overline {R \wedge \left( {\overline P \vee Q} \right) \wedge \left( {\overline Q \vee P} \right)} \vee S = \overline R \vee P \wedge \overline Q \vee Q \wedge \overline P \vee S = \overline R \vee (P \oplus Q) \vee S$ We have:

$\overline R \vee S \vee (P \oplus Q)\equiv \overline R \vee (P \oplus Q )\vee S$

Equivalence is performed.

Answer: Equivalence is performed

2) Simplify the left side of the equivalence

$\left( {\left( {P \wedge Q} \right) \to R} \right) \wedge \left( {Q \to \left( {S \vee R} \right)} \right) = \left( {\overline {\left( {P \wedge Q} \right)} \vee R} \right) \wedge \left( {\overline Q \vee \left( {S \vee R} \right)} \right) = \left( {\overline P \vee \overline Q \vee R} \right) \wedge \left( {\overline Q \vee S \vee R} \right) = \overline Q \vee R \vee \overline P \wedge S$

Simplify the right side of the equivalence

$Q \wedge \left( {S \to P} \right) \to R = \overline {Q \wedge \left( {S \to P} \right)} \vee R = \overline {Q \wedge \left( {\overline S \vee P} \right)} \vee R = \overline Q \vee \overline {\left( {\overline S \vee P} \right)} \vee R = \overline Q \vee S \wedge \overline P \vee R$

We have

$\overline Q \vee R \vee \overline P \wedge S\equiv \overline Q \vee S \wedge \overline P \vee R$

Equivalence is performed.

Answer: Equivalence is performed