10.1 As noted in the body of the chapter, there are exactly 16 dyadic connectives. Show the corresponding truth tables. How many monadic connectives are there?

10.2 Let p and q stand for arbitrary propositions. Prove that

     NOT ( p AND q ) ≡ ( NOT p ) OR ( NOT q )

10.3 Again let p and q denote arbitrary propositions. Prove that

     ( ( NOT p ) AND ( p OR q ) ) IMPLIES q

is a tautology. (I remind you from Chapter 4 that a tautology in logic is an expression that’s guaranteed to evaluate to TRUE, regardless of the values of any variables involved. Likewise, a contradiction is an expression that’s guaranteed to evaluate to FALSE, regardless of the values of any variables involved.)

10.4 (Repeated from the body of the chapter, but reworded here.) (a) Prove that all of the monadic and dyadic connectives can be expressed in terms of suitable combinations of NOT and either AND or OR; (b) prove also that they can all be expressed in terms of just a single connective.

10.5 Consider the predicate “x is a star.” (a) First, if the argument the sun is substituted for x, does the predicate become a proposition? If not, why not? And what about the argument the moon? (b) Second, if the argument the sun is substituted for x, is the predicate satisfied? If not, why not? And what about the argument the moon?

10.6 Consider the predicate “x has two moons.” If the argument Jupiter is substituted for x, is the predicate satisfied? Justify your answer.

10.7 Here’s constraint CX1 once again from Chapter 8:

     CONSTRAINT CX1 IS_EMPTY ( S WHERE STATUS < 1 OR STATUS > 100 ) ;

The expression IS_EMPTY (...) here is clearly a predicate. Now, in Chapter 8, I said the relvar name “S” in that predicate was acting as a designator. But isn’t it actually a parameter? If not, what’s the difference?

10.8 (Repeated from the body of the chapter.) What query does the following expression represent? And do you think that query is a “sensible” one?

     { SX.SNAME } WHERE EXISTS SPX ( FORALL PX ( SPX.SNO = SX.SNO AND
                                                 SPX.PNO = PX.PNO ) )

10.9 (Repeated from the body of the chapter.) Give SQL analogs of the relational calculus expressions in the subsection More Sample Queries in the body of the chapter.

10.10 Prove that AND and OR are associative.

10.11 Let p(x) and q be predicates in which x does and does not appear, respectively, as a free variable. Which of the following statements are valid?^[153] I remind you that the symbol “⇒ means implies; the symbol “≡” means is equivalent to. Note too that A ⇒ B and B⇒ A are together the same as A ≡ B (in other words, (A⇒ B AND B⇒ A) ≡ (A ≡ B) is a tautology).

10.12 Let p(x,y) be a predicate with free variables x and y. Which of the following statements are valid?

10.13 Where possible and reasonable, give relational calculus solutions to exercises from Chapter 6–Chapter 9.

10.14 Consider this query: “Get cities in which either a supplier or a part is located.” Can this query be expressed in the relational calculus? If not, why not?

10.15 Is SQL relationally complete? Note: To prove it is, you need to show that for every expression of the relational algebra, there exists a semantically equivalent expression in SQL. Alternatively, to prove it isn’t, you need to show there exists at least one expression of the relational algebra for which no such SQL equivalent exists.

10.16 Here’s a lightly edited excerpt from Chapter 8: “If the database contains only true propositions, then it’s consistent, but the converse isn’t necessarily so; if the database is inconsistent, then it contains at least one false proposition, but the converse isn’t necessarily so.” Are these two statements logically equivalent? In other words, is there some duplication here?

10.17 Is prenex normal form always achievable?