Negating a predicate with a biconditional

3.2k Views Asked by At

Negate the following statement and make the negation appear immediately before the predicates

$$ \forall x \forall y(Q(x,y) \leftrightarrow Q(y,x)) $$

I did the following steps:

$$ \neg(\forall x \forall y(Q(x,y) \leftrightarrow Q(y,x))) $$ $$ \exists x \neg \forall y(Q(x,y) \leftrightarrow Q(y,x)) $$ $$ \exists x \exists y \neg(Q(x,y) \leftrightarrow Q(y,x)) $$

Now, I do not know what to do simply because of the notation. I assumed the following, knowing that: $$ \neg(a \leftrightarrow b) \equiv \neg a \leftrightarrow b $$

Would it be enough/correct to leave the following as the answer?

$$ \exists x \exists y (\neg Q(x,y) \leftrightarrow Q(y,x)) $$

1

There are 1 best solutions below

0
On BEST ANSWER

First, let's note a couple of equivalences: $$\begin{align} p\leftrightarrow q &\equiv (p\land q)\lor (\neg p \land \neg q) \tag{1} \\ &\equiv (p\to q)\land (q \to p). \tag{2} \end{align} $$ The negation of $p\leftrightarrow q$ is therefore $$\begin{align} \neg(p\leftrightarrow q) &\equiv \neg((p\to q)\land (q\to p)) \tag{by (2)} \\ &\equiv \neg(p\to q)\lor \neg(q \to p) \tag{De Morgan} \\ &\equiv (p\land \neg q)\lor (q \land \neg p) \tag{$\neg(A\to B)\equiv (A\land \neg B)$} \\ &\equiv p\leftrightarrow \neg q \tag{by (1)} \\ &\equiv \neg p\leftrightarrow q. \tag{by (1)} \\ \end{align}$$ Now recall that $\neg\forall \equiv \exists\neg$. Thus the negation of $\forall x \forall y\,(Q(x,y)\leftrightarrow Q(y,x))$ is $$\begin{align} \neg \forall x \forall y\,(Q(x,y)\leftrightarrow Q(y,x)) &\equiv \exists x \exists y\,\neg\,(Q(x,y)\leftrightarrow Q(y,x)) \\ &\equiv \exists x \exists y\,(\neg\, Q(x,y)\leftrightarrow Q(y,x)) \\ &\equiv \exists x \exists y\,(Q(x,y)\leftrightarrow \neg\, Q(y,x)). \end{align}$$