Monday 18 March 2013

sequences,mathematical induction and recursion


Types of sequence



1.   Arithmetic Sequences

2.   Geometric Sequences

3.   Special Number Sequences

·        Triangle Numbers

·        Square Numbers

·        Cube Numbers

·        Fibonacci Numbers




Give 1 example sequences use in computer programming


Sequence in computer programming is the default control structure, instructions are executed one after another. They might, for example, carry out a series of arithmetic operations, assigning results to variables

Example:-
Make a list number of 100 students that attend “seminar keusahawanan”.

Pseudocode
BEGIN
            Declare a list as an array with 100 elements
              for (int student = 0, student<100; student++){
                    list[student] = student + 1 à (arithmetic operation)
                    print list[student]
              }
END

Answer:
No.Student = 0
Print list[student] = 1
No.Student = 1
Print list[student] = 2
.
.
.
.
Print list[student] = 99
No.Student = 100

Source Code
public class sequences {
            public static void main(String[] args) {
             int list [] = new int[100];
            for(int student = 0; student<100; student++) {
                        list[student] = student + 1;
                        System.out.println(list[student]);
                                    }
            }

}

Monday 11 March 2013

Task 3-continue set theory

Task 3 : Set Theory



1. COMPUTER REPRESENTATION of SETS



i) Let A = {1,2,3,5} (from universal set {1,2,3,4,5})


how to represent : 11101
1  2  3  4  5 
                                                            1  1  1  0  1  <---- if the number exist we represent the value      
                                                                                                 by 1, else 0
:- thus, the representation of {1,2,3,5} in computer is 11101 !

ii) Union = OR

   11100 V 10110 = 11110

iii) Intersection

     100111 ʌ 10111 = 100111


iv) Complement

     10101 ---> 01010



2. RELATION


If we want to describe a relationship between elements of two sets A and B, we can use ordered pairs with their first element taken from A and  their second element taken from B.
Since this is a relation between two sets, it is called a binary relation.

Definition:

Let A and B be sets. A binary relation from A to B is a subset of A´B.
In other words, for a binary relation R we have  R Í A´B.
We use the notation aRb to denote that (a, b)ÎR and aRb to denote that (a, b)ÏR.
When (a, b) belongs to R, a is said to be related to b by R.

Example: 

Let P be a set of people, C be a set of cars, and D be the relation describing which person drives which car(s).
P = {Carl, Suzanne, Peter, Carla}
C = {Mercedes, BMW, tricycle}
D = {(Carl, Mercedes), (Suzanne, Mercedes), (Suzanne, BMW), (Peter, tricycle)}
This means that Carl drives a Mercedes, Suzanne drives a Mercedes and a BMW, Peter drives a tricycle, and Carla does not drive any of these vehicles.

Functions as Relations

You might remember that a function f from a set A to a set B assigns a unique element of B to each element of A.
The graph of f is the set of ordered pairs (a, b) such that b = f(a).
Since the graph of f is a subset of A´B, it is a relation from A to B.
Moreover, for each element of A, there is exactly one ordered pair in the graph that has a as its first element.
Conversely, if R is a relation from A to B such that every element in A is the first element of exactly one ordered pair of R, then a function can be defined with R as its graph.
This is done by assigning to an element aÎA the unique element bÎB such that (a, b)ÎR.

Relations on a Set

