Logic and Proofs §

Propositions §

please don’t confuse AND/conjunction/$\wedge$ with OR/disjunction/$\vee$.

Tautology: always true

Contradiction: always false

Satisfiable: not a contradiction. not always false. not impossible.

SAT: propositional satisfiability. NP-complete.

Propositional equivalence §

$p$ and $q$ are logically equivalent if $p \leftrightarrow q$ ($p = q$) is a tautology.

De Morgan’s laws:

• $\neg (p \wedge q) \equiv \neg p \vee \neg q$

• $\neg (p \vee q) \equiv \neg p \wedge \neg q$

• double negation

  • $\neg (\neg p) \equiv p$

• commutative laws

  • $p \wedge q \equiv q \wedge p$
  • $p \vee q \equiv q \vee p$

• distributive laws

• implication laws

  • $p \rightarrow q \equiv \neg p \vee q$
  • $p \rightarrow q \equiv \neg q \rightarrow \neg p$
  • $p\leftrightarrow q \equiv (p \rightarrow q) \wedge (q \rightarrow p)$

prove equivalences using:

• truth tables
• a series of other equivalences

Predicates and Quantifiers §

variables.

e.g. $x \in \{1, 2, 3\}$, $P(x) := x \in \{1, 2, 3\}$

quantifiers:

• universal quantification

  $\forall x P(x)$. for all $x$ in the presumed domain, $P(x)$ is true

• existential quantification

  $\exists x P(x)$. there exists an $x$ such that $P(x)$ is true.

demorgan’s laws:

• $\neg \forall P(x) \equiv \exists x \neg P(x)$

• $\neg \exists P(x) \equiv \forall x \neg P(x)$

• $\forall x \forall y$

• $\exists x \exists y$

• $\forall x \exists y$

• $\exists x \forall y$

$\forall x \forall y \equiv \forall y \forall x$, $\exists x \exists y \equiv \exists y \exists x$

$\forall x \exists y \not \equiv \exists y \forall x$

negating nested quantifiers:

1. s/$\exists$/$\forall$/g
2. s/$\forall$/$\exists$/g
3. negate the proposition

Proofs and Proof Techniques §

proofs: valid arguments that establish the truth of statements

Rules of Inference §

Proof techniques §

• direct proofs
• contrapositive proofs
• proof by contradiction
• existence proofs
• counterexamples

Sets §

unordered collection of unique items

• roster method
• set comprehension

cardinality of a finite set: number of elements in the set

infinite sets: countable, uncountable

$\forall x(x \in A \rightarrow x \in B) \rightarrow A \subseteq B$

$\mathscr{P}(A) = 2^A = \{x : x \subseteq A\}$

$\mathscr{P}(\varnothing) = \{\varnothing\}$

Proper subsets ($\subset$): subsets excluding the set itself

Set operations §

• union — $A \cup B$
• intersection — $A \cap B$
  • disjoint: $A \cap B = \varnothing$
• difference — $A \setminus B = A = B$
• complement — $\overline{A} = U \setminus A$
• cartesian product — $A \times B = \{(x, y) : x \in A \wedge y \in B\}$
  • $A \times \varnothing = \varnothing$
  • $|A \times B| = |A| \times |B|$

Set identities §

• equality

  $A \subseteq B \wedge B \subseteq A$ implies $A = B$

• de morgan’s laws

  • $\overline{A \cap B} = \overline{A} \cup \overline{B}$
  • $\overline{A \cup B} = \overline{A} \cap \overline{B}$

• complementation law — $\overline{\overline{A}} = A$

• commutative

• associative

• distributive

Functions §

non-empty sets $D$ (domain) and $R$ (codomain)

function: assignment — from every element in $D$ to exactly one element in $R$

range (elements actually used as values) $\subseteq$ codomain

$f: A \rightarrow B$ and $f: C \rightarrow D$ are equal functions when:

• $A = C$
• $B = D$
• $\forall a \in A [f(a) = g(a)]$

when $f: A \rightarrow \mathbb{R}$ and $g: A \rightarrow \mathbb{R}$

• $f + g = (f + g)(a) = f(a) + g(a)$

• $fg = (f \cdot g)(a) = f(a) \cdot g(a)$

Injections, surjections, bijections §

• Injection aka “one-to-one”

  $f: A \rightarrow B$: $\forall a, b \in A \left(f(a) = f(b) \rightarrow a = b\right)$

  $|B| \geq |A|$

  hoz. line test

• Surjection aka “onto”

  $\forall b \in B (\exists a \in A (f(a) = b))$

  $|A| \geq |B|$

