Chap 7: Counting (Part 2)

Combining Principle:

DEFINITION

•       Using both multiplication and addition principle in solving a complicated counting problems.

•       Mostly used to solved problem in programming.

Example 1

•       The name of a variable is a string of one or two alphanumeric characters, where uppercase and lowercase letters are not distinguished. (An alphanumeric character is either one of the 26 English letters or one of the 10 digits.) Moreover, a variable name must begin with a letter and must be different from the five strings of two characters that are reserved for programming use. How many different variable names are there in this version of BASIC?

•       Solution: Let V equal the number of different variable names in this version of BASIC. Let V1 be the number of these that are one character long and V2 be the number of these that are two characters long. Then by the sum rule, V = V1 + V2. Note that V1 = 26, because a one-character variable name must be a letter. Furthermore, by the product rule there are 26 · 36 strings of length two that begin with a letter and end with an alphanumeric character. However, five of these are excluded, so V2 = 26 · 36 − 5 = 931. Hence, there are V = V1 + V2 = 26 + 931 = 957 different names for variables in this version of BASIC.

Chap 7: Counting (Part 1)

Multiplication Principle (Product Rule):

DEFINITION

If each of m and n is a positive integer, a is an m-element set, and b is an n-element set, then |a × b| = m.n
or restated, |a × b| = |a||b|.

Example 1:

A person wants to go from station A to station C via station B. There are three routes from A to B and four routes from B to C. In how many ways can he travel from A to C?

           Solution: 

                               A –> B in 3 ways

              B –> C in 4 ways

              => A –> C in 3 × 4 = 12 ways

Chapter 6: Graphs and Trees (Part 2)

Euler Path:

}   Let G be a graph, and let a and b be two distinct vertices of G. An Euler Path from a to b is a sequence of adjacent edges and vertices that starts at a, ends at b, passes through every vertex of G at least once, and traverses every edge of G exactly once.

}   Let G be a graph, and let a and b be two distinct vertices of G. There is an Euler path if and only if G is connected, a and b have odd degree, and all other vertices of G have positive even degree.

Fleury Algorithm:

Fleury's algorithm works by simply constructing a path, starting at an arbitrary vertex (or at an odd one if there are any) and picking any of its incident edges, with a single caveat: any edge is permissible but those that leave the remaining graph disconnected. (For a connected graph, an edge whose removal affects the connectivity of the graph is called a bridge.)

Practice: http://www.cut-the-knot.org/Curriculum/Combinatorics/FleuryAlgorithm.shtml

Chap 3: Mathematical Induction (II)

STRONG MATHEMATICAL INDUCTION:

Almost similar to ordinary mathematical induction, however in strong mathematical induction, the basis step may contain proofs for several initial values, and in inductive step the truth of the predicate P(n) is assumed and not just for one value of n but for all from a through k and then the truth of P(k+1) is proved.

Principle of Strong Mathematical Induction:

Let P(n) be a property that is defined for integer n, and let a and b be fixed integer with a≤b.

Suppose the following 2 statements are true:

①    P(a), P(a+1), … and P(b) are all tue (BASIS)

②    For any integer k≥b, if P(i) is true for all int I from a through k, then P(k+1) is true. (INDUCTIVE STEP)

Then, the statement “for all integer n≥a, P(n) is true.”

(The supposition that P(i) is true for all integer i from a through k is called the inductive hypothesis.)

(Another way to state the inductive hypothesis is to say that P(a), P(a+1),…, P(k) are all true)

Note: Any statement that can be proved by ordinary mathematical induction can be proved by strong induction too.

Chap 3: Mathematical Induction (I)

PRINCIPLE OF MATHEMATICAL INDUCTION:

To prove that P(n) is true for all positive integers n, where P(n) is a propositional function by 2 steps:

Basis      : We verify that P(1) is true @ show that an initial value is true for all Z⁺ of the propositional function.

Inductive  : We show that the conditional statement∀k (P(k) → P(k+1)) is true for all Z⁺ of k.

