This page attempts to provide a summary of all of the discrete structures that will be used in this class.

1 Propositional logic

What in programming is called a Boolean expression (i.e., an expression that evaluates to either true or false) is called a proposition in mathematical logic. When propositions are represented by a symbol, that symbol is almost always a single upper-case letter, optionally with a numeric subscript, like P or P_{23}.

There are two logical values and many logical operators; the three best known operators are shown in the following table together with various symbols used to represent them.

Concept	Java/C++	Python	This class	Bitwise	Other
true	true	True	\top or 1	-1	T, tautology
false	false	False	\bot or 0	0	F, contradiction
not P	!p	not p	\lnot P or \overline{P}	~p
P and Q	p && q	p and q	P \land Q	p & q	P Q, P \cdot Q
P or Q	p || q	p or q	P \lor Q	p | q	P + Q

\lnot has higher precedence than \land and \lor; thus (\lnot P \land Q) means \big((\lnot P) \land Q\big) not \color{darkred} \big(\lnot (P \land Q)\big). It is typical not to define the precedence of \land and \lor compared to one another, and to require parentheses if they both appear together; thus \color{darkred} (P \land Q \lor R) has undefined meaning and must not be written; use \big((P \land Q) \lor R\big) or \big(P \land (Q \lor R)\big) instead.

Because \land and \lor are associative, it does not matter in what order an expression like (P \land Q \land R) is evaluated; it is equivalent to both \big((P \land Q) \land R\big) and \big(P \land (Q \land R)\big).

We also discuss other boolean operators in this class, including \rightarrow, \oplus, and \leftrightarrow, as well as many properties of and techniques for manipulating logical expressions.

2 First-order Logic

A function that evaluates to either true or false is called a predicate. The variables used in a predicate are almost always represented by a single lower-case letter, optionally with a numeric subscript, like x or x_{23}.

The notation \forall x \in S \;.\; P(x) is read for all x in S, P(x), where S is a set and P is a predicate. The full expression is called a universally quantified statement and is itself a proposition, which is true if and only if P(x) is true for every x in S. If S is empty, \forall x \in S \;.\; P(x) is trivially true.

The notation \exists x \in S \;.\; P(x) is read there exists some x in S such that P(x), where S is a set and P is a predicate. The full expression is called an existentially quantified statement and is itself a proposition, which is true if and only if P(x) is true for at least one x in S. If S is empty, \exists x \in S \;.\; P(x) is trivially false.

A variable defined by a quantifier is considered to be bound from the period following the quantifier until the end of the expression, or until the end of the parenthetical in which the quantifier appeared; that portion of the expression is called the variable’s scope. A variable must not be bound more than once inside the same scope.

A quantifier may omit the set, as \forall x \;.\; P(x); in this usage there is an implicit set, sometimes called the domain or the universe of discourse, which the variable is assumed to be quantified over. Quantifiers in this form may only be used if the domain is specified or may be inferred from context.

Adjacent quantifiers may be combined with commas as a shorthand, but only if they are the same quantifier; \forall and \exists cannot be combined.

Quantifiers have lower precedence than any propositional logic operator.

We also discuss the quantifier \nexists and various properties of quantifiers and quantified statements in this class.

3 Set

A set is a value whose only property is having other values as its members. The most common representation of a set is as its members written between braces. The members of a set have no position, order, number of times appearing in the set, or any other properties beyond being a member of the set.

The number of distinct members of a set S is called the set’s cardinality and is denoted |S|. A set with cardinality 1 is sometimes called a singleton set.

The empty set has no members and is denoted either \{\} or \emptyset. Note that \emptyset (the empty set, also called the null set) is a different symbol than 0 (zero) or \phi (the Greek letter phi).

The expression x \in S is true if and only if x is a member of S (and thus only if S is a set). x \notin S = \lnot(x \in S).

A set can be defined based on any predicate using set-builder notation: \big\{ f(x) \;\big|\; P(x)\big\} is the set of all f(x) where P(x) is true.

The following set operators are defined:

Union

