SETS BOOLEAN PROPOSITIONAL LOGIC GRAPHS ALGORITHMS FUNCTIONS

sequence of vertices & edges. v & e can Dijkstra's To find the shortest path between nodes in
Property-Law Set Theory Formula Boundedness A+1 = 1 & A.0 = 0 Rules of Inference Walk
be repeated. k-length = k edges (example) a weighted graph - Greedy Approach Every element in Set A , maps to one element in set B
Injective
A⋂B=B⋂A
Sum of products: Product of sums:
Modus Ponens
⇒
(p ∧ (p → q)) q,
Trail a walk, no e is repeated Stage
Shortest
Vertex Distance
Previous
Not Visited
(One-to-One) f(a) = f(b) ↔ a = b or
f(x,y,z) = x.y+x.z+y.z f(x,y,z) = (x+y).(x+z).(y+z) if p → q is True and p is True, then q is True from S
Vertex f(a) ≠ f(b) ↔ a ≠ b
Commutativity
((p → q) ∧ ¬q) ⇒ ¬p,
A∪B=B∪A Modus Tollens
if p → q is True and ¬q is True, then ¬p is True
Path a trail, no v & e can be repeated a 0 undefined Horizontal Line test Line intersects graph only once = injective
Hypothetical ((p → q) ∧ (q → r)) ⇒ (p → r), a closed trail, starts & ends at the same
A ⋂ (B⋂C) = (A⋂B) ⋂ C Cirquit b ∞ undefined Vertical Line test Not a function if intersects more than once
Syllogism if p → q is True and q → r is True, then p → r is True vertex
((p ∨ q) ∧ ¬p) ⇒ q,
Associativity
Disjunctive initialization a,b,c,d
A ∪ (B∪C) = (A∪B) ∪ C Cycle a closed path, vertex reachable from self c ∞ undefined Every element in Set B , has at least one preimage in set A
Syllogism if (p ∨ q) is True and ¬p is True, then q is True
Surjective
K-Maps ≠ T.T. only for 2,3,4,5 variables From T.T. use only
Distributivity A ⋂ (B∪C) = (A⋂B) ∪ (A⋂C) lines that f= true. If input=1 use uncomplemented, if input = 0 Addition p ⇒ (p ∨ q), if p is True, then (p ∨ q) is True Eulerian Path
a walk, traverses each edge only once
(traversable)
d ∞ undefined
(Onto) f(x) = y, solve for xprove for ∀y in the Co-Domain,
∃x in the Domain (Range = Co-Domain)
use complemented. Cell = binary value, number of cells = 2^k
((p) ∧ (q)) ⇒ (p ∧ q), Eulerian path, starts & ends in same
A⋂A=A Conjunction
if p is True and q is True, then (p ∧ q) is True
Eulerian Cycle
vertex
a 0 undefined From Graph: x axis = Domain, y axis = Range
Idempotent
A∪A=A Simplification (p ∧ q) ⇒ p, if (p ∧ q) is True, then p is True Hamiltonian Path
a path, visits each vertex only once
(traceable)
b x a Inverse Function
If function = bijective, then inverse:
Set f(x) = y, Swap x and y, solve for y. Swap x and y again
((p ∨ q) ∧ (¬p ∨ r)) ⇒ (q ∨ r),
Let f (x) = 2x & g (x) = x+3:
1 b,c,d
Hamiltonian a Hamiltonian path, starts & ends in Composite
A∪Ø=A Resolution if (p ∨ q) is True and (¬p ∨ r) is True, then (q ∨ r) is
Cycle same vertex
c x a
Functions (f∘g) (x) = f (g (x) ) = f (x+3) = 2 (x+3) = 2x+6
Identity True
(g∘f) (x) = g (f (x) ) = g (2x) = 2x+3
G →G*: Check which paths do not have
A⋂U=A Logical Implication: A → B ≡ ~A ∨ B Transitive closure
a directed edge and add it
d ∞ undefined Logarithms y = a^x ↔ log base a of y = x
Equivalences Biconditional: A ↔ B ≡ (A → B) ∧ (B → A)
A ∩ (A ∪ B) = A Vertex Degree Number of incident edges a 0 undefined RELATIONS

Absorption aRa, ∀a∈S

