Discrete Math - The MKD Remix (CSC230 Version)

As a first example, the one-to-one correspondence between the set of uppercase English letters and the set of lowercase English letters is represented in the image. You can choose each letter in the upper row and follow the arrow down to the corresponding lowercase letter that it is paired with.

Notice that you could choose any lowercase letter in the image and follow the arrow up to its corresponding uppercase letter. This shows that the one-to-one correspondence is invertible in the sense that there is a second one-to-one correspondence that can "undo" what the first one-to-one correspondence does. This is why the arrows in the image point in both directions: It is natural to interpret the arrow as meaning "change case" in either direction.
In fact, the image for the one-to-one correspondence actually represents two functions: The first function is the uppercase-to-lowercase conversion that uses only the down arrows, and the second function lowercase-to-uppercase conversion that uses only the up arrows.

As a second example, consider the game "rock, paper, scissors." The image represents the one-to-one correspondence that pairs each element of the set \(\{ \text{"rock"},\,\text{"paper"},\,\text{"scissors"} \}\) with the element of the same set that it loses to.
Image credit: Remixer-created derivative of original work "THE_GAME_OF_KEN.(1910)-illustration-_page_315.png". According to Japanese Copyright Law (June 1, 2018 grant) the copyright on the original work has expired and is as such public domain. Also, the original work is in the public domain in the United States because it was published (or registered with the U.S. Copyright Office) before January 1, 1930.

For this one-to-one correspondence, it makes more sense to use arrows that point in only one direction. In the image, all the arrows point to the winner, so each arrow can be read as "loses to," for example "rock loses to paper".
Note 1: A one-to-one correspondence between a set and itself is called a permutation. You will see the term "permutation" again, used with a related but different meaning, in the Counting: Permutations and Combinations chapter.
Note 2: "Rock, paper, scissors" is a modern form of a very old game that appears to date back at least 1,800 years to China during the time of the Han dynasty. You can learn more about the history of "rock, paper, scissors" and other intrasitive games at this Wikipedia link. The image used in the Remix is derived from one that appears in a book published in 1910 that describes the Japanese game stone-ken or jan-ken.

Welcome to your first opportunity to use PythonTutor in this textbook!

The idea that it is "natural" to start counting from 0 may be familiar to you from coding: Both Java arrays and Python lists are indexed starting at 0.

Notice in the Python code below that the initial item in list L is the string "Discrete" at index 0, not index 1.

To step through the code, click on the "Next" button.

The multiplication principle, also called the product rule, is the following statement.

As an example, the number of possible strings of 2 characters with the first character being one of the 26 uppercase English letters and second character being one of the 10 Hindu-Arabic numerals is 260 = 26⋅10.

In this case, 26 and 10 are small integers so you can list all possibilities by arranging them in a table as shown in the image. What is important to notice is that this same technique (multiplying k and m) will work for much larger values of k and m, when creating such a table may be either not helpful or impossible.

Here are some examples of functions with their rules, domains, codomains, and ranges.

The code below shows two functions that are user-defined in Python.

Click on the "Next" button to step through the code.

What do you get when you "add" a Python object to itself?

Note that the answer depends on the object’s data type.

Click on the "Next" button to step through the code.

In this example, a Python function is defined recursively. The function takes any natural number input n (represented as an int in Python) and returns a value that we claim is \(5^n\).

Click on the "Next" button to step through the code.

Notice that each time the loop executes, a new instance of the function is created.

Later in the textbook, you will be able to prove that the power_of_5 function must return \(5^n\) for every natural number input n using a proof technique called mathematical induction.

The following examples show how to define a sequence from \(\mathbb{N}\) to \(\mathbb{N}\) using recursion. Notice that for each of the sequences we can compute the output value corresponding to any input value by repeatedly using the recurrence that relates a term to its preceding term in the sequence.

As an example, we can use the recurrence relations to compute \(b_{1}\) and \(c_{1}\) as follows. \[b_{1} = b_{0} + 2 = 3 + 2 = 5\] \[c_{1} = 2 c_{0} = 2 \cdot 3 = 6\]

The code below implements integer division for positive integers a and b.

Click on the "Next" button to step through the code.

Notice that each time the loop executes, the code prints an equation that shows that a is the sum of a whole number times b and a remainder r. The loop terminates when we compute a value for the remainder r that is both less than b and greater than or equal to 0.

Keep in mind that a graph is NOT the same as a drawing of the graph. In fact, a graph can usually be drawn in many different ways that may look very different. What is important is the connections, represented by the edges, between pairs of vertices.

In the image, two different drawings are shown for the same graph. Notice that in each drawing, the connections between pairs of vertices are the same: The only pair of vertices that is not connected by an edge is \(\{ C, D \}.\)

Also notice that there is no vertex drawn where the two edges cross in the 1st drawing on the left, so this graph has 4 exactly vertices: \(A,\) \(B,\) \(C,\) and \(D.\)

A graph can represent relationships between pairs of people.

Here is a graph that represents whether pairs of students are enrolled in at least one class together. Each of the 7 vertices represents a student, and each of the 7 edges represents a pair of students who are enrolled in a class together. The graph indicates that Adil and Elias are enrolled in at least one class together and that Elias and Maya are enrolled in at least one class together.

Here are some other examples of graphs.

A complete graph is a graph in which every pair of distinct vertices are the endpoints of exactly one edge. The image shows the complete graph on 4 vertices. Notice that two edges appear to "intersect" but there is no vertex drawn where the edges cross, so these edges do not have any points in common - as stated above, an edge contains only its endpoints.

A star graph is a graph that has one central vertex that is one of the endpoints of every edge in the graph. The image shows the star graph on 6 vertices. The star graph is one example of a tree, a graph in which for every pair of distinct vertices there is exactly one path of edges that can be used to connect the vertices. Some of the many applications of trees in computer science will be discussed in the Trees chapter.

