Discrete Midterm 1 Flashcards

Argument form

A pattern of reasoning; it is valid if the conclusion is true whenever all premises are true

Modus Ponens

From p and p ⇒ q conclude q

Modus Tollens

From ∼q and p ⇒ q conclude ∼p

Disjunctive addition

From p conclude p ∨ q

Conjunctive addition

From p and from q (separately) conclude p ∧ q

Conjunctive simplification

From p ∧ q conclude p and also conclude q

Disjunctive syllogism

From p ∨ q and ∼p conclude q

Hypothetical syllogism

From p ⇒ q and q ⇒ r conclude p ⇒ r

Division into cases

From p ∨ q and p ⇒ r and q ⇒ r conclude r

Resolution

From p ∨ q and ∼q ∨ z conclude p ∨ z

Tautology

A statement that is true for every truth assignment (example: p ∨ ∼p)

Contradiction

A statement that is false for every truth assignment (example: p ∧ ∼p)

Logical equivalence (≡ in logic)

Two statements have the same truth table

Commutativity

p ∧ q ≡ q ∧ p and p ∨ q ≡ q ∨ p

Associativity

(p ∧ q) ∧ r ≡ p ∧ (q ∧ r) and (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)

Distributivity

p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) and p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)

Identity laws

p ∧ T ≡ p and p ∨ F ≡ p

Negation laws

p ∨ ∼p ≡ T and p ∧ ∼p ≡ F

Double negation

∼(∼p) ≡ p

Idempotence

p ∧ p ≡ p and p ∨ p ≡ p

De Morgan's laws

∼(p ∧ q) ≡ ∼p ∨ ∼q and ∼(p ∨ q) ≡ ∼p ∧ ∼q

Universal bound laws

p ∨ T ≡ T and p ∧ F ≡ F

Absorption laws

p ∨ (p ∧ q) ≡ p and p ∧ (p ∨ q) ≡ p

Negations of T and F

∼F ≡ T and ∼T ≡ F

Contrapositive

p ⇒ q ≡ ∼q ⇒ ∼p (always equivalent to the original)

Inverse error

p ⇒ q is NOT equivalent to ∼p ⇒ ∼q (invalid reasoning)

Converse error

p ⇒ q is NOT equivalent to q ⇒ p (invalid reasoning)

Converse

The statement q ⇒ p formed from p ⇒ q

Inverse

The statement ∼p ⇒ ∼q formed from p ⇒ q

Biconditional equivalence

a ⇔ b ≡ (a ⇒ b) ∧ (b ⇒ a)

Implication as disjunction

a ⇒ b ≡ ∼a ∨ b

Negation of an implication

∼(p ⇒ q) ≡ p ∧ ∼q

Vacuous truth

An implication p ⇒ q with a false hypothesis p is true

∀ (for all quantifier)

∀x P(x) says P(x) holds for every x in the domain

∃ (there exists quantifier)

∃x P(x) says P(x) holds for at least one x in the domain

Negation of ∀

∼(∀x P(x)) ≡ ∃x ∼P(x)

Negation of ∃

∼(∃x P(x)) ≡ ∀x ∼P(x)

Counterexample

A single element that makes P(x) false; it disproves a ∀ statement

Constructive proof of ∃

Explicitly exhibit or construct an element that works

Non-constructive proof of ∃

Show an element must exist without producing it

Direct proof

Assume the hypothesis and derive the conclusion with definitions and algebra

Proof by contraposition

To prove p ⇒ q prove ∼q ⇒ ∼p instead

Proof by contradiction

Assume the negation of the claim and derive a falsehood; so the claim is true

Proof by cases

Split into exhaustive cases and prove the claim in each (uses division into cases)

Closure

Combining integers with + or × always gives an integer (also true for ℚ under + and ×)

Even

An integer n is even if n = 2k for some integer k

Odd

An integer n is odd if n = 2k + 1 for some integer k

Parity

Whether an integer is even or odd

Parity rules

even + even = even; odd + odd = even; even + odd = odd; odd × odd = odd; any × even = even

Parity lemma

n² is even ⇒ n is even (equivalently n odd ⇒ n² odd)

Divides (a | b)

a divides b iff b = a·k for some integer k

Prime

An integer greater than 1 whose only positive divisors are 1 and itself

Composite

An integer greater than 1 that is not prime

Prime divisibility lemma

If a prime p divides a² then p divides a (works for any prime; fails for composites like 4)

Euclid's lemma

If a prime p divides a·b then p divides a or p divides b

Unique Prime Factorization Theorem

Every integer n ≥ 2 is a product of primes in exactly one way up to reordering

Infinitely many primes

Proved by contradiction: if p₁ to pₙ were all the primes then p₁···pₙ + 1 has a prime factor not in the list

Rational number

A number a/b with a and b integers and b ≠ 0

Congruence (a ≡ b (mod m))

m divides a − b; a and b have the same remainder mod m

Congruence addition property

If a₁ ≡ b₁ and a₂ ≡ b₂ (mod m) then a₁ + a₂ ≡ b₁ + b₂ (mod m)

Congruence multiplication property

If a₁ ≡ b₁ and a₂ ≡ b₂ (mod m) then a₁·a₂ ≡ b₁·b₂ (mod m)

Congruence power property

If a ≡ b (mod m) then aᵏ ≡ bᵏ (mod m) for k ≥ 0

Congruence is an equivalence relation

It is reflexive (a ≡ a); symmetric (a ≡ b ⇒ b ≡ a); and transitive (a ≡ b and b ≡ c ⇒ a ≡ c)

Even and odd in mod notation

Even means a ≡ 0 (mod 2); odd means a ≡ 1 (mod 2)

Quotient-remainder theorem

For integer n and m > 0 there are unique q and r with n = mq + r and 0 ≤ r < m

Set

An unordered collection of distinct objects

Membership (∈)

x ∈ A means x is an element of A

Not a member (∉)

x ∉ A means x is not an element of A

Subset (A ⊆ B)

Every element of A is also in B; ∀x (x ∈ A ⇒ x ∈ B)

Proper subset (A ⊂ B)

A ⊆ B and A ≠ B

Set equality

A = B iff A ⊆ B and B ⊆ A

Empty set (∅)

The set with no elements; it is a subset of every set

{∅}

A set with exactly one element (the empty set); it is NOT empty

Power set P(A)

The set of all subsets of A; if |A| = n then |P(A)| = 2ⁿ

Power set of the empty set

P(∅) = {∅} which has 1 element

Set difference (A − B)

The elements that are in A but not in B (removes from A anything that also appears in B)

Union (A ∪ B)

Elements that are in A or in B (or both)

Intersection (A ∩ B)

Elements that are in both A and B

Complement (Aᶜ)

All elements of the universe that are not in A

Disjoint sets

Two sets with empty intersection

Cardinality |A|

The number of elements in a finite set A

Natural numbers (ℕ)

The counting numbers (1 2 3 … in this course)

Integers (ℤ)

All whole numbers positive negative and zero

Rationals (ℚ)

All fractions a/b with integers a and b ≠ 0

Dense set

A set where between any two elements there is another element of the set (ℚ is dense; ℤ is not)