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
    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

  • 0
    ok thanks for the feedback @coffeemath2012-12-05