Consider a fictitious state made up of \(10\) congressional districts with \(7\) thousand voters in each district. To win a district a party (Green or Blue) needs to win \(4\) thousand or more votes. Consider the following two districting map scenarios. In each scenario, the blue party earns \(28\) thousand votes, and the green party earns \(42\) thousand votes. In scenario \(A\), the blue party wins \(2\) out of \(10\) districts, but in scenario \(B\) it wins \(7\) out of \(10\) districts.

The following equations summarize how the preceding algorithm determines the digits in the base-ten expanded form numeral for the number 432.

\begin{equation} \begin{aligned} 432 {} & = 43 \cdot 10 + 2 & q {} & = 43 & r {} & = 2 & s & = [2] \\ 43 {} & = 4 \cdot 10 + 3 & q {} & = 4 & r {} & = 3 & s & = [2, 3] \\ 4 {} & = 0 \cdot 10 + 4 & q {} & = 0 & r {} & = 4 & s & = [2, 3, 4] \\ \end{aligned} \end{equation}

Notice that the items in \(s = [ r_{0}, \, r_{1}, \, r_{2} \)] are the numbers corresponding to the digits of the numeral \(“432”\) in reverse order, so \begin{equation} \begin{aligned} 432 & = r_{2} \cdot 10^{2} + r_{1} \cdot 10^{1} + r_{0} \cdot 10^{0} \\ & = 4 \cdot 10^{2} + 3 \cdot 10^{1} + 2 \cdot 10^{0} \end{aligned} \end{equation}

Notice that the algorithm is rewriting \(432\) as the sum \(2 + 10 \cdot (3 + 10 \cdot 4)).\)

The following equations summarize how the preceding algorithm determines the digits in the base-two expanded form numeral for the number 13.

\begin{equation} \begin{aligned} 13 {} & = 6 \cdot 2 + 1 & q {} & = 6 & r {} & = 1 & s & = [1] \\ 6 {} & = 3 \cdot 2 + 0 & q {} & = 3 & r {} & = 0 & s & = [1, 0] \\ 3 {} & = 1 \cdot 2 + 1 & q {} & = 1 & r {} & = 1 & s & = [1, 0, 1] \\ 1 {} & = 0 \cdot 2 + 1 & q {} & = 0 & r {} & = 1 & s & = [1, 0, 1, 1] \\ \end{aligned} \end{equation}

Notice that the items in \(s = [ r_{0}, \, r_{1}, \, r_{2} , \, r_{3} \)] are the numbers (in base-ten notation) corresponding to the digits of the numeral \(“(1101)_2”\) in reverse order, so \begin{equation} \begin{aligned} 13 & = r_{3} \cdot 2^{3} + r_{2} \cdot 2^{2} + r_{1} \cdot 2^{1} + r_{0} \cdot 2^{0} \\ & = 1 \cdot 2^{3} + 1 \cdot 2^{2} + 0 \cdot 2^{1} + 2 \cdot 2^{0} \end{aligned} \end{equation}

The algorithm rewrites \(13\) as \(1 + 2 \cdot (0 + 2 \cdot (1 + 1 \cdot 2))).\)
Again, notice that the items in the array \([1, 0, 1, 1\)] are listed in reverse order, so \(13 = (1101)_2\) where the base-ten numeral and the base-two numeral represent the same number, thirteen.

The following equations summarize how to determine the digits in the base-8 expanded form numeral for the number 100.

Note that for base-8 we use the eight digits ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, and ‘7’.

\begin{equation} \begin{aligned} 100 {} & = 12 \cdot 8 + 4 & q {} & = 12 & r {} & = 4 & s & = [4] \\ 12 {} & = 1 \cdot 8 + 4 & q {} & = 1 & r {} & = 4 & s & = [4, 4] \\ 1 {} & = 0 \cdot 8 + 1 & q {} & = 0 & r {} & = 1 & s & = [4, 4, 1] \\ \end{aligned} \end{equation}

Notice that \(s = [ 4, \, 4, \, 1 \)] are the numbers (in base-ten notation) corresponding to the base-8 digits of the numeral \(“(144)_8”\) in reverse order. You can verify that \(100 = 1 \cdot 8^{2} + 4 \cdot 8^{1} + 4 \cdot 8^{0}.\) This means that \(100 = (144)_8.\)

The following equations summarize how to determine the digits in the base-16 expanded form numeral for the number 500.

Note that for base-16, we need sixteen digits! It is traditional to use the ten Hindu-Arabic numerals followed by the first six uppercase English letters as the digits: ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’, ‘A’, ‘B’, ‘C’, ‘D’, ‘E’, and ‘F’. So \(10 = (A)_{16},\) \(11 = (B)_{16},\) \(12 = (C)_{16},\) \(13 = (D)_{16},\) \(14 = (E)_{16},\) and \(15 = (F)_{16}.\)
Note: Some programming languages like Python use the lowercase letters 'a' through 'f' instead of the uppercase letters.

The remainders stored in the array \(s\) are represented in base-ten notation, and will need to be replaced by the corresponding hexadecimal digits in the base-16 numeral for 500.

\begin{equation} \begin{aligned} 500 {} & = 31 \cdot 16 + 4 & q {} & = 31 & r {} & = 4 & s & = [4] \\ 31 {} & = 1 \cdot 16 + 15 & q {} & = 1 & r {} & = 15 & s & = [4, 15] \\ 1 {} & = 0 \cdot 16 + 1 & q {} & = 0 & r {} & = 1 & s & = [4, 15, 1] \\ \end{aligned} \end{equation}

As before, we have \(500 = 1 \cdot 16^{2} + 15 \cdot 16^{1} + 4 \cdot 16^{0},\) which you can verify is true. To write the base-16 numeral for 500, you need to replace "15" in base-ten by \((F)_{16}.\) So \(500 = (1F4)_{16}.\)

