We covered most of Sections 1.1, 1.2, 1.3 (no implication yet), and the first part of Section 1.4; for next time, please read through sections 1.3, 1.4 and 1.5, we will talk about those next time. The lecture notes for the second class should be available before Monday. Our topic will be databases and set theory. For this, and the next homeworks, I suggest you install the H2 Database Engine (the appendix has some information on installation.)
Submission: you can submit the homework to me either by hardcopy in class or email it to me.
Style: Please type up your homework (drawings by hand are ok, but text should be typed). Write up your solutions in full sentences.
1. [SQL Queries, 25pt] For each SQL query, please submit your SQL and a printout of the resulting table.
2. [Propositional Logic, 5pt] Using truth-tables, prove that Peirce's law is a tautology:
((p -> q) -> p) -> p
The truth-table for implication, ->, is the following:
3. [Binary operators, 10pt] Construct the truth-table for "p and q have opposite truth-values" and find an equivalent formula using only p, q, and any of the logical operations (and, or, not).
4. [SQL, multiple tables, 15pt] The following queries require multiple tables, remember to include the conditions equating foreign and primary keys.
5. [Extra Credit] (due to Martin Gardner) Multiple choice question: assuming at least one of the following statements is true, which one is it? Why?
6. [Extra Credit] (classic interview question)
You have a bucket of jelly beans. Some are red, some are blue, and some green. With your eyes closed, pick out 2 of a like color. How many do you have to grab to be sure you have 2 of the same?
7. [Extra Credit] If you find any typos and mistakes in the lecture notes, please let me know.