C959 Flashcards (Master set) latest updated version with 100% correct answers 2026-2027

Proof by Exhaustion

Prove the statement by checking each element individually. Unlike proof by cases, exhaustive proof looks at every case in a way that is not general.

Proof by Counterexample

Used to disprove a universal statement. For example, to disprove the statement, "All prime numbers are odd" find one example where this statement is false—the number 2—which is both even and prime.

Direct Proof

In the direct proof, we assume the hypothesis p is true and we try to prove that q is true. Thus making p→q true.

Proof by Contrapositive

A proof that makes use of the fact that p→q is equivalent to its contrapositive ¬q→¬p. So we assume that ¬q is true and try to prove that ¬p is true.

Proof by Contradiction

An indirect proof where if the theorem being proven has the form p → q, then the beginning assumption is p ∧ ¬q which is logically equivalent to ¬(p → q).

Proof by Cases

In proof by case, we are looking at all the possible cases that might arise in a theorem.

∴

Means "therefore".

Conditional Statements

If p then q. p → q. Only not true when p is true and q is false. It breaks the contract.

Converse

Converse of p → q is q → p.

Contrapositive

Contrapositive of p → q is ¬q → ¬p.

Inverse

Inverse of p → q is ¬p → ¬q.

Biconditional Statement

p if and only if q. p ↔ q. True when p and q have the same truth value (including False ↔ False) and is false when p and q have different truth values.

Logical Equivalence

p is logically equivalent to q. p ≡ q. Logically equivalent if they have the same truth value regardless of the truth values of their individual propositions. So p ≡ ¬¬p or ¬p ≡ p → ¬q.

Logical Operator

Conjunction — p ∧ q. True only if p and q are true.

Disjunction — p ∨ q. True when either of p or q, or both is true.

Exclusive or — p ⊕ q. True if either one of p or q is true but not both.

Negation — ¬p. Negates value. If True then not True, if False then not False.

Order of Operations

1. ¬ (not)

2. ∧ (and)

3. ∨ (or)

4. →

5. ↔

Predicate

Logical statement whose truth value is a function of one or more variables.

Free Variable

Variable is free to take on any value in the domain. In (∀x P(x)) ∧ Q(x), Q(x) is the free variable.

Bound Variable

Variable is bound to a quantifier. In (∀x P(x)) ∧ Q(x), P(x) is the bound variable.

DeMorgan's Laws for Quantifiers

¬∀ x F(x) as "Not every bird can fly." Which is logically equivalent (≡) to ∃ x ¬ F(x) as "There exists a bird that cannot fly."

¬∃ x Q(x) as "It is not true that there is a child in the class who is absent today." Which is logically equivalent (≡) to ∀ x ¬ Q(x) as "Every child in the class is not absent today."

Logical Symbol and Translations

-∀x∀y M(x,y)

- ∃x∃y M(x,y)

- ∃x∀y M(x,y)

- ∀x∃y M(x,y)

DeMorgan's Law for Nested Qualifiers

N

The set of natural numbers: All integers greater than or equal to 0.

For example, 0, 1, 2, …

Z

The set of all integers. For example, …, -2, -1, 0, 1, 2, …

Q

The set of rational numbers: All real numbers that can be expressed as a/b, where a and b are integers and b ≠ 0.

For example, 0, 1/2, 5.23, -5/3

R

The set of real numbers. Real numbers can be a continuous quantity.

For example, 0, 1/2, 5.23, -5/3, π, √2

Universal Set

A = B if and only if A ⊆ B and B ⊆ A

Proper Subset

An element of B that is not an element of A (i.e., A ≠ B). A ⊂ B.

Composition of Functions

f and g are two functions, where f: X → Y and g: Y → Z. The composition of g with f, denoted g ο f, is the function (g ο f): X → Z, such that for all x ∈ X, (g ο f)(x) = g(f(x)).

Composition of Functions (Example)

If f: R+ → R+, f(x) = x³ and g: R+ → R+, g(x) = x + 2. Then, (f ο g)(x) = f(g(x)) = (x + 2)³ and (g ο f)(x) = g(f(x)) = x³ + 2.

Exponential Functions

Logarithmic Functions

Cartesian Product

A and B, denoted A x B, is the set of all ordered pairs in which the first entry is in A and the second entry is in B. A x B = { (a, b) : a ∈ A and b ∈ B }.

Set Partitions

A non-empty set A is a collection of non-empty subsets of A such that each element of A is in exactly one of the subsets. Requirements:

- For all i, Aᵢ ⊆ A.

- For all i, Aᵢ ≠ ∅

- A₁, A₂, ...,Aₙ are pairwise disjoint (their intersections are empty).

- A = A₁ ∪ A₂ ∪ ... ∪ Aₙ

Prime Number

A number that can only be multiplied by 1 and itself. CAN BE EVEN and ODD. Cannot be negative. Example: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, etc.

Composite Number

A whole number that can be made by multiplying other whole numbers. CAN BE ODD and EVEN. Can be negative. Example: 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49, 50, 51, 52, 54, 55, 56, 57, 58, 60, 62, 63, 64, 65, 66, 68, 69, 70, 72, 74, 75, 76, 77, 78, 80, 81,82, 84, 85, 86, 87, 88, 90, 91, 92, 93, 94, 95, 96, 98, 99.

Inverse Finding

To inverse, the equation must be bijective. So, f(x) = y if and only if f-1(y) = x.

f: R → R, where f(x) = -x + 3. What is f-1? (Inverse)