Let \(b\) be an integer greater than 1. Any positive integer \(n\) can be expressed uniquely in the form \[n = r_kb^k + r_{k - 1}b^{k-1} + \cdots + r_1b^1 + r_0b^0,\]where \(k\) is a nonnegative integer, \(r_0,r_1,\dots,r_k\) are nonnegative integers less than \(b,\) and \(r_k \neq 0.\)

Suppose that we have a procedure that consists of completing one step, and that the step can be chosen from either a first set of j possible ways to complete the step or from a second set of k possible ways to complete the step, and that no way of completing the step is in both the first and second sets. Then there are \(j+k\) ways to complete the procedure.

A student in a Capstone course can choose a project from three different professors. The professors have 3, 7, and 4 possible projects, and no project is on more than one professor’s list. How many possible projects can the student choose?

The student can pick out a project by choosing from the first professor, the second professor, or the third professor. Since no project is on more than one list, the sum rules says that there are \(3 + 7 + 4 = 14\) projects to choose from.

A card will be drawn from a standard 52-card deck.
How many ways can the card be an even number or a king?
Image credit: This is a cropped version of "Set Of Playing Card". George Hodan has released this “Set Of Playing Card” image under Public Domain license (CC0 Public Domain).

Suppose that we have a procedure that consists of completing one step, and that the step can be chosen from either a first set of j possible ways to complete the step or from a second set of k possible ways to complete the step, but that there are m possible ways of completing the step that are in both the first and second sets. Then there are \(j+k-m\) ways to complete the procedure.

In a group of students, 17 are enrolled in discrete mathematics, 13 are enrolled in probability, and 6 are enrolled in both discrete mathematics and probability.
How many students are in the group?

There are 17 students enrolled in discrete mathematics, but 6 of these students are enrolled in both discrete mathematics and probability. Likewise, there are 13 enrolled in probability, but 6 of these students are enrolled in both discrete mathematics and probability.
If we applied the addition rule by computing \(17+13 = 30\), this counts the 6 students who are enrolled in both discrete mathematics and probability twice, once as a student enrolled in discrete mathematics and then again as a student enrolled in probability. We can repair the count by subtracting 6 from the sum of 17 and 13; this will count each of the students exactly once. That is, the number of students in the group is \(17+13-6=24.\)
Alternative solution
First form three sets that have no students in common: Subtract 6 from each of 17 and 13 to find that there are \(17-6=11\) students in the set of students who are are enrolled in discrete mathematics but not probability, \(13-6=7\) students in the set of students who are enrolled in probability but not discrete mathematics, and 6 students in the set of students who are enrolled in both discrete mathematics and probability. Notice that the Sum Rule can be used because no student can be in two (or more) of the sets: There are \((17-6)+(13-6)+6 = 24\) students, which is the correct count.
Also note that \((17-6)+(13-6)+6 = 17+(-6)+13+(-6)+6 = 17 + 13 -6 =24,\) which is the computation used in first solution.

A tech company has 200 applicants for a position. Of the applicants, 150 were computer science majors, 43 were business majors, and 25 were double majors in both computer science and business.
How many applicants did not major in either computer science or business?

By the subtraction rule, there are \(150 + 43 - 25 = 168\) applicants that majored in computer science or business (or both). The number of applicants who did not major in either computer science or business is \(200 - 168 = 32.\)

Suppose that we have a procedure that consists of completing two steps, that there are k possible ways to complete the first step, and for each possible way of completing the first step, there are m possible ways to complete the second step. Then there are k⋅m ways to complete the procedure.

Suppose there are 27 computers in a computer center and each computer has 15 ports. How many different ways are there to choose a specific port?

Choosing a port means you first choose a computer and then a port on that computer. Since there are 27 computers and 15 ways to choose a port on a computer, there are \((27)(15) = 405\) ways to choose a port.

How many functions are there from a set \(A\) with \(m\) elements to a set \(B\) with \(n\) elements?
Click on "Hint" to reveal the hidden text.

You can use more than one of the rules to solve a problem.

How many bitstrings of length four start with 1 or end with 00?

First, a bitstring of length four that starts with 1 will be of the form \(1~*~*~*\), where there are two choices for each \(*\), either 0 or 1. Use the product rule to compute that there are \((1)(2)(2)(2) = 2^3 = 8\) bitstrings of this form.

Secondly, a bitstring of length four that ends with 00 will be of the form \(*~*~0~0\), so there are \((2)(2)(1)(1) = 2^2 = 4\) bitstrings of this form.

Thirdly, a bitstring of length four that starts with 1 and ends with 00 will be of the form \(1~*~0~0\), so there are \((1)(2)(1)(1) = 2\) bitstrings of this form.

Now use the subtraction rule to compute the number of bitstrings of length four that start with 1 or end with 00 (or both): \(8 + 4 - 2 =10.\)

If a card is drawn from a standard 52-card deck, how many ways can the card be black or a face card (that is, either a Jack or a Queen or a King)?

Suppose that we have a procedure that can be completed in n possible ways, but that for each way of completing the procedure there are d possible ways with the same outcome. Then there are \(\frac{n}{d}\) ways to complete the procedure.

Four students will sit around a circular table, but two seatings are considered "not different" whenever each student has the same left neighbor and right neighbor. How many different seatings are there?

First use the product rule to find that there are (4)(3)(2)(1) = 24 possible ways for the 4 students to sit (For example, there are 4 choices for the "North," then 3 choices remaining for the "East," then 2 choices remaining for the "South," and 1 choice remaining for the "West.") Next, notice that if all the students shifted one chair to the left once, twice, or thrice, they would all have the same neighbors that they originally had. This means that for each of the 24 ways the students can sit, 4 of those ways are not considered different.
Therefore, there are \(\frac{24}{4}\) or 6 different seatings.

The code below checks to see if \(5\) and \(0\) are elements of the set \(A = \{1,-2,0,1,-3\}.\) Since \(5 \not\in A\) and \(0 \in A,\) the code prints False followed by True.

The code below lists all of the elements of the set \(A = \{1,-2,0,1,-3\}.\)

