Let $A=(A,+,\cdot)=(A,\vee,\wedge)$ be a Boolean Algebra. To ensure that $\overline{x}=y$ is sufficient that:

  1. $x+y=1_A$.
  2. $x\cdot y=0_A\;\wedge\;x\neq0_A$.
  3. $x\cdot(x+y)=\overline{y}\cdot x+\overline{(y+x)}$
  4. None of the above.

I have some doubts.

First question

First of all, do we have to find $\text{??}$ in $\forall x,y\in A(\text{??}\to\overline{x}=y)$?

Second question

I think the correct answer is (3) because: \begin{align*} x\cdot(x+y)=\overline{y}\cdot x+\overline{(y+x)}&\implies x\wedge(x\vee y)=(\overline{y}\wedge x)\vee\overline{(y\vee x)}\\ &\implies x=(\overline{y}\wedge x)\vee(\overline{y}\wedge\overline{x})\\ &\implies x=\overline{y}\wedge(x\vee\overline{x})\\ &\implies x=\overline{y}\wedge1_A=\overline{y}\\ &\implies\overline{x}=\overline{\overline{y}}\implies\boxed{\overline{x}=y} \end{align*}

but I am not sure if I also have to discard the other possibilites (because we could find 2,3,... sufficient conditions, not only 1).

Third question

Can you help me finding counterexamples for (1), (2) and (4)?

For example for (1) I said $(D_6,\mid)$ where $D_6=\text{Divisors of $6$}=\{1,2,3,6\}$, which is a Boolean Algebra, and its Hasse diagram is:

Hasse diagram

but $\forall x,y\in A(x\vee y=1_A\to\overline{x}=y)$ is false. Indeed, take $x=2$ and $y=6$. Then $2\vee6=6$ but $\overline{2}=3\neq6$.

What about (2) and (4) (if my counterexample is correct)?


Your reasoning is right.

As for counter-examples for (1) and (2), and then (4) will follow, consider the three-element Boolean algebra.

For example, $(D_{30},|)$. Here, $12\vee 15=30$, which is the top, but $12\wedge15=3$ which is not the bottom, and so (1) is not sufficient.
Check that also $2\wedge3$ is the bottom, but $2\vee3$ is not the top, so that $2$ is not the complement of $3$; so (2) is not sufficient either.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.