Introduction To Languages



Overall it looks good.

The parts highlighted with yellow are incorrect.

The parts highlighted with blue are correct but are to be moved elsewhere.

The sentences in red are my comments.

Introduction To Languages

And

Theory Of computation

Basic Mathematical Objects

Sets

What is a Set?

Set is a group of elements, having a property that characterizes those elements.

How to specify a Set?

One way is to enumerate the elements completely ( all the elements belonging to set are explicitly given) and give a property that characterizes the elements of the Set.

Example: A = {1,2,3,4,5}

Other way is to enumerate the elements in a way that makes clear what the remaining elements are and to give a property that characterizes the elements of the Set.

Example: B = {x/x is a positive integer less than or equal to 5}

C = {1,2,3,4,5,6,……..} ( this is an infinite set)

Add "Recursive definition of sets" with an example.

How to play around with Sets? What do you mean by this ?

x E B implies that x is an element of set B. Using this notation we can specify the set {1,2,3,4,5} by writing

Z = {x ( A \ x q)^(q->p) can be abbreviated using

biconditional conjunction as pq and is read as “p only if q” and “p if q”.

"p if and only if q"

f. Tautology: A compound proposition, which is true in every case.

E.g.: pV (q p V (p

g. Contradiction: This is the opposite of tautology, which is false in every case.

E.g.: p^(q p^(p

Logical implication and equivalence: If the value of Q q is true in every case in,

which p is true then p is said to logically imply q, which is represented as p=>q.

If p and q have same truth-value in each case then both are said to be logically

Equivalent represented as pq.

Logical quantifies and quantified statements: Quantifiers are used to make a

proposition about a domain individual objects. The proposition variable is bound to a particular

domain and not a free variable. Such statements with quantifiers is called a

“quantified statement”.

E.g.: Existential quantifiers (

Universal quantifier (

Need more on Predicate Logic. See my notes I gave you and also my Web pages on predicate logic.

Need an entry on "Relations" here.

Functions:

If f is a function and x is an element of its domain, the element of the co-domain associated with x is written as f(x). Move this down below the next paragraph.

A function associates with, or assigns to each element of one set to a single element in the other set. The former set is called the “domain” and the later is called “Co-domain”.

It A function is represented as follows:

f : A ( B where f is the function, A is the domain and B is the co-domain.

Types of functions:

1. Onto functions: If A and B are two sets, such that f: A ( B and every element in B is associated with an element in A then f is said to be an onto, surjective or surjection i.e. f(A)=B. Define this notation if you want to use it.

2. One-to-One functions: If A and B are two sets, such that f: A ( B and if no single element of B is associated with more than one element in A, then the function f is said to be One-to-One or injective or an injection.

4 must be mapped to something in B. Otherwise you don't have a function.

3. Bijection: A function is said to be bijection if it is both Onto and One-to-One.

Composition of functions:

If f: A ( B and g: B(C then, for any element x(A, the function h: A(C defined by h(x)=g(f(x)) is called the composition of g and f and is written as h=g o f.

Inverse of a function:

If f: A(B is a bijection, then for any y(B and x(A such that y=f(x), the inverse of f denoted by f-1 is defined as x=f-1(y).

-----------------------

[pic]

1

2

3

4

5

a

b

c

1

2

3

4

a

b

c

1

2

3

a

b

c

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

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download