JEE Main & Advanced Mathematics Mathematical Logic and Boolean Algebra Introduction

Boolean algebra is a tool for studying and applying mathematical logic which was originated by the English mathematician George Boolean. In 1854 he wrote a book “An investigation of the law of thought”, be developed a theory of logic using symbols instead of words. This more algebraic treatment of subject is now called boolean algebra  

Definition : A non empty set B together with two operations denoted by \['\vee '\] and \[\,'\wedge '\]  is said to be a boolean algebra if the following axioms hold :

(i) For all \[x,y\in B\]

(a) \[x\vee y\in B\]                          (Closure property for \[\vee \])

(b) \[x\wedge y\in B\]                   (Closure property for \[\wedge \])

(ii) For all \[x,y\in B\]

(a) \[x\vee y=y\vee x\]                 (Commutative law for \[\vee \])

(b) \[x\wedge y=y\wedge x\]    (Commutative law for \[\wedge \])

(iii) For all x, y and z in B,

(a) \[(x\vee y)\vee z=x\vee (y\vee z)\] (Associative law of\[\vee \])

(b) \[(x\wedge y)\wedge z=x\wedge (y\wedge z)\]       (Associative law of \[\wedge \])

(iv) For all x, y and z in B,

(a) \[x\vee (y\wedge z)=(x\vee y)\wedge (x\vee z)\]           (Distributive law of \[\vee \] over\[\wedge \])

(b) \[x\wedge (y\vee z)=(x\wedge y)\vee (x\wedge z)\]     (Distributive law of \[\wedge \] over \[\vee \])

(v) There exist elements denoted by 0 and 1 in B such that for all \[x\in B\],

(a) \[x\vee 0=x\]                                                                                           (0 is identity for \[\vee \])

(b) \[x\wedge 1=x\]                                                                                  (1 is identity for \[\wedge \])

(vi) For each \[x\in B\], there exists an element denoted by x¢, called the complement or negation of x in B such that

(a) \[x\vee x'=1\]

(b) \[x\wedge x'=0\]                                                                                    (Complement laws)

Principle of duality

The dual of any statement in a boolean aglebra B is the statement obtained by interchanging the operation Ú and Ù, and simultaneously interchanging the elements 0 and 1 in the original statement.

In a boolean algebra, the zero element 0 and the unit element 1 are unique.

Let B be a boolean algebra.  Then, for any x and y in B, we have

(a) \[x\vee x=x\]                                                                      (a¢) \[x\wedge x=x\]

(b) \[x\vee 1=1\]                                                                    (b¢) \[x\wedge 0=0\]

(c) \[x\vee (x\wedge y)=x\]                                            (c¢) \[x\wedge (x\vee y)=x\]

(d) \[{0}'=1\]                                                                          (d¢) \[{1}'=0\]

(e) \[({x}'{)}'=x\]

(f) \[(x\vee y{)}'={x}'\wedge {y}'\]                            (f¢) \[(x\wedge y{)}'={x}'\vee {y}'\]        

Important points :

• In view of (i) (a) and (b) above, one may note that the operations + and . are infact binary operations on B.

• We sometimes designate a boolean algebra by (B, \['\vee '\], \['\wedge '\], \['\], 0, 1) in order to emphasise its six parts; namely the set B, the two binary operations \['\vee '\] and \['\wedge '\], the complement operation and the two special elements 0 and 1. These special elements are called the zero element and the unit element. However, it may be noted that the symbols 0 and 1 do not necessarily represent the number zero and one.

• For the set S of all logical statement ,the operations + and . play the roles of \[\vee \] and \[\wedge \], respectively. The tautology t and the contradiction c play  the roles of 1 and 0, and the operation \['\tilde{\ }'\] plays the role of ‘¢’      

For \[P(A)\], the set of all subsets of a set A, the operations \[\cup \]and \[\cap \] play the roles of \['\vee '\]and \['\wedge '\], A and \[\varphi \] play the role of 1 and 0, and complementation plays the role of ‘¢’.