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:

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:

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

Vocabulary

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

A vocabulary is a set of:

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}$

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

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:

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

$\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:

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

Runs & Reachability

Given a transition system $(S, \to)$ and states $s, s’ \in 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

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

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

Kleene’s theorem

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