ML Aggarwal Class 12 Maths Solutions Section A Chapter 03 Boolean Algebra

3.1 Boolean Algebra

In 1854, George Boole created a mathematical system that eventually developed into Boolean Algebra. An algebraic structure made up of a set B with elements a, b, c ... and two binary operations called sum and product (shown as + and •) is a boolean algebra when all elements in B satisfy these axioms:

• (1) a + b, a • b ∈ B (closure property)
• (2) a + b = b + a and a • b = b • a (commutative property)
• (3) (a + b) + c = a + (b + c) and (a • b) • c = a • (b • c) (associative property)
• (4) a • (b + c) = a • b + a • c and a + (b • c) = (a + b) • (a + c) (distributive laws)
• (5) There exist an additive identity 0 and a multiplicative identity 1 (both in B) such that for all a ∈ B: a + 0 = a and a • 1 = a (identity)
• (6) For every a ∈ B, an element a′ ∈ B exists where a + a′ = 1 and a • a′ = 0 (complement or inverse)

Remarks

• Some mathematicians add an extra requirement - cardinality - stating that B must have at least two different elements a and b where a ≠ b.
• Axiom (6) differs greatly from standard algebra. In regular arithmetic, additive and multiplicative inverses are different (the additive inverse of 2 is -2, while the multiplicative inverse is 1/2). In boolean algebra, both inverses are identical. Also, typical algebra has a + a′ = 0 and a • a′ = 1, but boolean algebra has a + a′ = 1 and a • a′ = 0. This mirrors set theory, where A ∪ A′ = ξ (the universal set) and A ∩ A′ = φ (the empty set). Here, ξ works as the multiplicative identity since A ∩ ξ = A, and φ acts as the additive identity since A ∪ φ = A for all A ⊆ ξ. In boolean algebra, the inverse of a is written as a′, not a - 1.
• The rule a • (b + c) = a • b + a • c mirrors real numbers, but the distribution of + over • (that is, a + (b • c) = (a + b) • (a + c)) does not apply in regular algebra.
• In standard algebra, x + x + x + ... n times = nx, but in boolean algebra, adding x to itself any number of times just gives x. This rule is called the idempotent law.
• Sets form a classical example of a boolean algebra, so many texts use ∪ and ∩ in place of + and •.
• Modern computers and communication systems rely heavily on boolean algebra - binary digits (or bits) 0 and 1 represent electrical switches off or on, current absent or flowing, lights off or on, capacitors discharged or charged, and so on. This will become more obvious as we advance.
• The expression a • b is sometimes shortened to just ab.
• When brackets are absent, the • operation takes priority over +. So in a + b • c, we calculate b • c first.

Example. Let B = {0, 1} with operations + and • defined as:

Then (B, +, •) is a boolean algebra. (Verify that all axioms (1) through (6) hold.) Here 1 serves as the multiplicative identity and 0 serves as the additive identity. This is the simplest possible Boolean Algebra and is called Switching Algebra.

More Examples of Boolean Algebras

We have already shown one example: B = {0, 1}. As a second example, let A be any family of sets that is closed under union, intersection, and complement. Then (A, ∪, ∩) forms a Boolean Algebra. Note that the universal set ξ acts as the unit element and the empty set φ acts as the zero element.

Example 1. If V = {1, 2, 3}, A = {1, 2}, then A′ = {3}. Show that the set T = {V, A, A′, φ} along with operations ∪ and ∩ forms Boolean algebra.
Answer: We must verify that this system meets the core axioms of Boolean Algebra. The composition tables for ∪ and ∩ are:

(1) Closure: All unions and intersections of V, A, A′, φ stay within T.

(2) ∪ and ∩ are commutative for sets.

(3) ∪ and ∩ are associative for sets.

(4) ∪ and ∩ are distributive for sets (A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C), etc.)

(5) The additive identity for ∪ is φ, because V ∪ φ = V, A ∪ φ = A, A′ ∪ φ = A′, φ ∪ φ = φ. The unit element for ∩ is V, since V ∩ V = V, A ∩ V = A, A′ ∩ V = A′, φ ∩ V = φ.

(6) Inverse: A′ is the inverse of A, and φ is the inverse of V.

Since all core axioms are met, (T, ∪, ∩) is a boolean algebra.
In simple words: The four sets in T work together under union and intersection - any combination stays in the group, operations work the same no matter the order, and each set has an inverse that balances it out.

