Question

Establish these logical equivalences, where x does not occur as a free variable in A. Assume that the domain is nonempty.

$$\begin{gathered} \mathbf{\left(}\mathbf{a}\mathbf{\right)}\mathbf{}\mathbf{\forall }\mathbf{x}\mathbf{\left(}\mathbf{P}\mathbf{\right(}\mathbf{x}\mathbf{)}\mathbf{\to }\mathbf{A}\mathbf{)}\mathbf{\equiv }\mathbf{\exists }\mathbf{xP}\mathbf{\left(}\mathbf{x}\mathbf{\right)}\mathbf{\to }\mathbf{A} \\ \mathbf{\left(}\mathbf{b}\mathbf{\right)}\mathbf{}\mathbf{\exists }\mathbf{x}\mathbf{\left(}\mathbf{P}\mathbf{\right(}\mathbf{x}\mathbf{)}\mathbf{\to }\mathbf{A}\mathbf{)}\mathbf{\equiv }\mathbf{\forall }\mathbf{xP}\mathbf{(}\mathbf{x}\mathbf{\to }\mathbf{A} \end{gathered}$$

Short answer

(a) In all cases, the two propositions have the same truth value.

(b) In all cases, the two propositions have the same truth value.

Step-by-step solution

Solution

By the definition 3, statements involving predicates and quantifiers are logically equivalent if and only if they have the same truth value no matter which predicts are substituted into these propositional functions.

We use the notation $S\equiv T$to indicate that two statements S and T involving predicates and quantifiers are logically equivalent.

By definition 5, let p and q be propositions. The conditional statement $p\to q$is the proposition “if p , then q ”, the conditional statement $p\to q$ is false when p is true and q is false, and true otherwise.

We can established these equivalences by arguing that one side is true if and only if the other side is true.

Let’s explain that:

(a) ∀x(P(x)→A)≡∃xP(x)→A

Suppose that A is true. Then by definition 5, for each x,$P\left(x\right)\to A$is true; therefore, the left hand side is always true in this case.

Similarly, the right hand side is always true in this case.

For the second sub case, suppose that P(x) is true for some x . Then for that x, $P\left(x\right)\to A$is false, so the left hand side is false.

The right hand side is also false, because in this sub case $\exists xP\left(x\right)$is false.

Thus, in all case, the two propositions have the same truth value.

(b) ∃xP(x)→A)≡∀xP(x)→A

If $\exists xP\left(x\right)A$is true, then both sides are trivially true, because the conditional statements has true conclusions.

If A is false, then there are two sub cases:

If P(x) is false for some x, then $P\left(x\right)\to A$ is vacuously true for that x, so the left-hand side is true.

The same reasoning shows that the right-hand side is true, because in this sub case$\forall xP\left(x\right)$is false.

For the second sub case, suppose that P(x) is true for every x.

Then, for everyx,$P\left(x\right)\to A$ is false, so the left-hand side is false (there is no x marking the conditional statement true).

The right hand side is also false, because it is a conditional statement with a true hypothesis and a false conclusion.

Thus, in all cases, the two propositions have the same truth value.