Task 6 : TREE


    • THE TASK:
  • 1. Give the definition and example for each of the following term:
    a) Euler Path
    b) Euler Circuit

    2. Determine what are the properties that differentiate between (a) and (b) in Question 1?

    3. What are the algorithm or step by step to determine (a) and (b) in Question 1?

    4. Give the definition and example for each of the following term:
    a) Hamilton Path
    b) Hamilton Circuit

    5. Determine what are the properties that differentiate between (a) and (b) in Question 4?

    6. What are the algorithm or step by step to determine (a) and (b) in Question 4?


    1. a)
    • EULAR PATH:
    • Eulerian path is a trail in a graph which visits every edge exactly once.





b)
    • EULAR CIRCUIT
      An Euler circuit is a circuit that uses every edge of a graph exactly once.
    • I An Euler circuit starts and ends at the same vertex.





2.
    • EULAR PATH:
    • Starting at initial vertex and ending at other vertex.
    • Some degree vertex are odd.
    • Odd degree vertex => 2.
    • EULAR CIRCUIT: 
    • Starting with initial vertex and ending at initial vertex.
    • All degree vertex are even.


3.
    • Euler Path :
      • Pick any vertex to start 
      • From that vertex pick an edge to traverse 
      • Darken that edge, as a reminder that you can't  traverse it again
      • Travel that edge, coming to the next vertex 
      • Repeat 2-4 until all edges have been traversed, and you are back at the starting vertex
    • Euler Circuit 
      • Step One: Randomly moves from node to node, until stuck.  Since all nodes had even degree, the circuit must have stopped at its starting point. (It is a circuit.)
      • Step Two: If any of the arcs have not been included in our circuit, find an arc that touches our partial circuit, and add in a new circuit.
      • Each time we add a new circuit, we have included more nodes.  
      • Since there are only a finite number of nodes, eventually the whole graph is included.
4.
    • Example:
    • Hamilton circuit:                                                        

                                           a-b-e-d-c-a





    • Hamilton Path 

    • is a  path visits each vertex of a graph once and only once.
      • Not all edges is passes through because the vertex is passes olny once.





5.
    • HAMILTON CIRCUIT:
      • When this initial vertex is connected to each vertex until it  meet the end at initial vertex
    • HAMILTON PATH:
      • The initial vertex is connected each vertex until it meet the last vertex before initial vertex
6.
    •                TO DETERMINE HAMILTON CIRCUIT
      • DIRAC’S THEOREM:  If G is a simple graph with n vertices with n ≥ 3 such that the
      • degree of every vertex in G is at least n/2, then G has a Hamilton circuit
      • ORE’S THEOREM : If G is a simple graph with n vertices with n ≥ 3 such that
      • deg(u) + deg(v) ≥ n for every pair of nonadjacent vertices u and v in G, then G has a Hamilton circuit.
    • Randomized algorithm
      • A randomized algorithm for Hamiltonian path that is fast on most graphs is the following: Start from a random vertex, and continue if there is a neighbor not visited. If there are no more unvisited neighbors, and the path formed isn't Hamiltonian, pick a neighbor uniformly at random, and rotate using that neighbor as a pivot. (That is, add an edge to that neighbor, and remove one of the existing edges from that neighbor so as not to form a loop.) Then, continue the algorithm at the new end of the path.





  • Digg
  • Del.icio.us
  • StumbleUpon
  • Reddit
  • RSS

5th task: mathematical Induction I & II


TAF3023:DISCRETE MATHEMATICS
Task : Mathematical Induction I & II

1) What do you show in the basis step and what do you show in the inductive step when 
you use (ordinary) mathematical induction to prove that a property involving an 
integer n is true for all integers greater than or equal to some initial integer?
- You may use example of problems to explain this answer.

2) What is the inductive hypothesis in a proof by (ordinary) mathematical induction?

3) Are you able to use (ordinary) mathematical induction to construct proofs involving 
various kinds of statements such as formulas, divisibility properties and inequalities?
- You may use example of problems to explain this answer. Give examples of 
question for each type of problems (formulas, divisibility properties and inequalities)
..............................................................................................................................................................

1.  For our formula example, our proposition P(n) is   . Substituting this definition of P into the outline , we get the following outline for our specific claim :


Proof : We will show that  for any positive integer n, using induction on n.
Base : We need to show that the formula for n = 1, i.e.  .
Induction : Suppose that  for n = 1, 2, …, k-1. We need to show that
 k.

By the definition of summation notation,


Our inductive hypothesis states that at n = k – 1, 


Combining these two formulas, we get that 

