The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+22 votes
1.6k views

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 (68.8k points) | 1.6k 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))$

 

5 Answers

+28 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 (332k 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?
+8 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 Loyal (3.3k points)
+5 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 Veteran (22.7k points)
+4 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 (8.9k points)
+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.2k points)
I think even (1) is same as yours.
Answer:

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

32,443 questions
39,189 answers
108,813 comments
36,563 users