Sipser: Section 0.2

From CSWiki

CSC 341: Front Door

---

| CSC 341: Cooperative commentary | Sipser:_Chapter_0

Contents 1 Sets 2 Sequences and tuples 2.1 Cartesian products 3 Functions and relations 3.1 Equivalence relations 4 Graphs 5 Strings and languages 6 Boolean logic 7 Expressing all Boolean operations using only AND and NOT operations

Sets

set - a group of objects represented as a unit.

• Examples include {1,2,3}, {a,b,5}, and {} or (the null set).
• In a set, repetition and order are not important (unless we are speaking of a multiset)
• Important sets include N (the set of all natural numbers, integers >= 1) and Z (integers)

Sequences and tuples

Cartesian products

The following example may help elucidate the notion of Cartesian product. Recall the notation used in linear algebra for the n-dimensional vector space. This is really just referring to the set of real numbers, , taken to the nth Cartesian power.

Functions and relations

Equivalence relations

A relation ~ is an equivalence relation ~ if, and only if, it has these three properties:

1. For every x in the domain of the relation, x~x (reflexivity).
2. For every x and y in the domain of the relation, if x~y, then y~x (symmetry).
3. For every x, y, and z in the domain of the relation, if x~y and y~z, then x~z (transitivity).

For example, for any positive integer k, the mod k relation on integers (or on all the integers) is a equivalence relation (this idea is used a lot in Abstract Algebra).

Mathematically, this relation is .

Another example is the relation, among people, of being exactly the same height.

Graphs

Image used in examples: [here]

path - a sequence of nodes connected by edges (following direction)

• An example path would be 1-2-6-7-10-5-8-7-6
• A simple path does not repeat nodes, for example 1-9-3-4

cycle - a path that starts and ends at the same node

• An example is 1-2-4-3-2-1
• A simple cycle contains >= 3 nodes and repeates only the first/last, e.g. 1-2-4-3-0-1

Strings and languages

• An alphabet is a non-empty collection of symbols
• A string is an ordered list of symbols from some alphabet
  • is the empty string
• A language is a set of strings
  • is the language of no strings

Boolean logic

1. 
2. 
3. 
4. 
5. 
6. 
7. 
8. 
9. 

Boolean logic symbols:

1.  : and [only true if both operands are true]
2.  : or [true if one of the operands is true]
3.  : equality [operands are both true or both false]
4.  : xor [true if one but not both of the operands is true]
5.  : implication [only false when the first operand is true and its second operand is false, otherwise true.]

Expressing all Boolean operations using only AND and NOT operations

1 OR
=

2 IMPLICATION
=

3 EQUALITY
=

4 XOR
=

---

CSC 341: Front Door