Discrete Math

discrete objects

can always be itemized/counted and measurable

not discrete

no gap in the contents of an object, continuous

N+

the set of natural numbers without zero

N0

set of natural numbers with zero

set

an unordered collection of distinct objects

element

each object in a set

belonging to

What symbol is this: ∈

unordered (no order at all in a set)

distinct (no duplicate of any element)

What are the two criteria for a set?

the empty set (∅)

the set with no element

cardinality

the number of elements in S

cardinality

What does this denote: |S|

continuous

Is the set of real numbers continuous or discrete?

discrete

Is the set of natural numbers continuous or discrete?

def of set equality

A set A equals to another set B if and only if they have the same elements. ex. A = B

subset

A set A is a ______ of another set B if and only if every element of A is also an element of B. Denoted A ⊆ B.

proper subset

If A ⊆ B and A ≠ B, then A is a _______ _______ of B. Denoted A⊂B.

1) A set S is a subset of itself.

2) ∅ is a subset of every set.

What are the two important properties of subsets?

the total number of subsets of S

2*|S| denotes what?

superset

If A ⊆ B, B is called a __________ of A.

intersection

Let A and B be two sets. The _________ of A and B is the set of elements common to A and B. Denoted A∩B.

union

Let A and B be two sets. The ______ of A and B is the set of elements that belong to either A or B. Denoted A∪B.

commutativity

holds for union and intersection: states that you can switch positions of operands (A&B). Denoted A∩B=B∩A

associativity

holds for union and intersection: no matter the order of operations, the result will be the same. Denoted (A∩B)∩C=A∩(B∩C)

distributivity

Property that allows for the distribution of operations over addition or subtraction. Example: a(b + c) = ab + ac.

• holds for union and intersection

• C∩(A∪B) = (C∩A)∪(C∩B)

• C∪(A∩B) = (C∪A)∩(C∪B)

complement, set complement

Let A be a set. The ________ of A is the set of all elements in the universal set which DO NOT belong to A. Denoted A' or A with a line over it.

parentheses, complement, union & intersection

What is the priority order of an expression with parentheses, union and intersection, and complement?

• 0

• infinity

• any positive natural number

The cardinality of any set can be… (3 possibilities)

• A∪B with line over whole thing = ‾A∩B‾

• A∩B with line over whole thing = ‾A∪B‾

What are the two relationships De Morgan’s Law shows?

set difference (A-B)

Let A and B be two sets. What is the set of all elements of A that DO NOT belong to B? What is the denotation?

cartesian product (AxB)

Let A and B be two sets. What is the set of all ordered pairs of the format (a,b) that satisfies a belongs to A and b belongs to B? What is the denotation?

|A| x |B|

How do you find the cardinality of cartesian product?

(|AxB|) = ????

power set

Let A be a set. What is the set of all subsets of A?

proposition/statement

a declarative sentence that either true or false, but not both (no questions or undefined variables, fact, no opinions)

atomic proposition

propositions that cannot be expressed in terms of simpler propositions (ex. Fanchao likes pizza.)

compound proposition

propositions are formed from existing propositions using logical operations (ex. If Fanchao is good at computer science, then he is good at programming.)

negation, ‾p

Let p be a proposition. What is the statement “It is not the case that p.”? What is the denotation?

conjunction (and)

If all are T, output is T

If one or more is F, putput if F.

given two propositions p and q, the __________ of p and q, denoted by p∧q. What is the truth table rule for this?

disjunction,

If all are F, output is F.

If one or more is T, output is T.

given two propositions p and q, the __________ of p and q, denoted by p∨q. What is the truth table rule for this?

equivalence, p≡q

Let p and q be two propositions. p and q are _________ if they have the same truth table value in EVERY possible case. What is the denotation?

exclusive or, p pinwheel q

Let p and q be two propositions. What is called the proposition that is true when exactly one of p and q is true and is false otherwise. What is the denotation?

conditional

T F, F

Every other case is true

Let p and q be two propositions. The ___________ statement is the proposition “if p, then q”. What is the truth table rule for this?

compound conditional

In a conditional statement, p→q, if p and q are compound propositions, then p→q is a ___________ _________ statement.

converse (switch)

Given a conditional statements, p→q, the ___________ of this conditional statements is q→p.

inverse (negate)

Given a conditional statements, p→q, the inverse of this conditional statements is -p→-q.

contrapositive (switch and negate)

Given a conditional statements, p→q, the ___________ of this conditional statement is -q→-p.

biconditional

Let p and q be two propositions. The ______________ statement (p↔q) is the proposition “p if and only if q.” p↔q is true when p and q have the same truth value, and false otherwise.

tautology

a compound proposition that is always true (every case in the truth table is true)

contradiction

a compound proposition that is always false (every case in the truth table is false)

contingency

a compound proposition that is neither a tautology nor a contradiction (most propositions are these)

satisfiable

a compound proposition is __________ if there is an assignment of truth variable (i.e. inputs) that makes it true

(some cases and true and some are false OR all cases are true)

argument

a sequence of propositions (P1, P2,…,Pn, C.) The final proposition is called the conclusion. All the statements in this sentence except the conclusion are called premises.

(P1∧P2∧…∧Pn→C)

valid

An argument is _______ if and only if all the premises being true forces the conclusion to be true. In other words, it is impossible for all the premises to be true and the conclusion to be false.

sound

An argument is __________ if and only if it is valid and contains only true premises.

statement

quantifier + variable + predicate

variable

a symbol that represents a subject/object

quantifier

∀ called the universal quantifier, means “for all,” and ∃, called the existential qualifier, means “there exists at least one”

predicate

a symbol represents a description of a subject/object or relation between subjects/objects

1) Change ∀ to ∃, or change ∃ to ∀.

2) Negate the predicate.

How do you negate statements?

conjunction, disjunction

ex. ∀x [P(x)∧Q(x)] = [∀xPx]∧[∀xQx]

∀ can distribute over a _______, but not over a ____________.

disjunction, conjunction

ex. ∃x [P(x)∨Q(x)] = [∃xPx]∨[∃xQx]

∃ can distribute over a _________, but not over a ________.

domain of a variable

the set from which a variable takes values

ex. All students of MU like pizza. (______ is all students of MU.)

domain

Whenever a variable is used, its ______ must be clarified.