But
So, combining these equations, we get that k which
is what we needed to show.

One way to think of a proof by induction is that it’s a template for
building direct proofs. If I give you the specific value n = 47, you could
write a direct proof by starting with the base case and using the inductive
step 46 times to work your way from the n = 1 case up to the n = 47 case.



2. PROOFS FOR INEQUALITIES  IN MATHEMATHICAL INDUCTION PROBLEM
Let us denote the proposition in question by P (n), where n is a positive integer. The proof involves two steps:

Step 1: We first establish that the proposition P (n) is true for the lowest possible value of the positive integer n.

Step 2: We assume that P (k) is true and establish that P (k+1) is also true
Problem 1:

Use mathematical induction to prove that

1 + 2 + 3 + ... + n = n (n + 1) / 2

for all positive integers n.
Solution to Problem 1:
  • Let the statement P (n) be 

    1 + 2 + 3 + ... + n = n (n + 1) / 2 
  • STEP 1: We first show that p (1) is true.

    Left Side = 1

    Right Side = 1 (1 + 1) / 2 = 1 
  • Both sides of the statement are equal hence p (1) is true. 
  • STEP 2: We now assume that p (k) is true

    1 + 2 + 3 + ... + k = k (k + 1) / 2 
  • and show that p (k + 1) is true by adding k + 1 to both sides of the above statement

    1 + 2 + 3 + ... + k + (k + 1) = k (k + 1) / 2 + (k + 1)

    = (k + 1)(k / 2 + 1)

    = (k + 1)(k + 2) / 2 
  • The last statement may be written as

    1 + 2 + 3 + ... + k + (k + 1) = (k + 1)(k + 2) / 2 
  • Which is the statement p(k + 1).

Problem 2:

Prove that

1
 2 + 2 2 + 3 2 + ... + n 2 = n (n + 1) (2n + 1)/ 6

For all positive integers n.
Solution to Problem 2:
  • Statement P (n) is defined by 

    1
     2 + 2 2 + 3 2 + ... + n 2 = n (n + 1) (2n + 1)/ 2 
  • STEP 1: We first show that p (1) is true.

    Left Side = 1
     2 = 1

    Right Side = 1 (1 + 1) (2*1 + 1)/ 6 = 1 
  • Both sides of the statement are equal hence p (1) is true. 
  • STEP 2: We now assume that p (k) is true

    1
     2 + 2 2 + 3 2 + ... + k 2 = k (k + 1) (2k + 1)/ 6 
  • and show that p (k + 1) is true by adding (k + 1) 2 to both sides of the above statement

    1
     2 + 2 2 + 3 2 + ... + k 2 + (k + 1) 2 = k (k + 1) (2k + 1)/ 6 + (k + 1) 2 
  • Set common denominator and factor k + 1 on the right side

    = (k + 1) [ k (2k + 1)+ 6 (k + 1) ] /6 
  • Expand k (2k + 1)+ 6 (k + 1) 

    = (k + 1) [ 2k
     2 + 7k + 6 ] /6 
  • Now factor 2k 2 + 7k + 6.

    = (k + 1) [ (k + 2) (2k + 3) ] /6 
  • We have started from the statement P(k) and have shown that

    1
     2 + 2 2 + 3 2 + ... + k 2 + (k + 1) 2 = (k + 1) [ (k + 2) (2k + 3) ] /6 
  • Which is the statement P(k + 1).
 3)
Divisiblity properties
 eg: Use mathematical induction to prove that n3 − n is divisible by 3 whenever is a positive interger

BASIS STEP: The statement P(1) is true because 13 − 1 = 0 is divisible by 3. This completes
the basis step.
INDUCTIVE STEP: For the inductive hypothesis we assume that P(k) is true. we
assume that k3 − k is divisible by 3 

(k + 1)3 − (k + 1) is divisible by 3. 
(k + 1)3 − (k + 1) = (k3 + 3k2 + 3k + 1) (k + 1)
= (k3 − k) + 3(k2 + k).

Using the inductive hypothesis, we conclude that the first term k3 − k is divisible by 3. The
second term is divisible by 3 because it is 3 times an integer.

  • Digg
  • Del.icio.us
  • StumbleUpon
  • Reddit
  • RSS

4th Task


TAF3023: Discrete Mathematic Task 4: Sequences, Mathematical Induction and Recursion

4.1 Sequences
- Definition of sequence
- Example problem involving sequence.
-Types of sequence
-Give 1 example sequences use in computer programming

