2
$\begingroup$

Let $\psi_{1} := (P \wedge Q \wedge R)\vee(\neg P\wedge Q\wedge\neg R)\vee(\neg P\wedge\neg Q\wedge R)\vee(\neg P \wedge\neg Q\wedge\neg R)$ and

Let $\psi_{2} := (\neg P \wedge \neg Q) \vee (\neg P \wedge \neg R) \vee (P \wedge Q \wedge R)$

I have proven so far, that the two formulas in DNF are equivalent to $P\Leftrightarrow(Q\wedge R)$

Now I need to simplify $\psi_{1}$ with classical equivalences to obtain $\psi_{2}$

My problem is, that I am struggling with the distribution of $\vee$ and $\wedge$ with three Propositional variables in the brackets.

Maybe you guys can give me some tips or help me out a bit on this one.

$\endgroup$
1
$\begingroup$

HINT

Use:

Adjacency

$P \Leftrightarrow (P \lor Q) \land (P \lor \neg Q)$

$P \Leftrightarrow (P \land Q) \lor (P \land \neg Q)$

So, for example, you can combine the terms $\neg P \land \neg Q \land R$ and $\neg P \land \neg Q \land \neg R$ to $\neg P \land \neg Q$

In fact, that gets you almost there. Indeed, you could likewise combine $\neg P \land Q \land R$ and $\neg P \land \neg Q \land \neg R$ to $\neg P \land \neg R$

The only issue is that doing both combinations requires two terms $\neg P \land \neg Q \land \neg R$ . But, that's easy to obtain using:

Idempotence

$P \Leftrightarrow P \land P$

$P \Leftrightarrow P \lor P$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I got the same used $(\neg P \land \neg Q \land \neg R)$ and $(\neg P \land \neg Q \land R)$ to obtain $(\neg P \land \neg Q)$. I just haven´t figuered out what to do with the other two terms yet. $\endgroup$ – SuperMathBrothers Jan 16 '18 at 18:56
0
$\begingroup$

Hint: If you're familiar with distribution over two terms, break up $(X \vee Y \vee Z)$ into $((X \vee Y )\vee Z)$ and distribute twice.

| cite | improve this answer | |
$\endgroup$

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.