I have the following question and given answer:

Question: List the names of managers who have at least one dependant.

Answer: {e.Fname, e.Lname | EMPLOYEE(e) AND (∃d)(∃t)(DEPARTMENT(d) AND DEPENDANT(t) AND e.Ssn = d.Mgrssn AND t.Essn = e.Ssn) }

My answer was exactly the same except that instead of the (∃d)(∃t)(...) section I said (∃d)(DEPARTMENT(d) AND e.Ssn = d.Mgrssn) AND (∃t)(DEPENDANT(t) AND t.Essn = e.Ssn).

Are these equivalent?


1 Answer 1


Let me concentrate, as you asked, on section $(\exists d)(\exists t)(\cdots)$.

In case when one part of conjuction is "not depend" on letter under existence quantifier, holds $$(\exists d)(A \text{ and } B)\Leftrightarrow (\exists d)(A) \text{ and } B$$ Where we assume $B$ does not containt letter $d$. $$$$ In your case, for simplicity, let make following designations: $$\begin{array}{l} A(d) = \text{ DEPARTMENT(d) }\\ B(t) = \text{ DEPENDANT(t) } \\ C(d) = (\text{e.Ssn = d.Mgrssn})\\ E(t) = (\text{t.Essn = e.Ssn}) \end{array}$$ and assume, that $A,C$ doesn't depend on $t$ and $B,E$ doesn't depend on $d$. Then we have

$$(\exists d)(\exists t)\big(A(d) \text{ and } B(t)\text{ and } C(d) \text{ and } E(t)\big) \Leftrightarrow \\ \Leftrightarrow (\exists d)\big(A(d) \text{ and } C(d)\big) \text{ and } (\exists t) \big(B(t)\text{ and } E(t)\big)$$ So, you are right, they are equivalent in reviewed case.

Generally we cannot distribute existence quantifier with respect to $\text{AND}$(conjunction) operation as shows example: take $A=$"$d$ is even" and $B=$"$d$ is odd". Then, of course, sentence "$(\exists d)(A) \text{ and } (\exists d)(B)$" is true, but sentence "$(\exists d)(A \text{ and } B)$" is false.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.