Logical Equivalences and Implications for Quantified Statements

LOGICAL EQUIVALENCES AND IMPLICATIONS FOR QUANTIFIED STATEMENTS

EQUIVALENCES AND IMPLICATIONS

Let A and B be any two predicate formulas defined over a common universe denoted by the symbol E. If, for every assignment of object names from the universe of discourse E to each of the variables appearing in A and B, the resulting statements have the same truth values, then the predicate formulas A and B are said to be equivalent to each over E.

If E is arbitrary, then we say that A and B are equivalent, that is A↔B.

The definition of implication can be extended in the same way. It is assumed that the same object names are assigned to the same variables throughout both A and B.

Four types of equivalences

"all true" {∀x, P (x)} ↔ {┐(Ǝx) (┐P (x))} "none false"

"all false" {(∀x), (P (x))} ↔ {┐(Ǝx) (P (x))} "none true"

"not all true" {┐(∀x), (P(x))} ↔ {(Ǝx)( ┐P(x))} "atleast one false"

"not all false" {┐(∀x), (┐P(x))} ↔ {(Ǝx) (P(x))} "atleast one true"

Valid formulas

A formula A is said to be valid in E written A in E if, forevery assignment of object names from E to the corresponding variables in A and for every assignment of statements to statement variables, the resulting statements have truth value T. We shall frequently use some of the equivalences and implications given in the following table.

Table 1.

Table 2.

Example 1. Show that (∀x) (P(x)) → (Ǝx) (P(x)) is a logically valid statement.

Solution :

If ∀x P(x) is true in some particular universe, then the universe has atleast one object c in it and P(b) is a true statement for every b in the universe. In particular P(c) must be true. Thus (Ǝx) (P(x)) is true. Therefore

 (∀x) (P(x)) → (Ǝx) (P(x)) is a valid satement.

Remark: If all men are giants, then some men are giants is not a valid statement. If the universe contains no men, then ∀x M(x) → G(x) is true, while (Ǝx) (M(x) ^G(x)) is false, where M(x) : x is a man, G(x): x is a giant. Thus

(∀x) (M(x) → G(x)) → (Ǝx) (M(x)) ^ G(x))

is not logically valid.

Example 2. Show that (∀x) (P(x)) V (∀x) (Q(x)) → (∀x) (P(x)) V Q(x)) is logically valid.

Solution :

Consider the case when (∀x) (P(x)) v (∀x) (Q(x)) is true. Since this is a disjunction of if-statements, one of the statements (∀x) (P(x)) and (∀x) (Q(x)) must be true.

If (∀x) (P(x)) is true, then for every object b in the universe, P(b) is true, and hence P(b), v Q(b) is true. Similarly when (∀x) (Q(x) is true, P(b) v Q(b) is true for every object b. In both the cases P(b) v Q(b) is true for all b in the universe.

Therefore

(∀x) (P(x) v Q(x)) is true and

(∀x) (P(x)) V (∀x) (Q(x)) → (∀x) (P(x) v Q(x))

is a valid statement.

Example 3. Show by counterexample

 (∀x) (P(x)) v Q(x)) → (∀x) (P(x)) V (∀x) (Q (x)) is not valid.

Solution: Now consider the following statement

(∀x) (P(x) v Q(x)),

where P() : x is an even integer,

Q(x) : x is a prime integer and the universe is {2, 4, 6, 8, 3, 7, 11}

For this universe, the statement (∀x) (P(x) v Q(x)) is true, but both (∀x) (P(x)) and (∀x) (Q(x)) are not true. So (∀x) (P(x) V (Q (x)) is true,

(∀x) (P(x)) V (∀x) (Q(x)) is not true. Thus

(∀x) (P(x) v Q(x) → (∀x) (P(x)) v (∀x) (Q(x))

is not a valid statement.

Example 4. Prove that the statements

(a) (∀x) (P(x)) → P(y)

(b) P(y) → (Ǝx) (P(x))

are valid statements. (y represents any one of the objects in the given universe)

Solution :

(a) The logical validity of the first statement follows immediately from the fact that if (∀x) (P(x))) is true, then P(b) is true for every object b in the universe and hence it is true for any specific object y in the universe.

(b) The logical validity of the second statement is a consequence of the meaning of the existential quantifier. The statement (Ǝx) (P(x)) is true if and only if there exists atleast one object in the universe for which P(x) is true. Therefore, if P(y) is true, then (Ǝx) P(x)) is true.