Discrete Structure and Optimization

Binary Operation: - Let S be a non-empty set, and * said to be a binary operation on S  if a * b is defined for all a, b  ∊  S. In other words, * is a rule for any two elements in the set S. Closure Property: - Let S be a non-empty set, A binary operation * on S is said to be a closed binary operation on S, if  a * b  ∊  S, for all a, b  ∊  S. Associative Property: - Let S be a subset of Z. A binary operation * on S is said to be associative, if  (a * b) * c = a * (b * c) for all a, b, c  ∊  S Commutative Property: - Let S be a non-empty set. A binary operation * on S is said to be Commutative, if  a * b = b * a for all a, b  ∊  S. Identity Property: - A non-empty set S with binary operation *, is said to have an identity e  ∊  S, if e * a = a * e = a, for all a  ∊  S Distributive Property: - Let S be a non-empty set. Let * 1 and * 2 be two different binary operations on S.  Then...

An algebraic system <R, +, • >, where R is a non-empty set, ‘+’ and ‘•’ Two binary compositions defined onset R is called a ring if.                (R, +) is Abelian group (a+b)+c = a+(b+c) for all a,b,c ∊  R a+b = b+a for all a,b  ∊ R for all a  ∊ R, - a  ∊ R, such that a+(-a) = 0 for all a  ∊ R, o  ∊ R such that a + o = a     (R,  • ) is semi group (ab)c = a(bc)      Distributev Law {a(b+c) = ab + ac} and {(a+b)c = ac + bc} for all a,b,c  ∊ R Key Terms in Rings: - Integral Domain: - A commutative ring R which contains no proper zero-divisor is called an integral domain.                 If ab = 0 for a,b  ∊  z then                 a = 0 or b = 0 Sub ring: - A non-empty subset S ...

A recurrence relation is an equation that represents a sequence based on some rule. It helps in finding the subsequent term (next term) dependent upon the preceding term (previous term) Example: - Find B(3) of the sequence B(0) = 2 and B(k) = B(K-1)+3 for K ≥  1 1. By recursion formula B(3)        = B(2) + 3                 = (B(1) + 3) + 3                 = ((B(0) + 3) + 3) + 3                 = ((2 + 3) + 3) + 3                                                              = 11  2. By Iteration method B(1) = B(0) + 3 = 2 + 3 = 5 B(2) = B(1) + 3 = 5...

A graph is a diagram consisting of a collection of vertices together with edges joining certain pairs of these vertices. 𝐺=[𝑣(𝐺),𝑒(𝐺)] Graph Theory: - Graph Theory is the study of the relationship between vertices and edges. Types of Graph: - Directed Graph: - In which the edges have a direction associated with them. Undirected graph: - In which all the edges are bidirectional. Null graph: - not any edges only vertices. Simple graph: - undirected and no loop and no multi edges. Multigraph: - multiple edges between the same set. Connected graph: - if any two vertices of the graph are connected by a path Disconnected graph: - a graph where any two vertices or nodes are disconnected by a path. Cycle graph: - if a graph consists of a single cycle, it is called a cycle graph. Complete graph: - when each pair of vertices are connected by an edge then such graph is called a complete graph. Planar graph: - when no two edges of a graph intersect and are all the vertices and edges ar...

A combination is a selection of some or all, objects from a set of given objects, where the order of the objects does not matter. Example 1: - In other words choosing 3 balls out of 16, or choosing 13 balls out of 16 have the same number of combinations Example 2: - A former purchased 3 caws, 2 pigs, and 4 hens from a man who has 6 caws, 5 pigs, and 8 hens. Find the number m of choices that the former has –

A permutation is an ordered arrangement of the objects in a collection. They are further classified into two types. Repetition of Objects: - When a thing has n different types ….. !n Choosing r of something that has n different types, n * ....................... (r time) Example 1 : - In the lock, there are 10 numbers to choose from 0-9 and we choose 3 of them, 10 * 10 * 10 = 1000 (n**r) Example 2 : - How many 3 digits even numbers can be formed from the digits 1, 2, 3, 4, 5, 6 if the digits can be repeated? Number of 3 digit even number = 6 * 6 * 3 = 180 Without Repetition of Object: - In this case, we have to reduce the number of available choices each time. Example 3 : - In how many ways can a letter of the word PERMUTATIONS be arranged if the: - Words with start with P and ending with S let the first position be P & last position be S (both are fixed) Since letters are repeating. Total number of letters (n) = 10 & since, 2T Vowels are all together, Vowels in word PERMUT...

Boolean algebra is the category of algebra in which the variable’s values are the truth values, true and false ordinarily denoted 1 and 0 respectively. It is used to analyze and simplify digital circuits or digital gets. Boolean Algebra Operations Conjunction or AND  A B A ∧ B 1 1 1 1 0 0 0 1 0 0 0 0 Disjunction or OR   A B A V B 1 1 1 1 0 1 0 1 1 0 0 0 Negation or NOT  A ㄱA 1 0 0 1 Laws of Boolean Algebra Commutative law AB = BA A+B = B+A Associative law (AB)C = A(BC) (A+B) +C = A+(B+C) Distributive law A(B+C) = (AB) + (AC) A+(BC) = (A+B) (A+C) AND law A0 = 0 A1 = A AA = A AA’ = 0 OR law A +...

Function: - It is a mapping in which every element of set A is uniquely associated at the element with set B. The set of A is called Domain of a function and set of B is called co-domain. Domain: - The set of A is called Domain of function Co-Domain: - The set of B is called Co-Domain. Range: - It is a collection of the second values in the ordered pair. Types of Functions / Properties: - One-to-One (Injective): - One element of the Domain set is connected to one element of the Co-Domain set. Onto (Surjective): - Every element of the Co-domain set have one pre-image. Bijective (1:1 and onto): - Into: - If there exists even a single element in B having no pre-image in a, then f is said to be an into function.  Clearly, f is a function from A to B. Now, there exists an element C <- B, having no pre-image in A. so, f is an into function. One-one into: - f x -> y. The function f is called one-one into a function if different elements of x have different unique images ...