• Bijection

  both one-to-one and onto

  There exists a bijection $f: A \rightarrow B$ iff $|A| = |B|$

Inverse and composition §

Relations and their properties §

a binary relation from $A$ to $B$ is a subset of $A \times B$.

$(a, b) \in R$, $aRb$

$(a, b) \not \in R$, $a \not R b$

• reflexivity — $aRa$
• symmetric — $aRb \implies bRa$
  • antisymmetric — $aRb \wedge bRa \implies a = b$
• transitivity — $aRb \wedge bRc \implies aRc$

composing — $aRb \wedge bSc \implies a(R \circ S)c$

Representing relations §

• $|A| \times |B|$ adjacency matrix $M$ where:

  $m_{i,j} = \begin{cases}1 & a_i R b_j \\ 0 & a_i \not R b_j\end{cases}$

• di(rected)graphs

Relation closures §

"$S$ is the closure of $R$ wrt $P$" — relation $S$ is the smallest set that satisfies property $P$ such that $R \subseteq S$

[$R$ is a relation on set $A$]:

• reflexive closure

  $S = R \cup \{(a, a) : a \in A\}$

• symmetric closure

  $S = R \cup \{(a,b) : (b,a) \in R\}$

• transitive closure

Equivalence relations §

• reflexive

• symmetric

• transitive

  beware of “or”/“common” relations wrt transitivity

two element are equivalent ($a \sim b$) if they’re related by an equivalent relation.

$R$ is an equivalence relation on $A$, $a \in A$. equivalence class of $a$ ($[a]$) is $\{b \in A: (a,b) \in R\}$

partition of $A$.

• $A_1, A_2, \cdots, A_n$ are non-empty sets
• for any $a, b \leq n$, $A_a \cap A_b = \varnothing$
• $\bigcup_{i=1}^{n} A_i = A$

bipartition: $n = 2$.

fundamental theorem of equivalence relations: the set of all equivalence classes of a relation $R$ on $A$ form a partition of $A$.

Partial Orders §

• reflexive
• antisymmetric
• transitive

set $A$ + partial order $R$ = partial-ordered set aka “poset” $(A, R)$

$a$ and $b$ are elements of a poset $(A, \preceq)$. $a$ and $b$ are comparable if either $a \preceq b$ or $b \preceq a$. else, they are incomparable.

if $(A, \preceq)$ is a poset where every two elements of $A$ are comparable, $A$ is a totally ordered set and $\preceq$ is a total order.

Hasse diagrams are graphical reps of partial orders. excludes reflexivity and arrows that can be obtained by transitivty.

$a$ is a maximal element if there’s no $c \in A, c \neq a$ such that $a \preceq c$

$b$ is a minimal element if there’s no $c \in A, c \neq b$ such that $c \preceq b$

minimal and maximal elements do not have to exist or be unique.

$a$ is the greatest element if $\forall c \in A, c \preceq a$.

$b$ is the least element if $\forall c \in A, b \preceq c$.

greatest and least elements do not have to exist, but they must be unique.

a totally ordered set $(A, \preceq)$ is a well-ordered set if every non-empty subset of $A$ has a least element

Matrices §

Graphs §

Undirected graphs §

Pair $(V, E)$ where:

• $V$ is a non-empty set of nodes
• $E \subseteq \{A : A \in \mathscr{P}(V) \wedge |A| = 2\}$

Directed graphs §

aka digraphs

Pair $(V, E)$ where:

• $V$ is a non-empty set of nodes
• $E \subseteq (V \times V) - \{(u, u) : u \in V\}$

Jargon §

• neighbours

• degree

  • in-degree
  • out-degree

• tail, head