4.2 Mathematical Induction 1
-List down the principle of Mathematical Induction.
-Explain the method of Proof by mathematical Induction
-Give 2 example problems that use for solving mathematical induction.
_________________________________________________________________________________

4.1) SEQUENCES
A)Definition of sequences.
a)-Sequence is a function from a subset of the natural numbers(usually of the form {0, 1, 2, . . . } to a set S.  

-For an example:-
   A={0,1,2,3,4…….x} and  B={1,2,3,4……..x}
                  are called initial segments of N.
b)-Geometric progression is a sequence of the form
             a,ar,ar2,ar3………,arn,….
-Geometric progression is a discrete analogue of the exponential function f(x)=arn.
-Example:-
The sequence bn=(-1)n. We start with n=0. Initial term and common ratio equal to 1 and −1.The list of the term begins with b0,b1,b2,b3
1,−1, 1,−1, 1, . . . ;
c) -An arithmetic progression is a sequence of the form 
                             a, a + d, a  2d, . . . , a + nd, . . .
where the initial term a and the common difference d  are real numbers.

-An arithmetic progression is a discrete analogue of the linear function
 f (x) = dx + a.
 -Example:-
The sequence of sn=-1+4n.We start at n=0. Initial terms and common differences equal to −1 and 4. The list of terms s0, s1, s2, s3, . . . begins with
                                                −1, 3, 7, 11, . . . ,
d) -A recurrence relation for the sequence {an} is an equation that expresses an in terms of one or more of the previous terms of the sequence, namely, a0, a1, . . . , an−1, for all integers n with n ≥ n0, where n0 is a nonnegative integer. A sequence is called a solution of a recurrencerelation if its terms satisfy the recurrence relation.

- Let {an} be a sequence that satisfies the recurrence relation an = an−1 + 3 for n = 1, 2, 3, . . . , and suppose that a0 = 2. What are a1, a2, and a3?

- Example:-

Let {an} be a sequence that satisfies the recurrence relation an = an−1 + 3 for n = 1, 2, 3, . . . ,
and suppose that a0 = 2. What are a1, a2, and a3?

We see from the recurrence relation that a1 = a0 + 3 = 2 + 3 = 5. It then follows that 
a2 = 5 + 3 = 8 and  a3 = 8 + 3 = 11.

e) The Fibonacci sequence, f0, f1, f2, . . . , is defined by the initial conditions 
f0 = 0, f1 = 1,and the recurrence relation fn = fn−1 + fn−2 ,for n = 2, 3, 4, . . . .

-Example:-

Find the Fibonacci numbers f2, f3, f4, f5, and f6.
                        
The recurrence relation for the Fibonacci sequence tells us that we find successive erms by adding the previous two terms. Because the initial conditions tell us that f0 = 0 and f1 = 1, using the recurrence relation in the definition we find that             
      

4.1) SEQUENCES
A)Definition of sequences.
a)-Sequence is a function from a subset of the natural numbers(usually of the form {0, 1, 2, . . . } to a set S.  

-For an example:-
   A={0,1,2,3,4…….x} and  B={1,2,3,4……..x}
                  are called initial segments of N.

B)Types of sequences 
1)-Geometric progression is a sequence of the form

-Geometric progression is a discrete analogue of the exponential function f(x)=arn.
-Example:-
The sequence bn=(-1)n. We start with n=0. Initial term and common ratio equal to 1 and −1.The list of the term begins with b0,b1,b2,b3
1,−1, 1,−1, 1, . . . ;


2) -An arithmetic progression is a sequence of the form 

-An arithmetic progression is a discrete analogue of the linear function
 f (x) = dx + a.
 -Example:-
The sequence of sn=-1+4n.We start at n=0. Initial terms and common differences equal to −1 and 4. The list of terms s0, s1, s2, s3, . . . begins with
      −1, 3, 7, 11, . . . ,


3)The Fibonacci sequence, f0, f1, f2, . . . , is defined by the initial conditions 
f0 = 0, f1 = 1,and the recurrence relation fn = fn−1 + fn−2 ,for n = 2, 3, 4, . . . .

-Example:-

Find the Fibonacci numbers f2, f3, f4, f5, and f6.
                        
The recurrence relation for the Fibonacci sequence tells us that we find successive erms by adding the previous two terms. Because the initial conditions tell us that f0 = 0 and f1 = 1, using the recurrence relation in the definition we find that             

      
-A recurrence relation for the sequence {an} is an equation that expresses an in terms of one or more of the previous terms of the sequence, namely, a0, a1, . . . , an−1, for all integers n with n ≥ n0, where n0 is a nonnegative integer. A sequence is called a solution of a recurrencerelation if its terms satisfy the recurrence relation.

