Math161

Front 1

Negation
Truth Table

Back 1

A ¬A
T F
F T

Front 2

Conjuction
Truth Table

Back 2

A B A^B
T T T
T F F
F T F
F F F

Front 3

Disjunction
Truth Table

Back 3

A B AvB
T T T
T F T
F T T
F F F

Front 4

Implication
Truth Table

Back 4

A B A=>B
T T T
T F F
F T T
F F T

Front 5

Equivalence
Truth Table

Back 5

A B A<=>B
T T T
T F F
F T F
F F T

Front 6

Well Formed Formulas
Rules

Back 6

- All atomic stamements are wffs.
- If A and B are wffs then so is ¬A, A^B, AvB, A=>B and A<=>B

Front 7

Consistent

Back 7

A is consistent if it is truth in a least one row of its truth table.

Front 8

Inconsistent

Back 8

A is inconsistent if it is false in all rows of its truth table.

Front 9

Tautology

Back 9

A is a tautology if it is true in all rows of its truth table.

Front 10

Functional Completeness

Back 10

A collection of logical operators is functionally complete if
the operators in the collection can be used to express every other logical
operator.

Front 11

Argument

Back 11

A collection of wffs called premises and another wff called the conclusion.
A1,A2,...,An therefore C

Front 12

Valid Argument

Back 12

An argument is valid if (A1^A2^...^An)=>C is a tautology.
In every row in the truth table where the premises are true, the conclusion must also be true.

Front 13

Conjunction Elimination Rule

Back 13

j. A^B

A (^E j)

Front 14

Conjunction Introduction Rule

Back 14

j. A
k. B

A^B (^I j, k)

Front 15

Implication Elimination Rule

Back 15

j. A=>B
k. A

B (=>E j, k)

Front 16

Implication Introduction Rule

Back 16

j. A
...
k. B

A=>B (=>I j-k)

Front 17

Disjunction Introduction Rule

Back 17

j. A

AvB

Front 18

Disjunction Elimination Rule 1

Back 18

j. AvB
k. ¬A

B (vE1 j,k)

Front 19

Disjunction Elimination Rule 2

Back 19

j. AvB
k. A=>C
l. B=>C

C (vE2 j,k,l)

Front 20

Contradiction Introduction

Back 20

j. A^(¬A)

_|_ (_|_I j)

Front 21

Negation Introduction

Back 21

j. A => _|_

¬A (¬I j)

Front 22

Negation Elimination

Back 22

k. ¬(¬A)

A (¬E j)

Front 23

Equivalence Elimination

Back 23

j. A<=>B

A=>B (<=>E j)

Front 24

Equivalence Introduction

Back 24

j. A => B
k. B => A

A<=>B (<=>I j,k)

Front 25

Proof by contrapositive

Back 25

Prove that ¬Y => ¬X so Y is true because X is true.

Front 26

Proof by contradiction

Back 26

Prove that ¬Y is a contradiction so Y must be true.

Front 27

Symmetric Difference

Back 27

Contains the elements in one set or the other but not both.

Front 28

|AUB|

Back 28

|A| + |B| - |A∩B|

Front 29

AxB

Back 29

{(a,b):a in A and b in B}

Front 30

|AxB|

Back 30

|A| x |B|

Front 31

Power Set

Back 31

A collection of all the subsets of the given set.

Front 32

|P(A)|

Back 32

2^|A|

Front 33

C(n,k)

Back 33

The number of k-element subsets of a set of size n.

Front 34

Weak Induction

Back 34

If you grab 0, and grabbing something ensures you grab its successor, then you grab all the natural numbers.

Front 35

Strong Induction

Back 35

If you grab 0, and grabbing all a numbers predesessors ensures you grab that number, then you grab all the natural numbers.

Front 36

Least Number Principle

Back 36

If you grab a non-empty collection of natural numbers, then you
grab a smallest one.

Front 37

Reflexive

Back 37

For all a in A, (a, a) is in R.

Front 38

Symmetric

Back 38

For all a, b in A, (a, b) in R implies (b, a) in R.

Front 39

Antisymmetric

Back 39

When (a, b) in R and (b, a) in R, a =b.

Front 40

Transitive

Back 40

For all a, b, c in A, (a, b) in R and (b, c) in R implies (a, c) in R.

Front 41

Equivalence Relation

Back 41

Reflexive, Symmetric and Transitive.

Front 42

Equivalence Class

Back 42

Set of elements related to one another.

Front 43

Partition

Back 43

Collection of cells of A.
- The union of the cells is A.
- The cells are pairwise disjoint.

Front 44

Partial Order

Back 44

Reflexive, Antisymmetric, Transitive.

Front 45

Refinement

Back 45

One equivalence relation R is a refinement of another S if every cell of R is a subset of some cell of S.

Front 46

Po-isomorphic

Back 46

Two partial order are po-isomorphic if they have the same unlabelled Hasse diagram.

Front 47

Function

Back 47

A function from A to B
- The domain of f is A.
- if xfy and xfz then y=z.

Front 48

Injective Function

Back 48

f(x1)=f(x2) implies x1=x2.

Front 49

Surjective Function

Back 49

The range of f is B.

Front 50

Bijective Function

Back 50

Injective and surjective.

Front 51

Graph

Back 51

