Discrete Cheatsheet - cheat sheet PDF

Preview

Summary

cheat sheet...

Description

Order Matters Order Does Not Matter

No Repetition

P(n,k)=

n! ( n− k ) !

Repetition

n

k

(nk ) k (n−1+ k )

K= balls N=bins Complete Bayes Theorem:

Pr( E|H ) Pr ( H ) ( ) ( | Pr E H Pr H ) + Pr ( E|not H ) Pr ( not H )

Pr(H|E)=

Simplified version: Pr [ E∨H ]· Pr [ H ] Pr [ E]

Pr[H|E] =

Conditional probability: Pr[E1|E2] =

Pr [ E 1∩ E 2] . Pr [ E 2]

¬ (p → q) 

P ∩¬ q

If Ben is teaching Discrete Structures next semester, then so are Ariel and Diogenes.

Negation: Ben is teaching Discrete Structures next semester and Ariel or Diogenes are not teaching it.

 

If Virgil runs only one s ection of 1802 then Jose or Alden must run two each.

Negation: . Virgil runs only one section of 1802 and Jose and Alden are not running two.

De Morgan’s Laws:

1. 2.

¬ (A ∩ B) = ¬ A U ¬ B ¬ (A U B)= ¬ A ∩ ¬ B

Pigeonhole principle: There are 5 pigeons There are 3 Holes Celling(5/3)-> at least 2 pigeons per hole.

CNF DNF

All clauses are connected by AND All clauses are connected by OR

No clause inside a clause (i.e ( () ) ) No clause inside a clause (i.e ( () ) )

No negation of a clause No negation of a clause

Inclusion exclusion: To find the multiples of a certain number floor division should be applied Multiples of 3 in 1000 -> floor(1000/3)= 333.

Two's complement:

In order to get a binary in two’s complement it should be flipped and then should be added one....