3.5 Lesson: Boolean functions

• After completing this lesson you should be able to solve for a Boolean expression that matches a given input/output table.
• One way to define a Boolean function is to provide an input/output table that shows the output value of the function for every possible combination of input values

• A literal is a Boolean variable or the complement of a Boolean variable (for example, x or x). In a Boolean function whose input variables are v₁, v₂,…,v_k, a minterm is a product of literals u₁u₂…u_k such that each u_j is either v_j or v_j. Each of the variables appearing in a literal is one of the input variables and each input variable appears in one of the literals.

• Become familiar with the following new vocabulary:
  • Literal = a single Boolean variable or its complement; for example, x¯ and x.
  • Minterm = the product of literals; for example, x¯yz
• To find a Boolean expression that is equivalent to a Boolean function defined by an input/output table:
  • Each row of a table defining a Boolean function corresponds to a minterm.
  • Find each row where the value of f=1.
  • Write the expression for each row whose minterm equals 1.
  • Put an addition operator (+) between each expression.

3.6 Module 11: Normal Forms and Functional Completeness

• Conjunction and disjunctive normal forms
• Evaluating Boolean functions for completeness
• Solving Boolean functions with NAND and NOR

3.7 Lesson: Conjunctive and disjunctive normal forms

• After completing this lesson you should be able to determine the equivalent CNF/DNF expression from an input/output table for a Boolean function.
• Disjunctive normal form
• A Boolean expression that is a sum of products of literals is said to be in disjunctive normal form (abbreviated as DNF). 

• Conjunctive normal form
• A Boolean expression that is a product of sums of literals is said to be in conjunctive normal form (abbreviated as CNF). When logic is used to express a set of constraints in a computational problem, the result is often a CNF expression.

• The rules for disjunctive normal form DNF (the sum of products of literals):
  • Complements are applied to only single variables: x¯y¯+w is okay; xy¯+w is not allowed.
  • No addition within a term: xy¯+xz+w is okay; x¯(y¯+z)+w is not allowed.
• The rules for conjunctive normal form CNF (the product of sums of literals):
  • Complements are applied to only single variables: x¯+y¯ is okay; x+y¯ is not allowed.
  • No multiplication within a factor: (x+y¯+z) is okay; (xy¯+y+z) is not allowed.
  • The factors in a CNF expression can be single literals.
• The answer to the question posed in the introduction is DNF. The expression: f(x,y,z)=x¯yz+x+y¯z¯+xy¯z is in the DNF form.

3.8 Lesson: Functional completeness

• After completing this lesson you should be able to evaluate a Boolean function for completeness.

• Functional completeness
• A set of operations is functionally complete if any Boolean function can be expressed using only operations from the set. 
• The definition of functional completeness for a set of Boolean operations is based on the premise that any Boolean expression can be written using only the operations within the set. For example, the set of addition, multiplication, and complement operations is functionally complete because any Boolean expression can be written using only those three operations.
• The set of multiplication and complement operations is also functionally complete, with significant help from De Morgan’s laws. Any Boolean expression can be written using only the multiplication and complement operations.
• The set of addition and complement operations is functionally complete.
• Use these steps to rewrite a Boolean expression into a more efficient form using only multiplication and complement operations:Create an input/output table for the function.
• Find a DNF expression that is equivalent to the function
• Repeatedly apply De Morgan’s law to eliminate each addition operation
• Use these steps to rewrite a Boolean expression into a more efficient form using only addition and complement operations:Create an input-output table for the function
• Find a CNF expression that is equivalent to the function
• Repeatedly apply De Morgan’s law to eliminate each multiplication operation

3.9 Lesson: Boolean functions: NAND and NOR

• After completing this lesson you should be able to solve a given Boolean expression for an equivalent Boolean expression using NAND or NOR.
• Two functionally complete logical operations
• The NAND operation (which stands for “not and”) is denoted by the symbol ↑. The expression x ↑ y is equivalent to xy. The NOR operation (which stands for “not or”) is denoted by the symbol ↓. The expression x ↓ y is equivalent to x + y.

• NAND is the logical equivalent of “NOT AND” xy¯, and is denoted by x↑y.
• NOR is the logical equivalent of “NOT OR,” x+y¯, and is denoted by x↓y.
• The NAND and NOR operations are each functionally complete on their own.

3.10 Module 12: Boolean Satisfiability, Gates, and Circuits