S \cup T = \big\{x \;\big|\; (x \in S) \lor (x \in T)\big\}

Intersection

S \cap T = \big\{x \;\big|\; (x \in S) \land (x \in T)\big\}

Set Difference

S \setminus T = \big\{x \;\big|\; (x \in S) \land (x \notin T)\big\}

The following set-comparison predicates are defined:

Subset

S \subseteq T = \forall x \in S \;.\; x \in T

Proper Subset

S \subset T = (S \subseteq T) \land (S \ne T)

Superset

S \supseteq T = T \subseteq S

Proper Subset

S \supset T = T \subset S

The power set of another set S is the set of all the subsets of S. The power set is denoted \mathcal P(S) or pow(S) and can also be written \{ T \;|\; T \subseteq S\}.

\big|\mathcal P(S)\big| = 2^{\big|S\big|}.

The number of distinct k-member subsets of a n-member set is denoted \displaystyle{ n \choose k }, read n choose k, and is equal to \displaystyle{ n! \over (n-k)! k! }, where x! is the factorial of x.

4 Sequence

A sequence or tuple is a value which contains zero or more other values inside it, commonly called its elements or items. The elements of a sequence are in a specific order, and each may appear any number of times. The most common representation of a sequence is as its elements written in order, left to right, between parentheses.

In computing it is somewhat more common to use the term sequence when all of the elements are taken from the same set and tuple when they are taken from different sets. However, this tradition is not universally observed. We use both terms interchangeably in this course.

The number of elements of a sequence is called the sequence’s length. A sequence with length 1 is sometimes called a singleton sequence.

The empty sequence can be denoted (), \epsilon, or \varepsilon. Note that \epsilon (Greek letter epsilon, the empty sequence) and \in (the set member-of operator) are distinct symbols. The symbols \epsilon and \varepsilon are both lower-case Greek epsilons, just written in two different ways. Because epsilon is also a common symbol in computing (though not in this class) for a small nonzero value, it is useful to have two different epsilon symbols to choose from.

A sequence of length 2 is called a pair. A sequence of length 3 is sometimes called a triple, but that term is not commonly used in computing. There are names for longer sequences too, but they are rarely used.

If two sequences have the same elements but in different order, they are called permutations of one another. The number of permutations of a sequence is the factorial of the length of the sequence divided by the product of the factorials of the number of copies of each value in the sequence.

The Cartesian product of two sets S \times T is the set of all pairs where the first element comes from S and the second from T; that is, S \times T = \big\{(s,t) \;\big|\; s \in S \land t \in T\big\}. Cartesian product is commonly treated as a variable-arity operator, such that S \times T \times U is a set of triples but (S \times T) \times U and S \times (T \times U) are both sets of pairs.

The Cartesian power is defined analogously to the power in mathematics: S^k = \overbrace{S\times S\times\dots\times S}^{k\text{~}S\text{s}}. In other words, S^k is the set of all sequences of length k where all elements of each sequence in the set are members of S.

For all finite sets S and T, |S^k| = |S|^k and |S \times T| = |S| \cdot |T|

The Kleene star is the union of all Cartesian powers, S^* = S^0 \cup S^1 \cup S^2 \cup S^3 \cup \dots. In other words, S^* is the set of all sequences where all elements of each sequence in the set are members of S. More formally, S^* = \big\{x\;\big|\;\exists k \in \mathbb N \;.\; x \in S^k\big\}.

In most (but not all) contexts, a value and a singletone sequence containing just that value are treated as being equal (i.e. x = (x)). There is no standard way of determining which context is being used.

5 Integer

The set of all integers is denoted \mathbb Z. It is an infinite set, meaning it has infinitely many members.

The set of all non-negative integers is denoted \mathbb N.

The set of all positive integers is denoted \mathbb Z^+ or \mathbb N^+. In general, a superscript + after a set means only the positive elements and a superscript - means only the negative elements.

In computing¹, the natural numbers refers to \mathbb N.

An integer x is a divisor of an integer y if and only if y \div x is an integer. Factor is a synonym for divisor². If x is a divisor of y, then we say that y is divisible by x and y is a multiple of x.

