Lecture Notes on Boolean Algebra (Part 1 of 3)

1. Review of Propositional Logic in ICS141

Refresh your memory about Propositional Logic.

In addition to propositional logic, it would be good to have basic knowledge of Abstract Algebra.

2. Boolean Algebra

Propositional logic discussed in ICS141 can be reinterpreted from a viewpoint of algebra as Boolean algebra that is an algebraic system on the set B = {0,1}. A logical statement (called a proposition) in propositional logic is regarded as an expression in Boolean algebra. Applications of inference rules to derive a theorem in logic are similar to transformations and/or manipulations of expressions in algebra. Thus, in Boolean algebra, we can manipulate logical statements as algebraic expressions systematically.

Many technical terms in propositional logic are also used in Boolean algebra though, there are some technical terms specific to Boolean algebra.

Propositional Logic	Boolean Algebra
propositional variable	Boolean variable
proposition	Boolean expression
negation	complement
logical equivalence	equality

etc.

Logical Connectives vs Boolean Operators

Propositional Logic		Boolean Algebra
Logical Connective	Notation	Boolean Operator	Notation
negation	¬	complement	‾
conjunction	∧	AND	⋅
disjunction	∨	OR	+

Analogy between Boolean Algebra and Arithmetics

	Boolean Algebra	Arithmetics
Domain	truth values	numbers (e.g., integers and real numbers)
Operands	truth values and/or Boolean variables	numbers and/or variables
Unary Operator	NOT (complement)	− (negative sign)
Binary Operators	AND (conjunction), OR (disjunction)	+ (addition), − (subtraction), × (multiplication), / (division)

Review 2.1 on Boolean Operators:

Give a definition of the Boolean operator called Exclusive OR (denoted by XOR or ⊕) such as x ⊕ y.
Hint: Construct the truth table of x ⊕ y.
Give a definition of the Boolean operator called NAND (denoted by a vertical bar | which is also called the Sheffer stroke) such as x | y.
Give a definition of the Boolean operator called NOR (denoted by ↓) such as x ↓ y.

Boolean Expressions

A proposition with n propositional variables in propositional logic is regarded as an expression (called a Boolean expression) in Boolean algebra.

Notations for Boolean Expressions

  0 denotes F (false).
  1 denotes T (true).
  p ⋅ q denotes p AND q (i.e., p ∧ q in propositional logic).
     [Note that a dot "⋅" is often omitted.]
  p + q denotes p OR q (i.e., p ∨ q in propositional logic).
  _
  p denotes NOT p (i.e., ¬ p in propositional logic).
     [This operator is called a "complement".]

Some textbooks (especially, in the field of Electrical Engineering) denote the complement of p by p’ (read as “p prime”).

By the traditional convention, it is assumed that an AND operator has a higher precedence than an OR operator if there are no parentheses for explicitly clarifying the order of the operators. For example, x + y ⋅ z is interpreted as x + (y ⋅ z) rather than (x + y) ⋅ z and x y z + a b c is interpreted as (x ⋅ y ⋅ z) + (a ⋅ b ⋅ c).

Example 2.1

      ___              _______
  p + q r denotes p + ( q ⋅ r ).
            ___                   _ _
  Note that q r is different from q r.
  The former denotes NOT(q AND r) while the latter denotes (NOT(q)) AND (NOT(r)).

Review 2.2 on Boolean Expressions: Express the following propositions in Boolean algebra.

¬ (p ∨ q) ∧ ¬ (¬ r ∨ (p ∧ ¬ q)) Hint?
(p ∧ ¬ q) → r Hint?
p ∧ q ⇔ ¬ (¬ p ∨ ¬ q) Hint?

Boolean Functions

