Written by Luka Kerr on May 2, 2019

## Discrete Maths

### Sets

Power set: $Pow(X) = { A : A \subseteq X }$

Empty set: $\emptyset$

Set difference: $A \setminus B$

Set symmetric difference: $A \oplus B$

Set complement: $A^c$

Laws:

$\begin{array}{ll} A \cup A = A \\ A \cap A = A & \text{Idempotence} \\ (A^c)^c = A & \text{Double complementation} \\ A \cap \emptyset = \emptyset & \text{Annihilation} \\ (A \cap B)^c = A^c \cup B^c \\ (A \cup B)^c = A^c \cap B^c & \text{DeMorgan’s Laws} \end{array}$

### Formal Languages

Alphabet: A finite, non-empty set $\Sigma$

Word: A finite string of symbols from $\Sigma$

Empty word: $\lambda$ (sometimes $\epsilon$)

$\Sigma^*$: Set of all words

$\Sigma^+$: Set of all nonempty words

Concatenation: $XY = { xy : x \in X \land y \in Y }$

Kleene star: $X^*$, the set of words that are made up by concatenating 0 or more words in $X$

### Relations

Properties include:

$\begin{array}{ll} (x, x) \in R & \text{Reflexive} \\ (x, x) \not \in R) & \text{Anti-reflexive} \\ (x, y) \in R \to (y, x) \in R & \text{Symmetric} \\ (x, y), (y, x) \in R \to x = y & \text{Anti-symmetric} \\ (x, y), (y, z) \in R \to (x, z) \in R & \text{Transitive} \end{array}$

Equivalence Relation: Reflexive, symmetric and transitive.

Equivalence Class $[s]$, $s \in S$: $[s] = { t \in S : tRs }$

Converse: $R^\leftarrow = { (b, a) : (a, b) \in R }$

Relational composition: $(x, z) \in S; R$ iff $y \in Y : (x, y) \in R \land (y, z) \in S$

Transitive closure: $R^* = \underset{i \ge 0}{\bigcup} R^i$, where $R^0 = \Delta$ and $R^{i + 1} = R^i; R$

### Partial Order

A partial order $\preceq$ on $S$ is reflexive, antisymmetric and transitive.

### Functions

Composition: $g \circ f \equiv g(f(x))$

## Recursion & Induction

### Recursion

Consists of a basis (B) and recursive process (R).

A sequence/object/algorithm is recursively defined when (typically)

(B) some initial terms are specified, perhaps only the first one;

(R) later terms stated as functional expressions of the earlier terms.

### Induction

#### Mathematical Induction

Base Case [B]: $P(a_1), P(a_2), \dots , P(a_n)$ for some small set of examples $a_1 \dots a_n$ (often $n = 1$)

Inductive Step [I]: A general rule showing that if $P(x)$ holds for some cases $x = x_1, \dots , x_k$ then $P(y)$ holds for some new case $y$, constructed in some way from $x_1, \dots , x_k$

Conclusion: Starting with $a_1 \dots a_n$ and repeatedly applying the construction of $y$ from existing values, we can eventually construct all values in the domain of interest

#### Structural Induction

Base Case [B]: The property holds for all minimal objects – objects that have no predecessors; they are usually very simple objects allowing immediate verification

Inductive Step [I]: for any given object, if the property in question holds for all its predecessors (‘smaller’ objects) then it holds for the object itself

## Propositional Logic

### Well Formed Formulas

Let $Prop = \{ p, q, r \dots \}$

Let $\Sigma = Prop \cup \{ \top, \bot, \neg, \land, \lor, \to, \leftrightarrow, (, ) \}$

The well formed formulas (wffs) over $Prop$ is the smallest set of words over $\Sigma$ such that:

• $\top, \bot$ and all elements of $Prop$ are wffs
• If $\varphi$ is a wff, then $\neg \varphi$ is a wff
• If $\varphi$ and $\psi$ are wffs, then $(\varphi \land \psi)$, $(\varphi \lor \psi)$, $(\varphi \to \psi)$ and $(\varphi \leftrightarrow \psi)$ are wffs

