Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

2 Answers 2

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

share|improve this answer
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. –  coffeemath Nov 22 '12 at 2:34
    
ok thanks for the feedback @coffeemath –  bosra Dec 5 '12 at 22:43
add comment

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.

share|improve this answer
    
: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
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$. –  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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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