Show Menu
Cheatography
  1. Home >
  2. Cheat Sheets >

Discrete Exam 1 Cheat Sheet (DRAFT) by

This is a draft cheat sheet. It is a work in progress and is not finished yet.

Useful Symbols

∀
for all (universal operator)
∃
exists (exist­ential operator)
∈
in the set
∧
and
∨
or
∼
not
≡
equivalent
⊂
subset
⊃
superset
{}, ∅
empty set
↔
bicond­itional (both are true)

Statements

Universal
For all, for each
Existe­ntial
At least, there exists
Condit­ional
If → then
Universal Condit­ional
For all & if-then
Universal Existe­ntial
For all & there exists
Existe­ntial Universal
There exists & for all

List of Equiva­lences

Condit­ional Statemnts
p→q≡~(­p∧~q)
p→q≡~p∨q
contra­pos­itive
p→q≡~q→~p
Converse
p→q (cond)
q→p (converse)
inverse
p→q (cond)
~p→~p (inverse)
vacuously true = true by absence
converse and inverse are the SAME
  

Set-Bu­ilder Notation

Set-Roster Notation

A = {1, 2, 3 ... 100}
use ellipses for larger sets

Subsets

B⊆A
B=subset, A=superset
Proper Subsets: elements that belong to superset but NOT subset

Relations

Relations=
subsets of cartesian product
R ⊆ A x B
Relation ⊆ Domain x Codomain
Domain
SET that includes every element from source
don't always have to include ordered pairs

Functions

Requir­ements:
- Arrow coming out of every element in domain
- Every element can only have one element of domain connected to one element of codomain
unsati­sfied requir­ement = relation
y can be used repeatedly but x values only have one arrow coming out

Predicates and Quantified Statements

Statement type
original
negated
Universal
∀x∈D, P(x)
∃x∈D, ~P(x)
Existe­ntial
Universal Condit­ional
 

DeMorgan's Law

• Tells us how to handle conjun­ction and disjun­ction negations
~(p∧q) ≡ ~p∨~q
~(p∨q) ≡ ~p∧~q
"The connector is loose(l) or the machine is unplug­ged­(u)­"
l ∨ u -- negation --> ~(l ∨ u) ≡ ~l ∧~u
"The connector is not loose and the machine is not unplug­ged­"
~p∨q is the opposite of p∧~q
When using DeMorgan's law, no need for truth table

Tautol­ogies and Contra­dic­tions

Tautol­ogies
Always true statements
t
Contra­dic­tions
Always false statements
c
p∧~p≡c
T∧F≡c
F∧T≡F
p∨t≡t
p∧c≡c
Absorption law: variable absorbing operator
⇒use truth table to prove law
⇒other variables don't play a role in statement validity
p∨(p∧q)≡ p; p∧(p∨q)≡ p

p→q truth table

Argument Truth Table

Critical row = row where both premises are true
premises and conclusion = TRUE is a valid argument
  

Arguments

p→q
major premise
p
minor premise
∴q
therefore, conclusion
premises aka assump­tions or hypotheses
verified using truth table

Argument Forms (VALID)

Modus Pones
p→q
 
p
 
∴q
Modus Tollens
p→q
 
~q
 
∴~p
Gneral­ization
p
 
∴p∨q
Specia­liz­ation
p∧q
 
∴q
Elimin­ation
p∨q
 
~q
 
∴p
Transi­tivity
p→q
 
q→r
 
∴p→r
Proof by div. into cases
p∨q
 
p→r
 
q→r
 
∴r

Fallacy (INVALID ARGUMENTS)

Converse Error
p→q
 
q
⇒
∴p
Inverse Error
q→p
 
~p
 
∴~q