# True Airspeed ()

Classified in Mathematics

Written at on English with a size of 43 KB.

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

Existentia

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

ST: ST

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 as its nth element

Two ordered n-tuples are equal iff each corresponding pair of their elements is equal

A x B ={(a,b)| aA bB}

A x B= {(1,a),(2,a),(1,b),(2,b)}

Truth sets of Quantifiers

P(x) = |x| = 1 where {xZ | |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 a_n 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