Two logical statements are equivalent if the values in their truth tables are all equal.
Example
Show \(\neg(P\Rightarrow Q)\) is equivalent to \(P\wedge\neg\mathcal{Q}.\)
Solution
To make the truth table for logical statement(s) we break them down into their constituent parts. For example \(\neg(P\Rightarrow Q)\) is made up from \({P}\) and \({Q}\) which are put together as \(P\Rightarrow Q\) and finally negated into \(\neg(P\Rightarrow Q)\).
In \(P\wedge\neg\mathcal{Q}\) we still have \({P}\) and \({Q}\), but we also need \(\neg\mathcal{Q}\) which together with \({P}\) makes \(P\wedge\neg\mathcal{Q}.\)
First we fill in the columns for the statements \({P}\) and \({Q}\), making sure we have every combination of true and false (i.e., every combination of their values).
\(\begin{array}{|c|c|c|c|c|c|c|}\hline P&Q&\neg Q&P\wedge\neg Q&P\Rightarrow Q&\neg(P\Rightarrow Q)\\\hline\text{т}&\text{т}&&&&\\\hline\text{т}&\text{т}&&&&\\\hline\text{т}&\text{т}&&&&\\\hline\text{F}&\text{т}&&&&\\\hline\text{F}&\text{F}&&&&\\\hline\end{array}\)
Then we fill in the rest of the columns using the tables for the other connectives (not, and, or, …).
\(\begin{array}{|c|c|c|c|c|c|c|c|}\hline P&Q&\neg Q&P\wedge\neg Q&P\Rightarrow Q&\neg(P\Rightarrow Q)\\\hline\text{т}&\text{т}&\text{F}&\text{F}&\text{т}&\text{F}\\\hline\text{т}&\text{F}&\text{т}&\text{т}&\text{F}&\text{т}\\\hline\text{F}&\text{т}&\text{F}&\text{F}&\text{т}&\text{F}\\\hline\text{F}&\text{F}&\text{т}&\text{F}&\text{т}&\text{F}\\\hline\end{array}\)
Since the columns for \(\neg(P\Rightarrow Q)\) and \(P\wedge\neg\mathcal{Q}\) are the same, the statements are logically equivalent.
Negating Statements
We negate a statement by using the following formulas/rules:
\(\begin{aligned}&1.\quad\neg\left(P\wedge Q\right)\Leftrightarrow\neg P\vee\neg Q\\&2.\quad\neg\left(P\vee Q\right)\Leftrightarrow\neg P\wedge\neg Q\\&3.\quad\neg\left(P\Rightarrow Q\right)\Leftrightarrow P\wedge\neg Q\\&4.\quad\neg\left(\left(\forall x\right)R(x)\right)\Leftrightarrow(\exists x)\neg R(x)\\&5.\quad\neg\left(\left(\exists x\right)R(x)\right)\Leftrightarrow(\forall x)\neg R(x)\end{aligned}\)
Note that in negation, we switch and \(\text{(人)}\) and or \(\left(\wedge\right)\) and for every \(\mathrm{(V)}\) and there exists \(\text{(日)}\).
Example
Show the negation of
\(\left(\forall x\in F\right)\left[x\neq0\Rightarrow\left(\exists y\in F\right)\left(y\neq0\wedge x\cdot y=1\right)\right]\)
and simplify so that the formula does not include the negation symbol \(\text{¬}\).
Solution
\(\begin{gathered}
\text{} \neg\left\{\left(\forall x\in F\right)\left[x\neq0\Rightarrow\left(\left(\exists y\in F\right)\left(y\neq0\wedge x\cdot y=1\right)\right)\right]\right\} \\
\left.\left(\exists x\in F\right)\neg\right|x\neq0\Rightarrow\left(\left(\exists y\in F\right)\left(y\neq0\wedge x\cdot y=1\right)\right)] \\
\left.\left.\left(\exists x\in F\right)\right|x\neq0\wedge\neg\left(\left(\exists y\in F\right)\left(y\neq0\wedge x\cdot y=1\right)\right)\right] \\
\left.\left(\exists x\in F\right)\right|x\neq0\wedge\left(\left(\forall y\in F\right)\neg\left(y\neq0\wedge x\cdot y=1\right)\right)] \\
\left(\exists x\in F\right)\left[x\neq0\wedge\left(\left(\forall y\in F\right)\left(y=0\vee x\cdot y\neq1\right)\right)\right]
\end{gathered}\)
Example
Compute the negative of \(\left(\exists x\in\mathbb{R}\right)\left(\left(\left(\forall y\in\mathbb{R}\right)\left(y^2\neq x\right)\right)\lor\left(x\geq0\right)\right)\) without using the \(\text{¬}\) symbol .
Solution
\(\begin{aligned}
&\lnot\left\{\left(\exists x\in\mathbb{R}\right)\left(\left(\left(\forall y\in\mathbb{R}\right)\left(y^2\neq x\right)\right)\lor\left(x\geq0\right)\right)\right\} \\
&\left(\forall x\in\mathbb{R}\right)\lnot\left(\left(\left(\forall y\in\mathbb{R}\right)\left(y^2\neq x\right)\right)\lor\left(x\geq0\right)\right)\\
&\left(\forall x\in\mathbb{R}\right)\left(\neg\left(\left(\forall y\in\mathbb{R}\right)\left(y^2\neq x\right)\right)\wedge\neg\left(x\geq0\right)\right) \\
&\left(\forall x\in\mathbb{R}\right)\left(\left(\left(\exists y\in\mathbb{R}\right)\neg\left(y^2\neq x\right)\right)\wedge\left(x<0\right)\right) \\
&\left(\forall x\in\mathbb{R}\right)\left(\left(\left(\exists y\in\mathbb{R}\right)\left(y^2=x\right)\right)\wedge\left(x<0\right)\right)
\end{aligned}\)