Simplifying $[\{(\lnot p\lor q)\land(\lnot q\lor p)\}\to\{(q\lor\lnot p)\land p\}]\to[(p \leftrightarrow q)\lor(q \bigtriangleup p)]$

Question

Simplify the following expression:

$$\left[\{(\lnot p \lor q)\land(\lnot q \lor p)\}\rightarrow\{(q \lor \lnot p)\land p\}\right]\rightarrow\left[(p \leftrightarrow q)\lor(q \bigtriangleup p)\right]$$

Assume: $$p = \text{Jenny goes to the movies} \qquad q = \text{Jenny goes to the park}$$ It is known the expression given is a complex statement.

Using the information given simplify the statement and match the right answer. The answers given in my book are as follows:

1. Jenny either goes to the park or goes to the movies
2. Jenny goes to the movies if and only if she goes to the park
3. Jenny goes to the movies or she doesn't go to the movies
4. Jenny doesn't go to the park but she goes to the movies

My book defines the operator indicated as $\bigtriangleup$ as strong disjunction. This is shown in the truth table from below:

$\begin{array}{|c|c|c|} \hline p& q & p \bigtriangleup q \\ \hline T & T& F\\ \hline T& F& T\\ \hline F& T & T\\ \hline F& F & F\\ \hline \end{array}$

Then it indicates these identities related with the strong disjunction:

$p \bigtriangleup q \equiv \lnot (p \leftrightarrow q)$

$p \bigtriangleup q \equiv (\lnot p \leftrightarrow q)$

$p \bigtriangleup q \equiv (p \lor q) \land \lnot (p\land q)$

$p \bigtriangleup T \equiv \lnot p$

Considering these how can this expression or statement be simplified?.

Can someone help me with this problem please?. The thing is I'm stuck at the very beginning. I'm assuming that in order to make a simplification it might be needed to use logic algebra but this complex statement it is too long.

Does it exist a way to make it short without a fuss?.

I'm not sure if the identities which should be used here might be absorption or de Morgan's or any of those.

Can someone help me with a detailed step by step on how to use these and solve this riddle? The thing here is that what it confuses me the most is how to approach the biconditional therefore can someone help me?.

Answer 1

$$\left[\{(\lnot p \lor q)\land(\lnot q \lor p)\}\rightarrow\{(q \lor \lnot p)\land p\}\right]\rightarrow\left[(p \leftrightarrow q)\lor(q \bigtriangleup p)\right]$$

First,

$$\begin{align*} (\neg p\lor q)\land(\neg q\lor p)&\equiv\big((\neg p\lor q)\land\neg q\big)\lor\big((\neg p\lor q)\land p\big)\\ &\equiv(\neg p\land\neg q)\lor(q\land\neg q)\lor(\neg p\land p)\lor(q\land p)\\ &\equiv(\neg p\land\neg q)\lor(q\land p)\\ &\equiv p\leftrightarrow q\,, \end{align*}$$

and

$$(q\lor\neg p)\land p\equiv(q\land p)\lor(\neg p\land p)\equiv q\land p\,,$$

so

$$\big((\lnot p \lor q)\land(\lnot q \lor p)\big)\to\big((q \lor \lnot p)\land p\big)$$

is equivalent to $(p\leftrightarrow q)\to(p\land q)$. Now

$$\begin{align*} (p\leftrightarrow q)\to(p\land q)&\equiv\neg(p\leftrightarrow q)\lor(p\land q)\\ &\equiv(p\land\neg q)\lor(\neg p\land q)\lor(p\land q)\\ &\equiv(p\land\neg q)\lor\big((\neg p\lor p)\land q\big)\\ &\equiv(p\land\neg q)\lor q\\ &\equiv(p\lor q)\land(\neg q\lor q)\\ &\equiv p\lor q\,, \end{align*}$$

so we’ve now simplified the original expression to

$$(p\lor q)\to\big((p\leftrightarrow q)\lor(q\mathop{\triangle}p)\big)\,.$$

Finally,

$$(p\leftrightarrow q)\lor(q\mathop{\triangle}p)\equiv(p\leftrightarrow q)\lor\neg(p\leftrightarrow q)\equiv\top\,,$$

so the original expression simplifies to $(p\lor q)\to\top$, which further simplifies to $\top$.

In other words, it’s true no matter where Jenny goes. The only one of the four statements that is also a tautology (i.e., true no matter what Jenny does), is the third: Jenny goes to the movies or she doesn’t go to the movies.

Note that had I simplified $(p\leftrightarrow q)\lor(q\mathop{\triangle}p)$ to $\top$ first, I could, as I explained in the comments, immediately have concluded that the whole expression is a tautology: every implication of the form $\varphi\to\top$ is true no matter what the truth value of $\varphi$ is. This would have rendered unnecessary any simplification of the lefthand side of the main implication. I included that simplification as an illustration of the kinds of manipulation that might be needed in a different problem.