3
$\begingroup$

Just learning mathematical proof writing and came upon this interesting question Writing an expression using logic.

$$(P \land Q \land \lnot R) \lor (P \land \lnot Q \land \lnot R) \lor (\lnot P \land Q \land R)$$ Just to help myself prepare for these kind of questions (this question might have already been solved, but), how would you reduce this boolean sentence where as the question states, solving for (???) ?

$\endgroup$
3
$\begingroup$

The objective here is not to solve it, as there is no equation to solve, but to simplify the proposition: but what counts as simplified is subjective, and needs specification. For example, one can aim to write it in conjunctive normal form (as it is already in disjunctive normal form). Sometimes for questions like this you will be asked to show that the proposition is equivalent to some given proposition.

You have: $$(P \land Q \land \lnot R) \lor (P \land \lnot Q \land \lnot R) \lor (\lnot P \land Q \land R) \equiv \quad???\tag{1}$$

There are various ways to proceed and/or manipulate the expression into an equivalent form, using distribution, or De Morgan's in some cases, for example, depending on what your goal is.

E.g., in response to your question below: Note that we can use the distributive law to combine (factor out) like terms in the first two terms in $(1)$:

$$(P \land Q\land \lnot R) \lor (P \land \lnot Q \land \lnot R)$$ $$\equiv [(P \land \lnot R) \land Q] \lor [(P \land \lnot R) \land \lnot Q]$$ $$\equiv (P \land \lnot R) \land (Q \lor \lnot Q)$$ $$\equiv P \land \lnot R$$

That gives us, remembering we still have the third term of $(1)$ to retain:

$$(P \land Q \land \lnot R) \lor (P \land \lnot Q \land \lnot R) \lor (\lnot P \land Q \land R) \equiv \color{blue}{\bf (P\land \lnot R) \lor (\lnot P \land Q \land R)}\tag{2}$$

As mentioned, $(1)$ is already in one of the standard forms used in logic: Disjunctive normal form (DNF): and it meets the criteria given in the linked question you provide, to find an expression using only the connectives $\land, \lor, \lnot$: it represents all the information conveyed by the truth-table: and so can be considered to be a valid representation for "$???$". So can the RHS of $\color{blue}{\bf (2)}$

But what counts as "simplified" depends on some given, specified constraints.

$\endgroup$
  • $\begingroup$ Right, that's what I meant to ask, how to simplify it. So how is it simplified? I tried searching De Morgan's law but didn't find anything that made sense. Is there any reference you can make that will cap my curiosity? $\endgroup$ – Jlhglkj Glkjhg May 13 '13 at 1:57
  • $\begingroup$ You're welcome, Jlhglkj! ;-) $\endgroup$ – Namaste May 13 '13 at 2:17
  • $\begingroup$ Miss you Amy...++++ $\endgroup$ – mrs May 13 '13 at 2:48
  • $\begingroup$ Hello!!!! @Babak! Good to "see" you! ;-) $\endgroup$ – Namaste May 13 '13 at 2:54
  • $\begingroup$ I am at the Maths dept. right now and chatting in the chat room here. Asking something about non-edu geo. $\endgroup$ – mrs May 13 '13 at 2:55
2
$\begingroup$

You can start by combining the first two terms:

$$\begin{align*} (P\land Q\land\neg R)\lor(P\land\neg Q\land\neg R)&=\big((P\land\neg R)\land Q\big)\lor\big((P\land\neg R)\land\neg Q\big)\\ &=(P\land\neg R)\land(Q\lor\neg Q)\\ &=P\land\neg R\;. \end{align*}$$

That leaves you with

$$(P\land\neg R)\lor(\neg P\land Q\land R)\;.$$

I'm not at all sure that you can do anything nicer with a disjunctive form.

$\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.