0
$\begingroup$

Simplfiy $[[[(p\land q)\land r)]\lor [(p\land q)\land\lnot r)]]\lor\lnot q]\to s$

I know how to do it, but am stuck on the last few simplifications.

Below are a few things I am a bit confused on/ unsure if I'm correct


  1. For the first step, do I ignore the "or not q" and simplfiy everything on the left side?

  2. How does the distributive law work for simplifying $[(p\land q)\land r)]\lor [(p\land q)\land\lnot r)]$? Like this?

$(p\land q)$ multiplies $(p\land q)$ which gives the same result so this part is $(p\land q)$ with the $\land$ sign in the middle.

Then $r\lor\lnot r$ and final becomes $(p\land q) \land (r \lor \lnot r)$. This is correct but is this how it's supposed to be done?

  1. Last thing I'm confused on is the last part where you get $(p \lor \lnot q) \to s$ which is then finally simplified to $(q \to p) \to s$.

Is commutative law applied to $(p \lor \lnot q)$ then becomes $(\lnot q \lor p)$; then use conditional law?

Also, can I just stop at $(p \lor\lnot q) \to s$ OR do I have to simplify it one step more to $(q \to p) \to s$? IN OTHER WORDS, can I just ignore the implication/conditional law?


ALSO is writing the brackets required? for something like $(p \lor\lnot q) \to s$, can i write it without brackets like $p \lor \lnot q \to s$?

IMPORTANT: From each line of simplfication, where to write the law I used? Do I write it beside after using the law, or BEFORE using the law?

For example:

$\lnot\lnot p$ (use double negation)

$p$ ( double negation used)??

when to write the law used? Write it when literally using it, before using it, or after its used?

$\endgroup$

1 Answer 1

0
$\begingroup$
  1. Sure, you can 'ignore' the $\lor \neg q$ while working on the rest. You are likewise 'ignoring' the $\to s$. It's ok: boolean logic laws can be applied to component statement that, as such, ignore everything else about that statement, i.e.just leave the rest alone.

  2. Yes, you can treat the $p \land q$ as a single statement that, when distibuted over $r \lor \neg r$, results in $(p \land q \land r) \lor (p \land q \land \neg r)$. So, since Distribution works both ways (like all equivalence rules), that means that from $(p \land q \land r) \lor (p \land q \land \neg r)$ you can go to $(p \land q) \land (r \lor \neg r)$ by citing Distribution.

  3. It depends on how the implication law is defined for your system, but in most systems would indeed need to do a commutation before doing the implication.

As far as how far you need to go ... that depends on how 'most simplified' is defined. If it means to have as few operators as possible, then you'll need to do that final implication.

Finally, for citing the principles, there are many different philosophies. Personally, I like to put the names right in between the statements, so that it really becomes clear that it is a two-way equivalence that allows you to go from the one to the other, but also back. So, for example:

$$\neg \neg p$$

$$\overset{Double \ Negation}{\Leftrightarrow}$$

$$p$$

$\endgroup$
2
  • $\begingroup$ thank you. Also for simplification, how do you know when to stop simplifying? can there be more than one answer where different laws were used or is there always exactly one answer? $\endgroup$
    – user704743
    Oct 16, 2019 at 3:56
  • $\begingroup$ @PatrickPichart Excellent question! Again, it depends on how 'most simplified' is defined. But yes, even if it is defined clearly (such as 'shortest statement'), it can turn out to be really hard to demonstrate that you have reached the 'most simplified' statement. Still, typically with these kinds of problems hou get to something like $A \land B$, or just $P$, at which point it should be pretty clear you're 'there' .... but to actually prove you're 'there' can be really hard. It's not different from simplifying algebraic statements in arithmetic, really. $\endgroup$
    – Bram28
    Oct 16, 2019 at 12:29

You must log in to answer this question.