Problem 26 - Discrete Mathematics with Applications

Question

Define the operations \(+, \cdot,\) and \(^{\prime}\) on \(B=\\{0,1\\}\) as follows: \(x+y=\) \(\max \\{x, y\\}, x \cdot y=\min \\{x, y\\}, 0^{\prime}=1,\) and \(1^{\prime}=0 .\) Is \(\left\langle B,+, \cdot,,^{\prime}, 0,1\right\rangle \mathrm{a}\) boolean algebra?

Step-by-Step Solution

Answer

Yes, \((B, +, \cdot, \quad, 0, 1)\) is a Boolean algebra as it satisfies all the required properties: commutative law, associative law, identity element, absorption law, and complement laws for the given operations and set \(B=\{0,1\}\).

Step 1: Verify Commutative Law

To check if \(+, \cdot\) satisfy the commutative law, we need to test if \(x+y=y+x\) and \(x\cdot y=y\cdot x\) for all \(x, y \in B\). Since \(B=\{0, 1\}\), there are only four pairs of \((x, y):\) \((0, 0), (0, 1), (1, 0), (1, 1)\) to check. 1. \(0 + 0 = \max\{0, 0\} = 0\) and \(0 + 0 = 0\). 2. \(0 + 1 = \max\{0, 1\} = 1\) and \(1 + 0 = \max\{1, 0\} = 1\). 3. \(0\cdot0 = \min\{0,0\} =0\) and \(0\cdot0 = 0\) 4. \(1\cdot0 = \min\{1,0\} = 0\) and \(0\cdot1 =\min\{0,1\} = 0\) The commutative law holds for all pairs of \(x, y \in B\).

Step 2: Verify Associative Law

To check if \(+, \cdot\) satisfy the associative law, we need to verify if \((x+y)+z = x+(y+z)\) and \((x\cdot y)\cdot z = x\cdot (y\cdot z)\) for all \(x, y, z \in B\). Since \(B=\{0, 1\}\), we have 64 possible combinations of \((x, y, z)\). For \(+\): 1. \((0+0)+0 = 0+0 = 0\) and \(0+(0+0) = 0+0 = 0\) 2. \((0+0)+1 = 0+1 = 1\) and \(0+(0+1) = 0+1 = 1\) 3. \((1+0)+0 = 1+0 = 1\) and \(1+(0+0) = 1+0 = 1\) For \(\cdot\): 1. \((0\cdot0)\cdot0 = 0\cdot0 = 0\) and \(0\cdot(0\cdot0) = 0\cdot0 = 0\) 2. \((0\cdot0)\cdot1 = 0\cdot1 = 0\) and \(0\cdot(0\cdot1) = 0\cdot0 = 0\) 3. \((1\cdot0)\cdot0 = 0\cdot0 = 0\) and \(1\cdot(0\cdot0) = 1\cdot0 = 0\) The associative law holds for all \(x, y, z \in B\).

Step 3: Verify Identity Element

For the identity elements, we need to check that \(x+0=x\) and \(x\cdot 1=x\) for all \(x\in B\). 1. \(0+0 = \max\{0, 0\} = 0\), \(0\cdot 1=\min\{0, 1\} = 0\). 2. \(1+0 = \max\{1, 0\} = 1\), \(1\cdot 1 = \min\{1, 1\} = 1\). The identity element holds for all \(x \in B\).

Step 4: Verify Absorption Law

To verify the absorption law, we need to check if \(x[x\cdot y]=x\) and \(x\cdot(x+y)=x\) for all \(x, y \in B\). 1. \(0+[0\cdot0]=0+\min\{0, 0\}=0+0=0\) 2. \(0\cdot(0+0)=0\cdot(\max\{0, 0\})=0\cdot0=0\) 3. \(1+\min\{1, 0\}=1+0=1\) 4. \(1\cdot(1+0)=1\cdot(\max\{1, 0\})=1\cdot1=1\) The absorption law holds for all \(x, y \in B\).

Step 5: Verify Complement Laws

To verify the complement laws, we need to check if \(x+x^\prime=1\) and \(x\cdot x^\prime=0\) for all \(x \in B\). 1. \(0+0^\prime=0+1=\max\{0, 1\}=1\), \(0\cdot0^\prime=0\cdot1=\min\{0, 1\}=0\). 2. \(1+1^\prime=1+0=\max\{1, 0\}=1\), \(1\cdot1^\prime=1\cdot0=\min\{1, 0\}=0\). The complement laws hold for all \(x \in B\). Since all the required properties hold for the given operations and set \(B\), we can conclude that \((B, +, \cdot, \quad, 0, 1)\) is a Boolean algebra.

Key Concepts

Commutative Law

The Commutative Law is a fundamental property in Boolean algebra. It indicates that the order of values does not affect the result when performing certain operations, specifically addition (+) and multiplication (·). In other words:

• For addition: \(x + y = y + x\)
• For multiplication: \(x \cdot y = y \cdot x\)

This means we can swap the operands on either side of the operator without changing the outcome. When checking this law for set \(B = \{0, 1\}\), we test every possible pair of values. As demonstrated in the step-by-step solution, all combinations satisfy both the commutative properties for each operation, confirming that this law holds true for our Boolean algebra operations.

Associative Law

The Associative Law in Boolean algebra states that the grouping of variables does not affect the outcome. This applies to both addition and multiplication:

• For addition: \((x + y) + z = x + (y + z)\)
• For multiplication: \((x \cdot y) \cdot z = x \cdot (y \cdot z)\)

With this law, you can change how the values are grouped when adding or multiplying, allowing calculations in stages without affecting the final result. By checking all combinations of three elements from set \(B\), we find that the associative property is indeed maintained for both operations, as all checked examples yield the same outcome, regardless of how values are grouped.

Identity Element

The identity element in Boolean algebra refers to a special element that, when used in an operation with another element from the set, will return the other element unchanged. In Boolean algebra, these identity elements are:

• For addition (max operation): The identity is 0, since \(x + 0 = x\)
• For multiplication (min operation): The identity is 1, since \(x \cdot 1 = x\)

In simple terms, 0 does not change any value when added, and 1 does not change any value when multiplied. These straightforward properties ensure that every element in the set retains its own characteristics under these conditions, as confirmed by the given solution for each \(x\) in \(B\).

Complement Laws

Complement Laws revolve around the idea that each element has a unique complement in Boolean algebra, leading to very specific interactions:

• Addition with complement to achieve 1: \(x + x' = 1\)
• Multiplication with complement to achieve 0: \(x \cdot x' = 0\)

Here, \(x'\) represents the complement or opposite value of \(x\), where the complement of 0 is 1, and the complement of 1 is 0. These laws guarantee that any number combined with its opposite (complement) will always result in the total set value of 1 for addition or will cancel out to zero for multiplication. In checking these laws for each element in \(B\), we observe that the outcomes consistently follow these rules, proving the validity of the complement laws in this Boolean setup.