Simplify, equivalent for (p ∨ ¬q) ∧ (¬p ∨ ¬q)

Question

In my text book I'm asked to deduce a simpler expression for

(p ∨ ¬q) ∧ (¬p ∨ ¬q)

Looking at an equivalency table I did, it seems p ∨ ¬q gives the same results as (p ∨ ¬q) ∧ (¬p ∨ ¬q). However I'm not sure how you would deduce this without the table, as in, if I was outrightly asked to write the above in simpler terms I wouldn't know where to begin. Am I understanding this correctly?

My Table:

Answer 1

Here's the corrected table:

$$\begin{array}{cc|cccc|c} P & Q & \neg P & \neg Q & P\lor\neg Q & \neg P\lor\neg Q & (P\lor \neg Q)\land(\neg P\lor \neg Q)\\\hline T&T&F&F&T&F&F\\ T&F&F&T&T&T&T\\ F&T&T&F&F&T&F\\ F&F&T&T&T&T&T \end{array}$$

From this, you can see that $(p \lor \neg q)\land(\neg p \lor \neg q) \iff (\neg q)$

Answer 2

$$(p \lor \lnot q) \land (\lnot p \lor \lnot q) \iff (p \land \lnot p) \lor \lnot q \iff \lnot q.$$

Answer 3

This is actually an instance of the following logical equivalence principle:

Adjacency

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

So, with this principle, you can immediately say that:

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

When you do boolean algebra to simplify expressions, this situation comes up a lot, so I highly recommend remembering this equivalence principle!

Answer 4

Note that if $q$ is true one of the conjuncts will be true and the other false, and the conjunction will be false, whereas if $q$ is false both conjunts will be true, so the conjunction will be true. Since it's true iff $q$ isn't, the simplest expression for the truth-function is $\neg q$.

Answer 5

Just using the following properties of boolean algebra,

\begin{align} a\bar{a} &=0\\ 1 a &=a\\ 0 a &=0\\ a+\bar{a}&=1\\ 0+a &=a\\ 1+a &=1\\ a+a&=a\\ a(b+c)&=ab+ac \end{align}

you can simplify

\begin{align} (p+\bar{q})(\bar{p}+\bar{q}) &=p\bar{p}+ (p+\bar{p})\bar{q}+\bar{q}\bar{q}\\ &= 0 + 1\bar{q}+\bar{q}\\ &= 0 +\bar{q}\\ &=\bar{q} \end{align}

Answer 6

We can do this using propositional logic. With some mild short-cuts for brevity, we have:

1.  Assume: (p ∨ ¬q) ∧ (¬p ∨ ¬q)
2.  Conclude: p ∨ ¬q (from 1)
3.  Conclude: ¬p ∨ ¬q (from 1)
4.  Suppose p:
5.      Conclude ¬q (from 2,4)
6.  Conclude p → ¬q (from 4-5)
7.  Conclude ¬q ∨ ¬q (from 2, 6)
8.  Conclude ¬q (from 7)

I'll note that it is common to conclude 6 directly from 2.

So, this shows that ((p ∨ ¬q) ∧ (¬p ∨ ¬q)) → ¬q . However, now we have to ask: Does it show anything else? Let's apply basic substitution to check:
(p ∨ ¬q) ∧ (¬p ∨ ¬q)
(p ∨ ⊤) ∧ (¬p ∨ ⊤) (We know ¬q, so we can learn nothing further about q. Replace ¬q with T.
⊤ ∧ T (Anything ∨ T) is always true, regardless of the value anything. So that tells us nothing.

So, we can now conclude:
p ∨ ¬p (This is a tautology due to law of excluded middle, so it can remain unstated)
¬q

An even simpler proof would be proof by contradiction (i.e., assume q, then get (p) ∧ (¬p)). This is the approach taken by J.G.