Discrete Mathematics in FE Electrical and Computer

Have you ever wondered how your phone can process complex algorithms in the blink of an eye? Or how your laptop can sort through massive amounts of data with ease? The answer lies in the world of Discrete Mathematics – a powerful tool Electrical & Computer Engineers use to solve complex problems and design cutting-edge technology.

Let me take you on a journey to discover the fascinating world of Discrete Mathematics and its crucial role in shaping the modern world, from the earliest computer designs to the most advanced artificial intelligence systems. The Importance of discrete mathematics in electrical and computer engineering makes it crucial to uncover discrete mathematics applications from a career standpoint.

In this blog, we’ll explore the critical concepts of Discrete Mathematics in FE Electrical and Computer and their application in real-world engineering applications. You’ll learn how graph theory can help engineers design efficient networks, how boolean algebra plays a vital role in digital logic design, and how combinatorics is used in coding theory to ensure the security of sensitive information.

So, whether you’re an aspiring engineer or simply curious about the inner workings of modern technology, join me as we discuss Discrete Mathematics in FE Electrical and Computer. An explore how this seemingly abstract branch of mathematics can be used to create the technological wonders we rely on daily.

Logic and Boolean Algebra

Boolean Algebra is at the forefront of the subject when discussing discrete mathematics for computer science. Below are some of the widely used and crucial discrete mathematics topics you must prepare from all angles.

Propositional logic and truth tables

Propositional logic in mathematics deals with propositions or statements that are either true or false. In propositional logic, we use variables to represent propositions and logical operators such as NOT, AND, and OR to construct compound propositions.

In Boolean algebra, we use the same logical operators as propositional logic to construct logical expressions representing functions that take binary inputs (0/1 or True/False) and output a binary value. The variables in Boolean algebra can represent any logical proposition, and we use symbols such as A, B, C, ¬A, ¬B, and ¬C to denote the variables and their negations.

The three fundamental gates in Boolean algebra are the NOT gate, the AND gate, and the OR gate. The NOT gate is represented by a bar over a variable (e.g., ¬A), which outputs the opposite value of the input (i.e. 1 to 0 or True to False and vice versa). The AND gate is represented by a dot (∨ with the Addition function) and outputs a 1 if both inputs are True. The OR gate is represented by a plus sign (∧ with the Multiplication function) and outputs a 1 if either input is True.

To solve a Boolean algebra equation with three variables, we can create a truth table that lists all possible combinations of input values and the corresponding output values. Each row in the truth table represents a unique combination of input values, and the last column represents the function output for that input combination.

Here’s an example Boolean algebra equation with three variables written in symbolic form:

F = (A ∧ ¬B ∧  ¬C) ∨ (¬A ∧ B ∧ ¬C) ∨ (A ∧ B ∧ C)

Using this equation, we can create a truth table that lists all possible combinations of input values for A, B, and C, and the resulting output value of the function F.

Below is the resulting truth table:

Logical equivalences and inference rules

Logical equivalences and inference rules are fundamental concepts in discrete mathematics that help us reason about logical propositions and their relationships.

Logical equivalences are statements true for all possible values of their variables. They can be expressed using symbols such as ↔ or ≡ to indicate that two expressions are logically equivalent. Some common logical equivalences include:

Identity laws

A ∧ T ≡ A, A ∨ F ≡ A

Domination laws

A ∨ T ≡ T, A ∧ F ≡ F

Double negation

¬(¬A) ≡ A

De Morgan’s laws

(A ∧ B) ≡ A ∨ B

(A ∨ B) ≡ A ∧ B

OR

¬(A ∧ B) ≡ ¬A ∨ ¬B

¬(A ∨ B) ≡ ¬A ∧ ¬B

Distributive laws

A ∧ (B ∨ C) ≡ (A ∧ B) ∨ (A ∧ C), AND over OR

A ∨ (B ∧ C) ≡ (A ∨ B) ∧ (A ∨ C), OR over AND

Where “≡” shows congruency or equivalency. Inference rules are used to derive new logical propositions from existing ones based on the logical structure of the propositions. Some standard inference rules include:

Modus ponens

If A → B, and A is true, then B is true.

Modus tollens

If A → B, and ¬B is true, then ¬A is true.

Disjunctive syllogism

If A ∨ B, and ¬A is true, then B is true.

Conjunction

If A and B are true, then A ∧ B is true.

Simplification

