7

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:

table

Rodrigo de Azevedo
  • 1
Ari
  • 199
  • 1
    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 02:27
  • ah I see, so would that mean p ∧ (¬p ∨ ¬q) == (p ∨ ¬q) ∧ (¬p ∨ ¬q) – Ari Jun 15 '19 at 02:30
  • 2
    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 02:30
  • @AriVictor no. I don't see how you got that. Look carefully again at the identity. – lurker Jun 15 '19 at 02:34
  • @KitterCatter Sorry I don't follow? I understoof ∨ to mean when either is true, therefore if p is false and q is false, ¬ would be true making ∨¬ true? – Ari Jun 15 '19 at 02:35
  • 3
    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 02:37
  • @lurker right! I see, if we say a, b, c, then the three identities would be p, ¬p, and ¬q therefore ¬ ∧ (p ∨ ¬p) ? – Ari Jun 15 '19 at 02:38
  • @KitterCatter Ohh! I see now. – Ari Jun 15 '19 at 02:41
  • 2
    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 02:45
  • The column for $p$ or not $q$ is incorrect. You can see it because, in the table, it is the same as not $q$, which is suspicious since $p$ or not $q$ had more possibilities of truth, so it should be true more often than not $q$. – Taladris Jun 15 '19 at 07:23
  • 1
    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

6 Answers6

22

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

Robert Shore
  • 23,332
15

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

David Richerby
  • 2,450
N. Bar
  • 1,600
5

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!

Bram28
  • 100,612
  • 6
  • 70
  • 118
  • 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
  • 2
    @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
  • 1
    @Bram28 Fair enough -- I bow to your greater experience. – David Richerby Jun 15 '19 at 17:44
2

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}

Display Name
  • 2,715
0

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

J.G.
  • 115,835
0

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.

Brian
  • 116