{"id":253,"date":"2019-07-24T08:20:11","date_gmt":"2019-07-24T08:20:11","guid":{"rendered":"https:\/\/bcisnotes.com\/secondsemester\/?p=253"},"modified":"2020-01-09T14:32:31","modified_gmt":"2020-01-09T08:47:31","slug":"basic-theorems-properties-of-boolean-algebra","status":"publish","type":"post","link":"https:\/\/bcisnotes.com\/secondsemester\/digital-systems\/basic-theorems-properties-of-boolean-algebra\/","title":{"rendered":"Basic Theorems & Properties of Boolean Algebra || Boolean Algebra and Logic Gates || Bcis Notes"},"content":{"rendered":"

Basic theorems & Properties of Boolean algebra:<\/h2>\n

Duality\u00a0<\/strong><\/h2>\n

The Huntington postulates have been listed in pairs and designated by parts (a) and part (b). One part may be obtained from the other if the binary operators and those identity elements are interchanged. the important property of Boolean algebra is called the duality principle.\u00a0<\/em>It states that every algebraic expression deducible from the postulates of Boolean algebra remains valid if the operators and identity elements are interchanged. In a two-valued Boolean algebra, the identity elements and the elements of the set B are the same: 1 and 0. If the dual of an algebraic expression is desired, we simply interchange OR and AND operators and replace
\n1’s by 0’s and 0’s by 1’s.<\/p>\n

Basic theorems<\/strong><\/h2>\n

The theorems, like the postulates, are listed in pairs; each relation is the dual of the one paired with it. The postulates are basic axioms of the algebraic structure and need no proof. The theorems must be proven from the postulates. six theorems of Boolean algebra are given below:<\/p>\n

Theorem1: Idempotence (a) x + x = x (b) x.x = x
\nTheorem2: Existence: 0&1 (a) x + 1 = 1 (b) x.0 = 0
\nTheorem3: Involution (x’)’ = x
\nTheorem4: Associative (a) x + (y + z) = (x + y) + z (b) x(yz) = (xy)z
\nTheorem5: Demorgan (a) (x + y)’ = x’y’ (b) (xy)’ = x’ + y’
\nTheorem6: Absorption (a) x + xy = x (b) x(x + y) = x
\nProofs:
\n(a) The proofs of the theorems with one variable are presented below:
\nTHEOREM<\/strong> 1(a): x + x = x
\nx + x = (x + x) . 1 (P4: Identity element)
\n= (x + x)(x + x’) (P5: Existence of inverse)
\n= x + xx’ (P3: Distribution)
\n=x + 0 (P5: Existence of inverse)
\n=x (P4: Identity element)
\nTHEOREM<\/strong> 1(b): x\u00b7x = x
\nx.x = xx + 0 (P4: Identity element)
\n=xx + xx’ (P5: Existence of inverse)
\n=x(x + x’) (P3: Distribution)
\n= x.1 (P5: Existence of inverse)
\n=x (P4: Identity element)
\nHey! Each step in theorem 1(b) and 1(a) are dual of each other.<\/p>\n

THEOREM<\/strong> 2(a): x + 1 = 1
\nx + 1 = 1\u00b7 (x + 1) (P4: Identity element)
\n= (x + x’)(x + 1) (P5: Existence of inverse)
\n=x + x’\u00b71 (P3: Distribution)
\n= x + x’ (P4: Identity element)
\n= 1 (P5: Existence of inverse)<\/p>\n

THEOREM<\/strong> 2(b): x.0 = 0 by duality.<\/p>\n

THEOREM<\/strong> 3: (x ‘)’ = x. From P5, we have x + x’ = 1 and x.x’ = 0, which defines the complement of x. The complement of x’ is x and is also (x’)’. Therefore, since the complement is unique, we have that (x’)’ = x.<\/p>\n

(b) The theorems involving two or three variables may be proven algebraically from the postulates and
\nthe theorems that have already been proven. For example, let’s prove Demorgan\u2019s theorem:
\nTHEOREM 5<\/strong>(a): (x + y)’ = x’ y’
\nFrom postulate P5 (Existence of inverse), for every x in a Boolean algebra, there is a
\nunique x’ such that
\nx + x’ = 1 and x \u2022 x’ = 0<\/p>\n

So it is sufficient to show that x’y’ is the complement of x + y. We’ll do this by showing that (x + y) +
\n(x’y’) = 1 and (x + y) \u2022 (x’y’) = 0.
\n(x + y) + (x’y’) = [(x + y) + x’] [(x + y) + y’] [OR distributes over AND (P3)]
\n= [(y + x) + x’] [(x + y) + y’] [OR is commutative (P2)]
\n=\u00a0 [y + (x + x’)] [x + (y + y’)] [OR is associative (Theorem 3(a)), used twice]
\n= (y + 1)(x + 1) [Complement, x + x’ = 1 (P5), twice]
\n= 1 \u2022 1 [x + 1 = 1, (Theorem 2), twice]
\n= 1 [Idempotent, x \u2022 x = x (Theorem 1)]
\nAlso,
\n(x + y)(x’y’) = (x’y’) (x + y) [AND is commutative (P2)]
\n= [(x’y’) x] + [(x’y’) y] [AND distributes over OR (P3)]
\n= [(y’x’)x] + [(x’y’)y] [AND is commutative (P2)]
\n= [y'(x’x)] + [x'(y’y)] [AND is associative (Theorem 3(b)), twice]
\n= [y'(xx’)] + [x'(yy’)] [AND is commutative, twice]
\n= *y’ \u2022 0+ + *x’ \u2022 0+ [Complement, x \u2022 x’ = 0, twice]
\n= 0 + 0 [x \u2022 0 = 0, twice]
\n= 0 [Idempotent, x + x = x]
\nTHEOREM 5(b):<\/strong> (xy)’ = x’ + y’ \uf0df can be proved similarly as in Theorem 5(a). Each step in the proof of 5(b) is the dual of its 5(a) counterparts.
\nHey! Theorems above can also be proved using truth tables (alternative to algebraic simplification). Viz.<\/p>\n

Operator Precedence\u00a0<\/strong><\/p>\n

The operator precedence for evaluating Boolean expressions is
\n1. Parentheses
\n2. NOT
\n3. AND
\n4. OR
\nIn other words, the expression inside the parentheses must be evaluated before all other operations. The next operation that holds precedence is the complement, then follows the AND, and finally the OR. Example: (a+b.c).d’\u00a0 here we first evaluate \u2018b.c\u2019 and OR it with \u2018a\u2019 followed by ANDing with a complement of \u2018d\u2019.<\/p>\n

You may like an introduction to Boolean Algebra<\/a><\/p>\n

<\/div>