Discrete Mathematics Foundations: Sets, Logic, Graphs, and Proofs

Speaking Mathematically: Core Concepts

The Language of Sets

• ∀ - Universal quantifier (true for all values of a variable in a set)
• ∃ - Existential quantifier (true for at least one value of a variable in a set)

Common Set Notations:

• R - Set of all real numbers
• Z - Set of all integers
• Q - Set of all rational numbers
• N - Set of all positive integers
• (X)^+- - Positive/negative elements for a specific set X

x ∈ S means that x is an element of the set S.

• Example: x=5, S={1, 2, 3, 4, 5}

A ⊆ B means that A is a subset of the set B.

• Example: A={a,b}, B={a,b,c}
• Example: {2} ∈ {1, 2, 3} is false; {2} ∈ {{1}, {2}} is true; 2 ⊆ {1, 2, 3} is false; {2} ⊆ {1, 2, 3} is true
• Note: {9, 9, 1, 1, 7, 7} has only 3 distinct elements ({1, 7, 9}); {1, {2}} has 2 elements; {0} ≠ 0

Set-Builder Notation: {x ∈ S | P(x)}

• Means "the set of all elements x in S such that P(x) is true."

Cartesian Products

Ordered n-tuples are of the form (x₁, x₂, ..., x_n).

• (a, b) = (c, d) means a = c and b = d
• Example: (1, 2) ≠ (2, 1) ||| (3, 5/10) = (√9, ½)

Given A={x,y} and B={1,2,3}, A × B = {(x,1), (x,2), (x,3), (y,1), (y,2), (y,3)}.

• If C={a,b,c}, then (A × B) × C = {((x,1), a), ((x,2), a), etc.} while A × B × C = {(x,1,a), (x,2,a), (x,3,a), (y,1,a), etc.}

String Operations:

• L("aaa") means the length of string "aaa", which is 3.
• C("bbb") means concatenation of "bbb" at the end of a string, which for "a" is "abbb".

The Language of Relations and Functions

In A × B, the domain is the set A and the co-domain is the set B.

x R y means the pair (x,y) is an element in the set R.

Arrow Diagram of a Relation:

• Example: A={1,2,3}, B={1,2,3}.
• For every (x,y) ∈ A × B, (x,y) ∈ S means x < y. S = {(1,2), (1,3), (2,3)}

A function F from set A to set B is a relation, with domain A and co-domain B, that satisfies the following:

1. For every element x in A, there is an element y in B such that (x,y) ∈ F (every element in A is the first element of an ordered pair in F).
2. For all elements x in A and (y and z) in B, if (x,y) ∈ F and (x,z) ∈ F, then y=z (no two distinct ordered pairs in F have the same first element).

• Example: R = {(2,5), (4,1), (4,3), (6,5)} is not a function.
• Example: T = {(2,5), (4,1), (6,1)} is a function.

Types of Functions:

• Square Function: f(x) = x²
• Successor Function: g(n) = n + 1
• Constant Function: h(r) = 2 (same output no matter the input)

The Language of Graphs

• Vertex: A point on a graph.
• Edge: A line connecting a vertex to itself or another vertex (endpoint).
• Loop: An edge with one endpoint that connects a vertex to itself.
• Parallel Edges: Two or more edges with the same endpoints.
• Isolated Vertex: A vertex with no incident edges.
• Degree of Vertex: The number of edges incident (connected) to a vertex.
  • A loop contributes 2 to the degree of its vertex.
  • A simple edge contributes 1 to the degree of each of its two distinct endpoints.
  • An isolated vertex has a degree of 0.

Graph Components:

• Vertex Set: V(G) = {v₁, v₂, v₃, v₄, v₅, v₆}
• Edge Set: E(G) = {e₁, e₂, e₃, e₄, e₅, e₆, e₇}

Edge-Endpoint Function:

The Logic of Compound Statements

Logical Form and Logical Equivalence