We can denote the concept x is a divisor of y as x|y, but this notation is unusual in computing because | is already used for so many other concepts (e.g, for absolute values, cardinality, set-builder notation, conditional probability, complex magnitude, determinant, etc).

0 is not a divisor of any integer, not even itself. Every other integer is a divisor of 0.

The trivial divisors of any nonzero integer x are -x, -1, 1, and x. An integer x is prime if it is greater than 1 and has no non-trivial divisors.

The fundamental theorem of arithmetic states that every positive integer x has one and only one prime factorization, meaning a product of one or more prime numbers equaling x.

A prime factorization may include the same prime number more than once; the number of times a prime number p appears in the prime factorization of x is called the multiplicity of p in that factorization.

The greatest common divisor (GCD) of a set of integers is the largest integer that is a divisor of all of the integers in the set. If the GCD of two integers is 1, then the integers are called co-prime or relatively prime.

The notation x = y \mod q means x and y have the same remainder when divided by q, and can be formally expressed as \exists a,b,c \in \mathbb Z \;.\; (x = aq+c) \land (y = bq+c).

6 Rational

Any number that can be constructed by dividing one integer by another is called a rational number. The set of all rational numbers is denoted \mathbb Q.

Every rational number q can be written as a unique x \div y, where y is a positive integer, x is an integer, and x and y are co-prime.

There are numbers that are not rational numbers, such as \pi, but which belong to the set of real numbers, \mathbb R.

\mathbb R \supset \mathbb Q \supset \mathbb Z \supset \mathbb N.

The floor of any real number x, denoted \lfloor x \rfloor, is the largest integer that is not larger than x. The ceiling of any real number x, denoted \lceil x \rceil, is the smallest integer that is not smaller than x.

7 Function

A function maps a sequence (or single value, which is treated as equivalent to a singleton sequence for this purpose) to a value. It does this in a deterministic, single-valued way; for example, if f(2,3,4) = 11 once, then (for that f) f(2,3,4) is only and always 11, never any other value.

Each function is defined with a domain, the set of sequences to which it may be applied; and a co-domain, the set of values it may result in. That function f is defined with domain D and co-domain C can be denoted f:D\rightarrow C.

A function need not be defined for all values in its domain, nor be able to produce all values in its co-domain. If a function is defined with a domain, co-domain, and formula then it is defined only for that subset of the domain where the formula produces a member of the co-domain. The subset of the co-domain that is mapped to by at least one element of the domain is called the range of the function.

A function is called a predicate if its co-domain is the set \{\top,\bot\}, where \top represents the concept true and \bot represents the concept false. This is equivalent to the definition of predicate given in First-Order Logic.

A relation is a generalization of a function that allows a single domain value to map to more than one co-domain value. Each relation can also be defined using

• a predicate indicating which domain + co-domain elements are related
• a set of sequences, called the graph of the relation

Note that the relation itself is neither the predicate nor the set, but the predicate and set can express the meaning of the relation.

A relation is called functional if it is a function; that is, each element of the domain is related to at most one element in co-domain.

A binary relation is a relation that resembles a single-argument function or two-argument predicate. Binary relations are by far the most common type of non-functional relation in computing.

Binary relations are often written as a formula defining their predicate, but with a special symbol instead of an equals sign, like R(x,y): x < y or R(x,y) \Coloneqq x<y for the less-than relation. Many different symbols are used, though typically only one in any given document; the most common are :, \triangleq, \coloneqq, \Coloneqq, and \overset{\text{def}}{=}.

There are a large number of vocabulary terms to know about functions and relations.

A function f:D\rightarrow C is

• total if f(x) is defined for all x \in D.
• partial means either total or not total and is used in contexts where most functions are assumed to be total to identify subcontexts where that assumption does not apply.
• injective or 1-to-1 if f(x) = f(y) implies x = y.
• surjective or onto if the co-domain is equal to the range.
• bijective, invertible, or a 1-to-1 correspondence if it is total and injective and surjective.

