Simplifying in propositional logic with only negations, disjunctions, and conjunctions

logicpropositional-calculus

Sometimes when solving some exercises of propositional logic I have some doubts of whether a certain expression could be more simplified. But it is worse when I get an exercise and I cannot see exactly how to simplify it after using some of the laws.

The exercise is:

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

I tried using distributive law and Morgan law, and even introduced some conditionals to try to transform it, but still I cannot simplify the expression.

Best Answer

Okay, I firstly did the truth table ( I didn't do it first because I wanted to work with the different laws and learn to see how to apply them). This is left as it follows:

\begin{array}{ccccc} p & q & (\neg p \lor \neg q) & (p \lor q) & (\neg p \lor \neg q) \land (p \lor q)\\ \hline \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 \\ \end{array}

After this, and seeing that this was equal to $ \neg(p \leftrightarrow q) $ I tried to find it using the different laws. The procedure I followed was:

$$(\neg p \lor \neg q) \land (p \lor q) = [ (\neg p \lor \neg q) \land p] \lor[(\neg p \lor \neg q) \land q] \\ = [(\neg q \land p) \lor (\neg p \land q)] \\ = [\neg(q \lor \neg p) \lor \neg (p \lor \neg q)] \\ = [\neg (p \rightarrow q) \lor \neg(q \rightarrow p)] \\ = \neg [(p \rightarrow q) \land (q \rightarrow p)] \\ = \neg (p \leftrightarrow q)$$