The result of solving the equation

y = -x + 3 for x is x = -y + 3.

Therefore, f-1(y) = -y + 3 which is the same as f-1(x) = -x + 3.

f(x) = 3x + 1 and g(x) = x². Then, What is (f ο g)(2)? (Compositing)

Work inside out. (f o g)(x) = f(g(x)).

Apply g(2) into x² to get 4.

Then plugin 4 into 3x + 1 for f(4) which is 13. The answer is 13.

Sets of Sets

A = { { 1, 2 }, ∅, { 1, 2, 3 }, { 1 } }

- { 1, 2 } ∈ A.

- 1 is not an element of A, so 1 ∉ A, although { 1 } ∈ A.

- Furthermore, { 1 } ⊈ A since 1 ∉ A.

- The empty set ∅ is not the same as { ∅ }.

Power Sets

Set A, denoted P(A), is the set of all subsets of A.

if A = { 1, 2, 3 }, then:

-- P(A) = { ∅, { 1 }, { 2 }, { 3 }, { 1, 2 }, { 1, 3 }, { 2, 3 }, { 1, 2, 3 } }

Set Cardinality

The cardinality of a finite set A, denoted by |A|, is the number of elements in A. If A = { 2, 4, 6, 10 }, then |A| = 4.

Boolean Satisfiability, Gates, Circuits

Minterm

A product of literals u₁u₂...uᵢ such that each uⱼ is either vⱼ or vⱼ.

Disjunctive Normal Form (DNF)

A Boolean expression that is a sum of products of literals. c₁ + c₂ + .... + cm where each cⱼ for j ∈ {1, ..., m} is a product of literals.

Conjunctive Normal Form (CNF)

A Boolean expression that is a product of sums of literals, d₁ • d₂ • .... • dm where each dⱼ for j ∈ {1, ..., m} is a sum of literals.

Sequence

of nth term is 2ⁿ.

Solving a sequence depends on the formula.

So tₙ = 5ₙ - 4 if n = 1 would be t₁ = 5(1) - 4 = 1.

Piece Wise Formula

(Solution in Picture)

{ 2ₙ³ if n is odd.

aₙ ={

{5ₙ/2 if n is even.

Common Ratio

A geometric sequence is a sequence that increases or decreases by a constant factor. Such as moving up x6, or moving down /2.

Common Difference

Each term increases or decreases by the same constant value. Such as moving up +4 or moving down -10.

Open walk

A walk in which the first and last vertices are not the same. So, {4, 5, 6, 1, 2}

Closed walk

A walk in which the first and last vertices are the same. So, {4, 5, 6, 1, 4}

Trail

An open walk in which no edge occurs more than once.

Circuit

Is a closed walk in which no edge occurs more than once. ⟨ 1, 2, 3, 2, 1 ⟩

Path

Is a trail in which no vertex occurs more than once.

Cycle

A circuit of length at least 1 in which no vertex occurs more than once, except the first and last vertices which are the same. For example, ⟨2, 3, 2⟩

Adjacency Matrix

A matrix that records the number of direct links between vertices.

Reflexive

All self-loops are present.

Symmetric

If (x,y) is an edge, then (y,x) is also an edge.

Trasitive

Edges (e,a) and (a,b) imply the presence of edge (e,b).

Hasse Diagram

Only used for partial orders. Generally works bottom (lowest number) to top. It will always be in the same direction due to the anti-symmetry property.

Partially Ordered Set

The domain is {3, 5, 6, 7, 10, 14, 20, 30, 60}.

x ⪯ y or "x is at most y" if x evenly divides y.

Free Tree

When there is no particular organization of the vertices and edges.

Rooted Tree

When there is a root and items are set in a particular order.

Parents

Can include the root as well. Any branch that has a child.

Ancestor

The ancestors of vertex g are h, d, and b. Every vertex along the path from v to the root (except for the vertex v itself) is an ancestor of vertex v.

Child

Vertices c and g are the children of vertex h.

Descendant

The descendants of vertex h are c, g, and k.

Leaf

A vertex which has no children. (Ex: The leaves are a, f, c, k, i, and j.)

Sibling

They have the same parent. (Ex: Vertices h, i, and j are siblings because they have the same parent, which is vertex d.)

Maximum Cycle in a Graph

With a graph of n vertices, the length of a cycle can be no longer than n. Example of the picture, since it has 6 vertices, the graph can have no longer than 6.

Maximum Path in a Graph

With a graph of n vertices, the maximum length of a path would be n-1. For example, in the picture of nine vertices, the length of the path is 8: ⟨C, I, F, D, A, E, B, H, G⟩

Maximum Walk in a Graph

For a graph of n vertices, there is no longest walk assuming that there is at least one edge in the graph.

Preorder

The root is visited before the children.

Post-Order

The root is visited after the children.

Breadth-First

Visits vertices in the graph according to their proximity to the start vertex. Starting at a root vertex scan each neighbor before scanning their neighbors.

Depth-First

Starting at a root vertex, scan each neighbor and its neighbors and their neighbors. Once a neighbor has no more neighbors, backtrack to the previous neighbor and exhaust its neighbors.

Isomorphic Graph

Check by seeing if they have:

-Same number of vertices

-Same number of edges

-Same number of vertice degrees.

Total degree of Graph

The sum of the degrees of all of the vertices. For example, the total degree of the picture is 2 + 3 + 3 + 2 + 2 = 12.

(Hint: Just multiply the number of edges by 2. In the picture, there are 6 edges, so 12 is the total degree).