- Let {an} be a sequence that satisfies the recurrence relation an = an−1 + 3 for n = 1, 2, 3, . . . , and suppose that a0 = 2. What are a1, a2, and a3?

- Example:-

Let {an} be a sequence that satisfies the recurrence relation an = an−1 + 3 for n = 1, 2, 3, . . . ,
and suppose that a0 = 2. What are a1, a2, and a3?

We see from the recurrence relation that a1 = a0 + 3 = 2 + 3 = 5. It then follows that 
a2 = 5 + 3 = 8 and  a3 = 8 + 3 = 11.



C)Example sequences used in computer programming
Scanner k=new scanner(system.in);
int number;
number=k.nextInt();
while(number<=100){
if(number%2==0){
System.out.println(“even”);}
else{
System.out.println(“odd”);}
The statement above shows that when the modulus 2 of an input number is 0.The value has no remainder and is divisible by 2.In nutshell, it is an even number. On the other hand, when the modulus 2 of the number is 1.The number input is odd. Sequence is applied in a way that each number shows a pattern closely to sequence and it would be tiresome to calculate every single number to know if it’s odd or even. Sequence makes it easier to know the even and odd properties of a number with  a much more larger value by tracing out the pattern.


              EXAMPLE PROBLEM INVOLVING SEQUENCE

A sequence is a set of numbers such as 1, 2, 3, … or 96, 48, 24, … that follow some sort of formula. 
Example 1 :
Find five consecutive integers that sum up to 405.
Solution : 
Instead of implementing a guess and check method, suppose the five integers were x, x+1, x+2, x+3, and x+4 = 405. Their sum is 405, so we have
x + (x+1) + (x+2) + (x+3) + (x+4) = 405
5x + 10 = 405
x = 79
The five integers are 79, 80, 81, 82, and 83.

Example 2 : 
Find the sum of all the integers starting from 1 to 1000.
Solution :
The sequence of integers starting from 1 to 1000 is given by 
1, 2, 3, 4, …, 1000
The first term is 1 and the last term is 1000. The common difference is equal to 1. The formula that gives the sum of the first and terms of an arithmetic sequence knowing the first and last term of the sequence and the number of terms.
S1000 = 1000 (1 + 1000) / 2 = 500500




First Principle of Mathematical Induction.

Let P(n) be a predicate with domain of discourse (over) the natural numbers N = {0; 1; 2; …}. If 

          (1) P(0), and
          (2) P(n) → P(n + 1)

then 8nP(n).

Terminology: The hypothesis P(0) is called the basis step and the hypothesis,
P(n) → P(n + 1), is called the induction (or inductive) step.

The Principle of Mathematical Induction is an axiom of the system of natural
numbers that may be used to prove a quantified statement of the form 8nP(n), where
the universe of discourse is the set of natural numbers. The principle of induction has
a number of equivalent forms and is based on the last of the four Peano Axioms. The axiom of induction states that if S is a set of natural numbers such that (i) 0 ϵ S and (ii) if n ϵ S, then n + 1 ϵ S, then S = N. This is a fairly complicated statement: Not only is it an “if ..., then ..." statement, but its hypotheses also contains an “if ..., then ..." statement (if n ϵ S, then n + 1 ϵ S). When we apply the axiom to the truth set of a predicate P(n), we arrive at the first principle of mathematical induction stated above. More generally,
we may apply the principle of induction whenever the universe of discourse is a set of
integers of the form {k; k + 1; k + 2; …} where k is some fixed integer. In this case
it would be stated as follows:

Let P(n) be a predicate over {k; k + 1; k + 2; k + 3; …}, where k ϵ Z. If

(1) P(k), and
(2) P(n) → P(n + 1)

then 8nP(n).

In this context the “for all n", of course, means for all n ≥ k.

Why does the principle of induction work? This is essentially the domino effect.
Assume you have shown the premises. In other words you know P(0) is true and you
know that P(n) implies P(n + 1) for any integer n ≥ 0.

Since you know P(0) from the basis step and P(0) → P(1) from the inductive
step, we have P(1) (by modus ponens).
Since you now know P(1) and P(1) → P(2) from the inductive step, you have
P(2).
Since you now know P(2) and P(2) → P(3) from the inductive step, you have
P(3).
And so on ad infinitum (or ad nauseum).

The Second Principle of Mathematical Induction. 

Let k be an integer, and let P(n) be a predicate whose universe of discourse is the set of integers {k; k + 1; k + 2; …}. Suppose

1. P(k), and
2. P(j) for k ≤ j ≤ n implies P(n + 1).

Then 8nP(n).

The second principle of induction differs from the first only in the form of the
induction hypothesis. Here we assume not just P(n), but P(j) for all the integers j
between k and n (inclusive). We use this assumption to show P(n+1). This method
of induction is also called strong mathematical induction. It is used in computer
science in a variety of settings such as proving recursive formulas and estimating the
number of operations involved in so-called “divide-and-conquer" procedures.



examples of mathematical induction
1.  Version:1.0 StartHTML:0000000167 EndHTML:0000001580 StartFragment:0000000457 EndFragment:0000001564
Scanner k=new scanner(system.in);
int number;
number=k.nextInt();
while(number<=100){
if(number%2==0){
System.out.println(“even”);}
else{
System.out.println(“odd”);}

The statement above shows that when the modulus 2 of an input number is 0.The value has no remainder and is divisible by 2.In nutshell, it is an even number. On the other hand, when the modulus 2 of the number is 1.The number input is odd. Sequence is applied in a way that each number shows a pattern closely to sequence and it would be tiresome to calculate every single number to know if it’s odd or even. Sequence makes it easier to know the even and odd properties of a number with a much more larger value by tracing out the pattern.


2.  Express gcd(252, 198) = 18 as a linear combination of 252 and 198. Solution: To show that gcd(252, 198) = 18, the Euclidean algorithm uses these divisions:
252 = 1 · 198 + 54 198 = 3 · 54 + 36 54 = 1 · 36 + 18
36 = 2 · 18. Using the next-to-last division (the third division), we can express gcd(252, 198) = 18 as a
linear combination of 54 and 36. We find that 18 = 54 1 · 36. The second division tells us that 36 = 198 3 · 54.
Substituting this expression for 36 into the previous equation, we can express 18 as a linear combination of 54 and 198. We have
18 = 54 1 · 36 = 54 1 · (198 3 · 54) = 4 · 54 1 · 198. The first division tells us that 54 = 252 1 · 198.
Substituting this expression for 54 into the previous equation, we can express 18 as a linear combination of 252 and 198. We conclude that
18 = 4 · (252 1 · 198) 1 · 198 = 4 · 252 5 · 198, completing the solution.
We will use Theorem 6 to develop several useful results. One of our goals will be to prove the part of the fundamental theorem of arithmetic asserting that a positive integer has at most one prime factorization. We will show that if a positive integer has a factorization into primes, where the primes are written in nondecreasing order, then this factorization is unique.

slide show version:


  • Digg
  • Del.icio.us
  • StumbleUpon
  • Reddit
  • RSS

TASK 3

exciting math indeed. alot of reading and understandings accompanied with patience are required.
These are the assignment:


 TASK 3

 1. Explain how to represents sets using a computer. Give 1 example of representing sets by using computer and 1 example for representing each operation (union, intersection and complement), sets in computer respectively.
2. RELATION: a) Describe the concept of relations between 2 sets. b) Use the appropriate methods for representing relation(Reflexive, Symmetric, Antisymmetric and Transitive) c) Explain some of the properties of relations.
 3. FUNCTIONS
 a) Definition or concept of function on general sets.
 b) Explain the concept of Boolean Functions.
 c) Explain each types of function(Injective, Surjective and Bijective)
 d) Give the definition and examples of Inverse Function.
 e) Give the definition and examples of Composition Function

