0

I am new to boolean algebra questions so if anyone can help me pointing out thinking errors (if there are any) that would be fantastic. I am trying to solve the following:

if x ⊔ y' = 1 then x ⊔ y = x

Definitions:

The problem with operators ⊔ and ⊓ is a boolean algebra

y' = complement of y

1 and 0 are the identity elements: a ⊔ 1 = 1, a ⊓ 0 = 1, these properties must hold for every element from a set.

a ⊔ 0 = a

a ⊔ a' = 1

Proof

Based on the definitions I first want to look at x ⊔ y' = 1. From our given definitions there are two ways in which this can be the case. The first way is if y' = x'. The second way is if y' = 1.

1. If y' = x' then from definition a ⊔ a' = 1 it follows that x ⊔ y = x because: x ⊔ x' = x (idempotence).

2. If y' = 1 then it follows that x = y' can be rewritten as x ⊔ 1' which can be rewritten as x ⊔ 0 which equals x.

This shows that if x ⊔ y' = 1 then x ⊔ y = x.

Note: I am aware that the same problem has already been asked, I am trying to verify my different solution.

Link: Prove that: if $x \sqcup \bar{y}=1$, then $x \sqcup y=x$ (in a Boolean algebra)

Community
  • 1
EconAleks
  • 1

1 Answers1

1

Your proof is wrong in several ways.

  1. First, from $x \vee y' = 1$ it doesn't follow that $y' = x'$ or $y' = 1$. What follows is that $y' \geq x'$ and from there, $y \leq x$, yielding $x \vee y = x$.
  2. Then, in your case $y' = x'$ (not necessary), your reasoning is very confused: idempotency doesn't say that $x \vee x' = x$ (which wouldn't be true); it says that $x \vee x = x$. So perhaps you would like to argue there that if $y' = x'$, then $y = y'' = x'' = x$, yielding $x \vee y = x \vee x = x$ (by idempotency).
  3. In the case $y' = 1$, it doesn't follow that $x = y'$. Again you seem to hammer a bit your reasoning in order to get to the desired conclusion. I say this because you eventually write $x \vee y = x \vee 0 = x$, which is about right since $y' = 1$ implies that $y=0$.

All in all, it seems that you know more or less what you should use, but make a terrible mess when trying to write down your reasoning.
Perhaps you don't suffer from this problem in other areas and you just need to get your hands on approach in order to write down your ideas more fluently.

amrsa
  • 12,917