Notice that 1 appears in the set once even though it appears in the roster twice.

The set \(\{x \in D: P(x)\}\) can be expressed in Python as {for x in D if P(x)}. For example, the code below defines the set \(B\) as the set of positive elements of the set \(A = \{1,-2,0,1,-3\}.\)

Consider the following set: \[\{x \in \mathbb{Z} : -2 \leq x < 4\}.\] This is the set of all integers \(x\) such that \(-2\) is less than or equal \(x\) and \(x\) is less than 4. Using the roster method, this set can be written as \[\{-2,-1,0,1,2,3\}.\]

Match each set described using set builder notation in parts (a) through (f) with the same set described using the roster method in parts (A) through (F).

If we let \(A = \{1,2,3,4,5,6\}\) and \(B = \{1,3,5,7,9\},\) then \[A \cup B = \{1,2,3,4,5,6,7,9\}.\]

In Python, we can compute the union of sets \(A\) and \(B\) in one of the following ways:

A.union(B)
A | B

If we let \(A = \{1,2,3,4,5,6\}\) and \(B = \{1,3,5,7,9\},\) then \[A \cap B = \{1,3,5\}.\]

In Python, we can compute the intersection of sets \(A\) and \(B\) in one of the following ways:

A.intersection(B)
A & B

Suppose that our universal set is \(U = \{0,1,2,3,4,5,6,7,8,9\},\) the set of all decimal digits. If we let \(A = \{1,2,3,4,5,6\}\) and \(B = \{1,3,5,7,9\},\) then \[\overline{A} = \{0,7,8,9\}\] and \[\overline{B} = \{0,2,4,6,8\}.\]

Suppose that our universal set is \(\mathbb{Z}.\) If we let \(E\) be the set of all even integers, then \(\overline{E}\) is the set of all odd integers.

Draw Venn Diagrams for each of these combinations of the sets \(A\), \(B\), and \(C\).

The code below prints the truth table for negation. Note that the values True and False are constants in Python, and that not p implements the negation \(\neg p\) in Python.

Try to predict the variable names, values, and data types at different steps in the execution. Use the Next button to check your answers.

The code below prints the truth table for conjunction. Try to predict the variable names, values, and data types at different steps in the execution. Use the Next button to check your answers.

The code below prints the truth table for disjunction. Try to predict the variable names, values, and data types at different steps in the execution. Use the Next button to check your answers.

Complete the code below by clicking one of the "edit" links then replacing \(#FIX ME#\) with an expression involving \(p\), \(q\), and some of the Python operators not, and, and or. Once correctly defined, the correct truth table for the conditional statement should print.

Complete the code below by clicking one of the "edit" links then replacing \(#FIX ME#\) with an expression involving \(p\), \(q\), and some of the Python operators not, and, and or. Once correctly defined, the correct truth table for the biconditional statement should print.

The code below reveals the truth table of the compound proposition:

\((p \land q) \lor \neg q\)

Recall: \(\neg q\) is mathematical shorthand for not q.

Edit the code above to reveal the truth value of the compound proposition:

\((p \lor \neg q) \land \neg p\)

Hint: You only need to change line 10.

Create a truth table for the compound proposition:

\((p \land q) \rightarrow (p \land r)\) for all values of \(p, q, r\).

It should have 8 rows - since there are three simple propositions and each one has two possible truth values.

\(p \lor \neg p\) is an example of a tautology.

\(p \land \neg p\) is an example of a contradiction.

This can be seen in the truth table.

Notice that the truth values for \(p \lor \neg p\) are all True and \(p \land \neg p\) are all False.

Given any proposition \(p\), the compound proposition \[p \lor \neg p\] is a tautology (that is, the compound proposition is always True.)

Given any proposition \(p\), the compound proposition \[p \land \neg p\] is a contradiction (that is, the compound proposition is always False.)

\(\neg (p \land q)\equiv \neg p \lor \neg q\)

\(\neg (p \lor q)\equiv \neg p \land \neg q\)

Suppose we have a truth table for an unknown compound proposition. Perhaps someone wrote the truth table but did not write down the expression for the compound proposition in the header of the rightmost column.

We can write a new compound proposition that is equivalent to the unknown one, using the propositional variables \(p\), \(q\), and \(r\) and the logical operators \(\neg\), \(\land\) and \(\lor\) as follows:

For the truth table above, we have three rows with T in the rightmost column. The first of the three rows corresponds to \(p \land \neg q \land r\), which is only True if \(p\) is True, \(q\) is False, and \(r\) is True. In the same way, the second of the three rows corresponds to \(\neg p \land q \land \neg r\), and the third of the three rows corresponds to \(\neg p \land \neg q \land r\). We now form the disjunction of these three expressions. \[(p \land \neg q \land r) \lor (\neg p \land q \land \neg r) \lor (\neg p \land \neg q \land r)\]

This new compound proposition has a truth table that is the same as the one for the unknown proposition. This means that the expression we found is logically equivalent to the unknown proposition.

Consider the same unknown proposition we used in the previous example.

One way to find a CNF is as follows.

From the truth table above, we obtain the following DNF for the negation of the unknown proposition: \((p \land q \land r) \lor (p \land q \land \neg r) \lor (p \land \neg q \land \neg r) \lor (\neg p \land q \land r) \lor (\neg p \land \neg q \land \neg r)\).

Next, we negate the DNF, using De Morgan’s Laws, and simplify the resulting expression \[\neg [ (p \land q \land r) \lor (p \land q \land \neg r) \lor (p \land \neg q \land \neg r) \lor (\neg p \land q \land r) \lor (\neg p \land \neg q \land \neg r) ],\] which simplifies to the CNF we wanted to find, \[(\neg p \lor \neg q \lor \neg r) \land (\neg p \lor \neg q \lor r) \land (\neg p \lor q \lor r) \land (p \lor \neg q \lor \neg r) \land (p \lor q \lor r).\]

The last expression is logically equivalent to the unknown proposition.

The set \(\{ \neg , \land , \lor \}\) is functionally complete.

Let \(P(x)\) be the predicate \(x \leq 3\).

What are the propositions \(P(5)\) and \(P(2)\)? What are the truth values of \(P(5)\) and \(P(2)\)?

Let \(P(x)\) be the predicate "The sum of the first \(n\) positive odd integers is equal to \(n^{2}\)."

What are the propositions \(P(1{\small,}000)\) and \(P(1{\small,}000{\small,}000)\) ? Notice that code correctly outputs the two propositions as strings (of type str in Python). The predicate does not tell us whether the propositions it outputs are True or False.

Let \(Q(x,y)\) be the statement \(x-y=4\).

The Python code displays each of the three propositions \(Q(6,2)\), \(Q(1,5)\), and \(Q(-2,2)\) and describes their truth values.

Universal Quantifier \(\forall x, x + 1 \gt x\)

Let \(P(x)\) be the statement \(x + 1 \gt x\). Is this true for all integers x?

Universal Quantifier \(\forall x, x + x \gt x\)

Let \(P(x)\) be the statement \(x + x \gt x\). Is this true for all integers x?

Existential Quantifier \(\exists x, x^2 = 4\)

Let \(P(x)\) be the statement \(x^2 = 4\). Is this true for at least one integer x?

Existential Quantifier \(\exists x, x^3 = 4\)

Let \(P(x)\) be the statement \(x^3 = 4\). Is this true for at least one integer x?

For any predicate \(P(x)\) \[\neg \forall x P(x)\equiv \exists x \neg P(x)\] and \[\neg \exists x P(x) \equiv \forall x \neg P(x)\]

Using quantifiers, we write this statement as \(\exists x L(x)\) where \(L(x)\) is the proposition "\(x\) speaks Latin." and the domain is the students in the class. Its negation would be \(\forall x \neg L(x)\).

Find the negation of the statement "For all integers \(x\), \(x^2 \geq x\)."

Let \(Q(x,y)\) be the statement \(xy=0\). If the domain for both variables consists of all integers, what are the truth values of the following statements?

Find the negation of the statment "For all integers \(x\), there exists an integer \(y\) such that \(x=-y\)."

Using quantifiers, we write this statement as \(\forall x \exists y N(x,y)\) where \(N(x,y)\) is the proposition "\(x=-y\)." and the domain of \(x\) and \(y\) is the integers. Its negation would be \(\exists x \forall y \neg N(x,y)\).

Find the negation of the statement "Some student in the class will solve every practice problem."

Hint: Let \(x\) be a student in the class, \(y\) be a practice problem, and \(P(x,y)\) be the statement "student \(x\) has solved practice problem \(y\)".

Find the bitwise \(AND, OR, XOR\) for the following binary numbers,

\[ A = 111101\] \[ B = 001111\]

Using the truth tables for Boolean operators, where the results are noted in the bottom row, we have

Determine the output of the following logic circuit in terms of the input variables, \(p, q\), and \(r\).

Proceeding left to right, determine the output of the leftmost gates first using the basic gate outputs.

The output of the logic circuit is \( ( p \lor q)\land ( \neg p \lor \neg q)\)

Design a logic circuit for \((p\vee\lnot\ q)\land\lnot\ p\).

Working backwards from right to left we have the following sequence of gates

1) An AND gate \((p\vee\lnot\ q)\underline{\land} \lnot\ p\).

2) The inputs to the AND gate are \((p\vee\lnot\ q)\) and \(\lnot\ p\).

