The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+26 votes

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)$
    1. I only
    2. II only
    3. III only
    4. III and IV only
asked in Databases by Veteran (59.9k points) | 2.9k views
Change the category of this question from Mathematical Logic to Databases.
Thanks :)
I think it belongs to both Mathematical Logic & Databases. Keep Database tag, add Mathematical logic too !
relational calculus implies that..

I understand the meaning of the individual symbols used in this question, but I am not able to clearly interprete their meaning in the way they are used.

1. For example in tuple relational calculus we have ∀t (predicates) or we may have single predicate ∀t P(t). But I am first time seeing "belongs to ∈" symbol following quantifier. Somehow I feel it should be ∀t (r(P(t)))

2. Next we use r(t) in dbms to say tuple t belongs to relation r. But I never saw predicate used inside r(). Should it be "r(t) ^ P(t)" to make it more sensible or better to say to follow more standard usage?

So the whole expression should be ∀t (r(t) ^ P(t))

Am I correct on these? Or I am just plain wrong in understanding the usage of these symbols?

what is the exact meaning of third statement??

Let predicate $P(t)$ means "student is intelligent"

't' is some person and as for our predicate domain is 'student' so we'll talk when this person belongs to domain 'student'.

$\forall t\in r (P(t))$ will then mean "Every person who is a student is intelligent or simply every student is intelligent"

in other words we can also say it like "there exists no student ($\sim \exists t$) who is dull ($\sim P(t)$)"

Mathematical way

$\forall t\in r (P(t))$

$\equiv \sim \sim$( $\forall t\in r (P(t))$ )  //Use one negation to apply Demorgan law

$\equiv \sim \exists t\in r (\sim P(t))$

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

Option 2 saying that there exist t which is not belongs to r for which p (t) is this might valid may be not ,so here we cant say anything explicitly about the truthness of the 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.

5 Answers

+32 votes
Best answer
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.
answered by Veteran (400k points)
selected by
(1)  gives all tuples that dont satisfy P. So its equivalent to all tuples that satisfy P, right?

But it would describe the complement of set that contains all tuples that satisfy P.
@Arjun sir I got the answer

but in (1) if we give -ve inside what happens?

will it not be $\forall t \in r \left(P\left(t\right)\right)$
That is option 3 rt?
ok u mean

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

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

are same?
Yes, if we say in English they should mean the same.
just curious if we can reduce $∀t∈r(P(t))$ to $¬∃t∈r(¬P(t))$ by using propositional calculus manipulations, instead of interpreting English meaning of those expressions in order to find their equivalence? can we do this?
sir t is tuple variable, r is table and P ? P is attribute?
@Aspirant yes, you can do.

@Resilient P is a predicate- some condition working on a tuple.
okay sir got it....thank you.
doubt : negation of belongs to is belongs to how?
Is r a tuple variabkle or a relation?

Hi Arjun Sir,

one doubt: Just for my understanding 

Can we say negation of ∀t∈r(P(t)) is equivalent to 


yes, that will be


Can we say negation of $∀t∈r(P(t)) $ is equivalent to $∃t∉r(¬P(t))$

This is not same, because of

$∀t∈r(P(t))$ When we apply negation  $¬(∀t∈r(P(t)))\equiv $ $¬∀t∈r(¬(P(t))) $

                                                                                                            $\equiv ∃t∈r(¬P(t))$ 

And one more things $∃t∉r(¬P(t))$ it is Unsafe(Not safe) expression.


@Lakshman Patel RJIT sir... so equivalence given by @Abhijit Sen 4 is not correct?


please don't call me sir

I'm also an aspirant like your

you are right.

There is lot more difference.

see my comment clearly you will understand better.

In given question $(2)$ and $(4)$ query are unsafe.

see this also

II and IV are incorrect because they are talking about the tuples not in R.But we are bothered about the tuples in R.

I says there exists no tuple in R that satisfied P(t).-Just opposite of what is given to us.Rejected.

III says there is no single tuple in r that does not satisfy P(t).Mean all tuples in r satisfy p(t).so This is correct.
r(P(t)) means ? I mean what will be the english translation ?
+14 votes

(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))

answered by Active (4.6k points)

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

+14 votes

∀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. 

answered by Boss (11.7k points)
+11 votes

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.

answered by Boss (23.6k points)
Why no negation on belongs to symbol?
–1 vote

∃t∈r(⌝ P(t))--means that there are some tuples in relation r which do not satisfy the constraint P(t)

and if we put not before this statement we get there are no tuples in relation r which do not satisfy the constraint P(t) which is equivalent to saying all tuples in relation r satify predicate condition P(t)

answered by Active (1.1k points)
I think even (1) is same as yours.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,447 questions
53,651 answers
70,912 users