_________________________________________________________________________________

 1. Sets reprisented via computer

 There are two methods to represent sets using a computer :
 Unordered fashion
 a. Store the elements of the set in an unordered fashion: -Computing operation are union, intersection and differ entence of two set. -Each operation require large amount of searching elements.

Arbitrary ordering.
 b. Store the elements using an arbitrary ordering of the elements of the universal set.
Easy to make compute set.

1.  Let's assume that set U is a finite and of reasonable size.
2.  First, we'll specify an arbitrary ordering of elements of U, for instance a1, a2, a3, ..., an.
3. Then, we'll represent a subset A of U with the bit string of length n, where the i th bit in this string is:                                                       if ai ∈ A, and 0, if ai ∉ A.

A. Store the elements of the set in an unordered fashion: -Computing operation are union, intersection and differ entence of two set. -Each operation require large amount of searching elements.

 Example 1:     Let U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, and the ordering of elements of U has the elements in increasing order; that is, ai = i . What bit strings represent the subset of all odd integers in U, the subset of all even integers in U, and the subset of integers not exceeding 5 in U?    


Solution:    The bit string that represents the set of odd integers in U, namely, {1, 3, 5, 7, 9}, has a one bit in the first, third, fifth, seventh, and ninth positions, and a zero elsewhere. It is 10 1010 1010.   Similarly, we represent the subset of all even integers in U, namely, {2, 4, 6, 8, 10}, by the string   01 0101 0101.   The set of all integers in U that do not exceed 5, namely, {1, 2, 3, 4, 5}, is represented by the string   11 1110 0000. 1) 
Ā (Complement) Solution: Bit string for A: 0101 0111,
Then Ā = 1010 1000 (Therefore, Ā = {0,1,2,4})