• Boolean satisfiability
• Digital logic: circuits and gates
• Boolean expression for circuits
• Minimization of circuits

3.11 Lesson: Boolean satisfiability

• Boolean satisfiability, SAT, is an important process in computer science. SAT essentially means there exists at least one combination of input values for the variables in a Boolean function which result in a function output value of 1
• After completing this lesson you should be able to construct a Boolean expression that is satisfiable (i.e., evaluates to numeral one) from a given problem.
• Satisfiable and unsatisfiable expressions
• The Boolean satisfiability problem (called SAT for short) takes a Boolean expression as input and asks whether it is possible to set the values of the variables so that the expression evaluates to 1.
• If there is a way to set the input variables that causes a Boolean expression to evaluate to 1, then the expression is said to be satisfiable. Otherwise, the expression is unsatisfiable.
• Boolean satisfiability (SAT) means there is at least one possible set of input values for a Boolean expression which creates an output value of 1. Otherwise, the expression is unsatisfiable.
• You must use trial and error, as well as all your logic skills and understanding of Boolean operations, to determine satisfiability.
• In this lesson you should focus on the concept of satisfiability rather than proving it.

3.12 Lesson: Digital logic: Circuits and gates

• Boolean expressions are ultimately used to create efficient computer circuits. Circuits are composed of gates. Each gate receives a Boolean input value and through physical electrical pathways, produces a Boolean output value. I
• After completing this lesson you should be able to examine circuit and gate diagrams.
• The basic gates
• Circuits are built from electrical devices called gates. 
• The AND gate computes Boolean multiplication, the OR gate computes Boolean addition, and the inverter computes the complement. 

• The NAND gate computes the NAND operation x↑y. The gate outputs 0 if all inputs are 1 and outputs 1 otherwise.

• There are three basic gates which correspond to Boolean operations: AND, OR, inverter.
• A circuit is a series of connected gates producing a single Boolean value as output.
• Use the Boolean operations indicated by the gates in a circuit diagram to determine an output value from a specific set of input values.

3.13 Lesson: Boolean expressions for circuits

• After completing this lesson you should be able to determine an equivalent Boolean expression for each circuit.
• Describing a function using a circuit
•  In a combinatorial circuit the output of the circuit depends only on the present combination of input values and not on the state of a circuit.
• Steps in the circuit design process
• this section is only informational and is provided to help you visualize the concept. Refer back if interested or necessary
• Use these steps to create a Boolean expression from a circuit diagram:Begin working from the left side of the diagram assigning variables to the input wires.
• Follow each wire path through a gate, write the output as an expression using the input variables.
• Continue following wire-paths, carefully writing each output/input expression for each gate until you reach the final output wire.
• At this point, you will have created the Boolean expression equivalent to the circuit.

3.14 Lesson: Minimization of circuits

• After completing this lesson you should be able to minimize a circuit using the laws of Boolean algebra and the steps in the circuit design process.
• Purpose of circuit minimization
•  Circuit minimization is the simplification of a Boolean expression before converting to a circuit to yield a smaller circuit

• Simplifying a sum-of-products expression
• Simplification by applying the complement law
• Simplification by replicating a term
• Follow these steps to minimize a circuit using the laws of Boolean algebra:Interpret the digital circuit gates and input/output wires.
• Build an input/output table for all possible values for the input variables.
• Construct a Boolean expression from the input/output table using methods learned in previous lessons.
• Simplify the Boolean expression using the laws of Boolean algebra.

4.1 Unit 4: Matrix Operations

• Types of matrices
• Matrix addition and multiplication
• Inverse matrices
• Elementary matrix operations
• Gaussian elimination and invertibility

4.2 Module 13: Matrix Addition and Multiplication

• Types of matrices
• Matrix addition and scalar multiplication
• Matrix multiplication
• Matrix multiplication properties

4.3 Lesson: Types of matrices

• After completing this lesson you should be able to categorize the types of matrices
• Matrix notation and terminology
• A matrix is a rectangular array of numbers or expressions arranged in columns and rows. 
• The size of a matrix is given by m×n where m is the number of rows and n is the number of columns.
• A column matrix is composed of a single column.
• The size of a column matrix has the form m×1. A row matrix is composed of a single row. The size of a row matrix has the form 1×n.

A diagonal entry aij of matrix A is an entry where i=j. The main diagonal of A consists of all diagonal entries.

