Math 55 Midterm 1 UC Berkeley

Modus Ponens

deductive argument type: "If P, then Q; P, thus Q"

Modus Tollens

deductive argument type: "If P, then Q; Not Q, thus not P"

Hypothetical Syllogism

If P, then Q. If Q, then R. Therefore, if P, then R.

Disjunctive Syllogism

P or Q. Not P. Therefore Q.

Addition

P. Therefore P or Q

Simplification

p ∧ q

∴ p and Q

Conjunction

P. Q. Therefore P ^ Q

converse of p → q

q → p

Contrapositive of p → q

¬q → ¬p

inverse of p → q

¬p → ¬q

biconditional statement

p if and only if q

tautology

a compound proposition that is always true regardless of truth values that occur in it

Contradiction

A compound proposition that is always false

De Morgan's Law for Quantifiers

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

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

Universal Instantiation

∀xP(x)

∴P(c)

Universal Generalization

P(c) for some arbitrary c

∴ ∀xP(x)

Existential Instantiation

∃xP(x)

∴ P(c) for some c in domain

Existential Generalization

P(c) for some c

∴ ∃xP(x)

proof by contraposition

prove ¬q → ¬p

proof by contradiction

Assume statement we're trying to prove is F, then derive contradiction.

relatively prime

when the only common factor is one

Proof of Equivalence

To prove a biconditional statement, show p →q and q →p

Proof by Cases

Go through different cases

WLOG

Without Loss of Generality

Parity

One odd, one even or vice versa

Union AUB

set of elements in either A or B or in both

Intersection A ∩ B

elements in both A and in B

Two sets are disjoint if

A ∩ B ≠ ∅

Complement of A

Ā = B - A

Identity Laws: For all sets A

(a)A U ∅ = A

(b)A ∩ ∅ = ∅

Idempotent Laws

A U A = A

A ∩ A = A

Commutative

A U B = B U A

Associative (same for n)

(AUB) U C = A U (BUC)

Distributive

A ∩ (B U C) = (A ∩ B) U ( A ∩ C)

A U (B ∩ C) = (A U B) ∩ (A U C)

De Morgan's Laws

(a) complement of (AUB) = complement of A U complement of B

(b) complement of (A ∩ B) = complement of A ∩ complement of B

If f: A → B, say A is

domain

If f: A → B, say B is

codomain

If f(a) = b, say b is the

image of a

If f(a) = b, say a is a

preimage of b

Range of f is

the set of all images of elements of A

injective/one-to-one

iff f(a)=f(b) → a=b for all a, b in domain

Surjective/onto

every "B" has at least one matching "A" (maybe more than one).

Bijective

Both injective and surjective

geometric progression

a sequence of form a, ar, ar^2, ar^3, ... where initial term a and common ratio r are real

arithmetic progression

a sequence of form a, a+d, a+2d, a+3d, ... where initial term a and common difference d are real

Countable

A set that is finite or has same cardinality as positive integers

decimal representation

good when proving the set of ℝ is uncountable

a ≡ b (modm)

if m | (a-b)

iff amodm ≡ bmodm,

then a ≡ bmodm

Let m be a positive integer. If a ≡ b (modm) and c ≡ d (modm,

then a + c ≡ b + d (modm) and ac ≡ bd (modm)

base b expansion of n when b is a positive integer greater than 1

n=a_k•b^k+a_k-1•b^k-1+...+a_1b+a_0

Binary Expansion

Base 2

Decimal Expansion

Base 10

Division Algorithm

a = dq + r

q = adivd

r = amodd

Fundamental Theorem of Arithmetic

Every positive integer greater than 1 can be written uniquely as prime or as product of 2 or more primes, where primes written in weakly increasing order

If n is composite, then

n has a prime divisor less than or equal to the square root of n

Euclidean Algorithm for GCD

Divide larger number by smaller, then divide smaller number by remainder, then divide remainder by new remainder... until get remainder 0

Bezout's Theorem

If a, b are positive integers, then there exists integers s, t such that gcd(a,b) = sa + tb