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

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’

---

Detailed Video Solution: https://youtu.be/7DodebRTM10 

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

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

---

What if the relation \(r\) was empty? Would the same arguments (and the above answer) still hold good?

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

This is the example I want

---

The best ans !

---

superb ans sir, sir ans is perfect, no mistake in translating FOL into english
just in addition for more clarity , i would like to add 

P(t) : person t is in relationship 
r : it is set of boys in a class.
∃ = there exists = there is atleast one 

∃t∉r(P(t)) can be read as :
there exists a person who isnot belong to boys in class, is in relationship .
u can replace "exists" with "atleast one". u get ans as whatever sir written.

¬∃t∈r(¬P(t)) can be read as :
if u want to write in english ,whenever u see negation before quantifer, just apply to quantifer and read it.

there doesnot exist person in boys , who isnot in relationship.
ie. read as [there doesnot exist a boy in class who isnot in relationship.] 

exist = atleast one(>=1) , doesnot exist = !(>=1) = (<1) = 0 = no.

ie.  read as [there is no boy in class who isnot in relationship.] 

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?

Answer 5

it's a DM question !!

Option C , just bring negation inside .

Answer 6

The correct answer is C. III only.

Explanation:
The original expression ∀t∈r(P(t)) means "For all tuples tt in relation rr, the predicate P(t)is true."

Let's evaluate the options using logical equivalences:

• I. ¬∃t∈r(P(t)): This means "There does not exist a tuple in rr for which P(t) is true." This is the logical opposite of the original statement, so it is incorrect.

• II. ∃t∉r(P(t)): This means "There exists a tuple not in rr for which P(t) is true." This is completely unrelated to the original statement and is incorrect.

• III. ¬∃t∈r(¬P(t)): This means "There does not exist a tuple in rr for which P(t) is false." If there is no tuple in rr where P(t)P is false, it logically implies that P(t) must be true for all tuples in rr. This is logically equivalent to the original expression and is correct.

• IV. ∃t∉r(¬P(t): This means "There exists a tuple not in rr for which P(t) is false." This is also unrelated to the original statement and is incorrect.

Therefore, only expression III is equivalent.