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

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: • You can use, for example, a ∧ (b ∨ c) is equivalent to (a ∧ b) ∨ (a ∧ c). Check your logic identities. That's the point of the exercise. Jun 15, 2019 at 2:27
• I think something is buggy in your truth table $p \vee \neg q$ is true when $p$ is true Jun 15, 2019 at 2:30
• First row, $p$ is true, $\neg q$ is false so $p\vee \neg q$ should be true, you have it marked as false Jun 15, 2019 at 2:37
• No. p, ¬p, and ¬q are not identities. An identity is like what I showed you in my first comment. It's a logical rule showing how one form is equivalent to another. In your case the term (p ∨ ¬q) would correspond to a. Jun 15, 2019 at 2:45
• What is the textbook? While we can show many different ways to solve this, in a course like this it's critically important to be able to cite the starting assumptions/axioms/theorems that your reasoning is based on. Jun 15, 2019 at 14:37

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

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

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

$$(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!

• I'm not sure it's worth learning this as its own special fact. You can get it immediately from distribution of $\land$ and $\lor$ as in Robert Shore's answer, without needing to know its name. Jun 15, 2019 at 13:30
• @DavidRicherby: It's very useful for automated theorem proving. Jun 15, 2019 at 14:04
• @DavidRicherby To each their own I guess. I do boolean algebra a lot, and find this equivalence to be a great time-saver and insight-provider. Same with Absorption ($p \land (p \lor q) \Leftrightarrow p$) and Reduction ($p \land (\neg p \lor q) \Leftrightarrow p \land q$). Yes, they can all be derived from more basic principles, but boy, do things go faster if you have them. And, I quickly see things that others do not. Indeed, merely relying on the most elementary principles is like doing arithmetic using the Peano axioms, or programming in machine code. Jun 15, 2019 at 14:06
• @Kevin Good point :) Jun 15, 2019 at 14:08
• @Bram28 Fair enough -- I bow to your greater experience. Jun 15, 2019 at 17:44

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}

• Don't you also need $aa=a$ to get from $\bar{q}\bar{q}$ to $\bar{q}$? Jun 16, 2019 at 4:36
• @pizzapants184: Yes. You are correct. I forgot to write it. Jun 16, 2019 at 16:13

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

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.