7
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – lurker Jun 15 '19 at 2:27
  • 2
    $\begingroup$ I think something is buggy in your truth table $p \vee \neg q$ is true when $p$ is true $\endgroup$ – Kitter Catter Jun 15 '19 at 2:30
  • 3
    $\begingroup$ First row, $p$ is true, $\neg q$ is false so $p\vee \neg q$ should be true, you have it marked as false $\endgroup$ – Kitter Catter Jun 15 '19 at 2:37
  • 2
    $\begingroup$ 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. $\endgroup$ – lurker Jun 15 '19 at 2:45
  • 1
    $\begingroup$ 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. $\endgroup$ – Daniel R. Collins Jun 15 '19 at 14:37
14
$\begingroup$

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

$\endgroup$
19
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – David Richerby Jun 15 '19 at 13:30
  • $\begingroup$ @DavidRicherby: It's very useful for automated theorem proving. $\endgroup$ – Kevin Jun 15 '19 at 14:04
  • 2
    $\begingroup$ @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. $\endgroup$ – Bram28 Jun 15 '19 at 14:06
  • $\begingroup$ @Kevin Good point :) $\endgroup$ – Bram28 Jun 15 '19 at 14:08
  • 1
    $\begingroup$ @Bram28 Fair enough -- I bow to your greater experience. $\endgroup$ – David Richerby Jun 15 '19 at 17:44
2
$\begingroup$

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}

$\endgroup$
  • $\begingroup$ Don't you also need $aa=a$ to get from $\bar{q}\bar{q}$ to $\bar{q}$? $\endgroup$ – pizzapants184 Jun 16 '19 at 4:36
  • $\begingroup$ @pizzapants184: Yes. You are correct. I forgot to write it. $\endgroup$ – Money Oriented Programmer Jun 16 '19 at 16:13
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.