A zero matrix is a matrix in which all entries are 0. A zero matrix may be of any size appropriate to the context.

A square matrix has an equal number of rows and columns. The size of a square matrix is n×n.

A diagonal matrix is a square matrix in which all non-diagonal entries are 0.

An identity matrix I is a diagonal matrix in which all of the entries along the main diagonal are 1 and all other entries are 0. The identity

• The transpose of a matrix A, written AT, is the matrix that has as columns the rows of A. Thus, if A is an m×n matrix, AT is an n×m matrix.

• A matrix is a rectangular array of objects. If a matrix has m rows and n columns, it is said to be an (m x n) matrix.
• Single entries of a matrix are described by their location in the matrix. The entry aij refers to the entry that is in the ith row and the jth column.
• A square matrix is one where the number of rows equals the number of columns (m = n). The entries in a square matrix where i = j are called diagonal entries.
• The list of all diagonal entries in a matrix is called the main diagonal.
• A matrix whose entries are all zeros is called a zero matrix. It may be of any size.
• If a square matrix has zeros in every non-diagonal entry, it is called a diagonal matrix. Note, a square zero matrix is also a diagonal matrix.
• A square diagonal matrix whose diagonal entries are all ones is called an identity matrix.
• You can transpose a matrix so that the columns in one matrix are the rows and columns in the transposed matrix. The transposed matrix of matrix A is denoted AT . For example, the columns of matrix A are the rows in AT, and the the rows in matrix A are the columns in AT

4.4 Lesson: Matrix addition and scalar multiplication

• After completing this lesson you should be able to perform matrix addition and scalar multiplication.

• Matrix addition and subtraction
• Scalar multiplication
• To distinguish between an ordinary real number and a matrix, the term scalar refers to a real number, like 3, −5.1, or π.
• A scalar multiple of a matrix is a matrix in which each entry is multiplied by a scalar.
• Properties of matrix addition and scalar multiplication

• Two matrices can be added (or subtracted) if they are the same size (same number of rows and columns) by adding or subtracting each corresponding entry.
• If r is a number, called a scalar, and A is a matrix, then rA is the matrix obtained by multiplying every entry in A by the scalar r. The result is called a scalar multiple of A.
• Review these important properties (rules) of matrix addition and scalar multiplication

4.5 Lesson: Matrix multiplication

• After completing this lesson you should be able to perform matrix multiplication.
• Matrix multiplication
• For matrix multiplication, an m×n matrix A can only be multiplied by an n×p matrix B to yield an m×p matrix AB. If the number of columns in A is not equal to the number of rows in B, then the product AB is undefined. 

• The procedure for matrix multiplication
• Matrices are multiplied using the row-column rule. If the product AB is defined, the entry in row i, column j of AB is the sum of the products of corresponding entries of row i of A and column j of B. In other words, the entry in row i, column j of AB is the dot product of row i of A and the transpose of column j of B.
• The identity in matrix multiplication
• An n×n identity matrix, denoted I is a matrix with 1’s along the diagonal and 0’s as all other entries. 

• To get the ij-entry of the product of two matrices, denoted (AB)ij , multiply the ith row of A with The jth column of B. This is called the row-column rule.
• Matrices do not have to be the same size to be multiplied, but their inner dimensions must match. For example, an (m x n) matrix must be multiplied to an (n x p) matrix. The size of the product will be (m x p). If their inner dimensions are not the same, then AB is undefined.
• Matrix multiplication is not commutative, AB ≠ BA
• Similar in concept to set identities, the identify matrix is a square matrix where all the elements of the principal diagonal are ones and all other elements are zeros. The identity matrix is denoted In .
• If you multiply a matrix by an identity matrix the given matrix remains unchanged. For example, m x n matrix A multiplied by In yields A.

4.6 Lesson: Matrix multiplication properties

• After completing this lesson you should be able to evaluate properties of matrix multiplication.
• Properties of matrix multiplication

• Economic applications of matrix multiplication.

• In matrix multiplication the order in which two matrices are multiplied matters. Therefore, the commutative property of multiplication does not apply.
• Review the following properties of matrix multiplication:

4.7 Module 14: Gaussian Elimination and Matrix Inversion

• Introduction to inverse matrices
• Determining the existence of an inverse matrix
• Representing equations as a matrix
• Linear equations using an inverse matrix
• Elementary matrix operations
• Gaussian elimination
• Elementary matrices and invertibility