• Argument: A sequence of statements aimed at demonstrating the truth of an assertion.
• Conclusion: The assertion at the end of a sequence of statements.
• Premises: The preceding statements that support the conclusion.
• Logic: The science of reasoning or the science of necessary inference.
• Tautology: A statement form that is always true.
• Contradiction: A statement form that is always false.

Logical Symbols:

• ~ - "Not" (Negation)
• ^ - "And" (Conjunction)
• ∨ - "Or" (Disjunction)
• → - "Implies" (Conditional)
• ↔ - "Biconditional" (If and only if)
• ∴ - "Therefore"
• ≡ - "Equivalence"

Conditional Statements and Their Forms

Statement Forms with their Equivalencies:

• "If p then q"; "q if p"; "p → q"; "~p ∨ q"
  • Only false when p is true and q is false.
• Negation of a Conditional Statement:
  • "p and not q"; (p ^ ~q)
• Contrapositive of an If-Then Statement:
  • "If not q then not p" (~q → ~p)
• Converse of If-Then:
  • "If q then p" (q → p)
• Inverse of If-Then:
  • "If not p then not q" (~p → ~q)
• Only-If Statements:
  • "p only if q" is equivalent to "If p then q" OR "If not q then not p".
• Biconditional Statement:
  • "p if, and only if q"; (p ↔ q)
  • Only false when p and q have different truth values.
• Necessary Conditions:
  • R is necessary for S; "If not R then not S" (~R → ~S).
• Sufficient Conditions:
  • R is sufficient for S; "If R then S" (R → S).

Important Notes:

• A Conditional statement and its Contrapositive are logically equivalent.
• The Converse and Inverse of a conditional statement are logically equivalent.
• "And" and "Or" are associated with the conjunction (p ^ q) and disjunction (p ∨ q) of arguments, respectively.

Examples of Logical Reasoning:

• Premises: "If {p} the bell rings OR {q} the flag drops, then {r} the race is over."
• Conclusion: "Therefore, if the race is not over, then the bell has not rung and the flag has not dropped." (This is the contrapositive of the premise, demonstrating logical equivalence.)

Truth Table Examples:

Example of Logical Equivalence between Statements:

• (p ∨ q) → r ≡ (p → r) ^ (q → r)

Logical Equivalence Laws:

Digital Logic Circuits

Basic Logic Gates:

• ▷• - NOT Gate (Inverter)
• ◑ - AND Gate
• ⮞ - OR Gate
• ◑• - NAND Gate (AND gate followed by a NOT gate)
• ⮞• - NOR Gate (OR gate followed by a NOT gate)

Recognizer: A circuit that has only one "1" value for its Input/Output (I/O) table.

Constructing an I/O Table from a Circuit:

• List all possible combinations of input signals and determine the output for each.

Constructing a Boolean Expression from a Circuit:

• Trace through the circuit from left to right, noting the output of each gate.

Constructing a Circuit from a Boolean Expression:

• Starting from the right of the diagram (the given expression), separate the expression by creating gates that correspond to its logical symbols (e.g., AND gate for ^, OR gate for ∨).

Constructing a Circuit from an I/O Table:

• Identify each row in the table with an output value of "1".
• Create an expression that joins these rows together using the AND operator (^).
• If needed, simplify the expression using logical equivalence laws.

Elementary Number Theory and Proof Techniques

Direct Proof and Counterexample

Mathematical Definitions:

• Math.floor(x) - Returns the largest integer less than or equal to x.
• n is even ↔ n = 2k, for some integer k.
• n is odd ↔ n = 2k + 1, for some integer k.
• n is prime ↔ ∀ positive integers r and s, if n = r × s, then either (r=1 and s=n) or (s=1 and r=n).
• n is composite ↔ ∃ positive integers r and s such that n = r × s and 1 < r < n and 1 < s < n.

Proof Techniques:

• Direct Proof: Text
• Proof by Contraposition: Text
• Proof by Contradiction: Text

Even, Odd, Prime, and Composite Integers

Text

Proving Existential Statements

Text

Indirect Argument: Contradiction and Contraposition

Text