0
$\begingroup$

I am having some trouble with reducing some propositional logic statements.

The first one is as follows:

$\neg(P \lor Q) \lor \neg (P \lor \neg Q)$.

I used deMorgan's law to change this to:

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

Is there anything I can do to reduce this further?


The second one is:

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

I have no idea where to even start on this one.

Any tips?

Thanks.

$\endgroup$
1
$\begingroup$

(not(P or Q) or not (P or not Q).

I used deMorgan's law to change this to:

(not P and not Q) or (not P and Q)

$$\begin{align}\neg (P\lor Q)\lor \neg (P\lor \neg Q) & \equiv (\neg P\land \neg Q)\lor (\neg P\land Q) & \textsf{de'Morgan's Laws} \\ & \equiv \neg P \land (\neg Q\lor Q) & \textsf{Distribution} \end{align}$$

Can you take it from there?


((P or Q) iff (not P and Q)

First use $A\leftrightarrow B \equiv (A\land B)\lor(\neg A\land \neg B)$

$$\begin{align}(P\lor Q)\leftrightarrow (\neg P\land Q) & \equiv \big( (P\lor Q)\land(\neg P\land Q) \big) \lor \big(\neg (P\lor Q)\land \neg (\neg P\land Q) \big) \end{align}$$

Now simplify...

$\endgroup$
  • $\begingroup$ Ok, so I realize by looking at it that the first part of that ((P∨Q)∧(¬P∧Q)) can be simplified to (¬P∧Q), but what steps do I need to show to get to that? The second part can be simplified to (¬P∧¬Q), but again, I don't know the steps to prove it. $\endgroup$ – dibdub Jan 24 '16 at 6:25

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.