This Collection of learning materials is constructed to provide a flexible network of theory and examples for Discrete Structures as part of ISPeL, an Interactive System for Personalized Learning.The ISPeL System Project is funded by the NSF as part of PPSE, Programmers to Professional Software Engineers Program, at ECU .

The site is designed to be a reference for essential definitions, concepts, examples and practice problems in an environment that allows each learner to personalize their experience within a non-course-centric curriculum. To the extent possible, prerequisites for topics have been integrated within the topic’s development. Your collaboration is welcomed with the aim to make this site a valuable learning resource. The notes are still under construction and are developed with the intention of providing an open resource for both educators and learners. The content is not without typos, and the authors have done their best to present quality information. If you see areas for improvement, please let us know or submit a pull request with your fixes to our GitHub repository.

Each module outlined in the Overview of Discrete Structures below begins with an Introduction. The authors’ recommend that new learners begin with the study of the preliminaries presented in an Introduction section before investigating other concepts in the module. The materials presented are based on the ontology constructed by Dr. Venkat Gudivada, Dr. Kelle Clark and other research members of the ISPeL System Project Team funded by the NSF as part of the PPSE

Set Theory

Introduction

1. What is a set? Definition of a set answers this question.

2. There are some widely used sets whose members are all numbers. What do you call them? Number sets is the answer.

3. Can a set with no elements exists? What do you call such a set? AnEmpty set?

4. Can a set that encompasses all the elements of other sets exist? Ask the Universal set.

5. There are two sets \(A\) and \(B\) such that all the elements of the set \(A\) are contained in set \(B\). What do you call this relationship? Subsets and supersets.

Properties of sets

1. What do you call the number of elements in a set? Cardinality

2. How do you determine if two sets are equal? Set equality helps you answer this question.

3. Some sets have countably finite number of elements while others have an infinite number of elements. Which are those sets? Countable and uncountable sets provides an answer.

4. We want to find elements that are not in a set, but are in the universal set. Set complement operation does exactly this.

Operations on sets

1. How do you combine several sets to create a new set? Set union is the solution.

2. What does it mean to subtract a set from another set? Set difference explains this.

3. Sometimes we are interested in finding the elements that are common across a number of sets. Set intersection explains how this can be done.

4. Given two sets, we are interested in finding the elements which are in either of the sets, but not in their intersection. Set symmetric difference does exactly this.

5. Given two sets \(A\) and \(B\), we want to pair every element from the set \(A\) with every element in the set \(B\). Cartesian product shows you how to do this.

Power sets and partitions

1. What do you call all the subsets of a set? Power set Also, what is the cardinality of the power set?

2. What do you call the grouping of the elements of a set into non-empty subsets in such a way that every element is included in exactly one subset? Partition of a set

3. How do we define relationships between the elements of a set? Ask defining a relation on a set.

4. Using modular arithmetic as a unifying framework, we can explain the interrelatedness among power sets, relations, and partitions. How does the modular arithmetic accomplish this?

Functions

1. In this introduction to functions, rules are examined as the structure to describe relationships between sets. Domain, Range and Image sets are defined and requirement for a rule to be a function is given.

2. Functions can be classified by their behavior. The types of functions covered include injections, surjections, bijections, and homomorphisms.

3. Permutations are functions whose domain and range sets are the same with an arbitrary fixed ordering on the elements.

Operation on functions

1. Addition and subtraction are two operations on functions that is possible under some conditions when the Range set has an addition defined on the elements.

2. If the Range set has a multiplication defined on the set, then multiplication and division of functions to this Range set can possibly be defined.

3. Many concepts relevant to functions can be illustrated using Modular operations applied to functions.

Counting Methods

1. Strategies and known expressions for counting instances of objects in a collection are provided in this overview of combinatorics.

2. How do you determine the number of possible collections if you start with n objects and choose k of them without repeats? Combinations refer to these objects and there are ways to count these collections.

3. Permutations are collections of n objects chosen k at a time when order is relevant.

4. Counting methods can reveal the number of possible k-cycles in \(Z_n\) using modular arithmetic.

Proof Techniques

1. The introduction to proofs begins with differentiating between statements that have a true or false value and other constructs.

2. Translating statements into the language of Mathematics and Symbolic Logic sets the foundation for the construction of a proof.

3. There are many types of proofs commonly used in the fields of Computer Science and Mathematics. Here key proof techniques are explained.

4. Proofs of statements relating to Modular Arithmetic are given as examples of proof techniques applied.

Probability

1. Probability is the field of study focused on measuring uncertainty and likelihood of events.

2. When a variable’s value is dependent on a random phenomenon, the variable is a random variable.

3. A collection of all possible values that can be assumed by a random variable is known as the variable’s outcome space:

4. Probability theory concepts are demonstrated through example using the set \(Z_n\) with multiplication mod n is used to _Modular Arithmetics, Probability:

Groups

1. In this introduction to groups the pairing of a set and an operation on the elements of the collection are examined as one unit.

2. If a fixed set of axioms is true for given set and operation, the pair is a group.

3. The group \(Z_p\) under multiplication is used to model a few theorems for groups. Modular Arithmetics, Groups:

Back to top of page