Proof that expression is a tautology

Question

I'm studying to my exam and I have some doubts.

The expression: $$¬(P \Leftrightarrow Q) \Leftrightarrow P \oplus Q$$

The objective is to know if it is a tautology. I don't know the result.

I made this:

$$ ¬[¬(P \oplus Q)] \Leftrightarrow P \oplus Q $$ $$ ¬[¬((P \land ¬Q) \lor (\lnot P \land Q))] \Leftrightarrow P \oplus Q $$ $$ ¬[(¬P \lor Q) \land (P \lor \lnot Q)] \Leftrightarrow P \oplus Q $$

and now I'm stuck.

Any help?

Answer 1

Since you only have two variables, I'd suggest writing down it as a table:

$$ \begin{array}{lcr} \mbox{P} & \mbox{Q} & \mbox{P}\leftrightarrow \mbox{Q} & \neg (\mbox{P}\leftrightarrow \mbox{Q}) & \mbox{P}\oplus \mbox{Q}\\ T & T & T & F & F\\ T & F & F & T & T\\ F & T & F & T & T\\ F & F & T & F & F\end{array}$$

Thus, for every boolean values of $P$ and $Q$ we get that $\neg(\mbox{P}\leftrightarrow \mbox{Q})$ has the same boolean value as $\mbox{P}\oplus \mbox{Q}$, which is what you wanted to prove.

Another proof for the logic equality, using "proof trees". We assumein contradiction that we can satisfy the following expression $\neg \left( \left(\neg\left(\mbox{P} \leftrightarrow \mbox{Q}\right) \right) \leftrightarrow \left( \mbox{P} \oplus \mbox{Q}\right)\right)$.

by rules of $\leftrightarrow$ we deduce that we can satisfy at least one of the following:

1. $ \left(\mbox{P} \leftrightarrow \mbox{Q}\right) \wedge \left( \mbox{P} \oplus \mbox{Q}\right)$

2. $ \left(\neg\left(\mbox{P} \leftrightarrow \mbox{Q}\right) \right) \wedge \left( \neg \left( \mbox{P} \oplus \mbox{Q}\right) \right)$

Let's start from $1.$:

By rules of $\wedge$ we know that the expression $\mbox{P}\leftrightarrow \mbox{Q}$ is satisfied and so is the expression $\mbox{P} \oplus \mbox{Q}$. By rules of $\leftrightarrow$ we know that, since $\mbox{P}\leftrightarrow \mbox{Q}$ is satisfied, we have two sub-options:

1.1. $\mbox{P}$ and $\mbox{Q}$ are both satisfied, meaning $\mbox{P}=\mbox{Q}=true$.

1.2. $\mbox{P}$ and $\mbox{Q}$ are both not-satisfied, meaning $\mbox{P}=\mbox{Q}=false$.

Now since $\mbox{P}\oplus \mbox{Q}$ is satisfied, by rules of $\oplus$ we know that one of the following must apply:

1.3. $\mbox{P}$ is satisfied and $\mbox{Q}$ isn't, meaning $\mbox{P}=true$ and $\mbox{Q}=false$.

1.4. $\mbox{P}$ is not satisfied and $\mbox{Q}$ is, meaning $\mbox{P}=false$ and $\mbox{Q}=true$.

You can clearly see that $1.3.$ contradicts both $1.2.$ and $1.1.$, thus making the option $1.3.$ impossible. But the happens for $1.4.$, making this option impossible as well. Thus, we have no possible option to choose, meaning we got a contradiction.

This method is called "proof trees" because the contradiction can be seen better when writing this down in a tree shape, when you have two (or more) options you divide the tree into two branches, each for every option, and when you have only one option - you keep growing this one branch you are on.

Now, going on option $2$ can be done very similarly, and I'll leave this to you so you can get a better feeling of this method.

Good luck on your exam! :)

Answer 2

Why don't you do a Truth-False table?

$$\begin{align*}&P&Q&&P&\iff Q&&\neg(P\iff Q)&P\rlap{\;\,\cdot}\vee Q\\ &T&T&&&T&&F&F\\ &T&F&&&F&&T&T\\ &F&T&&&F&&T&T\\ &F&F&&&T&&F&F\end{align*}$$

assuming that $\;P\rlap{\;\,\cdot}\vee Q\;$ is true iff only one of the two is true.

Then yes: both formulae are logic equivalent.