Discrete Math - The MKD Remix

Most problems that involve computational methods, need to be solved using computers. Rather than solve for the temperature map of an entire planar region, we solve for the temperature using a discrete set of mesh or grid of points on a representative subset of the planar region.

Discrete mathematics is needed for computer science as information and data is stored digitally. Digitally represented data is inherently discrete and is processed using discrete methods. For example a course grid discrete representation of the 2-d temperature distribution from the plate above could be:

\( \left(\begin{matrix}1&1&1\\2&4&8\\3&9&27\\4&16&64\\5&25&125\\\end{matrix}\right) \)

A voter registry may have voters in a database accessible from a list:

\( \left(\begin{matrix}John\ Smith\\Raheem\ Johnson\\.\\.\\.\\Sarah\ Muller\\\end{matrix}\right) \)

Which may need to be accessed and sorted, say geographically or alphabetically.

Data science solutions to many problems use machine learning algorithms that are inherently discrete in nature. The information that needs processing is discrete, as are the basic problems in data science such as classification or clustering problems. In particular

Digital signal processing involves taking a video, audio, or other signal like temperature, pressure, position and velocity, which is continuous, digitizing it and then processing the digital signal mathematically.

Combinatorics involves in part the study of counting the number of objects, satisfying a specified condition, from sets of variable size. Enumeration and combinatorics is important in many areas and examples including:

Graph theory, which is the study of structures constructed with nodes and the edges joining them, has applications in many fields including,

An example of the shortest tour problem, is shown below, using a software solution.

Many probability assignments are based on counting and combinatorial methods.

Discrete mathematical techniques are important in understanding and analyzing social networks including social media networks.

The mathematics of voting is a thriving area of study, including mathematically analyzing the gerrymandering of congressional districts to favor and/or disfavor competing political parties. The following example illustrates some of the fundamental ideas related to gerrymandering.

Consider the following set described using set builder notation: \[\{x \in \mathbb{Z} : x^2 = 2\}.\]This is the set of all integers whose square is equal to 2. However, no such integers exist. Therefore, using the roster method to describe it, this is the set \(\{ \}.\)

We call the set \(\{ \}\) the empty set and denote this set by \(\emptyset.\) The empty set has no elements.

Suppose that a set \(A\) contains a finite number of distinct elements. We refer to the number of elements of \(A\) as the cardinality of \(A\) and denote this by \(|A|\). In this case, we also say that \(A\) is a finite set.

If \(A\) contains an infinite number of distinct elements, we say that \(A\) has infinite cardinality and that \(A\) is an infinite set.

Thus, we see that \(|\{0,1,2\}| = 3\), \(|\emptyset| = 0\), and \(|\mathbb{Z}|\) is an infinite cardinal number.

We say that two sets are equal if and only if they contain the same elements. When \(A\) and \(B\) are equal sets, we write \(A = B\). When \(A\) and \(B\) are not equal sets, we write \(A \neq B\).

The sets \(\{2,3,5\}\) and \(\{5,2,3\}\) are equal sets, since they contain the same elements. In fact, \(\{2,3,5\}\) and \(\{5,2,3\}\) are really just two different descriptions of the same set, in the same way that \(2 + 2\) and \(5 - 1\) are two different descriptions of the same number. So we can write \(\{2,3,5\} = \{5,2,3\}\) for the same reason we can write \(2 + 2 = 5 - 1\).

We say that a set \(A\) is a subset of a set \(B\) if and only if every element of \(A\) is an element of \(B.\) When \(A\) is a subset of \(B,\) we write \(A \subseteq B\). When \(A\) is not a subset of \(B,\) we write \(A \not\subseteq B\).

In order to show that \(A\) is a subset of \(B,\) we must show that, whenever \(x \in A,\) it is also the case that \(x \in B.\) In order to show that \(A\) is not a subset of \(B,\) we must find a single \(x\) such that \(x \in A\) but \(x \not \in B.\)

Note that, for any set \(A,\) it is always the case that \(\emptyset \subseteq A\) and \(A \subseteq A.\) For any sets \(A\) and \(B,\) if \(A \subseteq B\) and \(B \subseteq A,\) then \(A = B.\)

If \(A \subseteq B\) and \(B\) contains at least one element that is not in A, then we say \(A\) is a proper subset of \(B\), denoted \(A \subset B\).

Given a set \(A,\) we refer to the power set of \(A\) as the set of all subsets of \(A.\) The power set of \(A\) is denoted by \(\mathcal{P}(A).\)

If we let \(A = \{a,b,c\},\) we see that \[\mathcal{P}(A) = \{\emptyset, \{ a \}, \{ b \}, \{ c \}, \{a,b\}, \{a,c\}, \{b,c\}, \{a,b,c\}\}.\] The empty set only has the empty set as a subset. Thus, we see that \[\mathcal{P}(\emptyset) = \{\emptyset\}.\]We can also take the power set of a power set. For example, we have the following:

