Well Spring University Discrete Structure (CSC 222) PDF

WELL SPRING UNIVERSITY, BENIN CITY, EDOSTATE. DEPARTMENT OF COMPUTING SOFTWARE ENGINEERING,COMPUTER SCIENCE AND CYBER SECURITY PROGRAMME SECOND SEMESTER 2023/2024 (3 UNITS) DISCR...

WELL SPRING UNIVERSITY, BENIN CITY, EDOSTATE. DEPARTMENT OF COMPUTING SOFTWARE ENGINEERING,COMPUTER SCIENCE AND CYBER SECURITY PROGRAMME SECOND SEMESTER 2023/2024 (3 UNITS) DISCRETE STRUCTURE CSC/SEN/CYB 222 1  DISCRETE STRUCTURES What Are Discrete Structures Discrete math is mathematics that deals with discrete objects Discrete objects are those which are separated from (distinct from)each other, such as integers, rational numbers, houses, people, etc.Real numbers are not discrete. In this course, we’ll be concerned with objects such as integers, propositions, sets, relations and functions, which are all discrete. We’ll learn concepts associated with them, their properties, and relationships among them. Discrete structures are: – Theoretical basis of computer science – A mathematical foundation that makes you think logically – A prerequisite course to understand the fundamentals of programming. Applications of Discrete Mathematics in Computer Science There are various applications of discrete mathematics in computer science, which are described as follows: Theoretical Computer Science Discrete mathematics is used to include theoretical computer science, which is relevant to computing. Theoretical computer science draws heavily on logic and graph theory. Using theoretical computer science, we can easily compute the mathematical results by studying algorithms. In case of complexity, we will study the time taken by computations. While in the case of computability, we will study what can be computed by following the principle. Computability is closely related to both theories: formal language theory and automata theory. Information theory The quantification of information is described using the Information theory. Coding theory and information theory are closely related to each other. It has the ability to design storage methods and reliable and efficient data transmission. A lot of continuous topics are also included in the information theory, like analog encryption, analog signals, mathematical logic, and analog coding. 2 Mathematical logic Mathematical logic can also be known as formal logic. In logic, we will learn about the principles of valid inference and reasoning. We can also study completeness, consistency, and soundness. In various logic systems, the law of Peirce's (((P→Q)→P)→P) is considered as theory except for the Intuitionistic logic. In classical logic, it can verify very easily by using the truth table. When we study logic, it is also important to study mathematical proof. Set Theory Set theory can be described as a branch of mathematics in which we study sets. Sets contain the infinite set of prime numbers or objects like green, orange, black, etc. In several areas, we have various applications of sets with other relations and partially ordered sets. In discrete mathematics, our main focus will be on countable sets (including finite sets). Combinatorics Combinatorics is used to describe the way to combine and arrange discrete structures. In enumerative combinatorics, our main concern will be on counting some combinatorial object's numbers. For example, we can count partitions, combinations, and permutations by using the unified framework provided in the twelvefold way. In analytic combinatorics, our main concern will be on enumeration of combinatorial structure. Probability theory and complex analysis have various tools which help in analytic combinatorics. Analytic combinatorics is used to obtain the asymptotic formula. 3 Graph theory Graph theory can be considered as a part of combinatorics. In this, we will study about networks and graphs, but it is grown distinct enough and large enough with their problems, and it has its own right. In discrete mathematics, graph can be described as the prime objects of study. The most ubiquitous models of human-made and natural structure can be described by the Graph. Different types of relationships can be modeled by graphs. It is also able to process dynamics in the social, biological, and physical systems. Discrete probability theory In countable sample events, a lot of events will occur, and discrete probability theory is able to deal with these types of events. For example, suppose we are observing the number of birds in flocks for count observation. In this case, it will comprise only natural number values that are {0, 1, 2, 3}. In contrast, suppose we are observing the weight of birds for continuous observations. This case will comprise real number values, and the continuous probability distribution like normal will be used to model it.. 4 Number Theory In number theory, we will basically study the properties of numbers, especially integers. It contains several applications to linear and quadratic congruence, cryptanalysis, Diophantine equations, cryptography, prime number, primarily testing, cryptology, and particularly with regard to modular arithmetic. The geometry of numbers is included in other discrete aspects of number theory. Various techniques of continuous mathematics can also be used in the analytic number theory. We also have some topics of discrete objects that go beyond, and those topics include Diophantine approximation, transcendental numbers, and analysis and function fields. Computational geometry and Discrete geometry Combinatorial geometry and discrete geometry can be described as the combinatorial properties of geometrical object's discrete collections. In the case of discrete geometry, a long-standing topic is a tiling of the plane. All the geometrical problems can be solved by using the algorithms applied by computational geometry. Trees 5 A tree can be called an acyclic graph. A tree generally contains the non-empty finite set of elements which is known as nodes or vertices with the connected lines or edges between the nodes. The tree does not have multiple edges, simple circles, and loops. If we want to find the possible outcome of any experiment, the tree will be a good option to do this. Each node contains some minimum and maximum degrees. The minimum degree should be 1and the maximum degree can go upto n. The starting symbol of a tree is known as the root, and the root of a tree can't be null. Topology Topology can be described as the field of mathematics. It is used to contain subsets of topological space. Many discrete topics rise only because of using topology. We can provide the focus on topological invariants by doing their parts. The topologic invariants normally take discrete values that are finite topological space, topological graph theory, discrete topological space, combinatorial topology, topology (chemistry), computational topology, etc. BINARY OPERATION Definition: Binary operation is any rule of combination of any two elements of a given non empty set. The rule of combination of two elements of a set may give rise to another element which may or not belong to the set under consideration. It is usually denoted by symbols such as, *, Ө e.t.c. 6 Properties: A. Closure property: A non- empty set z is closed under a binary operation * if for all a, b € Z. Example; A binary operation * is defined on the set S= {0, 1, 2, 3, 4} by X*Y = x + y –xy. Find (a) 2 * 4 (b) 3* 1 (c) 0* 3. Is the set S closed under the operation *? Solution 2 * 4, i.e, x= 2,y=4 2+ 4 – (2×4) = 6-8 = -2. 3* 1 = 3+1-( 3x 1) = 4 – 3= 1 0*3 = 0 + 3 –( 0 x3) = 3 Since -2€ S, therefore the operation * is not closed in S. B. Commutative Property: If set S, a non empty set is closed under the binary operation *, for all a,b€ S. Then the operation * is commutative if a*b= b*a Therefore, a binary operation is commutative if the order of combination does not affect the result. Example; The operation * on the set R of real numbers is defined by: p*q= p3 + q3-3pq. Is the operation commutative? Solution p*q= p3 + q3 -3pq Commutative condition p*q= q*p To obtain q*p, use the same operation q*p, use the same operation p*q but replace p by q and q by p. Hence, q*p= p3+ q3 -3qp In conclusion p*q= q*p, the operation is commutative. C. Associative Property: If a non – empty set S is closed under a binary operation *, that is a*b €S. Then a binary operation is associative if (a*b) * c= a*(b*c) Such that C also belongs to S. Example: The operation Ө on the set Z of integers is defined by; a Ө b = 2a +3b -1. Determine whether or not the operation is associative in Z. Solution Introduce another element C Associative condition: (aӨb) Өc = a Ө (b Өc) (aӨb)Өc = (2a+ 3b- 1) Ө C = 2(2a +3b -1) + 3c -1 = 4a + 6b- 2+ 3c- 1 = 4a +6b+3c- 3. Also, the RHS, a Ө (b Ө c) = a Ө (2b+3c- 1) = 2a+ 3(2b +3c- 1) – 1 = 2a + 6b +9c -3 –1 a Ө (b Ө c) = 2a+ 6b+ 9c -4 Since, (a Ө b) Ө c ≠ a Ө (b Ө c), the operation is not associative in Z. Evaluation 1. An operation* defined on the set R of real numbers is x* y = 3x+ 2y- 1, x,y €R. Determine (a) 2*3 (b) -4* 5 (c) 1 * 1 3 2 7 is the operation closed. D. Distributive Property: If a set is closed under two or more binary operations (* Ө) for all a, b and c € S, such that: a*(bӨ c) = (a*b )Ө( a*c – Left distributive (BӨc) *a = (b*a) Ө(c*a) – Right distributive over the operation Ө Example: Given the set R of real numbers under the operations * and Ө defined by: a*b = a+ b- 3, aӨb= 5ab for all a, b € R. Does * distribute over Ө. Solution Let a, b,c € R a* ( bӨc) = (a*b) Ө (a*c) a* (bӨc) = a* (5ab) = a+ 5ab -3. (a*b) Ө (a*c) = (a+ b -3) Ө ( a+ c-3) = 5(a +b-3)(a +c -3) From the expansion, it’s obvious that, a* ( bӨc) ≠ (a*b) Ө (a*c) therefore * does not distribute over Ө. Evaluation: 1. A binary operation * is defined on the set R of real numbers by x*y= x +y + 3xy for all x, yɛR. determine whether or not * is: Commutative? Associative? General Evaluation 1. The operation * on the set R of real numbers is defined by: x * y = 3x + 2y – 1, x, yϵR. Determine (i) 2 * 3 (ii) 1/3 * ½ (iii) -4*5 2. The operation * on the set R, of real numbers is defined by; p*q = p3 + q3 – 3pq; p,q ϵR. Is the operation * commutative in R? Weekend Assignment 1. Two binary operation * and Ө are defined as m * n = mn – n -1 and m Ө n = mn + n -2 for al real number m n find the value of 3 Ө (4 * 5) (a) 60 (b) 57 (c) 54 (d) 42 If x * y = x + y –xy, find x, when (x*2) + (x*3) = 63 (a) 24 (b) 22 (c) -12 (d) -21 o A binary operation * is defined by a * b = ab. If a * 2 = 2 – a, find the possible values of a (a) 1, -1 (b) 1, 2 (c) 2, -2 (d) 1, -2 The binary operation * is defined on the set of integers p and q by p*q = pq + p + q. Find 2*(3*4) MAPPING AND FUNCTION Mapping or Functions: If A and B are two non-empty sets, then a relation ‘f‘ from set A to set B is said to be a function or mapping, If every element of set A is associated with unique element of set B. The function ‘f’ from A to B is denoted by f : A → B. If f is a function from A to B and x ∈ A, then f(x) ∈ B where f(x) is called the image of x under f and x is called the pre image of f(x) under ‘f’. Note: 8 For f to be a mapping from A to B: Every element of A must have image in B. Adjoining figure does not represent a mapping since the element d in set A is not associated with any element of set B. Function as a special kind of relation: Let us recall and review the function as a special kind of relation suppose, A and B are two non- empty sets, then a rule 'f' that associates each element of A with a unique element of B is called a function or a mapping from A to B. If 'f' is a mapping from A to B, we express it as f: A → B we read it as 'f' is a function from A to B. If ‘f ' is a function from A to B and x∈A and y∈B, then we say that y is the image of element x under the function ' f ' and denoted it by f(x). Relations A relation is a set of ordered pairs (x,y) where x and y are real numbers. “Ordered” pairs means that the order of the x and y coordinates matter, i.e. (3,4) is different to (4,3). Example of relations: The set of points (1,1),(1,5),(2,4),(3,3) forms a relation. The set of points satisfying the equation y=x−1 forms a relation. If we plot these points onto a graph, we get a straight line. The set of points satisfying the equation x2+y2=1 forms a relation. If we plot these points onto a graph, we get the unit circle. Classifying and Mapping Relations We can use an arrow diagram to represent the relation of mapping one set of points to another set of points. To do this, we list the x-coordinates into the first set X and the y-coordinates into the second set Y. Then we draw an arrow from xto y for each pair of (x,y). Consider the set of points (1,1),(1,5),(2,4),(3,3) from our previous example. We can visualise this relation in the arrow diagram below. Type of Mapping Arrow Diagram Description One-to-one Each element of set X is mapped to only one element of set Y Each element of set Y is mapped from at most one element of set X All elements in set X are mapped to at most one element in set Y. Many-to-one There exists an element in set Y which has more than one element mapped to it from set X. There exists an element in set X which is mapped to more than one element in One-to-many set Y All elements of set Y is mapped from at most one element of set X 9  There exists an element in set X which is mapped to more than one element in Many-to-many set Y. There exists an element in set Y which is mapped from more than one element of set X. This relation is known as a “one-to-many” relation since the first element of set X, 1, is mapped to more than one element in set Y, which are 1 and 5. There are four types of relation mapping which we describe in the table below: Functions A function is a set of ordered pair (x,y) where every pair has a unique x component. This means a function is a relation between two variables where each value of x has only one corresponding value for y. Hence, a function can be a “one-to-one” or “many-to-one” relation however, not all relations are functions. We can determine whether a relation is a function by drawing vertical lines on the graph of its curve. If there is only one point of intersection of a vertical line with the curve, then this verifies that there is only one y-value for every x-value. Hence, the curve is a function, otherwise the curve is not a function. This test is known as the vertical line test. Example: Let’s investigate the relations x2+y2 = 1 and y=x2−1 to determine whether they are functions. Solution: First, we can draw both curves as shown below. 10 Draw any vertical line, say x=0.5, through the graphs of the curves. The vertical line intersects the circle at two points whereas it will only intersect the parabola at one point. Therefore, we can say the circle x2+y2=1 is not a function and the parabola y=x2−1 is a function because there can only be one point of intersection for the vertical line test. Function Notation Now that we understand what functions are, we can use a special notation to represent them, called function notation. A function can be perceived as a machine that takes inputs and converts it into another form as an output. Consider the function from our previous example y=x2−1. We can interpret the function as a machine that inputs x values and converts it into outputs of y values. In our example, the machine will take in x-value, square it, and then subtract 1 from it. Using function notation, we can rewrite the equation of the curve as y=f(x)=x2−1 or simply f(x)=x2−1. For example, when x has a value of 2: So, when x=2,y=3 and by using function notation we can write this as f(2)=3. Discrete Probability Distribution Discrete probability distribution is a type of probability distribution that shows all possible values of a discrete random variable along with the associated probabilities. In other words, a 11  discrete probability distribution gives the likelihood of occurrence of each possible value of a discrete random variable. Geometric distributions, binomial distributions, and Bernoulli distributions are some commonly used discrete probability distributions. This article sheds light on the definition of a discrete probability distribution, its formulas, types, and various associated examples. What is Discrete Probability Distribution? A discrete probability distribution and a continuous probability distribution are two types of probability distributions that define discrete and continuous random variables respectively. A probability distribution can be defined as a function that describes all possible values of a random variable as well as the associated probabilities. Discrete Probability Distribution Definition A discrete probability distribution can be defined as a probability distribution giving the probability that a discrete random variable will have a specified value. Such a distribution will represent data that has a finite countable number of outcomes. There are two conditions that a discrete probability distribution must satisfy. These are given as follows: 0 ≤ P(X = x) ≤ 1. This implies that the probability of a discrete random variable, X, taking on an exact value, x, lies between 0 and 1. ∑P(X = x) =1. The sum of all probabilities must be equal to 1. Discrete Probability Distribution Example Suppose a fair dice is rolled and the discrete probability distribution has to be created. The possible outcomes are {1, 2, 3, 4, 5, 6}. Thus, the total number of outcomes will be 6. All numbers have a fair chance of turning up. This means that the probability of getting any one number is 1 / 6. Using this data the discrete probability distribution table for a dice roll can be given as follows: x 1 2 3 4 5 6 P(X = x)1 / 61 / 61 / 61 / 61 / 61 / 6 Discrete Probability Distribution Formula A discrete random variable is used to model a discrete probability distribution. There are two main functions associated with such a random variable. These are the probability mass function (pmf) and the probability distribution function or cumulative distribution function (CDF). Discrete Probability Distribution PMF 12 The probability mass function can be defined as a function that gives the probability of a discrete random variable, X, being exactly equal to some value, x. This function is required when creating a discrete probability distribution. The formula is given as follows: f(x) = P(X = x) Discrete Probability Distribution CDF The cumulative distribution function gives the probability that a discrete random variable will be lesser than or equal to a particular value. The value of the CDF can be calculated by using the discrete probability distribution. Its formula is given as follows: F(x) = P(X ≤ x) Discrete Probability Distribution Mean The mean of a discrete probability distribution gives the weighted average of all possible values of the discrete random variable. It is also known as the expected value. The formula for the mean of a discrete random variable is given as follows: E[X] = ∑x P(X = x) Discrete Probability Distribution Variance The discrete probability distribution variance gives the dispersion of the distribution about the mean. It can be defined as the average of the squared differences of the distribution from the mean, μ. The formula is given below: Var[X] = ∑(x - μ )2 P(X = x) Discrete Probability Distribution Types A discrete probability distribution is used in a Monte Carlo simulation to find the probabilities of different outcomes. The most commonly used types of discrete probability distributions are given below. Bernoulli Distribution A Bernoulli distribution is a type of a discrete probability distribution where the random variable can either be equal to 0 (failure) or be equal to 1 (success). The probability of getting a success is p and that of a failure is 1 - p. It is denoted as X ∼ Bernoulli (p). The pmf is expressed as follows: 13 P(X = x) = {p,ifx=11−p,ifx=0 Binomial Distribution A binomial distribution is a discrete probability distribution that gives the success probability in n Bernoulli trials. The probability of getting a success is given by p. It is represented as X ∼Binomial(n, p). The pmf is given as follows: P(X = x) = (nx)px(1−p)n−x Geometric Distribution A geometric distribution is another type of discrete probability distribution that represents the probability of getting a number of successive failures till the first success is obtained. It is given by X ∼G(p). The formula for the pmf is given as follows: P(X = x) = (1 - p)x p, where p is the success probability of the trial. Poisson Distribution Poisson distribution is a discrete probability distribution that is widely used in the field of finance. It gives the probability that a given number of events will take place within a fixed time period. The notation is written as X ∼Pois(λ ), where λ>0. The pmf is given by the following formula: P(X = x) = λxe−λx! How To Find Discrete Probability Distribution? A discrete probability distribution can be represented either in the form of a table or with the help of a graph. To find a discrete probability distribution the probability mass function is required. In other words, to construct a discrete probability distribution, all the values of the discrete random variable and the probabilities associated with them are required. Suppose a fair coin is tossed twice. Say, the discrete probability distribution has to be determined for the number of heads that are observed. The steps are as follows: Step 1: Determine the sample space of the experiment. When a fair coin is tossed twice the sample space is {HH, HT, TH, TT}. Here, H denotes a head and T represents a tail. Thus, the total number of outcomes is 4. Step 2: Define a discrete random variable, X. For the example let X be the number of heads observed. 14  Step 3: Identify the possible values that the variable can assume. There are 3 possible values of X. These are 0 (no head is observed), 1 (exactly one head is observed), and 2 (the coin lands on heads twice). Step 4: Calculate the probability associated with each outcome. In the given example, the probability can be calculated by the formula, number of favorable outcomes / total number of possible outcomes. Step 5: To get the discrete probability distribution represent the probabilities and the corresponding outcomes in tabular form or in graphical form. This is expressed as follows: x 0 {TT} 1 {HT, TH}2 {HH} P(X = x)1 / 4 = 0.252 / 4 = 0.5 1 / 4 = 0.25 A histogram can be used to represent the discrete probability distribution for this example. Important Notes on Discrete Probability Distribution A discrete probability distribution is used to model the outcomes of a discrete random variable as well as the associated probabilities. A discrete distribution is used to calculate the probability that a random variable will be exactly equal to some value. 0 ≤ P(X = x) ≤ 1 and ∑P(X = x) =1 are two conditions that must be satisfied by a discrete probability distribution. The examples of a discrete probability distribution are Bernoulli Distribution, binomial distribution, Poisson distribution, and geometric distribution. Examples on Discrete Probability Distribution 1. Example 1: Suppose a pair of fair dice are rolled. Let X be the random variable representing the sum of the dice. Construct a discrete probability distribution for the same. Solution: The sample space for rolling 2 dice is given as follows: 15 Thus, the total number of outcomes is 36. The possible values of X range between 2 to 12. X = 2 means that the sum of the dice is 2. This can happen only when (1, 1) is obtained. Hence, P(X = 2) = 1 / 36. Using a similar process, the discrete probability distribution can be represented as follows: x 2 3 4 5 6 7 8 9 10 11 12 P(X = x) 1 / 36 2 / 36 3 / 36 4 / 36 5 / 36 6 / 36 5 / 36 4 / 36 3 / 36 2 / 36 1 / 36 The graph of the discrete probability distribution is given as follows 2. Example 2: Given a discrete probability distribution, find the value of k. x 1 2 34 16  P(X = x)0.20.5k0.1 3. Solution: For a discrete probability distribution, ∑P(X = x) =1. By using this we get, 0.2 + 0.5 + k + 0.1 = 1 k + 0.8 = 1 k = 1 - 0.8 = 0.2 Answer: k = 0.2 4. Example 3: Find the expected value of the given discrete probability distribution. x 0 1 2 3 4 P(X = x)0.440.360.150.040.01 5. Solution: The formula for the expected value of a discrete probability distribution is E[X] = ∑x P(X = x) E[X] = (0)(0.44) +(1)(0.36) + (2)(0.15) + (3)(0.04) + (4)(0.01) = 0.82 Answer: E[X] = 0.82 MATRICES Matrices is a plural form of a matrix, which is a rectangular array or a table where numbers or elements are arranged in rows and columns. They can have any number of columns and rows. Different operations can be performed on matrices such as addition, scalar multiplication, multiplication, transposition, etc. There are certain rules to be followed while performing these matrix operations like they can be added or subtracted if only they have the same number of rows and columns whereas they can be multiplied if only columns in first and rows in second are exactly the same. Let us understand the different types of matrices and these rules in detail. Scalars, Vectors and Matrices In Physical Science 17 In Computing A scalar is a number, like 3, -5, 0.368, etc, A matrix having only one row and one column is called a scalar. Example The matrix A vector is a list of numbers (can be in a row or column), A matrix is an array of numbers (one or more rows, one or more columns). In fact a vector is also a matrix! Because a matrix can have just one row or one column. What are Matrices? 18 Matrices, the plural form of a matrix, are the arrangements of numbers, variables, symbols, or expressions in a rectangular table that contains various numbers of rows and columns. They are rectangular-shaped arrays, for which different operations like addition, multiplication, and transposition are defined. The numbers or entries in the matrix are known as its elements. Horizontal entries of matrices are called rows and vertical entries are known as columns. Matrix Definition A matrix is a rectangular array of numbers, variables, symbols, or expressions that are defined for the operations like subtraction, addition, and multiplications. The size of a matrix (which is known as the order of the matrix) is determined by the number of rows and columns in the matrix. The order of a matrix with 6 rows and 4 columns is represented as a 6 × 4 and is read as 6 by 4. For example, the given matrix B is a 3 × 4 matrix and is written as [B]3×4 : Notation of Matrices If a matrix has m rows and n columns, then it will have m × n elements. A matrix is represented by the uppercase letter, in this case, 'A', and the elements in the matrix are represented by the lower case letter and two subscripts representing the position of the element in the number of row and column in the same order, in this case, 'aij ', where i is the number of rows, and j is the number of columns. For example, in the given matrix A, element in the 3rd row and 2nd column would be a32 , can be verified in the matrix given below: 19 Calculate Matrices We can solve matrices by performing operations on them like addition, subtraction, multiplication, and so on. Calculating matrices depends upon the number of rows and columns. For addition and subtraction, the number of rows and columns must be the same whereas, for multiplication, number of columns in the first and the number of rows in the second matrix must be equal. The basic operations that can be performed on matrices are: Addition of Matrices Subtraction of Matrices Scalar Multiplication Multiplication of Matrices Transpose of Matrices Addition of Matrices The addition of matrices can only be possible if the number of rows and columns of both the matrices are the same. While adding 2 matrices, we add the corresponding elments. i.e., (A + B) = [aij ] + [bij] = [aij + bij], where i and j are the number of rows and columns respectively. For example Subtraction of Matrices Matrices subtraction is also possible only if the number of rows and columns of both the matrices are the same. While subtracting 2 matrices, we subtract the corresponding elements. i.e., (A - B) = [aij ] - [bij] = [aij - bij], where i and j are the row number and column number respectively. For example: 20 Scalar Multiplication The product of a matrix A with any number 'c' is obtained by multiplying every entry of the matrix A by c, is called scalar multiplication. i.e., (cA)ij = c(Aij) Properties of scalar multiplication in matrices The different properties of matrices for scalar multiplication of any scalars K and l, with matrices A and B are given as, K(A + B) = KA + KB (K + l)A = KA + lA (Kl)A = K(lA) = l(KA) (-K)A = -(KA) = K(-A) 1·A = A (-1)A = -A Multiplication of Matrices Matrices multiplication is defined only if the number of columns in the first matrix and rows in the second matrix are equal. To understand how matrices are multiplied, let us first consider a row vector R=[r1 r2...rn] Now, we will discuss matrix multiplication. It will soon become evident that to multiply 2 matrices A and B and to find AB, the number of columns in A should equal the number of rows in B. 21 Let A be of order m × n and B be of order n × p. The matrix AB will be of order m × p and will be obtained by multiplying each row vector of A successively with column vectors in B. Let us understand this using a concrete example: To obtain the element a11 of AB, we multiply R1 of A with C1 of B : To obtain the element a12 of AB, we multiply R1 of A with C2 of B: To obtain the element a21 of AB, we multiply R2 of A with C1 of B: 22 Proceeding this way, we obtain all the elements of AB. Let us generalize this: if A is or order m × n, and B of order n × p, then to obtain the element aij in AB, we multiply Ri in A with Cj in B: Properties of Matrix Multiplication There are different properties associated with the multiplication of matrices. For any three matrices A, B, and C: AB ≠ BA A(BC) = (AB)C A(B + C) = AB + AC (A + B)C = AC + BC AIm = A = AIn, for identity matrices Im  and In.  Am×nOn×p = Om×p , where O is a null matrix. Transpose of Matrix The transpose of a matrix is done when we replace the rows of a matrix to the columns and columns to the rows. Interchanging of rows and columns is known as the transpose of matrices. In the matrix given below, we have row elements as row-1: 2, -3, -4, and row-2: -1, 23  7, -7. On transposing, we will get the elements in column-1: 2, -3, -4, and column-2: -1, 7, -7, we can check that in the image given below: Properties of transposition in matrices There are various properties associated with transposition. For matrices A and B, given as, (AT)T = A (A + B)T = AT + BT, A and B being of the same order. (KA)T= KAT, K is any scalar(real or complex). (AB)T= BTAT, A and B being conformable for the product AB. (This is also called reversal law.) Apart from these operations, we have several other operations on matrices like finding its trace, determinant, minors and cofactors, adjoint, inverse, etc. Let us learn each of these in detail in the upcoming sections. Trace of a Matrix The trace of any matrix A, Tr(A) is defined as the sum of its diagonal elements. Some properties of trace of matrices are, tr(AB) = tr(BA) tr(A) = tr(AT) tr(cA) = c tr(A), for a scalar 'c' tr(A + B) = tr(A) + tr(B) Determinant of Matrices The determinant of a matrix is a number defined only for square matrices. It is used in the analysis of linear equations and their solution. The determinant formula helps calculate the determinant of a matrix using the elements of the matrix. Determinant of a matrix is equal to the summation of the product of the elements of a particular row or column with their respective cofactors. Determinant of a matrix A is denoted as |A|. Let say we want to find the determinant of the matrix 24 Minor of Matrix Minor for a particular element in the matrices is defined as the determinant of the matrix that is obtained when the row and column of the matrix in which that particular element lies are deleted, and the minor of the element aij is denoted as Mij. For example, for the given matrix, Cofactor of Matrix Cofactor of an element in the matrix A is obtained when the minor Mij of the matrix is multiplied with (-1)i+j. The cofactor of a matrix is denoted as Cij. If the minor of a matrix is Mij , then the cofactor of the matrix would be: 25 Note: Be extra cautious about the negative sign while calculating the cofactor of the matrix. Adjoint of Matrices The adjoint of matrices is calculated by finding the transpose of the cofactors of the elements of the given matrices. To find the adjoint of a matrix, we have to calculate the cofactors of the elements of the matrix and then transpose the cofactor matrix to get the adjoint of the given matrix. The adjoint of matrix A is denoted by adj(A). Let us understand Inverse of Matrices The inverse of any matrix is denoted as the matrix raised to the power (-1), i.e. for any matrix "A", the inverse matrix is denoted as A-1. The inverse of a square matrix, A is A-1 only when: A × A-1 = A-1 × A = I. There is a possibility that sometimes the inverse of a matrix does not exist if the determinant of the matrix is equal to zero(|A| = 0). The inverse of a matrix is shown by A-1. Matrices inverse is calculated by using the following formula: A-1 = (1/|A|)(Adj A) where |A| is the determinant of the matrix A and |A| ≠ 0. Adj A is the adjoint of the given matrix A. 26 Types of Matrices There are various types of matrices based on the number of elements and the arrangement of elements in them. Row matrix: A row matrix is a matrix having a single row is called a row matrix. Example: [1, −2, 4]. Column matrix: A column matrix is a matrix having a single column is called a column matrix. Example: [−1, 2, 5]T. Square matrix: A matrix having equal number of rows and columns is called a square matrix. For example: Rectangular Matrix: A matrix having unequal number of rows and columns is called a rectangular matrix. For example: 27 Diagonal matrices: A matrix with all non-diagonal elements to be zeros is known as a diagonal matrix. Example: Identity matrices: A diagonal matrix having all the diagonal elements equal to 1 is called an identity matrix. Example: Symmetric and skew-symmetric matrices: Symmetric matrices: A square matrix D of size n×n is considered to be symmetric if and only if DT= D. For example, D= Skew-symmetric matrices-A square matrix F of size n×n is considered to be skew-symmetric if and only if FT= - F. Invertible Matrix: Any square matrix A is called invertible matrix, if there exists another matrix B, such that, AB = BA = In 28 , where In is an identity matrix with n × n. Orthogonal Matrix: Any square matrix A is orthogonal if its transpose is equal to its inverse. i.e., AT = A-1 Solving a System of Equations Using Matrices While solving the system of equations using matrices, we have three matrices A, B, and X where A is known as the coefficient matrix, B is known as the constant matrix, and X contains all the variables of the equations which is known as a variable matrix. Matrix A is of the order m × n, while B is the column matrix of the order m × 1. The product of matrix A and matrix X results in matrix B; hence, X is a column matrix as well of the order n × 1. The matrices are arranged as: A X=B Let's understand how to solve a system of equations using matrices with the help of an example. We have a set of two equations as given below. The equations are: x + y = 8 2x + 3y = 10 Arrange all the coefficients, variables, and constants in the matrix in such a way that whenever we find the product of the matrices, the result obtained must result in the equation. Then the matrix equation is, AX = B where: To solve the equations, we need to find matrix X. It can be found by multiplying the inverse of matrix A with B, which is given as X=(A−1)B. To find the determinant of matrix A, we will follow the below steps: 29 Hence, |A| = 3 - 2 = 1 ∵ |A|≠0 , it is possible to find the inverse of matrix A. Now, by using the formula for finding the inverse of 2x2 matrix (which is mentioned in previous sections), Rank of a Matrix The rank of a matrix A is defined as the maximum number of linearly independent row(or column) vectors of the matrix. That means the rank of a matrix will always be less than or equal to the number of its rows or columns. The rank of a null matrix is zero since it has no independent row or column vectors. Eigen Values and Eigen Vectors of Matrices If A is any square matrix of order 'n', a matrix of A - λI can be formed, where I is a unit matrix of order n, such that the number λ, called the eigenvalue and a non-zero vector v, called the eigenvector, satisfy the equation, Av = λv. λ is an eigenvalue of an n×n-matrix A if and only if A − λIn is not invertible, which is equivalent to Det(A - λI) = 0. Matrices Formulas There are different formulas associated with matrix operations depending upon the type of matrix. Some of the matrices formulas are listed below: A(adj A) = (adj A) A = | A | In 30  | adj A | = | A |n-1 adj (adj A) = | A |n-2 A | adj (adj A) | = | A |(n-1)^2 adj (AB) = (adj B) (adj A) adj (Am) = (adj A)m, adj (kA) = kn-1 (adj A) , k ∈ R adj(In) = In adj 0 = 0 A is symmetric ⇒ (adj A) is also symmetric. A is diagonal ⇒ (adj A) is also diagonal. A is triangular ⇒adj A is also triangular. A is singular⇒| adj A | = 0 A-1 = (1/|A|) adj A (AB)-1 = B-1A-1 Important Notes on Matrices: Cofactor of the matrix A is obtained when the minor Mij of the matrix is multiplied with (-1)i+j. Matrices are rectangular-shaped arrays. The inverse of matrices is calculated by using the given formula: A-1 = (1/|A|)(adj A). The inverse of a matrix exists if and only if |A| ≠ 0. Solved Examples on Matrices 31 BOOLEAN ALGEBRA 32  Boolean algebra is algebra for the manipulation of objects that can take on only two values, typically true and false. It is common to interpret the digital value 0 as false and the digital value 1 as true. Boolean Expressions Boolean Expression: Combining the variables and operation yields Boolean expressions. Boolean Function: A Boolean function typically has one or more input values and yields a result, based on these input value, in the range {0, 1}. A Boolean operator can be completely described using a table that list inputs, all possible values for these inputs, and the resulting values of the operation. A truth table shows the relationship, in tabular form, between the input values and the result of a specific Boolean operator or function on the input variables. The AND operator is also known as a Boolean product. The Boolean expression xy is equivalent to the expression x * y and is read “x and y.” The behavior of this operator is characterized by the truth table shown in the Table. Truth Table for AND The OR operator is often referred to as a Boolean sum. The expression x+y is read “x or y”. The truth table for OR is shown in the Table The Truth Table OR 33 Both x and x’ are read as “NOT x.” The truth table for NOT is shown in Table. The Truth Table for NOT The rule of precedence for Boolean operators give NOT top priority, followed by AND, and then OR. The Truth Table for F(x, y, z) = x + y’z Boolean Algebra You have seen logic gates and how they can operate on binary numbers. Now, we need a mathematical framework for describing the relationship between logic gates and binary numbers. That framework is Boolean Algebra. This document of course provides only an introduction to Boolean algebra, refer to dedicated texts for a detailed discussion of the subject.The English mathematician George Boole (1815-1864) sought to give symbolic form to Aristotle's system of logic. Boole wrote a treatise on the subject in 1854, titled An Investigation of the Laws of Thought, on Which Are Founded the Mathematical Theories of Logic and Probabilities, which codified several rules of relationship between mathematical 34  quantities limited to one of two possible values: true or false, 1 or 0. His mathematical system became known as Boolean algebra. All arithmetic operations performed with Boolean quantities have but one of two possible outcomes: either 1 or 0. There is no such thing as "2" or "-1" or "1/2" in the Boolean world. It is a world in which all other possibilities are invalid by fiat. As one might guess, this is not the kind of math you want to use when balancing a checkbook or calculating current through a resistor. However, Claude Shannon of MIT fame recognized how Boolean algebra could be applied to on-and-off circuits, where all signals are characterized as either "high" (1) or "low" (0). His 1938 thesis, titled A Symbolic Analysis of Relay and Switching Circuits, put Boole's theoretical work to use in a way Boole never could have imagined, giving us a powerful mathematical tool for designing and analyzing digital circuits. In this section, you will find a lot of similarities between Boolean algebra and "normal" algebra, the kind of algebra involving so-called real numbers. Just bear in mind that the system of numbers defining Boolean algebra is severely limited in terms of scope, and that there can only be one of two possible values for any Boolean variable: 1 or 0. Consequently, the "Laws" of Boolean algebra often differ from the "Laws" of real-number algebra, making possible such statements as 1 + 1 = 1, which would normally be considered absurd. Once you comprehend the premise of all quantities in Boolean algebra being limited to the two possibilities of 1 and 0, and the general philosophical principle of Laws depending on quantitative definitions, the "nonsense" of Boolean algebra disappears. a. Boolean Arithmetic Let us begin our exploration of Boolean algebra by adding numbers together: The first three sums make perfect sense to anyone familiar with elementary addition. The last sum, though, is quite possibly responsible for more confusion than any other single statement in digital electronics, because it seems to run contrary to the basic principles of mathematics. Well, 35 itdoes contradict principles of addition for real numbers, but not for Boolean numbers. Remember that in the world of Boolean algebra, there are only two possible values for any quantity and for any arithmetic operation: 1 or 0. There is no such thing as "2" within the scope of Boolean values. Since the sum "1 + 1" certainly isn't 0, it must be 1 by process of elimination. It does not matter how many or few terms we add together, either. Consider the following sums: Take a close look at the two-term sums in the first set of equations. Does that pattern look familiar to you? It should! It is the same pattern of 1's and 0's as seen in the truth table for an OR gate. In other words, Boolean addition corresponds to the logical function of an "OR" gate, as shown in figure 10 below. Figure 10.Boolean addition and the OR gate There is no such thing as subtraction in the realm of Boolean mathematics. Subtraction implies the existence of negative numbers: 5 - 3 is the same thing as 5 + (-3), and in Boolean algebra negative quantities are forbidden. There is no such thing as division in Boolean mathematics, either, since division is really nothing more than compounded subtraction, in the same way that 36 multiplication is compounded addition. Multiplication is valid in Boolean algebra, and thankfully it is the same as in real-number algebra: anything multiplied by 0 is 0, and anything multiplied by 1 remains unchanged: This set of equations should also look familiar to you: it is the same pattern found in the truth table for an AND gate. In other words, Boolean multiplication corresponds to the logical function of an "AND" gate. Like "normal" algebra, Boolean algebra uses alphabetical letters to denote variables. Unlike "normal" algebra, though, Boolean variables are always UPPERCASE letters, never lower-case. Because they are allowed to possess only one of two possible values, either 1 or 0, each and every variable has a complement: the opposite of its value. For example, if variable "A" has a value of 0, then the complement of A has a value of 1. Boolean notation uses a bar above the variable character to denote complementation, like this. In written form, the complement of "A" denoted as "A-not" or "A-bar". Sometimes a "prime" symbol is used to represent complementation (A’). Boolean complementation finds equivalency in the form of the NOT gate. The basic definition of Boolean quantities has led to the simple rules of addition and multiplication, and has excluded both subtraction and division as valid arithmetic operations. We have symbols for denoting Boolean variables, and their complements. In the next section we will proceed to develop Boolean identities. b. Boolean Algebraic Identities In mathematics, an identity is a statement true for all possible values of its variable or variables. 37 The algebraic identity of x + 0 = x tells us that anything (x) added to zero equals the original "anything," no matter what value that "anything" (x) may be. Like ordinary algebra, Boolean algebra has its own unique identities based on the bivalent states of Boolean variables. I just list the identities here, for detailed descriptions refer to. If A is a Boolean variables, figure 11 below shows the basic Boolean algebraic identities. Figure 11.Basic Boolean algebraic identities c. Boolean Algebraic Properties Another type of mathematical identity, called a "property" or a "law," describes how differing variables relate to each other in a system of numbers. Assuming A and B are Boolean numbers, figure 12 lists the Boolean algebraic properties. Figure 12.Basic Boolean algebraic properties of additive association, multiplicative association and distribution d. Translating truth tables into Boolean expressions In designing digital circuits, the designer often begins with a truth table describing what the circuit should do. The design task is largely to determine what type of circuit will perform the function described in the truth table. While some people seem to have a natural ability to look at a truth table and immediately envision the necessary logic gate or relay logic circuitry for the task, there are procedural techniques available for the rest of us. Here, Boolean 38  algebra proves its utility in a most dramatic way. As an example let us take a look at the exclusive-OR (XOR) gate. Figure 8 is repeated below as figure 13 for convenience. Figure 13.XOR gate schematic symbol and truth table revisited It is not necessarily obvious what kind of logic circuit would satisfy the truth table. However, a simple method for designing such a circuit is found in a standard form of Boolean expression called the Sum-Of-Products, or SOP, form. As you might suspect, a Sum-Of-Products Boolean expression is literally a set of Boolean terms added (summed) together, each term being a multiplicative (product) combination of Boolean variables. An example of an SOP expression would be something like this: ABC + BC + DF, the sum of products "ABC," "BC," and "DF." Sum-Of-Products expressions are easy to generate from truth tables. All we have to do is examine the truth table for any rows where the output is "high" (1), and write a Boolean product term that would equal a value of 1 given those input conditions. In figure 13, rows 2 and 3 have output high. The product term corresponding to row 2 would be A’B since the term would have a value of 1 if and only if A = 0 and B = 1. Similarly, the product term corresponding to row 3 would be AB’. Now, we join our Boolean products together by addition to create a single Boolean expression for the truth table as a whole. The Δ is the symbol for XOR. A ⊕B = A'B + AB' Now, we can easily translate the right hand-side of the equation above into a circuit, refer to figure 14. Figure 14.Simplified gate-level schematic of XOR 39 An alternative to generating a Sum-Of-Products expression to account for all the "high" (1) output conditions in the truth table is to generate a Product-Of-Sums, or POS, expression, to account for all the "low" (0) output conditions instead. For the XOR gate above, a POS expression is (A’ + B’).(A + B). Both the Sum-Of-Products and Products-Of-Sums standard Boolean forms are powerful tools when applied to truth tables. They allow us to derive a Boolean expression -- and ultimately, an actual logic circuit -- from nothing but a truth table, which is a written specification for what we want a logic circuit to do. To be able to go from a written specification to an actual circuit using simple, deterministic procedures means that it is possible to automate the design process for a digital circuit. In other words, a computer could be programmed to design a custom logic circuit from a truth table specification! The steps to take from a truth table to the final circuit are so unambiguous and direct that it requires little, if any, creativity or other original thought to execute them. e. Boolean Rules for Simplification Boolean algebra finds its most practical use in the simplification of logic circuits. If we apply certain algebraic rules to a Boolean equation resulting from a truth table, we will get a simpler equation. The simplified equation may be translated into circuit form for a logic circuit performing the same function with fewer components. If equivalent function may be achieved with fewer components, the result will be increased reliability and decreased cost of manufacture. A few of the Boolean rules for simplification are shown below. Figure 15.Useful Boolean rules for simplification Proving the rules above requires the use of concepts learned in sections 5 (a), (b) and (c). I prove the first two below and leave the third as an exercise. 40 A + AB = A.(1 + B) [Distributive property] =A A + A’B = (A + AB) + A’B [From rule above: A = A+B] = A + (AB + A’B) [Additive association property] = A + B.(A + A’) [Distributive property] =A+B Now, we will encapsulate what we learned about the binary number systems, logic gates and Boolean algebra by designing a few common building blocks of digital systems. Boolean Identities Boolean expression can be simplified, but we need new identities, or laws, that apply to Boolean algebra instead of regular algebra. Basic Identities of Boolean Algebra DeMorgan’s law provides an easy way of finding the complement of a Boolean function. 41  Truth Tables for the AND Form of DeMorgan’s Law Simplification of Boolean Expressions Example using Identities Complements Truth Table Representation for a Function and Its Complement Representing Boolean Functions 42 In fact, there are an infinite number of Boolean expressions that are logically equivalent to one another. Two expressions that can be represented by the same truth table are considered logically equivalent. EXAMPLE The two most common standardized forms are the sum-of-products form and the product-of- sums form. In the sum-of-products form, ANDed variables are ORed together. For example, In the product-of-sums form, ORed variables are ANDed together. For example, The sum-of-products form is usually easier to work with and to simplify, so we use this form exclusively in the sections that follow. It is easy to convert a function to sum-of-products form using its truth table. We are interested in the values of the variables that make the function true (=1). Using the truth table, we list the values of the variables that result in a true function value. Each group of variables is then ORed together. EXAMPLE 43 Truth Table Representation for the Majority Function sum-of-products: F(x, y, z) = x’yz + xy’z + xyz’ + xyz. Decimal Number System The number system that we use in our day-to-day life is the decimal number system. Decimal number system has base 10 as it uses 10 digits from 0 to 9. In decimal number system, the successive positions to the left of the decimal point represent units, tens, hundreds, thousands, and so on. Each position represents a specific power of the base (10). For example, the decimal number 1234 consists of the digit 4 in the units position, 3 in the tens position, 2 in the hundreds position, and 1 in the thousands position. Its value can be written as (1 x 1000)+ (2 x 100)+ (3 x 10)+ (4 x l) (1 x 103)+ (2 x 102)+ (3 x 101)+ (4 x l00) 1000 + 200 + 30 + 4 1234 As a computer programmer or an IT professional, you should understand the following number systems which are frequently used in computers. S.No. Number System and Description 1 Binary Number System Base 2. Digits used : 0, 1 2 Octal Number System Base 8. Digits used : 0 to 7 3 Hexa Decimal Number System Base 16. Digits used: 0 to 9, Letters used : A- F Binary Number System Characteristics of the binary number system are as follows − Uses two digits, 0 and 1 Also called as base 2 number system Each position in a binary number represents a 0 power of the base (2). Example 20 Last position in a binary number represents a x power of the base (2). Example 2x where x represents the last position - 1. Example Binary Number: 101012 44  Step Binary Number Decimal Number Step 1 101012 ((1 x 24) + (0 x 23) + (1 x 22) + (0 x 21) + (1 x 20))10 Step 2 101012 (16 + 0 + 4 + 0 + 1)10 Step 3 101012 2110 Calculating Decimal Equivalent − Note − 101012 is normally written as 10101. Binary Number System The easiest way to vary instructions through electric signals is two-state system – on and off. On is represented as 1 and off as 0, though 0 is not actually no signal but signal at a lower voltage. The number system having just these two digits – 0 and 1 – is called binary number system. Each binary digit is also called a bit. Binary number system is also positional value system, where each digit has a value expressed in powers of 2, as displayed here. In any binary number, the rightmost digit is called least significant bit (LSB) and leftmost digit is called most significant bit (MSB). And decimal equivalent of this number is sum of product of each digit with its positional value. 110102 = 1×24 + 1×23 + 0×22 + 1×21 + 0×20 = 16 + 8 + 0 + 2 + 0 = 2610 Computer memory is measured in terms of how many bits it can store. Here is a chart for memory capacity conversion. 1 byte (B) = 8 bits 45  1 Kilobytes (KB) = 1024 bytes 1 Megabyte (MB) = 1024 KB 1 Gigabyte (GB) = 1024 MB 1 Terabyte (TB) = 1024 GB 1 Exabyte (EB) = 1024 PB 1 Zettabyte = 1024 EB 1 Yottabyte (YB) = 1024 ZB Number System Relationship The following table depicts the relationship between decimal, binary, octal and hexadecimal number systems. HEXADECIMAL DECIMAL OCTAL BINARY 0 0 0 0000 1 1 1 0001 2 2 2 0010 3 3 3 0011 4 4 4 0100 5 5 5 0101 6 6 6 0110 7 7 7 0111 8 8 10 1000 9 9 11 1001 A 10 12 1010 46 B 11 13 1011 C 12 14 1100 D 13 15 1101 E 14 16 1110 F 15 17 1111 Logic Gates We see that Boolean functions are implemented in digital computer circuits called gates. A gate is an electronic device that produces a result based on two or more input values. o In reality, gates consist of one to six transistors, but digital designers think of them as a single unit. o Integrated circuits contain collections of gates suited to a particular purpose. Symbols for Logic Gates The three simplest gates are the AND, OR, and NOT gates. The Three Basic Gates Another very useful gate is the exclusive OR (XOR) gate. The output of the XOR operation is true only when the values of the inputs differ. 47  The exclusive OR (XOR) Gate Universal Gates Two other common gates are NAND and NOR, which produce complementary output to AND and OR. The Truth Table and Logic Symbols for NAND and NOR Gates NAND and NOR are known as universal gates because they are inexpensive to manufacture and any Boolean function can be constructed using only NAND or only NOR gates. Three Circuits Constructed Using Only NAND Gates 48 Multiple Input Gates Gates can have multiple inputs and more than one output. Digital Components Every computer is built using collections of gates that are all connected by way of wires acting as signal gateway. Digital Circuits and Their Relationship to Boolean Algebra More complex Boolean expressions can be represented as combinations of AND, OR, and NOT gates, resulting in a logic diagram that describes the entire expression. A Logic Diagram for F(x, y, z) = x + y’z Integrated Circuits Gates are not sold individually; they are sold in units called integrated circuits (ICs). A chip (a small silicon semiconductor crystal) is a small electronic device consisting of the necessary electronic components (transistors, resistors, and capacitors) to implement various gates. The first IC were called SSI chips and contained up to 100 electronic components per chip. We now have ULSI (ultra large-scale integration) with more than 1 million electronic components per chip. 49  A simple SSI Integrated Circuit Putting It All Together: From Problem Description to Circuit Boolean logic is used to solve practical problems. Expressed in terms of Boolean logic practical problems can be expressed by truth tables. Truth tables can be readily rendered into Boolean logic circuits. Example 3.10 o Suppose we are to design a logic circuit to determine the best time to plant a garden. We consider three factors (inputs): (1) Time, where 0 represents day and 1 represents evening; (2) Moon phase, where 0 represents not full and 1 represents full; and (3) Temperature, where 0 represents 45°F and below, and 1 represents over 45°F. We determine that the best time to plant a garden is during the evening with a full moon. 50 o This results in the following truth table: A Boolean Matrix Question Given a boolean matrix mat[M][N] of size M X N, modify it such that if a matrix cell mat[i][j] is 1 (or true) then make all the cells of ith row and jth column as 1. Examples: Input: {{1, 0}, {0, 0}} Output: {{1, 1} {1, 0}} Input: {{0, 0, 0} {0, 0, 1}} Output: {{0, 0, 1} {1, 1, 1}} Input: {{1, 0, 0, 1},{0, 0, 1, 0},{0, 0, 0, 0}} Output: {{1, 1, 1, 1} {1, 1, 1, 1},{1, 0, 1, 1}} Solve Problem Follow the steps below to solve the problem 51  Create two temporary arrays row[M] and col[N]. Initialize all values of row[] and col[] as 0. Traverse the input matrix mat[M][N]. If you see an entry mat[i][j] as true, then mark row[i] and col[j] as true. Traverse the input matrix mat[M][N] again. For each entry mat[i][j], check the values of row[i] and col[j]. If any of the two values (row[i] or col[j]) is true, then mark mat[i][j] as true. Below is the implementation of the above approach: / C++ Code For A Boolean Matrix Question #include using namespace std; #define R 3 #define C 4 void modifyMatrix(bool mat[R][C]) { bool row[R]; bool col[C]; int i, j; for (i = 0; i < R; i++) row[i] = 0; for (i = 0; i < C; i++) col[i] = 0; // Store the rows and columns to be marked as // 1 in row[] and col[] arrays respectively for (i = 0; i < R; i++) { for (j = 0; j < C; j++) { if (mat[i][j] == 1) { row[i] = 1; col[j] = 1; } } } // Modify the input matrix mat[] using the // above constructed row[] and col[] arrays for (i = 0; i < R; i++) for (j = 0; j < C; j++) 52  if (row[i] == 1 || col[j] == 1) mat[i][j] = 1; * A utility function to print a 2D matrix */ void printMatrix(bool mat[R][C]) { int i, j; for (i = 0; i < R; i++) { for (j = 0; j < C; j++) cout