Logical Equivalence - A Proof with Predicates

Two statements involving quantifiers and predicates are logically equivalent if and only if they have the same truth values for every assignment of truth values, regardless which predicates are substituted into these statements and which domain is used.

If A and B are logically equivalent we write A ≡ B. Alternatively, A is logically equivalent to B if and only if A ↔ B is a tautology.

We can use this fact about the biconditional to prove two statements are logically equivalent

Example: Prove that ∀x(P(x)⋀Q(x)) ≡∀xP(x) ⋀∀xQ(x).

Proof:

To show that the statements are logically equivalent we need to show ∀x(P(x)⋀Q(x)) ↔ ∀xP(x) ⋀∀xQ(x) is a tautology.

So, we need to show
               ∀x(P(x)⋀Q(x)) → ∀xP(x) ⋀∀xQ(x) is a tautology
and         ∀xP(x) ⋀∀xQ(x) → ∀x(P(x)⋀Q(x)) is a tautology


First, we need to show∀x(P(x)⋀Q(x)) → ∀xP(x) ⋀∀xQ(x) is a tautology.

1.	∀x(P(x)⋀Q(x))	Premise
2.	P(x)⋀Q(x)	Universal Instantiation
3.	P(x)	Simplification
4.	Q(x)	Simplification
5.	∀xP(x)	Universal Generalisation
6.	∀xQ(x)	Universal Generalisation
7.	∀xP(x)⋀∀xQ(x)	Conjunction

Therefore, ∀x(P(x)⋀Q(x)) → ∀xP(x) ⋀∀xQ(x) is a tautology.

Similarly, we need to show∀xP(x) ⋀∀xQ(x) → ∀x(P(x)⋀Q(x)) is a tautology.

1.	∀xP(x)	Premise
2.	∀xQ(x)	Premise
3.	P(x)	Universal Instantiation
4.	Q(x)	Universal Instantiation
5.	P(x)⋀Q(x)	Conjunction
6.	∀x(P(x)⋀Q(x))	Universal Generalisation

Therefore, ∀x(P(x)⋀Q(x)) → ∀xP(x) ⋀∀xQ(x) is a tautology.

Therefore, ∀x(P(x)⋀Q(x)) ↔ ∀xP(x) ⋀∀xQ(x) is a tautology i.e.∀x(P(x)⋀Q(x)) ≡∀xP(x) ⋀∀xQ(x).