Unit 2 | DSTL Notes |Discrete Structure and Theory of Logic Notes | Aktu Notes

Unit 2 | DSTL Notes |Discrete Structure and Theory of Logic Notes | Aktu Notes

Function

- A function is considered to be a specific type of relation between sets.

- Formally, a function f from set A to set B, denoted as f:A→B, 

- assigns to every element x in set A exactly one element y in set B. This is often expressed as f(x)=y.

- Domain: The set of all valid input values x.

- Codomain: The set of all possible output values y.

- Range: The set of all actual output values that the function can produce

Classification of function

- Algebraic Functions: These involve a finite number of terms with powers and roots of the independent variable x.

1) Polynomial Functions: a0x^n+a1x^n−1+…+an where n is a positive integer and 0,1,.......a0,a1,…,an are constants.

2) Relational Functions: g(x)/f(x) where f(x) and g(x) are polynomials.

3) Irrational Functions: Involves radicals, such as f(x)=x^(1/3) or f(x)=x^(1/2)

- Transcendental Functions: These are not algebraic.

1) Trigonometric Functions: sinx, cosx, tanx ,secx, cosecx, cotx.

2) Inverse Trigonometric Functions: 

sin^(−1)x,cos^(−1)x,tan^(−1)x,cot^(−1)x,sec^(−1)x,csc^(−1)x. 

3) Exponential Functions: a^x where a>0.

4) Logarithmic Functions: log a x, the inverse of exponential functions.

Types of Mapping/ Functions

1) Injective Function (One-to-One): A function where each element of the domain maps to a unique element in the codomain. 

Let f:XY and f(x1)=f(x2) implies x1=x2

Ex: f(x)=2x - Every distinct x value maps to a unique f(x).

2) Surjective Function (Onto): A function where every element in the codomain has at least one pre-image in the domain.

Let f:XY and elements x ∈ X ,y ∈ Y then f(x)=y or Range(f)=Y

Ex: f(x)=x2 is not onto but f(x)=x3 is onto function 

Every real number y has at least one corresponding x.

3) Bijective Function: A function that is both injective and surjective

Ex: f(x)=3x+2 - Each x has a unique f(x), and every real number is a f(x).

4.Identity Function:

- if we have a function f:X→X, then f is called the identity function if f(a)=a for every element a in X.

- In other words, every element of the set X is mapped to itself by the function f. 

Question: solve these are bijective or not 

i) x^2 ii) x^3

i) Let x1 , x2  belongs to R such that f(x1 ) = f(x2 ) 

(x1^2 ) = (x2^2 ) => x1^2 = x2^2 => x1 = ± x2

Therefore, if x2 = 1 then x1 = ± 1 So, f is not one-to-one.

ii) Let x1 , x2 belongs to R such that f(x1 ) = f(x2 ) 

(x1^3) = (x2^3) => x1 = x2 Therefore f is not one-to-one.

Let y belongs to R such that y = x^3 => x = (y) 1/3 For all y belongs to R such that y = f(x)  Therefore f is onto. Hence, f is bijective.

Inverse Functions

- Two functions, f(x) and f^(−1) (y), are inverses if they "undo" each other's actions

- inverse function should be injective and surjective.

Composite Function

Composite function, denoted g∘f, represents the composition of two functions, f and g.

Question: If f: A -> B and g: B -> C are one-one functions, show that g o f is a one – one function.

1. let x, y ∈ A such that

2. g o f(x) = g o f(y)

3. g(f(x)) = g(f(y))

4. f(x) = f(y)

5. x = y Therefore, g o f is one – one function.

Question: If f : A -> B, g : B -> C are invertible functions, then show that g o f : A -> C is invertible and (g o f)^(–1) = f^(–1) o g^(–1)

Prove: g o f : A -> C

f and g are invertible functions then both are one-one and onto function 

f (x1) = f (x2) => x1 = x2 (from one-one)

g (y1) = g (y2) => y1 = y2 (from one-one)

