5.2k views

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 | 5.2k views
+3
option D
0

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

+5

Option (C) is also not valid...

Theorem:

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

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

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

+1

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

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.

edited by
+2
Yes , option D is wrong.But option C is also wrong, right ?
+3
no. C is valid.
+14
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...........}
+3
plz explain option (A).
0
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.
+1
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
+29

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
+1
thank for the answer @harveen singh

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

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.
+1 vote

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

OPTION D

 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

1
2