CH1 - Revision and Background Flashcards
Define an alphabet.
Define letters.
Define a word, subword and initial subword.
An alphabet is a finite set, with the elements as letters.
A word is a finite sequence of letters. An initial subword is a prefix of the word.
What does this symbol denote?
What is a subset of this known as?
The set of all words over sigma, including the empty word.
A subset of this is a language over sigma.
Define len-lex ordering of a language.
First sort by length, then lexicographically within each length.
Define a graph G (and therefore edge set E).
Define a directed graph.
Define a path.
Define a directed walk/path.
Ordered pair (V,E), where V is a set and E is a set of 2-element subsets of V.
E is a set of ordered pairs in a directed graph.
A path is a walk with distinct vertices.
A directed walk/path follows the direction of the arrows.
Define a tree.
Define a leaf.
State Lemma on trees and paths.
Define a rooted tree/ height of a vertex v in a rooted tree/ children of v.
A tree is a graph/digraph that is connected with no cycles.
A leaf is a vertex with a single neighbour.
Lemma: For all pairs of distinct vertices u and v, there exists a unique path from u to v.
A rooted tree has one vertex identified as the root. The height of v of the length of the path from the root to v. The height of the tree is the max length. Children of v are neighbours at a height 1 higher than v.
Define a boolean variable.
Define a truth assignment for a boolean expression E.
What does E(T) denote?
What does it mean for T to satisfy E?
A boolean variable can only take the values true (1) or false (0). We build boolean expressions from boolean variables.
A truth assignment is a map T from the variables in E to {0,1}. The value of E given T is denoted E(T).
T satisfies E if E(T)=1.
Define an identity for boolean expressions P and Q.
Define a countable set.
P=Q is an identity if P and Q are satisfied by exactly the same truth assignments. Once we know an identity holds, we can substitute one side for the other in any boolean expression without changing its truth value.
A is countable if A is finite or there exists a bijection from the natural numbers to A.
State Theorem on the (un)countability of the set U of infinite sequences over {0,1}.
Prove it.