3) These inputs come from the output of an INVERTER, for \(\underline{\lnot}\ p\) and an OR gate \((p \underline{\vee}\lnot\ q)\).

4) There are two inputs to the OR gate \((p \underline{\vee}\lnot\ q)\), being \(p\), and the output of an INVERTER, \(\underline{\lnot} q\).

Putting these now in left to right order we obtain the following logic circuit.

Design a logic circuit for \(r\land (p\lor (r\land \neg q))\).

Working backwards from right to left we have the following sequence of gates

1) An AND gate \(r\underline{\land} (p\lor (r\land \neg q))\).

2) The inputs to the AND gate are \(r\) and \(p\lor (r\land \neg q)\).

3) The input, \(p\lor (r\land \neg q)\), comes from the output of an OR gate for \(p \underline{\lor} (r\land \neg q)\).

4) The inputs to the OR gate, \(p \underline{\lor} (r\land \neg q)\), are \(p\) and \((r\land \neg q)\), which is an AND gate.

5) The inputs to the AND, gate, \(r \underline{\land} \neg q\), are \(r\) and the output of an INVERTER, \(\underline{\neg} q\).

Putting these now in left to right order we obtain the following logic circuit.

This rule of inference corresponds to the tautology \(((p \rightarrow q) \land (q \rightarrow r)) \rightarrow (p \rightarrow r)\).

This rule of inference corresponds to the tautology \(((p \rightarrow q) \land p) \rightarrow q\).

This rule of inference corresponds to the tautology \(((p \rightarrow q) \land \neg q) \rightarrow \neg p\).

This rule of inference corresponds to replacing the conditional \(p \rightarrow q\) by its logically equivalent contrapositive \(\neg q \rightarrow \neg p\) in the tautology, which gives \(((\neg q \rightarrow \neg p) \land \neg q) \rightarrow \neg p,\) then applying modus ponens to this new tautology.

This rule of inference corresponds to the tautology \(((p \rightarrow q) \land (q \rightarrow r) \land (p \lor q)) \rightarrow r\).

This rule of inference corresponds to the tautology \(((p \lor q) \land \neg q) \rightarrow p\).

This rule of inference corresponds to the tautology \(((p \rightarrow q) \land (\neg p \rightarrow r)) \rightarrow (q \lor r)\).

Notice that this rule of inference can also be written as
\(\neg p \lor q\)
\(p \lor r\)
\(\therefore q \lor r\)
This form of resolution is important to automated theorem-proving.

