0
$\begingroup$

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

2 Answers 2

2

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.

  • 0
    :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?2012-11-19
  • 1
    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$.2012-11-19
  • 0
    Ok thanks @ coffeemath. I will refactor the proof and come back with hopefully something that flows a lot better2012-11-19
0

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

  • 1
    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.2012-11-22
  • 0
    ok thanks for the feedback @coffeemath2012-12-05