discrete math notes

Page 1

CHAPTER 1

Axiomatic Method - using assumptions of true propositions to form a new conclusion.

Axioms - propositions that are accepted as true.

Corollary - a proposition that follows just a few logical steps from a theorem.

Implication - a proposition in the form "If P, then Q". These sometimes use the form "P IMPLIES Q."

Indirect Proof - a proof by contradiction, where it is shown that if a proposition were false, then some false fact would be true. Since a false fact by definition can't be true, the proposition must be true.

Inference Rules - logical deductions used to prove new propositions using previously proved ones.

Lemma - a preliminary proposition useful for proving later propositions.

Modus Ponens - a proof of P together with a proof that P implies Q is a proof of Q.

Proposition - a statement that is either true or false.

Predicate - a proposition who's truth depends on the value of one or more variable.

Theorem - important true proposition.

Symbols:

^ & : the statement A ^ B is true if A and B are both true; else it is false.

v + || : the statement A v B is true if A or B (or both) are true; if both are false, the statement is false.

∃ : ∃ x: P(x) means there is at least one x such that P(x) is true.

¬ : the statement ¬A is true if and only if A is false.

→ : A → B is true only in the case that either A is false or B is true.

∀ : ∀ x: P(x) means P(x) is true for all x.

Page 2

CHAPTER 2

Prime Factorization Theorem - Every integer greater than one has a unique expression as a product of prime numbers.

Well Ordered - When a set of real numbers has a minimum element in each of its nonempty subsets.

The Well Ordering Principle (WOP) - Every nonempty set of non-negative integers has a smallest element.

Page 3

CHAPTER 3

Propositional Variables - P and Q, Boolean variables.

Truth Tables - A table that indicates when P and Q are true depending on their Boolean relationship (not, and, or, P -> Q, etc.)