This rule of inference corresponds to the tautology \((\neg p \rightarrow (q \land \neg q)) \rightarrow p\).

Note that this tautology is often written in the alternate form \(((\neg p \rightarrow q) \land (\neg p \rightarrow \neg q)) \rightarrow p\), which can be more useful in some contexts.

For each of the tautologies shown, write the argument form for the corresponding rule of inference. If needed, refer to Example 2 in this chapter to see how the argument, argument form, and tautology are related.

The following argument was used as an example in the Logic chapter.

Notice that the second proposition above involves a universally-quantified predicate: The universal quantifier “Anyone” is applied to the predicate “\(\rule{12mm}{.5pt}\) who earned a B.S. in Computer Science must have earned a C or better in Discrete Math.”

In this argument, you use one of the rules of inference for quantified predicates to create a proposition about Sarah from the universally-quantified predicate as follows.

This new argument is of the form

If \(a,\) \(b,\) and \(c\) are integers such that both \(a\) and \(b\) are divisible by \(c,\) then for any integers \(m\) and \(n\) the integer \(ma+nb\) must be divisible by \(c.\)
This statement can be rephrased as “If the integers \(a\) and \(b\) are multiples of the integer \(c\), then any sum of integer multiples of \(a\) and \(b\) must also be a multiple of \(c.”\)

Before starting the formal proof, let’s look at a specific example. The integers 10, 6, and 2 are such that both 10 and 6 are divisible by 2. Suppose we have a pair of integers that we will use as multipliers, say 11 and 7, to form a new number \((11)(10)+(7)(6).\) Is the new number also divisible by 2? The answer is obviously "Yes" since we can just simplify the sum and divide by 2, but how can we justify this for every choice of the pair of multipliers? Notice that we can factor 2 out of 10 and 6 in the sum that defines our new number: \[ (11)(10) + (7)(6) = (11)(5)(2) + (7)(3)(2) = [(11)(5)+(7)(3)](2) \] We can find the common factor of 2 and "factor it out" as if it were a variable. This appears to work no matter what values are chosen for the first three integers and the pair of multipliers, so should be generalizable to a formal proof.

For the formal proof, start by supposing that \(a,\) \(b,\) and \(c\) are integers such that both \(a\) and \(b\) are divisible by \(c.\) This means that there are integers \(q\) and \(t\) such that \[ a=qc \text{ and } b=tc \]

For any integers \(m\) and \(n\), we can rewrite the expression \(ma+nb\) as \[ ma+nb = m(qc)+n(tc) = (mq)c + (nt)c = (mq+nt)c \]

The last part of the extended equality shows that \(ma+nb\) is a multiple of \(c,\) that is, \(ma+nb\) is divisible by \(c.\)

This shows that the statement of the theorem is a True proposition.

Q.E.D.

Write a proof of the following statement: If \(a,\) \(b,\) and \(c\) are integers such that \(a\) is divisible by \(b\) and \(b\) is divisible by \(c,\) then \(a\) must be divisible by \(c.\)

Let \(n\) represent an integer.

If \(n^{2}\) is even, then the integer \(n\) is even.

It is easier to prove "if it’s not the case that the integer \(n\) is even, then it’s not the case that \(n^{2}\) is even," so start by supposing that it’s not the case that the integer \(n\) is even.

This means that \(n\) must be odd, so there is an integer \(q\) such that \[ n = 2q + 1\]

This in turn means that \[ n^{2} = (2q + 1)^{2} = 4q^{2} + 4q + 1 = 2(2q^{2} + 2q) + 1\]

The last part of the extended equality shows that \(n^{2}\) is odd: When \(n^{2}\) is divided by 2, the remainder is 1. That is, \(n^2\) is not even.

This shows that the contrapositive of the statement of the theorem, "if the integer \(n\) is not even, then \(n^{2}\) is not even" is a True proposition. Since every conditional and its contrapositive are logically equivalent, this argument proves that "If \(n^{2}\) is even, then the integer \(n\) is even" is a True proposition.

Q.E.D.

Prove the following statement: If \(n^{2}\) is odd, then the integer \(n\) is odd.

For every natural number \(n,\) there are natural numbers \(a,\) \(b,\) and \(c\) such that \(n = a^{2} + b^{2} + c^{2}.\)

In this case, we can simply compute values of the expression \(a^{2} + b^{2} + c^{2}\) until we find a "gap." \[ 0^{2} + 0^{2} + 0^{2} = 0 \] \[ 1^{2} + 0^{2} + 0^{2} = 1 \] \[ 1^{2} + 1^{2} + 0^{2} = 2 \] \[ 1^{2} + 1^{2} + 1^{2} = 3 \] \[ 2^{2} + 0^{2} + 0^{2} = 4 \] \[ 2^{2} + 1^{2} + 0^{2} = 5 \] \[ 2^{2} + 1^{2} + 1^{2} = 6 \] \[ 2^{2} + 2^{2} + 0^{2} = 8 \] \[ 2^{2} + 2^{2} + 1^{2} = 9 \] \[ 3^{2} + 0^{2} + 0^{2} = 9 \] Notice that you cannot write 7 as a sum of three squares of natural numbers (There may be other numbers that cannot be written in this form, too, but 7 is the least such number and we only need to find one counterexample.)

This proves the negation of the Claim, namely

This may seem like a strange conjecture to consider until you find out that every natural number \(n\) can be written as \(n = a^{2} + b^{2} + c^{2} + d^{2}\) for some natural numbers \(a,\) \(b,\) \(c,\) and \(d,\) and that this may have been known about 1,800 years ago.

There are no positive integers \(a\) and \(b\) such that \(\displaystyle{ \left( \frac{a}{b} \right)^{2} } = 2.\)

It may be helpful to write the proposition out in symbols: \[ \neg (\exists a \in \mathbb{Z}) (\exists b \in \mathbb{Z}) \left( a > 0 \land b>0 \land \left( \frac{a}{b} \right)^{2} = 2 \right) \]