The union of the sets \(A\) and \(B\) is the set containing those elements that are in \(A\) or \(B\) or both, and is denoted by \(A \cup B\). More formally, \[A \cup B = \{x \in U : x \in A \text{ or } x \in B\}.\]

Note that "or" is read here as the "inclusive or". We have the following Venn Diagram for \(A \cup B\):

Note that, for any sets \(A\) and \(B,\) \[A \cup B = B \cup A.\]

The intersection of the sets \(A\) and \(B\) is the set containing those elements that are in \(A\) and \(B\) and is denoted by \(A \cap B\). More formally, \[A \cap B = \{x \in U : x \in A \text{ and } x \in B\}.\]

We have the following Venn Diagram for \(A \cap B\):

Note that, for any sets \(A\) and \(B,\) \[A \cap B = B \cap A.\] If it is the case that \(A \cap B = \emptyset,\) then we say that \(A\) and \(B\) are disjoint. In other words, two sets are disjoint if and only if they contain no elements in common.

The complement of a set \(A\) is the set of all elements in the universal set \(U\) which are not elements of \(A\) and is denoted by \(\overline{A}.\) More formally, \[\overline{A} = \{x \in U: x \not\in A\}.\] Note that other textbooks and internet sources may use different notation for the complement of \(A\), such as \(A'\) and \(A^{c}\), but these all stand for the same set, so that \(\overline{A} = A' = A^{c}\).

We have the following Venn Diagram for \(\overline{A}\):

For any set \(A,\) \[ \overline{\overline{A}} = A \] \[ \overline{A} \cup A = U \] + \[ \overline{A} \cap A = \emptyset. \]

The difference of the sets \(A\) and \(B\) is the set containing those elements that are in \(A\) but not in \(B\) and is denoted by \(A \setminus B\). Set difference is also denoted by \(A - B\). More formally, \[A \setminus B = \{x \in U: x \in A \text{ and } x \not\in B\}.\]

We have the following Venn Diagram for \(A \setminus B\):

Note that, for any sets \(A\) and \(B\), if \(A \neq B,\) then \[A \setminus B \neq B \setminus A.\] However, if \(A = B,\) then \(A\setminus B = B \setminus A = \emptyset\).

The symmetric difference of the sets \(A\) and \(B\) is the set containing those elements that are in \(A\) or \(B\) but not both \(A\) and \(B\). It is denoted by \(A \oplus B\) in this textbook, but other books and sources may use different notation such as \(A \Delta B\). More formally, \[A \oplus B = \{x \in U: (x \in A \text{ and } x \not\in B) \text{ or } (x \in B \text{ and } x \not\in A)\}.\]

We have the following Venn Diagram for \(A \oplus B\):

Note that, for any sets \(A\) and \(B,\) \[A \oplus B = B \oplus A.\]

We can also perform more than one set operation on a collection of sets. For example, let \(A,\) \(B,\) and \(C\) be sets and consider the following set: \[(A \setminus B) \cup (C \setminus B).\]This is the set that is obtained by taking the union of the sets \(A \setminus B\) and \(C \setminus B.\) We have \[(A \setminus B) \cup (B \setminus A) = \{x \in U: (x \in A \text{ and } x \not\in B) \text{ or } (x \in C \text{ and } x \not\in B)\}.\]

We have the following Venn Diagram for \((A \setminus B) \cup (C \setminus B)\):

Note that the Venn Diagram also represents \((A \cup C ) \setminus B\). In general, there are multiple ways to describe the result of multiple set operations.

Video Examples

The following two video examples feature Dr. Katherine Pinzon, Professor of Mathematics at Georgia Gwinnett College.

Video Example 1

Video Example 2

The Cartesian product of two sets \(A\) and \(B\) is the set of ordered pairs defined by,

\( A\times B=\{(a,b)|a\in A \text{ and } b\in B)\}\),

To ensure that we can properly interpret an expression involving multiple set operations, we can either use parentheses or rely on operator precedence.

When an expression for sets involves parentheses, complementation, intersection, and union, we start by evaluating all expressions enclosed in parentheses from left to right, then all complementations from left to right, then all intersections from left to right, and finally all unions from left to right. (Set difference and symmetric difference were left out of this discussion because there does not seem to be a standard definition for where they fit in! But, as shown earlier, those two operations can be rewritten in terms of complementation, union, and intersection.)

For example, the expression \(\overline{A} \cup B \cap C\) represents the same set as \((\overline{A}) \cup (B \cap C)\). Parentheses must be used if you want to represent a different set such as \((\overline{A} \cup B) \cap C\).

