Logical equivalence

Subsection 1.3.4 Logical equivalence

When the domain of a propositional function only consists of a couple of elements we can rewrite the universal and existential quantification with the logical operations \(\land\) and \(\lor\text{.}\)

🔗

Example 1.3.4.1. Quantification with domain \(\{1,2,3\}\).

Consider a propositional function \(P\) with domain \(\{1,2,3\}\text{.}\) Then

\(\displaystyle \forall x\, P(x)=P(1)\land P(2)\land P(3)\)
🔗

🔗
\(\displaystyle \exists x\, P(x)=P(1)\lor P(2)\lor P(3)\)
🔗

🔗

🔗

Example 1.3.4.2. De Morgan with domain \(\{1,2\}\).

Let \(Q(x)\) be a propositional function with domain \(\{1,2\}\text{.}\) Then, by De Morgan’s laws 1.2.2.1, we have

\begin{equation*} \lnot\bigl(\forall x\,P(x)\bigr)= \lnot\bigl(P(1)\land P(2)\bigr) \equiv \lnot P(1)\lor \lnot P(2) = \exists x\,\lnot P(x) \end{equation*}

and

\begin{equation*} \lnot\bigl(\exists x\,P(x)\bigr)= \lnot\bigl(P(1)\lor P(2)\bigr) \equiv \lnot P(1)\land \lnot P(2) = \forall x\,\lnot P(x) \end{equation*}

🔗

Before we state and prove the theorems analogous to De Morgan’s laws for propositional functions we generalize the notion of logical equivalence.

🔗

Definition 1.3.4.3.

Two statements \(S\) and \(T\) involving predicates and quantifiers are logically equivalent, denoted \(S \equiv T\text{,}\) if they have the same truth value no matter which predicates are substituted into these statements and which domain is used.

🔗

Theorem 1.3.4.4. De Morgan’s laws for quantifiers.

Let \(P\) be a propositional function. Then the following logical equivalences hold.

\(\lnot \forall x \,P(x) \equiv \exists x\lnot P(x)\) .
🔗

🔗
\(\lnot \exists x \,P(x) \equiv \forall x\lnot P(x)\) .
🔗

🔗

🔗

Proof.

We prove the first statement and leave the proof of the second as an exercise.

🔗

We want to show

\begin{equation*} \lnot \forall x \,P(x) \equiv \exists x\lnot P(x). \end{equation*}

We just need to show that the left side and the right side have the same truth values, independent of what \(P\) or \(x\) actually is.

🔗

We first prove that if \(\lnot\left(\forall x\, P(x)\right)\) is true then \(\exists x\,\lnot P(x)\) is true

🔗

If \(\lnot\left(\forall x\, P(x)\right)\) is true then \(\forall x\, P(x)\) is false.

🔗

If \(\forall x\, P(x)\) is false there is a counterexample \(c\) in the domain of \(P\) such that \(P(c)\) is false.

🔗

If \(P(c)\) is false then \(\lnot P(c)\) is true.

🔗

So \(c\) is a witness for \(\exists x\,\lnot P(x)\text{,}\) which means that \(\exists x\,\lnot P(x)\) is true.

🔗

We now prove that if \(\lnot\left(\forall x\, P(x)\right)\) is false then \(\exists x\,\lnot P(x)\) is false.}

🔗

If \(\lnot\left(\forall x\, P(x)\right)\) is false then \(\forall x\, P(x)\) is true.

🔗

So \(P(x)\) is true for all \(x\) in the domain of \(P\text{.}\)

🔗

So \(\lnot P(x)\) is false for all \(x\) in the domain of \(P\text{.}\)

🔗

That is, there is no \(x\) in the domain of \(P\) such that \(\lnot P(x)\) is true.

🔗

So \(\exists x\,\lnot P(x)\) is false.

🔗

As the two propositions can only be true or false this proves that \(\lnot\left(\forall x\, P(x)\right) \equiv \exists x\,\lnot P(x)\text{.}\)

🔗

Example 1.3.4.5. No one is perfect.

Consider the statement “No one is perfect.” Translate it into a logical expression using predicates and quantifiers. Then use De Morgan’s laws to rewrite it.

🔗

The statement is that there does not exist a person that is perfect. Let \(P(x)\) be “\(x\) is perfect,” with domain the set of all people. Then the statement is \(\lnot \exists x \,P(x)\) . By De Morgan’s laws

\begin{equation*} \lnot \exists x \,P(x) \equiv \forall x\lnot P(x), \end{equation*}

which says that everyone is imperfect.

🔗

Example 1.3.4.6. Some raccoons have rabies.

Consider the statement “Some raccoons have rabies.”

Express the statement with a propositional function and a quantifier.
🔗

🔗
Give the negation of the expression.
🔗

🔗
Formulate the negation such that there is no negation to the left of the quantifier.
🔗

🔗
Express the negation in English.
🔗

🔗

🔗

Solution.

Let the domain of our propositional function be the set of all raccoons.
🔗

Let our propositional function \(F(x)\) be “\(x\) has rabies”.
🔗

Then “Some raccoons have rabies” can be expressed as \(\exists x\,F(x)\)
🔗

🔗
The negation of \(\exists x\,F(x)\) is \(\lnot \exists x\,F(x) \)
🔗

🔗
By De Morgan’s laws we have \(\lnot \exists x\,F(x) \equiv \forall x\, \lnot F(x)\) .
🔗

🔗
\(\forall x\, \lnot F(x)\) in English is “No raccoon has rabies.”
🔗

🔗

🔗

Example 1.3.4.7. Lewis Carroll.

Consider the three statements

All lions are fierce.
🔗

🔗
Some lions do not drink coffee.
🔗

🔗
Some fierce creatures do not drink coffee.
🔗

🔗

🔗

We write the three statements into logical expression using predicates and quantifiers.

🔗

Let \(L\) , \(F\text{,}\) and \(C\) be propositional functions with domain all creatures, where

\(L(x) \) is given by “\(x\) is a lion,”
🔗

🔗
\(F(x) \) is given by “\(x\) is fierce,” and
🔗

🔗
\(C(x) \) is given by “\(x\) drinks coffee,”
🔗

🔗

Then the three statements become:

\(\displaystyle \forall x \,(L(x) \implies F(x))\)
🔗

🔗
\(\displaystyle \exists x \,(L(x)\land\lnot C(x))\)
🔗

🔗
\(\displaystyle \exists x \,(F(x)\land\lnot C(x))\)
🔗

🔗

🔗

Suppose we know that the first two statements are true. Does this allow us to deduce the third statement ?

🔗

Suppose the first two statements are true. The second statement guarantees the existence of a creature, we’ll call this creature \(\bob\text{,}\) such that \(L(\bob)\) and \(\lnot C(\bob)\) are both true. Since \(L(\bob)\) is true, the conditional in the first statement tells us that \(F(\bob)\) is true. Since \(F(\bob)\) and \(\lnot C(\bob)\) are both true, \(\bob\) provides the example to show the third statement is true.

🔗

In other words, since some lions do not drink coffee, there must be a lion that does not drink coffee. Let’s call this lion \(\bob\text{.}\) Then since all lions are fierce, we have that \(\bob\) is fierce. Since \(\bob\) is fierce and does not drink coffee, we know that some fierce creatures do not drink coffee.

🔗

Prev Top Next