### Satisfiability, Entailment, Equivalence

A valuation satisfies a theory $T$ if $\llbracket \varphi \rrbracket_v = \mathbf{true}$ for every $\varphi \in T$.

A theory/formula is satisfiable if there’s a valuation that satisfies it.

A formula is a tautology if every valuation satisfies it.

Entailment: $T \models \varphi$ if for every valuation that satisfies $T$, we have $\llbracket \varphi \rrbracket_v = \mathbf{true}$.

Logical equivalence: $\varphi \equiv \psi$ if $\llbracket \varphi \rrbracket_v = \llbracket \psi \rrbracket_v$ for all valuations.

### Valuations

A truth assignment (or model) is a function $v : Prop \to \mathbb{B}$

We can extend $v$ to a function $\llbracket \cdot \rrbracket_v : \text{WFFs} \to \mathbb{B}$ recursively:

• $\llbracket \top \rrbracket_v =$ true
• $\llbracket \bot \rrbracket_v =$ false
• $\llbracket p \rrbracket_v = v(p)$
• $\llbracket \neg \varphi \rrbracket_v = ! \llbracket \varphi \rrbracket_v$
• $\llbracket (\varphi \land \psi) \rrbracket_v = \llbracket \varphi \rrbracket_v$ && $\llbracket \psi \rrbracket_v$
• $\llbracket (\varphi \lor \psi) \rrbracket_v = \llbracket \varphi \rrbracket_v$ || $\llbracket \psi \rrbracket_v$
• $\llbracket (\varphi \to \psi) \rrbracket_v = !\llbracket \varphi \rrbracket_v$ || $\llbracket \psi \rrbracket_v$
• $\llbracket (\varphi \leftrightarrow \psi) \rrbracket_v = (!\llbracket \varphi \rrbracket_v$ || $\llbracket \psi \rrbracket_v)$ && $(!\llbracket \psi \rrbracket_v$ || $\llbracket \varphi \rrbracket_v)$

### CNF & DNF

A propositional formula is in CNF (conjunctive normal form) if it has the form $\bigwedge_{i} c_{i}$, where each clause $c_i$ is a disjunction of literals.

A propositional formula is in DNF (disjunctive normal form) if it has the form $\bigvee_{i} c_{i}$, where each clause $c_i$ is a conjunction of literals.

For every boolean expression $\phi$ there exists an equivalent expression in conjunctive normal form and an equivalent expression in disjunctive normal form.

#### Converting

Push Negations Down using De Morgan’s laws and the double negation rule

$\begin{array}{rcl} \neg (x \lor y) & \equiv & \neg x \land \neg y \\ \neg (x \land y) & \equiv & \neg x \lor \neg y \\ \neg \neg x & \equiv & x \end{array}$

Using the distribution rules

$\begin{array}{rcl} x \lor (y_1 \land \dots \land y_n) & = & (x \lor y_1) \land \dots \land (x \lor y_n) \\ (y_1 \land \dots \land y_n) \lor x & = & (y_1 \lor x) \land \dots \land (y_n \lor x) \end{array}$

Using the equivalence $A \to B \equiv \neg A \lor B$

Using the equivalence $(A \leftrightarrow B) \equiv (A \to B) \land (B \to A)$

#### Examples

CNF: $(p \lor \neg q) \land (u \lor v)$

DNF: $(p \land \neg q) \lor (u \land v)$

## Predicate Logic

### Domain Of Discourse

• Predicates: Relations on the domain
• Functions: Operators on the domain
• Constants: “Named” elements of the domain
• Variables: “Unnamed” elements of the domain (placeholders for elements)
• Quantifiers: Range over domain elements

### Vocabulary

A vocabulary indicates what predicates, functions and constants we can use to build up our formulas.

A vocabulary is a set of:

• Predicate “symbols” $P, Q, \dots$, each with an assoicated arity (number of arguments)
• Function “symbols” $f, g, \dots$, each with an assoicated arity (number of arguments)
• Constant “symbols” $c, d, \dots$ (also known as 0-arity functions)

## Natural Deduction

Below some of the natural deduction inference rules for propositional and predicate logic.

Note: the notation $[A] \dots B$, means “assuming $A$, we can deduce $B$”.

$\begin{array}{|c|c|c|} \hline \rule[-4ex]{0pt}{10ex} \dfrac{A \qquad B}{A \land B} (\land \text{-I}) & \dfrac{A}{A \lor B} (\lor \text{-I1}) & \dfrac{B}{A \lor B} (\lor \text{-I2}) \\ \hline \rule[-4ex]{0pt}{10ex} \dfrac{A \land B}{A} (\land \text{-E1}) & \dfrac{A \land B}{B} (\land \text{-E2}) & \dfrac{A \qquad \neg A}{\bot} (\neg \text{-E}) \\ \hline \rule[-4ex]{0pt}{10ex} \dfrac{A \to B \qquad A}{B} (\to \text{-E}) & \dfrac{A \leftrightarrow B \qquad A}{B} (\leftrightarrow \text{-E1}) & \dfrac{A \leftrightarrow B \qquad B}{A} (\leftrightarrow \text{-E2}) \\ \hline \rule[-4ex]{0pt}{10ex} \dfrac{A \lor B \qquad [A] \dots C \qquad [B] \dots C}{C} (\lor \text{-E}) & \dfrac{[A] \dots B}{A \to B} (\to \text{-I}) & \dfrac{[A] \dots B \qquad [B] \dots A}{A \leftrightarrow B} (\leftrightarrow \text{-I}) \\ \hline \rule[-4ex]{0pt}{10ex} \dfrac{[A] \dots \bot}{\neg A} (\neg \text{-I}) & \dfrac{[\neg A] \dots \bot}{A} (\text{IP}) & \dfrac{\bot}{A} (\text{X}) \\ \hline \rule[-4ex]{0pt}{10ex} \dfrac{\neg \neg A}{A} (\text{DNE}) & \dfrac{A}{A} (\text{R}) & \dfrac{[A] \dots B \qquad [\neg A] \dots B}{B} (\text{LEM}) \\ \hline \rule[-4ex]{0pt}{10ex} \dfrac{A \lor B \qquad \neg A}{B} (\text{DS}) & \dfrac{A \to B \qquad \neg B}{\neg A} (\text{MT}) & \dfrac{\neg (A \lor B)}{\neg A \land \neg B} (\text{DM}) \\ \hline \rule[-4ex]{0pt}{10ex} \dfrac{}{a = a} (= \text{-I}) & \dfrac{a = b \qquad A(a)}{A(b)} (= \text{-E1}) & \dfrac{a = b \qquad A(b)}{A(a)} (= \text{-E2}) \\ \hline \rule[-4ex]{0pt}{10ex} \dfrac{A(c) \qquad \text{\scriptsize{(1, 2, 3)}}}{\forall x A(x)} (\forall \text{-I}) & \dfrac{A(c) \qquad \text{\scriptsize{(2)}}}{\exists x A(x)} (\exists \text{-I}) & \dfrac{\forall x A(x)}{A(c)} (\forall \text{-E}) \\ \hline \dfrac{\exists x A(x) \qquad [A(c)] \dots B \qquad \text{\scriptsize{(1, 2, 4)}}}{B} (\exists \text{-E}) & & \begin{array}{ll} \text{\small{(1):}} & \text{\small{c is arbitrary}} \\ \text{\small{(2):}} & \text{\small{x is not free in A(c)}} \\ \text{\small{(3):}} & \text{\small{c is not free in A(x)}} \\ \text{\small{(4):}} & \text{\small{c is not free in B}} \end{array} \\ \hline \end{array}$

