# Introduction to Discrete Mathematics: Logic, Sets, and Functions

## 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 a
_{1}as its first element… and a_{n}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)}

- Ordered n-tuple: is the ordered collection that has a
- 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

- P(x) = |x| = 1 where {x∈Z | |x| = 1} = {1,-1}

### 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

- b is the
- 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 a
_{n}to denote term - Arithmetic and Geometric sequences

- Use a

### 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