A set of vertices, a set of edges and incidence relation between them such that each edge is incident with either 1 or 2 vertices.

Front 52

Simple Graph

Back 52

No loops or parallel edges.

Front 53

Walk

Back 53

An alternating sequence of vertices and edges. Such that ei is incident with both vi and vi+1.

Front 54

Path

Back 54

A walk with no duplicate vertices.

Front 55

Closed Walk

Back 55

The first and last vertex are equal.

Front 56

Cycle

Back 56

A closed walk in which only the first and last vertex is equal.

Front 57

Incidence Matrix

Back 57

Rows are labelled by vertices and columns by edges. i,j is 1 if vi is incident with ej otherwise it is 0.

Front 58

Adjacency Matrix

Back 58

Rows and columns labelled by vertices. 1 if there is an edge connecting the two vertices.

Front 59

Degree of a vertex. d(v)

Back 59

The number of edges incident with it.

Front 60

The handshaking lemma.

Back 60

The sum of the degrees of the vertices is twice the number of edges.

Front 61

Connectivity

Back 61

The vertex u is connected to vertex v if there is a walk from u to v.
ρ is an equivalence relation.
The relation ρ on G. uρv only if and only if u is connected to v

Front 62

Components

Back 62

The equivalence classes of ρ are the components of G.

Front 63

Connected Graph

Back 63

Has only one component.

Front 64

Complete Graph

Back 64

Kn is the simple graph with n vertices and all possible edges.

Front 65

Number of edges of Kn

Back 65

n(n-1)/2

Front 66

Bipartite Graph

Back 66

It's vertex set can be partitioned into two sets V1 and V2 such that each edge of G joins a vertex in V1 to a vertex in V2.

Front 67

Length of a cycle

Back 67

Number of edges in it.

Front 68

A graph is bipartite if and only if...

Back 68

Every cycle has even length.

Front 69

Complete Bipartite Graph

Back 69

Km,n has vertex set V1 U V2, where |V1|=m, |V2|=n and there is an edge between each vertex in V1 and each vertex in V2.

Front 70

Number of edges of Km,n

Back 70

mn

Front 71

Isomorphism

Back 71

A pair of bijections between G1 and G2, f:V1->V2 and g:E1->E2 such that v is incident with e in G1 if and only if f(v) is incident with g(e) in G2.

Front 72

Tree

Back 72

A connected graph with no cycles.

Front 73

Forest

Back 73

Graph with no cycles.

Front 74

G\e

Back 74

The graph obtaining by deleting the edge e from G.

Front 75

Isthmus

Back 75

An edge e of a connected graph G is an isthmus if G\e is disconnected.

Front 76

An edge e of the connected graph G is an isthmus if and only if...

Back 76

It belongs to no cycles.

Front 77

A graph is a tree if and only if...

Back 77

It is connected and every edge is an isthmus.

Front 78

If e is an isthmus of the connected graph G, then G\e has exactly ... components.

Back 78

2.

Front 79

Let G be a connected graph with v vertices. G is a tree if and only if...

Back 79

It has v-1 edges.

Front 80

A tree with more than one vertex has ... vertices of degree one.

Back 80

At least two.

Front 81

Length of a path

Back 81

The number of edges in it.

Front 82

Spanning Tree

Back 82

A spanning tree of G is a tree whose vertex set is V and whose edge set is a subset of E.

Front 83

Every connected graph has a...

Back 83

Spanning tree.

Front 84

Minimum-Cost Spanning Tree

Back 84

Sum of the weights of the edges is minimum amongst all spanning trees.

Front 85

Kruskal's Algorithm

Back 85

Order edges by increasing weight.
-Add each edge unless it forms a cycle.

Front 86

Planar Drawing

Back 86

A drawing of a graph on the plane such that no edges cross.

Front 87

Planar Graph

Back 87

A graph which has a planar drawing.

Front 88

Euler's Formula

Back 88

For any planar drawing of a connected planar graph G, we have v-e+f=2.

Front 89

In a connected simple planar graph with at least three vertices...

Back 89

e<=3v-6

Front 90

Contraction

Back 90

G/e. Remove e and fuse together the vertices that are endpoints of e.

Front 91

Minor

Back 91

A graph obtained by a sequence of deletions and contractions.

Front 92

If G is planar then...

Back 92

Any minor of G is planar.

Front 93

A graph is planar if and only if...

Back 93

It has no minor isomorphic to K5 or K3,3.

Front 94

Planar Dual

Back 94

G*. In each face draw a vertex and if there is an edge that the faces share, put an edge between the vertices.

Front 95

Chromatic Number

Back 95

The smallest number k such that G is k-colourable.

Front 96

The chromatic number of Kn.

Back 96

n.

Front 97

A graph has chromatic number 2 if and only if...

Back 97

It is bipartite.

Front 98

G\v

Back 98

The graph obtained by deleting v and all edges incident with v.

Front 99

If the largest degree of a vertex in a loopless graph G is k, then the chromatic number of G is...

Back 99

At most k+1.

Front 100

A loopless planar graph G has at least one vertex x with...

Back 100

d(x) <= 5.

Front 101

Finite

Back 101

A set is finite if it has cardinality n for some n.

Front 102

Countable

Back 102

An infinite set is countable if A is equicardinal with N, i.e. there is a bijection between A and N.