1
$\begingroup$

From Rosen's Discrete Math textbook, where they define logical equivalence involving quantifiers:

enter image description here

"Statements involving predicates and quantifiers are logically equivalent if and only if they have the same truth value no matter which predicates are substituted into these statements and which domain of discourse is used for the variables in these propositional functions. We use the notation S ≡ T to indicate that two statements S and T involving predicates and quantifiers are logically equivalent."

"Determine whether ∀x(P(x) → Q(x)) and ∀xP(x) → ∀xQ(x) are logically equivalent. Justify your answer."

  1. Does the logical equivalence $$∀x(P(x) ∧ Q(x)) ≡ ∀xP(x) ∧ ∀xQ(x)$$ say that $$P(a) ∧ Q(a) ≡ P(a) ∧ Q(b),$$ where a & b are elements of some domain S (here I'm under the assumption that the domain of LHS must match the domain Of RHS), is possible?

  2. Must the domain of $P(x)$ match the domain of $Q(x)?$

  3. Is it correct to assert the logical equivalence $$2 + 2 = 4 ≡ 3 + 2 = 5,$$ since in "all conditions" they have same truth value, since both are always true statements?

  4. Does $$\forall x(P(x) \leftrightarrow Q(x))$$ mean that $$P(x_{1}) ≡ Q(x_{1}), \dots , P(x_{n}) ≡ Q(x_{n}),$$ where ${x_{1}, \dots, x_{n} }$ are members of the domain?

$\endgroup$
2
  • $\begingroup$ As already said, every interpretation I has its own domain D. To prove the equiv above, you have to show that in every I the two sides of the bi-conditional have the same truth value. Thus, considering a fixed I, the domain D is fixed and you have to use it for the entire formula. $\endgroup$ Commented May 22 at 5:55
  • $\begingroup$ This does not mean that every variable will have the same value, but in the proof above the argument is. Let $I$ an interpretation whatver with domain $D$ and let $a$ an element whatever of the domain. To say that the LHS is true means that $P(a) ∧ Q(a)$ is true and thus we have that $P(a)$ is true and $Q(a)$ is true. But $a$ is an element whatever: thus, by Generalization (this is the key−point) $\forall x P(x)$ is true and $\forall x Q(x)$ is true. And vice-versa. $\endgroup$ Commented May 22 at 12:17

1 Answer 1

2
$\begingroup$
  1. Is it correct to assert the logical equivalence $$2 + 2 = 4 \quad≡\quad 3 + 2 = 5,$$ since in "all conditions" they have same truth value, since both are always true statements?

Although the left and right statements are equivalent in arithmetic, they are not equivalent when the non-logical binary operator + is reinterpreted to mean "if both inputs are positive then output 4; otherwise output 5"; therefore, they are not logically equivalent statements. Logical equivalence is a very strong ask: the statements must have the same truth value regardless of interpretation.

  1. Does the logical equivalence $$∀x(P(x) ∧ Q(x)) \quad≡\quad ∀xP(x) ∧ ∀xQ(x)$$

In other words: $$∀x(P(\color\red p) ∧ Q(\color\red p)) \quad≡\quad ∀\color{cyan} qP(\color{cyan} q) ∧ ∀\color{brown} rQ(\color{brown} r).$$

say that $$P(a) ∧ Q(a) \quad≡\quad P(a) ∧ Q(b)$$ is possible?

Not at all. You might be alternately forgetting several things: doesn't claim that both sides are true, it asserts a relationship between the two sides, and this relationship needs to hold very strongly, as explained above.

Incidentally, has other common meanings besides logical equivalence.

  1. Does $$\forall x(P(x) \leftrightarrow Q(x))$$ mean that $$P(x_{1}) ≡ Q(x_{1}),\dots , (x_{n}) ≡ Q(x_{n})\;?$$

No, the former just means that $$P(x_{1}) ↔ Q(x_{1}),\dots , P(x_{n}) ↔ Q(x_{n});$$ no logical equivalence is being asserted.

  1. Must the domain of $P(x)$ match the domain of $Q(x)?$

Within a single discourse context, it doesn't make sense for statements to be having separate domains of discourse.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .