Transcript CS 490

CS 490
Mathematical Logic, Combinatorics,
Counting Arguments, Graph Theory,
Number Theory, Discrete Probability,
Recurrence Relation.
Thao Tran.
Mathematical Logic

Proposition and Logical Operators:

Proposition:



A proposition is a sentence to which one and only one of the terms true o false can
be meaningful applied.
Example: “four is even,” “43 >= 21”
Logical Operators:

Conjunction (And): If p and q are propositions, their conjunction, p and q (denoted p
^ q), is defined by:
p
0
0
1
1

q
0
1
0
1
p^q
0
0
0
1
Disjunction (Or): If p and q are propositions, their disjunction, p and q (denoted p v
q), is defined by:
p q pvq
0
0
1
1
0
1
0
1
0
1
1
1
Mathematical Logic (cont.)

Negation:

if p is a proposition, its negation, not p, is denoted ~p and is
defined by
p
0
1

~p
1
0
Conditional Operator( if…then):


The conditional statement if p then q, denoted
p --> q , is defined by
p
q
pq
0
0
1
0
1
1
1
0
0
1
1
1
Example:

If I pass the final, then I’ll graduate.
Mathematical Logic( cont.)

Truth table:
Mathematical Logic (cont.)

Tautology, Contradiction and Equivalent:

Tautology: An expression involving logical variables that is true
in all cases of its truth table.


Contradiction: An expression involving logical variable that is
false in all cases of its truth table.


Example: p v ~p
Example: p ^ ~p
Equivalent: Let S be a set of propositions and let r and s be
propositions generated by S. r and s are equivalent if r <--> s is
a tautology, denoted rs.

Example: p v q  q v p
Counting Principles


It is frequently necessary to count how
many ways certain choices can be made.
Basic methods:



Sum and product rules
Counting functions and sequences
Binomial theorem
Sum and Product Rules

Rule of sum:


The number of ways in which either of two mutually
exclusive events can occur is equal to the sum of the
number of ways in which each can occur separately.
Rule of product:

The number of ways in which two independent events
E1 and E2 can occur is the product of the numbers of
ways in which E1 and E2 can occur separately.
Sum and Product (cont.)

Example:

Suppose that a system of car registrartion is
adopted in which and allowable registration plate
consists of 1,2, or 3 letters, followed by a number
(not starting with 0) having the same number of
digits as there are letters. How many possible
registration are there?
Sum and Product (cont.)

Solution:

(26 x 9) + (26 x 26 x 9 x 10) + (26 x 26 x 26
x 9 x 10 x 10) = 15879474
Binomial Theorems

Binomial Theorem


(x+y)n = ∑nr=0( nr) xryn-r
Where :
( nr) =n!/(n-r)!r!
Power Set

Definition:


If A is any set, the power set of A is the set of
all subsets of A, including the empty set and A
itself. It is denoted P(A).
Example:
If A = {1, 2} then
 P(A) = { φ, {1}, {2}, {1,2}}


Formula:

P(A) = 2#A
Number Theory

The natural numbers:


N = {0, 1, 2, 3, …}
The integers:

Z = {…, -2, -1, 0, 1, 2, …}


The rational numbers:


Denoted Q (quotient), comprises all those numbers that can be written
in the form a/b, with a,b in Z
The real numbers:



Z stands for Zahlen, meaning “numbers” in Geman
Denoted R:
Example: √2, π
The complex numbers:


The set C of complex numbers is the set of all numbers of the form
a+bi where a and b are real numbers and i2 = -1
The reason for extending from R to C is to be able to solve all
polynomial equation
Recurrence Relations

Definition:


Let S be a sequence of numbers. A recurrence
relation on S is a formula that relates all but a finite
number of terms of S to previous terms of S. That is,
there is a k0 in the domain of S such that if k > k0,
then S(k) is expressed in terms that preceed S(k). If
the domain of S is {0, 1, 2…}, the terms S(0),
S(1),…,S(k0) are not defined by the recurrence
formula. Their values are the initial conditions (or
boundary conditions, or basis) that complete the
definition of S.
Example:

The Fibonacci sequence:


Fk = Fk-2 + Fk-1 , k >= 2 , F0=1, F1= 1
This recurrence relation is called a second-order relation
because Fk depends on the two previous terms of F.
Recurrence Relations (cont.)

Solving a recurrence relation:


Sequence are often most easily defined with a
recurrence relation; however, the calculation
of terms by directly applying a recurrence
relation can be time consuming.
Example:

Find recurrence relation for the sequence defined
by:

D(k) = 5*2k , k>=0
Recurrence Relations (cont.)

Answer:
D(k) = 5*2k = 2*5*2k-1 = 2D(k-1)
The relation is:
D(k) – 2D(k-1) = 0
Initial condition D(0) = 5.

Homogeneous recurrent relation:

An nth order linear relation is a homogeneous recurrence
relation if f(k) = 0 for all k. For each recurrence relation


S(k) + C1S(k-1)+…+CnS(k-n)=f(k)
The associated homogeneous relation is

S(k)+C1S(k-1)+ … + CnS(k-n)=0
Graph Theory

Directed Graph:



Consist of a set of vertices, V, and a set of edges, E, connecting
certain elements of V. Each element of E is an order pair. The
first entry is the initial vertex of the edge and the second entry
is the terminal vertex.
Example:
Simple Graph & Multigraph:

Simple graph is one for which there is no more than one edge
directed from any one vertex to any other vertex. All other
graphs are called multigraph.
Graph Theory(cont.)

Traversals:

Eulerian Graph:

Konigsberg Bridge Problem:
Graph Theory (cont.)

Answer:

A Eulerian path through a graph is a path whose
edge list contains each edge of the graph exactly
once.
Graph Theory (cont.)

Hamiltonian Graph:


A hamiltonian path through
a graph is a path whose
vertex list contains each
vertex of the graph exactly
once.A hamiltonian graph
is a graph that possesses a
Hamiltonian path.
Traveling salesman problem
:

A salesman who wants to
minimize the number of
miles the he travels in
visiting his custommers.
Discrete Probability


The calculation of discrete probability usually involves
counting arguments
Permutation:


Prn , is called the number of permutations of n objects taken r at
a time.
Prn = n(n-1)…(n-r+1)
= n! / (n-r)!

Combination:



Define for an r-element subset of an n-element set A is a
combination of A, taken r at a time.
Cnr = n! / r!(n-r)!
Example: Compute the number of distinct 5 card hands which
can be dealt from a deck of 52 cards.
Discrete Probability (cont.)

Answer:


C552 = 52!/(5! 47!) = 2,598,960
The pigeonhole principle:

If n pigeons are assigned to m pigeonholes,
and m < n, then at least one pigeonhole
contains two or more pigeons. More generally,
if n>km, then at least one pigeonhole must
contain more than k pogeons.
References



Truss, J.K. Discrete Mathematics for Computer
Scientist. Addison-Wesley Publishing
Company,
1991.
Kolman, Bernard and Robert. Discrete
Mathematical Structures for
Computer
Science. Drexel University.
Doerr, Alan and Kenneth. Applied
Discrete Structures for Computer
Science. Science Research Associates, Inc. 1985.