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.
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
that takes two natural numbers n and k as arguments
and returns a set containing all of the k-member breakouts of n.
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.
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.
Here are the links to the readings for Monday's class:
Axiom Systems and Mathematical Theories
Bell Numbers and Integer Partitions
Definitions and Libraries
Factorials, Falling Powers, and Binomial Coefficients
Laws of Relations
Laws of Sets
Permutations and Combinations
The Predicate Calculus
The Propositional Calculus
Records in R7RS Scheme
Scheme: A Refresher
Scheme in DrRacket
Semantics of the Predicate Calculus
Text Formatting and Typesetting with LATEX
Theorems of the Propositional Calculus
Evaluating Sentences of the Predicate Calculus in Finite Universes
Generating and Counting Bags
Generating Permutations and Combinations
Getting Started with LATEX
Libraries in R7RS Scheme
Prose Proofs about Sets
Proofs about Sets
Proofs in the Predicate Calculus
Records in R7RS Scheme
Setting up DrRacket for R7RS Programming