Terms

Logical equivalence

Distribution laws for quantifiers: Upside-down A distributes over OR and E distributes over OR but not vice versa

Negation law quantifiers: negation applied to a ‘for all’ will become there exists and vice versa

Tautology: Always valid/ T

Counterexample: list what P and Q have to be in order to make the propositions have their truth values that show that the argument is not valid

Rules of inference for quantified statements

Universal Instantiation: ‘For all x in X, P(x), therefore P(c) for an arbitrary c in X’

Universal Generalization: ‘P(c) for an arbitraty c in X, therfore For alll x in X, P(x)’

Existential Instantiation: ‘There exists x in X s.t. P(x), P(c) for all c in X

Existential Generalization: ‘P(c) for some c in X, therefore, there exists x in X, P(x)

Proof: A valid argument that establishes the truth of a mathematical statement

ODD integer in Z: can always be expressed as “there exists K in Z s.t. n = 2k''

EVEN integer in Z: can always be expressed as “there exists K in Z s,t, n = 2*k+1”

Direct Proof(P → Q): Assume P is True, then show step-by-step that Q must follow

Indirect Proof (Contraposition): To prove P → Q, assume ¬Q is True, then show ¬P must follow (Prove the Contrapositive)

Corollory: let n be in Z, if N² is even, then n is even.

Proof by Contradiction (General) To prove P, assume ¬P is True, then derive a logical contradiction (Impossible situation)

Proving a biconditional statement: Show the implication of both side, ie P→Q and P←Q(Q→p)

Lemma: For all n in Z, n² does not equal 3

Proof by equivalence:

Proof by cases

Proposition: A statement that is either true or false not both

Theorem: A statement or proposition that has been proven to be true based on established axioms, definitions, and previously proven theorems

Conjecture: Statement where the truth value is unknown

Set defintions

A is included in B: denoted by a U rotated 90 degrees with an underline, if and only if x is an element A implies x is an element of B

A Includes B: is the opposite denoted by (Backwards U rotated -90 degrees with an underline, if and only if B (U rotated 90 degrees) A

A is equal to B: denoted by A=B, stated as if and only if A (U rotated 90 degrees) B and B is less than or equal to A(?)

Set Operations (A & B are sets)

Intersection: denoted by a upside down U(A (upside down U) B), and contains what the two sets have in common

Union: denoted by “A U B”, contains the “union” of both sets ie all of the elements from both sets in one

Difference: Denoted by A \ B or A - B, meaning that we remove anything A had in common with B

Symmetric difference: A (Triangle) B, meaning that the new set contains every unique from A and B (ie we remove any thing they shared in common) (equivalent to saying (AUB)\(A(upside down U) B) as this removes everything A and B had in common)

Compliment: For A is included in B, x difference A is the complement of A in x, If x is clear from context, we may write A^c for the complement of A

(Lecture 6 &7 to do later)