# 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)]$

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?.

• How do you define $q\mathop{\triangle}p$? If it’s equivalent to $(q\land\neg p)\lor(\neg q\land p)$, then the righthand side of the outermost implication is always true, so the whole statement is true, and Jenny could do anything at all. Dec 24 '20 at 3:40
• @BrianM.Scott According to my book $p \bigtriangleup q \equiv \lnot (p \leftrightarrow q)$ it also states that $p \bigtriangleup q \equiv (p \lor q) \land \lnot (p\land q)$ it also states $p \bigtriangleup V \equiv \lnot p$ and also $p \bigtriangleup q \equiv (\lnot p \leftrightarrow q)$. I'm adding these as it might help in the solution but so far I'm confused. The operator is labeled as a strong disjunction. I'm not very familiar with this. Given these considerations would help better? Dec 24 '20 at 4:28
• Okay; it means what I thought it meant. And that means that $$(p\leftrightarrow q)\lor(q\mathop{\triangle}p)$$ is equivalent to $$(p\leftrightarrow q)\lor\neg(p\leftrightarrow q)\,,$$ which is always true, so if your parentheses are correctly placed, the whole statement is a tautology: it’s always true. Dec 24 '20 at 4:31
• @BrianM.Scott I meant by the way that $p\bigtriangleup T \equiv \lnot p$ Sorry for the typo. I'm still confused, hence an answer with steps is required. I don't know how you got to the conclusion that all is a tautology. Given this, how is this translated into words?. Jenny goes to the movies or what?. Please I'm stuck. The nested part is confusing. Dec 24 '20 at 4:46
• The expression has the form $\varphi\to\psi$, where $\psi$ is $$(p\leftrightarrow q)\lor(q\mathop{\triangle}p)\,.$$ An implication is always true when its conclusion is true, and $\psi$ is always true, so the expression reduces simply to $\top$. Unfortunately, that doesn’t agree with any of the four proposed verbal answers. It is possible to simplify $\varphi$ considerably, but there isn’t much point, since $\varphi\to\top$ is always true no matter what $\varphi$ is. Thus, the original expression is true no matter what the truth values of $p$ and $q$ are. The question appears to be defective. Dec 24 '20 at 4:54

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

• Why the third statement is a tautology?. Dec 24 '20 at 5:37
• @ChrisSteinbeckBell: Because it’s $p\lor\neg p$, which is equivalent to $\top$. Dec 24 '20 at 5:39
• Sorry I missed this part. I see that you used a couple of identities, it seems that those are distributive and biconditional. Sorry for being lethargic in understanding this but now I get the idea. The catch here was that since the conclusion reduces to a tautology the implication is also a tautology. Which translated in terms of the statement of the problem as the option where it mentions Jenny going to the movies or not going to the movies. Dec 24 '20 at 5:55
• @ChrisSteinbeckBell: Yes, that’s the only one of the four that is a tautology. It’s a somewhat convoluted problem, and if one simply starts simplifying from left to right, one ends up doing an awful lot of unnecessary work! Then it may take a bit of thought to realize that one of the four answers really is a tautology and so is a match, even though what it says in words doesn’t sound at all like any of the simplified forms of the original expression. Dec 24 '20 at 6:06