## Hoare Logic

### $\mathcal{L}$

• Assignment: $x := e$
• Sequencing: $P; Q$
• Conditional: if $b$ then $P$ else $Q$ fi
• While: while $b$ do $P$ od

### Hoare Triples

$\{ \varphi \} \ P \ \{ \psi \}$ where

$\varphi$: The precondition – an assertion about the state prior to the execution of the code fragment

$P$: The code fragment

$\psi$: The postcondition – an assertion about the state after to the execution of the code fragment if it terminates

### $\mathcal{L}$ Rules

$\begin{array}{lcl} \text{Assignment} & \dfrac{}{\{ \varphi[e / x] \} x := e \{ \varphi \}} & (\text{ass}) \\ \\ \text{Sequence} & \dfrac{ \{ \varphi \} \ P \ \{ \psi \} \qquad \{ \psi \} \ Q \ \{ \rho \} }{\{ \varphi \} \ P; Q \ \{ \rho \}} & (\text{seq}) \\ \\ \text{While} & \dfrac{ \{ \varphi \land g \} \ P \ \{ \varphi \} }{\{ \varphi \} \ \mathbf{while} \ g \ \mathbf{do} \ P \ \mathbf{od} \ \{ \varphi \land \neg g \}} & (\text{loop}) \\ \\ \text{Pre/Post (Strength/Weak)ening} & \dfrac{ \varphi' \to \varphi \qquad \{ \varphi \} \ P \ \{ \psi \} \qquad \psi \to \psi' }{\{ \varphi' \} \ P \ \{ \psi' \}} & (\text{cons}) \\ \end{array}$

### $\mathcal{L}$ Semantics

An environment or state is a function from variables to numeric values. We denote by $Env$ the set of all environments.

