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:
- 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
Microworld:
Finite Sets: Counting, Recursion, and
Logic, Next Steps
Click the Hyperlink above to visit the Microworld in your Browser.
Author: James White
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:
- 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 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:
- 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" 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:
-
"Run ActiveX Controls and Plugins" set either to enable or prompt.
-
"Initialize and Script ActiveX Controls not marked as safe" set either to enable or prompt.
Return to the listing of MathwrightWeb Microworlds
| - James E. White, Ph.D. , Library Director, | ||
| author of this website, Mathwright 2000, MindScapes, | ||
| MathwrightWeb, and Mathwright32 |
