3
$\begingroup$

How can I get $(A ↔ ¬B)$ or $(¬A ↔ B)$ from $¬(A ↔ B)$ using propositional laws?

I tried expanding $¬(A ↔ B)$ and I got to $(A ∧ ¬B) ∨ (B ∧ ¬A)$

I also tried expanding $(A ↔ ¬B)$ and I got to $(¬A ∨ ¬B) ∧ (B ∨ A)$

I don't know where in my expansion I went off the wrong path

$\endgroup$
3
  • $\begingroup$ If it helps, $\neg(A \Leftrightarrow B)$ is xor = "Exclusive or" = $A \oplus B$. en.wikipedia.org/wiki/Exclusive_or $\endgroup$
    – zkutch
    Nov 11, 2020 at 2:25
  • $\begingroup$ I'm not sure I understand the question, but note that $\neg(A\leftrightarrow B)$ is symmetric in $A$ and $B$, and $A\leftrightarrow\neg B$ is not. So there's nothing you can do to the former to get to the latter. $\endgroup$
    – Mark S.
    Nov 11, 2020 at 2:46
  • $\begingroup$ As mark says you can get to them because that expression implies what you got, not necessarily what is in your first sentence. $\endgroup$
    – Derek Luna
    Nov 11, 2020 at 2:48

2 Answers 2

5
$\begingroup$

Your expansion of $\lnot(A\leftrightarrow B)$ into $(A\land\lnot B)\lor(B\land\lnot A)$ was correct.

Your expansion of $(A\leftrightarrow\lnot B)$ into $(\lnot A\lor\lnot B)\land(B\lor A)$ was also correct.

Well done. As @zkutch pointed out, the negation of $A\leftrightarrow B$ can also be though of as exclusive or (XOR), meaning one or the other but not both.


To address your comment, we first expand $\lnot(A\leftrightarrow B)$ into $\lnot((A\land B)\lor(\lnot A\land\lnot B))$. Then we use De Morgan's laws (which flip $\land$'s, $\lor$'s, and negate everything which isn't one) to get $\lnot(A\land B)\land\lnot(\lnot A\land\lnot B)$, which turns into $(\lnot A\lor \lnot B)\land(A\lor B)$.

We then distribute over the $\land$ to arrive at $(\lnot A\land A)\lor (\lnot A\land B)\lor(\lnot B\land A)\lor(\lnot B\land B)$, which simplifies to $(\lnot A\land B)\lor(\lnot B\land A)$.

Since $(\lnot A\land B)\lor(\lnot B\land A)$ reads as $A$ is true and not $B$, or $B$ is true and not $A$, it is equivalent to $A\leftrightarrow\lnot B$.

$\endgroup$
4
  • 1
    $\begingroup$ But is there any way I can get from one to another? Think of it as a proving question and I want to show using proportional laws that ¬(A↔B) is equal to (A↔¬B). I've been thinking about this for a while now. $\endgroup$ Nov 11, 2020 at 2:34
  • $\begingroup$ @UneducatedPotato Let me know if you get stuck at any point in the derivation. $\endgroup$
    – user400188
    Nov 11, 2020 at 2:54
  • $\begingroup$ Thanks for the explanation. I just wish there was a way we could show how (¬A∧B)∨(¬B∧A) is equivalent to A↔¬B @user400188 $\endgroup$ Nov 11, 2020 at 2:59
  • 1
    $\begingroup$ @UneducatedPotato The very definition of $A$ if and only if $C$ is $(A\land C)\lor(\lnot A\land\lnot C)$. If you substitute $\lnot B$ for $C$, you will get your answer. $\endgroup$
    – user400188
    Nov 11, 2020 at 3:25
2
$\begingroup$

Distribute:

$$(A\land\lnot B)\lor(B\land\lnot A)=(A\lor B)\land(\lnot B\lor B)\land(A\lor\lnot A)\land(\lnot B\lor\lnot A)$$

and then recognize that $(P\lor\lnot P)$ is always true, so the middle two pairs drop out and the right hand side reduces to

$$(A\lor B)\land(\lnot B\lor\lnot A)$$

$\endgroup$
1
  • $\begingroup$ Ah, I didn't see that user400188 had edited their answer to include what amounts to the same thing. $\endgroup$ Nov 11, 2020 at 3:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .