Can this be simplified: $(p\vee\neg\ q) \wedge (\neg p\vee q)$?

Question

I'm taking a discrete math class and didn't know if this could be simplified more.

So far, we've learned these properties: Identities, commutative, associative, distributive, complement, idempotent, De-Morgan's, double negation.

Answer 1

You can use the distributive laws several times:

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

Whether you consider this a simplification is a matter of definition; many people find a disjunction of conjunctions (an OR of ANDs) easier to understand intuitively than a conjunction of disjunctions (an AND of ORs), and if you have the biconditional available, that last line definitely should count as a simplification.

Answer 2

Recall that $p \Rightarrow q$ is false only when $p$ is true and $q$ is false. Therefore, the truth table of $p \Rightarrow q$ is the same as that of $\neg p \vee q$. Thus, $p \Rightarrow q$ is logically equivalent to $\neg p \vee q$. It follows that the statement $(p \vee \neg q) \wedge (\neg p \vee q)$ is logically equivalent to $(q \Rightarrow p) \wedge (p \Rightarrow q)$, which is logically equivalent to $p \iff q$.