How does one tell if logical expressions are equivalent?

Question

How do I check if these expressions are equivalent?

• ∀a,b [P(a) ∧ ¬R(a) ∧ S(b)] → G(a,b)

• ∀a [(P(a) ∧ ¬R(a)) → (∀b [S(b) → G(a,b)])]

Answer 1

Expressions are equivalent if they can be related with an if and only if connection.

One way to check if they are equivalent is to use a tree proof generator. Putting these expressions into such a tool will also require one to write a well-formed formula eliminating any ambiguity.

Here is the result of the tool showing that the expressions are equivalent as I entered them:

A tree proof attempts to prove the result by negating it, transform the negated statement using equivalences and explore all available branches. If one of the branches did not lead to an "x", a contradiction, then that branch could be used to form a countermodel. In this case all branches closed. No contradiction was found and so the original equivalence was valid.

Another way to check that the two statements are equivalent is to find a natural deduction proof of the equivalence.

---

Tree Proof Generator. https://www.umsu.de/logik/trees/

Answer 2

The first observation is that moving the ∀b quantifier in the second formula to the front is unproblematic since we can safely move a quantifier from the right-hand side of an implication to the outside provided we don't bind any variables that were free before, which is the case here, so

∀a,b [(P(a) ∧ ¬R(a) ∧ S(b)) → G(a,b)]           (first formula)

is equivalent to

∀a,b [(P(a) ∧ ¬R(a)) → (S(b) → G(a,b))]         (second formula with ∀b moved to the front)

Now we can imagine the quantifers away and also abstract away from the structure of the subformulas -- since the only difference between the two formulas lies in the connectives while the predicates between the connectives are all the same, identity or difference in the truth values of the two formulas does not depend on the predicate logical interpretation of the quantifiers or predications but only on the syntactic structure of the two formulas, so it is permissible for the sake of the equivalence check to replace the predications by simple propositional letters while leaving the general structure intact:

(P ∧ ¬R ∧ S) → G           (first formula with the predications replaced by propositional variables)

(P ∧ ¬R) → (S → G)         (second formula with the predications replaced by propositional variables)

To further simplify, we can turn the identical subformulas P ∧ ¬R into one propositional variable Q so only have the relevant differences:

(Q ∧ S) → G           (first formula further simplified)

Q → (S → G)           (second formula further simplified)

The two formulas have the same syntactic structure as the original ones, just heavily simplified by abstracting away over the parts that are identical anyway -- but this simplification is all we need, as the rest makes no difference to the question of equivalence.

And now that we have two propositional formulas, we can simply put that into a truth table and check whether the respective columns of the two formulas are identical:

G   Q   S   (Q ∧ S) → G    ≡    Q → (S → G)
F   F   F         T        ✓        T
F   F   T         T        ✓        T
F   T   F         T        ✓        T
F   T   T         F        ✓        F
T   F   F         T        ✓        T
T   F   T         T        ✓        T
T   T   F         T        ✓        T
T   T   T         T        ✓        T

As you can say, the two formulas have the same truth values in all rows, so they are equivalent. In general, we have an equivalence between statements of the form (A ∧ B) → C) and A → (B → C): Stating "If A and B hold, then C is true" is equivalent to stating "If A holds, then if B holds, then C is true. Since the two formulas are jut more complex instances of this scheme, they are equilvalent.

Reminder: This procedure -- replacing the predicate logical subformulas by propositional variables and then simply using a truth table -- only works because the two formulas only differ in their syntactic (propositional) structure and not in their predications, so we don't need the complicated ontology of predicate logical interpretation to check their equivalence. We can not in general employ truth tables for predicate logic, as there may be differences in the structure of the predications. But for the particular case of the pair of formulas in question, this way of argumentation works just fine.