# Discrete Structures

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