Definition: A relation on the set A is a relation from A to A.
In other words, a relation on the set A is a subset of A´A.
Example: Let A = {1, 2, 3, 4}. Which ordered pairs are in the relation R = {(a, b) | a < b} ?
Answer: R = {(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}

Properties of Relation

(1)Reflexive
A relation R on a set A is called reflexive if (a, a)ÎR for every element aÎA.
Example:
= {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}

Answer: R is reflexive because they both contain all pairs of the form (a, a),namely, (1, 1), (2, 2), (3, 3), and (4, 4).

(2)Irreflexive
A relation on a set A is called irreflexive if (a, a)ÏR for every element aÎA.
Example:
These 4 irreflexive relations are :
1. Empty
2. {(1,2)}
3. {(2,1)}
4. {(1,2), (2,1)}

(3)Symmetric
A relation R on a set A is called symmetric if (b, a)ÎR whenever (a, b)ÎR for all a, bÎA.

Example:

R={(1, 1), (1, 2), (2, 1)}

Answer: R is symmetric.Both (2, 1) and (1, 2) are in the relation so R is symmetric.

(4) Antisymmetric
A relation R on a set A is called antisymmetric if a = b whenever (a, b)ÎR and (b, a)ÎR.

Example:

R={(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)}

Answer:R is antisymmetric.There is no pair of elements a and b with a ≠ b such that both (a, b) and (b, a) belong to the relation.


(5)Transitive
A relation R on a set A is called transitive if whenever (a, b)ÎR and (b, c)ÎR, then (a, c)ÎR for a, b, cÎA.

Example: Are the following relations on {1, 2, 3, 4} transitive?

Answer: R = {(1, 1), (1, 2), (2, 2), (2, 1), (3, 3)}

3. FUNCTIONS

Definition or concept of function on general sets

In discrete mathematics ,functions are used
in the definition of such discrete structures as sequences and strings.
used to represent how long it takes a computer to solve problems of a given size.

Concept of function:

Let and be nonempty sets.
function f from to is an assignment of exactly one element of to each element of A.
We write f (a) if is the unique element of assigned by the function to the element of A.
If is a function from to B, we write f → B

•If is a function from to B, we say that is the domain of and is the codomain of f.
•If f (a) b, we say that is the image of a and is a preimage of b.
•The range, or image, of is the set of all images of elements of A.,
• if is a function from to B, we say that f maps A to B.

Concept of Boolean Function

Definition 1 : literal is a Boolean variable or its complement. A minterm of Boolean variables x1x2, . . . , xn is Boolean product yy2. . .yn where yi xi or
Example1:
Find the minterm such that = 1 if x1 = x3 = 0 and = 0 if x2 = x4 = x5 = 1.
Solution: The minterm is
The sum of minterms that represents the functions is called the sum-of-products expansion or the disjunctive normal form of the Boolean function.

Injective functions

Injective means that every member of “A” has its own unique matching member in “B”.
A function f is injective if and only if whenever f(x) = f(y), x =y.
It’s also called “one to one”.
Ex: {a, b, c, d} to {1,2,3,4,5} with f(a) =2, f(b) =1, f(c)=3, f(d)=4 is one to one.

Surjective functions (an onto function)

 Surjective means that every “B” has at least one matching “A” (maybe more than one).
A function f (from set A to B) is surjective if and only for every y in B, there at least one x in A such that f(x) = y, in other words f is surjective if and only if f(A) = B.
Ex: f be the function from {a,b,c,d,e} to {1,2,3,4} defined by f(a)=2, f(b)=1, f(c)=3, f(d)=3, f(e)=4. Is f is onto function?
Answer: NO

Bijective functions 

Bijective means both Injective and Surjective together.
Perfect “one-to-one correspondence” between the members of the sets is existed.
A function f (from set A to B) is bijective if, for every y in B, there is exactly one x in A such that f(x) = y.
Ex: f be the function from {a,b,c,d,e} to {1,2,3,4,5} with f(a)=2, f(b)=1,
f (c)=6, f(d)=3, f(e)=5. Is f a bijection?
Answer: YES.

Definition and example of inverse function

An inverse function, which we call f-1  is another function that take y back to x. f(x)= y. So, f-1(y)= x.

Example:
  Let f: Z    Z be such that f(x)=x+1
  f(x)= x+1
  y=x+1
  y-1=x
  f-1(y)= y-1
  
Definition and example of composition function


Let g be a function from the set A to the set B and let f be a function from the set B to the set C. The composition of the functions f and g, denoted  by f ◦ g, is defined by
                              (f ◦ g)(a) = f (g(a)).

Example:
         f (x) = 2x + 3 and g(x) = 3x + 2

Solution:
        (f ◦ g)(x) = f (g(x)) 
        f (3x + 2) = 2(3x + 2) + 3 = 6x + 7
   and
        (g ◦ f )(x) = g(f (x))
         g(2x + 3) = 3(2x + 3) + 2 = 6x + 11.

































Monday 25 February 2013

Logic

1.PROPOSITIONAL LOGIC
Material Equivalence - Asserts the statements always have the same truth value                              






2.PROPORTIONALEQUIVALENCES


Definition: two propositional form on the same variables (logically) equivalent if they have the same result column in their truth table notation .

Tautology = proposition that is always true
Contradiction = proposition that is always false
Contingency = proposition that is neither tautology nor contradiction



Contigency
Two compound proposition p and q are logically equivalent if the columns in a truth table giving their truth values agree.
p ≡q if and only if p    q is a tautology.



3.PREDICATES AND QUANTIFIERS



 Proposition 

 a possible condition of the world about which  want to say           
       something.
                 


Propositional Variables


a variable which can be the true or false.



 Types of Truth Table 





Negation





       Conjunction - assert both statement are true




Disjunction - Asserts at least one statement is true
Material implication -  assume it is true unless proven false



Introduction to Predicates

➳ Also known as propositional function

➳ Sentences that contain variable either true or false depending on value assign to variables.

Denote by P(x)
Exp : P(x): x>3

Definition Quantifiers

Quantifers are words that refer to quantities such as "some" or "all" and tell for
      how many elements a given predicate is true

 Two type  of quantifiers


 universal quantifier:

DEFINITION
v  predicate is true for all values 
v  symbol:   "
v read: for all

example
P(x) : “x must take a discrete mathematics course”
Q(x):  “x is a computer science student”.

Express the statement “Every computer science student
must take a discrete mathematics course”.
"x(Q(x) → P(x))

Express the statement “Everybody must take a discrete
mathematics course or be a computer science student”.
"x(Q(x) ˅ P(x))


existential quantifier:
 DEFINITION
v  predicate is true for some values 
v  symbol: $ 
v  read: there exists

P(x) : “x must take a discrete mathematics course”
Q(x):  “x is a computer science student”.

Express the statement “some computer science student
must take a discrete mathematics course”.
$x(Q(x) → P(x))

Express the statement “some student must take a discrete
mathematics course or be a computer science student”.
$x(Q(x) ˄ P(x))

EXAMPLES OF USING QUANTIFIERS IN REALITY

Assume:

A(x) :  x is a apple.
B(x) :  x is a banana.
C(x) :  x is cherry.

and the universe of discourse for all three functions is the set of all fruits.

-  Everything is a apple :  "x A(x)
- All apple are banana :   "A(x) → B(x) ]
-Some are banana :  $x B(x)