HALF ADDER: used for Degree Monotonic non-increasing sequence of
A ∪ (A ∩ B) = A 2 bit addition
A,B: sum (XOR) + carry out (AND) PREDICATE LOGIC
Sequence vertices degrees
b x a Reflexive digraph: always loop on every element
matrix: leading diagonal contains only 1s
2 c,d ∀a,b∈S, if aRb then bRa
FULL ADDER: for more A, B, carry-in: sum + carry out Always EVEN,
A⋂Ø=Ø than 2 bits (bits + carry bit) (2 half adders + OR)
Quantifiers Symbol Sum of D.S
twice the number of edges
c x a Symmetric digraph: no single connection (either no connection or parallel edges)
matrix: symmetric in respect to leading diagonal
Domination
∀a,b∈S, if aRb & bRa then a=b
∀ : "For all" - ∀x P(x) = P(x) is true for all x in the
A∪U=A INDUCTION & RECURSION Universal Quantifier
domain.
Number of Edges Sum of D.S. / 2 d x b Antisymmetric digraph: no parallel edges
matrix: if i≠j & mij≠0 then mij = 0
Assume P(n) = True For a collection of No loops, no parallel edges - n vertices =
A–A=Ø Induction then show that P(n+1) = True sets
∀x P(x) = P(n₁) ∨ P(n₂) ∨ ... Simple Graph
n-1 degree
3 ... ... ... Transitive ∀a,b,c∈S, if aRb & bRc then aRc
Existential Ǝ: "There exists." ∃x P(x) = there is at least one x for All vertices = same degrees, Algorithm continues until all nodes are visited and
Set Difference A - B = A ⋂ B' 1. Basis Step Test+Show that for n=1, P(1) = True
Quantifier which P(x) is true.
Regular Graph
r regular = r degree. D.S.: G = r * n shortest path has been found.
Equivalance Reflexive + Symmetric + Transitive
For a collection of Simple graph, every 2 vertices are
A - B = (A ∪ B) ⋂ B' 2. Induction Hypothesis Assume n=k and so P(n) = P(k)
sets
∃x P(x) = P(n₁) ∧ P(n₂) ∧ ... Complete Graph
connected. D.S.: G = n (n-1)
TREES Partial Order Reflexive + Antisymmetric + Transitive
Unique Existential If there exists Bijection that preserves Undirected graphs, no cycles, all vertices
Symmetric A ⊕ B = (A ∪ B) - (A ∩ B) 3. Induction Step Show that P(k+1) is Also True
Quantifier
Ǝ!: there exists a unique ...
adjacency
Trees
are conected
Total Order Partial Order + ∀a,b∈S, aRb or bRa
Difference
A Δ B = (A-B) U (B- A) 4. Conclusion P is True for all n, n+1 Rules of Inference Isomorphic Every element of G1 maps to 1 element in G2 Forest Disconnected graph with no cycles COMBINATORICS
Graphs 1 vertex has been designated as the root
Double Assume P(n) = True Universal Independent events: n x m possible ways
complement (A’)’ = A Strong Induction
then show that P(n+1) = True Instantiation
If ∀x P(x) is true, then P(c) is true for any constant c. G1 & G2 = SAME D.S. Rooted tree & every vertex arranged hierarchically - Product Rule
For Sets: |A x B| = |A| x |B|
parent/child relation
Vertices can be divided in 2 disjoint sets Connected subgraph of main graph,
Empty & Universal Existential If P(c) is true for some constant c, then ∃x P(x) is Mutually Exclusive events: n + m possible ways
Set Compliments Ø’ = ∪ & ∪’ = Ø 1. Basis Step Test+Show that for n=1, P(1) = True
Generalization true.
such that all edges have 1 endpoint in each Spanning tree contains all vertices of original graph but Addition Rule
For Sets: |A ∪ B| = |A| + |B| as long as A,B are disjoint
set without the cycles
Bipartite Graphs
Subtraction Rule
Assume P(i) = True ∀ positive Universal Modus If ∀x (A(x) → B(x)) is true and A(c) is true, then B(c) To count the total number of distinct elements and avoid double
A ∪ A’ = U 2. Induction Hypothesis
integers i from 1 to k Ponens is true.
Created sets have the same D.S. (Inclusion Exclusion
Principle) counting or overlapping |A ∪ B| = |A| + |B| - |A ∩ B|
If k positive integer & k+1 objects are placed inside k containers, then at
Complement Law Existential Modus If ∃x (A(x) ∧ B(x)) is true, then B(c) is true for some Traversal algorithm, explores a graph by least 1 container has 2 or more objects
A ⋂ A’ = Ø 3. Induction Step Show that P(k+1) is also true
Ponens constant c. visiting its vertices layer by layer.
ALGORITHMS Pigeonhole Principle
If N objexts are placed in k boxes, at least one box contains ⌈N/k⌉objects
Breadth First
(ceiling)
Search
Starts from a specified source vertex and
Permutations Ordered arrangement of distinct elements in a set
A’ = U – A 4. Conclusion P is True for all n, n+1 ¬(∀x P(x)) ≡ ∃x ¬P(x) moves outward to its neighbors before visiting
De Morgan's their neighbors.
(Order Is Important) r-permutations = arrangement of r objects
Laws for P(n,r) = (n!) / (n-r)!
Function calls itself, breaking a Quantifiers: Number of
(A ∪ B)’ = A’ ⋂ B’ Recursion
problem into smaller steps ¬(∃x P(x)) ≡ ∀x ¬P(x) Square matrix, leading diagonal = loops Permutations
(ex. How many ways to select 1st, 2nd & 3rd prize winner out of 50
De Morgan’s people: P(50,3) = 50x49x48 = ...
Binding Variables Undirected graph: number of edges = Combinations r-combination of elements in a set is an unordered arrangement of r
(A ⋂ B)’ = A’ ∪ B’ 1. Basis Clause Specify some initial elements
in quantifiers ex. ∃x P(x,y) = x: bound, y:free half the sum of all elements (Order Not Important) elements
Prim: Number of
Adjacency Starts with any Kruskal:
Establishes a systematic way to important only if different quantifiers: Matrix Combinations
Carninality of set Number of distinct Order of node in a weighted Starts with the cheapest edge in a
2. Recursive Clause generate new elements from known Directed graph: the squared
(||) elements in a set elements
Precedence ∀ and ∃ , ¬ , ∨ , ∧ , → , ↔ matrix = number of paths of
spanning tree
Continues adding
weighted spanning tree
Continues adding cheapest edges (Binomial
cheapest edges Coefficient)
length 2 between 2 vertices
P(S): powerset of a set S
Guarantees that the only way to obtain Tautology: A compound proposition that is true for all possible truth Repeatedly split ascending order lists in
the set of all possible subsets, including the empty set (∅) 3. Terminal Clause Divide & Conquer half until search returns the required record Binomials:
and S itself
the elements of S is clauses 1 + 2 value assignments to its constituent propositions.
Each term in a sequence is a linear
2 terms connected
Add each corresponding elements (only
Number of edges from root to that node with + or -
Cardinality of Powerset:
P(S) = 2^n (n = number of elements in the set)
Linear Recurrence function of earlier terms (ex. Fibonacci Propositional Statements (P → Q ) Matrix - Addition
same size matrices)
Depth of node
Sequence)

Inverse: Contradiction: Matrix - Only if number of rows in M1 = number of

Addition principle |A∪B| = |A| + |B| Homogenous:
Multiplication columns in M2
Height of node Longest path from that node to a leaf Binomial Theorem
¬P → ¬Q ¬(P → Q) or P ∧ ¬Q
Inclusion |A∪B| = |A| + |B| − |A ∩ B| or
Converse: Contrapositive: Depth/Height of Maximum path length across all
Exclusion |A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ Non-Homogenous: Pascal's Identity
B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C| Q→P ¬Q → ¬P tree nodes
Principle
Arithmetic Sequence: Number Triangle, numbers arranged in staggered rows such that every element
Common Sets Rooted tree, every node has children ≤ m Pascal's Triangle is the sum of the 2 elements directly above it.
The difference between 2 Truth Tables Number of lines of n variables = 2^n Repetition Order Matters
Z = set of integers = {...,−2,−1,0,1,2,...} terms is a constant d
Regular: Every node has exactly m children
M-ary trees Permitted YES | NO
T.T of Implication
N = set of natural numbers = {1,2,3,...} Sum of the first n terms (P→Q: At most, m^h vertices at level h
if p then q,
p implies q,
YES
Geometric Sequence:
p only if q, Always same D.S. & bijection that k distinguishable objects in n k indistinguishable objects in n
W = set of whole numbers = {0,1,2,3,...} The difference between 2 q whenever p, Isomorphic trees preserves adjacency - Same D.S. not distinguishable boxes, distinguishable boxes,
terms is a ratio r q follows from p ) always isomorphic trees without exclusion without exclusion

T.T of Left Subtree: Values in the nodes ≤

Q = set of rational numbers = {...,-3/2, 1/4, 7/5,...} Biconditional Binary Search the value of the node itself.
(denominator ≠0) (P↔Q: Tree Right Subtree: Values in the nodes ≥
Sum of the first n terms
p if and only if q, the value of the node itself. NO
p is equivelent to q,
p is a necessary and Short values in ascending order and find k distinguishable objects in n k indistinguishable objects in n
R = set of real numbers (ALL numbers) sufficient condition Weighted Graphs Each edge is assigned a numerical value Building a B.S.T the root ( r = floor [(min + max) / 2] ) distinguishable boxes, distinguishable boxes,
for q) Repeat to complete the left & right subtrees with exclusion with exclusion