GATE CSE 2008 | Question: 15

Question

Which of the following tuple relational calculus expression(s) is/are equivalent to $\forall t \in r \left(P\left(t\right)\right)$?

1. $\neg \exists t \in r \left(P\left(t\right)\right)$
2. $\exists t \notin r \left(P\left(t\right)\right)$
3. $\neg \exists t \in r \left(\neg P\left(t\right)\right)$
4. $\exists t \notin r \left(\neg P\left(t\right)\right)$
   • A. I only
   • B. II only
   • C. III only
   • D. III and IV only

Comments

It means for all t which is belongs to r p (t) is true...so it means there exist no t which is belongs to r for which p (t) is false....so option 3 is correct...

Option 2 saying that there exist t which is not belongs to r for which p (t) is true...so this might valid may be not ,so here we cant say anything explicitly about the truthness of the statememt..so its not the correct option....similarly  option 4 and 1 is not correct  option ..

---

question says for all tuple t in r, t satisfies the condition.
It is equivalent to saying that there not exist any tuple t in r which do not satisfies the condition.

---

Crucial point : A ∉ B = A ∈ B’

Answer 1

Only III is correct.
The given statement means for all tuples from r, P is true. III means there does not exist a tuple in r where P is not true. Both are equivalent.

IV is not correct as it as saying that there exist a tuple, not in r for which P is not true, which is not what the given expression means.

Comments

Okay sure

---

no, it is safe.

apply TRUE, FALSE TO THIS QUERY.

THIS EXPRESSION (~EMPLOYEE) IS FALSE IN EVERY CASE.

HENCE THE REMAINING EXPRESSION HAS TO BE TRUE, NOW IF THE EMPLOYEE IS MAN. THEN THE WHOLE EXPRESSION BECOMES TRUE AS THEY ARE JOINED BY BINARY OR OPERATION

BUT IF THE EMPLOYEE IS FEMALE THEN SHE CAN NOT BE THE SUPERVISOR

OTHER HAND, IF THE EMPLOYEE IS MALE THEN NO NEED TO CHECK OTHER CONDITIONS.

---

dont understand the belongs to r thing, never seen it in discrete logic

Answer 2

∀t∈r(P(t)):  All boys in the class are in a relationship.
 

I) ¬∃t∈r(P(t)) : There is not a single boy in the class who is in a relationship.  (X)
II) ∃t∉r(P(t)) : There is at least one boy in the class who does not belong those boys who are in a relationship. (X)
III) ¬∃t∈r(¬P(t)) : There is not a single boy in the class who is not in a relationship. (Matches the qsn)
IV) ∃t∉r(¬P(t)) : There is at least one boy in the class who does not belong to those boys who are not in a relationship. (X)

Only IV is little bit tricky. Please read again carefully.  We need "all boys" instead of "at least one" to match our original qsn.
So only option III is true.
Hence  C is the answer. 

Comments

Such a nice reference! :)

---

simple and clear

---

This is the example I want

Answer 3

(IV) is incorrect as Arjun sir have explained.Above is simplification of given expression to (III).

Note that, ∀_x∈t (P(x))=∀_x (x∊t-->P(x))

                ∃_x∈t (P(x))= ∃_x (x∊t^P(x))

Comments

@jatin saini @Arjun Sir,

Are these 2 rules? 

∀x∈t (P(x))=∀x (x∊t-->P(x))

∃x∈t (P(x))= ∃x (x∊t^P(x))

Answer 4

Concept:- A statement is equivalent to its double negation.

i.e. x=~(~x)

Similarly compare below expression with above expression.

$\forall t \in r \left(P\left(t\right)\right)$ = $\neg$ ( $\exists t \in r \left(\neg P\left(t\right)\right)$ )

Hence C is Ans.

Comments

Why no negation on belongs to symbol?