A Boolean expression with n Boolean variables represents a function f : {0,1}ⁿ → {0,1} that is called an n-ary Boolean function (or n-place Boolean function). The integer n is called the arity (or degree) of the Boolean function. Note that there may be more than one Boolean expression representing the same Boolean function. Two Boolean expressions are said to be equivalent if their truth values are identical for every possible truth assignment to Boolean variables of the Boolean expressions. Since each Boolean function is uniquely defined by a truth table, it is common to use a truth table as the specification of a Boolean function. Thus, two Boolean expressions are equivalent iff their truth tables are identical.

Example 2.2

Threshold Function τ: Suppose that an unsigned binary integer is given by three bits x₁, x₂ and x₃ where x₁ is the most significant bit and x₃ is the least significant bit. Let k be a nonnegative integer. τ(x₁,x₂,x₃,k) = 1 iff the unsigned binary integer represented by x₁ x₂ x₃ is at least k.

x₁ x₂ x₃ τ for k = 5

0 0 0 0

0 0 1 0

0 1 0 0

0 1 1 0

1 0 0 0

1 0 1 1

1 1 0 1

1 1 1 1
Majority Function μ: Let x₁, x₂ and x₃ be input bits. Suppose that μ(x₁,x₂,x₃) = 1 iff the number of bits with 1 is 2 or more (i.e., the majority among the input bits).

x₁ x₂ x₃ μ

0 0 0 0

0 0 1 0

0 1 0 0

0 1 1 1

1 0 0 0

1 0 1 1

1 1 0 1

1 1 1 1

x₁	x₂	x₃	τ for k = 5
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	0
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

x₁	x₂	x₃	μ
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

Review 2.3 on Boolean Functions:

How many distinct n-ary Boolean functions are there? Hint?
Construct a truth table of the following 4-ary Boolean function.
```
       _ _         ____
  (w + x)y + x(y + (wz))
```

Determine whether the following Boolean expressions equivalent. Hint?

      _
  x + z
        _    _          _   _ _
  y(x + z) + y x + (x + x ) y z

Each equivalence or tautology in propositional logic corresponds to an identity or law in Boolean algebra. Important identities and laws are summarized in Algebraic Laws in Boolean Algebra regarding axioms and useful theorems in Boolean algebra.

Example 2.3

            _   _ _                   _ _
z x y + x y z + x y z = x y + z(x y + x y)

-----------------------------------------------------------------
Boolean Expression                  Identity or Law to Be Applied
-----------------------------------------------------------------
            _   _ _
z x y + x y z + x y z               Given LHS

            _   _ _
x y z + x y z + x y z               Commutativity

                    _   _ _
x y z + x y z + x y z + x y z       Idempotent Law

            _           _ _
x y z + x y z + x y z + x y z       Commutativity

         _            _ _
(xy)(z + z) + x y z + x y z         Distributivity

                _ _
(xy)1 + x y z + x y z               Complement Law

              _ _
x y + x y z + x y z                 Identity Law

              _ _
x y + z(xy) + x y z                 Commutativity

                _ _
x y + z(xy) + z(x y)                Commutativity

                _ _
x y + z((xy) + (x y))               Distributivity
-----------------------------------------------------------------

Example 2.4

_______
    ___   _
x + y z = x y z

-----------------------------------------------------------------
Boolean Expression                  Identity or Law to Be Applied
-----------------------------------------------------------------
_______
    ___
x + y z                             Given LHS

  ___
_ ___
x y z                               DeMorgan's Law

_
x y z                               Involution Law
-----------------------------------------------------------------

Example 2.5

_____________
          ___
_______     _     _
x + y z + x y = x y

-----------------------------------------------------------------
Boolean Expression                  Identity or Law to Be Applied
-----------------------------------------------------------------
_____________
          ___
_______     _
x + y z + x y                       Given LHS

           ___
 _______   ___
 _______     _
(x + y z) (x y)                     DeMorgan's Law

 _______
 _______     _
(x + y z) (x y)                     Involution Law

             _
(x + y z) (x y)                     Involution Law

   _
(x y) (x + y z)                     Commutativity

  _       _
x y x + x y y z                     Distributivity

  _
x y x + x 0 z                       Idempotent Law

  _
