# 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

• 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

• 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