This is the same way arithmetic expressions like \(-3 + 5 \cdot 2\) are evaluated: The value of \(-3 + 5 \cdot 2\) is \((-3) + (5 \cdot 2) = 7\), not \((-3 + 5) \cdot 2 = 4\).

Suppose we have three sets \(A\), \(B\), and \(C\), and have partitioned the universe \(U\) into the 8 subsets as discussed above. Then a set that corresponds to any shading of the Venn diagram can be written as a union of intersections of three sets, with one set chosen from each of the pairs \(\{ A,\,\overline{A} \}\), \(\{ B,\,\overline{B} \}\), and \(\{ C,\,\overline{C} \}\). For example, the set shown in the figure below is equal to \((\overline{A} \cap \overline{B} \cap \overline{C}) \cup (A \cap \overline{B} \cap \overline{C}) \cup (\overline{A} \cap B \cap \overline{C}) \cup (\overline{A} \cap B \cap C)\).

This type of expression is called a disjunctive normal form (or DNF) for the set that it represents. We will see an analog of these in a different context in the chapter on Logic.

"I am not an astronaut."

The negation of a proposition \(p\), denoted in mathematics by \(\neg p\) and read as "not \(p\)", is the proposition "It is not the case that \(p\)". Note that \(\neg p\) can also be denoted by \(\overline{p}\) or \(\sim \! p.\)

For example, the negation of the proposition "Today is Friday." would be "It is not the case that, today is Friday." or more succinctly "Today is not Friday."

From the truth table it can be seen that exactly one of the two propositions \(p\) and \(\neg p\) is True and exactly one is False.

It can also be seen that the two propositions \(p\) and \(\neg (\neg p)\) always have the same truth value.

"I am a rock and I am an island."

Let \(p\) and \(q\) be propositions. The conjunction of \(p\) and \(q\), denoted in mathematics by \(p \land q\) and read as "\(p\) and \(q\)", is True when both \(p\) and \(q\) are True and is False otherwise.

Notice that the two propositions \(p \land q\) and \(q \land p\) always have the same truth value.

"They studied hard or they are extremely bright."

Let \(p\) and \(q\) be propositions. The disjunction of \(p\) and \(q\), denoted in mathematics by \(p \lor q\) and read as "\(p\) or \(q\)", is True when at least one of \(p\) and \(q\) are True and is False otherwise.

Notice that the two propositions \(p \lor q\) and \(q \lor p\) always have the same truth value.

"Take either 2 Advil or 2 Tylenol."

Let \(p\) and \(q\) be propositions. The exclusive disjunction of \(p\) and \(q\) (also known as xor), denoted in mathematics by \(p \oplus q\), is True when exactly one of \(p\) and \(q\) are True and False otherwise.

Notice that the two propositions \(p \oplus q\) and \(q \oplus p\) always have the same truth value.

"If you get a 100 on the final exam, then you earn an A in the class."

Let \(p\) and \(q\) be propositions. The conditional statement \(p \rightarrow q\), read as "if p then q", "p implies q", or, more formally, "the conditional with hypothesis p and conclusion q", is the proposition that is False when p is True and q is False, and True otherwise. The conditional statement \(p \rightarrow q\) is also called "the implication \(p \rightarrow q\)". Note that \(p \rightarrow q\) can also be denoted by \(p \Rightarrow q\) or \(p \implies q.\) In addition, there are many other ways to express the conditional \(p \rightarrow q\) in English, two of which are "p only if q" and "q if p".

Given propositions p and q, we can form three additional compound propositions that are related to the conditional \(p \rightarrow q\):

The exteneded truth table for the conditional and the three related propositions is shown below.

In the section on logically equivalent propositions we will discuss the bullet points in the preceding note in more detail.

We illustrate these four propositions with an example.

"It is raining outside if and only if it is a cloudy day."

Let \(p\) and \(q\) be propositions. The biconditional \(p \leftrightarrow q\), read as "p if and only if q", is the proposition that is True when p and q have the same truth value, and False otherwise. The biconditional is also called "the bi-implication". Note that \(p \leftrightarrow q\) can also be denoted by \(p \Leftrightarrow q\) or \(p \iff q.\)

From the truth table it can be seen that the two propositions \(p \leftrightarrow q\) and \(q \leftrightarrow p\) always have the same truth value.

It is important to contrast the conditional with the biconditional. Consider the conditional example "If you get a 100 on the final exam, then you earn an A in the class." This means that when you get a 100 on the final you also get an A in the class. The conditional represents a one-way contract: You earn an A in the class if you get a 100 on the final exam. There is nothing said about the result (the grade you earn in the class) if you do NOT meet the condition (get a 100 on the final exam).

As a biconditional the example would say "You get a 100 on the final exam if and only if you earn an A in the class." This becomes a two-way contract: You earn an A in the class if you get a 100 on the final, but you do not earn an A in the class if you do not get a 100 on the final.

