4,887 views

Let $a(x, y), b(x, y,)$ and $c(x, y)$ be three statements with variables $x$ and $y$ chosen from some universe. Consider the following statement:

$\qquad(\exists x)(\forall y)[(a(x, y) \wedge b(x, y)) \wedge \neg c(x, y)]$

Which one of the following is its equivalent?

1. $(\forall x)(\exists y)[(a(x, y) \vee b(x, y)) \to c(x, y)]$
2. $(\exists x)(\forall y)[(a(x, y) \vee b(x, y)) \wedge\neg c(x, y)]$
3. $\neg (\forall x)(\exists y)[(a(x, y) \wedge b(x, y)) \to c(x, y)]$
4. $\neg (\forall x)(\exists y)[(a(x, y) \vee b(x, y)) \to c(x, y)]$

$(\exists x)(\forall y)[(a(x, y) \wedge b(x, y)) \wedge ¬c(x, y)]$

$\quad \equiv ¬(\forall x)¬(\forall y)[(a(x, y) \wedge b(x, y)) \wedge ¬c(x, y)]$
$\quad (\because (\exists x) F(x) = \neg \forall x \neg F(x))$

$\quad \equiv ¬(\forall x)(\exists y)¬[(a(x, y) \wedge b(x, y)) \wedge ¬c(x, y)]$
$\quad (\because (\forall x) F(x) = \neg \exists x \neg F(x)), \neg \neg F(x) = F(x))$

$\quad \equiv ¬(\forall x)(\exists y)[¬(a(x, y) \wedge b(x, y)) \vee c(x, y)]$

$\quad \equiv ¬(\forall x)(\exists y)[(a(x, y) \wedge b(x, y)) → c(x, y)]$

(C) choice.

by

Please explain Sir,how the first step is derived
That is Demorgan's law-

$$\exists x f(x) = \neg \forall x \neg f(x)$$

Also

$$\forall x f(x) = \neg \exists x \neg f(x)$$

In English we can say that if f(x) is true for all x, then there does not exist any x for which f(x) is not false. Similarly, if there exist an x for which f(x) is true, then it is not the case that f(x) is false for all x.
how 2nd step is calculated?

plz explain sir
it is the same Demorgan's law. See now..
Nice Explanation Arjun sir
edited
but @Arjun sir

Demorgan law is

¬∀xP(x) ≡ ∃x¬P(x)

¬∃xP(x) ≡ ∀x¬P(x)

then why did u write it as

∃xf(x)=¬∀x¬f(x)

@Arnab , ¬∀x¬f(x) = ∃x¬¬f(x) = ∃xf(x)(because by demorgan's law we are getting this)

srestha

what is now not in syllabus??

edited by

@akash

I thought it is logic programming

sorry misunderstood