GATE IT 2004 | Question: 3

Question

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?

• A. $(\forall x)(\exists y)[(a(x, y) \vee b(x, y)) \to c(x, y)]$
• B. $(\exists x)(\forall y)[(a(x, y) \vee b(x, y)) \wedge\neg c(x, y)]$
• C. $\neg (\forall x)(\exists y)[(a(x, y) \wedge b(x, y)) \to c(x, y)]$
• D. $\neg (\forall x)(\exists y)[(a(x, y) \vee b(x, y)) \to c(x, y)]$

Comments

https://youtu.be/s41PLmHGf08?list=PLIPZ2_p3RNHidhFvyKH4U_VE1rFAyvG8U&t=4449

Answer 1

$(\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.

Comments

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

---

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)

please clear my doubt sir

---

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

---

@akash

I thought it is logic programming

like this https://gateoverflow.in/958/gate2003-71

sorry misunderstood

---

@Arjun sir, do we have to check the logical equivalence for each option like this? because, then it will consume quite a good amount of time. Any other quick way to figure it out?

---

got it

Answer 2

.

Answer 3

Question can solve with help to small  concept :

p  is equivalent to q if and only if  p implies q is true and q implies p is true 

now how to approch , 

first take p implies q try  to make it false ( true implies false is false )  if possi s sto there  go for next  if not possible then now check for q-> p it is also valid then as both side valid therefore we can conclude that equiv to  q