Discrete Math Fundamentals

Welcome to "Discrete Math Fundamentals!"  This course teaches the three underlying concepts of discrete mathematics: sets, propositions, and propositional logic.  It is directed to anyone in the field of computer science who wants to quickly learn or brush up on the fundamentals of discrete math.  The principles presented in this course form the foundations for many computer science algorithms and are studied in many computer science educational programs.

Sets

Set Definition

A set is an unordered collection of objects called elements.  

Example:

The collection of a square, a circle, and a rectangle can be considered a set of the basic shapes.  The square, circle, and rectangle are said to be elements of the set of basic shapes.  

Point out all of the elements that do not belong in the set of dogs.

Roster Method

A set and its elements are often written in a shorthand form called the roster method.  In this method, an uppercase letter is used to denote the set and all of the set's elements are listed between braces.  For instance, the set of basic shapes can be denoted by:

       S = {square, rectangle, circle}

Example 1:

The set of vowels can be denoted by:

       V = {a, e, i, o, u}

Example 2:

The set of odd numbers from one to nine can be denoted by:

       N = {1, 3, 5, 7, 9}

Match each set with its respective elements.

  • The set of even numbers from 2 to 10 =
    {2, 4, 6, 8, 10}
  • The set of cats =
    {cheeta, panther, lion}
  • The set of planets =
    {Venus, Mars, Jupiter, Saturn, Pluto}

Venn Diagrams

A Venn diagram is a graphical representation of a set.  In a Venn diagram:

  •  A rectangle is used to represent all the objects under consideration, denoted by U (universal set) 
  •  Inside the rectangle, circles are used to represent sets
  • Points within the circles represent elements of the set

Example:

Suppose we want to construct a Venn diagram for the set of vowels.  We can do so in the following steps:

  1. First we draw a rectangle to denote our universal set or U .  This is the set of all objects under consideration, so in our case U is the 26 letters of the alphabet.
  2. Second, we draw a circle within the rectangle to represent the set of vowels, V.   
  3. Lastly, we draw points within the circle to represent its individual elements.  In our case, each point represents one of the five vowels.  

Venn Diagram Construction

Construct a Venn diagram of the set N = {1, 2, 3, 4, 5} by dragging the boxes below to the correct slots in the figure.
  • N
  • U
  • 1
  • 2
  • 3
  • 4
  • 5

Subsets

If we have a set A and a set B, then A is a subset of B if every element in A is also an element of B.

Example 1:  

Suppose we have the following two sets:

       A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

       B = {1, 2, 3, 4, 5}

As we can see below, every element in B is also an element of A.  Thus, B is a subset of A.  

       A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

       B = {1, 2, 3, 4, 5}

Example 2:  

Suppose we have the following two sets:

       A = {a, b, c, d, e, f, g}

       B = {1, 2, 3, 4, 5, 6, 7}

Because none of the elements in set B are in set A, B is not a subset of A.

Example 3:

Suppose we have the following two sets:

       A = {1, 3, 5, 7, 9}

       B = {1, 3, 4}

As we can see below, set A contains two of B's elements.  However, set A does not contain the number 4 which is the third element of B.  Thus, B is not a subset of A.  

       A = {1, 3, 5, 7, 9}

      B = {1, 3, 4}

Identifying Subsets

Select the option below that is a subset of the set above.

Propositions

Definition of a Proposition

A proposition is a declarative sentence that is either true or false.  For example, the following sentences are all propositions.

  • Tallahassee is the capital of Florida.
  • The tree is red.  
  • 2 + 2 = 4

Statements that are not declarative are not propositions as they are neither true nor false.  The sentences below are not propositions.

  • Where are you?
  • Go to the store.  
  • x - y = z  

Note: In the last statement, we cannot determine whether it is true or false because we do not know the values of x, y, and z.  

 

 

 

Which of the following sentences are propositions?

  • Where is the cat?
  • The earth is round.
  • x + 2 = 10
  • 2 + 2 = 1
  • Hello!
  • The United States is a Republic.

Truth Values

The truth value of a proposition is true (T) if the statement is true and the truth value of a proposition is false (F), if the proposition is false.  

Example 1:

Suppose we have the proposition, "Toronto is the capital of Georgia."  Since Toronto is not the capital of Georgia, the truth value of this proposition is false (F).  

Example 2:

Suppose we have the proposition "The earth is round."  The truth value of this proposition is true (T) because the earth is indeed round.  

Determine the truth values of the following statements.

  • Washington, DC is the capital of the United States of America
  • The earth is not flat.
  • The sun orbits around the earth.
  • The United States is surrounded on both sides by oceans.

Propositional Logic

Compound Propositions

A compound proposition is one or more propositions combined together.  Two propositions can be combined in one or more of the following ways:

  • Negation
  • Conjunction
  • Disjunction
  • Implication
  • Biconditional

Negation

In negation, a proposition's truth value is reversed using the phrase, "it is not the case that."  The truth value of a negated proposition is always the opposite of the original truth value.  

Example 1:

The negation of the proposition, "The moon is round" is:

       "It is not the case that the moon is round."

This negation can be rewritten more simply as:

        "The moon is not round." 

Example 2:

The negation of the proposition, "The moon is not round" is:

        "The moon is round."

Match each proposition with its negation.

  • Texas is a state.
    Texas is not a state.
  • Texas is not a state.
    Texas is a state.
  • I am eating desert.
    It is not the case that I am eating desert.

Conjunction

In conjunction, two propositions are combined using the connective "and."

Example 1:

The conjunction of the propositions, "The earth is round" and "The earth is blue" is:

       "The earth is round and the earth is blue."

Example 2: 

The conjunction of the two propositions, "The moon is silver" and "The moon is not made of green cheese" is:

       "The moon is silver and the moon is not made of green cheese."

Conjunct the two propositions, "It is lightening" and "It is thundering" by filling in the blank.

It is lightening  it is thundering.

Disjunction

In disjunction, two propositions are combined using the connective "or."

Example 1:

The disjunction of the propositions, "The road is 12 miles long" and "The road is 13 miles long" is: 

       "The road is 12 miles long or the road is 13 miles long."

Example 2:

The disjunction of propositions, "The earth is round" and "The earth is flat" is:

       "The earth is round or the earth is flat." 

Disjunct the two propositions, "It is storming" and "It is sunny" by selecting the correct connective.

It is storming  it is sunny.

Implication

In implicationtwo propositions are combined to form an "If, then" statement.  

Example 1:

The implication of the propositions, "It is storming" and "It is raining" is:

       "If  it is storming, then it is raining."

Example 2:  

The implication of the propositions, "It is sunny" and "I will go to the beach" is:

       "If  it is sunny, then I will go to the beach."

The implication of the two propositions, "I wake up at 6:30" and "I will go to the store" is?

  • If I wake up at 6:30, then I will go to the store.
  • If I go to the store, then I will wake up at 6:30.

Biconditional

The biconditional of two propositions is formed by connecting the two statements with the phrase, "if and only if."

Example 1:

The biconditional of the propositions, "I will go to town" and "The sun is shining" is:  

       "I will go to town, if and only if, the sun is shining."

Example 2:

The biconditional of the propositions, "I will paint the barn" and "It is 90 degrees outside" is:  

        "I will paint the barn if and only if  it is 90 degrees outside."

Fill in the blank to find the biconditional of the propositions, "I will eat cake" and "The cake has chocolate icing."

I will eat cake  the cake has chocolate icing.

Suggested Readings & Credits

Supplementary Readings

The following print and online resources provide additional information on the topics covered in this course.  

Photo Credits

Photos used in the illustrative graphics and graphical questions:

Clipart

Other