Question

Which one of the following well-formed formulae in predicate calculus is NOT valid?
1. (∀x p(x) ⇒ ∀x q(x)) ⇒ (∃x ¬ p(x) ∨ ∀x q(x))
2. (∃x p(x) ∨ ∃x q(x)) ⇒ ∃x (p(x) ∨ q(x)) 
3. ∃x (p(x) ∧ q(x)) ⇒ (∃x p(x) ∧ ∃x q(x))
4. ∀x (p(x) ∨ q(x)) ⇒ (∀x p(x) ∨ ∀x q(x))

Answer 1

Correct Answer - Option 4 : ∀x (p(x) ∨ q(x)) ⇒ (∀x p(x) ∨ ∀x q(x))

Concept:

p ⇒ q means ¬p ∨ q

It means that p is true, and q is false, in that case this implication fails.

Explanation:

Consider, p(x) = x is a prime number

q(x) = x is a non-prime number

Option 1:

(∀x p(x) ⇒ ∀x q(x)) ⇒ (∃x ¬ p(x) ∨ ∀x q(x))   

In this, case after implication it becomes true and in case implication if there is true after implication then that predicate is valid. (∃x ¬ p(x) ∨ ∀x q(x)), this will become true by the example.

Option 2:

(∃x p(x) ∨ ∃x q(x)) ⇒ ∃x (p(x) ∨ q(x))   

This implication is also valid. In this, before implication it will become false. So, it is valid.

Option 3:

∃x (p(x) ∧ q(x)) ⇒ (∃x p(x) ∧ ∃x q(x))  

There exists a number x, which is both prime and non-prime which is false. A false statement can imply either true or false. So, it is valid.

Option 4:

∀x (p(x) ∨ q(x)) ⇒ (∀x p(x) ∨ ∀x q(x))  

Here, before implication, for all x, x is either prime or non-prime which is true.

After implication, for all x, x is prime or for all x, x is non-prime which is false. So, here a true statement implies a false statement which results in false. So, it is not valid.