SQL and Relational Theory, 2nd Edition

EXERCISES

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