Similarly, we can say that mathematical induction is a method for proving a property defined that the property for integer n is true for all values of n that are greater than or equal to some initial interger.

                   P(1)^∀k(P(k) → P(k+1))) → ∀nP(n)

METHOD OF PROOF:

The proofs of the basis and inductive steps shown in the example illustrate 2 different ways to show an equation is true

p Transforming LHS and RHS independently until they seem to be equal.

p Transforming one side of equation until it is seen to be the same as the other side of the equation.

Chapter 3: Sequences and Mathematical Induction (I)

Presentation week. All notes are available in slides. You can download this slide at this link:
Chapter 3: Sequences and Mathematical Induction (I)

Chap 2: Set Theory (Part 6)

FUNCTIONS:

• A function f from a set X to a set Y is a relation from X to Y such that x Î X is related to one and only one y Î Y
• X is called the domain & Y is called the range. We say x is mapped into y.
• f = {(a, 3), (b, 3), (c, 5), (d, 1)}
• Functions are described as:
• Set of ordered pairs, example f as given before
• Using a formula such as f(x) = expression, example : f (x) = 2x + 2
• Illustration as in the example below

Chap 2: Set Theory (Part 5)

Relation between 2 sets:

™ A relation between two sets A and B is a subset of the Cartesian product AxB; A is called the source set and B is called the target set.

™ Often, we use notation aRb to denote that (a.b)єR and a~Rb to denote that (a,b)∉  ..

EXAMPLE:

Let U={0,1,2,3,4,5,6} represent set with bit strings

a) A= {2,4,5,6}

      bit string is 0010111

 b) B is the set of all odd integer, B Í U.

      B= {1,3,5} the bit string is 0101010

 c) C is a subset of U, containing all integers greater than 4.

      C={5,6} the bit string is 0000011

Chap 2: Set Theory (Part 4)

COMPUTER REPRESENTATION OF SETS:
 There are many ways to represent sets using a computer.
 One of the method is to store elements using an arbitrary ordering of elements of the universal set.
◦ Ordered set (less time-consuming)
◦ Unordered set (time consuming)
 An arbitrary ordering of the elements of U (universal set), for instance, a1, a2, …, an, then representing a subset of A of U with bit string of length n, where the ith bit in this string is 1 if a1 belongs to A and is 0 if a does not belong to A.

EXAMPLE:
Let U={0,1,2,3,4,5,6} represent set with bit strings (binary form)
a) A= {2,4,5,6}
      bit string is 0010111
 b) B is the set of all odd integer, BÍ U.
      B= {1,3,5} the bit string is 0101010
 c) C is a subset of U, containing all integers greater than 4.
      C={5,6} the bit string is 0000011

Chap 2: Concept of Sets (Part 3)

 SET OPERATIONS:

DEFINITION : UNION OF SETS

Let A and B be sets. The union of the sets A and B, denoted by

A υ B, is the set that contains those elements that are either in A

or in B, or in both.

A υ B = {x | (x Є A)v (x Є B)}

Chap 2: Concept of Sets (Part 2)

 SET OF NUMBERS:

Chap 2: Concept of Sets (Part 1)

DEFINITIONS:

①    A set is an unordered collection of objects, known as elements or members of the set.

②    Sets are usually denoted as capital letters; its elements are denoted as lowercase letters.

③    Often, but not always the object in a set have similar properties.

Eg. S = {a, b, c, d, …} (sets of all English alphabets)

       S= {a, 1, ali, law} (random sets)

1.4 Nested Quantifiers

DEFINITIONS:

It is existed where by one quantifier is within the scope of another.

Example: ∀x∃y(x+y=0) can be translated as

              ∀x Q(x) where Q(x) is ∃y P(x,y) and P(x,y) is x+y=0

Solving Stated Involving Nested Quantifers

Assume that the domain x,y є R, then

①     ∀x∀y(x+y=y+x) shows that x+y=y+x for all real number of x and y (commutative law)