If A ∧ B is true, then A and B are both true.

For example, using the distributive law, we can show that the following two expressions are logically equivalent:

A ∧ (B ∨ C) ≡ (A ∧ B) ∨ (A ∧ C)

To prove this, we can use a truth table or apply the distributive law to both sides of the equation and simplify the resulting expression:

For instance,

For Distributive Law of OR over AND:

A ∨ (B ∧ C) ⇔ (A ∨ B) ∧ (A ∨ C)

Distributive Law of AND over OR

A ∧ (B ∨ C) ⇔ (A ∧ B) ∨ (A ∧ C)

Another example of an inference rule is the modus ponens. If we have the following two propositions:

A → B

A

We can use the modus ponens to infer that B is true. This is because if A implies B, and A is true, then we can conclude that B must also be true.

One typical example of “A implies B” in daily life is the conditional scenario, “If it rains, then the ground gets wet.” In this case, A is the proposition “it rains,” and B is the proposition “the ground gets wet.”

In general, “A implies B” means that if A is true, then B must also be true. It expresses a cause-and-effect relationship between two propositions, where the truth of A is necessary for the truth of B.

Boolean algebra and its properties

Boolean Algebra is a branch that deals with binary variables and logical operations. Its properties make it useful for digital logic design and analysis. Here are some of the critical properties and logical equivalencies used in Boolean Algebra:

Commutative laws

The order of operands does not affect the result of an operation. For example, A ∨ B = B ∨ A and A ∧ B = B ∧ A.

Associative laws

The result of an operation is independent of the order of operands. For example, (A ∨ B) ∨ C = A ∨ (B ∨ C) and (A ∧ B) ∧ C = A ∧ (B ∧ C).

Distributive laws

The distributive laws relate the two basic binary operators (AND and OR). For example, A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C) and A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C).

Identity laws

These laws state that if a variable is combined with a particular identity element, the result is that variable. For example, A ∧ T = A and A ∨ F = A.

Where T means True or 1, and F means False or 0.

Complement laws

Every variable has a complement, which is the opposite of its value. For example, ¬A represents the complement of A.

Absorption laws

The absorption laws state that the result of a Boolean operation will always be one of the operands. For example, A ∨ (A ∧ B) = A and A ∧ (A ∨ B) = A.

De Morgan’s laws

The same as we studied above. These properties of Boolean Algebra can be used to simplify and manipulate Boolean expressions, which are used in digital logic circuits and computer programming. By applying these laws, complex Boolean expressions can be reduced to simpler forms, making them easier to analyze and understand.

Simplification of Boolean expressions

Apart from the above rules, some other rules can be used to simplify Boolean algebra equations, like

• ¬(¬A) = A
• A ∧ A = A and A ∨ A = A
• A ∧ ¬A = 0
• A ∨ ¬A = 1

What is the purpose and Importance of discrete mathematics in electrical and computer engineering? Are you going to use it any time in the future? Of course yes. For instance, consider the example below to discover how boolean algebra can be used to design logical circuits using logic gates. It showcases the use of the AND and OR gates to create a more complex logic function and how the resulting truth table can be used to verify the correctness of the circuit design.

Suppose we want the output F to be 1 if A and B are both 1, OR if C is 1. Otherwise, the output should be 0. This can be implemented using an OR gate and an AND gate.

The boolean equation for the output F can be written as

F = (A ∧ B)  ∨ C

We can represent this circuit using the following logic gate diagram:

 In this circuit, the AND gate takes input from A and B, while the OR gate takes input from the output of the AND gate and the input C. The output of the OR gate is the final output F.

We can create a truth table to show the possible combinations of input values and the resulting output values as follows:

In this truth table, each row represents a possible combination of input values for A, B, and C. The output F is evaluated based on the inputs and the boolean equation for F and is recorded in the final column. You can use an LED on output signal F to test the truth table in real life circuit. When it’s ON it means the output is 1 and if it remains off it means the output is 0. This is the perfect and real-life example of discrete mathematics in computer science.

Sets, Relations, and Functions

Another eminent domain in Discrete Mathematics in FE Electrical and Computer is Sets, Relations, and Functions, which everyone has studied in secondary schooling. But here we will discuss in the context of applications of discrete mathematics in electrical and computer engineering. In computer science, set theory is used to design and optimize data structures and algorithms.