To ensure that we can properly interpret a compund proposition involving multiple logical operations, we can either use parentheses or rely on operator precedence.

To evaluate a compound proposition, we start by evaluating

Note that exclusive-disjunction \(\oplus\) was left out of the discussion - this is because different sources assign it different precedences, usually just above or just below the disjunction \(\lor\). For this reason, it’s best to use parentheses whenever \(\oplus\) is present in a compound proposition.

For example, the compound proposition \(\neg p \lor q \land r \rightarrow s\) represents the same proposition as \(((\neg p) \lor (q \land r)) \rightarrow s\). Parentheses must be used if you want to represent a different proposition such as \((\neg p \lor q) \land (r \rightarrow s)\).

To find truth values of compound propositions, it is useful to break them up into smaller parts.

When creating your own truth table it is crucial to be systematic about ensuring you have all possible truth values for each of the simple propositions. Each simple proposition has two possible truth values, so the number of rows in the table should be \(2^n\) where \(n\) is the number of propositions. You should also consider breaking complex propositions into smaller pieces.

A proposition is a tautology if its truth value is always True. That is, a tautology is True for every possible interpretation of its propositional variables.

A proposition is called satisfiable if there is at least one interpretation for which the proposition is True.

A proposition is unsatisfiable if there is no interpretation for which the proposition is True.

A proposition is a contradiction if its truth value is always False. That is, a contradiction is False for every possible interpretation of its propositional variables. This is just another way of saying that it is unsatisfiable.

A proposition that is neither a tautology nor a contradiction is said to be a contingency since its truth value can be either True or False, contingent on the truth value assigned to its propositional variables.

The two compound propositions in the previous example are so important that they have their own names,

Two important logical equivalences are De Morgan’s Law. These describe how we "distribute" the \(\neg\) operator across the \(\land\) and \(\lor\) operators.

De Morgan’s Laws can be verified by creating truth tables for \(\neg (p \land q) \leftrightarrow \neg p \lor \neg q\) and \(\neg (p \lor q) \leftrightarrow \neg p \land \neg q\) to show that these propositions are True for every interpretation of \(p\) and \(q\).

Here is a collection of additional equivalencies of compound propositions. Each of these can be verified by constructing a truth table to show that the biconditional of the left-hand side and the right-hand side of the logical equivalence is true for all interpretations of the propositional variables.

Double Negation: + \[ p \equiv \neg (\neg p) \]

Commutative laws: \[ p \lor q \equiv q \lor p \] \[ p \land q \equiv q \land p \]

Associative laws: \[ p \lor (q \lor r) \equiv (p \lor q) \lor r \] \[ p \land (q \land r) \equiv (p \land q) \land r \]

Distributive laws: \[ p \lor (q \land r) \equiv (p \lor q) \land (p \lor r) \] \[ p \land (q \lor r) \equiv (p \land q) \lor (p \land r) \]

It is traditional to focus on negation \(\neg\), conjunction \(\land\), and disjunction \(\lor\) as the three primary logical operations. This is because any compound proposition can be rewritten in terms of these three operations and the propositional variables present in the original compound proposition.

One way to justify this is by using an expression in disjunctive normal form (DNF), which is a disjunction of one or more conjunctions, where only one of the conjunctions can be true for any interpretation of the propositional variables. This description should become clearer after reading the following example.

In some applications of propositional logic, it is more useful to find a logically equivalent expression for a given proposition that is written as a conjunction of several disjunctions. This conjunctive normal form (CNF) can be constructed as shown in the following example.

A predicate is a statement that includes one or more variables such that when values are assigned to the variables the predicate becomes a proposition.

Predicates are denoted as \(P(x)\) or \(Q(x,y)\) where \(P\) and \(Q\) represent the statements and \(x\) and \(y\) are variables. After a value is assigned to each variable, the predicate becomes a proposition which has a truth value. That is, we "evaluate" a predicate by substituting inputs into the variables and get a proposition as the output.

Consider the statements

Each of these statements considers a proposition over an entire population or set, called the domain, and quantifies how many elements (or people) in the set satisfy the proposition. To represent this idea, we use two main quantifiers, the universal quantifier and the existential quantifier.

The Universal Quantifier, \(\forall\), represents the statement "for all", "for every", "for each". When it comes before a statement, it means that statement is true for all values in the domain.

The Existential Quantifier, \(\exists\), represents the statement "there exists", "for some", "at least one". When it comes before a statement, it means the statement is true for at least one value in the domain.

Recall the previous example statements:

Let \(P(x)\) be the predicate "\(x^2 \geq 0\)". Then we write the statement as \(\forall x P(x)\), where the domain is the set of all integers. This quantified statement will be true since anytime you square a nonzero integer it is positive and \(0^2=0\).