$\begin{array}{ll} \text{Assignment}: & (\eta, \eta') \in \llbracket x := e \rrbracket \ \text{iff} \ \eta' = \eta[x \mapsto \llbracket e \rrbracket^{\eta}] \\ \text{Predicate}: & \langle b \rangle = \{ \eta : \llbracket b \rrbracket^n = \mathbf{true} \} \\ & \llbracket b \rrbracket = \{ (\eta, \eta) : \eta \in \langle b \rangle \} \\ \text{Sequencing}: & \llbracket P; Q \rrbracket = \llbracket P \rrbracket; \llbracket Q \rrbracket \\ \text{Conditional}: & \llbracket \mathbf{if} \ b \ \mathbf{then} \ P \ \mathbf{else} \ Q \ \mathbf{fi} \rrbracket = \llbracket b; P \rrbracket \cup \llbracket \neg b; Q \rrbracket \\ \text{While}: & \llbracket \mathbf{while} \ b \ \mathbf{do} \ P \ \mathbf{od} \rrbracket = \llbracket b; P \rrbracket^*; \llbracket \neg b \rrbracket \end{array}$

### Weakest Precondition

Given a program $P$ and a postcondition $\psi$, the weakest precondition of $P$ with respect to $\psi$, $wp(P, \psi)$, is a predicate $\varphi$ such that

$\{ \varphi \} \ P \ \{ \psi \} \quad \text{and} \quad \text{if} \ \{ \varphi' \} \ P \ \{ \psi \} \ \text{then} \ \varphi' \to \varphi$

Assignment: $wp(x := e, \psi) = \psi[e / x]$

Sequence: $wp(P; S, \psi) = wp(P, wp(S, \psi))$

Conditional: $wp(\mathbf{if} \$b$\ \mathbf{then} \$P$\ \mathbf{else} \$Q$\ \mathbf{fi}, \psi) = (b \land wp(P, \psi)) \lor (\neg b \land wp(Q, \psi))$

While:

Find a loop invariant $I$ such that

• $\varphi \to I$
• ${ I \land b } \ P \ { I }$
• $I \land \neg b \to \psi$

### Termination

$[\varphi] P [\psi]$ asserts that if $\varphi$ hold at a starting state and $P$ is executed, then $P$ will terminate and $\psi$ will hold in the resulting state.

#### Rules For Total Correctness

$\begin{array}{lcl} \text{Assignment} & \dfrac{}{[ \varphi[e / x] ] x := e [ \varphi ]} & (\text{ass}) \\ \\ \text{Sequence} & \dfrac{[ \varphi ] \ P \ [ \psi ] \qquad [ \psi ] \ Q \ [ \rho ]}{[ \varphi ] \ P; Q \ [ \rho ]} & (\text{seq}) \\ \\ \text{Conditional} & \dfrac{[ \varphi \land g ] \ P \ [ \psi ] \qquad [ \varphi \land \neg g ] \ Q \ [ \psi ]}{[ \varphi ] \ \mathbf{if} \ g \ \mathbf{then} \ P \ \mathbf{else} \ Q \ \mathbf{fi} \ [ \psi ]} & (\text{if}) \\ \\ \text{While} & \dfrac{ [ \varphi \land g \land (v = N) ] \ P \ [ \varphi \land (v < N) ] \qquad (\varphi \land g) \to (v > 0) }{[ \varphi ] \ \mathbf{while} \ g \ \mathbf{do} \ P \ \mathbf{od} \ [ \varphi \land \neg g ]} & (\text{loop}) \\ \\ \text{Pre/Post (Strength/Weak)ening} & \dfrac{ \varphi' \to \varphi \qquad [ \varphi ] \ P \ [ \psi ] \qquad \psi \to \psi' }{[ \varphi' ] \ P \ [ \psi' ]} & (\text{cons}) \\ \end{array}$

#### Terminating While Loops

Partial correctness: Find an invariant $I$ such that:

• $\varphi \to I$
• $[I \land b] \ P \ [I]$
• $(I \land \neg b) \to \psi$

Show termination: Find a variant $v$ such that:

• $(I \land b) \to v > 0$
• $[I \land b \land v = N] \ P \ [v < N]$

### $\mathcal{L^+}$

$\begin{array}{lll} \text{Assignment} & x := e \\ \text{Predicate} & \varphi \\ \text{Sequencing} & P; Q \\ \text{Choice} & P + Q & \text{Make a non-deterministic choice between P and Q} \\ \text{Loop} & P^* & \text{Loop for a non-deterministic number of iterations} \end{array}$

## State Machines

A transition system is a pair $(S, \to)$ where:

• $S$ is a set of states
• $\to \subseteq S \times S$ is a transition relation

If $(s, s’) \in \to$, we write $s \to s’$.

• $S$ may have a start state $s_0$
• $S$ may have final states $F \subseteq S$
• The transitions may be labelled by elements of a set $\Lambda$:
• $\to \subseteq S \times \Lambda \times S$
• $(s, a, s’) \in \to$ is written as $s \overset{a}{\to} s’$
• If $\to$ is a function, we say the system is deterministic, otherwise it is non- deterministic

### Runs & Reachability

Given a transition system $(S, \to)$ and states $s, s’ \in S$

• A run from $s$ is a (possibly infinite) sequence $s_1, s_2 \dots$ such that $s = s_1$ and $s_i \to s_{i + 1}$ for all $i \ge 1$
• We say $s’$ is reachable from $s$, written $s \overset{*}{\to} s’$ if $(s, s’)$ is in the transitive closure of $\to$
• A state $s’$ is reachable from $s$ if there is a run from $s$ which contains $s’$

### Safety & Liveness

Safety: Something bad will never happen. In the context of transition systems, “will a transition system always avoid a particular state or states”

Liveness: Something good will happen. In the context of transition systems, “will a transition system always reach a particular state or states”

### The Invariant Principle

A preserved invariant of a transition system is a unary predicate $\varphi$ on states such that if $\varphi(s)$ holds, and $s \to s’$, then $\varphi(s’)$ holds.

Invariant Principle: If a preserved invariant holds at a state $s$, then it holds for all states reachable from $s$

### Partial & Total Correctness, & Termination

Partial Correctness: A transition system is partially correct for $\varphi$ if $\varphi(s’)$ holds for all states $s’ \in F$ that are reachable from $s_0$

Termination: A transition system terminates from a state $s \in S$ if there is an $N \in \mathbb{N}$ such that all runs from $s$ have lenght at most $N$

Total Correctness: A transition system is totally correct for $\varphi$ if it terminates from $s_0$ and $\varphi$ holds in the last state of every run

## Finite State Automata

### Deterministic Finite Automata

A DFA is a tuple $(Q, \Sigma, \delta, q_0, F)$ where

• $Q$ is a finite set of states
• $\Sigma$ is the input alphabet
• $\delta : Q \times \Sigma \to Q$ is the transition function
• $q_0 \in Q$ is the start state
• $F \subseteq Q$ is the set of final/accepting states

For a DFA $A = (Q, \Sigma, \delta, q_0, F)$, the language of $A$, $L(A)$ is the set of words from $\Sigma^*$ which are accepted by $A$.

### Non-Deterministic Finite Automata

A NFA is a tuple $(Q, \Sigma, \delta, q_0, F)$ where

• $Q$ is a finite set of states
• $\Sigma$ is the input alphabet
• $\delta \subseteq Q \times (\Sigma \cup { \epsilon }) \times Q$ is the transition relation
• $q_0 \in Q$ is the start state
• $F \subseteq Q$ is the set of final/accepting states

For any DFA, there exists an NFA, and vice versa.

## Regular Languages

A language $L \subseteq \Sigma^*$ is regular is there is some DFA $A$, such that $L = L(A)$.

Equivalently, there is some NFA $B$ such that $L = L(B)$.

Complementation: If $L$ is a regular language then $L^c = \Sigma^* \setminus L$ is a regular language

Union: If $L_1$ and $L_2$ are regular languages, then $L_1 \cup L_2$ is regular

Intersection: If $L_1$ and $L_2$ are regular languages, then $L_1 \cap L_2$ is regular

Concatenation: If $L_1$ and $L_2$ are regular languages, then $L_1 \cdot L_2$ is regular

Kleene star: If $L$ is a regular language, then $L^*$ is regular

### Regular Expressions

• $\emptyset$ is a regular expression
• $\epsilon$ is a regular expression
• $a$ is a regular expression for all $a \in \Sigma$
• If $E_1$ and $E_2$ are regular expressions, then $E_1 E_2$ is a regular expression
• If $E_1$ and $E_2$ are regular expressions, then $E_1 + E_2$ is a regular expression
• If $E$ is a regular expression, then $E^*$ is a regular expression

Kleene’s theorem

• For any regular expression $E$, $L(E)$ is a regular language
• For any regular language $L$, there is a regular expression $E$ such that $L = L(E)$

### Myhill-Nerode Theorem

Let $x, y \in \Sigma^*$ and let $L \subseteq \Sigma^*$. We say that $x$ and $y$ are $L-$indistinguishable, written $x \equiv_L y$ if for every $z \in \Sigma^*$:

$xz \in L \ \text{iff} \ yz \in L$

$\equiv_L$ is an equivalence relation.

The index of $L$ is the number of equivalence classes of $\equiv_L$.

The index of $L$ may be finite or infinite.

Myhill-Nerode Theorem: $L$ is regular if and only if $L$ has finite index. Moreover, the index is the size (= number of states) of the smallest DFA accepting $L$.

### Context Free Grammars

A context free grammar is a 4-tuple $G = (V, \Sigma, R, S)$ where

• $V$ is a finite set of variables (or non-terminals)
• $\Sigma$ (the alphabet) is a finite set of terminals
• $R$ is a finite set of productions. A production (or rule) is an element of $V \times (V \cup \Sigma)^*$, written $A \to w$
• $S \in V$ is the start symbol