Similarly, functions and relations define relations in different objects, classes, and libraries in modern languages like Python, R, and JAVA. Electrical engineering also relies heavily on the mathematics of sets, relations, and functions, where engineers use these concepts to design circuits and define the state of a switch or diode. Let’s crack these concepts one by one.

Set operations and set identities

Set operations are used to manipulate and compare sets. The common set operations are union, intersection, difference, and complement. Set identities are mathematical statements that are always true for any set, regardless of their elements. Some common set identities include the commutative property, associative property, and distributive property.

Some main set operations in sets for sets A = {1, 2, 3} and B = {2, 3, 4}, include:

Union

A ∪ B = {1, 2, 3, 4}

Intersection

A ∩ B = {2, 3}

Difference

A – B = {1}

Complement

A’ = U – A

Where U is the Universal set containing all elements that other sets contain with additional elements.

Moreover, the commutative property, associative property, distributive property, and De Morgan laws in sets are the same as boolean algebra, where changing the grouping of operands in a logical operation does not impact the result.

Commutative property

A ∪ B = B ∪ A

A ∩ B = B ∩ A

Associative property

(A ∪ B) ∪ C = A ∪ (B ∪ C)

(A ∩ B) ∩ C = A ∩ (B ∩ C)

Distributive property

A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

It shows that, commutative, associative, and distributive properties of sets are similar to their counterparts in boolean algebra because both sets and boolean values have two binary operations (union/intersection and logical OR/AND, respectively).

Relations and their properties

Relations are used to describe how elements from one set are linked to elements of another set. There are different types of relations, including reflexive, symmetric, transitive, and antisymmetric.

Suppose we have a set A = {1, 2, 3} and a relation R on A defined as {(1,2), (2,3)}.

Reflexive

R is reflexive if for every x in A, (x,x) is in R. However, in this case, for the elements 1, 2, and 3, (1,1), (2,2), and (3,3) are not in R, therefore, R is not reflexive.

Symmetric

R is symmetric if for every (x,y) in R, (y,x) is also in R. In this case, (1,2) is in R, but (2,1) is not in R. Similarly, (2,3) is in R, but (3,2) is not in R. Therefore, R is not symmetric.

Transitive

R is transitive if for every (x,y) and (y,z) in R, (x,z) is also in R. In this case, (1,2) and (2,3) are in R, but (1,3) is not in R. Therefore, R is not transitive.

Antisymmetric

R is antisymmetric if for every (x,y) and (y,x) in R, x = y. In this case, (1,2) is in R, but (2,1) is not in R. Therefore, R is antisymmetric.

Functions and their properties

Functions are used to describe how elements from one set are mapped to elements in another set. A function can be represented as a set of ordered pairs, where each input element maps to a unique output element. Some common properties of functions include injectivity, surjectivity, and bijectivity.

Consider you two sets: A = {1, 2, 3} and B = {4, 5, 6, 7, 8}. We define a function h from A to B for any equation h(x).

h(1) = 4

h(2) = 5

h(3) = 7

Then, we can apply the concepts of injectivity, surjectivity, and bijectivity to this function as follows:

Injective

h is injective if each element in B is mapped to by at most one element in A. In this case, h is injective since each element in B is only mapped to a single element in A.

Surjective

h is surjective if each element in B is mapped to by at least one element in A. In this case, h is not surjective since the elements 6 and 8 in B are not mapped to by any element in A.

Bijective

h is bijective if it is both injective and surjective. In this case, h is not bijective since it fails to satisfy the surjective condition.

Conclusion

Now you have a rich idea about the Importance of discrete mathematics in electrical and computer engineering. This interesting area of study plays a crucial role in the development of modern technology and its impact on our lives. Applications of discrete mathematics range from digital signal processing and communication systems to computer networking and cryptography.

With the increasing demand for faster and more efficient computational systems, we can expect to see further advancements in the field of Discrete Mathematics and graph theory, such as the development of new algorithms for machine learning and AI, which will continue to revolutionize the way we perceive and use technology.

Learn more about Combinatorics, Cryptography, and Graph Theory in FE Electrical & Computer, a specifically designed & comprehensive guide that further extends the subject of discrete Mathematics in FE Electrical and Computer.

Wasim Asghar – P.E, P.ENG, M.ENG

Licensed Professional Engineer in Texas (PE), Florida (PE) and Ontario (P. Eng) with consulting experience in design, commissioning and plant engineering for clients in Energy, Mining and Infrastructure.

• LinkedIn
• YouTube