Let \(Q(s)\) be the predicate "student \(s\) has a birthday in July". Then we write the statement as \(\exists s Q(s)\), where the domain is the set of all students in the class. This statement will be true as long as at least one student in the class has a birthday in July. It will be false, otherwise.

It is important to consider the negation of a quantified expression.

This is a universally quantified statement and can be expressed as \(\forall x P(x)\) where \(P(x)\) is the statement "\(x\) has taken Programming Fundamentals" and the domain consists of all the students in this class. The negation of the statement would be "It is not true that every student in this has taken Programming Fundamentals." Equivalently,

This is an existentially quantified statement expressed as \(\exists x \neg P(x)\).

This demonstrates that the negation of a universally quantified statement is an existential statement. In symbols, we have \(\neg \forall x P(x)\equiv \exists x \neg P(x)\).

Similarly, the negation of an existential statement is a universal statement. \(\neg \exists x P(x) \equiv \forall x \neg P(x)\).

The predicate of a quantified statement could be a compound statement. For instance,

This is written as \(\exists x (B(x) \land F(x))\) where \(B(x)\) is the proposition "\(x\) is big." and \(F(x)\) is the proposition "\(x\) is fluffy." and the domain is dogs. Negating this statement would give

\(\neg \exists x (B(x) \land F(x)) \equiv \forall x \neg (B(x) \land F(x)) \equiv \forall x (\neg B(x) \lor \neg F(x))\)

In words,

There are times it will take more than one quantifier to express a statement.

This statement contains both a universal and an existential quantifier. \(\forall x \exists y S(x,y)\) where \(x\) and \(y\) are integers and \(S(x,y)\) is the proposition \(x+y=0\). This statement means, if you have any integer \(x\) (for instance \(x=5\)) then you can find an integer \(y\) (for instance \(y=-5\)) such that \(x+y=0\).

The order of the quantifiers matters. \(\exists x \forall y S(x,y)\) would be

Note that in this statement you find an integer \(x\) so that when you add any integer \(y\) to it you always get 0.

The first statement, for all integers \(x\), there exists an integer \(y\) such that \(x+y=0\), is true. For any integer \(x\) you could choose \(y=-x\) and \(x+y=x+(-x)=0\). While the second statement, there exists an integer \(x\), such that for all integers \(y\), \(x+y=0\), is false.

To negate nested quantifiers, repeatedly apply De Morgan’s Laws of negating a quantifier and a predicate.

Namely, \(\neg \forall x P(x) \equiv \exists x \neg P(x)\) and \(\neg \exists x P(x) \equiv \forall x \neg P(x)\).

A bitwise operation is a Boolean operation that operates on the individual bits (\(0s\), or \(1s\)) of the operand(s) and are summarized

We summarize the truth tables for the bitwise boolean operators.

Logic circuits are important in designing the arithmetic and logic units of a computer processor. Consider the problem of adding two \(8\)-bit numbers in binary. In binary \(0+0=0\), and \(1+0=0+1=1\), but, as in decimal addition, in binary \(1+1=2\), which in binary will be a sum of \(0\) and a carry of \(1\) to the next significant column on the left. Thinking then of adding a specific column of two binary digits, say \(A\) and \(B\), involves as input the digits \(A, B\) and the carry in from the previous column say \(C_{in}\). The output will be the sum \(S\) and the carry out to the next column, say \(C_{out}\). These are the basic components of what is called a binary adder.

The logic table for binary addition based on the digital inputs \(A, B, C_{in}\), and digital outputs \(S\) and \(C_{out}\) is summarized in the table.

It can be shown that the logic for the outputs \(S\), and \(C_{out}\) is given by the following propositions \[ C_{out}=(A\land B)\lor \left(B\land C_{in}\right)\lor \left(A\land C_{in}\right)\] \[S=\left(\sim A\land \sim B\land C_{in}\right)\lor \left(\sim A\land B\land \sim C_{in}\right)\lor \left(A\land \sim B\land \sim C_{in}\right)\lor \left(A\land B\land C_{in}\right) \]

Implementing these logical outputs based on the inputs \((A,B, C_{in})\), is through the use of electronic circuits called logic gates.

The basic logic gates, are the Inverter or Not gate, the And gate, the Or gate and the Xor gate. The graphical representation for each is shown below.

We end this section by first analyzing logic circuits to give their outputs in terms of their input variables, and then, constructing logic circuits based on logical statements.

In the next two examples, we design logic circuits based on logical propositions. The idea is to work backward using order of operations from the right to the left.

The following rule of inference is called pure hypothetical syllogism, but we will use the less formal name transitivity. It is the basis of conditional proof in mathematics.

By applying transitivity multiple times, we can build a finite chain of implications of any length we want:

