Discrete Math Exam 1

DeMorgan’s Laws

~(p/\q)= ~p \/ ~q and ~(p\/q)= ~p /\ ~q

Distributive law

p/\(q\/r)=(p/\q)\/(p/\r) and p\/(q/\r)=(p\/q)/\(p\/r)

Commutative laws

p/\q=q/\p and p\/q=q\/p

Associative laws

(p/\q)/\r=p/\(q/\r) and (p\/q)\/r=p\/(q\/r)

What is a statement

True or false, but not both

How do we write “but not”

/\~

How to make a truth table with p,q,r?

p: 4 T’s, 4 F’s. q: 2 T’s, 2 F’s, 2 T’s, 2 F’s. r: Alternate T F

How to know two things are logically equivalent?

They always have the same truth values

Tautology

A statement that is always true regardless of truth values for its variables

Contradiction

A statement that is always false regardless of truth values for its variables

How are if-then and or related?

p→q=~p\/q

Negation of a Conditional statement

~(p→q)=p/\~q (NOT another conditional statement)

Contrapositive of a conditional statement

p→q=~q→~p

Converse of a conditional statement

p→q becomes q→p

Inverse of a conditional statement

p→q becomes ~p→~q

What does only if mean?

if not q, then not p. Also = p→q

What is the biconditional of p and q?

p if and only if q, p<->q. sometimes if and only if = iff

What is a sufficient condition?

r is a sufficient condition for s = if r then s

What is a necessary condition?

if not r then not s

What does it mean for an argument form is valid?

All premises are true and conclusion is true

What is modus ponens

If p then q.

p

therefore q

(Valid)

Modus tollens

If p then q.

~q

therefore ~p

(Valid)

Generalization

p

therefor p\/q

and 

q

therefore p\/q

Specialization

p/\q

therefore p

and

p/\q

therefore q

Elimination

p\/q

~q

therefore p

and

p\/q

~p

therefore q

Transitivity

p→q

q→r

therefore p→r

Proof by division into cases

p\/q

p→r

q→r

therefore r

What is a sound argument

It is valid and ALL premises are true

Universal quantifier

Upside down A, “for every/each/any/all”

Universal statement

∀x ∈ D, Q(x)

Existential quantifier 

∃ “there exists”

Existential statement

∃x ∈ D such that Q(x)

What do these domains mean? R, N, Z, Q

Real numbers, natural numbers (positive integers), all integers, rational numbers

Universal conditional statements

∀x, if P(x) then Q(x)

Negation of universal statements

There exists x in the domain such that not p

Negation of existential statements

For all x, not P(x)

What is n choose r?

n!/r!(n-r)!

Sum of the first n integers

(n(n+1))/2

Sum of a geometric sequence

r^(n+1) -1/r-1