Mathwright Visualization Studio free demonstration Microworld:
Interactive
Web Course
Discrete
Mathematics and Computational Structures,
Part 2
Finite Sets: Counting, Recursion, and Logic, Next Steps
Requires
the Java MathwrightWeb ActiveX Control to read in your Browser.
For proper viewing, be sure to use Version 2.10 or later, dated May 12, 2003
Download free MathwrightWeb to view
Microworlds in your browser, then press
or
Library members, download the free Mathwright32
Reader, then press
For proper viewing, be sure to use Version 2.10 or later, dated May 12, 2003
Microworld: Finite
Sets: Counting, Recursion, and Logic, Next Steps
Click the Hyperlink above
to visit the Microworld in your Browser.
Author:
James
White
This
Microworld is the second half of a 12-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:
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 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:
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 various
purposes. Each graph is conceptually a set of nodes N, together with a set
of relations Ri :N -> N. You may have no more than 20 nodes in a graph, and
each node will have a name which may contain no more than 25 characters. Graphs
are constructed in three steps:
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" depicted
above.
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. There is a detailed
discussion of that environment there, and we won't repeat it here. 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.
Once
you download our free Mathwright32 Reader above, then simply click
Get This Microworld, and it will be downloaded to your machine and
installed in a directory there. You may find it whenever you want to view
it, by going to the Start, Programs, Mathwright32 Reader menu.
To
visit our Microworlds in your browser, it must be able to read ActiveX
controls. Microsoft Internet Explorer 4.0 Browser (or later)
is so equipped. You should check that the Security Settings under Tools,
Internet Options, Security for the Internet, Custom Level has:
Return to the listing of MathwrightWeb Microworlds
| - James E. White, Ph.D. , Library Director, | ||
| author of this website, Mathwright 2000, MindScapes, | ||
| MathwrightWeb, and Mathwright32 |