Showing logical equivalence for predicates?

74 Views Asked by At

Let $P$, $Q$, and $R$ be predicate symbols and $x$ be the predicate variable.

Do I use the fact that $$\forall x, Q(x)\wedge R(x)\equiv \forall x, R(x)\wedge Q(x)$$ or the fact that $$\exists x, Q(x)\wedge R(x)\equiv \exists x, R(x)\wedge Q(x)$$ to show that $$\forall x,(P(x) \leftrightarrow (R(x)\wedge Q(x)) \equiv \forall x,(P(x) \leftrightarrow (Q(x)\wedge R(x)) \;?$$

For propositions $p, q,$ and $r$, we can use the fact that $q\wedge r \equiv r\wedge q$ to show that $$p \leftrightarrow (q \wedge r) \equiv p \leftrightarrow (r \wedge q)$$

We can "substitute" $q \wedge r$ for $r \wedge q$ since they're logically equivalent. But since predicates aren't propositions, they don't have a truth value until concrete values are substituted in place for the predicate variable(s). So I'm not sure if we can say that $$Q(x) \wedge R(x) \equiv R(x) \wedge Q(x)$$ since they're not propositions. From what I know, predicates only become propositions when we substitute the predicate variable(s) for some concrete value(s) or use quantifiers on the predicates. That's why I was confused on whether to use the fact that $\forall x, Q(x)\wedge R(x)\equiv \forall x, R(x)\wedge Q(x)$ or the fact that $\exists x, Q(x)\wedge R(x)\equiv \exists x, R(x)\wedge Q(x)$ to show that $$\forall x,(P(x) \leftrightarrow (R(x)\wedge Q(x)) \equiv \forall x,(P(x) \leftrightarrow (Q(x)\wedge R(x))$$

I want to "substitute" $R(x)\wedge Q(x)$ with $Q(x)\wedge R(x)$ but since neither $R(x)$ nor $Q(x)$ are propositions, I turn them into propositions using quantifiers which gave me the two quantified statements that I showed earlier and I want to "substitute" either one with $R(x)\wedge Q(x)$, but I'm not sure which one to use.

It could be that I'm getting this whole idea incorrect. I'd appreciate to be corrected. Thanks.

1

There are 1 best solutions below

2
On BEST ANSWER

Since the relevant logically equivalent part is inside the scope of a quantifier, you would use the fact that $Q(x) \land R(x)$ and $R(x) \land Q(x)$ are equivalent for any assignment of $x$, and hence also under the universal quantification. Something along the lines of "Since $v(x)$ was arbitrary, the above holds for all assignments, therefore ... $\forall x (\ldots) $ ...".