A binary relation defined by predicate R(x,y) is

• reflexive if every x is related to itself; that is, \forall x\;.\; R(x,x)
• irreflexive if no x is related to itself; that is, \forall x\;.\; \lnot R(x,x)
• transitive if \forall x,y,z\;.\; \big(R(x,y) \land R(y,z)\big) \rightarrow R(x,z)
• symmetric if \forall x,y\;.\; R(x,y) \rightarrow R(y,x)
• asymmetric if \forall x,y\;.\; R(x,y) \rightarrow \lnot R(y,x).
• antisymmetric if \forall x,y\;.\; \big((x \ne y) \land R(x,y)\big) \rightarrow \lnot R(y,x)

Note that a relation is asymmetric if and only if it is both antisymmetric and irreflexive.

Several combinations of the above properties have special names:

• an equivalence relation is reflexive, transitive, and symmetric
• a partial order is transitive and antisymmetric
  • a strict partial order is also irreflexive, implying it is also asymmetric
  • a non-strict partial order is also reflexive
  • Note (confusingly) that it is possible for a partial order to be neither strict nor non-strict
• a total order is a partial order such that every pair of values is either related or is related in the reverse order; that is, \forall x,y\;.\; (x \ne y) \rightarrow \big(R(x,y) \lor R(y,x)).
  • total orders also have strict and non-strict variants.
  • note the overloaded use of the word total: total order is a type of binary relation; total is a property of some functions

8 Summation

The notation \displaystyle{ \sum_{x \in S} f(x) } is called summation notation and means the sum of all f(x) where x is an element of S.

By definition, the sum of an empty set is 0.

The notation \displaystyle{ \sum_{x = a}^{b} f(x) } is shorthand for \displaystyle{ \sum_{x \in S} f(x) } where S = \big\{ x \;\big|\; (x \in \mathbb Z) \land (x \ge a) \land (x \le b) \big\}.

The notation \displaystyle{ \prod_{x \in S} } and \displaystyle{ \prod_{x=a}^{b} } are defined similarly but as products, not sums, of their elements. The product of an empty set is defined to be 1.

n! is called the factorial of n and is defined to be \displaystyle{ \prod_{x=1}^{n} x }. Thus, 0! = 1 because it is the product of an empty set.

9 Logarithm

note: logarithms are not technically part of discrete mathematics, being instead a topic within continuous mathematics. However, they are widely used in computing and not universally understood by entering students, so we’ll cover them in this course.

The logarithm is a family of functions that are the inverses of exponentiation. It is defined by the following identity: \big(x^y = z\big) \equiv \big(\log_x(z) = y\big) The expression \log_x(y) is read the log base x of y.

Logarithms are defined for all positive bases except 1, though we almost always assume the base is greater than 1.

For any given base b > 1,

• \log_b : \mathbb R^+ \rightarrow \mathbb R is bijective
• \log_b is monotonically increasing; that is (x > y) \equiv \big(\log_b(x) > \log_b(y)\big)
  • (note if 0 < b < 1, \log_b is monotonically decreasing instead)
• \displaystyle{ \log_b(b^x) = x }
• \displaystyle{ b^{\log_b(x)} = x }
• \displaystyle{ \log_b(x y) = \log_b(x) + \log_b(y) }
• \displaystyle{ \log_b\left(\frac{x}{y}\right) = \log_b(x) - \log_b(y) }
• \displaystyle{ \log_b(x^y) = y \log_b(x) }
• \displaystyle{ \log_b(x) = \frac{\log_a(x)}{\log_a(b)} }

Logarithms have many other interesting properties and show up in many areas of computing; the above identities will be sufficient for this class.

---

1. In some other disciplines (not computing), the natural numbers refers to \mathbb Z^+ instead of \mathbb Z^+ \cup \{0\}. In computing if we need to name \mathbb Z^{+} we call it the positive integers or the whole numbers.↩︎

2. Usually. You can find various websites saying various A factor is like a divisor except X but they don’t agree on what the X is.↩︎