Discrete Math Unit 2 Key Terms for Lessons 7-9

im so hungry chat

EVEN DEFINITION (for any integer n)

There exists an integer k such that: n = 2k

ODD DEFINITION (for any integer n)

There exists an integer k such that: n = 2k + 1

PERFECT SQUARE (for any integer n)

There exists an integer k such that: n = k²

RATIONAL (for any real number x)

x = (a/b) where a & b are ints AND b DNE 0. OTHERWISE, x is said to be irrational.

Indirect Proof

Theorem is provided by proving a logically equivalent theorem instead of the original theorem

Proof by Contrapositive

Conclusion is assumed to be false AND the premise deduced to be false by invoking a series of axioms, definitions, and other theorems

Biconditional Proof

A proof for a biconditional statement in which it is shown that the premise implies the conclusion, AND that the conclusion implies the premise

Proof by Contradiction

Proof in which the premises are assumed to be true, the conclusion is assumed to be false, and a contradiction is derived

Proof by Counterexample

Proof that proves a universally quantified statement is false by providing a counterexample

Proof by Cases

Proof for a universal statement in which the domain can be divided up into several mutually exclusive cases, proving that the conclusion holds for each of the cases proves that it holds for the entire hypothesis

Elements

the objects in a set

The Empty Set

{ } , Ø

Equality of Sets

two sets are set to be equal IF AND ONLY IF they have the exact same elements. Order and repeated elements may be ignored.

Cardinality

Denoted by the number of elements in the set, denoted as |A|. Repeated elements do not contribute to the cardinality.

if n is a non-negative int:

|A| = n finite

otherwise,

A is infinite

Power Set

The Power Set is the set of all of the subsets in the given set.

iF |S| = n, then |P(S)| = 2^n