Mathematical Foundation of Computer Science

DHARM

N-COM\APPENDIX.PM5

356 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

Theorem involving 2/3 variables can be proved algebraically by using the postulates and

the theorems proved above. Validity of the theorems T4 and T5 can be seen using truth table

similar to the table shown in Fig. A.3. Next we shall discuss the proof of the theorem T6.

(T6)LHS

x + x. y = x. 1 + x. y ∴ x. 1 = x P1

= x. (1 + y) ∴ x. y + x. z = x. (y + z) P4

= x. (y + 1) ∴ x + y = y + x P3

= x. 1 ∴ y + 1 = 1 T2

= x ∴ x. 1 = x P1

RHS Hence, proved.

(T6′)LHS

x. (x + y) = (x + 0). (x + y) ∴ x + 0 = x P1

= x + 0. y ∴ x + y. z = (x + y). (x + z) P4

= x + 0 ∴ 0. x = 0 T3

= x ∴ x + 0 = x P1

RHS Hence, proved.

Duality Theorem

Every algebraic expression is construe from the postulates of the Boolean algebra remains
valid if the both operators and identity elements are interchanged.
Principle of duality states that any Boolean expression remains true if AND, OR, 1, 0
are replaced by OR, AND, 0, 1 respectively. This principle reflects the obvious symmetry existing
among the operators and the Boolean variables that allows many concepts to exist in dual
form. For example, the pairs of the postulates listed in the table (Fig. A.4) are dual to each
other, one may be obtained from other if operator ‘+’ is interchange to ‘. ’ and replaces the
identity element from 1 to 0 and vice versa.

A.4 Boolean Functions...........................................................................................................

A Boolean function is a Boolean expression consisting of one/more variables, binary operators

(OR, AND) that are denoted by (+, .) respectively, unary operator (NOT) denoted by ( ′ ) and

parenthesis. Since, Boolean variables can take value either 0 or 1, so truth value of the function

is either 0 or 1 on each possible interpretation. The truth values of the Boolean function on

various combinations of truth values of Boolean variables are obtained using truth table. For

example, the truth values of following Boolean functions are shown in truth table in Fig. A.5.

(i)F 1 = x y z

(ii)F 2 = x. y + y′. z

(iii)F 3 = (x + y). (y + z′)

(iv)F 4 = x + y. z