2)       A ∩ B (Intersection) Solution: Bit string for A: 0101 0111 Bit string for B: 1111 1100
Then, A ∩ B =0101 0111 ˄  1111 1100 = 0101 0100        
         (A ∩ B = {1,3,5} )

3)      A U B (Union) Solution: Bit string for A: 0101 0111 Bit string for B: 1111 1100   Then A U B = 0101 0111 ˅  1111 1100 = 1111 1111
(A U B = U = {0,1,2,3,4,5,6,7})



 2.Relation 

 Relation Between 2 Sets:
 A relation is a set of ordered pairs(x,y) ,
 -the first component are the input values(Domain).
 - second component are the output values(Range).

A relation R defined by ( , {(x,y):x  }), is the set of ordered pairs of all Input Values (x) and all Output Values(y) such that each element x is related to the corresponding element y. Here, x=Domain of the Relation y=Range of the Relation x & y no values, it will repeated x is called Independent variable and y is called Dependent variable because its value depends on the x-value chosen.







 3.FUNCTION

Function DEFINITION OR CONCEPT OF FUNTION ON GENERAL SETS
Function is a relation between a set of inputs and a set of permissible outputs with the property that each input is related to exactly one output. As an example:-

The function f maps to A to B 


Boolean function
A Boolean function describes the ways to gain the value of boolean output via logical calculation from Boolean inputs. 
The functions play a basic role in questions of complexity theory also the design of circuits and chips for digital computers.



The properties of Boolean functions play a critical role in cryptography, particularly in the design of symmetric key algorithms Boolean functions are often represented by sentences in propositional logic, and sometimes as multivariate(involving 2 or more variables) A literal is a Boolean variable or its complement. A minterm of the Boolean variables x1,x2,...,xn is a Boolean product y1y2 ···yn, where yi = xi or yi = xi. Hence, a minterm is a product of n literals, with one literal for each variable.

Example:
Find the sum-of-products expansion for the function F (x, y, z) = (x + y)z. Solution: We will find the sum-of-products expansion of F (x, y, z) in two ways. First, we will use Boolean identities to expand the product and simplify.
We find that
 F (x, y, z) = (x + y)z =xz+yz =x1z+1yz =x(y+y)z+(x+x)yz 
=xyz+xyz+xyz+xyz =xyz+xyz+xyz.

 Distributive law Identity law Unit property Distributive law Idempotent law Second, we can construct the sum-of-products expansion by determining the values of F for all possible values of the variables x, y, and z. These values are found in Table 2. The sum-of- products expansion of F is the Boolean sum of three minterms corresponding to the three rows of this table that give the value 1 for the function.
This gives F (x, y, z) = xyz + xy z + xyz.
It is also possible to find a Boolean expression that represents a Boolean function by taking a Boolean product of Boolean sums. The resulting expansion is called the conjunctive normal form or product-of-sums expansion of the function.



INJUCTIVE : f (a) = f (b) implies that a = b for all a and b in the domain of f. Involves one to one function.

It can be injective (or one-to-one), where any value in the codomain/range can be produced by at most one value from the domain. The example function f(x) is NOT injective if we define its domain and codomain both as the real numbers (since 4*4 = 16, but (-4)*(-4) = 16). 
Despite, if we define its domain as the positive real numbers, then it is injective.


SURJECTIVE : Onto function every element b ∈ B there is an element a ∈ A with f (a) = b. BIJECTION : one-to-one function AND onto function.

this can be surjective (or onto), which means that every value in the codomain can be produced by the function. If we define both the domain and the codomain of the example f(x) to be all real numbers, then f(x) is NOT surjective, due to unable to produce negative numbers with the given domain.


INVERSE FUNCTION : Definition Let f be the bijection from set A to the set B The inverse function of f is the function that assigns to an element b belonging to B the unique element a in A such that   f (a) = b  The inverse function of f is denoted by  fˉˡ  Hence,  fˉˡ (b) = a  when f(a) = b
Example:

Example
let f : R     
R be the bijection given by the formula: f(x)= 4x + 1
    • Write f(x) = y ,that is  4x + 1 = y
    • Then solve for x
                   4x = y + 1
                    x = y – 1
                            4
Answer:   fˉˡ (y)= = y – 1
                                      4

 DEFINITION OF COMPOSITION OF FUNCTION
Process to combine two functions . One function is to be done first then its result is substitute in place of each x to another function. notation for a composite function : ( ƒº g) (x) = ƒ( g(x))

Given that ƒ (x) =5x and g (x) =x²+2.
Find ( ƒºg )(x) and (gºƒ)(x)
Solution 1:                                      Solution 2: (ƒºg)(x)                                          (gºƒ)(x)
 -ƒ( g (x))                                       - g(ƒ(x))
  ƒ (x²+2)                                       - g(5x)
  5( x²+2)                                        -(5x)²+2
  = 5x²+10                                      -5x²+2

Given that ρ(x)=x+4 and h(x) = x²
get the value of 
 a) (hºρ)(x)                 b) (ρºh)(3)
    -h(ρ(x))                    -ρ(h(x))
    -h(x+4)²                   -ρ(3)²
    -x²+8x+8                 -9+4 =11

here are the slides :) enjoy


  • Digg
  • Del.icio.us
  • StumbleUpon
  • Reddit
  • RSS

task 2

this is our second mission after accomplished with our presentations.
might have some modifications needed to be applied on our former posts.



...................................................................................................................................................................

Second Task: TAF3023

Chapter 2: Concept of Set
List of items that you should include on your slide and blog.
  1. Way of listing the elements of Sets
  2. Specifying properties of sets
  3. Set membership
  4. Empty set
  5. Set of numbers (Z,N,etc....)
  6. Set Equality
  7. Venn Diagram
  8. Subset
  9. Power Set
  10. Set Operation
-Union
-Intersection
-Disjoint Set
-Set Difference
-Set Complimentary
-Characteristics of set
11. Generalised Union and Intersection
12. Cartesian Product

we compiled our quest in completing our second task by seacrhing in the web, books as refrences.
again to remind, we dont own the copyrights :)
enjoy!

  • Digg
  • Del.icio.us
  • StumbleUpon
  • Reddit
  • RSS

outcomes ^__^

we have been working in our own group to come out with these outcomes.
these are the things we have been searching though out the web, books etc
again we don't own the copyrights, instead knowledge have the rights to be spread :)
enjoy the 'outcomes'


1. PROPOSITIONAL LOGIC

     
        Propositional Logic is concerned with propositions and their interrelationships. It also known as sentential logic and statement logic is the branch of logic that studies ways of joining or modifying entire propositions, statements or sentences. It were form more complicated propositions as well as the logical relationships and properties that are derived from these methods of combining or altering statements. 
well in simpler words, you can just imagine such combinations of the sudoku puzzles, the cubics, it is all the matter of logics and great numbers of different codes and ways produced of any events etc

Example and Observations:
  • "An argument is any group of propositions where one proposition is claimed to follow from the others, and where the others are treated as furnishing grounds or support for the truth of the one. An argument is not a mere collection of propositions, but a group with a particular, rather formal, structure.

    "The conclusion of an argument is the one proposition that is arrived at and affirmed on the basis of the other propositions of the argument.

    "The premises of an argument are the other propositions which are assumed or otherwise accepted as providing support or justification for accepting the one proposition which is the conclusion. Thus, in the three propositions that follow in the universal deductive categorical syllogism, the first two are premises and the third the conclusion:
All men are mortal.
Socrates is a man.
Socrates is mortal.
(Ruggero J. Aldisert, "Logic in Forensic Science." Forensic Science and Law, ed. by Cyril H. Wecht and John T. Rago. Taylor & Francis, 2006)

Example of Arguments
  • the software won’t compile or it produces a division by zero error.
      the software does not produce a division by zero error
      Therefore the software will not compile.
                 if its in general form it will defines appropriate propositional
                 variables.
                this example of argument is called 'disjunctive syllogism'.


Another disjunctive syllogism examples:
The cars are yellow or green.
The cars are not green.
Therefore the cars are yellow.
Let X be: the cars are yellow.
Let Y be: the cars are green.

Rewritten argument:
X or Y not Y
Therefore X
This argument is valid, its not that meaningful since both X and Y are not true.

Propositional variable
  • A variable which can neither be TRUE nor FALSE.
  • The atomic formulas of propositional logic.
  • Typically, the formulas built up recursively(repeatedly) from some propositional variable, some number of logical connectives and some logical quantifiers. 