4.8 Lesson: Inverse matrix: Introduction

• In algebra classes you learned to solve a linear equation by “undoing” certain operations.- You solved these problems by applying the inverse operations to the equation.
• After completing this lesson you should be able to calculate the inverse of a 2 x 2 matrix.
• The inverse of a matrix
• Given a square matrix A, the matrix A−1 is called the inverse of matrix A if A⋅A−1=A−1⋅A=I. Only square matrices can have an inverse. 
• An invertible matrix (or nonsingular matrix) is a square matrix that has an inverse. A singular matrix is a square matrix that does not have an inverse.
• The inverse of a 2×2 matrix

Now that you have completed this lesson you should be able to calculate the inverse of a 2×2 matrix. Take a moment to think about what you’ve learned in this lesson:

• Only square matrices can have an inverse, but NOT ALL square matrices can have an inverse.
  • A square matrix that has an inverse is called nonsingular.
  • A square matrix that does not have an inverse is called singular.
• Given a square matrix, A, the inverse of A, denoted A−1 is a square matrix with the property that AA−1=A−1A=In.
• The determinant of a matrix helps to find the inverse of a matrix. The determinant is denoted with two vertical lines on either side. For example |A| is the determinant of the matrix A.
• Given 2×2 matrix A[abcd], to find the inverse matrix (A−1)
  1. Find the determinant of A. Multiply ad and subtract cb. The equation is: |A|=ad−bc.
     • If det(A)≠0, then A−1 exists. Proceed to the next step.
     • If det(A)=0, then A−1 does not exist. Stop the process.
  2. Obtain a modified matrix. Modify the matrix by switching the diagonal entries and changing the sign of the other two entries. For example, [d−b−ca].
  3. Multiply the reciprocal of the determinant of A to the modified 2×2 matrix. For example, if the determinant of A is 2 (2/1) the reciprocal of 2 is 1/2. Multiply 1/2 by [d−b−ca] to find the inverse of[abcd].

4.9 Lesson: Inverse matrix: Properties

• After completing this lesson you should be able to evaluate whether a matrix is an inverse from a given matrix and a possible inverse.
• Properties of inverse matrices

• Not all matrices are invertible; i.e., the inverse of an (n x n) matrix does not exist.
• To determine if the matrix is invertible apply the following properties of invertible 2 x 2 matrices:
  • If matrix A is nonsingular (has an inverse), then A−1is unique.
  • Any matrix that has a zero row or a zero column is singular (does not have an inverse matrix).
  • A square matrix A is nonsingular (has an inverse) if det(A) ≠ 0.
  • A square matrix A is singular (does not have an inverse) if det(A) = 0.
  • If A is nonsingular (has an inverse) then kA is nonsingular for any nonzero scalar k.
  • If A and B are nonsingular (have an inverse) and of the same size then AB is invertible and (AB)−1 = B−1 A−1.

4.10 Lesson: Representing equations as a matrix

• After completing this lesson you should be able to construct a given set of linear equations as matrix equations and vice versa.
• the coefficient matrix is

where aij is the coefficient of the xj from the ith equation for i=1,…,m and j=1,…,n.

An augmented matrix is formed when two matrices are combined. Augmented matrices are useful when solving a system of linear equations. The augmented matrix for the system above consists of the coefficient matrix and the column matrix formed by the constants on the right-hand side of each equation, and is written as

• Representing a system of linear equations as a matrix equation

• The matrix equation is a way to represent a system of equations.
  • The matrix A is called the coefficient matrix because it consists of the coefficients of the equations.
  • The variable vector is x.
  • The constant vector is b.a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2⋮am1x1+am2x2+…+amnxn=bn

• To represent linear equations with a matrix equation, follow these steps:
  • To create the coefficient matrix, use the coefficients of each equation to create the rows of the coefficient matrix. For example, a11 , a12 , …. 1n make up the first row. The coefficients a21, a22 , … a2n make up the second row.
  • To create the column x vector, place the variables from the equations and in the same order to create the x column. For example, (x1 , x2) make up the vector x column.
  • To create the column constant vector (column b), place the results of each equation in order in the b column. For example, (b1 , b2) make up the b column.

• To create linear equations from the matrix equation use the dot product. For a refresher on dot product matrix multiplication see the “Matrix Multiplication” in the previous module.