Click Back to return
THE MATHWRIGHT LIBRARY NEWSLETTER, October 2002, VOL
4, #7
A publication of Bluejay Lispware
James E. White, Editor
The official publication of the New Mathwright Library and Café:
In this issue:
Featured Microworlds this Month!
1) Featured Microworlds this Month!
Symbolic
Calculator
by James White, Mathwright
Library, and
Visiting Professor
of Mathematics, Naval
Postgraduate School
Use
this command-line calculator for graphics, Exact or Decimal arithmetic and
algebra, factoring numbers and polynomials, differentiation, integration,
matrix calculations, sprite animation, and for a variety of other purposes.
If our over 300 built-in commands and functions (that you will find described
in detail at the Library Online Help) do
not fit the bill, then use the script window to create your own programs or
commands! Define simple functions easily at the command line. The tutorial
in the Microworld steps you through nearly 100 examples.
This
calculator gives you a chance to try new things. For example, create your
own sprites and move them using your own programs. Use Bignumbers for "unlimited"
accuracy. This may be the only calculator you will ever need!
Discrete
Mathematics and Computational Structures Course, Part 1
by James White, Mathwright
Library, and
Visiting Professor
of Mathematics,
Naval Postgraduate School
This
22 page Interactive Web Course is the first half of a 14-week course in Discrete
Mathematics. It is an introduction to the theory of sets. In a series of 11
readings, you will learn the elements of a language and a methodology for
the clear formulation of ideas in Set Theory. We recommend that you pursue
the readings in the order in which they appear below, beginning with "Sets
as Conceptual Tools." You may read the 44-page collection of lectures either
within the Microworld, or as a Word 2000 document. To download the Lectures
as Word Document, click here, then extract
the file to your disk.
Also,
to download the Laboratory Instructions as Word Document, click here,
then extract the file to your disk.
- Sets as Conceptual Tools
- Sets and Logic
- Operations on Sets
- Boolean Algebra of Sets
- Relations
- Algebra of Relations
- Functions
- Composition of Functions
- Permutations of Sets
- Graphs and Directed Sets
- Order and Cardinality
The
readings contain many problems and exercises that illustrate its themes and
test your understanding. These readings will direct you to our seven "activities,"
where you may test your ideas, and make them more tangible and concrete. You
may, of course, visit those activities at any time, and you are encouraged
to do so.
The
aim of Sets, Functions, and Relations is to help the reader visualize,
in a variety of ways, the basic properties of the objects in its title by
making them concrete. While the purview of set theory is all of modern mathematics,
our presentation begins with the consideration of simple small and discrete
sets. Many of its central ideas may be captured in this realm -- and many
may not. By "small" we mean finite. And by "finite", we mean "not infinite."
But even that idea, the idea of some infinite thing, will have its clearest
formulation in set theory itself, as we'll see in the last reading on "Order
and Cardinality" by proceeding from the solid intuitions already built up
from consideration of the properties of "small" sets. So no harm is done by
proceeding from the familiar and concrete to the less familiar and less concrete.
The
seven activities are designed to support your progress in visualizing sets,
at each step of the way. These activities are:
- Set Constructor
- Set Viewer
- Operations Lab
- Relations Viewer
- Workshop
- Office
- Set Safari Game
For
each of these activities pages, you will find detailed instructions how to
use the page under the Instructions button on that page.
The
Set Constructor is the first place you go to build new sets for use
throughout this Microworld. Later, in the Workshop, you may build sets
more conveniently, but this is the place to start.
The
Set Viewer is a place to view simple sets. Each set will have a name.
16 sets are predefined for you. They have the names: mammal, aquatic, lays_eggs,
reptile, bird, hunts, snake, has_horns, feline, canine, primate, has_tusks,
ungulate, fruit_eater, quadruped, and has_fur. As you create new sets,
first in the Constructor, and later by command, using set operations and relations,
new sets will be named: an1, an2, ... The sets of animals that you
work with on projects may be saved to disk and later restored. In the Set
Viewer, you may see the animals of any set that you name as colorful pictures.
The
Operations Lab is the place to begin experimenting with the basic operations
on sets: Union, Intersection and Complementation. These operations
are discussed in the Reading "Operations on Sets." There you may use the Show
command to show pictures of sets obtained by combining old sets using these
operations, the Build command to create new sets in this way, the Size
Command to tell the size of any set, and the IsEqual and Subset
commands to compare sets.
The
Relation Viewer is the first and simplest place to define and view
relations between sets, and functions between sets. Here, you choose two sets:
a Source set and a Target set, and define any relation or function
from Source to Target. The properties of relations and functions are discussed
in several of the readings, notably, "Algebra of Relations," and "Composition
of Functions" and while the algebraic manipulation of these is best done in
the Workshop, here you may create and view them with pictures. Like Sets,
each relation and function created in the Microworld has a name such as: re1,
re2,.. and these may also be saved to disk and later restored.
The
Workshop and Office have similar functions. The Workshop is
more graphical, and the Office more text-oriented. In these environments,
you may use the Show command to show Sets, Relations, the results of operations
on sets, the results of algebraic operations (such as composition and inversion)
on relations or functions, the images and preimages of relations between sets,
the effects of permutations (as invertible functions) and so on, interactively.
You may use the Build Command to create new sets and relations by any combination
of the mentioned operations. You may test sets so constructed for equality
or for subsets. We also explore in the Workshop the structure of elementary
groups, such as dihedral groups, the properties of ordering
and equivalence relations, and the notion of cardinality.
Finally,
the Set Safari Game brings it all together with an amusing exploration
of the relations between set operations and the propositional calculus
of logic. The rules of the game are simple (but described in more detail
there). The computer creates a "hidden" set of animals, telling you its size
only. It creates this set by generating randomly a proposition from the primitive
16 proposition-sets listed above. Such a proposition might be: "the union
of all reptiles and animals that both hunt and are not quadrupeds" This is
a definite set, and the computer can generate 2^17 such propositions randomly
(over 100,000). This corresponds to a somewhat smaller number of actual sets
(There are 2^46-1 sets possible).
The
player then proposes propositions, such as: "the intersection of mammals and
animals that do not hunt" The computer replies by informing the player of
the number of animals in its set that satisfy the proposition. Using
this information, the player proceeds to the next guess. If the player's proposition
produces the identical set, the computer congratulates the player, and then
shows its proposition and the set it produced. The player may of course use
any of the commands (Show, Build, Subset, IsEqual and Size) to help
her along. Often, with care, the player can find the precise set within 10
guesses, but the propositions are seldom identical.
The
reasoning employed is, of course, precisely the reasoning that we formalize
and develop in the readings, and so this exercise is a useful accompaniment
to the course of readings.
Discrete
Mathematics and Computational Structures Course, Part 2
by James White, Mathwright
Library, and
Visiting Professor
of Mathematics,
Naval Postgraduate School
This
20 page Interactive Web Course is the second half of a 14-week course in Discrete
Mathematics. The term "Discrete Mathematics" in this Microworld will refer
loosely to the collection of techniques, ideas, and constructions that have
evolved over the years to describe artificial systems, and in particular,
those systems from which the modern theories of computing have evolved. So,
for example, an excellent model for our subject is the Turing Machine, or,
equivalently, the lambda-calculus of Alonzo Church. In fact, the lambda-calculus
is the conceptual basis for the computer language, LISP, which is the
language in which this Microworld is written.
We
recommend that you follow the 9 readings of this Microworld in the order in
which they appear below, beginning with "Iteration and Recursion."
You
may read the 72-page collection of lectures either within the Microworld,
or as a Word 2000 document. To download the Lectures as Word Document, click
here, then extract the file to your disk.
Also,
to download the Laboratory Instructions as Word Document, click here,
then extract the file to your disk.
Those readings are:
- Iteration and Recursion
- Sets defined by Propositions
- The Art of Counting
- Relations and Functions
- Digraphs as Relations
- The Art of Searching
- Critical Path Analysis
- Automatic Problem Solving
- Graphs and Logic
The
readings contain many problems and exercises that illustrate its themes. They
often cover some of the same ground as those of the first Microworld, but
they do it in more depth, and so will develop and test your understanding.
These readings will also give you the opportunity to experiment in the 8 Activity
Labs with the ideas they develop. They will direct you to those activities
where appropriate, and of course, you may visit those any time you like.
While
the first Microworld worked with finite sets from a universe of 46 animals,
in this Microworld we work with two types of sets: Finite sets of numbers,
and subsets of products of finite sets of numbers. We examine three ways
to define sets. The first is by recursive definition, the second is
by propositions, and the third is by algebra, that is, through
the use of Boolean Operations, Products, and the construction of images
and preimages of functions and relations.
An
example of the construction of sets by recursion is the famous Fibonacci sequence.
Another example generates the nth level in Pascal's triangle, and so defines
the basis for a large number of combinatorial and counting arguments. Examples
of the second type are familiar from the "set builder notation." Thus "The
set of positive whole numbers less than 100 that are congruent to their squares
modulo 7" is an example. We have seen instances of the third type in the
Set Safari game. But now, we may define interesting functions and relations
for example that can help us formulate and solve problems in probability,
game theory, and even computational logic.
The
8 activities are designed to support your progress in working with discrete
models. These activities are:
- Recursion Lab
- Number Set Constructor
- Relations/Functions Lab
- Graph Constructor
- Path Finder Lab
- Rule-Based System Lab
- Workshop
- Fly-by-Night Airline
For
each of these activities pages, you will find detailed instructions how to
use the page under the Instructions button on that page.
The
Recursion Lab allows you to construct sequences (ordered sets) of numbers
by means of recursion formulas, such as: a(1) = 1, and a(k) = a(k-1)*k which
defines the "factorial function," so important in combinatorics. We will discover
there a number of beautiful relations that have their simplest and most elegant
formulations as recursions.
The
Number Set Constructor is the place to build sets of numbers defined
by propositions:
{ x in MySet | p(x) is true }
to build products of these sets, and to build subsets of products (e.g. relations) by propositions of the form:
{ v in MySet | ( p(v(1)) is true ) or ( q(v(2)) is true ) }
and so on.
You
may use any of the functions in the list below to build elaborate and decorative
sets: The sets you create in this lab are available for use on all of the
other pages of the Microworld. Each set will have a name. As you create new
sets, first in the Constructor, and later by command, using set operations
and relations, new sets will be named: Set1, Set2, ...
The
Relation/Function Lab is where you define relations, functions,
and propositions for use elsewhere in the Microworld. These relations
may be composed, inverted, applied to sets and used in other ways.
The
Graph Constructor is where you will build and study graphs for deductive
information retrieval using Prolog in the Rule-Based Systems Lab. Each graph
is conceptually a set of nodes N, together with a set of relations Ri :N ->
N. Graphs are constructed in three steps:
- Name and define the nodes (This defines the set)
- Create the relations (These relations are associated to the set as arrows)
- Assign "attributes" for the arrows of the relations.
Once
a graph is created, it may be saved to disk. It is referred to by whatever
name the system assigned to the set, and when the environment is restored,
the graph is retrieved by referring to that set. For example, you may create
a simple graph where the arrows of the relation represent kinship relations
(each relation shown automatically in a different color). Or you may create
more complex graphs such as the one in our "Fly-by-Night Airline".
The
relations of these graphs may of course be manipulated algebraically. But
they may also be the object of various kinds of "search" and of deductive
information retrieval." For example, we could ask for all the paths from Washington
D.C. to San Francisco that are under 3500 miles in length.
The
Path Finder Lab is where you experiment with path analysis on a directed
graph that we supply. You may do similar experiments on your own directed
graphs in the WorkShop.
The
Rule-Based System Lab uses a Prolog-style Automatic Problem Solver
to enable you to create sophisticated relational databases, and to formulate
rules for which the system will systematically search out all solutions to
your queries. This illustrates an important and powerful application of search.
We explain this search strategy in detail (backward chaining with recursive
backtracking) because it is the main engine of a large class of "Expert Systems."
You will in fact create your own Expert System and experiment with it here.
The
WorkShop is the place to experiment with the basic Boolean operations
on sets: Union, Intersection and Complementation. It is also the place
to work with the set builder notation to build rich and illustrative new sets.
In this environment, you may use the Show and Describe commands to show Sets,
Relations, the results of operations on sets, the results of algebraic operations
(such as composition and inversion) on relations or functions, the images
and preimages of relations between sets, the effects of permutations (as invertible
functions) and so on, interactively. You may also use the Build and Construct
Commands to create new sets and relations by any combination of the mentioned
operations. You may test sets so constructed for equality or for subsets.
We
also explore in the Workshop the application of programs that you write to
search directed graphs that you build. We look at the structure of elementary
groups, such as dihedral groups, the properties of ordering and equivalence
relations, and the notion of cardinality.
Finally,
a visit to the Fly-by-Night Airline will introduce you to the science
of path analysis using Prolog. It is an amusing discussion that will familiarize
you with all options that are available to you in the Rules Based Systems
Lab, and is an excellent preparation for your work there. Roughly speaking,
you attempt to plan routes between the hub cities of the airline, and the
system will then find all shorter routes (if any). You may also use the system
to help you with your planning by asking certain questions about routes.