This course meets from 10:50 AM - 12:05 PM TTh in Business 110.
will be available in LaTeX,
A schedule of lectures tells
what I plan to talk about, and what I expect you to have read, by each
We're using the textbook
Language of First-Order Logic, by Jon Barwise and John Etchemendy.
This book comes with a floppy disk in the back, either for Macintosh or
Windows. You may buy and use whichever you prefer: the Macintosh
edition has a red cover, while the Windows edition has a blue cover.
The authors have set up an
errata page for the textbook.
I used this textbook a year ago for the MTP
course in Mathematical Logic, and was quite happy with it. It comes
with a computer program named "Tarski's World" which allows the user to
experiment with logical sentences interpreted in an on-screen "world".
Some of your homework assignments will be turned in on floppy disk,
while others will be turned in on paper (or, if you prefer, by email).
- Homework 1, assigned 16 Sept, due 30 Sept, extended to 9 Oct
because the book hadn't come in yet
- Problems from chapter 2 of the textbook:
3,4,5,19 (to be turned in on floppy disk)
6,8,9,10,17,18,21,22,24 (to be turned in on paper or by email)
Note: some of the statements in problem 2.9
cannot be translated; your job is to translate the ones that
can, and give some explanation of why the others can't.
- Homework 2, assigned 21 Oct, due 4 Nov
Problems 3.9,3.17*,3.18,3.20,3.26* (paper or email)
Problems 3.30,3.31,3.34 (informal proofs on paper or email;
counterexamples on disk)
Problems 3.43 (formal proof, paper or email)
Problem 3.60* (paper or email)
Problems 4.4,4.5 (on disk)
Problems 4.11 (paper or email)
Problem 4.14 (informal proofs, paper or email; counterexamples on disk)
Problems 4.25 (formal proofs, paper or email)
- Homework 3, assigned 6 Nov, due 25 Nov
Problems 5.18, 5.23, 5.24, 5.25, 6.9, 6.26, 6.37, 6.52 (paper or email)
Problems 6.19, 6.20, 6.23, 6.50 (on disk)
- Homework 4, aka take-home final exam,
assigned 25 Nov, due at the scheduled exam time, 10:30 AM, 16 December.
Problems 7.2, 7.3, 7.4, 7.9, 7.10, 7.25, 7.27, 7.28, 7.29, 7.30, 7.31,
Problems 8.16, 8.17, 8.18, 8.19, 8.25, 8.26, 8.34, 8.35
And on mathematical induction, the following three:
- Prove that there exists a real number x>1 such that for all
sufficiently large n,
Fn >= xn,
where Fn indicates the n-th Fibonacci number,
F0 = F1 = 1 and
for n > 1, Fn = Fn-1 + Fn-2.
Hint: You'll need to use a base case larger than
1. How much larger depends on what value of x you choose.
Extra credit: What is the smallest value of x for
which you can't make your proof work, even by picking a large base
- Prove that for every natural number n, and every square on a
2n x 2n checkerboard, there is a way to tile
the checkerboard using 3-square, L-shaped tiles, leaving out only
the specified square and not overlapping any tiles.
- Prove the "Pigeonhole Principle": that for any finite set S
and any function
g : S --> S, if g is not onto, then g is not one-to-one.
("g is onto" would mean
that for every element x of S, there is a y in S such that g(y)=x.
"g is one-to-one" would mean that
for every elements x and y of S, if g(x)=g(y) then x=y.)
By Tuesday, 16 Dec, you should have read through chapter 9
of the textbook.
Thu Dec 11 15:45:33 EST 1997
Stephen Bloch / firstname.lastname@example.org