$\begingroup$

Find a formula using only the connectives: conjunction, disjunction, and negation that is equivalent to, P exclusive or Q. I cannot figure out a way to come up with a logical equivalent statement without randomly guessing.

$\endgroup$ 5

3 Answers

$\begingroup$

You want $p$ to be true or $q$ to be true, but not both at the same time, thus all of the below formula would give you the correct result:

1. "$p$ is true or $q$ is true, and it's not the case that both $p$ and $q$ are true"

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

2. "$p$ is true and $q$ is false, or $p$ is false and $q$ is true¹"

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

3. (explaining @Jon Mark Perry's first forumla) "it is neither the case that both $p$ and $q$ are true nor that both $p$ and $q$ are false²"

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

4. (explaining Jon Mark Perry's second one) "$p$ is true or $q$ is true, but either $p$ or $q$ must be false³"

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

Of course, there is an infinite number of logically equivalent statements (e.g. $(a \land a)$ would trivially be another possible formula to just saying $(a)$, now replace $(a)$ by one of the inclusive-or-formulas and you got another one), but the above listed should be the most intuitive ones.

¹ By the inclusive logical or $\lor$ used here, the statement would also be true if both sides of the formula were true, but that will never happen anyway, since $p \land \neg p$ is a contradiction.
² $\neg(a \lor b)$ ("not $a$ or $b$") reads as "neither $a$ nor $b$".
³ Again, the inclusive or in the second part of the statement would also allow for both $p$ and $q$ to be false, but that possibility is ruled out be the first part of the conjuntion.

$\endgroup$ $\begingroup$

Given a truth table of a boolean function, you can always create a boolean function that is equivalent using only conjunction, disjunction, and negation.

If one looks at the truth value of xor, it is only true in two cases: if $p$ is true and $q$ is false OR $p$ is false and $q$ is true which can be written as $(p \wedge \overline{q}) \vee (\overline{p} \wedge q)$.

$\endgroup$ $\begingroup$

We have:

$$\lnot ((P \land Q) \lor (\lnot P \land \lnot Q))$$

and:

$$(P\lor Q)\land (\lnot P \lor \lnot Q)$$

From the comments:

$$(P\lor Q) \land \lnot(P \land Q)$$

addendum: adding lemontree's for completeness:

$$(P \land \lnot Q) \lor (\lnot P \land Q))$$

$\endgroup$

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

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