Among the 4 logical expressions below, determine which are logically equivalent and which are negation of each other.

First question. I noticed my tutor likes to use these two symbols, $\leftrightarrow \Leftrightarrow$ interchangeably. Can I also do so? Are they similar to each other?

Among the 4 logical expressions below, determine which are logically equivalent and which are negation of each other.

(1) $\neg(p\Leftrightarrow q)$

(2) $(\neg p)\Leftrightarrow(\neg q)$

(3) $(\neg p)\Leftrightarrow q$

(4) $p\Leftrightarrow (\neg q)$

(1) $\neg(p\Leftrightarrow q)\equiv \neg((p\to q)\wedge (q\to p))\equiv \neg(p\to q)\vee \neg(q \to p))\equiv\neg(\neg p\vee q)\vee \neg(\neg q \vee p)\equiv (p\wedge\neg q)\vee(q\wedge \neg p)$

(2) $(\neg p)\Leftrightarrow(\neg q)\equiv (\neg p \to \neg q)\wedge(\neg q \to\neg p)\equiv(p\vee\neg q)\wedge(q\vee\neg p)$

So far it seems (1)$\not\equiv$(2), in-fact, when I take the negation of (1), i.e $\neg$(1) , I get $\neg((p\wedge\neg q)\vee(q\wedge \neg p))\equiv\neg(p\wedge\neg q)\wedge\neg(q\wedge\neg p)\equiv(\neg p\vee q)\wedge(\neg q\vee p)\equiv(\neg q\vee p)\wedge(\neg p \wedge q)\equiv(p\vee\neg q)\wedge(q\vee\neg p)$

Therefore, (1) and (2) are negations of each other! Lets continue...

(3) $(\neg p)\Leftrightarrow q\equiv(\neg p \to q)\wedge( q\to\neg p)\equiv(p\vee q)\wedge(\neg q\vee\neg p)$

(4) $p\Leftrightarrow (\neg q)\equiv(p\to\neg q)\wedge(\neg q\to p)\equiv(\neg p\vee\neg q)\wedge(q\vee p)\equiv(p\vee q)\wedge(\neg q\vee\neg p)$

It is evident that (3) and (4) are logically equivalent to each other.

(i), (iii), (iv) are logically equivalent to each other, and are negation to (ii).

Why? I can't link it up together. Thanks in advance.

-

Start from your expression of (1), that is, $(p\wedge\neg q)\vee(q\wedge \neg p)$, and distribute $\wedge$ over $\vee$. This yields that (1) is the conjunction of $\neg q\vee\neg p$, $\neg q\vee q$, $p\vee\neg p$, and $p\vee q$. Two of these are tautologies hence (1) is equivalent to $(\neg q\vee\neg p)\wedge(p\vee q)$, which you showed to be equivalent to your (4). Hence (1) and (4) are equivalent.

The other cases you already proved.

-
Excellent~~~~~Thanks. – Yellow Skies Oct 1 '12 at 13:33

Your teacher is right, as you will see if you do truth-tables.

And the right-hand sides of your equivalences (1) and (3) are themselves equivalent, as you will see if you do truth-tables (or manipulate the rhs of (3) info DNF to match the rhs of (1)).

-
Well, this question is part of my mid-term exams, and technically, i only have 6 minutes to complete this! Thats a little too short for a truth table kinda... – Yellow Skies Oct 1 '12 at 13:24
Eh? You could have written truth-tables much faster than all those equivalences. Evaluating each of (1) to (4) on each of four lines can instantly be done in your head, so the only working is to write down 16 Ts or Fs! :-) – Peter Smith Oct 1 '12 at 13:51