• subgraph

  subset of nodes and subset of edges. $V' \subseteq V \wedge E' \subseteq E$

  • induced subgraph

    subset of edges and all edges that connect them. $V' \subseteq V \wedge E' = \{\{u, v\} \in E : u, v \in V'\}$

Special graphs §

• complete graph: graph with an edge between every two nodes

• cycle

• bipartite graph

  $V$ can be bipartitioned into $V_1$ and $V_2$ such that $E \subseteq (V_1 \times V_2 \cup V_2 \times V_1)$

  bipartite theorem: a graph is bipartite iff there exists a function $f : V \rightarrow \{1, 2\}$ such that $\forall {u, v} \in E, f(u) \neq f(v)$

  colour neighbours of $1$-coloured nodes with $2$ and vice-versa

  • complete bipartite graph

• forest: acyclic

• tree: connected and acyclic.

Connectivity §

• path

  • simple — path that doesn’t contain the same node more than once
  • circuit — path that begins and ends at the same node
  • cycle — simple circuit

• connected

  • connected component
  • strongly connected
  • weakly connected
  • strongly connected component

Graph Isomorphism §

• graph isomorphism

  equivalence relation

• subgraph isomorphism

  partial order

Q: subgraph isomorphism vs subgraph

• every graph is isomorphic to itself
• $(g_1, g_2) \in R \rightarrow (g_2, g_1) \in R$
• $(g_1, g_2) \in R \wedge (g_2, g_3) \in R \rightarrow (g_1, g_3) \in R$

Representing graphs §

$n :=$ number of nodes

$m :=$ number of edges

• adjacency list set

  input size $(n, m)$

  ❤ sparse

• adjacency matrix

  input size $n$

  ❤ dense

Sequences and Summations §

sequence: a function from a subset of the set of integers to a set $S$. $a_n$, $\{a_n\}$

• geometric progression $a, ar, ar^2, \cdots$

  initial term $a$, common ratio $r$

• arithmetic progression $a, a + d, a + 2d, \cdots$

  initial term $a$, common difference $d$

recurrence relation for a sequence is an equation that expresses $a_n$ in terms of one or more of the previous terms of the sequence

summation:

• $\sum_{n = 0}^{\infty} a_n$
• $\sum_{n = i}^{n=j} a_n$
• $\sum_{n \in S} a_n$

series: sum of a sequence from $n = 0$ or $n = 1$ as necessary

• telescoping sums
• perturbation method

Algorithm Efficiency §

finite sequence of precise instructions for performing a computation

• a name
• input/output
• unambiguous steps
• finite {time,number of steps}
• correct output values for each set of input values

Big O notation §

$f(x) = \mathcal{O}\left(g(x)\right)$ if there exist positive constants $C$ and $k$ such that $f(x) \leq Cg(x)$ for all $x \geq k$

• $f(x) = a_n x^n + a_{n - 1} x^{n - 1} + \cdots +a_1 x + a_0 = \mathcal{O}(x^n)$
• $f_1(x) = \mathcal{O}(g(x))$, $f_2(x) = \mathcal{O}(h(x))$. $(f_1 + f_2)(x) = \mathcal{O}\left(\max\left(g(x), h(x)\right)\right)$
• $f_1(x) = \mathcal{O}(g(x))$, $f_2(x) = \mathcal{O}(h(x))$. $(f_1 \cdot f_2)(x) = \mathcal{O}(g(x) \cdot h(x))$

Big Omega notation §

$f(x) = \Omega\left(g(x)\right)$ if there exist positive constants $C$ and $k$ such that $f(x) \geq Cg(x)$ for all $x \geq k$

$f(x) = \Omega(g(x)) \Leftrightarrow g(x) = \mathcal{O}(f(x))$

Big Theta notation §

… aka “order of”

$f(x) = \Theta\left(g(x)\right)$ if there exist positive constants $C_1$, $C_2$, and $k$ such that $C_1 g(x) \leq f(x) \leq C_2 g(x)$ for all $x \geq k$

$f(x) = \Theta(g(x))$ iff $f(x) = \mathcal{O}(g(x))$ and $f(x) = \Omega(g(x))$.

Complexity of algorithms §

efficiency:

• time
• space

ignore multiplicative and additive constants

for a given input size $n$:

• worst case — upper bound

• best case — usually useless

• average case — informative, but requires making assumptions about the input

• $\Theta(1)$

• $\Theta(\log n)$

• $\Theta(n)$

• $\Theta(n \log n)$

• $\Theta(n^a)$

• $\Theta(a^n)$, $n > 1$

• $\Theta(n!)$

if there exists a polynomial-time worst-case algorithm for a problem, the problem is tractable. else, it’s intractable.

• tractable: class P
• intractable
  • solution can be verified in polynomial time: class NP
  • class NP-complete

halting problem:

• does a given computer program terminate for a given input
• proven unsolvable

post correspondence problem

BFS §

[see also: COMP 140’s BFS section]

[see also: COMP 140’s Queue section]

Mathematical Induction §

$[P(1) \wedge \forall k (P(k) \rightarrow P(k + 1))] \rightarrow \forall n P(n)$

Important fact: The set of positive integers is well-ordered.

1. Basis step: Show that $P(1)$

2. Inductive step: Show that $\forall k P(k) \rightarrow P(k + 1)$

   The assumption that $P(k)$ is called the inductive hypothesis

Strong Mathematical Induction §

1. Basis step: Show that $P(1)$

2. Inductive step: Show that $\forall k [P(1) \wedge P(2) \wedge \cdots \wedge P(k)] \rightarrow P(k + 1)$