The Gateway to Computer Science Excellence
+42 votes

Which one of the following well-formed formulae in predicate calculus is NOT valid ?

  1. $(\forall _{x} p(x) \implies \forall _{x} q(x)) \implies (\exists _{x} \neg p(x) \vee \forall _{x} q(x))$
  2. $(\exists x p(x) \vee \exists x q (x)) \implies \exists x (p(x) \vee q (x))$
  3. $\exists x (p(x) \wedge q(x)) \implies (\exists x p(x) \wedge \exists x q(x))$
  4. $\forall x (p(x) \vee q(x)) \implies (\forall x p(x) \vee \forall x q(x))$
in Mathematical Logic by Boss (41.9k points)
edited by | 6.2k views
option D

why this show in many question  [Math Processing Error] ??


Option (C) is also not valid...


  1. ∀x[P(x) ∧ Q(x)] ≡ (∀xP(x) ∧ ∀xQ(x))
  2. ∀x[P(x) ∨ Q(x)] is not ≡ (∀xP(x) ∨ ∀xQ(x))
  3. ∃x[P(x) ∧ Q(x)] is not ≡ (∃xP(x) ∧ ∃xQ(x))
  4. ∃x[P(x) ∨ Q(x)] ≡ (∃xP(x) ∨ ∃xQ(x))

plz see this link

exactly! option (c) is also not valid @lubna

@rajoramanoj  Your Internet Slow Try To Again Refresh Page (Some Applects,Scripts  Not Properly running In your Browser ) 


@hacker16  @Lubna Khan  your equivalence relations are correct..

But there is  difference between validity of equivalence ($\equiv or \Leftrightarrow$)   and implication( $\Rightarrow$).

option C is valid.

4 Answers

+46 votes
Best answer

Here, (D) is not valid

Let me prove by an example

What (D) is saying here is:

For all $x$ ( $x$ is even no or $x$ is odd no ) $\implies$ For all $x$( $x$ is even no ) or For all $x$ ( $x$ is odd no)


If every $x$ is either even or odd, then every $x$ must be even or every $x$ must be odd.

If our domain is the set of natural numbers LHS is true but RHS is false as not all natural numbers are even or odd.

Answer is (D).

by Boss (41.9k points)
edited by
Yes , option D is wrong.But option C is also wrong, right ?
no. C is valid.
C) there exist x (x divisible by 2 and x divisible by 3) -> there exists x (x divisible by 2) and there exists x(x divisible by3)

for eg. left side contains set {6,12,18.............}

right side will also contain {6,12...........}
plz explain option (A).
but in option c if we assume that P(x) is positive and Q(x) is negative then in the option c then in the option c the left hand side is coming to be false while the right hand side is coming to be true because

∃x(P(x)⋀Q(x))) is false because here there  exits a x where it is positive and negative simultaneously is false but in the right hand side portion

∃x P(x)  ⋀ ∃x Q(x) is true because there exits a x ie the number is positive and there exits a x ie the number is negative.
i guess its something like this
      lets take left-side as p and right side as q

now that arrow inbetween shows conditional operator then answer will be false only if q is false

so even in your +ive and -ive number assumption  only option d will be false

According to Rosen-

We can distribute a universal quantifier over a conjunction only.

We can distribute a existential quantifier over a disjunction only.

But here we are not discussing about Logical equivalence.

The question is about Implication.. So in questions like these should we always consider examples?

For ex- In this question option a and b are 100% valid.

for option c and d. Let take two statements

Statement 1- P(x) x is a even number

Statement 2- P(y) y is a odd number.

Option C- LHS- For All x, x is a even no and a odd number (FALSE) So P->Q is true if P is false. Hence it is valid

Option D-LHS- For  all x, x is either a even no or a odd number(True) RHS- For all x, x is a even number or for all x, x is a odd number which is false. So P->Q is false if P is true and Q is false. Hence this is not valid (Because to be valid all the sets should be valid and here we found a non satisfying set.)

Lecture 4- Discrete Structures by Kamala MAM Nptel
thank for the answer @harveen singh

 what is the diference between Implication & Logical equivalence

Let $P$ and $Q$ be two logical expressions.

1. Equivalence : $P \equiv Q $ means $P \iff Q$ i.e. $(P \implies Q)\wedge (Q \implies P)$

2. Implication : $P \implies Q$ only.
+10 votes

lets take there are two elements x1 and x2 in the UOD.

So ∀xp(x) = p(x1) ^ p(x2) so converting into digital logic formula p1.p2 and ∃xp(x)=p1+p2

so lets check the options


(∀xp(x)⟹∀xq(x))⟹(∃x¬p(x)∨∀xq(x)) = (p1.p2 => q1.q2) =>((~p1+~p2)+(q1.q2)

A=(p1.p2 => q1.q2)


so now validate the formula to show if there is any case where we get A=True and B=False which is not possible now you can said it is a valid formula carry with rest of the options in similar way out of which you with get a True & False combination for option D 

by (267 points)
+7 votes
A valid proposition is one which is a tautology.

A) Here, both sides are equivalent. Use p -> q = ¬p v q to verify. Hence, is is valid.

B) The existential quantifier is distributive over disjunction. Hence, both sides are equivalent and thus, the statement is valid.

C) Here, both sides are not equivalent since existential quantifier is not distributive over conjunction. But, it is still valid because if left side is true, then there exists an x=a such that both p(a)=T and q(a)=T. Applying existential generalisation with a as the particular element in the domain of x, the right side is true.

D) When left side is true, the right side can be false. If left side is true, this means for every x, p(x) v q(x) = T. But at the same time, the right side can be false because both p(x) and q(x) can be false for different values of x.

So, D is invalid.
by Active (1.8k points)
+2 votes

We can also prove this by making T or F combination & the trick we've to apply is T->F which is F i.e not valid.

for check validity it's easy to prove not valid by 1 combination(T->F) rather than proving valid by 3 combinations(T->T, F->T, F->F).

option A

  X P(X) Q(X)
X1 T T
X2 T T

So, using this combination we can't get T -> F, i.e option A is valid.

always choose a combination such that LHS of  implication will be T & using that combination check whether RHS will be F or not.

option B

X P(X) Q(X)
X1 T F
X2 F T

We can't get T -> F

option C

X P(X) Q(X)
X1 T T
X2 F F

NO T -> F


X P(X) Q(X)
X1 T F
X2 F T

So, here we get T -> F  i.e it's not a valid one

by Active (4k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,366 answers
105,265 users