This document contains my solutions to the Chapter 2 exercises.
Which of the following rules are operations on the indicated set? (\({\mathbb{Z}{}}\) designates the set of the integers, \({\mathbb{Q}{}}\) the rational numbers, and \({\mathbb{R}{}}\) the real numbers.) For each rule which is not an operation, explain why it is not.
Example \(a * b = \displaystyle \frac{a + b}{ab}\), on the set \({\mathbb{Z}{}}\).
Solution This is not an operation on \({\mathbb{Z}{}}\). There are integers \(a\) and \(b\) such that \((a+b)/ab\) is not an integer. (For example,
is not an integer.) Thus, \({\mathbb{Z}{}}\) is not closed under \(*\).
-
\(a*b = \sqrt{|ab|}\), on the set \({\mathbb{Q}{}}\).
Solution This is not an operation on \({\mathbb{Q}{}}\). Here is a counter example: \(2*1 = \sqrt{|2 \cdot 1|} = \sqrt{2}\). The result is an irrational number, and therefore \({\mathbb{Q}{}}\) is not closed under \(*\).
-
\(a*b = a \ln b\), on the set \(\{x \in {\mathbb{R}{}}: x > 0\}\).
Solution This is not an operation because it is not closed. A counter example is obtained by choosing \(a=1\) and \(b=0.5\): \(1 * 0.5 = \ln 0.5 \approx -0.693 < 0\).
-
\(a*b\) is a root of the equation \(x^2 - a^2 b^2 = 0\), on the set \({\mathbb{R}{}}\).
Solution This is not an operation because it is not uniquely defined. If we pick \(a=2,b=2\) then we have \(x^2 - 2^2 \cdot 2^2 = 0\). The roots of that equation are \(x = \pm 4\). This means that \(a*b\) is not uniquely defined, therefore \(*\) is not an operation.
-
Subtraction, on the set \({\mathbb{Z}{}}\).
Solution This is an operation. It is defined for all pairs \(\{(a,b) : a,b \in {\mathbb{Z}{}}\}\), it is uniquely defined for each pair, and it is closed.
-
Subtraction, on the set \(\{ n \in {\mathbb{Z}{}}: n \ge 0\}\).
Solution This is not an operation because it is not closed: \(4*10 = 4 - 10 = -4 < 0\).
-
\(a * b = |a-b|\), on the set \(\{ n \in {\mathbb{Z}{}}: n \ge 0\}\).
Solution This is an operation. It is defined for all pairs \(\{(a,b) : a,b \in {\mathbb{Z}{}}, a \ge 0, b \ge 0\}\). It is uniquely defined for each pair, and it is closed.
Each of the following is an operation \(*\) on \({\mathbb{R}{}}\). Indicate whether or not
-
it is commutative,
-
it is associative,
-
\({\mathbb{R}{}}\) has an identity element with respect to \(*\),
-
every \(x \in {\mathbb{R}{}}\) has an inverse with respect to \(*\).
Instructions For i, compute \(x * y\) and \(y * x\), and verify whether or not they are equal. For ii, compute \(x * (y * z)\) and \((x * y) * z\), and verify whether or not they are equal. For iii, first solve the equation \(x * e = x\) for \(e\); if the equation caonnot be solved, there is no identity element. If it can be solved, it is still necessary to check that \(e*x=x*e=x\) for any \(x\in {\mathbb{R}{}}\). If it checks, then \(e\) is an identity element. For iv, first note that if there is no identity element, there can be no inverses. If there is an identity element \(e\), first solve the equation \(x*x'=e\) for \(x'\); if the equation cannot be solved, \(x\) does not have an inverse. If it can be solved, check to make sure that \(x*x'=x'*x=e\). If this checks, \(x'\) is the inverse of \(x\).
Example \(x * y = x + y + 1\)
| Associative | Commutative | Identity | Inverses |
|---|---|---|---|
Yes \(\boxtimes \quad\) No \(\square\) |
Yes \(\boxtimes \quad\) No \(\square\) |
Yes \(\boxtimes \quad\) No \(\square\) |
Yes \(\boxtimes \quad\) No \(\square\) |
-
\(x * y = x + y + 1;\quad y * x = y + x + 1 = x + y + 1\).
(Thus, \(*\) is commutative.) -
\(x * (y * z) = x * (y + z + 1) = x + (y + z + 1) + 1 = x + y + z + 2\). \((x * y) * z = (x + y + 1) * z = (x + y + 1) + z + 1 = x + y + z + 2\).
(\(*\) is associative.) -
Solve \(x * e = x\) for \(e\):
\(x * e = x + e + 1 = x\); therefore \(e = -1\).
Check: \(x * (-1) = x + (-1) + 1 = x\); \((-1) * x = (-1) + x + 1 = x\).
Therefore, \(-1\) is the identity element.
(\(*\) has an identity element.) -
Solve \(x * x' = e\) for \(x'\):
\(x * x' = x + x' + 1 = -1\); therefore \(x' = -x - 2\).
Check: \(x * (-2 - x) = x + (-2 - x) + 1 = -1\); \((-2 - x) * x = (-2 - x) + x + 1 = -1\).
Therefore, \(-x - 2\) is the inverse of \(x\).
(Every element has an inverse.)
-
\(x*y = x + 2y + 4\)
Associative Commutative Identity Inverses Yes \(\square \quad\) No \(\boxtimes\)
Yes \(\square \quad\) No \(\boxtimes\)
Yes \(\square \quad\) No \(\boxtimes\)
Yes \(\square \quad\) No \(\boxtimes\)
Solution The solution follows:
-
The operation is not commutative
\[\begin{aligned} x * y & = x + 2y + 4 \\ y * x & = y + 2x + 4 \\ & = 2x + y + 4 \end{aligned}\]Now choose \(x=0\) and \(y=1\) and we see that
\[\begin{aligned} 0 * 1 & = 0 + 2 + 4 \\ & = 6 \\ 1 * 0 & = 1 + 0 + 4 \\ & = 5 \end{aligned}\](\(*\) is not commutative.)
-
The operation is not associative
\[\begin{aligned} x * (y * z) & = x * (y + 2z + 4) \\ & = x + 2(y + 2z + 4) + 4 \\ & = x + 2y + 4z + 12 \\ \text{therefore} \quad -4z - 12 & = x + 2y \\ (x * y) * z & = (x + 2y + 4) * z \\ & = (x + 2y + 4) + 2z + 4 \\ & = x + 2y + 2z + 8 \\ \text{therefore} \quad -2z - 8 & = x + 2y \\ \end{aligned}\]From this we can see that the two ways to associate can only be equal under the condition that \(-4z - 12 = -2z - 8\), or only when \(z=-2\). So let’s choose a combination of values where \(z \ne -2\): \(\{ x = 0, y = 0, z = 0 \}\)
\[\begin{aligned} 0 * (0 * 0) & = 0 * (0 + 2 \cdot 0 + 4) \\ & = 0 * 4 \\ & = 0 + 2 \cdot 4 + 4 \\ & = 12 \\ (0 * 0) * 0 & = (0 + 2 \cdot 0 + 4) * 0 \\ & = 4 * 0 \\ & = 4 + 2 \cdot 0 + 4 \\ & = 8 \end{aligned}\](\(*\) is not associative)
-
Check to see if their is an identity element:
\[\begin{aligned} x * e & = x \\ x * e & = x + 2e + 4 \\ x & = x + 2e + 4 \\ 0 & = 2e + 4 \\ 2e & = -4 \\ e & = -2 \end{aligned}\]Now check to see if \(x*e=e*x=x\):
\[\begin{aligned} x * -2 & = x + (2)(-2) + 4 \\ & = x - 4 + 4 \\ & = x \\ -2 * x & = -2 + 2x + 4 \\ & = 2x + 2 \end{aligned}\]We can see \(x*e \ne e*x\) therefore there is no identity element.
-
No need to check for an inverse. There is no identity.
-
-
\(x * y = x + 2y - xy\)
Associative Commutative Identity Inverses Yes \(\square \quad\) No \(\boxtimes\)
Yes \(\square \quad\) No \(\boxtimes\)
Yes \(\square \quad\) No \(\boxtimes\)
Yes \(\square \quad\) No \(\boxtimes\)
Solution The solution follows:
-
The operation is not commutative:
\[\begin{aligned} x * y & = x + 2y - xy \\ y * x & = y + 2x - yx \\ & = 2x + y - xy \\ & = (x + 2y - xy) + x - y \\ & = (x * y) + x - y \end{aligned}\]So if \(x * y = y * x\) then \(x * y = x * y + x - y\) which means \(0 = x - y\) which requires that \(x = y\). So in general \(*\) is not commutative. Check with \(\{ x = 0, y = 1 \}\):
\(0 * 1 = 0 + 2 \cdot 1 - 0 \cdot 1 = 2\)
\(1 * 0 = 1 + 2 \cdot 0 - 1 \cdot 0 = 1\) -
The operation is not associative. Check with \(\{ x = 0, y = 0, z = 1 \}\):
\[\begin{aligned} 0 * (0 * 1) & = 0 * (0 + 2 \cdot 1 - 0 \cdot 1) \\ & = 0 * 2 \\ & = 0 + 2 \cdot 2 - 0 \cdot 1 \\ & = 4 \\ (0 * 0) * 1 & = (0 + 2 \cdot 0 - 0 \cdot 0) * 0 \\ & = 0 * 1 \\ & = 0 + 2 \cdot 1 - 0 \cdot 1 \\ & = 2 \end{aligned}\] -
From the following we can see that \(e=0\).
\[\begin{aligned} x * e & = x \\ x * e & = x + 2e - xe \\ x & = x + 2e - xe \notag \\ 0 & = 2e - xe \notag \\ e(2-x) & = 0 \notag \\ e & = 0 \quad (\text{when } x \ne 2) \\ \end{aligned}\](We need to check what happens when \(x = 2\): we have \(2*y=2+2y-2y=2\). So when \(x=2\), \(x*y\) is always equal to 2 no matter what \(y\) is.)
Now we must check that \(x*e=e*x=x\):
\[\begin{aligned} e * x & = e + 2x - ex \\ & = 0 + 2x - 0 \\ & = 2x \\ & \ne x \end{aligned}\]Therefore, there is no identity element.
-
Since there is no identity element, there are no inverses.
-
-
\(x * y = | x + y |\)
Associative Commutative Identity Inverses Yes \(\square \quad\) No \(\boxtimes\)
Yes \(\boxtimes \quad\) No \(\square\)
Yes \(\square \quad\) No \(\boxtimes\)
Yes \(\square \quad\) No \(\boxtimes\)
Solution The solution follows:
-
From the following we can see that the operation is commutative:
\[\begin{aligned} x * y & = | x + y | \\ y * x & = | y + x | \\ & = | x + y | \end{aligned}\] -
It is not associative. Here is a counter example using \(x = 7, y = -13, z = 1\)
\[\begin{aligned} x * (y * z) & = 7 * \lvert -13 + 1 \rvert \\ & = \lvert 7 + 12 \rvert \notag \\ & = 19 \notag \\ (x * y) * z & = \lvert 7 + -13 \rvert * 1 \\ & = \lvert -6 \rvert * 1 \notag \\ & = \lvert 6 + 1 \rvert \notag \\ & = 7 \notag \\ & \ne 19 \notag \end{aligned}\] -
The value of \(0\) works as an identity element for non-negative numbers. However, there is no possible identity element for negative numbers. This is because the result of the absolute value function always returns non-negative values.
-
Since there is no identity element, there are no inverses.
-
-
\(x * y = | x - y |\)
Associative Commutative Identity Inverses Yes \(\square \quad\) No \(\boxtimes\)
Yes \(\boxtimes \quad\) No \(\square\)
Yes \(\square \quad\) No \(\boxtimes\)
Yes \(\square \quad\) No \(\boxtimes\)
Solution The solution is as follows:
-
The operation is commutative:
\[\begin{aligned} x * y & = | x - y | \\ & = \begin{cases} x - y, & \text{if } x \ge y; \\ y - x, & \text{otherwise.} \end{cases} \\ y * x & = | y - x | \\ & = \begin{cases} x - y, & \text{if } x \ge y; \\ y - x, & \text{otherwise.} \end{cases} \end{aligned}\] -
The operation is not associative. A counter example is provided by choosing \(x = 1, y = -2, z = 3\).
\[\begin{aligned} x * (y * z) & = 1 * |(-2) - 3| \\ & = 1 * 5 \notag \\ & = | 1 - 5 | \notag \\ & = 4 \notag \\ (x * y) * z & = | 1 - (-2) | * 3 \\ & = 3 * 3 \notag \\ & = | 3 - 3 | \notag \\ & = 0 \notag \\ & \ne 4 \notag \end{aligned}\] -
Again, there can be no identity element, since the result of the operation is always non-negative. Therefore, there can be no number \(x * e = x\) for \(x < 0\).
-
Since there is no identity element, there can be no inverse.
-
-
\(x*y = xy + 1\)
Associative Commutative Identity Inverses Yes \(\square \quad\) No \(\boxtimes\)
Yes \(\boxtimes \quad\) No \(\square\)
Yes \(\square \quad\) No \(\boxtimes\)
Yes \(\square \quad\) No \(\boxtimes\)
Solution The solution is as follows:
-
The operation is commutative as seen below.
\[\begin{aligned} x * y & = xy + 1 \\ y * x & = yx + 1 \\ & = xy + 1 \quad\text{(Multiplication is commutative.)} \end{aligned}\] -
The operation is not associative as seen below.
\[\begin{aligned} x * (y * z) & = x * (yz + 1) \\ & = x(yz + 1) + 1 \\ & = x + xyz + 1 \\ (x * y) * z & = (xy + 1) * z \\ & = (xy + 1)z + 1 \\ & = z + xyz + 1 \\ & \ne x + xyz + 1 \end{aligned}\] -
We can see below that their is no constant value defined for the identity element. Our equations find a formula for \(e\) which depens on \(x\). This is not a constant value.
\[\begin{aligned} x * e & = x \\ x * e & = xe + 1 \\ x & = xe + 1 \\ x - 1 & = xe \\ xe & = x - 1 \\ e & = \frac{x - 1}{x} \\ \end{aligned}\] -
There is no identity element, so there is no inverse.
-
-
\(x * y = \max\{x,y\} =\) the larger of the two numbers \(x\) and \(y\).
Associative Commutative Identity Inverses Yes \(\boxtimes \quad\) No \(\square\)
Yes \(\boxtimes \quad\) No \(\square\)
Yes \(\square \quad\) No \(\boxtimes\)
Yes \(\square \quad\) No \(\boxtimes\)
Solution The solution is as follows.
-
The operation is commutative.
\[\begin{aligned} x * y & = \max\{x,y\} \\ & = \begin{cases} x, & \text{if } x \ge y; \\ y, & \text{otherwise.} \end{cases} \\ y * x & = \max\{y,x\} \\ & = \begin{cases} x, & \text{if } x \ge y; \\ y, & \text{otherwise.} \end{cases} \end{aligned}\] -
The operation is associative.
\[\begin{aligned} x * (y * z) & = x * \max\{y,z\} \\ &= \max\{x, \max\{y,z\}\} \\ &= \begin{cases} \max\{x, y\}, \text{if } y \ge z; \\ \max\{x, z\}, \text{otherwise.} \end{cases} \\ & = \begin{cases} x, & \text{if } x \ge y \land x \ge z; \\ y, & \text{if } x < y \land y \ge z; \\ z, & \text{otherwise.} \end{cases} \\ (x * y) * z & = \max\{x,y\} * z \\ & = \max\{\max\{x,y\}, z\} \\ & = \begin{cases} \max\{x,z\}, \text{if } x \ge y; \\ \max\{y,z\}, \text{otherwise.} \end{cases} \\ & = \begin{cases} x, & \text{if } x \ge y \land x \ge z; \\ y, & \text{if } x < y \land y \ge z; \\ z, & \text{otherwise.} \end{cases} \\ \end{aligned}\] -
There is no identity element. We will prove this by contradiction. Assume that there is some identity element \(e\). Then by definition \(x * e = x\) for all \(x\). Let us choose a value \(m = e - 1\). Then we have \(m * e = (e-1) * e = \max(e-1,e) = e \ne m\). Therefore, \(e\) is not an identity element.
-
Since there is no identity element, there are no inverses.
-
-
\(\displaystyle x * y = \frac{xy}{x + y + 1}\) on the set of positive real numbers.
Solution The solution is as follows
-
The operation is commutative.
\[\begin{aligned} x * y & = \frac{xy}{x + y + 1} \\ y * x & = \frac{yx}{y + x + 1} \\ & = \frac{xy}{x + y + 1} && (+,\cdot \text{ are commutative}) \end{aligned}\] -
The operation is not associative. This can be demonstrated with the values \(x = 2, y = 3, z = 4\).
\[\begin{aligned} 2 * (3 * 4) & = 2 * \frac{3 \cdot 4}{3 + 4 + 1} \\ & = 2 * (3/2) \\ & = \frac{2 \cdot (3/2)}{2 + (3/2) + 1} \\ & = \frac{6/2}{9/2} \\ & = \frac{6}{9} \\ & = \frac{2}{3} \\ (2 * 3) * 4 & = \frac{2 \cdot 3}{2 + 3 + 1} * 4 \\ & = \frac{6}{7} * 4 \\ & = \frac{(6/7) \cdot 4}{(6/7) + 4 + 1} \\ & = \frac{24/7}{41/7} \\ & = \frac{24}{41} \end{aligned}\] -
There is no identity element. As a matter of fact, the equation \(x * e = x\) can only be solved when \(x = 0\) or \(x = -1\), as shown below.
\[\begin{aligned} \frac{ex}{e + x + 1} & = x \\ ex & = x^2 + ex + x \\ x^2 + ex + x & = ex \\ x^2 + x & = 0 \\ x(x+1) & = 0 \\ x & = 0, -1 \end{aligned}\] -
Since there is no identity, there can be no inverses.
-
Let \(A\) be the two-element set \(A = \{a,b\}\).
-
Write the tables of all 16 operations on \(A\). (Use the format explained on page 20.) Label these operations \(O_1\) to \(O_{16}\).
Solution The tables are shown below:
\(O_{16}\) \begin{array}{cc} (x,y) & x*y \\\hline (a,a) & a \\ (a,b) & a \\ (b,a) & a \\ (b,b) & a \\ \end{array}
\(O_1\) \begin{array}{cc} (x,y) & x*y \\\hline (a,a) & a \\ (a,b) & a \\ (b,a) & a \\ (b,b) & b \\ \end{array}
\(O_2\) \begin{array}{cc} (x,y) & x*y \\\hline (a,a) & a \\ (a,b) & a \\ (b,a) & b \\ (b,b) & a \\ \end{array}
\(O_3\) \begin{array}{cc} (x,y) & x*y \\\hline (a,a) & a \\ (a,b) & a \\ (b,a) & b \\ (b,b) & b \\ \end{array}
\(O_4\) \begin{array}{cc} (x,y) & x*y \\\hline (a,a) & a \\ (a,b) & b \\ (b,a) & a \\ (b,b) & a \\ \end{array}
\(O_5\) \begin{array}{cc} (x,y) & x*y \\\hline (a,a) & a \\ (a,b) & b \\ (b,a) & a \\ (b,b) & b \\ \end{array}
\(O_6\) \begin{array}{cc} (x,y) & x*y \\\hline (a,a) & a \\ (a,b) & b \\ (b,a) & b \\ (b,b) & a \\ \end{array}
\(O_7\) \begin{array}{cc} (x,y) & x*y \\\hline (a,a) & a \\ (a,b) & b \\ (b,a) & b \\ (b,b) & b \\ \end{array}
\(O_8\) \begin{array}{cc} (x,y) & x*y \\\hline (a,a) & b \\ (a,b) & a \\ (b,a) & a \\ (b,b) & a \\ \end{array}
\(O_9\) \begin{array}{cc} (x,y) & x*y \\\hline (a,a) & b \\ (a,b) & a \\ (b,a) & a \\ (b,b) & b \\ \end{array}
\(O_{10}\) \begin{array}{cc} (x,y) & x*y \\\hline (a,a) & b \\ (a,b) & a \\ (b,a) & b \\ (b,b) & a \\ \end{array}
\(O_{11}\) \begin{array}{cc} (x,y) & x*y \\\hline (a,a) & b \\ (a,b) & a \\ (b,a) & b \\ (b,b) & b \\ \end{array}
\(O_{12}\) \begin{array}{cc} (x,y) & x*y \\\hline (a,a) & b \\ (a,b) & b \\ (b,a) & a \\ (b,b) & a \\ \end{array}
\(O_{13}\) \begin{array}{cc} (x,y) & x*y \\\hline (a,a) & b \\ (a,b) & b \\ (b,a) & a \\ (b,b) & b \\ \end{array}
\(O_{14}\) \begin{array}{cc} (x,y) & x*y \\\hline (a,a) & b \\ (a,b) & b \\ (b,a) & b \\ (b,b) & a \\ \end{array}
\(O_{15}\) \begin{array}{cc} (x,y) & x*y \\\hline (a,a) & b \\ (a,b) & b \\ (b,a) & b \\ (b,b) & b \\ \end{array}
-
Identify which of the operations \(O_1\) to \(O_{16}\) are commutative.
Solution This can be solved very easily by looking at the second and third entries in each table to see if \(a*b=b*a\). The commutative entries are \(O_1, O_6, O_7, O_8, O_9, O_{14}, O_{15}, O_{16}\). commutative.
-
Identify which operations, among \(O_1\) to \(O_{16}\), are associative.
Solution There are eight cases to check for each operation. They are identified and labelled here.
\(\begin{aligned} a * (a * a) & = (a * a) * a && 1\\ a * (a * b) & = (a * a) * b && 2\\ a * (b * a) & = (a * b) * a && 3\\ a * (b * b) & = (a * b) * b && 4\\ b * (a * a) & = (b * a) * a && 5\\ b * (a * b) & = (b * a) * b && 6\\ b * (b * a) & = (b * b) * a && 7\\ b * (b * b) & = (b * b) * b && 8 \end{aligned}\)
If an operation is commutative then only cases 2 and 4 actually need to be checked. The rest can be proven just with the fact that they are commutative. This is proven by the following list of proofs (except for cases 2 and 4 which must be checked).
Case 1: \begin{aligned} a * (a * a) & = (a * a) * a && \text{(Commutativity)} \end{aligned}
Case 2: \begin{aligned} a * (a * b) & = (a * a) * b && \text{Must be checked} \end{aligned}
Case 3: \begin{aligned} a * (b * a) & = a * (a * b) && \text{(Commutativity)} \\ & = (a * b) * a && \text{(Commutativity)} \end{aligned}
Case 4: \begin{aligned} a * (b * b) & = (a * b) * b && \text{Must be checked} \end{aligned}
Case 5: Assuming Case 2 is shown to be true for an operation then this is true: \begin{aligned} b * (a * a) & = (a * a) * b && \text{(Commutativity)} \\ & = a * (a * b) && \text{(By case 2)} \\ & = a * (b * a) && \text{(Commutativity)} \\ & = (b * a) * a && \text{(Commutativity)} \end{aligned}
Case 6: \begin{aligned} b * (a * b) & = b * (b * a) && \text{(Commutativity)} \\ & = (b * a) * b && \text{(Commutativity)} \end{aligned}
Case 7: Assuming Case 4 is shown to be true for an operation then this is true: \begin{aligned} b * (b * a) & = b * (a * b) && \text{(Commutativity)} \\ & = (a * b) * b && \text{(Commutativity)} \\ & = a * (b * b) && \text{(By case 4)} \\ & = (b * b) * a && \text{(Commutativity)} \end{aligned}
Case 8: \begin{aligned} b * (b * b) & = (b * b) * b && \text{(Commutativity)} \end{aligned}
Now we need to start checking all the cases.
\(\mathbf{O_1}\): This operation is commutative. Cases 2 and 4 are true, so this operation is associative.
\begin{aligned} a *_1 (a *_1 b) & = a *_1 a && (O_1)\\ & = a && (O_1)\\ (a *_1 a) *_1 b & = a *_1 b && (O_1)\\ & = a && (O_1) \end{aligned} Case 4 Proof: \begin{aligned} a *_1 (b *_1 b) & = a *_1 b && (O_1)\\ & = a (O_1)\\ (a *_1 b) *_1 b & = a *_1 b && (O_1)\\ & = a && (O_1) \end{aligned}Case 2 Proof:
\(\mathbf{O_2}\): This operation is not commutative. Therefore there are eight cases to check. Rather than check them all, we’ll use boolean algebra. We assume \(a\) is the value
falseand \(b\) is the valuetrue. Then the operation is equivalent to the boolean equation \(x\land \lnot y\). Here are the equations for \(x * (y * z)\) and \((x * y) * z\).\[\begin{aligned} x * (y * z) & = x * (y \land \lnot z) \\ & = x \land \lnot(y \land \lnot z)\\ & = x \land (\lnot y \lor z) \\ (x * y) * z & = (x \land \lnot y) * z \\ & = (x \land \lnot y) \land \lnot z \\ & = x \land \lnot y \land \lnot z \end{aligned}\]\begin{aligned} f \land \lnot s & = x \land (\lnot y \lor z) \land \lnot (x \land \lnot y \land \lnot z))\\ & = (x \land \lnot y \lor x \land z) \land (\lnot x \lor y \lor z) \\ & = (x \land y \land z) \lor (x \land \lnot y \land z) \lor (x \land z) \\ & = (x \land z) \land (y \lor \lnot y \lor \top) \\ & = x \land z \end{aligned}Now we need to find a difference. So we’ll find values for \(x,y,z\) where the first equation evalutes to a different value than the second equation. We’ll do this with an equation of the form \(f \land \lnot s\) where \(f\) is the first equation and \(s\) is the second equation.
\begin{aligned} b * (a * b) & = b * a \\ & = b \\ (b * a) * b & = b * b \\ & = a \\ & \ne b \end{aligned}So the two formulas differ when \(x = b, z = b\). Let’s check.
Therefore this operation is not associative.
\begin{aligned} x * (y * z) & = x * y \\ & = x \\ (x * y) * z & = x * z \\ & = x \end{aligned}\(\mathbf{O_3}\): This operation is equivalent to the equation \(x * y = x\). This can be seen by observing the table for \(O_3\). With this information we can easily check to see if the operation is associative.
Both equations evaluate to \(x\) so we can see that \(O_3\) is associative.
\begin{aligned} x * (y * z) & = x * (\lnot y \land z) \\ & = \lnot x \land \lnot y \land z \\ (x * y) * z & = (\lnot x \land y) * z \\ & = \lnot (\lnot x \land y) \land z \end{aligned}\(\mathbf{O_4}\): This operation is not commutative. It is equivalent to the equation \(x * y = \lnot x \land y\).
\begin{aligned} s \land \lnot f & = (\lnot (\lnot x \land y) \land z) \land \lnot (\lnot x \land \lnot y \land z ) \\ & = (x \lor \lnot y) \land z \land (x \lor y \lor \lnot z) \\ & = (x \lor \lnot y) \land ((x \land z) \lor (y \land z) \lor \bot)\\ & = (x \land z) \lor (x \land y \land z) \lor (\lnot y \land x \land z) \lor (\lnot y \land y \land z) \\ & = (x \land z) \land (\top \lor y \lor \lnot y) \\ & = x \land z \end{aligned}Let’s find a set of values where the second formula is true but the first is not: \(s \land \lnot f\).
\begin{aligned} b * (b * b) & = b * a \\ & = a \\ (b * b) * b & = a * b \\ & = b \\ & \ne a \end{aligned}When \(x = b, z = b\) we find a difference, therefore \(O_4\) is not associative.
\begin{aligned} x * (y * z) & = x * z \\ & = z \\ (x * y) * z & = y * z \\ & = z \end{aligned}\(\mathbf{O_5}\): This is not commutative either. It is equivalent to \(x * y = y\). It is associative. We can see this since both formulas evaluate to the same thing.
\begin{aligned} a * (a * b) & = a * b && \text{(Left hand side of case 2.)}\\ & = b \\ (a * a) * b & = a * b && \text{(Right hand side of case 2.)}\\ & = b && \text{(Case 2 is true.)} \\ a * (b * b) & = a * a && \text{(Left hand side of case 4.)}\\ & = a \\ (a * b) * b & = b * b && \text{(Right hand side of case 4.)} \\ & = a && \text{(Case 4 is true.)} \end{aligned}\(\mathbf{O_6}\): This operation is commutative. We just have to check cases 2 and 4 from above. Below we see both cases are true, therefore this operation is associative.
\begin{aligned} a * (a * b) & = a * b && \text{(Left hand side of case 2.)}\\ & = b \\ (a * a) * b & = a * b && \text{(Right hand side of case 2.)}\\ & = b && \text{(Case 2 is true.)}\\ a * (b * b) & = a * b && \text{(Left hand side of case 4.)} \\ & = b \\ (a * b) * b & = b * b && \text{(Right hand side of case 4.)} \\ & = b && \text{(Case 4 is true.)} \end{aligned}\(\mathbf{O_7}\): This operation is commutative. Cases 2 and 4 are true, therefore this operation is associative.
\begin{aligned} a * (a * b) & = a * a && \text{(Left hand side of case 2.)} \\ & = b \\ (a * a) * b & = b * b && \text{(Right hand side of case 2.)} \\ & = a && \text{(Case 2 is false.)} \end{aligned}\(\mathbf{O_8}\): This operation is commutative. Case 2 is false, therefore this operation is not associative.
\begin{aligned} a * (a * b) & = a * a \\ & = b \\ (a * a) * b & = b * b \\ & = b && \text{(Case 2 is true.)} \\ a * (b * b) & = a * b \\ & = a \\ (a * b) * b & = a * b \\ & = a && \text{(Case 4 is true.)} \end{aligned}\(\mathbf{O_9}\): This operation is commutative. Cases 2 and 4 are true, therefore this operation is associative.
\begin{aligned} x * y & = \lnot y \\ x * (y * z) & = x * \lnot z \\ & = z \\ (x * y) * z & = \lnot y * z \\ & = \lnot z \\ & \ne z \end{aligned}\(\mathbf{O_{10}}\): This operation is not commutative. This operation corresponds to the boolean equation \(x * y = \lnot y\).
\begin{aligned} x * y & = x \lor (\lnot z \land \lnot y) \\ x * (y * z) & = x * (y \lor (\lnot y \land \lnot z)) \\ & = x \lor (\lnot x \land \lnot (y \lor (\lnot y \land \lnot z))) \\ & = x \lor (\lnot x \land (\lnot y \land \lnot (\lnot y \land \lnot z))) \\ & = x \lor (\lnot x \land (\lnot y \land (y \lor z))) \\ & = x \lor (\lnot x \land \lnot y \land y) \lor (\lnot x \land \lnot y \land z) \\ & = x \lor (\lnot x \land \lnot y \land z) \\ (x * y) * z & = (x \lor (\lnot x \land \lnot y) * z \\ & = (x \lor (\lnot x \land \lnot y) \lor (z \land (x \lor (\lnot x \land \lnot y))) \\ & = x \lor (\lnot x \land \lnot y) \lor (x \land z) \lor (\lnot x \land \lnot y \land z) \\ & = x \lor (\lnot x \land \lnot y) \end{aligned}\(\mathbf{O_{11}}\): This operation is not commutative. The equivalent binary equation is \(x * y = x \lor \lnot x \land \lnot y\).
\begin{aligned} a * (a * a) & = a * b \\ & = a \\ (a * a) * a & = b * a \\ & = b \end{aligned}One of the equations is true for \({x = a, y = a }\) and the other one is false for the same set of values. So this is our counter example to show that \(O_{11}\) is not associative.
\begin{aligned} x * y & = \lnot x \\ x * (y * z) & = x * \lnot y \\ & = \lnot x \\ (x * y) * z & = \lnot x * z \\ & = x \end{aligned}\(\mathbf{O_{12}}\): This operation is not commutative. Its boolean equivalent equation is \(x * y = \lnot x\). This operation is not associative. The two equations evaluate to different values.
\begin{aligned} a * (a * a) & = a * b \\ & = b \\ (a * a) * a & = b * a \\ & = a \end{aligned}\(\mathbf{O_{13}}\): This operation is not commutative. It’s boolean equivalent equation is \(x * y = \lnot x \lor (x \land y)\). Using calculations similar to the other problems we find a set of values that shows this operation is not associative. Choose \(x = a, y = a, z = a\).
\begin{aligned} a * (a * b) & = a * b \\ & = b \\ (a * a) * b & = b * b \\ & = a \end{aligned}\(\mathbf{O_{14}}\): This operation is commutative. Check cases 2 and 4. Case 2 is false. So this operation is not associative.
\(\mathbf{O_{15}}\): This operation is associative since it always evaluates to \(b\).
\(\mathbf{O_{16}}\): This operation is associative since it always evaluates to \(a\).
Finally we have the following operations are associative: \(O_1\), \(O_3\), \(O_5\), \(O_6\), \(O_7\), \(O_9\), \(O_{15}\), \(O_{16}\).
-
For which of the operations \(O_1\) to \(O_{16}\) is there an identity element?
Solution First We can rule out all operations that are not commutative.
TODO I think this logic is flawed. Just because an operation is not commutative doesn’t mean that it’s not commutative for \$e\$
This is because we require that \(x*e=e*x=x\). That leaves eight cases. Next we can rule out \(O_{15}\) and \(O_{16}\) because the former never returns a \(b\) value, and the latter never returns an \(a\) value. Then we can rule out \(O_8\) because there is no value of \(y\) such that \(b *_8 y = b\). Likewise, we can rule out \(O_{14}\) because there is no value of \(y\) such that \(a *_{14} y = a\). That leaves four operations for consideration: \(O_1, O_6, O_7\) and \(O_9\). It will be shown that each of these has an identity element.
\begin{aligned} O_1&= x \land y && \text{Operation 1} \\ & = x \land {\top}&& \text{Subst: } e_1 = {\top}\\ & = x && \square \\ O_6& = (\lnot x \land y) \lor (x \land \lnot y) && \text{Operation 6} \\ & = (\lnot x \land {\bot}) \lor (x \land \lnot {\bot}) && \text{Subst: } e_6 = {\bot}\\ & = {\bot}\lor (x \land {\top}) \\ & = x && \square \\ O_7& = x \lor y && \text{Operation 7} \\ & = x \lor {\bot}&& \text{Subst: } e_7 = {\bot}\\ & = x && \square \\ O_9& = (\lnot x \land \lnot y) \lor (x \land y) && \text{Operation 9} \\ & = (\lnot x \land \lnot {\top}) \lor (x \land {\top}) && \text{Subst: } e_9 = {\top}\\ & = (\lnot x \land {\bot}) \lor x \\ & = {\bot}\lor x \\ & = x && \square \end{aligned}The identity element of \(O_1\) is \(b\). This can be shown by noting \(a *_{1} b = b *_{1} a = a\) and \(b *_1 b = b\). The identity element of \(O_6\) is \(a\) because \(a *_6 a = a\) and \(b *_6 a = a *_6 b = b\). The identity element of \(O_7\) is \(a\). We can check that \(a *_7 a = a\) and \(b *_7 a = a *_7 b = a\). The identity element of \(O_9\) is \(b\). \(a *_9 b = b *_9 a = a\) and \(b *_9 b = b\). These results are validated using boolean algebra.
-
For which of the operations \(O_1\) to \(O_{16}\) does every element have an inverse?
Solution The answer is that only \(O_6\) and \(O_9\) provide inverses for every element.
As we saw in the last problem only 4 operations have an identity: \(O_1\), \(O_6\), \(O_7\) and \(O_9\). So, these are the only four operations we need to consider. \(O_1\) does not have an inverse for the value \(a\), as there is no value of \(y\) that makes the following equation true: \(a * y = b\). Likewise, \(O_7\) does not provide an inverse for the value \(b\) as there is no value for \(y\) which makes the following equation true: \(b * y = a\).
The remaining two operations do provide inverses for every element. For \(O_6\) we have that \(a^{-1} = a \text{ and } b^{-1} = b\). For \(O_9\) we have that \(a^{-1} = a \text{ and } b^{-1} = b\). In general for these two operations we have that \(x^{-1} = x\).
Digital computers and related machines proces information which is received in the form of input sequences. An input sequence is a finite sequence of symbols from some alphabet \(A\). For instance, if \(A=\{0,1\}\) (that is, if the alphabet consists of only the two symbols 0 and 1), then examples of input sequences are 011010 and 1010111. If \(A=\{a,b,c\}\), then examples of input sequences are babbcac and cccabaa. Output sequences are defined in the same way as input sequences. The set of all sequences of symbols in the alphabet \(A\) is denoted by \(A^*\).
There is an operation on \(A^*\) called concatenation: If \(\mathbf{a}\) and \(\mathbf{b}\) are in \(A^*\), say \(\mathbf{a} = a_1 a_2 \ldots a_n\) and \(\mathbf{b} = b_1 b_2 \ldots b_m\), then
In other words, the sequence \(\mathbf{ab}\) consists of the two sequences \(\mathbf{a}\) and \(\mathbf{b}\) end to end. For example, in the alphabet \(A=\{0,1\}\), if \(\mathbf{a} = 1001\) and \(\mathbf{b} = 010\), then \(\mathbf{ab} = 1001010\).
The symbol \(\lambda\) denotes the empty sequence.
-
Prove that the operation above is associative.
\begin{aligned} (\mathbf{ab})\mathbf{c} & = (a_1 a_2 \ldots a_r b_1 b_2 \ldots b_s)\mathbf{c}\\ & = a_1 a_2 \ldots a_r b_1 b_2 \ldots b_s c_1 c_2 \ldots c_t \\ \mathbf{a}(\mathbf{bc}) & = \mathbf{a}(b_1 b_2 \ldots b_s c_1 c_2 \ldots c_t)\\ & = a_1 a_2 \ldots a_r b_1 b_2 \ldots b_s c_1 c_2 \ldots c_t \square \end{aligned}Let \(\mathbf{a} = a_1 a_2 \ldots a_r\), and \(\mathbf{b} = b_1 b_2 \ldots b_s\), and \(\mathbf{c} = c_1 c_2 \ldots c_t\). Then we have
-
Explain why the operation is not commutative.
Solution It is not commutative because commutativity changes the order of the symbols in the resulting output sequence. For example, let \(\mathbf{a} = a_1 a_2 \ldots a_n\) and \(\mathbf{b} = b_1 b_2 \ldots b_m\). Then, as before, we have \(\mathbf{ab} = a_1 a_2 \ldots a_n b_1 b_2 \ldots b_m\). However, we get a different result for \(\mathbf{ba}\): \(\mathbf{ba} = b_1 b_2 \ldots b_m a_1 a_2 \ldots a_n\).
-
Prove that there is an identity element for this operation.
\begin{aligned} \mathbf{a}\lambda & = a_1 a_2 \ldots a_n \lambda \\ & = a_1 a_2 \ldots a_n && \text{Defn. of }\lambda \\ & = \mathbf{a} && \text{Defn. of }\mathbf{a} \\ \lambda\mathbf{a} & = \lambda a_1 a_2 \ldots a_n \\ & = a_1 a_2 \ldots a_n && \text{Defn. of }\lambda \\ & = \mathbf{a} && \text{Defn. of } \mathbf{a} \square \end{aligned}We choose the identity element, \(e\), to be the empty sequence \(\lambda\), and again choose \(\mathbf{a} = a_1 a_2 \ldots a_n\). Now we will demonstrate that \(e\) is indeed the identity element.