Recall that if we have propositions p and q, we can form the conditional with hypothesis \(p\) and consequent \(q\), written as \(p \rightarrow q\), as well as three other related conditionals.

Also, recall that \((p \rightarrow q) \equiv (\neg q \rightarrow \neg p)\). That is, \((p \rightarrow q) \leftrightarrow (\neg q \rightarrow \neg p)\) is a tautology. This means that the conditional is logically equivalent to its contrapositive. The conditional is NOT logically equivalent to either its converse or its inverse, as was shown using truth tables in the Logic chapter.

From the four conditionals we get two rules of inference and two fallacies. Together, these four argument forms are referred to as the mixed hypothetical syllogisms.

First, here are the two rules of inference.

Next, here are the two fallacies. They are included because they are very common errors to be aware of and to avoid.

The following image uses an Euler diagram of two sets \(A \subseteq B\) to explain why the converse error is a fallacy. The image can also be used to explain why the inverse error is a fallacy.

Suppose you were told that \(c\) is an element of \(B\) in the preceding image. Can you determine whether \(c\) is an element of \(A\), too?

Any tautology of the form \(p \rightarrow q\) can be used to define a rule of inference. In particular, we can define a rule of inference corresponding to the tautology \((p_{1} \land p_{2} \land \ldots \land p_{n})\rightarrow p_{1}\) for each integer \(n \geq 1\). This means that there are at least as many possible tautologies as there are natural numbers! How do we deal with infinitely many tautologies?

In general, there is a small number of rules of inference that are used in most proofs. Proofs often are built up to a large size by applying just a few rules of inference multiple times.

Here are some of the more commonly-used rules of inference. In the remix author’s opinion, it’s better to practice using these rules of inference rather than to focus on memorizing them as formal rules with special names.

There are many more rules of inference we could write down and give names to. Instead, we’ll just list a few tautologies.

The ceiling, \(f(x)=\lceil x\rceil\), function rounds up \(x\) to the nearest integer.

The ceiling function, used to compute the ceiling of \(x\), denoted, \( f(x)=\lceil x \rceil \) gives the smallest integer greater than or equal to \(x\).

For example, \( \lceil 3.4 \rceil =4\) and \( \lceil 3.7 \rceil =4\).

The floor \( f(x)=\lfloor x \rfloor \), rounds down \(x\) to the nearest integer.

The floor function, used to compute the floor of \(x\), denoted \( f(x)=\lfloor x \rfloor \), gives the greatest integer less than or equal to \(x\).

For example,\( \lfloor 3.4 \rfloor =3\) and \( \lfloor 3.7 \rfloor =3\).

The graphs of the ceiling (\( \lceil x\rceil\))and floor (\( \lfloor x \rfloor \)) functions are shown below.

The function \(h\left(x\right)=\max{\left(f\left(x\right)\right)},\ g(x))\) is evaluated at each \(x\) for which both \(f(x)\) and \(g(x)\) are defined by the function