To prove this proposition by contradiction, we ASSUME that its negation is True, that is we use the premise \[ \text{ Premise: } \neg \neg (\exists a \in \mathbb{Z}) (\exists b \in \mathbb{Z}) \left( a > 0 \land b>0 \land \left( \frac{a}{b} \right)^{2} = 2 \right) \] In words, we assume: There are integers \(a\) and \(b\) such that \(a > 0,\) \(b > 0,\) and \(\displaystyle{ \left( \frac{a}{b} \right)^{2} } = 2.\)

We know that we can reduce the fraction so that \(a\) and \(b\) have no common prime factors (You know how to do this - just divide both numerator and denominator by their greatest common divisor. In fact, we will prove that this can be done in the mathematical induction chapter later in the textbook, but for now just treat it like a "known fact".)

To eliminate the fraction we can rewrite the equation as \[ a^{2} = 2 b^{2} \]

From this new equation, \(a^{2}\) must be divisible by 2. Use the theorem we proved earlier in this section to conclude that \(a\) must be divisible by 2, too. This means that there is an integer \(q\) such that \(a = 2q.\) Substitute the last expression for \(a\) in the equation to get \[ (2q)^{2} = 2 b^{2} \] which we can rewrite as \[ 4 q^{2} = 2 b^{2} \] or \[ 2 q^{2} = b^{2} \] From this equation, \(b^{2}\) is divisible by 2, and we can conclude that \(b\) is divisible by 2, too.

So…​ we have positive integers \(a\) and \(b\) that have no common prime factors, and we have proven that \(a\) and \(b\) have a common prime factor, namely 2. We have arrived at a contradiction.

Apply the Contradiction Rule to infer that the premise must be False.

We have proven the following theorem.

Suppose that \(n\) and \(k\) are positive integers. If each of \(n\) objects is assigned to one of \(k\) categories, then at least one category contains at least \(\displaystyle{\left\lceil \frac{n}{k} \right\rceil}\) objects.

First, recall that \(\lceil x \rceil\) is the ceiling function whose output is the least integer that is greater than or equal to \(x\) (that is, \(\lceil x \rceil\) rounds a real number \(x\) up to the next greatest integer.) The graph of the function is shown in section 3 of this appendix.

Next, before starting a formal proof, let’s look at a specific example to understand what we need to prove. Suppose we want to assign 13 people to the 3 categories "high school student," "post-secondary student," and "other". It’s not hard to see that when we assign people to the categories, the sum of the numbers in the categories has to be 13, so at least one of the categories has at least \(5 = \displaystyle{\left\lceil \frac{13}{3} \right\rceil}\) people. That is, if each category had at most \(4 = \displaystyle{\left\lceil \frac{13}{3} \right\rceil - 1}\) people, then the sum of those numbers would be at most \((3)(4) = 12,\) but we know that the sum should be equal to 13 - this is a contradiction. You can formalize this argument to use \(n\) and \(k\) instead of the specific values 13 and 3, which will provide a formal proof using the "proof by contradiction" technique.

Now, to prove this proposition by contradiction, suppose that the conditional is False. That is, we assume that

So we are assuming that the negation of the last bulleted statement must be True, that is "Every category contains fewer than \(\displaystyle{\left\lceil \frac{n}{k} \right\rceil}\) objects" is True. You should verify that this is the correct negation by using De Morgan’s laws for quantifiers.

Label the categories with the integers \(1, 2, \ldots k\) and let the integers \(c_1, c_2, \ldots, c_k\) be the counts of objects in each of the categories, that is, assume that the number of objects assigned to category \(i\) is \(c_i.\) From the assumption, every \(c_i\) is less than or equal to \(\displaystyle{\left\lceil \frac{n}{k} \right\rceil} - 1.\) The total number of objects assigned to categories is therefore \[ c_1 + c_2 + \cdots + c_k \leq k \left( \displaystyle{\left\lceil \frac{n}{k} \right\rceil} - 1 \right) \]

For any real number \(x,\) it is true by definition of the ceiling function that \(\displaystyle{x \leq \left\lceil x \right\rceil < x+1}\)

This means that \[ c_1 + c_2 + \cdots + c_k \leq k \left( \displaystyle{\left\lceil \frac{n}{k} \right\rceil} - 1 \right) < k \left( \displaystyle{\left( \frac{n}{k} + 1 \right)} - 1 \right) \] and the expression on the right simplifies to \(n.\)

So the number of objects assigned to the categories must be strictly less than \(n,\) but we also have as a premise that all \(n\) objects were assigned. This is a contradiction.

Apply the Contradiction Rule to infer that it is False that the last bulleted statement is False, that is, conclude that the conditional statement of the theorem must be True.

We have proven the theorem.

Let’s prove the following theorem: \[ \text{If \(n\) is an integer, then \(n(n+1)\) is an even integer.} \]

Consider the following two cases:

Since the statement "\(n\) is an odd integer or \(n\) is an even integer" must be True no matter what value the integer \(n\) has, this shows that the statement of the theorem is a True proposition.

Q.E.D.

Consider the sequence \(a_n=3n+1\) defined for all natural numbers \(n.\) The first 5 terms of this sequence are shown below.

\(a_0=\ 3\left(0\right)+1=1\)

\(a_1=\ 3\left(1\right)+1=4\)

\(a_2=3\left(2\right)+1=7\)

\(a_3=3\left(3\right)+1=10\)

\(a_4=3\left(4\right)+1=13\)

Notice that this sequence can be defined recursively using a recurrence relation : \[a_0=1 \text{ and } a_n=a_{n-1}+3 \text{ for } n \in \mathbb{N}_{>0}.\] So

\(a_0=1\)

\(a_1=a_{1-1}+3=a_0+3=1+3=4\)

\(a_2=a_{2-1}+3=a_1+3=4+3=7\)

