Introduction to Discrete Mathematics: Logic, Sets, and Functions

Posted on Sep 5, 2024 in Electronics

Logic and Proof

Propositional Logic

Twelve Ways to Say: p ⇒ q

  • If p, then q.
  • If p, q.
  • q if p.
  • q when p.
  • p is sufficient for q.
  • q is necessary for p.
  • A sufficient condition for q is p.
  • A necessary condition for p is q.
  • p implies q.
  • p only if q.
  • q whenever p.
  • q follows from p.

Related Conditional Statements

  • Contrapositive: ¬ q → ¬ p
  • Inverse ¬ p: → ¬ q
  • Converse: q → p

Biconditionals

  • “p is necessary and sufficient for q”
  • “If p then q, and conversely”
  • “p iff q”

Precedence

  • Neg
  • And, or
  • Implies or biconditional

Propositional Equivalences

  • Tautology is always true while contradictions are always false
  • Distributive Laws
    • p ∨ (q ∧ r) ≡ (p v q) ∧ (p v r)
    • p ∧ (q v r) ≡ (p ∧ q) v (p ∧ r)
  • De Morgan’s Laws
    • ¬(p ∧ q) ≡ ¬p v ¬q
    • ¬(p ∨ q) ≡ ¬p ∧ ¬q

Predicate Calculus

Predicate Logic

  • Let P(x) denote …

Quantifiers

  • Universal
    • P(x1) ^ P(x2) ^ (Px3)
  • Existential
    • P(x1) or P(x2) or (Px3)
  • Uniqueness (May be unnecessary)
    • ∃!x
    • There is exactly one…

De Morgan’s Laws

  • ¬∃x P(x) ≡ ∀x ¬P(x)
  • ¬∀x P(x) ≡ ∃x ¬P(x)

Nested Quantifiers

  • Nested quantifiers
    • ∀x ∃x Q(x) ≡ ∀x (∃x Q(x))
    • Read from the left quantifier to the right quantifier for ordering
  • Quantifying Two Variables
    • ∀x∀yP(x, y) ≡ ∀y∀xP(x, y) = true when P(x, y) is true for every x and y
    • ∀x∃yP(x, y) = true when for every x, there is a y for which P(x, y) is true
    • ∃x∀yP(x, y) = true when there is an x for which P(x, y) is true for every y
    • ∃x∃yP(x, y) ≡ ∃y∃xP(x, y) = true when a pair (x,y) for P(x, y) is true
  • Negating Nested Quantifiers
    • ¬∃x∀yP(x, y) = ∀x¬∀yP(x, y) = ∀x∃y ¬P(x, y)

Rules of Inference

  • Look to Table 1 on rules
  • Quantifiers: Look at Table 2
  • Fallacies
    • Denying the hypothesis

Introduction to Proofs

TERMS

  • Theorem is a statement that can be proven true
  • Proposition are less important theorems
  • Use proofs to justify theorems
    • Include axioms (or postulates): Statements assumed to be true
  • Lemma is a less important theorem that is helpful in the proof
  • Corollary is a statement that can be established directly from a theorem
  • A conjecture is a statement that is being proposed to be a true statement

Direct Approach or p → q:

  • Assume that p is true and with rules of inference prove that q is true

Proof by Contraposition:

  • Assume that ¬q is true and try to prove that ¬p

Proof by Contradiction

  • Give an example where the theorem fails

Proof by Exhaustion: Try everything (only works with a finite number of possibilities)

Proof by Cases: You can break things into groups and show that certain groups work

Proof by Implication

  • Assume P is true
    • Assume P, P then Q, therefore Q
    • Holds because if P is true you get Q and if P is false then Q is automatically implied
    • After you prove Q it is no longer safe to assume P still holds
  • Prove the contrapositive
    • Assume Not Q show that it implies Not P

Proving Biconditional

  • Prove each implies the other
    • P implies Q and Q implies P
  • Construct a chain of iffs
    • Show P iff R iff Q so P iff Q

Existence Proof:

  • Constructive:
    • Find an x that satisfies ∃xP(x)
  • Non-Constructive:
  • Proof by contradiction and show that the negations of the existential quantification implies a contradiction

Proof Strategies:

  • If statement is a conditional statement: (1) direct proof, (2) indirect proof, (3) Proof by Contradiction

Sets, Functions, Sequences and Sums

Sets

  • A set is an unordered collection of objects
    • Objects in a set are called the elements/members
  • Number Sets
    • N = Natural numbers
    • Z = Integers
    • Q = rational numbers
    • R = real numbers
    • ∅ = the empty set = {}
  • Sets are equal iff they have the same elements
    • Repetition and order don’t matter
  • S⊆T
    • T and S⊆T
  • Proper Subset
    • S⊂T: S⊆T
  • Cardinality(|S|): distinct elements in S
  • Power set (P(S)): The set of all subsets of the S
  • Cartesian Products
    • Ordered n-tuple: is the ordered collection that has a1 as its first element… and an as its nth element
    • Two ordered n-tuples are equal iff each corresponding pair of their elements is equal
    • A x B ={(a,b)| a∈A b∈B}
      • A x B= {(1,a),(2,a),(1,b),(2,b)}
  • Truth sets of Quantifiers
    • P(x) = |x| = 1 where {x∈Z | |x| = 1} = {1,-1}
      • ∀xP(x) over domain U true iff U is the truth set of P
      • ∃xP(x) over domain U true iff U is nonempty

Set Operations

  • Unioning (∪) two sets combines all the elements of two sets (additive)
  • Intersection (∩) creates a set containing all elements contained by both sets
    • Disjoint: if intersection of intersection is an empty set
  • Subtraction (–) creates a set containing only elements of either on or the other set but not both
    • Complement of B with respect to A = A-B
  • U is the universal set

Functions

  • f(a) → b
    • b is the image of a
    • a is the preimage of b’
    • f maps A to B
  • If f1 and f2 are functions from A to R
    • f1 + f2 = A to R
    • f1 * f2 = A to R
  • Injection: One to One
    • Horizontal line test: every mapping to Y has exactly one value in X
    • f(a) = f(b) implies that a = b for all a and b in domain of f
  • Surjective
    • A function f from A to B surjective iff every element b in B and there is an element A with f(a) = b
  • Bijection is Surjective and Injective
  • f-1 (b) = a

Sequences and Summations

  • A sequence is a function from a subset of the set of integers
    • Use an to denote term
    • Arithmetic and Geometric sequences

Modular Arithmetic and Division

  • Division
    • a|b denotes that such that b = ac
    • a is a multiple of b
  • Modular arithmetic
    • Amod m = b mod m