The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+23 votes

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

- $\neg \exists t \in r \left(P\left(t\right)\right)$
- $\exists t \notin r \left(P\left(t\right)\right)$
- $\neg \exists t \in r \left(\neg P\left(t\right)\right)$
- $\exists t \notin r \left(\neg P\left(t\right)\right)$
- I only
- II only
- III only
- III and IV only

0

I think it belongs to both Mathematical Logic & Databases. Keep Database tag, add Mathematical logic too !

+1

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?

+2

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

+30 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.

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.

0

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

But it would describe the complement of set that contains all tuples that satisfy P.

0

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

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

will it not be $\forall t \in r \left(P\left(t\right)\right)$

0

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?

$\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?

0

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?

+9 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))

+8 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)

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

+6 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.

0 votes

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

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.9k
- Digital Logic 2k
- Programming & DS 3.6k
- Algorithms 3k
- Theory of Computation 3.9k
- Compiler Design 1.5k
- Databases 2.9k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 949
- Others 1.3k
- Admissions 408
- Exam Queries 419
- Tier 1 Placement Questions 17
- Job Queries 55
- Projects 9

34,780 questions

41,758 answers

118,934 comments

41,400 users