x y x + 0 z                         Null Law

  _
x y x + z 0                         Commutativity

  _
x y x + 0                           Null Law

  _
x y x                               Identity Law

    _
x x y                               Commutativity

  _
x y                                 Idempotent Law
-----------------------------------------------------------------

Review 2.4 on Transformation of Boolean Expressions by Identities and Laws:

Prove the equality x + y(x + z) = (x + y)(x + z) by showing literally step by step which identity or law is applied for transforming a Boolean expression.
Prove the following equality by showing literally step by step which identity or law is applied for transforming a Boolean expression.
```
        _    _          _   _ _       _
  y(x + z) + y x + (x + x ) y z = x + z
```
Prove the following equality by showing literally step by step which identity or law is applied for transforming a Boolean expression.
```
    _ _        _ _ _   _ _       _ _     _         _
x + y(x + z) = x y z + x y z + x y z + x y z + x y z + x y z
```

Duality

In the list of identities and laws (Algebraic Laws in Boolean Algebra) in Boolean algebra, they are paired so that every identity or law has its counterpart.

The dual of a Boolean expression is a Boolean expression constructed by interchanging all between AND and OR operators and between Boolean constants 0 and 1.

Example 2.5

x⋅(y+0) and x+(y⋅1) are dual to each other.
(x⋅1)+y+z and (x+0)yz are dual to each other.

By using the duality principle of Boolean algebra, an identity or law can logically be derived from another identity or law.

Review 2.5 on the Duality of Boolean Expressions:

Show how you construct the dual of the Boolean expression x(x + y).
Show how you construct the dual of the following Boolean expression.
```
          _ _ _
  x y z + x y z
```
Show how you construct the dual of the following Boolean expression.
```
    _   _
  x z + x ⋅ 1 + x ⋅ 0
```

3. Normal Forms

Terminology

A literal is either a Boolean variable or its complement.

A disjunctive normal form of a Boolean function f is a disjunction of conjunctions which represents f.

                                 _     _
Example 3.1:  f(w,x,y,z) = wy + xy + wyz + x

A minterm of an n-ary Boolean function is a conjunction of n literals such that each of n Boolean variables appears exactly once,
```
              _  _
Example 3.2:  wxyz for f(w,x,y,z)
```
A sum-of-products expansion (or canonical minterm representation) of an n-ary Boolean function f with Boolean variables x₁, x₂, … , x_n is a disjunction of minterms of f.
```
                           _  _    _       _
Example 3.3:  f(w,x,y,z) = wxyz + wxyz + wxyz
```
A clause is a disjunction of literals, e.g., (x + y + z).

A conjunctive normal form of a Boolean function f is a conjunction of clauses which represents f.

                                _         _       _
Example 3.4:  f(w,x,y,z) = (w + x)(y + z)(w + x + z)
              where f consists of 3 clauses

A maxterm of an n-ary Boolean function is a disjunction of n literals such that each of n Boolean variables appears exactly once,
```
              _           _
Example 3.5:  w + x + y + z for f(w,x,y,z)
```
A product-of-sums expansion (or canonical maxterm representation) of an n-ary Boolean function f with Boolean variables x₁, x₂, … , x_n is a conjunction of maxterms of f.
```
                           _           _      _
Example 3.6: f(w,x,y,z) = (w + x + y + z)(w + x + y + z)
```

Theorem 3.1: For every Boolean function f, there are disjunctive and conjunctive normal forms of f.

