Intro Discrete Mathematics Notes

Xiyan Shao 2020/12/10

Personal notes for CSE20 - Discrete Mathematics for Computer Science. Taken Fall 2020, with professor Shachar Lovett. See Course Homepage

Sets

Recursive definition of sets

Basis step: Specify finitely many elements of \(S\)

Recursive step: Give a rule for creating a new element of \(S\) from known values existing in \(S\), and potentially other values.

String

The set \(\Sigma^*\)of strings over the alphabet \(\Sigma\) is defined recursively by

Basis step: \(\lambda \in \Sigma^*\) (where \(\lambda\) is the empty string containing no symbols)

Recursive step: \(w\in \Sigma^* \land x\in\Sigma \rightarrow wx \in \Sigma^*\).

Set operations

Set equality

When \(A\) and \(B\) are sets, \(A = B\) means \(∀x(x ∈ A\leftrightarrow x ∈ B)\)

Subset

When \(A\) and \(B\) are sets, \(A ⊆ B\) means \(∀x(x ∈ A → x ∈ B)\)

Proper subset

When \(A\) and \(B\) are sets, \(A\subsetneq B\) means \((A ⊆ B) ∧ (A = B)\)

Union

When \(A\) and \(B\) are sets, \(A ∪ B = \{x | x ∈ A ∨ x ∈ B\}\)

Intersection

When \(A\) and \(B\) are sets, \(A ∩ B = \{x | x ∈ A ∧ x ∈ B\}\)

Set difference

When \(A\) and \(B\) are sets, \(A - B = \{x | x ∈ A ∧ x \not∈ B\}\)

Disjoint sets

Sets \(A\) and \(B\) are disjoint means \(A ∩ B = ∅\)

Power set

When \(S\) is a set, \(P (S) = \{X | X ⊆ S\}\)

Cartesian product

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

Set-wise concatenation

\(A \circ B=\{a b \mid a \in A \text { and } b \in B\}\)

Sets of Integers

\(\mathbb N\) ⇒ The set of natural numbers, \(\{1,2,3,\cdots\}\)

\(\mathbb Z\) ⇒ The set of integers, \(\{\cdots,-2,-1,0,1,2,\cdots\}\)

\(\mathbb Z^+\)⇒ The set of positive integers \(\{1,2,3,\cdots\}\)

\(\mathbb Z^{\neq 0}\)⇒ The set of nonzero integers

Primes and rationals

When \(a\) and \(b\) are integers and \(a\) is nonzero, \(a\) divides \(b\) means there is an integer \(c\) such that \(b = ac\).

Symbolically, \(F(a, b)=\exists c \in \mathbb{Z}(b=a c)\) and is a predicate over the domain \(\mathbb{Z}^{\neq 0} \times \mathbb{Z}\).

Terminology: \(a\) is a factor of \(b\), \(a\) is a divisor of \(b\), \(b\) is a multiple of \(a\), \(a|b\).

Prime

An integer \(p\) greater than \(1\) is called prime means the only positive factors of \(p\) are \(1\) and \(p\). A positive integer that is greater than \(1\) and is not prime is called composite.

A formal definition of the predicate \(Pr\) over the domain \(\mathbb Z\) which evaluates to \(T\) exactly when the input is prime is

\[(x > 1) ∧ ∀a( ( a > 0 ∧ F (a, x) ) → (a = 1 ∨ a = x) )\]

Rationals

\(\mathbb Q\) ⇒ \((\{\frac{p}{q} \mid p \in \mathbb{Z} \text { and } q \in \mathbb{Z} \text { and } q \neq 0 )\}\), or \((\{x \in \mathbb{R} \mid \exists p \in \mathbb{Z} \exists q \in \mathbb{Z}^{+}(p=x \cdot q))\}\)

Division algorithm

Let \(n\) be an integer and \(d\) a positive integer. There are unique integers \(q\) and \(r\), with \(0 ≤ r < d\), such that \(n = dq + r\). In this case, \(d\) is called the divisor, \(n\) is called the dividend, \(q\) is called the quotient, and \(r\) is called the remainder. We write \(q = n \text{ div } d\) and \(r = n \mod d\).

Greatest common divisor

