# Element chasing style proof applied to Boolean algebra problem

I would like to apply an element chasing style proof to the following problem:

Let $P$, $Q$ and $R$ be elements of a Boolean algebra. Prove that if $$\tag 1 P + Q = P + R$$ and $$\tag 2 P \cdot Q = P \cdot R$$ then $$\tag 3 Q = R$$

Given (1) above we know the $F(P,Q) = P + Q$ and $F(P,R) = P + R$ are both boolean functions of degree 2. Let $B = \{1,0\}$, which is the set of all Boolean variables. Then if we let $P \in B$ be arbitrary, we know that (1) may hold where $Q \in B$ is arbitrary and where $R \in B$ is arbitrary. That is (1) holds where $Q$ and $R$ are the same elements of the set $B$ and where they are different elements of $B$.

However, given that we are told (2) above holds and if we let $P \in B$ be arbitrary, we know that by the Identity ($P\cdot 1=P$) and Domination laws ($P\cdot 0 = 0$) that (2) can only hold where $Q$ and $R$ are the same $\in$ in $B$ and not when they are different elements of the set $B$.

$\therefore$ (3) must hold which states $Q = R$

Please could I get some feedback on this proof. Is it okay to apply an element chasing style to a problem like this or are other ways preferred? Could someone comment on whether the proof above goes far enough to conclusively prove that Q = R given (1) and (2)? thanks

Thanks

-

If $P=0$ then statement (1) simplifies to $Q=R$.

If $P=1$ then statement (2) simplifies to $Q=R$.

So all you need is to justify the two rules of "simplify" above, using whtever axioms you have available in the Boolean algebra system you are using.

-
:Thanks for the post. However, I would like to know is my proof above not explicit enough? The proof maybe verbose but I tried to just use a step by step process to rigorously expose that given (1) and (2) that (3) must then be true..Any thoughts greatly appreciated? – bosra Nov 19 '12 at 21:52
From (2) and $P$ arbitrary, cannot get $Q=R$ since maybe $P=0$, in which case $PQ$ and $PR$ are both zero by domination, and so (using only (2)) we cannot conclude that $Q=R$. I couldn't easily follow your proof, which left me wondering how (1) ended up getting used. It seems to me you need to use both (1) and (2) to conclude $Q=R$, and as I say I couldn't easily follow the structure of your argument. Maybe start out with "case 1: $P=0$, etc" and another case 2 for $P=1$. – coffeemath Nov 19 '12 at 22:03
Ok thanks @ coffeemath. I will refactor the proof and come back with hopefully something that flows a lot better – bosra Nov 19 '12 at 22:28

Starting with the case where P = 0

We are told that (1) P + Q = P + R holds

$\therefore$ We know by the following identity and domination laws that Q = R.

     0 + 0 = 0 (identity)
0 + 1 = 1 (domination)


We are told that (2) P.Q = P.R holds. If we investigate this in the absence of (1) we find that by the following identity and domination laws:

     0.0 = 0 (domination)
0.1 = 0 (identity)


that, given our assumption P = 0, that (2) holds when Q and R are the same or different values. However, given that we are told (1) and (2) hold, it can only be the case that Q and R are the same value.

We can use the same kind of logic to deduce that Q and R are equal when it is the case that P = 1. In order for (2) to hold, when P = 1, the following identity and domination laws reveal that Q must equal R.

     1.0 = 0 (domination)
1.1 = 1 (identity)


Given that we are told (1) and (2) hold, it can only be the case that (1) and (2) are satisfied when Q and R are the same value. $\therefore$ in order for (1) and (2) to hold (3) must hold too

    1 + 0 = 1 (identity)
1 + 1 = 1 (domination)


Please could someone review this post as I would like ensure the proof is solid?

Many thanks

-
It is OK but has more subcases than you need. In case P=0 you can use just assumption (1), since 0+x=x, so that "0+Q=0+R" already says "Q=R" after applying the law 0+x=x to both sides of "0+Q=0+R". Your case P=1 can also be done without two subcases, and can be finished using only assumption (2) and the law 1*x=x to both sides of "1*Q=1*R". To me the unnecessary extra subcases seem confusing to read, since one feels things are already shown without two subcases of each case P=0 and P=1. – coffeemath Nov 22 '12 at 2:34
ok thanks for the feedback @coffeemath – bosra Dec 5 '12 at 22:43