retagged by
16,924 views
42 votes
42 votes

Which one of the following predicate formulae is NOT logically valid?

Note that $W$ is a predicate formula without any free occurrence of $x$.

  1. $\forall x (p(x) \vee W) \equiv \forall x \: ( px) \vee W$
  2. $\exists x(p(x) \wedge W) \equiv \exists x \: p(x) \wedge W$
  3. $\forall x(p(x) \rightarrow W) \equiv \forall x \: p(x) \rightarrow W$
  4. $\exists x(p(x) \rightarrow W) \equiv \forall x \:  p(x) \rightarrow W$
retagged by

9 Answers

2 votes
2 votes

To solve such questions consider domain to be (x1,x2)

keep in mind these two rules :

  1. ∀x is “ANDing” of all values in the domain because ∀x is only true if predicate is true for all the values of domain
  2. ∃x is “ORing” of all values in the domain because ∃x  is true if predicate is true for atleast 1 value of the domain

 

Option                       L.H.S                R.H.S L.H.S==R.H.S
A

∀x(p(x)∨W)

(p(x1)∨W)^(p(x2)∨W)

=(p1+w)(p2+w)

=p1p2+p1w+p2w+w

=p1p2+w(p1+p2+1)

=p1p2+w


∀x(px)∨W

=(p(x1)^p(x2))∨W

= p1p2+w

                  True
B

∃x(p(x)∧W)

=p1w+p2w

=w(p1+p2)


∃xp(x)∧W

=(p1+p2)w

             

True

C

∀x(p(x)→W)

=(p1→W)p2(→w)

=(p1’+w)(p2’+w)

=p1’p2’+p1’w+p2’w+w

=p1’p2’+w(p1’+p2’+1)

=p1’p2’+w

∀xp(x)→W

=(p1p2→w)

=(p1p2)’+w

=p1’+p2’+w

False
D

∃x(p(x)→W)

=(p1→W)+(p2→W)

=p1’+w+p2’+w

=p1’+p2’+w


∀xp(x)→W

=p1p2→W

=(p1p2)’+w

=p1’+p2’+w

 

True

So in only option C L.H.S !=R.H.S

Answer (C)

0 votes
0 votes

Option C is logically invalid. Hence option C is correct

0 votes
0 votes

Let domain of $x = \{x_1, x_2\}$

Option A:

$[\forall x (P(x) \lor W) \equiv \forall x P(x) \lor W]$

$LHS: \forall x (P(x) \lor W) =(P(x_1) + W) * (P(x_2) + W) =P(x_1)P(x_2) + W$

$ RHS: \forall x P(x) \lor W = P(x_1)*P(x_2) + W$

$\therefore LHS \equiv RHS$

 

Option B:

$[\exists x (P(x) \land W) \equiv \exists x P(x) \land W ]$

$LHS: \exists x (P(x) \land W) = (P(x_1).W)+(P(x_2).W) = \{P(x_1)+P(x_2)\}*W$

$RHS: \exists x P(x) \land W = \{P(x_1) + P(x_2)\} * W$

$\therefore LHS \equiv RHS$

 

Option C:

$[\forall x (P(x) \rightarrow W) \equiv \forall x P(x) \rightarrow W]$

$LHS: \forall x (P(x) \rightarrow W) = \{(P(x_1) \rightarrow W)*(P(x_2) \rightarrow W)\} = (P’(x_1) + W)(P’(x_2) + W) = P’(x_1)P’(x_2) + W$

$RHS: \forall x P(x) \rightarrow W = (P(x_1)P(x_2)) \rightarrow W = (P(x_1)P(x_2)’ + W = P’(x_1) + P’(x_2) + W$

$\therefore LHS \not \equiv RHS$

 

Option D:

$[\exists x (P(x) \rightarrow W) \equiv \forall x P(x) \rightarrow W]$

$LHS: \exists x (P(x) \rightarrow W) = \{(P(x_1) \rightarrow W) + (P(x_2) \rightarrow W)\} = P’(x_1) + W + P’(x_2) + W = P’(x_1) + P’(x_2) + W$

$RHS: \forall x P(x) \rightarrow W = (P(x_1)*P(x_2)) \rightarrow W = (P(x_1)P(x_2))’ + W =  P’(x_1) + P’(x_2) + W$

$\therefore LHS \equiv RHS$

Answer:

Related questions

9 votes
9 votes
3 answers
4
Arjun asked Feb 12, 2020
5,732 views
If $P = 3$, $R = 27$, $T = 243$, then $Q + S =$ ________$40$$80$$90$$110$