Truth table
The general truth tables for each of the connectives informs the value of any possible statement for each of it.

Negation


Conjunction
(declare BOTH statements are true.)


Disjunction
(declare at least ONE statement is true.)


Material  Equivalence
(Asserts the statements always have the SAME truth value.)

Material  Implication
(Antecedent sufficient for consequent)
Assume that a material implication is TRUE except proven FALSE.


To determine how many lines a truth table will have use this formula:
Lines = 2n
n = the number of different letters (simple statements) in the statement.

Starting with the left most letter, divide the table in half.  
Assign T as the value of the left most letter for the first half of the table, 
and F as its value for the second  half of the table.
Move to the next new letter to the right, and cut the alternation between T & F in half.  
Repeat this process until you are alternating between T& F line by line for the right most letter.

Assuming you are playing puzzles! :)

Tautology:  A statement forms invokes as its become true. got T on every line beneath its main symbol on it's truth table
Self-Contradiction:  A statement in which the form of invoke that it be FALSE.  
It’s truth table has F on every line beneath its main symbol.
Contingent Statement:  A statement in which the truth value is depend on the particular combinations of values for its letters (simple statements). 
It’s truth table has T on some lines and F on some lines on the bottom of the main symbol.


#  Logically Equivalent Statements:  The 2 statements have the same equal truth value on every line beneath their main symbols.

# Logically Contradictory Statements:  The 2 statements have the opposite(different) truth values on every line beneath their main symbols.


Consistent Statements:
    1. The statements are neither equal nor opposed.
    2. The least is when one line statement's is true
Inconsistent Statements:
    1. The statements are neither equal nor opposed.
    2. there is not even a line should be true.
If there is no line on which all the premises are true and the conclusion false, then the argument is valid.

If there is even one line on which all the premises are true and the conclusion false, then the argument is invalid.




2. PROPOSITIONAL EQUIVALENCE

Definition:
1.Tautology : is a proposition that is always true.
Example:-p ˅ ¬p          




e.g:
P:the switch is on.
Q:the switch is on.
This is tautology.Both is true.

2.Contradiction :  is a proposition that’s is always false.
Example:-p Ʌ¬p 
e.g:
P:the switch is off.
Q:the switch is off.
This is contradiction.Both is false.

3.Contingency :is a proposition that’s is neither  a tautology nor a contradiction.
Example:-p ˅ q→¬r
e.g:
P:the switch is off.
Q:the switch is on.
This is contingency.Both is neither  tautology nor a contradiction.

LOGICAL EQUIVALENT
Definition-proposition r and s are logically equivalent if the statement  r↔s is a tautology.
Notation:If  r and s are logically equivalent, we write as

r ˂═> s





3. PREDICATES AND QUANTIFIERS

Predicates:

    • Is a method to determine statement  which is true or false value based on one or more variables. 
    • In a statement there are 2 things:

      >Subject.
      >Predicate



Propositional Function?
    • A statement of in term of p (x1,x2……,xn)
    - P(x1,x2,…,xn) propositional function value of p. P is a.k.a predicate.
      ** (x1,x2,…,xn) n is tuple

functions :
    • To determine either the statement is true or false
    • To prove of argument 1 or more which are given.
    • If the value is assigned, proposition can be concluded
Example:
    • A ( a,b,c,d), we denote it to“(a+1),(b+1),(c+1)= d+1”. Given that, A (2,3,4,11) and A(2,2,2,9).
      Which is the truth value? 


Quantifiers:

A  quantifier is a type of logical symbol that is used to make a quantification or assertion about the set of value which make the formula or formulas true

Simpler: quantifier is an expression that make the formula true

Types of Quantifiers:

(i) universal Quantifiers :


assert that p(x) is true for every values in particular domains

e.g of expression: 
for all” or “for every” or “each” or ”for any

Example in daily life:

e.g of universal quantifier in daily life:
*for every car that the factory want to sell, it must be painted.

*All driver must obey the laws to prevent themselves to get fine




(ii) Existential Quantifier:




e.g of existential quantifier in daily life:
*not everybody in your class who know how to talk in javanese
*at least 3 people in your class is in the dean list

*there is a couple of person in your class whose using macbook


(iii) uniqueness Quantifier



refrences:


http://en.wikipedia.org/wiki/Proposition
http://logic.stanford.edu/classes/cs157/2009/notes/chap02.html
etc






  • Digg
  • Del.icio.us
  • StumbleUpon
  • Reddit
  • RSS