Let \(a\) and \(b\) be integers, not both zero. The largest integer \(d\) such that \(d\) is a factor of \(a\) and \(d\) is a factor of \(b\) is called the greatest common divisor of \(a\) and \(b\) and is denoted by \(\gcd(a, b)\).

Number representations

Base expansion and conversions

For \(b\) an integer greater than 1 and \(n\) a positive integer, the base \(b\) expansion of \(n\) is

\[((a_{k-1} \cdots a_{1} a_{0}))_{b}\]

where k is a positive integer, \(a_{0}, a_{1}, \ldots, a_{k-1}\) are non negative integers less than \(b, a_{k-1} \neq 0,\) and

\[n=a_{k-1} b^{k-1}+\cdots+a_{1} b+a_{0}\]

Base \(b\) fixed-width \(w\) expansion of \(n\) ⇒ could have leading zeros.

Base \(b\) fixed-width expansion of \(x\) with with integer part width \(x\) and fractional part width \(w'\)⇒

\[x \geq a_{w-1} b^{w-1}+\cdots+a_{1} b+a_{0}+c_{1} b^{-1}+\cdots+c_{w^{\prime}} b^{-w^{\prime}}\]

and

\[x<a_{w-1} b^{w-1}+\cdots+a_{1} b+a_{0}+c_{1} b^{-1}+\cdots+((c_{w^{\prime}}+1)) b^{-w^{\prime}}\]

Representing negative integers

Signed-magnitude ⇒\(([1 a_{w-2} \cdots a_{0})]_{s, w}\) where \(n=((a_{w-2} \cdots a_{0}))_{2, w-1}\)

Two’s complement ⇒ \(([1 a_{w-2} \cdots a_{0})]_{2 c, w}\)where \(2^{w-1}-n=((a_{w-2} \cdots a_{0}))_{2, w-1}\)

To represent \(–n\) in 2s complement with width \(w\)

Logics

Logic gates and circuits

\[\begin{array}{cc||c|c|c}&& \text { Conjunction } & \text { Exclusive or } & \text { Disjunction } \\\\p & q & p \wedge q & p \oplus q & p \vee q \\\\\hline T & T &T& F & T \\\\T & F & F & T & T \\\\F & T & F & T & T \\\\F & F & F & F & F\end{array}\]

\[\begin{array}{c||c}\text { Input } & \text { Output } \\\\ & \text { Negation } \\\\ p & \neg p \\\\ \hline T & F \\\\ F & T\end{array}\]

Compound proposition

Terminologies

Logically equivalent ⇒ same truth values for all settigns of truth values to their propostition variables

Tautology ⇒ compound proposition that evaluates to true for all settings of truth values to its propositional vaiables; it is abbreviated T

Contradiction ⇒ compound proposition that evaluates to false for all settings of truth values to its propositional variables; it is abbreviated F

Consistency ⇒ a collection of compound propositions is consistent means there is an assignment of truth values to the variables that makes all these propositions true.

Note: \(p\equiv q\) is NOT a compound proposition

CNF

A compound proposition is in conjunctive normal form (CNF) means that it is an AND of ORs of variables and their negations.

To write ⇒ Look for rows that are false.

DNF

A compound proposition is in disjunctive normal form (DNF) means that it is an OR of ANDs of variables and their negations.

To write ⇒ Look for rows that are true

Conditionals

Terminologies

The hypothesis of \(p → q\) is \(p\)

The antecedent of \(p → q\) is \(p\)

The conclusion of \(p → q\) is \(q\)

The consequent of \(p → q\) is \(q\)

The converse of \(p \rightarrow q\) is \(q \rightarrow p\)

The inverse of p \(\rightarrow q\) is \(\neg p \rightarrow \neg q\)

The contrapositive of \(p \rightarrow q\) is \(\neg q \rightarrow \neg p\)

Truth table

\[\begin{array}{cc||c|c|c|c|c} & & \text { AND } & \text { XOR } & \text { OR } & \text { Conditional } & \text { Biconditional } \\\\ p & q & p \wedge q & p \oplus q & p \vee q & p \rightarrow q & p \leftrightarrow q \\\\ \hline T & T & T & F & T & T & T \\\\ T & F & F & T & T & F & F \\\\ F & T & F & T & T & T & F \\\\ F & F & F & F & F & T & T\end{array}\]

The only way to make the conditional statement \(p → q\) false is to have \(p\) be true and \(q\) be false.

Important logical equivalences

\[\begin{aligned}p \leftrightarrow q \quad &\not\equiv \quad p \wedge q \\\\ \neg(p \leftrightarrow q) \quad &\equiv \quad p \oplus q \\\\ p \rightarrow q \quad &\equiv \quad \neg p \vee q \\\\ p \leftrightarrow q \quad &\equiv \quad q \leftrightarrow p \\\\ p \rightarrow q \quad &\not\equiv \quad q \rightarrow p \\\\ p \rightarrow q \quad &\not\equiv \quad \neg p \rightarrow \neg q \\\\ p \rightarrow q &\equiv \quad \neg q \rightarrow \neg p\end{aligned}\]

Predicates

A predicate is a function from a given set (domain) to \(\{T , F \}\).

A predicate can be applied, or evaluated at, an element of the domain.

Two predicates over the same domain are equivalent means they evaluate to the same truth values for all possible assignments of domain elements to the input.

The truth set of a predicate is the collection of all elements in its domain where the predicate evaluates to \(T\).

Notation: for a predicate \(P\) with domain \(X_{1} \times \cdots \times X_{n}\) and a \(n\)-tuple \(((x_{1}, \ldots, x_{n}))\) with each \(x_{i} \in X\), we write \(P((x_{1}, \ldots, x_{n}))\) to mean \(P((((x_{1}, \ldots, x_{n}))))\).

Quantifiers

The universal quantification of \(P (x)\) is the statement “\(P (x)\) for all values of \(x\) in the domain” and is written \(∀xP (x)\). An element for which \(P (x) = F\) is called a counterexample of \(∀xP (x)\).

The existential quantification of \(P (x)\) is the statement “There exists an element \(x\) in the domain such that \(P (x)\)” and is written \(∃xP (x)\). An element for which \(P (x) = T\) is called a witness of \(∃xP (x)\).

Quantifier version of De Morgan’s law

Proof

Strategies

Basics

Proof of universal by exhaustion

To prove that \(∀x P (x)\) is true when \(P\) has a finite domain, evaluate the predicate at each domain element to confirm that it is always \(T\).

Proof by universal generalization

To prove that \(∀x P (x)\) is true, we can take an arbitrary element \(e\) from the domain and show that \(P (e)\) is true, without making any assumptions about \(e\) other than that it comes from the domain.

Evidence for conjunction

To prove that \(p ∧ q\) is true, have two subgoals: subgoal (1) prove \(p\) is true; and, subgoal (2) prove \(q\) is true. To prove that \(p ∧ q\) is false, it’s enough to prove that \(p\) is false.

To prove that \(p ∧ q\) is false, it’s enough to prove that \(q\) is false.

Proof by cases

To prove \(q\), if we know that \(p_1 ∨ p_2\) is true, and we can show that \((p_1 → q)\) is true and we can show that \((p_2 → q)\), then we can conclude \(q\) is true

Proof of conditional by direct proof

To prove that the conditional statement \(p → q\) is true, we can assume \(p\) is true and use that assumption to show \(q\) is true.

Proof of conditional by contrapositive proof

To prove that the implication \(p → q\) is true, we can assume \(q\) is false and use that assumption to show \(p\) is also false.

Proof by Contradiction

To prove that a statement \(p\) is true, pick another statement \(r\) and once we show that \(¬p → (r ∧ ¬r)\) then we can conclude that \(p\) is true.

Induction

Proof by structural Induction

To prove a universal quantification over a recursively defined set:

Basis Step: Show the statement holds for elements specified in the basis step of the definition.

Recursive Step: Show that if the statement is true for each of the elements used to construct new elements in the recursive step of the definition, the result holds for these new elements.

Proof by Mathematical Induction

To prove a universal quantification over the set of all integers greater than or equals some base integer \(b\): Basis Step: Show the statement holds for b.

Recursive Step: Consider an arbitrary integer n greater than or equal to \(b\), assume (as the induction hypothesis) that the property holds for \(n\), and use this and other facts to prove that the property holds for \(n + 1\).

Proof by Strong Induction

To prove that a universal quantification over the set of all integers greater than or equal to some base integer \(b\) holds, pick a fixed nonnegative integer \(j\) and then:

Basis Step

Show the statement holds for \(b, b + 1, . . . , b + j\).

Recursive Step

Consider an arbitrary integer \(n\) greater than or equal to \(b + j\), assume (as the strong induction hypothesis) that the property holds for each of \(b, b + 1, . . . , n\), and use this and other facts to prove that the property holds for \(n + 1\).

Cardinality

Functions and comparing cardinalities

Let \(D\) and \(C\) be nonempty sets. A function \(f\) from \(D\) (domain) to \(C\) (codomain) is an assignment of one element of \(C\) to each element of \(D\).

One-to-one Function

A function \(f : D → C\) is one-to-one (or injective) means for every \(a\), \(b\) in the domain \(D\), if \(f (a) = f (b)\) then \(a = b\).

For sets \(A\), \(B\), we say that the cardinality of \(A\) is no bigger than the cardinality of \(B\), and write \(|A| ≤ |B|\), to mean there is a one-to-one function with domain \(A\) and codomain \(B\).

\(|A| \leq|B|\) means \(\exists f: A \rightarrow B \forall a_{1} \in A \forall a_{2} \in A((a_{1} \neq a_{2} \rightarrow f((a_{1})) \neq f((a_{2}))))\)

Onto function

A function \(f : D → C\) is onto (or surjective) means for every \(b\) in the codomain, there is an element \(a\) in the domain with \(f (a) = b\).

Formally, \(f : D → C\) is onto means \(∀b ∈ C \exists a ∈ D (f (a) = b)\).

For sets \(A\), \(B\), we say that the cardinality of \(A\) is no smaller than the cardinality of \(B\), and write \(|A| ≥ |B|\), to mean there is an onto function with domain \(A\) and codomain \(B\).

\(|A|\ge|B|\) means \(\exists f: A \rightarrow B \forall b \in B \exists a \in A(f(a)=b)\)

Bijection

A function \(f : D → C\) is a bijection means that it is both one-to-one and onto. The inverse of a bijection \(f : D → C\) is the function \(g : C → D\) such that \(g(b) = a \text{ iff } f (a) = b\).

\(|A|=|B|\) means\(\exists f: A \rightarrow B \forall b \in B \exists a \in A((f(a)=b \wedge \forall a^{\prime} \in A((a \neq a^{\prime} \rightarrow f((a^{\prime})) \neq b))))\)

Cantor-Schroder-Bernstein Theorem

\(|A|=|B| \text { iff } (|A| \leq|B| \text { and }|B| \leq|A|) \text { iff } (|A| \geq|B| \text { and }|B| \geq|A|)\)

To prove \(|A| = |B|\), we can do any one of the following

Properties of cardinality

\[\begin{array}{l}\forall A(|A|=|A|) \\\\ \forall A \forall B(|A|=|B| \rightarrow|B|=|A|) \\\\ \forall A \forall B \forall C((|A|=|B| \wedge|B|=|C|) \rightarrow|A|=|C|)\end{array}\]

Countably infinite sets

A set \(A\) is countably infinite means it is the same size as \(\mathbb N\).

An infinite set is countable if and only if it is possible to list the elements of the set in a sequence

Examples of countably infinite sets: \(S, L, \Z, \Z^+, \Z , \Z × \Z\).

Uncountable sets

An uncountable set is a set that is not finite and is not countably infinite.

Cantor’s diagonal argument

Claim: \(|\mathbb{N}|<|\mathcal{P}(\mathbb{N})|\) Proof: Towards a proof by universal generalization, consider an arbitrary function \(f: \mathbb{N} \rightarrow \mathcal{P}(\mathbb{N})\). We want to prove that \(f\) is not onto. Rewriting using the definition of onto:

\[\neg(\forall B \in \mathcal{P}(\mathbb{N}) \exists a \in \mathbb{N}(f(a)=B))\]

By logical equivalence, we can write this as an existential statement:

\[\exists B \in \mathcal{P}(\mathbb{N}) \forall a \in \mathbb{N}(f(a) \neq B)\]

In search of a witness, define the following collection of nonnegative integers:

\[D_{f}=\{n \in \mathbb{N} \mid n \notin f(n)\}\]

By definition of power set, since all elements of \(D_{f}\) are in \(\mathbb{N}\), it follows that

\[D_{f} \in \mathcal{P}(\mathbb{N})\]

Therefore, it’s enough to prove the following lemma: Lemma: \(\forall a \in \mathbb{N}((f(a) \neq D_{f}))\)

Proof of lemma: Towards universal generalization, consider an arbitrary \(a \in \mathbb{N}\). By definition of set equality, we want to prove that \(\exists x((\neg((x \in f(a) \leftrightarrow x \in D_{f}))))\). For a witness, consider \(x=a\). There are two cases: \(a \in f(a) \vee a \notin f(a)\). By definition of \(D_{f}\), each guarantees that \(f(a) \neq D_{f}\).

By the Lemma, we have proved that \(f\) is not onto, and since \(f\) was arbitrary, there are no onto functions from \(\mathbb{N}\) to \(\mathcal{P}(\mathbb{N})\).

The set of real numbers

\(\mathbb R\) is uncountable

Reflexiviy ⇒ \(\forall a \in \mathbb{R}(a \leq a)\)

Antisymmetry ⇒ \(\forall a \in \mathbb{R} \forall b \in \mathbb{R}((a \leq b \wedge b \leq a) \rightarrow(a=b))\)

Transitivity ⇒ \(\forall a \in \mathbb{R} \forall b \in \mathbb{R} \forall c \in \mathbb{R}((a \leq b \wedge b \leq c) \rightarrow(a \leq c))\)

Trichotomy ⇒ \(\forall a \in \mathbb{R} \forall b \in \mathbb{R}((a=b \vee b>a \vee a<b)\)

Least upper bound ⇒ Every nonempty set of real numbers that is bounded above has a least upper bound

Nested intervals ⇒ For each sequence of intervals \([a_n, b_n]\) where, for each \(n\), \(a_n < a_n+1 < b_n+1 < b_n\), there is at least one real number \(x\) such that, for all \(n\), \(a_n ≤ x ≤ b_n\).

Relation

When \(A\) and \(B\) are sets, we say any subset of \(A × B\) is a binary relation. There are other ways to represent a relation \(R\).

When \(A\) is a set, we say any subset of \(A × A\) is a (binary) relation on \(A\).

Let \(R_{(\bmod\ n)}\) be the set of all pairs of integers \((a, b)\) such that \((a \bmod n = b \bmod n)\). Then \(a\) is congruent to \(b\) mod \(n\) means \((a, b) ∈ R_{(\bmod\ n)}\). A common notation is to write this as \(a ≡ b(\bmod\ n)\).

A relation \(R\) on a set \(A\) is called reflexive means \((a, a) ∈ R\) for every element \(a ∈ A\). A relation \(R\) on a set \(A\) is called symmetric means \((b, a) ∈ R\) whenever \((a, b) ∈ R\), for all \(a, b ∈ A\). A relation \(R\) on a set \(A\) is called transitive means whenever \((a, b) ∈ R\) and \((b, c) ∈ R\), then \((a, c) ∈ R\), for all \(a, b, c ∈ A\).

Equivalence relations

A relation is an equivalence relation means it is reflexive, symmetric, and transitive.

An equivalence class of an element \(a ∈ A\) for an equivalence relation \(R\) on the set \(A\) is the set \(\{s ∈ A|(a, s) ∈ R\}\). We write this as \([a]_R\).

A partition of a set \(A\) is a set of non-empty, disjoint subsets \(A_1, A_2, · · · , A_n\) such that \(A_1 ∪ A_2 ∪ · · · ∪ A_n = A\).

We can partition a set using equivalence classes.

Modular arithmetic

For \(a, b ∈ \Z\) and positive integer \(n, (a, b) ∈ R(\bmod\ n)\) if and only if \(n|a-b\).

For \(a, b ∈ \Z\) and positive integer \(n\), if \(a ≡ b(\bmod\ n)\) and \(c ≡ d(\bmod\ n)\) then \(a + c ≡ b + d(\bmod\ n)\) and \(ac ≡ bd(\bmod\ n)\). Informally: can bring mod “inside” and do it first, for addition and for multiplication.

\((a ⋅ b) \bmod m = [(a \bmod m) ⋅ (b \bmod m)] \bmod m\)

\((a^b\bmod c)^n\bmod c=a^{bn}\bmod c\) (basis of Diffie-Hellman key exchange)