edited by
16,706 views
69 votes
69 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))$
edited by

6 Answers

Best answer
68 votes
68 votes

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)

OR

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).

edited by
20 votes
20 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

1)

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

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

B=((~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 

13 votes
13 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.
10 votes
10 votes

$A)$

$(\forall _{x} p(x) \implies \forall _{x} q(x)) \implies (\exists _{x} \neg p(x) \vee \forall _{x} q(x))$

$(\forall _{x} p(x) \implies \forall _{x} q(x)) \implies (\neg\forall _{x}  p(x) \vee \forall _{x} q(x))$

$(p1p2\rightarrow q1q2)\rightarrow \neg(p1p2)+q1q2$

$\neg(p1p2)+q1q2\rightarrow \neg p1+\neg p2+q1q2$

$(\neg p1+\neg p2+q1q2)\rightarrow (\neg p1+\neg p2+q1q2)$

Valid

 

$D)$

$\forall x (p(x) \vee q(x)) \implies (\forall x p(x) \vee \forall x q(x))$

$(p1+q1).(p2+q2)\rightarrow p1p2+q1q2$

$(p1p2+p1q2+p2q1+q1q2)\rightarrow$ $(p1p2+q1q2)$

Set RHS : $(p1p2+q1q2)$ as False, and try to make LHS true. If you can make LHS true by trying different possibilities then this wff is NOT valid.  

If you consider $1.$ case of $p1p2\ \&\ 2.$ case of $q1q2$ then LHS can be made TRUE and hence $D)$ is not VALID

 

 

 

 

 

Similarly try for other 2 options.

Correct Answer : D

Answer:

Related questions

100 votes
100 votes
11 answers
1
Akash Kanase asked Feb 12, 2016
19,672 views
Consider the following expressions:$false$$Q$$true$$P\vee Q$$\neg Q\vee P$The number of expressions given above that are logically implied by $P \wedge (P \Rightarrow Q)$...
88 votes
88 votes
5 answers
2