# 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. – lurker Jun 15 '19 at 2:27
• I think something is buggy in your truth table $p \vee \neg q$ is true when $p$ is true – Kitter Catter Jun 15 '19 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 – Kitter Catter Jun 15 '19 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. – lurker Jun 15 '19 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. – Daniel R. Collins Jun 15 '19 at 14:37

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

$$(p \lor \lnot q) \land (\lnot p \lor \lnot q) \iff (p \land \lnot p) \lor \lnot q \iff \lnot 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. – David Richerby Jun 15 '19 at 13:30
• @DavidRicherby: It's very useful for automated theorem proving. – Kevin Jun 15 '19 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. – Bram28 Jun 15 '19 at 14:06
• @Kevin Good point :) – Bram28 Jun 15 '19 at 14:08
• @Bram28 Fair enough -- I bow to your greater experience. – David Richerby Jun 15 '19 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}$? – pizzapants184 Jun 16 '19 at 4:36
• @pizzapants184: Yes. You are correct. I forgot to write it. – Kim Jong Un Jun 16 '19 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.