Exam Tip: Always verify all six axioms systematically using the operation tables - examiners look for explicit checks of closure, identity elements, and inverses.

Example 2. Let D_n denote the set of divisors of n, where n is a natural number. Define operations +, • and ′ on D_n as a + b = lcm {a, b} (least common multiple of a and b), a • b = gcd {a, b} (greatest common divisor of a and b), and a′ = n/a. Prove that D_4 is not a boolean algebra, while D_6 is a boolean algebra.
Answer:

(i) For D₄ = {1, 2, 4}, the operation tables are:

Operations + and • show closure, commutativity, and associativity. For distribution of + over •: 1 + (2 • 4) = 1 + 2 = 2 and (1 + 2) • (1 + 4) = 2 • 4 = 2. Distribution works for other elements too. The additive identity is 1 (since a + 1 = a for all a). The unit element is 4 (since a • 4 = a for all a). From the ′ table, 2′ = 2. However, 2 + 2 = 2 ≠ 4 (the unit element), and 2 • 2 = 2 ≠ 1 (the additive identity). This breaks the complement axiom, so D₄ is not a boolean algebra.

(ii) For D₆ = {1, 2, 3, 6}, the operation tables are:

Closure, commutativity, associativity, and distributivity all hold. The additive identity is 1 (a + 1 = a for all a), and the unit element is 6 (a • 6 = a for all a). Checking the complement axiom: 1 + 6 = 6, 1 • 6 = 1; 2 + 3 = 6, 2 • 3 = 1; 3 + 2 = 6, 3 • 2 = 1; 6 + 1 = 6, 6 • 1 = 1. All complement requirements are satisfied. Therefore, D₆ is a boolean algebra.

Note: In general, when n is a product of distinct prime numbers, D_n forms a boolean algebra, with lcm as +, gcd as •, n/a as complement, 1 as additive identity, and n as unit element. However, if any prime appears more than once in n's factorization, D_n is not a boolean algebra.
In simple words: D₆ works because each element has a proper complement that follows all the rules - when you add an element to its complement, you get the maximum (6), and when you multiply them, you get the minimum (1). D₄ fails because 2 cannot find a proper complement.

Exam Tip: Always check the complement property last - it is the most likely axiom to fail. Show specific examples where it breaks down to disprove a boolean algebra.

Exercise 3.1

Question 1. If B = {φ, ξ, S, S′} where S is any non-empty subset of ξ, then show that B along with the operations ∪ and ∩ forms a boolean algebra.
Answer: We need to verify all six core axioms using these four sets. The + operation (∪) and • operation (∩) are closed on B since any union or intersection of the given sets yields another member of B. Commutativity holds for both ∪ and ∩ (the order of sets doesn't change the result). Associativity applies to both operations (regrouping sets doesn't affect the outcome). Distributivity is a property of set operations. The additive identity is φ (any set combined with the empty set via ∪ equals itself), and the multiplicative identity is ξ (any set combined with ξ via ∩ equals itself). The complements are: S′ is the complement of S, φ is the complement of ξ, and vice versa. All axioms are satisfied, so (B, ∪, ∩) is a boolean algebra.
In simple words: The four sets form a closed group under ∪ and ∩, each set has its opposite pair, and all boolean rules hold perfectly.

Exam Tip: When dealing with power set problems, remember that ξ and φ serve as multiplicative and additive identities, and complements are always symmetric pairs.

Question 2. Let B = {{1}, {2}, {1, 2}, φ}. Show that (B, ∩, ∪, ′, φ, {1, 2}) is a boolean algebra.
Answer: All results of intersecting or uniting these four sets remain in B, satisfying closure. Set operations are commutative and associative. Distribution holds (A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)). The additive identity is φ (any set ∪ φ gives that set), and the multiplicative identity is {1, 2} (any set ∩ {1, 2} gives that set). Complements: {1} has complement {2}, {2} has complement {1}, {1, 2} has complement φ, and φ has complement {1, 2}. Each pair satisfies the inverse requirements. All axioms hold, confirming (B, ∩, ∪, ′, φ, {1, 2}) is a boolean algebra.
In simple words: The four sets work as a boolean system because each operation stays within the group, operations follow set rules, and every set pairs with its perfect opposite.