②     ∀x∀y(x+y=0) shows that for all real number of x, there is a real number y such that x+y=0 (additive inverse)

③     ∀x∀y∀z(x+(y+z)=(x+y)+z) shows associative law for addition of real numbers.

To prove that ∀x∀y P(x,y) is true, we loop through the values for x, and for each x, we loop through the values through y; if it’s true if all values of x,y is true.

1.3 Predicates and Quantifiers

DEFINITIONS:

①     Predicates is a logical operator that returns a Boolean value that is either true or false.

We also use predicates in programming.

Consider the statement “x is absent in the class today.”

Ø  Since x is an unknown, this statement is not a propositional statement.

However, we do know that when we assign a value (object) into x, the whole statement will make sense as it explains how a subject (x) is being affected.

Hence, we can say that x is a subject which can take any value into the statement to turn the whole statement into a propositional statement and it can hold a set of truth values.

Likewise, “is absent in the class today” represents what does the property that x holds.

Ø  Hence, “is absent in the class today” is known as the predicate for x (subject).

Ø  The predicate and subject, if combined together, can be written as P(x) where P is the predicate and x is the subject of the statement. It is also known as the propositional function.

In general, a statement of the form P(X_1, X_2, X_{3, …,} X_n) is the value of proposition function P at n-tuple (X_1, X_2, X_{3, …,} X_n) and P is known as n-place predicate or n-ary predicate.

1.2 Propositional Equivalences

DEFINITION:

A compound proposition that is always true, no matters what the truth values of the propositional variable that occur in it, is called TAUTOLOGY. A compound proposition that is always false is CONTRADICTION neither is called CONTINGENCY.

LOGICAL EQUIVALENCES

Compound propositions that have the same truth values in all possible cases are called logically equivalences .

                                                     @

The compound propositions p and q are called logically equivalence if p↔q is a tautology. The notation p≡q denotes that p and q are logically equivalent.

REMARK : The sym ≡is not a logical connective and p ≡ q is not a compound proposition but rather is the statement that p↔q is a tautology. The symbol ó is used instead of ≡ to denote logical equivalent.

1.1 Proposition Logic

Chap 1: The Foundations- Logics and Proofs

1.1 Proposition Logic

DEFINITIONS:

①     Propositional is a declarative sentence that is either true or false, but not both. It normally uses lower case roman letters (p, q, r,…) to denote its propositional variables (statement variables), denoted by T when the statement is true and F for false statement.

②     Logic means the study of either of proposition logic or first-order predicate logic.

p/s: Logic encompasses the following attributes:

l   Syntax         : Define the syntactically acceptable object of language. Also

known as formulae

l  Semantics    : Formulae of logic associate each formula with a meaning.

l  Proof-theory : Manipulating formulae according to the perceived reasoning.

③     Atomic proposition is a truth or falsity that does not depend on the truth or falsity of any other proposition.

Discrete Mathematic- An Preview

"As far as the laws of mathematics refer to reality, they are not certain; and as far as they are certain, they do not refer to reality."

Albert Einstein (1879 - 1955), "Geometry and Experience", January 27, 1921

     Discrete mathematics is the study structural mathematics fundamentally focusing in the study of objects which are finite and infinite. Therefore, study of continuous mathematics such as “calculus” and “algebra” are different from the study of discrete mathematics. Often in time, the structures behind a mathematical theorem and logics will be elaborated in this course, and students are required to define or even construct a new theorem based on the learned topics. Thus, mathematical reasoning is prioritized so as to read, understand, and define mathematical arguments and statements using methods of proof. These concepts are often useful in studying and solving problems related to computer science and logic, such as automata theory, cryptography, software testing, software development and programming languages using proposed algorithms based on the proven theories.

Introduction of VocaloidEx Members

VocaloidEx Members:
Hello and welcome everyone to our simple blog website. As of today we would like to give all of our gratitude to all of our visitors by introducing our crew of this website....From time to time, we as the editors will try our best to upload our notes on Discrete Mathematics. We hope that you'll enjoy it very much...thank you~