\( h(x) =\max(f(x),g(x)) = \left\{ \begin{array}{c} f(x) \\ g(x) \end{array} \right. \begin{array}{c} \text{if } f(x)\text{ }\geq g(x) \\ \text{if } f(x) < g(x) \end{array} \)

So for example if \(f(x) =\ \sqrt x\), and \(g(x) =x^2\) then \(h(x)=\max(f(x),g(x))\), has \(h(1/4) =\max\) \( \left(\sqrt{\frac{1}{4}},\ \left(\frac{1}{4}\right)^2\right) \) \(=max\left(\frac{1}{2},\frac{1}{16}\right)=\frac{1}{2}\), and \(h(4) =\max\) \(\left(\sqrt4,\ 4^2\right)=\max(2,16)=16\). The graph of \(h(x) =\max(\sqrt x,\ x^2)\) over the interval \((0,2)\) is shown below.

The function \(h(x) =\min(f(x),g(x))\) is evaluated at each \(x\) for which both \(f(x)\) and \(g(x)\) are defined and is similar to the \(max\) function, but is defined by the minimum of \(f(x)\), and \(g(x)\) at each \(x\).

\( h(x) =\min(f(x),g(x)) = \left\{ \begin{array}{c} f(x) \\ g(x) \end{array} \right. \begin{array}{c} \text{if } f(x)\text{ }\leq g(x) \\ \text{if } f(x) > g(x) \end{array} \)

So for example if \(f(x) =\ \sqrt x\), and \(g(x) =x^2\) then \(h(x)=\min(f(x),g(x))\), has \(h(1/4) =\min\) \( \left(\sqrt{\frac{1}{4}},\ \left(\frac{1}{4}\right)^2\right) \) \(=\min\left(\frac{1}{2},\frac{1}{16}\right)=\frac{1}{16}\), and \(h(4) =\min\) \(\left(\sqrt4,\ 4^2\right)=\min(2,16)=2\).

The graph of \(h(x) =min(\sqrt x,\ x^2)\) over the interval \([0,2 \)], is shown below

To find the total number of outcomes for two or more successive events where both events must occur, multiply the number of outcomes for each event together. For instance, if you want to find the number of outcomes possible when you roll a die and toss a coin, you could use the product rule. It is important to note that the events must be independent, meaning one doesn’t effect the other.

This is called the product rule for counting because it involves multiplying to find a product. The product rule can be extended to more than two choices.

Video Example

The following video example features Dr. Joshua Roberts, Associate Professor of Mathematics at Georgia Gwinnett College.

Consider finding the total number of ways a particular event occurs from a variety of different mutually exclusive options (mutually exclusive means that the options do not have anything in common.) For instance, if you want to find the number of ways to pick, at random, a student enrolled in Discrete Math this semester, you could use the sum rule to add the number of students in each section of Discrete Math (assuming that no student is enrolled in more than one section).

This is called the sum rule for counting because it involves adding to find a total. The sum rule can also be extended to more than two choices.

Video Example

The following video example features Dr. Katherine Pinzon, Professor of Mathematics at Georgia Gwinnett College.

If your events are not mutually exclusive, to find the total number of possibilities use the subtraction rule.

Video Example

A permutation of a set of elements is an ordered arrangement of the elements. A permutation may involve every element of the set, or only some of the elements of the set.

Consider the first four letters of the English alphabet, \(A, B, C, D\).

By listing all possible permutations of \(A, B, C, D\), we can determine that there are 24 permutations of the letters taken four at a time, 24 permutations of the letters taken three at a time, and 6 permutations of the letters taken three at a time. But what if we wanted to find all the possible permutations of the twenty six letters \(A, B, C, D, \ldots , X, Y, Z\)? It is very time consuming to write out all possible permutations of the twenty six letters taken, say, twenty one at a time, so we will develop a method and formula for doing this.

In general, given a set of \(n\) objects, an ordered arrangment of \(r \le n\) of the objects is called an \(r\)-permutation or a permutation of \(n\) objects taken \(r\) at a time. We use the notation \(P(n,r)\) to represent the number of permutations of \(n\) objects taken \(r\) at a time. Note that \(_nP_r\) is another commonly used notation, especially on calculators.

Suppose we have \(n\) objects and want to construct a \(2\)-permutation of the objects. There are \(n\) possible choices for the first object, and once that object is chosen, there are \(n-1\) possible choices for the second object. We now use the product rule to conclude that there are \(n(n-1)\) ways to choose the two objects; note that the order of the choices matters here.

We can generalize this argument, informally, as follows: Suppose we have \(n\) objects and want to construct an \(r\)-permutation, where \(r \le n.\) There are \(n\) possible choices for the first object, \(n-1\) possible choices for the second object, and so on, until we have \(n-(r-1)\) possible choices for the \(r\text{th}\) object. Apply the product rule repeatedly to find that there are \( n(n-1)\cdots (n-r+1)\) \(r\)-permutations of the \(n\) objects.

Note that a formal proof can be done by using mathematical induction.

The previous code example gives evidence for the following theorem. Again, a formal proof can be done by using mathematical induction.

Video Example

A selection of objects from a set of \(n\) objects where order of selection does not matter is called a combination. Notice that each combination corresponds to a subset of the set of \(n\) objects.

Consider the letters \(A, B, C, D\) and choose three at a time where the order does not matter. In this case we are selecting a subset of size three instead of a sequence of length three. The sets \(\{ A, B, C \}\) and \(\{ B, C, A \}\) are just two ways of describing the same set since the order in which elements of a set are listed does not matter.

This shows that there are 4 combinations of 4 objects taken 3 at a time, 6 combinations of 4 objects taken 2 at a time, and 4 combinations of 4 objects taken 1 at a time.

In general, given a set of \(n\) objects, an unordered selection of \(r\le n\) of them is called an \(r\)-combination or a combination of \(n\) objects taken \(r\) at a time. We will denote this by \(C(n,r)\), read as '\(n\) choose \(r\)'. Note that \(_nC_r\) is commonly used by calculators.

Using this notation, we can write \(C(4,3) = 4\), \(C(4,2) = 6\), and \(C(4,1) = 4\).

Notice that \(C(4,3) = C(4,1)\); it may appear that this "just happens to be true", but in fact is an example of the next theorem. In this case, a combination of 4 objects taken 3 at a time corresponds to a combination of 4 objects taken 1 at a time - we can choose 3 of the 4 elements by "throwing out" the 1 element we don’t want to keep. That is, we choose the 3-element subset we care about indirectly by instead choosing the 1-element complement of the subset.

In general, there is always a one-to-one correspondence between the combinations of \(n\) objects taken \(r\) at a time and the combinations of \(n\) objects taken \(n-r\) at a time: Choosing \(r\) elements for a subset corresponds to choosing the \(n-r\) elements for the complement of the subset.

A formal proof of the theorem can be written by proving that, for any set \(S\), the function with domain and codomain \(\mathcal{P}(S)\) and that maps each subset of \(S\) to its complement is both injective and surjective.

Next, notice that every \(r\)-combination corresponds to \(P(r, r) = r!\) different \(r\)-permutations. That is, to select a \(r\)-permutation we could instead first select a \(r\)-combination without regard to order and then order the \(r\) elements.

As an example, suppose we have \(n\) objects and want to construct a \(3\)-permutation. We could instead first choose a \(3\)-combination of the objects. There are \(C(n,3)\) possible \(3\)-combinations. Once we have chosen a specific \(3\)-combination, we can reorder the 3 elements in \(P(3,3) = 3!\) ways. This argument shows that \(P(n,3) = C(n,3) \cdot P(3,3) = C(n,3) \cdot 3!\), so \(C(n,3) = \displaystyle \frac{P(n,3)}{3!}\).

We can generalize this argument for each natural number \(r \leq n\) to arrive at the next theoren.

A formal proof of the theorem can be done by using mathematical induction.

Video Example

Video Example

There are many different programming languages for programmers to choose from. Each language has its own advantages and disadvantages, and new languages gain popularity while older ones slowly lose ground. In this book, we use the Python 3 programming language. It is popular in both academia and industry, and was designed with education in mind.

PythonTutor is an environment for creating very short and simple Python programs and visualizing their execution. This enables beginners to visually see the data as it gets manipulated by the instructions.

Program files can contain source code and comments. Comments are not instructions for the computer to follow, but instead notes for programmers to read. Comments in Python start with a pound sign (#). Anything following the pound sign that is on the same line as the pound sign will not be executed. Often, at the very beginning of a program, comments are used to indicate the author and other information. Comments are also used to explain tricky sections of code or disable code from executing.

Exponential functions are of the form \(f\left(x\right)=b^x\), where \(b\) is the base and the variable \(x\) is in the exponent. The base \(b>0\) and \(b ≠ 1\). Properties of exponential functions come from properties of exponents. When the base \(b\) is greater than 1 the exponential function is increasing exponentially, as in the case \(f(x) = 2^x\).

\begin{array}{llcccccccccl} & x & -5 & -4 & -3 & -2 & -1 & 0 & 1 & 2 & 3 & 4 & 5 \\ & 2^x & \frac{1}{32} & \frac{1}{16} & \frac{1}{8} & \frac{1}{4} & \frac{1}{2} & 1 & 2 & 4 & 8 & 16 & 32 \end{array}

When the base \(b\) is less than 1 the exponential function is decreasing exponentially, as in the case \(f(x) = \left(\frac{1}{3}\right) ^x\).

\begin{array}{llcccccccccl} & x & -5 & -4 & -3 & -2 & -1 & 0 & 1 & 2 & 3 & 4 & 5 \\ & (\frac{1}{3})^x & 243 & 81 & 27 & 9 & 3 & 1 & \frac{1}{3} & \frac{1}{9} & \frac{1}{27} & \frac{1}{81} & \frac{1}{243} \end{array}

Logarithmic functions are the inverse functions corresponding to exponential functions and are used to solve exponential equations. For example, \(y=2^x\) is solved for \(x\) by inverting \(x=\log_2{y}\). Properties of logarithms follow from this relationship between exponentials and logarithms and properties of the exponentials.

We summarize three important properties of logarithms.

All other properties of logarithmic functions come from properties relating the logarithm as the inverse of the exponential and the equivalence of the logarithm \(a =\log_b m\) with \(b^a=m\).

When the base \(b\) is greater than 1, the logarithm function is increasing, as in the case \(f(x) = \log_2 x\).

\begin{array}{llllllcccccc} & x & \frac{1}{32} & \frac{1}{16} & \frac{1}{8} & \frac{1}{4} & \frac{1}{2} & 1 & 2 & 4 & 8 & 16 & 32 \\ & log_2 x & -5 & -4 & -3 & -2 & -1 & 0 & 1 & 2 & 3 & 4 & 5 \end{array}

When the base \(b\) is less than 1, the logarithm function is decreasing exponentially, as in the case \(f(x) = \log_{\frac{1}{3}} \ x\).

\begin{array}{llllllcccccl} & x & \frac{1}{243} & \frac{1}{81} & \frac{1}{27} & \frac{1}{9} & \frac{1}{3} & 1 & 3 & 9 & 27 & 81 & 243 \\ & \log_{\frac{1}{3}} x & 5 & 4 & 3 & 2 & 1 & 0 & -1 & -2 & -3 & -4 & -5 \end{array}