\(a_3=a_{3-1}+3=a_2+3=7+3=10\)

\(a_4=a_{4-1}+3=a_3+3=10+3=13\)

Notice that an arithmetic sequence is determined by an initial term and a common difference. The arithmetic sequence \(a_n=3n+1\) is the sequence with initial term \(a_0=1\) and common difference \(d=3\). The general arithmetic sequence is \(a_n=c + d\cdot n\) with initial term \(c\) and common difference \(d.\)

Consider the sequence \(b_n=2\cdot\ 3^n\) defined for all natural numbers \(n.\) The first 5 terms of this sequence are shown below.

\(b_0=2\cdot\ 3^0=2\)

\(b_1=2\cdot\ 3^1=6\)

\(b_2=2\cdot\ 3^2=18\)

\(b_3=2\cdot\ 3^3=54\)

\(b_4=2\cdot\ 3^4=162\)

Notice that this sequence can be defined recursively using a recurrence relation : \[b_0=2 \text{ and } b_n=3\cdot b_{n-1} \text{ for } n \in \mathbb{N}_{>0}.\] So

\(b_0=2\)

\(b_1=3\cdot b_{1-1}=3\cdot2=6\)

\(b_2=3\cdot b_{2-1}=3\cdot6=18\)

\(b_3=3\cdot b_{3-1}=3\cdot18=54\)

\(b_4=3\cdot b_{3-1}=3\cdot54=162\)

Notice that a geometric sequence is determined by an initial term and a common ratio. The geometric sequence \(b_n=2\cdot\ 3^n\) is the sequence with initial term \(b_0=2\) and common ratio \(r=3\). The general geometric sequence is \(b_n=c \cdot r^n\) with initial term \(c\) and common ratio \(r.\)

The factorial of a natural number can be treated as a term of a sequence, called the factorial function. The commonly-used notation for a term of this sequence is \(n!\) and the sequence is defined as \[n! = n \cdot (n-1) \cdots 2 \cdot 1\] with \(1! = 1\) and \(0! = 1.\)

Notice that the factorial can be defined a bit more precisely by using the recurrence relation \[0!=1 \text{ and } n!=n\cdot (n-1)! \text{ for } n \in \mathbb{N}_{>0}.\] So the first few values of the factorial are

\(0!=1\)

\(1!=1\cdot (1-1)!=1\cdot1=1\)

\(2!=2\cdot (2-1)!=2\cdot1=2\)

\(3!=3\cdot (3-1)!=3\cdot2=6\)

\(4!=4\cdot (4-1)!=4\cdot6=24\)

The Fibonacci sequence can be defined recursively as \[f_{0}=0, \, f_{1}=1, \text{ and } f_{n} = f_{n-1} + f_{n-2} \text{ for } n \geq 2.\]

\(f_{2} = f_{2-1} + f_{2-2} = f_{1} + f_{0} = 1+0 = 1\)

\(f_{3} = f_{3-1} + f_{3-2} = f_{2} + f_{1} = 1+1 = 2\)

\(f_{4} = f_{4-1} + f_{4-2} = f_{3} + f_{2} = 2+1 = 3\)

\(f_{5} = f_{5-1} + f_{5-2} = f_{4} + f_{3} = 3+2 = 5\)

\(f_{6} = f_{6-1} + f_{6-2} = f_{5} + f_{4} = 5+3 = 8\)

\(f_{7} = f_{7-1} + f_{7-2} = f_{6} + f_{5} = 8+5 = 13\)

Note: The definition used in this textbook matches the ones used in several textbooks, but be warned that other may use definitions that are slightly different (e.g., some sources state the initial values as \(f_{0}=1\) and \(f_{1}=1.\)

Consider the sequence \(p_{n}(x)\) of functions that are defined for real number inputs \(x.\)

\(p_{0}(x) = 1,\) that is, the constant function 1,

\(p_{1}(x) = x,\)

\(p_{2}(x) = x^{2},\)

\(p_{3}(x) = x^{3},\)

and in general,

\(p_{n}(x) = x^{n}.\)

This is the sequence of \(n\)th power functions. The subscript of each of the functions matches the power that the input, \(x,\) will be raised to.

Notice that we can define the sequence recursively by \[p_{0}(x)=1, \, f_{1}=1, \text{ and } p_{n}(x) = x \cdot p_{n-1}(x) \text{ for } n \geq 1.\]

The set of well-formed formulas is defined recursively as follows:

A rooted tree is a type of graph. Graphs are described informally in the Introducing Discrete Mathematics chapter.

The set of rooted trees, is defined recursively as follows.

The preceding image shows the basis step and represents, in part, the results of the first and second uses of the recursion step. In the image, the new root nodes created at each recursion step appear at the top of the newly-created rooted trees. In each rooted tree, edges are treated as if they are directed “down,” away from the new root node; this will be discussed in more detail in the Trees chapter.

Notice that infinitely-many rooted trees are constructed at each use of the recursion step, so we cannot show all the rooted trees produced at any step other than the basis step. Also, we would need to complete infinitely many steps to construct all possible rooted trees, but any one particular rooted tree you want to construct will be produced after only finitely many uses of the recursion step.

Consider again the Fibonacci numbers, but this time given by a function \(f(n)\) where \(f(0)=0\), \(f(1)=1\) and \(f(n)=f(n-1)+f(n-2)\) for integers \(n \geq 2.\)

Applying the formula gives \begin{align*} f(2)&=f(1)+f(0)=1+0=1\\ f(3)&=f(2)+f(1)=1+1=2\\ f(4)&=f(3)+f(2)=2+1=3\\ f(5)&=f(4)+f(3)=3+2=5\\ f(6)&=f(5)+f(4)=5+3=8\\ \end{align*} Thinking of this as a recurrence relation we would write \(f_0=0, f_1=1\) and \(f_n=f_{n-1}+f_{n-2}\). Generating the sequence \({0,1,1,2,3,5,8,\ldots}\).