Construction of a Sum-of-Products Expansion

  Step 1:  Construct a truth table of a Boolean function f.
  Step 2:  For each combination of truth values of variables for which f is equal to 1,
           create a minterm so that the value 1 of a variable x corresponds to a literal x
                                                       _
           and the value 0 of x corresponds to literal x.
  Step 3:  Construct disjunction of all the minterms obtained at Step 2.

                           _______
                             _
  Example 3.7:  f(x,y,z) = ( x y ) (x + z)

	---------------------------------------------------------------
                                        _____
                                _        _
	x	y	z	x y	(x y)	x+z	f	minterm
	---------------------------------------------------------------
	0	0	0	0	1	0	0
								_ _
	0	0	1	0	1	1	1	x y z
	0	1	0	1	0	0	0
	0	1	1	1	0	1	0
								  _ _
	1	0	0	0	1	1	1	x y z
								  _
	1	0	1	0	1	1	1	x y z
								    _
	1	1	0	0	1	1	1	x y z
	1	1	1	0	1	1	1	x y z
	---------------------------------------------------------------
                 _ _       _ _     _         _
     f(x,y,z) =  x y z + x y z + x y z + x y z + x y z

Construction of a Product-of-Sums Expansion
This is dual to the above process for constructing a sum-of-products expansion.

  Step 1:  Construct a truth table of a Boolean function f.
  Step 2:  For each combination of truth values of variables for which f is equal to 0,
           create a maxterm so that the value 0 of a variable x corresponds to a literal x
                                                       _
           and the value 1 of x corresponds to literal x.
  Step 3:  Construct conjunction of all the maxterms obtained at Step 2.

The Boolean function in the above example is expressed as follows.

                                _             _   _
f(x,y,z) =  ( x + y + z ) ( x + y + z ) ( x + y + z )

Remark 3.1: Some textbooks (especially in the field of electrical engineering) use the following notation for specifying the sum-of-product expansion of a Boolean function,

f(x,y,z) = Σm(1,4,5,6,7)

where “Σm” indicates the sum of minterms and each nonnegative integer in a list denotes the binary representation of a row corresponding to a minterm. Similarly, the following specifies a Boolean function with minterms whose values are “don’t care”.

f(x,y,z) = Σm(1,4,5,7) + Σd(0,6)

4. Exercises

Prove or disprove the following equality by Boolean algebra.

              _     _       _ _   _       _ _     _ _ _       _
  x y z + x y z + x y z + x y z + x y z + x y z + x y z = x + y + z

Construct a truth table for the even parity bit e of three bits x₁, x₂ and x₃ and then derive a sum-of-products expansion of e, where the even parity bit e always makes the number of 1's in the 4 bits x₁, x₂, x₃ and e to be even.
For the Boolean expression x + y + z, show how to derive an equivalent Boolean expression whose Boolean operators are only AND (⋅) and complement.
Prove the following equality in Boolean algebra. Note that your proof must indecate which axiom, identity, equivalence or law is applied to each step in a transformation from the left-hand side to the right-hand side or vice versa.
x + (y ⋅ (x + z)) = (x + y) ⋅ (x + z)
Show how to convert x + y into its equivalent expression including only the NAND operator | in Boolean algebra.
By using only identities and laws of Boolean algebra in the lecture notes (you cannot use a truth table), prove x + (y(x + z)) = (x + y)(x + z). You must show the equivalence by presenting a step-by-step sequence of applications of the identities to Boolean expressions.

Show how you derive the sum-of-products expansion of the following Boolean function.

               _   _     _      _       _       _     _
f(x,y,z) = x ( y + y z + x ) + (x y + y z ) ( x y z + x z )

Prove or disprove the following equality.

        _     _           _   _ _       _
y ( x + z ) + y x + ( x + x ) y ̄z = x + z

Show how you construct an equivalent Boolean expression to the following in the disjunctive normal form.
```
    _   _
x + y ( x + z )
```
Suppose a threshold Boolean function f(x₁,x₂,x₃) = 1 iff the unsigned binary integer x₁ x₂ x₃ is at least 4 in decimal. Show how you derive the Boolean expression of f in the disjunctive normal form.
Show how you derive a Boolean expression using only AND and NOT operators that is equivalent to the following Boolean function.
```
    _   _
x + y ( x + z )
```
Hint: Apply DeMorgan's laws.

Show how you derive the sum-of-products expansion of the following Boolean function.

                      _   _
f(x,y,z) = ( x + y )( x + y + z )

More Exercises