since (g o f) (x1 ) = (g o f) (x2 ) 

=> g [f(x1)] = g [f (x2)] 

=> f (x1 ) = f(x2 ) [g is one-to-one] 

=> x1 = x2 [f is one-to-one] 

Since g is onto, for z belongs to C, there exists y belongs to B such that g (y) = z. 

Also f being onto there exists x belongs to A such that f (x) = y.

Hence z = g (y) = g [f(x)] = (g o f) (x)

Thus, g o f is one-to-one onto function and hence (g o f)^(–1) exists. g o f is invertible 

Prove:(g o f)^(–1) = f^(–1) o g^(–1)

(g o f)^(–1) (z) = x 

(g o f) (x) = z <=> g (f (x)) = z 

g (y) = z where y = f (x) 

<=> y = g^(–1) (z) 

f^(–1) (y) = f^(–1) (g^(–1) (z)) = (f^(–1) o g(–1) ) (z)

x = (f^(–1) o g(–1)) (z) [f^(–1) (y) = x] 

Thus, (g o f)^(–1) (z) = (f^(–1) o g^(–1)) (z). 

So, (g o f)^(–1) = f^(–1) o g^(–1)

Growth of Functions

- The growth of a function, often discussed in the context of asymptotic analysis, 

- describes how the function's value increases as the input grows towards infinity.

- Here are some common growth rates of functions

- constant growth , logarithmic growth , linear growth , polynomial growth , exponential growth ,fractional growth 

- we can analysis the growth of function using notation , we have mainly three types of notations in the functions:

Big-oh notation:

- It is the method of expressing the upper bound of an function running time. 

- It is the measure of the longest amount of time. The function f (n) = O (g (n)) 

- f(n) <= c.g(n) where n>n0

- Example: 3n+2=O(n) as 3n+2≤4n for all n≥2

Big-Omega notation:

- It is the method of expressing the lower bound of an function running time. 

- It is the measure of the smallest amount of time. The function f (n) = Ω(g (n)) 

- f(n) >= c.g(n) where n>n0

- Example: 3n-3= Ω (n) as 3n-3 >=2n for all n≥3 

Theta(Θ) notation:

- It is the method of expressing the both lower and upper bound of an function running time. 

- It is the measure of the average amount of time. The function f (n) = Θ(g (n)) 

- c1.g(n) <= f(n) <= c2.g(n) where n>n0

- Example: 3n-3=O(n) as 2n<= 3n-3 <= 4n for all n≥3

Boolean Algebra

- Boolean algebra works with variables that can have only two values: true (1) or false (0).

- It defines operations like AND (⋅), OR (+), and NOT (x’) to manipulate these binary variables.

- True is represented by 1 and false by 0. These values are used to represent the outcomes of logical operations.

- Using these operations, you can combine true/false statements to form new statements and analyze their truth 

values.

- Applications: in digital circuit design, computer programming, and logical reasoning.

Axioms of Boolean Algebra

- Fundamental rules defining properties of logical operations and variables.

1. Identity laws: x+0=x and x⋅1=x

2. Complement laws: x+x¯=1 and x⋅x¯=0

3. Associative laws: x+(y+z)=(x+y)+z and x⋅(y⋅z)=(x⋅y)⋅z

4. Distributive laws: x⋅(y+z)=(x⋅y)+(x⋅z) and x+(y⋅z)=(x+y)⋅(x+z)

Laws of Boolean Algebra

- Derived from axioms, they represent algebraic manipulations applicable to Boolean expressions.

- Idempotent laws: a. a + a = a b. a.a = a 

- Boundedness (Dominance) laws: (i) a + 1 = 1 (ii) a.0 = 0 

- Absorption laws: (i) a + (a.b) = a (ii) a.(a + b) = a 

- Associative laws: 

(i) (a + b) + c = a + (b + c) (ii) (a.b).c = a.(b.c) 

- Uniqueness of complement: 

a + x = 1 and a.x = 0, then x = a 

- Involution law: (a')' = a 

- De-Morgan’s laws: (i) (a + b)' = a'.b' (ii) (a.b)' = a' + b'

- Commutative laws: (i) a+b=b+a (ii) a.b=b.a

Proves of Laws of Boolean Algebra

Absorption Law : 

To prove : a.(a + b) = a

Let a.(a + b) = (a + 0).(a + b) by Identity 

= a + 0.b by Distributive 

= a + 0 by commutative+Dominance 

= a by Identity 

To prove : a + a.b = a

Let a + a.b = a.1 + a.b by Identity 

= a.(1 + b) by Distributive 

= a.1 by Commutative +Dominance 

= a by Identity law

Idempotent Law:

To prove : a + a = a and a.a = a 

Let a = a + 0 by Identity 

= a + a. a' by Complement 

= (a + a).(a + a') by Distributive 

= (a + a).1 by Complement 

= a + a by Identity 

Now let a = a.1 by Identity 

= a.(a + a') by Complement 

= a.a + a.a' by Distributive 

= a.a + 0 by Complement 

= a.a by Identity

De Morgan's Law

To prove : (a + b)' = a'.b'

To prove the theorem we will show that (a + b) + a'.b' = 1 

Consider ,

(a + b) + a'.b' = {(a + b) + a'}.{(a + b) + b'} by Distributive 

= {(b + a) + a'}.{(a + b) + b'} by Commutative 

= {b + (a + a')}.{a + (b + b')} by Associative 

= (b + 1).(a + 1) by Complement 

= 1.1 by Dominance 

= 1 

Also consider 

(a + b).a'b' = a'b'.(a + b) by Commutative 

= a'b'.a + a'b'.b by Distributive 

= a.(a'b') + a'.(b' b) by Commutative 

= (a. a').b' + a'.(b. b') by Associative 

= 0. b' + a'.0 by Complement 

= b'.0 + a'.0 by Commutative 

= 0 + 0 by Dominance 

= 0 So, a'b' is complement of (a + b) i.e.(a + b)' = a' b'

SOP (Sum of Products)

- Represents a logical expression as the OR (sum) of one or more terms (products).

- Each term is the AND (product) of variables or their complements.

- Example(for algebra): F(x, y, z) = xyz' + xy'z' + x'yz'

- Example(for kmap): f(a,b,c)=Σm(1,3,5,6) means f equals 1 for minterms 1, 3, 5, and 6, and equals 0 for all other minterms.

POS (Product of Sums)

- Represents a logical expression as the AND (product) of one or more terms (sums).

- Each term is OR (sum) of variables or their complements.

- Example(for kmap): f(a,b,c)=ΠM(0,2,4,7) means f equals 0 for maxterms 0, 2, 4, and 7, and equals 1 for all other maxterms.

- Example(for algebra): F(x, y, z) = (x+y+z)(x+y'+z)(x'+y+z)(x'+y'+z) (x'+y'+z')

Kmap (Karnaugh map)

- The Karnaugh Map also called as K Map is a graphical representation

- that provides a systematic method for simplifying the boolean expressions.

- For a boolean expression consisƟng of n-variables, number of cells required in K Map = 2n cells.

Representation of Kmap (2,3,4 variable)

Rules of Kmaps

- No zeros allowed.

- No diagonals.

- Only power of 2 number of cells in each group.

- Groups should be as large as possible.

- Every one must be in at least one group.

- Overlapping allowed.

- Wrap around allowed.

- Fewest number of groups possible.

Question: F(A, B, C, D) = Σm (0, 1, 2, 5, 7, 8, 9, 10, 13, 15)

Question: F(A, B, C, D) = Σm (0, 1, 3, 5, 7, 8, 9, 11, 13, 15)

Question: F(A, B, C, D) = Σm (1, 3, 4, 6, 8, 9, 11, 13, 15) + Σd (0, 2, 14)