## Homework 2 (due 4/16) CSC 202

We finished chapter 1 and started on chapter 2 (2.1-2.3 and 2.5). Next week we will finish chapter 2 and start talking about relations and first-order logic. I suggest you read through Sections 2.1-2.3 carefully, since it contains several additional examples and exercises (some with solutions).

Submission: you can submit the homework to me either by hardcopy in class or email it to me.

1. [Check Constraints] Write complete ALTER TABLE commands for the following check constraints (see Section 1.4). Also, for each check constraint write an INSERT statement that violates the constraint. (Double-check by running them on the database.)

1. [10pt] The career in Student is one of the following: GRD, UGRD, SAL. Hint: here is what the SQL for adding the constraint will look like:
```ALTER TABLE Student
CHECK ( ... );
```
1. [15pt] All IT courses are undergraduate courses (that is, their course number is less than 420 (this is a bit tricky; think about it carefully: what are you trying to exclude? Make sure you test your constraint with examples).

2. [Set Theory, 10pt] True of False? If true, give a proof, if false, find sets A, B, C that show that it is false:

A n (B u C) = (A n B) u C, for all sets A, B, C.

(u is union, n is intersection).

3. [Programming Logic, 15pt] Some programming languages (functional languages in particular) contain an if-then-else expression. That is you write

if condition then a else b,

and if condition holds, the value returned will be that of a and if not, the value of b. (In C you could write (a <= b ? a : b) to compute the minimum of a and b.)

1. [5pt] Find the truth-table of the truth-function "if p then q else r".
2. [10pt] Find the disjunctive normal form for "if p then q else r".

4. [SQL Queries, 30] For each SQL query, please submit your SQL and a printout of the resulting table. Be careful writing both of these, and make sure you double-check that your output is what you expect it to be.

1. [15pt] List student groups which have both Chicago and non-Chicago members (HerCTI is the only such group in our database).
2. [15pt] List students that are not presidents of any student society.

5. [Extra Credit] You have five jars of quarters. One jar contains all counterfeit quarters, the remaining jars contain good quarters only. The counterfeit quarters are 5 grams each, the real quarters 6 grams. You also have a scale. You can pick any number of coins from the jars and make one weighing on the scale. How do you determine which jar contains the counterfeit quarters?

6. [Extra Credit] Show that every truth-function can be written using just logical nand (see Section 1.5 for definition of nand). Hint: show that negation and logical and can be expressed just using nand.

7. [Extra Credit] An old English nursery rhyme goes as follows:

For want of a nail the shoe was lost.
For want of a shoe the horse was lost.
For want of a horse the rider was lost.
For want of a rider the battle was lost.
For want of a battle the kingdom was lost.
And all for the want of a horseshoe nail.

What is the logical structure of this nursery rhyme? Introduce appropriate atomic propositions (one for each object), and then use these propositions to describe the statements in the rhyme.

8. [Extra Credit] If you find any typos and mistakes in the lecture notes, please let me know.

Marcus Schaefer
Last updated: April 10h, 2007.