Page 135 - Discrete Mathematics and Its Applications

114 1 / The Foundations: Logic and Proofs

Computations and Explorations

Use a computational program or programs you have written to do these exercises.

1. Look for positive integers that are not the sum of the cubes ∗ 4. Try to find winning strategies for the game of Chomp for
of nine different positive integers. different initial configurations of cookies.
2. Look for positive integers greater than 79 that are not the 5. Constructthe12differentpentominoes,whereapentomino
sum of the fourth powers of 18 positive integers.
is a polyomino consisting of five squares.
3. Find as many positive integers as you can that can be writ-
ten as the sum of cubes of positive integers, in two different 6. Find all the rectangles of 60 squares that can be tiled using
ways, sharing this property with 1729. every one of the 12 different pentominoes.

Writing Projects

Respond to these with essays using outside sources.

1. Discuss logical paradoxes, including the paradox of Epi- 8. Discuss some of the techniques used in computational
menides the Cretan, Jourdain’s card paradox, and the bar- logic, including Skolem’s rule.
ber paradox, and how they are resolved.
9. “Automated theorem proving” is the task of using com-
2. Describe how fuzzy logic is being applied to practical ap- puters to mechanically prove theorems. Discuss the goals
plications. Consult one or more of the recent books on and applications of automated theorem proving and the
fuzzy logic written for general audiences. progress made in developing automated theorem provers.
3. Describe some of the practical problems that can be mod- 10. Describe how DNA computing has been used to solve
eled as satisfiability problems. instances of the satisfiability problem.
4. Describe some of the techniques that have been devised 11. Look up some of the incorrect proofs of famous open
to help people solve Sudoku puzzles without the use of a questions and open questions that were solved since 1970
computer.
and describe the type of error made in each proof.
5. Describe the basic rules of WFF’N PROOF, The Game of
Modern Logic, developed by Layman Allen. Give exam- 12. Discuss what is known about winning strategies in the
ples of some of the games included in WFF’N PROOF. game of Chomp.
6. Read some of the writings of Lewis Carroll on symbolic 13. Describe various aspects of proof strategy discussed by
logic. Describe in detail some of the models he used to George Pólya in his writings on reasoning, including
represent logical arguments and the rules of inference he [Po62], [Po71], and [Po90].
used in these arguments. 14. Describe a few problems and results about tilings with
7. Extend the discussion of Prolog given in Section 1.4, ex- polyominoes, as described in [Go94] and [Ma91], for ex-
plaining in more depth how Prolog employs resolution. ample.