Discrete Structures

CSC/MAT 208 · Fall, 2018

Department of Computer Science · Grinnell College

Class News

November 23, 2018

I see that I changed the sample inference halfway through the hard-copy version of the handout on the semantics of the predicate calculus, switching the premise from ‘P(t(c))’ in the first section to ‘P(t(x))’ in the third. I have corrected this error in the on-line version of the handout, with some adjustments both to the table and to the following text.

November 14, 2018

In today's class, I incautiously gave away the answer to exercise 4 of exercise set #3 even before the exercise set was due. So I'm replacing it with a different exercise, which will be due on November 21. (Any of you who still want to write up and submit a solution to the original problem may do so for extra credit.)

Here's the replacement exercise:

A breakout for a natural number n is a bag of natural numbers that add up to n. For example, the bag 〚 5, 1, 1, 0 〛 is a breakout of 7, because 5 + 1 + 1 + 0 = 7.

Obviously, there are infinitely many breakouts of any natural number, because any breakout can be extended by adding another 0 to the bag. But there is still possible to count breakouts of a specific natural number n of a fixed bag cardinality k. For example, there are exactly eleven four-member breakouts of 7, namely 〚 7, 0, 0, 0 〛, 〚 6, 1, 0, 0 〛, 〚 5, 2, 0, 0 〛, 〚 5, 1, 1, 0 〛, 〚 4, 3, 0, 0 〛, 〚 4, 2, 1, 0 〛, 〚 4, 1, 1, 1 〛, 〚 3, 3, 1, 0 〛, 〚 3, 2, 2, 0 〛, 〚 3, 2, 1, 1 〛, and 〚 2, 2, 2, 1 〛.

(a) For any natural numbers n and k, let K(n, k) be the number of k-member breakouts of n. Write a recursive definition of the function K and provide a combinatorial justification for your definition.

(b) Design, write, and test a Scheme procedure breakouts that takes two natural numbers n and k as arguments and returns a set containing all of the k-member breakouts of n.

(c) The shape of a Skat hand is a bag that contains the number of cards in each of the four suits in that hand. For example, the shape of a Skat hand that comprises five spades, one heart, three diamonds, and one club is 〚 5, 1, 3, 1 〛. Determine how many different shapes a Skat hand can have.

September 18, 2018

In case you need more practice with formal proofs using the propositional calculus, I've drawn up a list of important theorems and put them in a handout: Theorems of the Propositional Calculus. Feel free to prove any of them that look appealing and to use the ones that you prove in subsequent proofs.

September 9, 2018

Here are the links to the readings for Monday's class:

Course Information

Readings

Labs

Exercises