Equivalence of Predicate Formulas

In this class, We discuss the Equivalence of Predicate Formulas.

The reader should have prior knowledge of the validity of predicate inference examples. Click here.

We say that two predicate formulas are equal if their truth tables are the same.

We take a simple example understanding to prove the equivalence of formulas.

Example 1:

¬ (x) (A(x)) <=> ∃x ¬(A(x))

Take D: x will die

¬ (x) (D(x)) <=> ∃x ¬(D(x))

¬ (x) (D(x)) means not for all x “x will die”

The above statement says there exists at least one who will not die.

∃x ¬(D(x)) has the same meaning there exists at least one who will not die.

Example 2:

¬∃x (D(x)) <=> (x) ¬(D(x))

¬∃x (D(x)) means everyone will live forever.

(x) ¬(D(x)) will get the same meaning above.

Example 3:

(x) (A(x) ∧ B(x)) <=> (x)A(x) ∧ (x) B(x)

(x) (A(x) ∧ B(x)) will be true if for every x “A(x) and B(x)” has to be true.

(x)A(x) will be true if for every x A(x) has to be true.

(x) B(x) will be true if for every x, B(x) has to be true.

So, both are equal.

Example 4:

∃x(A(x) ∨ B(x)) <=> ∃xA(x) ∨ ∃xB(x)