Mathematical Foundation of Computer Science

DHARM

N-COM\APPENDIX.PM5

354 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

• Since, 0 + 0 = 0 and 0 + 1 = 0 + 1 = 1 (existence of an identity 0 for operation ‘+’) and
  
  
  1. 1 = 1 and 0. 1 = 1. 0 = 0 (existence of an identity 1 for operation ‘. ’).
  
  
  
  


• Commutative law is obvious from the symmetry of the binary operations ‘+’ and ‘. ’
  shown in tables.


• Distribution law such that distribution of operation ‘.’ over operation ‘+’ such that
  x. (y + z) = (x. y) + (x. z) hold valid. That can be verified from the same truth values
  shown in the column 5 and 8 of the table Fig. A.3.
  xyzy + zx. (y + z) x. yx. z (x. y) + (x. z)
  000 0 0 00 0
  001 1 0 00 0
  010 1 0 00 0
  011 1 0 00 0
  100 0 0 00 0
  101 1 1 01 1
  110 1 1 10 1
  111 1 1 11 1
  123 4 5 67 8 ←
  Fig. A.3
  Similarly we can verify the distribution of the operation ‘+’ over operation ‘.’ using
  truth table.


• For the verification of x + x′ = 1 (and x. x′ = 0) the complement of the elements 0 and
  1, since, 0 + 0′ = 0 + 1 = 1 and 1 + 1′ = 1 + 0 = 1 (and also 0. 0′ = 0. 1 = 0 and 1. 1′ =

1. 0 = 0).

• Since, set X = {0, 1} or the set contains unique elements i.e., 0 ≠ 1.

A.3 Theorems of Boolean Algebra.........................................................................................

Now we can discuss the basic theorems of Boolean algebra and its most common postulates.
The postulates shown in the in the table (Fig. A.4) is abbreviated by P1 – P4 and the theorems
by T1 – T6.

Abbreviation Statement of Rules Name

P1 x + 0 = xx. 1 = x

P2 x + x′ = 1 x. x′ = 0

P3 x + y = y + xx. y = y. x Commutative

P4 x. (y + z) = x. y + x. zx + y. z = (x + y). (x + z) Distributive

T1 x + x = xx. x = x

T2 x + 1 = 1 x. 0 = 0

T3 (x′)′ = x Involution

T4 x + (y + z) = (x + y) + zx. (y. z) = (x. y). z Associative

T5 (x + y)′ = x′. y′ (x. y)′ = x′ + y′ De Morgan’s

T6 x + x. y = x x. (x + y) = x Absorption

Fig. A.4

Column

number