Exam Tip: Verify complements by checking that a ∪ a′ equals the universal set and a ∩ a′ equals the empty set for each element.

Question 3. Let B = {φ, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}. Show that (B, ∪, ∩, ′, φ, {1, 2, 3}) is a boolean algebra.
Answer: All unions and intersections of these eight sets (the power set of {1, 2, 3}) belong to B, giving closure. Union and intersection are commutative and associative on sets. Distributivity is satisfied. The additive identity is φ (A ∪ φ = A for all A), and the multiplicative identity is {1, 2, 3} (A ∩ {1, 2, 3} = A for all A). Complements within the universal set {1, 2, 3} are: φ ↔ {1, 2, 3}, {1} ↔ {2, 3}, {2} ↔ {1, 3}, {3} ↔ {1, 2}. Each element a satisfies a ∪ a′ = {1, 2, 3} and a ∩ a′ = φ. All properties of a boolean algebra are met, so (B, ∪, ∩, ′, φ, {1, 2, 3}) is a boolean algebra.
In simple words: This is the full power set of a 3-element universal set, and it works perfectly as a boolean algebra because all operations stay within the 8 sets and every subset has its exact opposite within the group.

Exam Tip: Power sets of any finite set form boolean algebras - the number of elements will be 2^n where n is the size of the universal set.

Question 4. Let D_n = set of divisors of n, where n is a natural number. Define operations +, • and ′ as a + b = lcm {a, b}, a • b = gcd {a, b}, a′ = n/a. Prove that D_8 is not a boolean algebra while D_15 is a boolean algebra.
Answer: For D₈ = {1, 2, 4, 8}: Since 8 = 2³, it has a repeated prime factor. The complement of 2 would be 8/2 = 4. Testing the inverse: 2 + 4 = lcm(2, 4) = 4 ≠ 8 (should equal the unit element). Also, 2 • 4 = gcd(2, 4) = 2 ≠ 1 (should equal the additive identity). The complement axiom fails, so D₈ is not a boolean algebra. For D₁₅ = {1, 3, 5, 15}: Since 15 = 3 × 5 (product of distinct primes), complements work as follows: 1′ = 15, 3′ = 5, 5′ = 3, 15′ = 1. Checking: 1 + 15 = 15, 1 • 15 = 1; 3 + 5 = lcm(3, 5) = 15, 3 • 5 = gcd(3, 5) = 1; 5 + 3 = 15, 5 • 3 = 1; 15 + 1 = 15, 15 • 1 = 1. All inverse requirements hold. The additive identity is 1, the multiplicative identity is 15, and all other boolean algebra properties are satisfied. Therefore, D₁₅ is a boolean algebra.
In simple words: D₁₅ works because 15 has no repeated prime factors, giving every divisor a perfect opposite. D₈ fails because 8 = 2 × 2 × 2 creates divisors that cannot properly pair up.

Exam Tip: Check whether n is a product of distinct primes first - if yes, D_n is definitely a boolean algebra; if any prime repeats, it definitely isn't.

3.2 Duality in a Boolean Algebra

The dual of a statement in boolean algebra is created by swapping + with • and also swapping 1 with 0 in the original statement. For instance, the dual of a + b = b + a is a • b = b • a. Similarly, the dual of a + a = 1 is a • a = 0. The Principle of Duality states that when any theorem holds in a Boolean algebra, its dual statement is also true. When a theorem comes from basic axioms, the dual statement can be derived by using the dual form of each proof step. For example, proving a + a = a automatically gives us a • a = a by duality. Similarly, proving a + 1 = 1 means a • 0 = 0 must also be true. This means that once a theorem is proven in boolean algebra, we get its dual without extra work.

3.3 Elementary Properties of Boolean Algebra

Many important properties of Boolean Algebra follow from basic axioms (1) through (6). Here are the key ones:

• (i) (Idempotent Law): a + a = a and a • a = a.
• (ii) (Boundedness Laws): a + 1 = 1 and a • 0 = 0.
• (iii) (Involution Law): (a′)′ = a.
• (iv) 1′ = 0 and 0′ = 1.
• (v) (De Morgan's Laws): (a + b)′ = a′ • b′ and (a • b)′ = a′ + b′.
• (vi) (Law of absorption): a + (a • b) = a and a • (a + b) = a.
• (vii) (Uniqueness of inverse): for every a ∈ B, a′ is unique.

Proofs of Properties:

(i) To prove a + a = a: By the identity axiom, a = a + 0. Substituting 0 = a • a′ (by the inverse axiom), we get a = a + (a • a′). Applying the distributive law: a = (a + a) • (a + a′). Using the inverse axiom: a = (a + a) • 1. By the identity axiom: a = a + a.

To prove a • a = a: Similarly, a = a • 1. Substituting 1 = a + a′: a = a • (a + a′). By the distributive law: a = (a • a) + (a • a′). By the inverse axiom: a = (a • a) + 0. By the identity axiom: a = a • a. The property a • a = a also follows by duality from a + a = a.

(ii) To prove a + 1 = 1: By the inverse axiom, 1 = a + a′. Substituting 1 = a + a′ • 1 (by the identity axiom), we get a + a′ = a + (a′ • 1). By the distributive law: a + a′ = (a + a′) • (a + 1). By the inverse axiom: 1 = 1 • (a + 1). By the identity axiom: 1 = a + 1. The property a • 0 = 0 follows by duality.

(iii) To prove (a′)′ = a: Since a′ is the complement of a, by definition we have a + a′ = 1 and a • a′ = 0. These can be rewritten as a′ + a = 1 and a′ • a = 0. By axiom (6), (a′)′ = a.

(iv) To prove 1′ = 0 and 0′ = 1: By identity, 1′ = 1′ • 1. By commutativity: 1′ = 1 • 1′. By the inverse axiom: 1′ = 0. The property 0′ = 1 follows by duality.

Remark: To show that a′ = b or b′ = a (that is, to show a and b are complements of each other), prove both a + b = 1 and a • b = 0.

(v) De Morgan's Laws - To prove (a + b)′ = a′ • b′: Consider (a + b) • (a′ • b′). By commutativity: (a′ • b′) • (a + b). By the distributive law: ((a′ • b′) • a) + ((a′ • b′) • b). Rearranging: ((b′ • a′) • a) + ((a′ • b′) • b), which becomes (b′ • (a′ • a)) + (a′ • (b′ • b)). By the inverse axiom: (b′ • 0) + (a′ • 0) = 0 + 0 = 0. Also, (a + b) + (a′ • b′) = (a + b + a′) • (a + b + b′) = (a + a′ + b) • (a + 1) = (1 + b) • 1 = 1 • 1 = 1. By the definition of inverse: (a + b)′ = a′ • b′.

To prove (a • b)′ = a′ + b′: Consider (a • b) + (a′ + b′). By commutativity: a′ + b′ + a • b. By the distributive law: (a′ + b′ + a) • (a′ + b′ + b) = (a + a′ + b′) • (a′ + b + b′) = (1 + b′) • (a′ + 1) = 1 • 1 = 1. Also, (a • b) • (a′ + b′) = (a • b) • a′ + (a • b) • b′ = (a • a′) • b + a • (b • b′) = 0 • b + a • 0 = 0 + 0 = 0. By the definition of inverse: (a • b)′ = a′ + b′. The property (a • b)′ = a′ + b′ also follows by duality from (a + b)′ = a′ • b′.

(vi) Law of Absorption - To prove a + (a • b) = a: By identity, a + (a • b) = a • 1 + a • b. By the distributive law: a • (1 + b). By property (ii): a • 1. By identity: a.

To prove a • (a + b) = a: By identity, a • (a + b) = (a + 0) • (a + b). By the distributive law: a + (0 • b). Since 0 • b = 0: a + 0. By identity: a. The property a • (a + b) = a also follows by duality from a + (a • b) = a.

(vii) Uniqueness of Complement - Let a′₁ and a′₂ be two complements of a. Then: a + a′₁ = 1, a • a′₁ = 0, a + a′₂ = 1, a • a′₂ = 0. Now, a′₁ = a′₁ • 1 = a′₁ • (a + a′₂) = (a′₁ • a) + (a′₁ • a′₂) = 0 + (a′₁ • a′₂) = (a • a′₂) + (a′₁ • a′₂) = (a + a′₁) • a′₂ = 1 • a′₂ = a′₂. Thus, a′₁ = a′₂, proving uniqueness.

Example 1. Write the dual of each of the following statements:
(i) x + (y • x) = x
(ii) x • y′ + y = x + y
(iii) (x + y) • (x + 1) = x + x • y + y
(iv) (x′ + y) • (x + y′) = x′ • y′ + x • y
(v) [(x′ + y) • (y′ + z)] • (x′ + z)′ = 0
Answer: By switching + and • and also swapping 1 and 0 in each statement, the dual statements are:

(i) x • (y + x) = x
(ii) (x + y′) • y = x • y
(iii) (x • y) + (x • 0) = x • (x + y) • y
(iv) (x′ • y) + (x • y′) = (x′ + y′) • (x + y)
(v) [(x′ • y) + (y′ • z)] + (x′ • z)′ = 1
In simple words: To write the dual, swap all + signs with • signs and swap all 0s with 1s, leaving the variables and complements untouched.

Exam Tip: When writing duals, be systematic - go through the entire statement and swap each operation and identity without missing any.

Example 2. Prove that a + (a′ • b) = a + b and a • (a′ + b) = a • b.
Answer: To prove the first: a + (a′ • b) = (a + a′) • (a + b) (by the distributive law) = 1 • (a + b) (by the complement axiom) = a + b (by the identity axiom). Similarly, for the second: a • (a′ + b) = (a • a′) + (a • b) (by the distributive law) = 0 + (a • b) (by the complement axiom) = a • b (by the identity axiom).
In simple words: When a complement pairs with something, it either "disappears" (turns to 0 or 1 depending on the operation) and leaves behind the other part.

Exam Tip: These absorption-style rules are shortcuts - once you see a complement in an expression, use these identities to simplify immediately.

Example 3. Prove that a + (a′ • c + b) = a + b + c.
Answer: a + (a′ • c + b) = (a + a′ • c) + b (by the associative law) = ((a + a′) • (a + c)) + b (by the distributive law) = (1 • (a + c)) + b (by the complement axiom) = (a + c) + b (by the identity axiom) = a + (c + b) (by associativity) = a + (b + c) (by commutativity) = a + b + c.
In simple words: The complement a′ combines with c, then uses the distributive property to separate. Once a + a′ appears, it becomes 1, which then cancels out when multiplied, leaving just (a + c). Then everything combines together.

Exam Tip: Work step-by-step through distributive expansions - don't skip steps, as examiners check that you understand each transformation.

Example 4. Prove that ab + c(a′ + b′) = ab + c.
Answer: ab + c(a′ + b′) = ab + c(ab)′ (by De Morgan's law - (a′ + b′) = (ab)′) = (ab + c) • (ab + (ab)′) (by the distributive law) = (ab + c) • 1 (by the complement axiom) = ab + c (by the identity axiom).
In simple words: De Morgan's law converts (a′ + b′) into (ab)′, then the distributive law creates two parts that add together, one of which is a perfect complement pair that equals 1.

Exam Tip: Recognise De Morgan's patterns quickly - (a + b)′ becomes a′ • b′, and (ab)′ becomes a′ + b′.

Example 5. Prove that (x + y) • (x + 1) = x + x • y + y.
Answer: (x + y) • (x + 1) = (x + y) • 1 (by the boundedness law: a + 1 = 1) = x + y (by the identity axiom) = (x + x • y) + y (by the absorption law: x = x + x • y) = x + x • y + y (by the associative law).
In simple words: The x + 1 part becomes just 1, so we multiply (x + y) by 1 to get x + y. Then we use a sneaky trick - we rewrite x as x + x • y - since x absorbs the product x • y - and then separate everything.

Exam Tip: When you see a + 1 or a • 0, replace them immediately with 1 and 0 respectively - these are automatic simplifications.

Example 6. Show that in a boolean algebra, the zero element 0 and the unit element 1 are unique.
Answer: Suppose 0 and 0̄ are both additive identities. Then: by definition, a + 0 = a for all a ∈ B, so 0̄ + 0 = 0̄ ... (i). Also, a + 0̄ = a for all a ∈ B, so 0 + 0̄ = 0 ... (ii). By commutativity: 0̄ + 0 = 0 + 0̄, which gives 0̄ = 0 using (i) and (ii). Thus, the zero element is unique. Similarly, suppose 1 and 1̄ are both unit elements. Then: a • 1 = a and a • 1̄ = a for all a. So 1̄ • 1 = 1̄ and 1 • 1̄ = 1. By commutativity: 1̄ • 1 = 1 • 1̄, giving 1̄ = 1. Thus, the unit element is unique.
In simple words: If two elements both acted like zero (or both like one), they would have to be equal to each other by the definition of what they do.

Exam Tip: Uniqueness proofs use the property that defines the element - assume two exist, apply the property to both, and show they must be identical.

Example 7. Prove the following: (i) If x + y = 0, then x = 0 = y (ii) x • y′ = 0 if and only if x • y = x (iii) x = 0 if and only if y = x • y′ + x′ • y for all y.
Answer: (i) Given x + y = 0. Now x = x • (x + y) (by the absorption law) = x • 0 (since x + y = 0) = 0. Similarly, y = y • (y + x) = y • (x + y) = y • 0 = 0. (ii) First, assume x • y′ = 0. Then (x • y′)′ = 0′, so x′ + y = 1. Now x = x • 1 = x • (x′ + y) (using x′ + y = 1) = (x • x′) + (x • y) = 0 + (x • y) = x • y. For the converse, assume x • y = x. Then x • y′ = (x • y) • y′ (using x = x • y) = x • (y • y′) = x • 0 = 0. (iii) First, assume x = 0. Then x • y′ + x′ • y = 0 • y′ + 0′ • y = 0 + 1 • y = 0 + y = y. Conversely, assume y = x • y′ + x′ • y for all y. Substitute y = 0: 0 = x • 0′ + x′ • 0 = (x • 1) + (x′ • 0) = x + 0 = x. Thus, x = 0.
In simple words: (i) The sum is zero only when both parts are zero. (ii) If x AND (NOT y) equals zero, then x must be contained entirely within y. (iii) The expression x • y′ + x′ • y acts like "exclusive or" - it equals y only when x is zero.

Exam Tip: For "if and only if" statements, prove both directions separately - forward direction first, then the reverse direction.

Example 8. Prove that if x + y = x + z and x′ + y = x′ + z, then y = z.
Answer: Given: x + y = x + z ... (i) and x′ + y = x′ + z ... (ii). Now y = y + 0 = y + (x • x′) (since x • x′ = 0) = (y + x) • (y + x′) (by the distributive law) = (x + y) • (x′ + y) (by commutativity) = (x + z) • (x′ + z) (using (i) and (ii)) = (x • x′) + z (by the distributive law) = 0 + z = z. Thus, y = z.
In simple words: We break y into two pieces using the rule y + (x • x′) = y, then regroup those pieces using the facts we were given, and they turn into the same pieces that make up z.

Exam Tip: This is a cancellation law proof - inserting an identity (0 = x • x′) early on often leads to the needed regrouping.

Example 9. A boolean algebra cannot have exactly three elements.
Answer: Assume a boolean algebra B has exactly three elements: B = {0, 1, x}, where x ≠ 0 and x ≠ 1. Since x ∈ B, there exists x′ ∈ B with x + x′ = 1 and x • x′ = 0. Since B has only three elements, x′ must be one of 0, 1, or x. If x′ = 0, then (x′)′ = 0′ gives x = 1, a contradiction. If x′ = 1, then (x′)′ = 1′ gives x = 0, a contradiction. If x′ = x, then from x + x′ = 1, we get x + x = 1, so x = 1 (by the idempotent law x + x = x), again a contradiction. All cases fail, so a boolean algebra cannot have exactly three elements.
In simple words: No matter what we try, every complement leads to a contradiction - proving three elements is impossible for a boolean algebra.

Exam Tip: This proof works by exhausting all cases - after checking all possible values, no valid option remains, so the assumption must be false.

Exercise 3.2

Question 1. Write the dual statement of each of the following:
(i) (1 + x) • (0 + y) = y
(ii) (x • y)′ = x′ + y′
(iii) a + 1 = 1
(iv) x + x′y = x + y
(v) x + [x • (y + 1)] = x
(vi) x + [(y′ + x) • y]′ = 1
(vii) (x + y)′ = x′ • y′
(viii) (x′ + y′)′ = x • y
(ix) (1 • x) + 0 = x
(x) (1 • x)′ = 0 + x′
(xi) If x + y = 0 then x = 0 = y
(xii) x • y′ = 0 if and only if x • y = x
(xiii) x = 0 if and only if y = x • y′ + x′ • y for all y
Answer:
(i) (0 • x) + (1 • y) = y
(ii) (x + y)′ = x′ • y′
(iii) a • 0 = 0
(iv) x • (x′ + y) = x • y
(v) x • [x + (y • 0)] = x
(vi) x • [(y′ • x) + y]′ = 0
(vii) (x • y)′ = x′ + y′
(viii) (x′ • y′)′ = x + y
(ix) (0 + x) • 1 = x
(x) (0 + x)′ = 1 • x′
(xi) If x • y = 1 then x = 1 = y
(xii) x + y′ = 1 if and only if x + y = x
(xiii) x = 1 if and only if y = (x + y′) • (x′ + y) for all y
In simple words: In each dual statement, every + becomes •, every • becomes +, every 0 becomes 1, and every 1 becomes 0. Variables and their complements stay unchanged.

Exam Tip: Write the dual mechanically - swap the operations and identities throughout without hesitation.

Question 2. Using elementary properties of boolean algebra, prove that: (i) x + x • (y + 1) = x (ii) (a + b) a′ b′ = 0 (iii) (x + y) + (x′ • y′) = 1.
Answer:
(i) x + x • (y + 1) = x + x • 1 (by the boundedness law: y + 1 = 1) = x + x (by the identity law: x • 1 = x) = x (by the idempotent law).

(ii) (a + b) a′ b′ = ((a + b) a′) b′ (by associativity of •). Now (a + b) a′ = a a′ + b a′ (by the distributive law) = 0 + b a′ (by the inverse law) = b a′. So ((a + b) a′) b′ = (b a′) b′ = b (a′ b′) (by associativity) = b (b′ a′) (by commutativity) = (b b′) a′ (by associativity) = 0 • a′ (by the inverse law) = 0.

(iii) (x + y) + (x′ • y′) = (x + y + x′) • (x + y + y′) (by the distributive law) = (x + x′ + y) • (x + y + y′) (by commutativity) = (1 + y) • (x + 1) (since x + x′ = 1 and y + y′ = 1) = 1 • 1 (by the boundedness law: a + 1 = 1) = 1.
In simple words: (i) Adding 1 to anything inside a product makes that product equal 1, so x + x • 1 becomes x + x, which collapses to x. (ii) When you multiply a sum by the complements of both its parts, you get 0. (iii) A sum plus its own complement under De Morgan's transformation equals 1.

Exam Tip: For product proofs like (ii), use the distributive law first to separate the operations, then apply inverse and idempotent laws.

Question 3. Prove the following statements: (i) If x • y = 1, then x = 1 = y (ii) x + y′ = 1 if and only if x + y = x.
Answer:
(i) Given x • y = 1. Now x = x • 1 = x • (x • y) (using x • y = 1) = (x • x) • y (by associativity) = x • y (by idempotence: x • x = x) = 1. Similarly, y = y • 1 = y • (x • y) = (y • x) • y (by associativity) = x • (y • y) (by commutativity, then associativity) = x • y (by idempotence) = 1. Thus, x = 1 = y.

(ii) Forward: Assume x + y′ = 1. Now x + y = x + y • 1 (by identity) = x + y • (x + y′) (using x + y′ = 1) = (x + y • x) + (y • y′) (by the distributive law) = (x + y • x) + 0 (by the inverse law) = x + (y • x) (by association, and y • x = x • y by commutativity) = x (by absorption: x + (x • y) = x). Reverse: Assume x + y = x. Then x + y′ = (x + y) + y′ = x + (y + y′) (by associativity) = x + 1 (by the inverse law) = 1 (by the boundedness law).
In simple words: (i) A product equals 1 only when both factors are 1. (ii) The statement "x + y′ = 1" means "either x is true or y is false (or both)", which is true exactly when "x + y = x" - that is, when all of y is already included in x.

Exam Tip: For "if and only if" proofs, always show both directions - assume one side, derive the other, then start fresh and assume the opposite direction.

3.4 Boolean Expressions and Functions

In a boolean algebra (B, +, •, ′, 0, 1), constants refer to specific elements like 0 and 1, or other defined elements of B. Variables such as x and y can stand for any element of B. In boolean algebra {0, 1}, there are two constants (0 and 1), and we can create any number of variables (x, y, z, etc.) that can take either value.

A boolean expression is formed by combining variables and constants using the operations +, •, and ′ a finite number of times. Examples include: x + 1, x + y, x′ + y • 0, (x + y)(y′ + z), [(x₁ • x₂) + x₃]′, and so on.

A boolean function is defined by a boolean expression. Examples are: f(x) = x′, f(x, y) = x + y, g(x, y) = x • y′ + 1. Different expressions may represent the same function - for instance, x • (y + z) and (x • y) + (x • z) both give the same function in three variables.

A boolean function of n variables x₁, x₂, ..., xₙ is a mapping from B^n to B, written as f(x₁, x₂, ..., xₙ) or g(x₁, x₂, ..., xₙ).

Example 1. Find the value of the boolean expression (x₁ • x₂)′ + x₃ if (i) x₁ = 1, x₂ = 0, x₃ = 1 (ii) x₁ = 1, x₂ = 1, x₃ = 0.
Answer: (i) Substituting: (1 • 0)′ + 1 = (0)′ + 1 = 1 + 1 = 1. (ii) Substituting: (1 • 1)′ + 0 = (1)′ + 0 = 0 + 0 = 0.
In simple words: Replace each variable with its number, then compute step by step - multiplication first, then complements, then addition.

Exam Tip: Always substitute carefully - double-check that you've put the right value in each position.

Example 2. Construct input/output table for the boolean function f on boolean algebra {0, 1} defined by: (i) f (x₁, x₂) = x₁ • x₂′ (ii) f (x₁, x₂, x₃) = (x₁ • x₂)′ + x₃.
Answer: (i) For two variables, the table is:

(ii) For three variables, the table is:

In simple words: Work through each row by evaluating the expression with those input values - fill intermediate columns to track your work.

Exam Tip: For n variables, the table has 2^n rows - two variables give 4 rows, three give 8 rows, and so on.

Example 3. Define a boolean function f on boolean algebra {0, 1} corresponding to the expression x + y′. Give its domain and range. Construct input/output table (or truth table).
Answer: We define f: B² → B as f(x, y) = x + y′, where x, y ∈ {0, 1}. The domain is B² = ({0, 1})² = {0, 1} × {0, 1} = {(0, 0), (0, 1), (1, 0), (1, 1)}. Computing each output: f(0, 0) = 0 + 0′ = 0 + 1 = 1; f(0, 1) = 0 + 1′ = 0 + 0 = 0; f(1, 0) = 1 + 0′ = 1 + 1 = 1; f(1, 1) = 1 + 1′ = 1 + 0 = 1. The range is {0, 1}.

Truth table:

In simple words: The domain includes all possible pairs of 0s and 1s for the two variables. The range is just {0, 1} because those are the only values the function can output in a boolean algebra.

Exam Tip: Always name the domain and range explicitly - examiners often ask for these separately.

Example 4. (i) If f (x, y, z) = xy + yz′ + x′yz in boolean algebra B = {0, 1}, evaluate f (0, 0, 0) and f (0, 1, 1). How many rows would the truth table have? (ii) Write a boolean expression in terms of x, y or their complements which has value 1 when x = 0, y = 1 and assumes value 0 otherwise.
Answer: (i) f(0, 0, 0) = (0)(0) + (0)(0′) + (0′)(0)(0) = 0 + (0)(1) + (1)(0)(0) = 0 + 0 + 0 = 0. f(0, 1, 1) = (0)(1) + (1)(1′) + (0′)(1)(1) = 0 + (1)(0) + (1)(1)(1) = 0 + 0 + 1 = 1. With 3 variables each having 2 possible values, the truth table has 2 × 2 × 2 = 8 rows.

(ii) The product x • y has value 1 only when x = 1 and y = 1; otherwise it is 0. We want output 1 only when x = 0 and y = 1. This matches x′y (NOT x AND y). A truth table confirms:

The expression x′y has value 1 only when x = 0 and y = 1, and is 0 in all other cases.
In simple words: To build an expression that is 1 in exactly one case, use the AND of the complements needed to match that case - if you want x = 0 and y = 1, use NOT x AND y, which is written as x′y.

Exam Tip: When constructing expressions for specific inputs, think backwards - what combination of variables and complements gives 1 only in that row? Multiply (AND) them together.